1 #ifndef STK_UTIL_DIAG_Mapv_h 2 #define STK_UTIL_DIAG_Mapv_h 4 #include <stk_util/util/FeatureTest.hpp> 93 #define mapv_assert( expr ) assert( expr ) 95 #define mapv_assert( expr ) 102 #include <functional> 104 #ifdef SIERRA_IA64_OPTIMIZER_FIX 105 #pragma optimize("", off) 112 template <
typename Key_Type ,
class Key_Compare >
class MapvNode ;
114 template <
class Derived_Type ,
class Memory_Policy >
class Mapv ;
116 template <
class Derived_Type ,
class Next ,
class Prev >
class MapvIterator ;
128 enum { black = 0 , red = 1 };
130 MapvNodeBase * parent ;
131 MapvNodeBase * left ;
132 MapvNodeBase * right ;
135 inline void remove_from_container();
138 virtual ~MapvNodeBase() { remove_from_container(); }
140 MapvNodeBase() : parent(0), left(0), right(0), color(black) {}
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 ;
167 template <
typename Key_Type ,
class Key_Compare = std::less<Key_Type> >
168 class MapvNode :
private MapvNodeBase {
171 typedef Key_Type key_type ;
172 typedef Key_Compare key_compare ;
174 bool mapv_valid()
const {
return this && MapvNodeBase::parent ; }
175 void mapv_remove() { MapvNodeBase::remove_from_container(); }
182 { remove_from_container();
return Key = K ; }
187 MapvNode(
const key_type & K ) : Key(K) {}
195 MapvNode(
const MapvNode<Key_Type,Key_Compare> & );
197 MapvNode<Key_Type,Key_Compare> &
198 operator = (
const MapvNode<Key_Type,Key_Compare> & );
201 template<
class dType ,
class N ,
class P >
friend class MapvIterator ;
202 template<
class dType ,
class mPolicy >
friend class Mapv ;
211 typedef MapvNodeBase * ptr ;
212 typedef const MapvNodeBase * cptr ;
213 static ptr op( cptr x )
217 while ( y->left ) y = y->left ;
220 mapv_assert( x->parent );
222 while ( x == y->right ) y = ( x = y )->parent ;
223 if ( x == y->parent ) y = y->right ;
231 typedef MapvNodeBase * ptr ;
232 typedef const MapvNodeBase * cptr ;
233 static ptr op( cptr x )
237 while ( y->right ) y = y->right ;
240 mapv_assert( x->parent );
242 while ( x == y->left ) y = ( x = y )->parent ;
243 if ( x == y->parent ) y = y->left ;
249 template <
class Type ,
class Next ,
class Prev >
250 class MapvIterator :
public std::iterator<std::bidirectional_iterator_tag,Type>
253 template <
class T ,
class M >
friend class Mapv ;
254 template <
class T ,
class N,
class P >
friend class MapvIterator ;
261 Type * ptr()
const {
return n->MapvNodeBase::parent == 0 ? (Type*) 0 : n ; }
263 MapvIterator( MapvNodeBase * x ) : n( static_cast<Type*>(x) ) {}
264 MapvIterator( Type * x ) : n( x ) {}
265 MapvIterator( Type & x ) : n( &x ) {}
269 typedef MapvIterator<Type,Next,Prev> SelfType ;
275 template<
class T,
class N,
class P>
276 MapvIterator(
const MapvIterator<T,N,P> & x ) : n( x.n ) {}
282 template<
class T,
class N,
class P>
283 SelfType & operator = (
const MapvIterator<T,N,P> & x )
284 { n = x.n ;
return *this ; }
290 bool valid_to_dereference()
const {
return n && n->MapvNodeBase::parent ; }
297 MapvIterator() : n(0) {}
298 MapvIterator(
const SelfType & x ) : n( x.n ) {}
300 SelfType & operator = (
const SelfType & x ) { n = x.n ;
return *this ; }
302 Type & operator * ()
const 303 { mapv_assert( valid_to_dereference() );
return *n ; }
304 Type * operator ->()
const 305 { mapv_assert( valid_to_dereference() );
return n ; }
307 SelfType & operator++(){ n =
static_cast<Type*
>(Next::op(n));
return *
this; }
308 SelfType & operator--(){ n =
static_cast<Type*
>(Prev::op(n));
return *
this; }
310 SelfType operator++(
int)
311 { Type * t = n ; n =
static_cast<Type*
>(Next::op(n));
return SelfType(t); }
313 SelfType operator--(
int)
314 { Type * t = n ; n =
static_cast<Type*
>(Prev::op(n));
return SelfType(t); }
316 template<
class T,
class N,
class P>
317 bool operator == (
const MapvIterator<T,N,P> & y )
const 318 {
return n == y.n ; }
320 template<
class T,
class N,
class P>
321 bool operator != (
const MapvIterator<T,N,P> & y )
const 322 {
return n != y.n ; }
332 MapvNodeBase left_end ;
333 MapvNodeBase right_end ;
339 typedef MapvNodeBase nType ;
340 typedef MapvNodeBase * pType ;
342 static MapvBase * container(
const nType * x )
345 if ( x && x->parent ) {
347 while ( x != x->parent->parent ) x = x->parent ;
349 h =
static_cast<MapvBase*
>( x->parent );
356 static nType * minimum( nType * );
357 static nType * maximum( nType * );
359 void rotate_left( nType * x );
360 void rotate_right( nType * x );
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 ; }
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 ; }
374 void remove( MapvNodeBase * );
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 ); }
380 nType * nBegin()
const 381 {
return ( left_end.right != nREnd() ) ? left_end.right : nEnd(); }
383 nType * nRBegin()
const 384 {
return ( right_end.left != nEnd() ) ? right_end.left : nREnd(); }
386 MapvBase() : MapvNodeBase(), left_end(), right_end(), Count(0)
388 header()->color = red ;
389 leftmost( header()->left = nREnd() );
390 rightmost( header()->right = nEnd() );
393 void insert( nType * y , nType * z ,
bool z_lt_y );
395 nType * unbalancing_removal( nType ** n );
396 static void WarnOptimize();
398 friend class MapvNodeBase ;
399 template<
class dType ,
class mPolicy >
friend class Mapv ;
402 inline void MapvNodeBase::remove_from_container()
404 MapvBase *
const c = MapvBase::container(
this);
405 if ( c ) c->remove(
this );
411 template <
class Derived_Type>
412 struct MapvNewDeletePolicy {
413 typedef typename Derived_Type::key_type key_type ;
415 Derived_Type * create(
const key_type & K ) {
return new Derived_Type(K); }
417 void destroy( Derived_Type * p ) {
delete p ; }
420 template <
class Derived_Type>
421 struct MapvDeleteOnlyPolicy {
422 typedef typename Derived_Type::key_type key_type ;
424 Derived_Type * create(
const key_type & K ) {
return (Derived_Type*) 0 ; }
426 void destroy( Derived_Type * p ) {
delete p ; }
429 template <
class Derived_Type>
430 struct MapvNullPolicy {
431 typedef typename Derived_Type::key_type key_type ;
433 Derived_Type * create(
const key_type & K ) {
return (Derived_Type*) 0 ; }
435 void destroy( Derived_Type * p ) {}
441 template <
class Derived_Type ,
442 class Memory_Policy = MapvDeleteOnlyPolicy<Derived_Type> >
443 class Mapv :
public MapvBase {
447 typedef Mapv<Derived_Type,Memory_Policy> SelfType ;
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 ;
458 typedef value_type * pointer ;
459 typedef const value_type * const_pointer ;
460 typedef value_type & reference ;
461 typedef const value_type & const_reference ;
464 :
public std::binary_function<value_type,value_type,bool>
469 bool operator()(
const value_type& x,
const value_type& y)
const 470 {
return comp( x.mapv_key() , y.mapv_key() ); }
473 typedef MapvIterNext Next ;
474 typedef MapvIterPrev Prev ;
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 ;
481 typedef std::pair<iterator, bool> pair_iterator_bool ;
487 Mapv(
const SelfType & );
489 SelfType & operator = (
const SelfType & );
491 Memory_Policy memoryPolicy ;
492 key_compare key_less ;
493 value_compare value_less ;
495 static const key_type & key( nType *
const n )
496 {
return static_cast<MapvNode<key_type,key_compare>*
>(n)->mapv_key(); }
498 static value_type * cast( nType * n )
499 {
return static_cast<value_type*
>(n); }
502 #ifdef SIERRA_IA64_OPTIMIZER_FIX 503 Derived_Type * lb(
const key_type & k )
const 505 volatile pType y = nEnd();
506 volatile pType x = nRoot();
508 bool go_right = key_less(key(x), k);
521 Derived_Type * ub(
const key_type & k )
const 525 while ( x ) x = key_less(k,key(x)) ? ( y = x )->left : x->right ;
530 Derived_Type * lb(
const key_type & k )
const 534 while ( x ) x = key_less(key(x),k) ? x->right : ( y = x )->left ;
538 Derived_Type * ub(
const key_type & k )
const 542 while ( x ) x = key_less(k,key(x)) ? ( y = x )->left : x->right ;
545 #endif // SIERRA_IA64_OPTIMIZER_FIX 547 Derived_Type * f(
const key_type & k )
const 549 nType *
const e = nEnd();
550 nType *
const y = lb(k);
553 return cast( ( y == e || key_less(k,key(y)) ) ? e : y );
558 static SelfType * container(
const Derived_Type & n )
560 MapvBase *
const c = MapvBase::container(&n);
561 return c ?
static_cast<SelfType*
>( c ) : (SelfType*) 0 ;
564 static SelfType * container(
const Derived_Type * n )
565 {
return n ? container( *n ) : (SelfType*) 0 ; }
569 key_compare key_comp()
const {
return key_less ; }
570 value_compare value_comp()
const {
return value_less ; }
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())); }
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())); }
582 bool empty()
const {
return MapvBase::Count == 0 ; }
583 size_type size()
const {
return MapvBase::Count ; }
588 iterator lower_bound(
const key_type & k ) {
return iterator( lb(k) ); }
589 iterator
upper_bound(
const key_type & k ) {
return iterator( ub(k) ); }
591 const_iterator lower_bound(
const key_type & k )
const 592 {
return const_iterator( lb(k) ); }
594 const_iterator
upper_bound(
const key_type & k )
const 595 {
return const_iterator( ub(k) ); }
597 iterator
find(
const key_type & k ) {
return iterator( f(k) ); }
599 const_iterator
find(
const key_type & k )
const 600 {
return const_iterator( f(k) ); }
607 value_type & operator[](
const key_type & k )
615 { y = x ; x = ( flag = key_less(k, key(x)) ) ? x->left : x->right ; }
619 const bool k_lt_y = flag ;
621 x = flag && y != nBegin() ? ( flag = false , MapvIterPrev::op(y) ) : y ;
623 if ( flag || ( flag = key_less( key(x) , k ) ) ) {
624 x = memoryPolicy.create(k);
625 MapvBase::insert( y , x , k_lt_y );
627 return *
static_cast<pointer
>(x);
638 pair_iterator_bool
insert(
const pointer v )
648 x = ( flag = key_less(v->mapv_key(), key(x)) ) ? x->left : x->right ;
653 const bool k_lt_y = flag ;
655 x = flag && y != nBegin() ? ( flag = false , MapvIterPrev::op(y) ) : y ;
657 if ( flag || ( flag = key_less( key(x) , v->mapv_key() ) ) ) {
659 MapvBase::insert( y , x , k_lt_y );
661 return pair_iterator_bool( iterator(x), flag );
664 pair_iterator_bool
insert( reference v ) {
return insert( &v ); }
669 pointer
remove(
const key_type & k )
672 return ( nEnd() != v ) ? ( MapvBase::remove(v) , v ) : (pointer) 0 ;
675 pointer
remove( iterator i )
676 { MapvBase::remove( i.n );
return i.n ; }
678 void erase(
const key_type & K )
679 { pointer v =
remove(K);
if ( v ) memoryPolicy.destroy(v); }
681 void erase( iterator i )
682 { pointer v =
remove(i);
if ( v ) memoryPolicy.destroy(v); }
694 nType * n = nBegin();
696 while ( ( t = unbalancing_removal( &n ) ) ) {
697 memoryPolicy.destroy( cast( t ) );
702 virtual ~Mapv() { clear(); }
709 size_type
count = 0 ;
710 const_iterator i = begin();
713 while ( i != end() &&
714 ( ++(j=i) == end() || key_less(i->mapv_key(), j->mapv_key()) )
718 return ( i == end() &&
count == size() );
726 template <
class Derived_Type >
728 :
public Mapv<Derived_Type,MapvNullPolicy<Derived_Type> > {};
733 #ifdef SIERRA_IA64_OPTIMIZER_FIX 734 #pragma optimize("", on) 739 #endif // STK_UTIL_DIAG_Mapv_h const key_type & mapv_key() const
const Key_Type & mapv_key(const key_type &K)
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.
bool insert(PartVector &v, Part &part)
Insert a part into a properly ordered collection of parts. Returns true if this is a new insertion...
eastl::iterator_traits< InputIterator >::difference_type count(InputIterator first, InputIterator last, const T &value)