Sierra Toolkit Version of the Day
VecSet.hpp
Go to the documentation of this file.
00001 /*--------------------------------------------------------------------*/
00002 /*    Copyright 2002 Sandia Corporation.                              */
00003 /*    Under the terms of Contract DE-AC04-94AL85000, there is a       */
00004 /*    non-exclusive license for use of this work by or on behalf      */
00005 /*    of the U.S. Government.  Export of this program may require     */
00006 /*    a license from the United States Government.                    */
00007 /*--------------------------------------------------------------------*/
00014 #ifndef STK_UTIL_UTIL_vecset_hpp
00015 #define STK_UTIL_UTIL_vecset_hpp
00016 
00017 #include <utility>
00018 #include <vector>
00019 #include <functional>
00020 
00021 namespace sierra {
00022 
00058 template <class Key, class Compare = std::less<Key> >
00059 class vecset {
00060 private:
00061   template <typename T>
00062   struct const_key_type_meta_func
00063   {
00064     typedef const T type;
00065   };
00066 
00067   template <typename T>
00068   struct const_key_type_meta_func<T*>
00069   {
00070     typedef const T* const type;
00071   };
00072 
00073 public:
00074 
00075   typedef Key      key_type;
00076   typedef Key      value_type;
00077   typedef Compare  key_compare;
00078   typedef Compare  value_compare;
00079   typedef typename const_key_type_meta_func<Key>::type const_key_type;
00080 
00081 private:
00082 
00083   typedef std::vector<key_type> storage ;
00084 
00085 public:
00086 
00087   typedef typename storage::allocator_type         allocator_type ;
00088   typedef typename allocator_type::reference       reference ;
00089   typedef typename allocator_type::const_reference const_reference ;
00090   typedef typename allocator_type::pointer         pointer ;
00091   typedef typename allocator_type::const_pointer   const_pointer ;
00092   typedef typename storage::size_type              size_type ;
00093   typedef typename storage::difference_type        difference_type ;
00094   typedef typename storage::iterator       iterator ;
00095   typedef typename storage::const_iterator         const_iterator ;
00096   typedef typename storage::reverse_iterator       reverse_iterator ;
00097   typedef typename storage::const_reverse_iterator const_reverse_iterator ;
00098 
00099   //--------------------------------------------------------------------
00100 private:
00101 
00102   key_compare KeyComp ;
00103   storage     Storage ;
00104 
00105 public:
00106   //--------------------------------------------------------------------
00107 
00108   ~vecset()
00109   {}
00110 
00111   vecset() : Storage()
00112   {}
00113 
00114   vecset( const vecset<Key,Compare> & rhs ) : Storage(rhs.Storage)
00115   {}
00116 
00117   vecset<Key,Compare> & operator = ( const vecset<Key,Compare> & rhs ) {
00118     Storage = rhs.Storage ;
00119     return *this ;
00120   }
00121 
00122   void swap( vecset<Key,Compare> & v ) {
00123     Storage.swap( v.Storage );
00124   }
00125 
00126   iterator               begin()          { return Storage.begin(); }
00127   iterator               end()            { return Storage.end(); }
00128   const_iterator         begin() const    { return Storage.begin(); }
00129   const_iterator         end() const      { return Storage.end(); }
00130   reverse_iterator       rbegin()         { return Storage.rbegin(); }
00131   reverse_iterator       rend()           { return Storage.rend(); }
00132   const_reverse_iterator rbegin() const   { return Storage.rbegin(); }
00133   const_reverse_iterator rend() const     { return Storage.rend(); }
00134   bool                   empty() const    { return Storage.empty(); }
00135   size_type              size() const     { return Storage.size(); }
00136   size_type              max_size() const { return Storage.max_size(); }
00137 
00138   iterator lower_bound( const_key_type & k ) {
00139     iterator __first = begin();
00140     iterator __last = end();
00141 
00142     difference_type __len = __last - __first;
00143     difference_type __half;
00144     iterator __middle;
00145 
00146     while (__len > 0) {
00147       __half = __len >> 1;
00148       __middle = __first;
00149       __middle += __half;
00150       if (KeyComp(*__middle, k)) {
00151   __first = __middle;
00152   ++__first;
00153   __len = __len - __half - 1;
00154       }
00155       else
00156   __len = __half;
00157     }
00158     return __first;
00159   }
00160 
00161   const_iterator lower_bound( const_key_type & k ) const {
00162     const_iterator __first = begin();
00163     const_iterator __last = end();
00164 
00165     difference_type __len = __last - __first;
00166     difference_type __half;
00167     const_iterator __middle;
00168 
00169     while (__len > 0) {
00170       __half = __len >> 1;
00171       __middle = __first;
00172       __middle += __half;
00173       if (KeyComp(*__middle, k)) {
00174   __first = __middle;
00175   ++__first;
00176   __len = __len - __half - 1;
00177       }
00178       else
00179   __len = __half;
00180     }
00181     return __first;
00182   }
00183 
00184   iterator upper_bound( const_key_type & k ) {
00185     iterator __first = begin();
00186     iterator __last = end();
00187 
00188     difference_type __len = __last - __first;
00189     difference_type __half;
00190     iterator __middle;
00191 
00192     while (__len > 0) {
00193       __half = __len >> 1;
00194       __middle = __first;
00195       __middle += __half;
00196       if (__comp(k, *__middle))
00197   __len = __half;
00198       else {
00199   __first = __middle;
00200   ++__first;
00201   __len = __len - __half - 1;
00202       }
00203     }
00204     return __first;
00205   }
00206 
00207 
00208   const_iterator upper_bound( const_key_type & k ) const {
00209     const_iterator __first = begin();
00210     const_iterator __last = end();
00211 
00212     difference_type __len = __last - __first;
00213     difference_type __half;
00214     const_iterator __middle;
00215 
00216     while (__len > 0) {
00217       __half = __len >> 1;
00218       __middle = __first;
00219       __middle += __half;
00220       if (__comp(k, *__middle))
00221   __len = __half;
00222       else {
00223   __first = __middle;
00224   ++__first;
00225   __len = __len - __half - 1;
00226       }
00227     }
00228     return __first;
00229   }
00230 
00231   std::pair<iterator,bool> insert( const value_type & v ) {
00232     typename storage::iterator ip = lower_bound(v);
00233     // (ip-1)->first < v <= ip->first
00234     const bool b = Storage.end() == ip || KeyComp( v , *ip );
00235     // b = v != *ip
00236     if ( b ) ip = Storage.insert(ip,v);
00237     return std::pair<iterator,bool>( ip, b );
00238   }
00239 
00240   void erase( iterator i ) {
00241     Storage.erase( Storage.begin() + ( i - begin() ) );
00242   }
00243 
00244   void erase( iterator first , iterator last ) {
00245     Storage.erase( Storage.begin() + ( first - begin() ) ,
00246        Storage.begin() + ( last  - begin() ) );
00247   }
00248 
00249   size_type erase( const_key_type & k ) {
00250     typename storage::iterator i = lower_bound(k );
00251     return KeyComp( k , *i ) ? 0 : ( Storage.erase(i) , 1 );
00252   }
00253 
00254   void clear() {
00255     Storage.clear();
00256   }
00257 
00258   key_compare   key_comp() const   { return KeyComp ; }
00259   value_compare value_comp() const { return KeyComp ; }
00260 
00261   iterator find( const_key_type & k ) {
00262     const iterator i = lower_bound(k);
00263     return end() == i || KeyComp( k , *i ) ? end() : i ;
00264   }
00265 
00266   const_iterator find( const_key_type & k ) const {
00267     const const_iterator i = lower_bound(k);
00268     return end() == i || KeyComp( k , *i ) ? end() : i ;
00269   }
00270 
00271   size_type count( const_key_type & k ) const {
00272     const const_iterator i = lower_bound(k);
00273     return end() == i || KeyComp( k , *i ) ? 0 : 1 ;
00274   }
00275 
00276   //--------------------------------------------------------------------
00277   // Allow conversion to constant vector
00278 
00279   operator const storage & () const {
00280     return Storage ;
00281   }
00282 
00283   void reserve( size_type n ) {
00284     Storage.reserve( n );
00285   }
00286 
00287   bool operator == ( const vecset<Key,Compare> & rhs ) const {
00288     return Storage == rhs.Storage ;
00289   }
00290 
00291   bool operator != ( const vecset<Key,Compare> & rhs ) const {
00292     return Storage != rhs.Storage ;
00293   }
00294 };
00295 
00296 }
00297 
00298 #endif // STK_UTIL_UTIL_vecset_hpp
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines