Sierra Toolkit Version of the Day
VecMap.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_vecmap_hpp
00015 #define STK_UTIL_UTIL_vecmap_hpp
00016 
00017 #include <utility>
00018 #include <functional>
00019 #include <vector>
00020 #include <algorithm>
00021 
00022 namespace sierra {
00023 
00059 template <class Key, class T, class Compare = std::less<Key> >
00060 class vecmap {
00061 public:
00062   typedef Key      key_type ;
00063   typedef T        mapped_type ;
00064   typedef Compare  key_compare ;
00065 
00066 private: // Hidden storage type
00067   typedef std::vector< std::pair<const key_type,mapped_type> > storage ;
00068 
00069 public:
00070   typedef typename storage::value_type             value_type ;
00071   typedef typename storage::allocator_type         allocator_type ;
00072   typedef typename allocator_type::reference       reference ;
00073   typedef typename allocator_type::const_reference const_reference ;
00074   typedef typename allocator_type::pointer         pointer ;
00075   typedef typename allocator_type::const_pointer   const_pointer ;
00076   typedef typename storage::size_type              size_type ;
00077   typedef typename storage::difference_type        difference_type ;
00078   typedef typename storage::iterator               iterator ;
00079   typedef typename storage::const_iterator         const_iterator ;
00080   typedef typename storage::reverse_iterator       reverse_iterator ;
00081   typedef typename storage::const_reverse_iterator const_reverse_iterator ;
00082 
00083   typedef std::pair<key_type,mapped_type> value_type_unconst_key ;
00084 
00085 private: // key compare functors
00086   class value_compare
00087     : public std::binary_function<value_type,value_type,bool> {
00088   private:
00089     key_compare comp ;
00090   public:
00091     bool operator ()( const value_type & RHS , const value_type & LHS ) const
00092     { return comp( RHS.first , LHS.first ); }
00093   };
00094 
00095   class value_compare_key
00096     : public std::binary_function<value_type,key_type,bool> {
00097   private:
00098     key_compare comp ;
00099   public:
00100     bool operator()( const value_type & RHS , const key_type & LHS ) const
00101     { return comp( RHS.first , LHS ); }
00102   };
00103 
00104   class value_compare_unconst_key
00105     : public std::binary_function<value_type_unconst_key,key_type,bool> {
00106   private:
00107     key_compare comp ;
00108   public:
00109     bool operator()( const value_type_unconst_key & RHS , const key_type & LHS ) const
00110     { return comp( RHS.first , LHS ); }
00111   };
00112 
00113 private: // Object data
00114   std::vector<value_type_unconst_key> Storage;
00115   value_compare     ValueComp ;
00116   value_compare_key     ValueKeyComp ;
00117   value_compare_unconst_key   UnconstValueKeyComp ;
00118   key_compare       KeyComp ;
00119 
00120 private:
00121   storage & pub() {
00122     char &i = reinterpret_cast<char&>(Storage);
00123     return reinterpret_cast<storage&>(i);
00124   }
00125 
00126   const storage & pub() const {
00127     const char &i = reinterpret_cast<const char&>(Storage);
00128     return reinterpret_cast<const storage&>(i);
00129   }
00130 
00131   typedef typename std::vector<value_type_unconst_key>::iterator iterator_private ;
00132 
00133   static iterator_private & castit( iterator & i )
00134   { return reinterpret_cast<iterator_private &>(i); }
00135 
00136   static iterator & castit( iterator_private & i )
00137   { return reinterpret_cast<iterator &>(i); }
00138 
00139 public:
00140   ~vecmap() {}
00141 
00142   vecmap() : Storage() {}
00143 
00144   vecmap( const vecmap<Key,T,Compare> & rhs ) : Storage(rhs.Storage) {}
00145 
00146   vecmap<Key,T,Compare> & operator = ( const vecmap<Key,T,Compare> & rhs ) {
00147     Storage = rhs.Storage ;
00148     return *this ;
00149   }
00150 
00151   void swap( vecmap<Key,T,Compare> & v ) {
00152     Storage.swap( v.Storage );
00153   }
00154 
00155   iterator               begin()          { return pub().begin(); }
00156   iterator               end()            { return pub().end(); }
00157   const_iterator         begin() const    { return pub().begin(); }
00158   const_iterator         end() const      { return pub().end(); }
00159   reverse_iterator       rbegin()         { return pub().rbegin(); }
00160   reverse_iterator       rend()           { return pub().rend(); }
00161   const_reverse_iterator rbegin() const   { return pub().rbegin(); }
00162   const_reverse_iterator rend() const     { return pub().rend(); }
00163   bool                   empty() const    { return Storage.empty(); }
00164   size_type              size() const     { return Storage.size(); }
00165   size_type              max_size() const { return Storage.max_size(); }
00166 
00167 
00168   typename std::vector<value_type_unconst_key>::iterator lower_bound_private_comp_( const key_type & k ) {
00169     typename std::vector<value_type_unconst_key>::iterator __first = Storage.begin();
00170     typename std::vector<value_type_unconst_key>::iterator __last = Storage.end();
00171 
00172 //    difference_type __len = std::distance(__first, __last);
00173     difference_type __len = __last - __first;
00174     difference_type __half;
00175     typename std::vector<value_type_unconst_key>::iterator __middle;
00176 
00177     while (__len > 0) {
00178       __half = __len >> 1;
00179       __middle = __first;
00180 //      std::advance(__middle, __half);
00181       __middle += __half;
00182       if (UnconstValueKeyComp(*__middle, k)) {
00183   __first = __middle;
00184   ++__first;
00185   __len = __len - __half - 1;
00186       }
00187       else
00188   __len = __half;
00189     }
00190     return __first;
00191   }
00192 
00193   std::pair<iterator,bool> insert( const value_type & v ) {
00194     typename std::vector<value_type_unconst_key>::iterator ip =
00195       lower_bound_private_comp_(v.first);
00196     // (ip-1)->first < v.first <= ip->first
00197     const bool b = Storage.end() == ip || KeyComp( v.first , ip->first );
00198     // b = v.first != ip->first
00199     if ( b ) ip = Storage.insert(ip,value_type_unconst_key(v.first,v.second));
00200     return std::pair<iterator,bool>( castit(ip), b );
00201   }
00202 
00203   mapped_type & operator[]( const key_type & k ) {
00204     typename std::vector<value_type_unconst_key>::iterator ip =
00205       lower_bound_private_comp_(k);
00206 
00207     // (ip-1)->first < k <= ip->first
00208     if ( Storage.end() == ip || KeyComp(k,ip->first) ) {
00209       // k != ip->first => insert
00210       ( ip = Storage.insert(ip,value_type_unconst_key()) )->first = k ;
00211     }
00212     return ip->second ;
00213   }
00214 
00215   void erase( iterator i ) {
00216     Storage.erase( castit(i) );
00217   }
00218 
00219   void erase( iterator first , iterator last ) {
00220     Storage.erase( castit(first), castit(last) );
00221   }
00222 
00223   size_type erase( const key_type & k ) {
00224     const typename std::vector<value_type_unconst_key>::iterator i =
00225       lower_bound_private_comp_(k);
00226     return KeyComp( k , i->first ) ? 0 : ( Storage.erase(i) , 1 );
00227   }
00228 
00229   void clear() {
00230     Storage.clear();
00231   }
00232 
00233   key_compare   key_comp() const   { return KeyComp ; }
00234 
00235   value_compare value_comp() const { return ValueComp ; }
00236 
00237   iterator lower_bound( const key_type & k ) {
00238     iterator __first = begin();
00239     iterator __last = end();
00240 
00241 //    difference_type __len = std::distance(__first, __last);
00242     difference_type __len = __last - __first;
00243     difference_type __half;
00244     iterator __middle;
00245 
00246     while (__len > 0) {
00247       __half = __len >> 1;
00248       __middle = __first;
00249 //      std::advance(__middle, __half);
00250       __middle += __half;
00251       if (ValueKeyComp(*__middle, k)) {
00252   __first = __middle;
00253   ++__first;
00254   __len = __len - __half - 1;
00255       }
00256       else
00257   __len = __half;
00258     }
00259     return __first;
00260   }
00261 
00262   const_iterator lower_bound( const key_type & k ) const {
00263     const_iterator __first = begin();
00264     const_iterator __last = end();
00265 
00266 //    difference_type __len = std::distance(__first, __last);
00267     difference_type __len = __last - __first;
00268     difference_type __half;
00269     const_iterator __middle;
00270 
00271     while (__len > 0) {
00272       __half = __len >> 1;
00273       __middle = __first;
00274 //      std::advance(__middle, __half);
00275       __middle += __half;
00276       if (ValueKeyComp(*__middle, k)) {
00277   __first = __middle;
00278   ++__first;
00279   __len = __len - __half - 1;
00280       }
00281       else
00282   __len = __half;
00283     }
00284     return __first;
00285   }
00286 
00287   iterator upper_bound( const key_type & k ) {
00288     iterator __first = begin();
00289     iterator __last = end();
00290 
00291 //    difference_type __len = std::distance(__first, __last);
00292     difference_type __len = __last - __first;
00293     difference_type __half;
00294     iterator __middle;
00295 
00296     while (__len > 0) {
00297       __half = __len >> 1;
00298       __middle = __first;
00299 //      std::advance(__middle, __half);
00300       __middle += __half;
00301       if (__comp(k, *__middle))
00302   __len = __half;
00303       else {
00304   __first = __middle;
00305   ++__first;
00306   __len = __len - __half - 1;
00307       }
00308     }
00309     return __first;
00310   }
00311 
00312 
00313   const_iterator upper_bound( const key_type & k ) const {
00314     const_iterator __first = begin();
00315     const_iterator __last = end();
00316 
00317 //    difference_type __len = std::distance(__first, __last);
00318     difference_type __len = __last - __first;
00319     difference_type __half;
00320     const_iterator __middle;
00321 
00322     while (__len > 0) {
00323       __half = __len >> 1;
00324       __middle = __first;
00325 //      std::advance(__middle, __half);
00326       __middle += __half;
00327       if (__comp(k, *__middle))
00328   __len = __half;
00329       else {
00330   __first = __middle;
00331   ++__first;
00332   __len = __len - __half - 1;
00333       }
00334     }
00335     return __first;
00336   }
00337 
00338 
00339   iterator find( const key_type & k ) {
00340     const iterator i = lower_bound(k);
00341     return end() == i || KeyComp( k , i->first ) ? end() : i ;
00342   }
00343 
00344   const_iterator find( const key_type & k ) const {
00345     const const_iterator i = lower_bound(k);
00346     return end() == i || KeyComp( k , i->first ) ? end() : i ;
00347   }
00348 
00349   size_type count( const key_type & k ) const {
00350     const const_iterator i = lower_bound(k);
00351     return end() == i || KeyComp( k , i->first ) ? 0 : 1 ;
00352   }
00353 
00354   //--------------------------------------------------------------------
00355   // Is ok to get constant versions of the underlyingstorage
00356 
00357   operator const std::vector<value_type> & () const {
00358     return * reinterpret_cast<const std::vector<value_type>*>( &Storage );
00359   }
00360 
00361   operator const std::vector< std::pair<key_type,mapped_type> > & () const {
00362     return Storage ;
00363   }
00364 
00365   void reserve( size_type n ) {
00366     Storage.reserve(n);
00367   }
00368 
00369   bool operator == ( const vecmap<Key,T,Compare> & rhs ) const {
00370     return Storage == rhs.Storage ;
00371   }
00372 
00373   bool operator != ( const vecmap<Key,T,Compare> & rhs ) const {
00374     return Storage != rhs.Storage ;
00375   }
00376 };
00377 
00378 } // namespace sierra
00379 
00380 #endif // STK_UTIL_UTIL_vecmap_hpp
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines