Sierra Toolkit  Version of the Day
Mapv.hpp
1 #ifndef STK_UTIL_DIAG_Mapv_h
2 #define STK_UTIL_DIAG_Mapv_h
3 
4 #include <stk_util/util/FeatureTest.hpp>
5 #include <cstddef>
6 
7 // ---------------------------------------------------------------------
8 // Author: H. Carter Edwards
9 //
10 // Purpose:
11 // A map-style associative container for large allocated data objects.
12 // ---------------------------------------------------------------------
13 // Usage / Instantiation:
14 //
15 // Each node in a "virtual map" must be derived from the 'MapvNode'
16 // base class. Their should be only one 'MapvNode' base class.
17 //
18 // class MY_CLASS : public MapvNode<Key_Type> , other_base_classes {
19 // // 'MY_CLASS' internal data & methods
20 // };
21 //
22 // class MY_CLASS2 : MY_CLASS {
23 //
24 // };
25 //
26 // The Key_Type template argument is the data type of the ordering key
27 // for the virtual map. The Key_Type must support the 'less<Key_Type>'
28 // template function object.
29 // ---------------------------------------------------------------------
30 // Features and Limitations:
31 //
32 // The 'MapvNode' derived objects may be inserted into a 'Mapv' container
33 // without being copied.
34 //
35 // When a 'MapvNode' derived object is destroyed it is automatically
36 // removed from the 'Mapv' container. Destruction of a 'Mapv' container
37 // automatically invokes the 'delete' operator for each 'MapvNode'
38 // derived object that resides in the container at the time of its
39 // destruction.
40 //
41 // The 'insert' and 'remove' operations cause the 'Mapv' container to
42 // rebalance its binary tree. These rebalancing algorithms are lengthy.
43 // As such the majority of the 'insert' and 'remove' operations are
44 // implemented in the seperately compiled 'Mapv.C' file. The subprograms
45 // in 'Mapv.C' are shared by all instantiations of 'Mapv', thus
46 // "code bloat" is kept to a minimum.
47 //
48 // Alteration of a 'mavnode' derived objects 'key' value is likely
49 // to invalidate its position in the binary. Thus alteration of the
50 // 'key' value removes the object from its 'Mapv' container.
51 //
52 // ---------------------------------------------------------------------
53 // Acknowledgements:
54 //
55 // Most all of the algorithms in this class were obtained from
56 // the Hewlett-Packard source for the Standard Template Library,
57 // thus the inclusion of Hewlett-Packard's copyright notice.
58 // ---------------------------------------------------------------------
59 /*
60  * Copyright (c) 1994
61  * Hewlett-Packard Company
62  *
63  * Permission to use, copy, modify, distribute and sell this software
64  * and its documentation for any purpose is hereby granted without fee,
65  * provided that the above copyright notice appear in all copies and
66  * that both that copyright notice and this permission notice appear
67  * in supporting documentation. Hewlett-Packard Company makes no
68  * representations about the suitability of this software for any
69  * purpose. It is provided "as is" without express or implied warranty.
70  *
71  */
72 /*
73 Red-black tree class, designed for use in implementing STL
74 associative containers (set, multiset, map, and multimap).
75 The insertion and deletion algorithms are based on those in Cormen,
76 Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
77 except that
78 
79 (1) the header cell is maintained with links not only to the root
80 but also to the leftmost node of the tree, to enable constant time
81 begin(), and to the rightmost node of the tree, to enable linear time
82 performance when used with the generic set algorithms (set_union,
83 etc.);
84 
85 (2) when a node being deleted has two children its successor node is
86 relinked into its place, rather than copied, so that the only
87 iterators invalidated are those referring to the deleted node.
88 */
89 // ---------------------------------------------------------------------
90 // Don't force usage of 'assert', but if available then use it
91 
92 #ifdef MAPV_ASSERT_H
93 #define mapv_assert( expr ) assert( expr )
94 #else
95 #define mapv_assert( expr ) /* do nothing */
96 #endif
97 
98 // STL includes:
99 
100 #include <utility>
101 #include <iterator>
102 #include <functional>
103 
104 #ifdef SIERRA_IA64_OPTIMIZER_FIX
105 #pragma optimize("", off)
106 #endif
107 
108 namespace sierra {
109 
110 // class MyType : public MapvNode<MyKey> { ... };
111 
112 template < typename Key_Type , class Key_Compare > class MapvNode ;
113 
114 template < class Derived_Type , class Memory_Policy > class Mapv ;
115 
116 template < class Derived_Type , class Next , class Prev > class MapvIterator ;
117 
118 // ---------------------------------------------------------------------
119 // ---------------------------------------------------------------------
122 class MapvIterNext ;
123 class MapvIterPrev ;
124 
125 class MapvNodeBase {
126 private:
127 
128  enum { black = 0 , red = 1 };
129 
130  MapvNodeBase * parent ; // Binary tree node
131  MapvNodeBase * left ; // Binary tree node
132  MapvNodeBase * right ; // Binary tree node
133  unsigned color ; // Red-black color
134 
135  inline void remove_from_container();
136 
138  virtual ~MapvNodeBase() { remove_from_container(); }
139 
140  MapvNodeBase() : parent(0), left(0), right(0), color(black) {}
141 
142  // Friends of this very private class
143 
144  friend class MapvBase ;
145  friend class MapvIterNext ;
146  friend class MapvIterPrev ;
147  template < class dType , class N, class P > friend class MapvIterator ;
148  template < class dType , class mPolicy > friend class Mapv ;
149  template < class kType , class kCompare > friend class MapvNode ;
150 };
151 
152 // ---------------------------------------------------------------------
167 template < typename Key_Type , class Key_Compare = std::less<Key_Type> >
168 class MapvNode : private MapvNodeBase {
169 public:
170 
171  typedef Key_Type key_type ;
172  typedef Key_Compare key_compare ;
173 
174  bool mapv_valid() const { return this && MapvNodeBase::parent ; }
175  void mapv_remove() { MapvNodeBase::remove_from_container(); }
176 
178  const key_type & mapv_key() const { return Key ; }
179 
181  const Key_Type & mapv_key( const key_type & K )
182  { remove_from_container(); return Key = K ; }
183 
185  virtual ~MapvNode() {}
186  MapvNode() {}
187  MapvNode( const key_type & K ) : Key(K) {}
188 
189 private:
190 
191  Key_Type Key ;
192 
193  // Disallow copy constructor and assignment operator
194 
195  MapvNode( const MapvNode<Key_Type,Key_Compare> & );
196 
197  MapvNode<Key_Type,Key_Compare> &
198  operator = ( const MapvNode<Key_Type,Key_Compare> & );
199 
200  // friends to access the MapvNodeBase base class and Key member
201  template< class dType , class N , class P > friend class MapvIterator ;
202  template< class dType , class mPolicy > friend class Mapv ;
203 };
204 
205 //----------------------------------------------------------------------
206 //----------------------------------------------------------------------
210 public:
211  typedef MapvNodeBase * ptr ;
212  typedef const MapvNodeBase * cptr ;
213  static ptr op( cptr x )
214  {
215  ptr y = x->right;
216  if ( y ) {
217  while ( y->left ) y = y->left ;
218  }
219  else {
220  mapv_assert( x->parent /* incrementing 'end()' iterator */ );
221  y = x->parent ;
222  while ( x == y->right ) y = ( x = y )->parent ;
223  if ( x == y->parent ) y = y->right ;
224  }
225  return y ;
226  }
227 };
228 
229 class MapvIterPrev {
230 public:
231  typedef MapvNodeBase * ptr ;
232  typedef const MapvNodeBase * cptr ;
233  static ptr op( cptr x )
234  {
235  ptr y = x->left;
236  if ( y ) {
237  while ( y->right ) y = y->right ;
238  }
239  else {
240  mapv_assert( x->parent /* decrementing 'end()' iterator */ );
241  y = x->parent ;
242  while ( x == y->left ) y = ( x = y )->parent ;
243  if ( x == y->parent ) y = y->left ;
244  }
245  return y ;
246  }
247 };
248 
249 template < class Type , class Next , class Prev >
250 class MapvIterator : public std::iterator<std::bidirectional_iterator_tag,Type>
251 {
252 private:
253  template < class T , class M > friend class Mapv ;
254  template < class T , class N, class P > friend class MapvIterator ;
255 
256  Type * n ;
257 
261  Type * ptr() const { return n->MapvNodeBase::parent == 0 ? (Type*) 0 : n ; }
262 
263  MapvIterator( MapvNodeBase * x ) : n( static_cast<Type*>(x) ) {}
264  MapvIterator( Type * x ) : n( x ) {}
265  MapvIterator( Type & x ) : n( &x ) {}
266 
267 public:
268 
269  typedef MapvIterator<Type,Next,Prev> SelfType ;
270 
275  template<class T,class N, class P>
276  MapvIterator( const MapvIterator<T,N,P> & x ) : n( x.n ) {}
277 
282  template<class T,class N,class P>
283  SelfType & operator = ( const MapvIterator<T,N,P> & x )
284  { n = x.n ; return *this ; }
285 
290  bool valid_to_dereference() const { return n && n->MapvNodeBase::parent ; }
291 
292 // /** Conversion to bool: true for dereferenceable iterator */
293 // operator bool () const { return valid_to_dereference(); }
294 
295  //--------------------------------------------------------------------
296 
297  MapvIterator() : n(0) {}
298  MapvIterator( const SelfType & x ) : n( x.n ) {}
299 
300  SelfType & operator = ( const SelfType & x ) { n = x.n ; return *this ; }
301 
302  Type & operator * () const
303  { mapv_assert( valid_to_dereference() ); return *n ; }
304  Type * operator ->() const
305  { mapv_assert( valid_to_dereference() ); return n ; }
306 
307  SelfType & operator++(){ n = static_cast<Type*>(Next::op(n)); return *this; }
308  SelfType & operator--(){ n = static_cast<Type*>(Prev::op(n)); return *this; }
309 
310  SelfType operator++(int)
311  { Type * t = n ; n = static_cast<Type*>(Next::op(n)); return SelfType(t); }
312 
313  SelfType operator--(int)
314  { Type * t = n ; n = static_cast<Type*>(Prev::op(n)); return SelfType(t); }
315 
316  template<class T,class N, class P>
317  bool operator == ( const MapvIterator<T,N,P> & y ) const
318  { return n == y.n ; }
319 
320  template<class T,class N, class P>
321  bool operator != ( const MapvIterator<T,N,P> & y ) const
322  { return n != y.n ; }
323 };
324 
325 //----------------------------------------------------------------------
326 //----------------------------------------------------------------------
329 class MapvBase : private MapvNodeBase {
330 private:
331 
332  MapvNodeBase left_end ; // 'rend()' node
333  MapvNodeBase right_end ; // 'end()' node
334 
335  size_t Count ;
336 
337  //------------------------------------
338 
339  typedef MapvNodeBase nType ;
340  typedef MapvNodeBase * pType ;
341 
342  static MapvBase * container( const nType * x )
343  {
344  MapvBase * h = 0 ;
345  if ( x && x->parent ) {
346  // Search for root node, while loop breaks at root node
347  while ( x != x->parent->parent ) x = x->parent ;
348  // the root node's parent is the header
349  h = static_cast<MapvBase*>( x->parent );
350  }
351  return h ;
352  }
353 
354 // ---------------------------------------------------------------------
355 
356  static nType * minimum( nType * );
357  static nType * maximum( nType * );
358 
359  void rotate_left( nType * x );
360  void rotate_right( nType * x );
361 
362  nType * header() const { return const_cast<nType*>((const nType*)this); }
363  nType * rightmost() const { return right_end.left ; }
364  nType * leftmost() const { return left_end.right ; }
365 
366  void rightmost( nType * N ) { right_end.left = N ; }
367  void leftmost( nType * N ) { left_end.right = N ; }
368  void root( nType * N ) { header()->parent = N ; }
369 
370  //------------------------------------
371 
372  virtual ~MapvBase();
373 
374  void remove( MapvNodeBase * );
375 
376  nType * nRoot() const { return header()->parent ; }
377  nType * nEnd() const { return const_cast<nType*>( & right_end ); }
378  nType * nREnd() const { return const_cast<nType*>( & left_end ); }
379 
380  nType * nBegin() const
381  { return ( left_end.right != nREnd() ) ? left_end.right : nEnd(); }
382 
383  nType * nRBegin() const
384  { return ( right_end.left != nEnd() ) ? right_end.left : nREnd(); }
385 
386  MapvBase() : MapvNodeBase(), left_end(), right_end(), Count(0)
387  {
388  header()->color = red ; /* Color the header node red */
389  leftmost( header()->left = nREnd() ); // left end of the tree
390  rightmost( header()->right = nEnd() ); // right end of the tree
391  }
392 
393  void insert( nType * y , nType * z , bool z_lt_y );
394 
395  nType * unbalancing_removal( nType ** n );
396  static void WarnOptimize();
397 
398  friend class MapvNodeBase ;
399  template< class dType , class mPolicy > friend class Mapv ;
400 };
401 
402 inline void MapvNodeBase::remove_from_container()
403 {
404  MapvBase * const c = MapvBase::container(this);
405  if ( c ) c->remove( this );
406 }
407 
408 //----------------------------------------------------------------------
409 //----------------------------------------------------------------------
410 
411 template <class Derived_Type>
412 struct MapvNewDeletePolicy {
413  typedef typename Derived_Type::key_type key_type ;
414 
415  Derived_Type * create( const key_type & K ) { return new Derived_Type(K); }
416 
417  void destroy( Derived_Type * p ) { delete p ; }
418 };
419 
420 template <class Derived_Type>
421 struct MapvDeleteOnlyPolicy {
422  typedef typename Derived_Type::key_type key_type ;
423 
424  Derived_Type * create( const key_type & K ) { return (Derived_Type*) 0 ; }
425 
426  void destroy( Derived_Type * p ) { delete p ; }
427 };
428 
429 template <class Derived_Type>
430 struct MapvNullPolicy {
431  typedef typename Derived_Type::key_type key_type ;
432 
433  Derived_Type * create( const key_type & K ) { return (Derived_Type*) 0 ; }
434 
435  void destroy( Derived_Type * p ) {}
436 };
437 
438 //----------------------------------------------------------------------
439 //----------------------------------------------------------------------
440 
441 template < class Derived_Type ,
442  class Memory_Policy = MapvDeleteOnlyPolicy<Derived_Type> >
443 class Mapv : public MapvBase {
444 public:
445 
446  // 'self' type
447  typedef Mapv<Derived_Type,Memory_Policy> SelfType ;
448 
449  // NOTE: value_type == Derived_Type, the chain of
450  // typedefs insures the correct derivation has occured.
451 
452  typedef typename Derived_Type::key_type key_type ;
453  typedef typename Derived_Type::key_compare key_compare ;
454  typedef Derived_Type value_type ;
455  typedef size_t size_type ;
456  typedef ptrdiff_t difference_type ;
457 
458  typedef value_type * pointer ;
459  typedef const value_type * const_pointer ;
460  typedef value_type & reference ;
461  typedef const value_type & const_reference ;
462 
463  struct value_compare
464  : public std::binary_function<value_type,value_type,bool>
465  {
466  protected:
467  key_compare comp ;
468  public:
469  bool operator()(const value_type& x, const value_type& y) const
470  { return comp( x.mapv_key() , y.mapv_key() ); }
471  };
472 
473  typedef MapvIterNext Next ;
474  typedef MapvIterPrev Prev ;
475 
476  typedef MapvIterator< Derived_Type,Next,Prev> iterator ;
477  typedef MapvIterator<const Derived_Type,Next,Prev> const_iterator ;
478  typedef MapvIterator< Derived_Type,Prev,Next> reverse_iterator ;
479  typedef MapvIterator<const Derived_Type,Prev,Next> const_reverse_iterator ;
480 
481  typedef std::pair<iterator, bool> pair_iterator_bool ;
482 
483 private:
484 
485  // Disallow copy and assignment
486 
487  Mapv( const SelfType & );
488 
489  SelfType & operator = ( const SelfType & );
490 
491  Memory_Policy memoryPolicy ;
492  key_compare key_less ; // An "abstract" object
493  value_compare value_less ; // An "abstract" object
494 
495  static const key_type & key( nType * const n )
496  { return static_cast<MapvNode<key_type,key_compare>*>(n)->mapv_key(); }
497 
498  static value_type * cast( nType * n )
499  { return static_cast<value_type*>(n); }
500 
501 // WORKAROUND: 4/7/2010 -- This works for our SGI Itanium Intel compiler on sasg1132
502 #ifdef SIERRA_IA64_OPTIMIZER_FIX
503  Derived_Type * lb( const key_type & k ) const
504  {
505  volatile pType y = nEnd(); // [DGB] -- Altix intel-10.1 optimizer hack
506  volatile pType x = nRoot(); // [DGB] -- Altix intel-10.1 optimizer hack
507  while ( x ) {
508  bool go_right = key_less(key(x), k);
509 
510  if (go_right) {
511  x = x->right;
512  }
513  else {
514  y = x;
515  x = x->left;
516  }
517  }
518  return cast(y);
519  }
520 
521  Derived_Type * ub( const key_type & k ) const
522  {
523  pType y = nEnd();
524  pType x = nRoot();
525  while ( x ) x = key_less(k,key(x)) ? ( y = x )->left : x->right ;
526  return cast(y);
527  }
528 
529 #else
530  Derived_Type * lb( const key_type & k ) const
531  {
532  pType y = nEnd();
533  pType x = nRoot();
534  while ( x ) x = key_less(key(x),k) ? x->right : ( y = x )->left ;
535  return cast(y);
536  }
537 
538  Derived_Type * ub( const key_type & k ) const
539  {
540  pType y = nEnd();
541  pType x = nRoot();
542  while ( x ) x = key_less(k,key(x)) ? ( y = x )->left : x->right ;
543  return cast(y);
544  }
545 #endif // SIERRA_IA64_OPTIMIZER_FIX
546 
547  Derived_Type * f( const key_type & k ) const
548  {
549  nType * const e = nEnd();
550  nType * const y = lb(k); // k <= y->mapv_key()
551 
552  // If 'end()' or k < y->mapv_key() then not found
553  return cast( ( y == e || key_less(k,key(y)) ) ? e : y );
554  }
555 
556 public:
557 
558  static SelfType * container( const Derived_Type & n )
559  {
560  MapvBase * const c = MapvBase::container(&n);
561  return c ? static_cast<SelfType*>( c ) : (SelfType*) 0 ;
562  }
563 
564  static SelfType * container( const Derived_Type * n )
565  { return n ? container( *n ) : (SelfType*) 0 ; }
566 
567  // -------------------------------------------------------------------
568 
569  key_compare key_comp() const { return key_less ; }
570  value_compare value_comp() const { return value_less ; }
571 
572  const_iterator begin() const { return const_iterator(cast(nBegin())); }
573  const_iterator end() const { return const_iterator(cast(nEnd())); }
574  const_iterator rbegin() const { return const_iterator(cast(nRBegin())); }
575  const_iterator rend() const { return const_iterator(cast(nREnd())); }
576 
577  iterator begin() { return iterator(cast(nBegin())); }
578  iterator end() { return iterator(cast(nEnd())); }
579  iterator rbegin() { return iterator(cast(nRBegin())); }
580  iterator rend() { return iterator(cast(nREnd())); }
581 
582  bool empty() const { return MapvBase::Count == 0 ; }
583  size_type size() const { return MapvBase::Count ; }
584 
585  // -------------------------------------------------------------------
586  // search operations:
587 
588  iterator lower_bound( const key_type & k ) { return iterator( lb(k) ); }
589  iterator upper_bound( const key_type & k ) { return iterator( ub(k) ); }
590 
591  const_iterator lower_bound( const key_type & k ) const
592  { return const_iterator( lb(k) ); }
593 
594  const_iterator upper_bound( const key_type & k ) const
595  { return const_iterator( ub(k) ); }
596 
597  iterator find( const key_type & k ) { return iterator( f(k) ); }
598 
599  const_iterator find( const key_type & k ) const
600  { return const_iterator( f(k) ); }
601 
602  // -------------------------------------------------------------------
603 
607  value_type & operator[]( const key_type & k )
608  {
609  pType y = nEnd();
610  pType x = nRoot();
611 
612  bool flag = true ;
613 
614  while ( x )
615  { y = x ; x = ( flag = key_less(k, key(x)) ) ? x->left : x->right ; }
616 
617  /* flag = k < y , check previous value if exists */
618 
619  const bool k_lt_y = flag ;
620 
621  x = flag && y != nBegin() ? ( flag = false , MapvIterPrev::op(y) ) : y ;
622 
623  if ( flag || ( flag = key_less( key(x) , k ) ) ) {
624  x = memoryPolicy.create(k);
625  MapvBase::insert( y , x , k_lt_y );
626  }
627  return *static_cast<pointer>(x);
628  }
629 
638  pair_iterator_bool insert( const pointer v )
639  {
640  WarnOptimize();
641  pType y = nEnd();
642  pType x = nRoot();
643 
644  bool flag = true ;
645 
646  while ( x ) {
647  y = x ;
648  x = ( flag = key_less(v->mapv_key(), key(x)) ) ? x->left : x->right ;
649  }
650 
651  /* flag = k < y , check previous value if exists */
652 
653  const bool k_lt_y = flag ;
654 
655  x = flag && y != nBegin() ? ( flag = false , MapvIterPrev::op(y) ) : y ;
656 
657  if ( flag || ( flag = key_less( key(x) , v->mapv_key() ) ) ) {
658  x = v ;
659  MapvBase::insert( y , x , k_lt_y );
660  }
661  return pair_iterator_bool( iterator(x), flag );
662  }
663 
664  pair_iterator_bool insert( reference v ) { return insert( &v ); }
665 
666  // -------------------------------------------------------------------
667  // Remove & erase operations
668 
669  pointer remove( const key_type & k )
670  {
671  pointer v = f(k);
672  return ( nEnd() != v ) ? ( MapvBase::remove(v) , v ) : (pointer) 0 ;
673  }
674 
675  pointer remove( iterator i )
676  { MapvBase::remove( i.n ); return i.n ; }
677 
678  void erase( const key_type & K )
679  { pointer v = remove(K); if ( v ) memoryPolicy.destroy(v); }
680 
681  void erase( iterator i )
682  { pointer v = remove(i); if ( v ) memoryPolicy.destroy(v); }
683 
684  // -------------------------------------------------------------------
685  // construction / destruction
686  // Destruction will apply the 'Derived_Type::destroy'
687  // method to each node in the tree.
688 
689  Mapv() {}
690 
691  void clear()
692  {
693  if ( Count ) {
694  nType * n = nBegin();
695  nType * t ;
696  while ( ( t = unbalancing_removal( &n ) ) ) {
697  memoryPolicy.destroy( cast( t ) );
698  }
699  }
700  }
701 
702  virtual ~Mapv() { clear(); }
703 
704  // -------------------------------------------------------------------
705  // Verify the integrity of the tree
706 
707  bool verify() const
708  {
709  size_type count = 0 ;
710  const_iterator i = begin();
711  const_iterator j ;
712 
713  while ( i != end() &&
714  ( ++(j=i) == end() || key_less(i->mapv_key(), j->mapv_key()) )
715  && --j == i )
716  { ++i ; ++count ; }
717 
718  return ( i == end() && count == size() );
719  }
720 };
721 
722 // ---------------------------------------------------------------------
723 
724 // For the 'no_delete' operator.
725 
726 template < class Derived_Type >
727 class Mapv_no_delete
728  : public Mapv<Derived_Type,MapvNullPolicy<Derived_Type> > {};
729 
730 // ---------------------------------------------------------------------
731 
732 }
733 #ifdef SIERRA_IA64_OPTIMIZER_FIX
734 #pragma optimize("", on)
735 #endif
736 
737 #undef mapv_assert
738 
739 #endif // STK_UTIL_DIAG_Mapv_h
const key_type & mapv_key() const
Definition: Mapv.hpp:178
Definition: Env.cpp:53
const Key_Type & mapv_key(const key_type &K)
Definition: Mapv.hpp:181
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T &value)
Part * find(const PartVector &parts, const std::string &name)
Find a part by name in a collection of parts.
Definition: Part.cpp:22
virtual ~MapvNode()
Definition: Mapv.hpp:185
bool insert(PartVector &v, Part &part)
Insert a part into a properly ordered collection of parts. Returns true if this is a new insertion...
Definition: Part.cpp:85
eastl::iterator_traits< InputIterator >::difference_type count(InputIterator first, InputIterator last, const T &value)