/* -*- C++ -*- */ /************************************************************************* * Copyright(c) 1995~2005 Masaharu Goto (cint@pcroot.cern.ch) * * For the licensing terms see the file COPYING * ************************************************************************/ // lib/prec_stl/vector #pragma ifndef PREC_STL_VECTOR #pragma define PREC_STL_VECTOR #pragma link off global PREC_STL_VECTOR; #pragma link C++ nestedtypedef; #pragma link C++ nestedclass; #if defined(G__HP_aCC) || defined(G__SUNPRO_CC) #pragma mask_newdelete 0x1c; #else #pragma mask_newdelete 0x10; #endif // Imported from ANSI/ISO C++ 1997/Nov draft // Got some ideas from Scott Snyder, Fermi-lab // Modified by Masaharu Goto // SGI KCC porting by Philippe Canal, Fermi-lab #include <_iterator> #include <_memory> #include <_utility> #if defined(G__AIX) template class _Ptrit; #endif #if defined(G__ANSIISOLIB) || (G__GNUC>=3) template > #elif defined(G__GNUC) && !defined(G__KCC) #if (G__GNUC_VER>=2095) template > #else template #endif #elif defined(G__HPUX) template #else template > #endif class vector { public: typedef T value_type; #if ((defined(G__GNUC) || defined(G__SGI)) && !defined(G__KCC)) || defined(G__HPUX) typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef size_t size_type; typedef ptrdiff_t difference_type; #else typedef typename Allocator::pointer pointer; typedef typename Allocator::const_pointer const_pointer; typedef typename Allocator::reference reference; typedef typename Allocator::const_reference const_reference; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; #endif #if defined(G__KCC) typedef typename Allocator::pointer iterator; typedef typename Allocator::const_pointer const_iterator; typedef Allocator allocator_type; typedef reverse_iterator reverse_iterator; typedef reverse_iterator const_reverse_iterator; #elif defined(G__AIX) typedef Allocator allocator_type; typedef _Ptrit iterator; typedef _Ptrit const_iterator; //class iterator; //class const_iterator; typedef typename std::reverse_iterator reverse_iterator; typedef typename std::reverse_iterator const_reverse_iterator; #elif (defined(G__SUN) && !defined(G__GNUC)) typedef T* iterator; typedef const T* const_iterator; typedef reverse_iterator const_reverse_iterator; typedef reverse_iterator reverse_iterator; #elif defined(G__VISUAL) && (G__MSC_VER>=1300) // CLASS const_iterator class const_iterator; friend class const_iterator; class const_iterator : public _Ranit { // iterator for nonmutable vector public: typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef Allocator::difference_type difference_type; //typedef const_pointer pointer; //typedef T* pointer; typedef Allocator::pointer pointer; typedef const pointer const_pointer; typedef const_reference reference; const_iterator(); #if (G__MSC_VER>=1310) //const_iterator(pointer _Ptr); const_iterator(T *const _Ptr); #endif const_reference operator*() const; const_pointer operator->() const; const_iterator& operator++(); const_iterator operator++(int); const_iterator& operator--(); const_iterator operator--(int); const_iterator& operator+=(difference_type _Off); const_iterator operator+(difference_type _Off) const; const_iterator& operator-=(difference_type _Off); const_iterator operator-(difference_type _Off) const; difference_type operator-(const const_iterator& _Right) const; const_reference operator[](difference_type _Off) const; bool operator==(const const_iterator& _Right) const; bool operator!=(const const_iterator& _Right) const; bool operator<(const const_iterator& _Right) const; bool operator>(const const_iterator& _Right) const; bool operator<=(const const_iterator& _Right) const; bool operator>=(const const_iterator& _Right) const; //friend const_iterator operator+(difference_type _Off, //const const_iterator& _Right); #if (G__MSC_VER>=1310) pointer _Myptr; // offset of element in vector #endif }; // CLASS iterator class iterator; friend class iterator; class iterator : public const_iterator { // iterator for mutable vector public: typedef random_access_iterator_tag iterator_category; typedef T value_type; typedef Allocator::diffrence_type difference_type; #if (G__MSC_VER>=1310) typedef Allocator::pointer pointer; #else typedef Allocator::reference *pointer; #endif typedef Allocator::reference reference; iterator(); #if (G__MSC_VER>=1310) iterator(pointer _Ptr); #endif reference operator*() const; pointer operator->() const; iterator& operator++(); iterator operator++(int); iterator& operator--(); iterator operator--(int); iterator& operator+=(difference_type _Off); iterator operator+(difference_type _Off) const; iterator& operator-=(difference_type _Off); iterator operator-(difference_type _Off) const; #if (G__MSC_VER>=1310) difference_type operator-(const const_iterator& _Right) const; #else difference_type operator-(const iterator& _Right) const; #endif reference operator[](difference_type _Off) const; //friend iterator operator+(difference_type _Off, //const iterator& _Right); }; typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; #elif (!defined(G__INTEL_COMPILER) && (G__GNUC_VER>3001)) #ifndef G__OLDIMPLEMENTATION1703 class iterator { public: iterator(); explicit iterator(const pointer& __i) ; // Allow iterator to const_iterator conversion template inline iterator(const iterator& __i); // Forward iterator requirements reference operator*() const ; pointer operator->() const ; iterator& operator++(); iterator operator++(int) ; // Bidirectional iterator requirements iterator& operator--() ; iterator operator--(int) ; // Random access iterator requirements reference operator[](const difference_type& __n) const; iterator& operator+=(const difference_type& __n); iterator operator+(const difference_type& __n) const; iterator& operator-=(const difference_type& __n); iterator operator-(const difference_type& __n) const; const pointer& base() const ; #ifndef G__OLDIMPLEMENTATION2165 iterator operator=(const iterator& x) ; #endif }; friend bool operator==(const vector::iterator& x,const vector::iterator& y)const; friend bool operator!=(const vector::iterator& x,const vector::iterator& y)const; friend bool operator<(const vector::iterator& x,const vector::iterator& y)const; friend bool operator>(const vector::iterator& x,const vector::iterator& y)const; friend bool operator<=(const vector::iterator& x,const vector::iterator& y)const; friend bool operator>=(const vector::iterator& x,const vector::iterator& y)const; friend vector::iterator::difference_type operator-(const vector::iterator& x,const vector::iterator& y)const; friend vector::iterator operator+(const vector::iterator::difference_type x,const vector::iterator& y)const; typedef const iterator const_iterator; #else /* 1703 */ typedef vector vector_type; typedef __gnu_cxx::__normal_iterator iterator; typedef __gnu_cxx::__normal_iterator const_iterator; #endif /* 1703 */ #elif defined(G__VISUAL) && (G__MSC_VER<1300) typedef T* iterator; typedef const T* const_iterator; //typedef Allocator allocator_type; //typedef reverse_iterator reverse_iterator; //typedef reverse_iterator const_reverse_iterator; #elif (!defined(G__INTEL_COMPILER) && (G__GNUC_VER>=3001)) class iterator { public: iterator(); explicit iterator(const pointer& __i) ; // Allow iterator to const_iterator conversion template inline iterator(const iterator& __i); // Forward iterator requirements reference operator*() const ; pointer operator->() const ; iterator& operator++(); iterator operator++(int) ; // Bidirectional iterator requirements iterator& operator--() ; iterator operator--(int) ; // Random access iterator requirements reference operator[](const difference_type& __n) const; iterator& operator+=(const difference_type& __n); iterator operator+(const difference_type& __n) const; iterator& operator-=(const difference_type& __n); iterator operator-(const difference_type& __n) const; difference_type operator-(const iterator& __n) const; const pointer& base() const ; }; friend bool operator==(const vector::iterator& x,const vector::iterator& y)const; friend bool operator!=(const vector::iterator& x,const vector::iterator& y)const; friend bool operator<(const vector::iterator& x,const vector::iterator& y)const; friend bool operator>(const vector::iterator& x,const vector::iterator& y)const; friend bool operator<=(const vector::iterator& x,const vector::iterator& y)const; friend bool operator>=(const vector::iterator& x,const vector::iterator& y)const; friend vector::iterator operator+(const vector::iterator::difference_type x,const vector::iterator& y)const; typedef const iterator const_iterator; #elif (!defined(G__INTEL_COMPILER) && (G__GNUC_VER>=3000)) typedef vector vector_type; typedef std::__normal_iterator iterator; typedef std::__normal_iterator const_iterator; #elif (defined(G__INTEL_COMPILER)) typedef T* iterator; typedef const T* const_iterator; typedef reverse_iterator reverse_iterator; typedef reverse_iterator const_reverse_iterator; #else typedef T* iterator; typedef const T* const_iterator; //typedef Allocator allocator_type; typedef reverse_iterator reverse_iterator; typedef reverse_iterator const_reverse_iterator; #endif #if defined(G__VISUAL) && (G__MSC_VER>=1300) // already done above #elif defined(G__BORLANDCC5) typedef reverse_iterator reverse_iterator; #elif ((!defined (G__INTEL_COMPILER) && (G__GNUC_VER>=3001)) || defined(G__AIX)) && (!defined(G__SUN)) typedef reverse_iterator const_reverse_iterator; typedef reverse_iterator reverse_iterator; #else // G__BORLANDCC5 #if defined(G__KCC) && 0 //There is a bug in the CINT parsing of #if between the 'class X' and the body of the class //declaration. so for now we keep this dummy test ... // typedef reverse_iterator reverse_iterator; #else class reverse_iterator #if defined(G__VISUAL) : public _Ranit #elif !defined(G__SUNPRO_CC) && !defined(G__INTEL_COMPILER) && !defined(G__KCC) && !defined(G__AIX) && !defined(G__ALPHA) : public std::random_access_iterator #endif { public: reverse_iterator(const reverse_iterator& x) ; #if !defined(G__BORLAND) && !defined(G__KCC) && !(defined (G__SGI)&&!defined(G__GNU)) && !defined(G__ALPHA) reverse_iterator& operator=(const reverse_iterator& x) ; #endif #if !(G__GNUC>=3) && !defined(G__KCC) T* base() ; #else iterator base() ; #endif T& operator*() const ; #ifndef G__OLDIMPLEMENTATION2019 T* operator->() const ; #endif reverse_iterator& operator++(); reverse_iterator operator++(int a); reverse_iterator& operator--(); reverse_iterator operator--(int a); reverse_iterator operator+(long n); reverse_iterator operator-(long n); reverse_iterator& operator+=(long n); reverse_iterator& operator-=(long n); T& operator[](long n) ; private: }; #if defined(G__SUN) && defined(G__GNUC) typedef const reverse_iterator const_reverse_iterator; #endif #endif #endif // G__BORLANDCC5 friend bool operator==(const vector::reverse_iterator& x ,const vector::reverse_iterator& y) const; friend bool operator!=(const vector::reverse_iterator& x ,const vector::reverse_iterator& y) const; #if !(G__GNUC_VER>3001) || defined(G__INTEL_COMPILER) typedef const reverse_iterator const_reverse_iterator; #endif #if (G__GNUC>=3) && !defined(G__KCC) && !defined(G__INTEL_COMPILER) friend bool operator==(vector::const_iterator& x ,vector::const_iterator& y) const; friend bool operator!=(vector::const_iterator& x ,vector::const_iterator& y) const; #endif #if 0 friend random_access_iterator_tag iterator_category(random_access_iterator& x); //friend random_access_iterator_tag //iterator_category(vector::reverse_iterator& x); #endif #if (!defined(G__GNUC)) || (G__GNUC>=3) T& at(size_type n); #endif iterator begin(void) ; iterator end(void) ; reverse_iterator rbegin(void) ; reverse_iterator rend(void) ; #ifdef G__CONSTNESSFLAG const_iterator begin(void) const; const_iterator end(void) const; const_reverse_iterator rbegin(void) const; const_reverse_iterator rend(void) const; #endif size_type size(void) const ; size_type max_size(void) const ; void resize(size_type sz) ; void resize(size_type sz, T c) ; size_type capacity(void) const ; bool empty(void) const ; T& operator[](size_type n) ; vector(void) ; vector(size_type n,const T& value=T()) ; vector(const vector& x) ; vector(const_iterator first,const_iterator last) ; ~vector(void) ; vector& operator=(const vector& x); void reserve(size_type n) ; T& front(void) ; T& back(void) ; void push_back(const T& x) ; void swap(vector& x); iterator insert(iterator position,const T& x); void insert(iterator position,const_iterator first,const_iterator last); void insert(iterator position,size_type n,const T& x); void pop_back(void) ; void erase(iterator position) ; void erase(iterator first,iterator last) ; void clear() ; #if (G__GNUC>=3) || defined(G__KCC) // doesn't work on VC++ 5.0 friend bool operator==(const vector& x, const vector& y); friend bool operator< (const vector& x, const vector& y); friend bool operator!=(const vector& x, const vector& y); friend bool operator> (const vector& x, const vector& y); friend bool operator>=(const vector& x, const vector& y); friend bool operator<=(const vector& x, const vector& y); #endif // specialized algorithms: #if !defined(G__GNUC) || defined(G__KCC) // doesn't work on egcs friend void swap(vector& x, vector& y); #endif #pragma ifndef G__NOALGORITHM // Generic algorithm #if defined(G__GNUC) || defined(G__BORLAND) || defined(G__KCC) // input iter friend vector::iterator find(vector::iterator first,vector::iterator last,const T& value); // forward iter friend vector::iterator find_end(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2); friend vector::iterator find_first_of(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2); friend vector::iterator adjacent_find(vector::iterator first,vector::iterator last); // input iter #if !defined(G__BORLAND) friend vector::difference_type count(vector::iterator first,vector::iterator last,const T& value); #endif #if 0 friend pair mismatch(vector::iterator first1,vector::iterator last1, vector::iterator first2); #endif friend bool equal(vector::iterator first1,vector::iterator last1, vector::iterator first2); // forward iter friend vector::iterator search(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2); friend vector::iterator search_n(vector::iterator first,vector::iterator last ,vector::size_type count,const T& value); // input and output iter -> forward iter friend vector::iterator copy(vector::iterator first,vector::iterator last, vector::iterator result); // bidirectional iter friend vector::iterator copy_backward(vector::iterator first,vector::iterator last, vector::iterator result); // just value_type friend void swap(T& a,T& b); // forward iter friend vector::iterator swap_ranges(vector::iterator first1,vector::iterator last1, vector::iterator first2); friend void iter_swap(vector::iterator a,vector::iterator b); friend void replace(vector::iterator first,vector::iterator last, const T& old_value,const T& new_value); // input, output iter -> forward iter friend vector::iterator replace_copy(vector::iterator first,vector::iterator last, vector::iterator result, const T& old_value,const T& new_value); // forward iter friend void fill(vector::iterator first,vector::iterator last,const T& value); #if (G__GNUC>=3) || defined(G__KCC) friend void fill_n(vector::iterator first,vector::size_type n,const T& value); #endif friend vector::iterator remove(vector::iterator first,vector::iterator last,const T& value); // input,output iter -> forward iter friend vector::iterator remove_copy(vector::iterator first,vector::iterator last, vector::iterator result,const T& value); friend vector::iterator unique(vector::iterator first,vector::iterator last); friend vector::iterator unique_copy(vector::iterator first,vector::iterator last, vector::iterator result); friend void reverse(vector::iterator first,vector::iterator last); friend vector::iterator reverse_copy(vector::iterator first,vector::iterator last, vector::iterator result); // forward iter #if (G__GNUC>=3) || defined(G__KCC) friend void rotate(vector::iterator first,vector::iterator mid, vector::iterator last); #endif // forward iter friend vector::iterator rotate_copy(vector::iterator first,vector::iterator mid, vector::iterator last,vector::iterator result); // randomaccess iter friend void random_shuffle(vector::iterator first,vector::iterator last); // randomaccess iter friend void sort(vector::iterator first,vector::iterator last); friend void stable_sort(vector::iterator first,vector::iterator last); friend void partial_sort(vector::iterator first,vector::iterator mid, vector::iterator last); friend vector::iterator partial_sort_copy(vector::iterator first,vector::iterator last, vector::iterator result_first, vector::iterator result_last); friend void nth_element(vector::iterator first,vector::iterator nth, vector::iterator last); // forward iter friend vector::iterator lower_bound(vector::iterator first,vector::iterator last,const T& value); friend vector::iterator upper_bound(vector::iterator first,vector::iterator last,const T& value); #if 0 friend pair equal_range(vector::iterator first,vector::iterator last,const T& value); #endif friend bool binary_search(vector::iterator first,vector::iterator last, const T& value); friend vector::iterator merge(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2, vector::iterator result); friend void inplace_merge(vector::iterator first,vector::iterator middle, vector::iterator last); friend bool includes(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2); friend vector::iterator set_union(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2, vector::iterator result); friend vector::iterator set_intersection(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2, vector::iterator result); friend vector::iterator set_difference(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2, vector::iterator result); friend vector::iterator set_symmetric_difference(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2, vector::iterator result); // random access friend void push_heap(vector::iterator first,vector::iterator last); friend void pop_heap(vector::iterator first,vector::iterator last); friend void make_heap(vector::iterator first,vector::iterator last); friend void sort_heap(vector::iterator first,vector::iterator last); // min,max, just value_type friend const T& min(const T& a,const T& b); friend const T& max(const T& a,const T& b); // forward iter friend vector::iterator min_element(vector::iterator first,vector::iterator last); friend vector::iterator max_element(vector::iterator first,vector::iterator last); // input iter friend bool lexicographical_compare(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2); // bidirectional iter friend bool next_permutation(vector::iterator first,vector::iterator last); friend bool prev_permutation(vector::iterator first,vector::iterator last); #elif defined(G__VISUAL) friend void reverse(vector::iterator first,vector::iterator last); friend void sort(vector::iterator first,vector::iterator last); friend vector::iterator find(vector::iterator first,vector::iterator last,const T& value); friend vector::iterator search(vector::iterator first1,vector::iterator last1, vector::iterator first2,vector::iterator last2); friend vector::iterator copy(vector::iterator first,vector::iterator last, vector::iterator result); friend void fill(vector::iterator first,vector::iterator last,const T& value); #if 0 // this is the limit that VC++ can handle friend vector::iterator remove(vector::iterator first,vector::iterator last,const T& value); friend vector::iterator unique(vector::iterator first,vector::iterator last); #endif #endif // G__VISUAL,G__GNUC,G__BORLAND #pragma endif // G__NOALGORITHM // iterator_category resolution //friend random_access_iterator_tag iterator_category(vector::iterator x); }; #ifdef G__VECTORBOOL ////////////////////////////////////////////////////////////////////////// // vector > specialization ////////////////////////////////////////////////////////////////////////// template class vector { public: // types: typedef bool const_reference; #if defined(G__VISUAL) && (G__MSC_VER<=1200) class iterator { public: iterator(); //iterator(const iterator&); #if 0 iterator& operator=(const iterator&); iterator& operator++(); iterator operator++(int); iterator& operator--(); iterator operator--(int); bool operator*(); #ifndef G__OLDIMPLEMENTATION2019 //bool* operator->() const; #endif #endif ~iterator(); }; typedef const iterator const_iterator; // See _lib.container.requirements_ #else class iterator { public: iterator(); //iterator(const iterator&); iterator& operator=(const iterator&); iterator& operator++(); iterator operator++(int); iterator& operator--(); iterator operator--(int); bool operator*(); #ifndef G__OLDIMPLEMENTATION2019 //bool* operator->() const; #endif ~iterator(); }; typedef const iterator const_iterator; // See _lib.container.requirements_ #endif typedef unsigned int size_type; // See _lib.container.requirements_ typedef long difference_type; // See _lib.container.requirements_ typedef bool value_type; typedef Allocator allocator_type; //typedef pointer; //typedef implementation defined const_pointer //typedef std::reverse_iterator reverse_iterator; class reverse_iterator { public: reverse_iterator(); reverse_iterator(const reverse_iterator&); reverse_iterator& operator=(const reverse_iterator&); reverse_iterator& operator++(); reverse_iterator operator++(int); reverse_iterator& operator--(); reverse_iterator operator--(int); bool operator*(); #ifndef G__OLDIMPLEMENTATION2019 //bool* operator->() const; #endif ~reverse_iterator(); }; typedef const reverse_iterator const_reverse_iterator; // bit reference: class reference { //friend class vector; reference(); public: ~reference(); operator bool() const; reference& operator=(const bool x); reference& operator=(const reference& x); void flip(); // flips the bit }; // construct/copy/destroy: explicit vector(const Allocator& = Allocator()); #ifdef __CINT__ explicit vector(size_type n, const bool& value = bool()); #else explicit vector(size_type n,const bool& value=bool(),const Allocator&=Allocator()); #endif template vector(InputIterator first, InputIterator last, const Allocator& = Allocator()); vector(const vector& x); ~vector(); vector& operator=(const vector& x); template void assign(InputIterator first, InputIterator last); void assign(size_type n, const bool t); #ifndef __CINT__ allocator_type get_allocator() const; #endif // iterators: iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const; reverse_iterator rbegin(); const_reverse_iterator rbegin() const; reverse_iterator rend(); const_reverse_iterator rend() const; // capacity: size_type size() const; size_type max_size() const; void resize(size_type sz, bool c = false); size_type capacity() const; bool empty() const; void reserve(size_type n); // element access: #ifndef __CINT__ reference operator[](size_type n); const_reference operator[](size_type n) const; const_reference at(size_type n) const; reference at(size_type n); reference front(); const_reference front() const; reference back(); const_reference back() const; #endif // modifiers: void push_back(const bool& x); void pop_back(); iterator insert(iterator position, const bool& x); void insert (iterator position, size_type n, const bool& x); template void insert(iterator position, InputIterator first, InputIterator last); iterator erase(iterator position); iterator erase(iterator first, iterator last); void swap(vector&); #ifndef __CINT__ static void swap(reference x, reference y); void flip(); // flips all bits #endif void clear(); }; template bool operator==(const vector& x, const vector& y); template bool operator< (const vector& x, const vector& y); template bool operator!=(const vector& x, const vector& y); template (const vector& x, const vector& y); template bool operator>=(const vector& x, const vector& y); template bool operator<=(const vector& x, const vector& y); // specialized algorithms: template void swap(vector& x, vector& y); #endif #pragma endif