Sierra Toolkit Version of the Day
Mapv.hpp
00001 #ifndef STK_UTIL_DIAG_Mapv_h
00002 #define STK_UTIL_DIAG_Mapv_h
00003 
00004 #include <stk_util/util/FeatureTest.hpp>
00005 #include <cstddef>
00006 
00007 // ---------------------------------------------------------------------
00008 // Author: H. Carter Edwards
00009 //
00010 // Purpose:
00011 //   A map-style associative container for large allocated data objects.
00012 // ---------------------------------------------------------------------
00013 // Usage / Instantiation:
00014 //
00015 // Each node in a "virtual map" must be derived from the 'MapvNode'
00016 // base class.  Their should be only one 'MapvNode' base class.
00017 //
00018 //  class MY_CLASS : public MapvNode<Key_Type> , other_base_classes {
00019 //    // 'MY_CLASS' internal data & methods
00020 //  };
00021 //
00022 //  class MY_CLASS2 : MY_CLASS {
00023 //
00024 //  };
00025 //
00026 // The Key_Type template argument is the data type of the ordering key
00027 // for the virtual map.  The Key_Type must support the 'less<Key_Type>'
00028 // template function object.
00029 // ---------------------------------------------------------------------
00030 // Features and Limitations:
00031 //
00032 // The 'MapvNode' derived objects may be inserted into a 'Mapv' container
00033 // without being copied.
00034 //
00035 // When a 'MapvNode' derived object is destroyed it is automatically
00036 // removed from the 'Mapv' container.  Destruction of a 'Mapv' container
00037 // automatically invokes the 'delete' operator for each 'MapvNode'
00038 // derived object that resides in the container at the time of its
00039 // destruction.
00040 //
00041 // The 'insert' and 'remove' operations cause the 'Mapv' container to
00042 // rebalance its binary tree.  These rebalancing algorithms are lengthy.
00043 // As such the majority of the 'insert' and 'remove' operations are
00044 // implemented in the seperately compiled 'Mapv.C' file.  The subprograms
00045 // in 'Mapv.C' are shared by all instantiations of 'Mapv', thus
00046 // "code bloat" is kept to a minimum.
00047 //
00048 // Alteration of a 'mavnode' derived objects 'key' value is likely
00049 // to invalidate its position in the binary.  Thus alteration of the
00050 // 'key' value removes the object from its 'Mapv' container.
00051 //
00052 // ---------------------------------------------------------------------
00053 // Acknowledgements:
00054 //
00055 //   Most all of the algorithms in this class were obtained from
00056 // the Hewlett-Packard source for the Standard Template Library,
00057 // thus the inclusion of Hewlett-Packard's copyright notice.
00058 // ---------------------------------------------------------------------
00059 /*
00060  * Copyright (c) 1994
00061  * Hewlett-Packard Company
00062  *
00063  * Permission to use, copy, modify, distribute and sell this software
00064  * and its documentation for any purpose is hereby granted without fee,
00065  * provided that the above copyright notice appear in all copies and
00066  * that both that copyright notice and this permission notice appear
00067  * in supporting documentation.  Hewlett-Packard Company makes no
00068  * representations about the suitability of this software for any
00069  * purpose.  It is provided "as is" without express or implied warranty.
00070  *
00071  */
00072 /*
00073 Red-black tree class, designed for use in implementing STL
00074 associative containers (set, multiset, map, and multimap).
00075 The insertion and deletion algorithms are based on those in Cormen,
00076 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
00077 except that
00078 
00079 (1) the header cell is maintained with links not only to the root
00080 but also to the leftmost node of the tree, to enable constant time
00081 begin(), and to the rightmost node of the tree, to enable linear time
00082 performance when used with the generic set algorithms (set_union,
00083 etc.);
00084 
00085 (2) when a node being deleted has two children its successor node is
00086 relinked into its place, rather than copied, so that the only
00087 iterators invalidated are those referring to the deleted node.
00088 */
00089 // ---------------------------------------------------------------------
00090 // Don't force usage of 'assert', but if available then use it
00091 
00092 #ifdef MAPV_ASSERT_H
00093 #define mapv_assert( expr ) assert( expr )
00094 #else
00095 #define mapv_assert( expr ) /* do nothing */
00096 #endif
00097 
00098 // STL includes:
00099 
00100 #include <utility>
00101 #include <iterator>
00102 #include <functional>
00103 
00104 #ifdef SIERRA_IA64_OPTIMIZER_FIX
00105 #pragma optimize("", off)
00106 #endif
00107 
00108 namespace sierra {
00109 
00110 // class MyType : public MapvNode<MyKey> { ... };
00111 
00112 template < typename Key_Type , class Key_Compare > class MapvNode ;
00113 
00114 template < class Derived_Type , class Memory_Policy > class Mapv ;
00115 
00116 template < class Derived_Type , class Next , class Prev > class MapvIterator ;
00117 
00118 // ---------------------------------------------------------------------
00119 // ---------------------------------------------------------------------
00122 class MapvIterNext ;
00123 class MapvIterPrev ;
00124 
00125 class MapvNodeBase {
00126 private:
00127 
00128   enum { black = 0 , red = 1 };
00129 
00130   MapvNodeBase * parent ; // Binary tree node
00131   MapvNodeBase * left ;   // Binary tree node
00132   MapvNodeBase * right ;  // Binary tree node
00133   unsigned       color ;  // Red-black color
00134 
00135   inline void remove_from_container();
00136 
00138   virtual ~MapvNodeBase() { remove_from_container(); }
00139 
00140   MapvNodeBase() : parent(0), left(0), right(0), color(black) {}
00141 
00142   // Friends of this very private class
00143 
00144   friend class MapvBase ;
00145   friend class MapvIterNext ;
00146   friend class MapvIterPrev ;
00147   template < class dType , class N, class P > friend class MapvIterator ;
00148   template < class dType , class mPolicy > friend class Mapv ;
00149   template < class kType , class kCompare > friend class MapvNode ;
00150 };
00151 
00152 // ---------------------------------------------------------------------
00167 template < typename Key_Type , class Key_Compare = std::less<Key_Type> >
00168 class MapvNode : private MapvNodeBase {
00169 public:
00170 
00171   typedef Key_Type    key_type ;
00172   typedef Key_Compare key_compare ;
00173 
00174   bool mapv_valid() const { return this && MapvNodeBase::parent ; }
00175   void mapv_remove()      { MapvNodeBase::remove_from_container(); }
00176 
00178   const key_type & mapv_key() const { return Key ; }
00179 
00181   const Key_Type & mapv_key( const key_type & K )
00182     { remove_from_container(); return Key = K  ; }
00183 
00185   virtual ~MapvNode() {}
00186   MapvNode() {}
00187   MapvNode( const key_type & K ) : Key(K) {}
00188 
00189 private:
00190 
00191   Key_Type Key ;
00192 
00193   // Disallow copy constructor and assignment operator
00194 
00195   MapvNode( const MapvNode<Key_Type,Key_Compare> & );
00196 
00197   MapvNode<Key_Type,Key_Compare> &
00198     operator = ( const MapvNode<Key_Type,Key_Compare> & );
00199 
00200   // friends to access the MapvNodeBase base class and Key member
00201   template< class dType , class N , class P > friend class MapvIterator ;
00202   template< class dType , class mPolicy > friend class Mapv ;
00203 };
00204 
00205 //----------------------------------------------------------------------
00206 //----------------------------------------------------------------------
00209 class MapvIterNext {
00210 public:
00211   typedef       MapvNodeBase *  ptr ;
00212   typedef const MapvNodeBase * cptr ;
00213   static ptr op( cptr x )
00214     {
00215       ptr y = x->right;
00216       if ( y ) {
00217   while ( y->left ) y = y->left ;
00218       }
00219       else {
00220   mapv_assert( x->parent /* incrementing 'end()' iterator */ );
00221   y = x->parent ;
00222   while ( x == y->right ) y = ( x = y )->parent ;
00223   if ( x == y->parent ) y = y->right ;
00224       }
00225       return y ;
00226     }
00227 };
00228 
00229 class MapvIterPrev {
00230 public:
00231   typedef       MapvNodeBase *  ptr ;
00232   typedef const MapvNodeBase * cptr ;
00233   static ptr op( cptr x )
00234     {
00235       ptr y = x->left;
00236       if ( y ) {
00237   while ( y->right ) y = y->right ;
00238       }
00239       else {
00240   mapv_assert( x->parent /* decrementing 'end()' iterator */ );
00241   y = x->parent ;
00242   while ( x == y->left ) y = ( x = y )->parent ;
00243   if ( x == y->parent ) y = y->left ;
00244       }
00245       return y ;
00246     }
00247 };
00248 
00249 template < class Type , class Next , class Prev >
00250 class MapvIterator : public std::iterator<std::bidirectional_iterator_tag,Type>
00251 {
00252 private:
00253   template < class T , class M > friend class Mapv ;
00254   template < class T , class N, class P > friend class MapvIterator ;
00255 
00256   Type * n ;
00257 
00261   Type * ptr() const { return n->MapvNodeBase::parent == 0 ? (Type*) 0 : n ; }
00262 
00263   MapvIterator( MapvNodeBase * x ) : n( static_cast<Type*>(x) )  {}
00264   MapvIterator( Type * x ) : n( x )  {}
00265   MapvIterator( Type & x ) : n( &x ) {}
00266 
00267 public:
00268 
00269   typedef MapvIterator<Type,Next,Prev> SelfType ;
00270 
00275   template<class T,class N, class P>
00276     MapvIterator( const MapvIterator<T,N,P> & x ) : n( x.n ) {}
00277 
00282   template<class T,class N,class P>
00283     SelfType & operator = ( const MapvIterator<T,N,P> & x )
00284       { n = x.n ; return *this ; }
00285 
00290   bool valid_to_dereference() const { return n && n->MapvNodeBase::parent ; }
00291 
00292 //   /** Conversion to bool: true for dereferenceable iterator */
00293 //   operator bool () const { return valid_to_dereference(); }
00294 
00295   //--------------------------------------------------------------------
00296 
00297   MapvIterator() : n(0) {}
00298   MapvIterator( const SelfType & x ) : n( x.n ) {}
00299 
00300   SelfType & operator = ( const SelfType & x ) { n = x.n ; return *this ; }
00301 
00302   Type & operator * () const
00303     { mapv_assert( valid_to_dereference() ); return *n ; }
00304   Type * operator ->() const
00305     { mapv_assert( valid_to_dereference() ); return n ; }
00306 
00307   SelfType & operator++(){ n = static_cast<Type*>(Next::op(n)); return *this; }
00308   SelfType & operator--(){ n = static_cast<Type*>(Prev::op(n)); return *this; }
00309 
00310   SelfType operator++(int)
00311     { Type * t = n ; n = static_cast<Type*>(Next::op(n)); return SelfType(t); }
00312 
00313   SelfType operator--(int)
00314     { Type * t = n ; n = static_cast<Type*>(Prev::op(n)); return SelfType(t); }
00315 
00316   template<class T,class N, class P>
00317     bool operator == ( const MapvIterator<T,N,P> & y ) const
00318       { return n == y.n ; }
00319 
00320   template<class T,class N, class P>
00321     bool operator != ( const MapvIterator<T,N,P> & y ) const
00322       { return n != y.n ; }
00323 };
00324 
00325 //----------------------------------------------------------------------
00326 //----------------------------------------------------------------------
00329 class MapvBase : private MapvNodeBase {
00330 private:
00331 
00332   MapvNodeBase left_end ;  // 'rend()' node
00333   MapvNodeBase right_end ; // 'end()' node
00334 
00335   size_t Count ;
00336 
00337   //------------------------------------
00338 
00339   typedef MapvNodeBase   nType ;
00340   typedef MapvNodeBase * pType ;
00341 
00342   static MapvBase * container( const nType * x )
00343     {
00344       MapvBase * h = 0 ;
00345       if ( x && x->parent ) {
00346   // Search for root node, while loop breaks at root node
00347   while ( x != x->parent->parent ) x = x->parent ;
00348   // the root node's parent is the header
00349   h = static_cast<MapvBase*>( x->parent );
00350       }
00351       return h ;
00352     }
00353 
00354 // ---------------------------------------------------------------------
00355 
00356   static nType * minimum( nType * );
00357   static nType * maximum( nType * );
00358 
00359   void rotate_left(  nType * x );
00360   void rotate_right( nType * x );
00361 
00362   nType * header()    const { return const_cast<nType*>((const nType*)this); }
00363   nType * rightmost() const { return right_end.left ; }
00364   nType * leftmost()  const { return left_end.right ; }
00365 
00366   void rightmost( nType * N ) { right_end.left = N ; }
00367   void leftmost(  nType * N ) { left_end.right = N ; }
00368   void root(      nType * N ) { header()->parent = N ; }
00369 
00370   //------------------------------------
00371 
00372   virtual ~MapvBase();
00373 
00374   void remove( MapvNodeBase * );
00375 
00376   nType * nRoot() const { return header()->parent ; }
00377   nType * nEnd()  const { return const_cast<nType*>( & right_end ); }
00378   nType * nREnd() const { return const_cast<nType*>( & left_end ); }
00379 
00380   nType * nBegin() const
00381     { return ( left_end.right != nREnd() ) ? left_end.right : nEnd(); }
00382 
00383   nType * nRBegin() const
00384     { return ( right_end.left != nEnd() ) ? right_end.left : nREnd(); }
00385 
00386   MapvBase() : MapvNodeBase(), left_end(), right_end(), Count(0)
00387     {
00388       header()->color = red ;  /* Color the header node red */
00389       leftmost(  header()->left  = nREnd() ); // left end of the tree
00390       rightmost( header()->right = nEnd() );  // right end of the tree
00391     }
00392 
00393   void insert( nType * y , nType * z , bool z_lt_y );
00394 
00395   nType * unbalancing_removal( nType ** n );
00396   static void WarnOptimize();
00397 
00398   friend class MapvNodeBase ;
00399   template< class dType , class mPolicy > friend class Mapv ;
00400 };
00401 
00402 inline void MapvNodeBase::remove_from_container()
00403 {
00404   MapvBase * const c = MapvBase::container(this);
00405   if ( c ) c->remove( this );
00406 }
00407 
00408 //----------------------------------------------------------------------
00409 //----------------------------------------------------------------------
00410 
00411 template <class Derived_Type>
00412 struct MapvNewDeletePolicy {
00413   typedef typename Derived_Type::key_type key_type ;
00414 
00415   Derived_Type * create( const key_type & K ) { return new Derived_Type(K); }
00416 
00417   void destroy( Derived_Type * p ) { delete p ; }
00418 };
00419 
00420 template <class Derived_Type>
00421 struct MapvDeleteOnlyPolicy {
00422   typedef typename Derived_Type::key_type key_type ;
00423 
00424   Derived_Type * create( const key_type & K ) { return (Derived_Type*) 0 ; }
00425 
00426   void destroy( Derived_Type * p ) { delete p ; }
00427 };
00428 
00429 template <class Derived_Type>
00430 struct MapvNullPolicy {
00431   typedef typename Derived_Type::key_type key_type ;
00432 
00433   Derived_Type * create( const key_type & K ) { return (Derived_Type*) 0 ; }
00434 
00435   void destroy( Derived_Type * p ) {}
00436 };
00437 
00438 //----------------------------------------------------------------------
00439 //----------------------------------------------------------------------
00440 
00441 template < class Derived_Type ,
00442      class Memory_Policy = MapvDeleteOnlyPolicy<Derived_Type> >
00443 class Mapv : public MapvBase {
00444 public:
00445 
00446   // 'self' type
00447   typedef Mapv<Derived_Type,Memory_Policy> SelfType ;
00448 
00449   // NOTE: value_type == Derived_Type, the chain of
00450   //       typedefs insures the correct derivation has occured.
00451 
00452   typedef typename Derived_Type::key_type     key_type ;
00453   typedef typename Derived_Type::key_compare  key_compare ;
00454   typedef Derived_Type                        value_type ;
00455   typedef size_t                              size_type ;
00456   typedef ptrdiff_t                           difference_type ;
00457 
00458   typedef       value_type * pointer ;
00459   typedef const value_type * const_pointer ;
00460   typedef       value_type & reference ;
00461   typedef const value_type & const_reference ;
00462 
00463   struct value_compare
00464     : public std::binary_function<value_type,value_type,bool>
00465   {
00466   protected:
00467     key_compare comp ;
00468   public:
00469     bool operator()(const value_type& x, const value_type& y) const
00470       { return comp( x.mapv_key() , y.mapv_key() ); }
00471   };
00472 
00473   typedef MapvIterNext Next ;
00474   typedef MapvIterPrev Prev ;
00475 
00476   typedef MapvIterator<      Derived_Type,Next,Prev> iterator ;
00477   typedef MapvIterator<const Derived_Type,Next,Prev> const_iterator ;
00478   typedef MapvIterator<      Derived_Type,Prev,Next> reverse_iterator ;
00479   typedef MapvIterator<const Derived_Type,Prev,Next> const_reverse_iterator ;
00480 
00481   typedef std::pair<iterator, bool> pair_iterator_bool ;
00482 
00483 private:
00484 
00485   // Disallow copy and assignment
00486 
00487   Mapv( const SelfType & );
00488 
00489   SelfType & operator = ( const SelfType & );
00490 
00491   Memory_Policy memoryPolicy ;
00492   key_compare   key_less ;      // An "abstract" object
00493   value_compare value_less ;    // An "abstract" object
00494 
00495   static const key_type & key( nType * const n )
00496     { return static_cast<MapvNode<key_type,key_compare>*>(n)->mapv_key(); }
00497 
00498   static value_type * cast( nType * n )
00499     { return static_cast<value_type*>(n); }
00500 
00501 // WORKAROUND: 4/7/2010 -- This works for our SGI Itanium Intel compiler on sasg1132 
00502 #ifdef SIERRA_IA64_OPTIMIZER_FIX
00503    Derived_Type * lb( const key_type & k ) const
00504      {
00505       volatile pType y = nEnd();  // [DGB] -- Altix intel-10.1 optimizer hack
00506       volatile pType x = nRoot(); // [DGB] -- Altix intel-10.1 optimizer hack
00507       while ( x ) {
00508         bool go_right = key_less(key(x), k);
00509         
00510         if (go_right) {
00511           x = x->right;
00512         }
00513         else {
00514           y = x;
00515           x = x->left;
00516         }
00517       }      
00518       return cast(y);
00519     }
00520 
00521   Derived_Type * ub( const key_type & k ) const
00522     {
00523       pType y = nEnd();
00524       pType x = nRoot();
00525       while ( x ) x = key_less(k,key(x)) ? ( y = x )->left : x->right ;
00526       return cast(y);
00527     }
00528 
00529 #else
00530   Derived_Type * lb( const key_type & k ) const
00531     {
00532       pType y = nEnd();
00533       pType x = nRoot();
00534       while ( x ) x = key_less(key(x),k) ? x->right : ( y = x )->left ;
00535       return cast(y);
00536     }
00537 
00538   Derived_Type * ub( const key_type & k ) const
00539     {
00540       pType y = nEnd();
00541       pType x = nRoot();
00542       while ( x ) x = key_less(k,key(x)) ? ( y = x )->left : x->right ;
00543       return cast(y);
00544     }
00545 #endif // SIERRA_IA64_OPTIMIZER_FIX
00546 
00547   Derived_Type * f( const key_type & k ) const
00548     {
00549       nType * const e = nEnd();
00550       nType * const y = lb(k); // k <= y->mapv_key()
00551 
00552       // If 'end()' or k < y->mapv_key() then not found
00553       return cast( ( y == e || key_less(k,key(y)) ) ? e : y );
00554     }
00555 
00556 public:
00557 
00558   static SelfType * container( const Derived_Type & n )
00559     {
00560       MapvBase * const c = MapvBase::container(&n);
00561       return c ? static_cast<SelfType*>( c ) : (SelfType*) 0 ;
00562     }
00563 
00564   static SelfType * container( const Derived_Type * n )
00565     { return n ? container( *n ) : (SelfType*) 0 ; }
00566 
00567   // -------------------------------------------------------------------
00568 
00569   key_compare   key_comp()   const { return key_less ; }
00570   value_compare value_comp() const { return value_less ; }
00571 
00572   const_iterator begin()  const { return const_iterator(cast(nBegin())); }
00573   const_iterator end()    const { return const_iterator(cast(nEnd())); }
00574   const_iterator rbegin() const { return const_iterator(cast(nRBegin())); }
00575   const_iterator rend()   const { return const_iterator(cast(nREnd())); }
00576 
00577   iterator begin()  { return iterator(cast(nBegin())); }
00578   iterator end()    { return iterator(cast(nEnd())); }
00579   iterator rbegin() { return iterator(cast(nRBegin())); }
00580   iterator rend()   { return iterator(cast(nREnd())); }
00581 
00582   bool      empty() const { return MapvBase::Count == 0 ; }
00583   size_type size()  const { return MapvBase::Count ; }
00584 
00585   // -------------------------------------------------------------------
00586   // search operations:
00587 
00588   iterator lower_bound( const key_type & k ) { return iterator( lb(k) ); }
00589   iterator upper_bound( const key_type & k ) { return iterator( ub(k) ); }
00590 
00591   const_iterator lower_bound( const key_type & k ) const
00592     { return const_iterator( lb(k) ); }
00593 
00594   const_iterator upper_bound( const key_type & k ) const
00595     { return const_iterator( ub(k) ); }
00596 
00597   iterator find( const key_type & k ) { return iterator( f(k) ); }
00598 
00599   const_iterator find( const key_type & k ) const
00600     { return const_iterator( f(k) ); }
00601 
00602   // -------------------------------------------------------------------
00603 
00607   value_type & operator[]( const key_type & k )
00608     {
00609       pType y = nEnd();
00610       pType x = nRoot();
00611 
00612       bool flag = true ;
00613 
00614       while ( x )
00615   { y = x ; x = ( flag = key_less(k, key(x)) ) ? x->left : x->right ; }
00616 
00617       /* flag = k < y , check previous value if exists */
00618 
00619       const bool k_lt_y = flag ;
00620 
00621       x = flag && y != nBegin() ? ( flag = false , MapvIterPrev::op(y) ) : y ;
00622 
00623       if ( flag || ( flag = key_less( key(x) , k ) ) ) {
00624   x = memoryPolicy.create(k);
00625   MapvBase::insert( y , x , k_lt_y );
00626       }
00627       return *static_cast<pointer>(x);
00628     }
00629 
00638   pair_iterator_bool insert( const pointer v )
00639     {
00640       WarnOptimize();
00641       pType y = nEnd();
00642       pType x = nRoot();
00643 
00644       bool flag = true ;
00645 
00646       while ( x ) {
00647   y = x ;
00648   x = ( flag = key_less(v->mapv_key(), key(x)) ) ? x->left : x->right ;
00649       }
00650 
00651       /* flag = k < y , check previous value if exists */
00652 
00653       const bool k_lt_y = flag ;
00654 
00655       x = flag && y != nBegin() ? ( flag = false , MapvIterPrev::op(y) ) : y ;
00656 
00657       if ( flag || ( flag = key_less( key(x) , v->mapv_key() ) ) ) {
00658   x = v ;
00659   MapvBase::insert( y , x , k_lt_y );
00660       }
00661       return pair_iterator_bool( iterator(x), flag );
00662     }
00663 
00664   pair_iterator_bool insert( reference v ) { return insert( &v ); }
00665 
00666   // -------------------------------------------------------------------
00667   // Remove & erase operations
00668 
00669   pointer remove( const key_type & k )
00670     {
00671       pointer v = f(k);
00672       return ( nEnd() != v ) ? ( MapvBase::remove(v) , v ) : (pointer) 0 ;
00673     }
00674 
00675   pointer remove( iterator i )
00676     { MapvBase::remove( i.n ); return i.n ; }
00677 
00678   void erase( const key_type & K )
00679     { pointer v = remove(K); if ( v ) memoryPolicy.destroy(v); }
00680 
00681   void erase( iterator i )
00682     { pointer v = remove(i); if ( v ) memoryPolicy.destroy(v); }
00683 
00684   // -------------------------------------------------------------------
00685   // construction / destruction
00686   // Destruction will apply the 'Derived_Type::destroy'
00687   // method to each node in the tree.
00688 
00689   Mapv() {}
00690 
00691   void clear()
00692     {
00693       if ( Count ) {
00694   nType * n = nBegin();
00695   nType * t ;
00696   while ( ( t = unbalancing_removal( &n ) ) ) {
00697     memoryPolicy.destroy( cast( t ) );
00698   }
00699       }
00700     }
00701 
00702   virtual ~Mapv() { clear(); }
00703 
00704   // -------------------------------------------------------------------
00705   // Verify the integrity of the tree
00706 
00707   bool verify() const
00708     {
00709       size_type count = 0 ;
00710       const_iterator  i = begin();
00711       const_iterator  j ;
00712 
00713       while ( i != end() &&
00714        ( ++(j=i) == end() || key_less(i->mapv_key(), j->mapv_key()) )
00715        && --j == i )
00716   { ++i ; ++count ; }
00717 
00718       return ( i == end() && count == size() );
00719     }
00720 };
00721 
00722 // ---------------------------------------------------------------------
00723 
00724 // For the 'no_delete' operator.
00725 
00726 template < class Derived_Type >
00727 class Mapv_no_delete
00728   : public Mapv<Derived_Type,MapvNullPolicy<Derived_Type> > {};
00729 
00730 // ---------------------------------------------------------------------
00731 
00732 }
00733 #ifdef SIERRA_IA64_OPTIMIZER_FIX
00734 #pragma optimize("", on)
00735 #endif
00736 
00737 #undef mapv_assert
00738 
00739 #endif // STK_UTIL_DIAG_Mapv_h
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines