Setv.hpp

00001 /*------------------------------------------------------------------------*/
00002 /*      phdMesh : Parallel Heterogneous Dynamic unstructured Mesh         */
00003 /*                Copyright (2007) Sandia Corporation                     */
00004 /*                                                                        */
00005 /*  Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive   */
00006 /*  license for use of this work by or on behalf of the U.S. Government.  */
00007 /*                                                                        */
00008 /*  This library is free software; you can redistribute it and/or modify  */
00009 /*  it under the terms of the GNU Lesser General Public License as        */
00010 /*  published by the Free Software Foundation; either version 2.1 of the  */
00011 /*  License, or (at your option) any later version.                       */
00012 /*                                                                        */
00013 /*  This library is distributed in the hope that it will be useful,       */
00014 /*  but WITHOUT ANY WARRANTY; without even the implied warranty of        */
00015 /*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU     */
00016 /*  Lesser General Public License for more details.                       */
00017 /*                                                                        */
00018 /*  You should have received a copy of the GNU Lesser General Public      */
00019 /*  License along with this library; if not, write to the Free Software   */
00020 /*  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307   */
00021 /*  USA                                                                   */
00022 /*------------------------------------------------------------------------*/
00023 
00024 #ifndef util_Setv_hpp
00025 #define util_Setv_hpp
00026 
00027 #include <utility>
00028 #include <iterator>
00029 #include <functional>
00030 
00031 namespace phdmesh {
00032 
00083 // ---------------------------------------------------------------------
00084 // ---------------------------------------------------------------------
00085 
00086 #ifndef DOXYGEN_COMPILE
00087 
00088 template < typename KeyType > class SetvMember ;
00089 
00090 template < class ValueType , bool Forward > class SetvIter ;
00091 
00092 template < class ValueType, class KeyCompare, class Allocator > class Setv ;
00093 
00094 // ---------------------------------------------------------------------
00095 
00096 template<>
00097 class SetvMember<void> {
00098 public:
00099   ~SetvMember(); // Destructor removes member from its container
00100   SetvMember();
00101 
00102   enum { black = 0 , red = 1 };
00103 
00104   SetvMember<void> * parent ; // Binary tree node
00105   SetvMember<void> * left ;   // Binary tree node
00106   SetvMember<void> * right ;  // Binary tree node
00107   unsigned           color ;  // Red-black color
00108 
00109 private:
00110   SetvMember<void>( const SetvMember<void> & );
00111   SetvMember<void> & operator = ( const SetvMember<void> & );
00112 };
00113 
00114 template<bool Forward>
00115 SetvMember<void> * setv_iterate( const SetvMember<void> * );
00116 
00117 template<>
00118 SetvMember<void> * setv_iterate<true>(  const SetvMember<void> * );
00119 
00120 template<>
00121 SetvMember<void> * setv_iterate<false>( const SetvMember<void> * );
00122 
00123 #endif /* DOXYGEN_COMPILE */
00124 
00125 // ---------------------------------------------------------------------
00126 // ---------------------------------------------------------------------
00137 template < typename KeyType >
00138 class SetvMember : private SetvMember<void> {
00139 public:
00141   typedef KeyType key_type ;
00142 
00144   const key_type & key() const { return m_key ; }
00145 
00147   ~SetvMember() {}
00148 
00150   SetvMember() : SetvMember<void>() {}
00151 
00153   SetvMember( const SetvMember<key_type> & rhs )
00154     : SetvMember<void>(), m_key( rhs.m_key ) {}
00155 
00157   explicit SetvMember( const KeyType & k )
00158     : SetvMember<void>(), m_key( k ) {}
00159 
00160 private:
00161 
00163   SetvMember<key_type> & operator = ( const SetvMember<key_type> & m );
00164 
00165   key_type m_key ;
00166 
00167   template< class T , class C , class A > friend class Setv ;
00168   template< class T , bool F > friend class SetvIter ;
00169 };
00170 
00171 //----------------------------------------------------------------------
00178 template < class Type , bool Forward>
00179 class SetvIter : public std::iterator<std::bidirectional_iterator_tag,Type>
00180 {
00181 private:
00182 
00183   Type * n ;
00184 
00185   SetvIter( Type * x ) : n(x) {}
00186 
00187   template < class T , bool F >            friend class SetvIter ;
00188   template < class T , class C , class A > friend class Setv ;
00189 
00190 public:
00191 
00193   operator bool () const { return n && n->parent ; }
00194 
00196   SetvIter() : n(NULL) {}
00197 
00201   template<class T,bool F> SetvIter( const SetvIter<T,F> & x ) : n(x.n) {}
00202 
00206   template<class T,bool F>
00207     SetvIter<Type,Forward> & operator = ( const SetvIter<T,F> & x )
00208       { n = x.n ; return *this ; }
00209 
00211   template<class T,bool F>
00212     bool operator == ( const SetvIter<T,F> & y ) const { return n == y.n ; }
00213 
00215   template<class T,bool F>
00216     bool operator != ( const SetvIter<T,F> & y ) const { return n != y.n ; }
00217 
00219   Type & operator * () const
00220     { return *(operator bool() ? n : reinterpret_cast<Type*>(NULL) ); }
00221 
00223   Type * operator ->() const
00224     { return  (operator bool() ? n : reinterpret_cast<Type*>(NULL) ); }
00225 
00227   SetvIter<Type,Forward> & operator++()
00228     { n = static_cast<Type*>( setv_iterate<Forward>(n) ); return *this ; }
00229 
00231   SetvIter<Type,Forward> & operator--()
00232     { n = static_cast<Type*>( setv_iterate<!Forward>(n) ); return *this ; }
00233 
00235   SetvIter<Type,Forward> operator++(int)
00236     {
00237       Type * const t = n ;
00238       n = static_cast<Type*>( setv_iterate<Forward>(n) );
00239       return SetvIter<Type,Forward>(t);
00240     }
00241 
00243   SetvIter<Type,Forward> operator--(int)
00244     {
00245       Type * const t = n ;
00246       n = static_cast<Type*>( setv_iterate<!Forward>(n) );
00247       return SetvIter<Type,Forward>(t);
00248     }
00249 };
00250 
00251 //----------------------------------------------------------------------
00252 
00253 #ifndef DOXYGEN_COMPILE
00254 
00255 template<>
00256 class Setv<void,void,void> : private SetvMember<void> {
00257 protected:
00258   friend class SetvMember<void> ; // For destructor to remove
00259 
00260   Setv();
00261   ~Setv();
00262 
00263   size_t size() const { return m_size ; }
00264 
00265   SetvMember<void> * nRoot() const { return m_header.parent ; }
00266 
00267   SetvMember<void> * nEnd() const
00268     { return const_cast<SetvMember<void>*>( & m_right_end ); }
00269 
00270   SetvMember<void> * nREnd() const
00271     { return const_cast<SetvMember<void>*>( & m_left_end ); }
00272 
00273   SetvMember<void> * nBegin()  const
00274     { return ( m_left_end.right != nREnd() ) ? m_left_end.right : nEnd(); }
00275 
00276   SetvMember<void> * nRBegin() const
00277     { return ( m_right_end.left != nEnd() ) ? m_right_end.left : nREnd(); }
00278 
00279   void initialize();
00280 
00281   void insert( SetvMember<void> * y , SetvMember<void> * z , bool z_lt_y );
00282 
00283   void remove( SetvMember<void> * );
00284 
00285   SetvMember<void> * unbalancing_removal( SetvMember<void> ** n );
00286 
00287   static Setv<void,void,void> * container( const SetvMember<void> * );
00288 
00289 private:
00290 
00291   SetvMember<void> & m_header ;    // head node is this
00292   SetvMember<void>   m_left_end ;  // 'rend()' node
00293   SetvMember<void>   m_right_end ; // 'end()' node
00294   size_t             m_size ;
00295 
00296   // root      == m_header.parent
00297   // leftmost  == m_left_end.right
00298   // rightmost == m_right_end.left
00299 };
00300 
00301 #endif /* DOXYGEN_COMPILE */
00302 
00303 //----------------------------------------------------------------------
00317 template < class ValueType ,
00318            class KeyCompare = std::less<typename ValueType::key_type> ,
00319            class Allocator = std::allocator<ValueType> >
00320 class Setv : private Setv<void,void,void> {
00321 public:
00323   typedef typename ValueType::key_type key_type ;
00324 
00326   typedef ValueType   value_type ;
00327 
00329   typedef KeyCompare  key_compare ;
00330 
00332   typedef Allocator   allocator_type ;
00333 
00334 #ifndef DOXYGEN_COMPILE
00335 
00336   typedef typename allocator_type::reference       reference ;
00337   typedef typename allocator_type::const_reference const_reference ;
00338   typedef typename allocator_type::pointer         pointer ;
00339   typedef typename allocator_type::const_pointer   const_pointer ;
00340   typedef typename allocator_type::size_type       size_type ;
00341   typedef typename allocator_type::difference_type difference_type ;
00342 
00343   typedef SetvIter<      value_type,true>  iterator ;
00344   typedef SetvIter<const value_type,true>  const_iterator ;
00345   typedef SetvIter<      value_type,false> reverse_iterator ;
00346   typedef SetvIter<const value_type,false> const_reverse_iterator ;
00347 
00348   struct value_compare : public std::binary_function<value_type,value_type,bool>
00349   {
00350     protected:
00351       key_compare comp ;
00352     public:
00353       bool operator()(const value_type& x, const value_type& y) const {
00354         return comp( x.SetvMember<key_type>::key() ,
00355                      y.SetvMember<key_type>::key() );
00356       }
00357   };
00358 
00359 #endif /* DOXYGEN_COMPILE */
00360 
00361   ~Setv();
00362 
00364   Setv( const key_compare    & arg_compare = key_compare(),
00365         const allocator_type & arg_alloc = allocator_type() )
00366     : Setv<void,void,void>(),
00367       alloc(arg_alloc), key_less(arg_compare), value_less() {}
00368 
00370   Setv( const Setv<value_type,key_compare,allocator_type> & );
00371 
00373   Setv<value_type,key_compare,allocator_type> & operator =
00374     ( const Setv<value_type,key_compare,allocator_type> & );
00375 
00377   allocator_type get_allocator() const { return alloc ; }
00378 
00382   iterator begin() const
00383     { return iterator(
00384         static_cast<value_type*>( Setv<void,void,void>::nBegin() ) ); }
00385 
00386   iterator end() const
00387     { return iterator(
00388         static_cast<value_type*>( Setv<void,void,void>::nEnd() ) ); }
00389 
00390   reverse_iterator rbegin() const
00391     { return reverse_iterator(
00392         static_cast<value_type*>( Setv<void,void,void>::nRBegin() ) ); }
00393 
00394   reverse_iterator rend() const
00395     { return reverse_iterator(
00396         static_cast<value_type*>( Setv<void,void,void>::nREnd() ) ); }
00397 
00418   std::pair<iterator,bool>
00419     insert( const key_type & key , value_type * value = NULL );
00420 
00422   std::pair<iterator,bool> insert( value_type * );
00423 
00425   void erase( iterator position );
00426 
00428   void erase( value_type * );
00429 
00431   size_type erase( const key_type & );
00432 
00436   void remove( value_type & v )
00437     { Setv<void,void,void>::remove( &v ); }
00438 
00440   void clear();
00444   bool      empty() const { return Setv<void,void,void>::size() == 0 ; }
00445 
00447   size_type size()  const { return Setv<void,void,void>::size() ; }
00448 
00450   size_type max_size() const { return alloc.max_size(); }
00451 
00453   key_compare   key_comp()   const { return key_less ; }
00454 
00456   value_compare value_comp() const { return value_less ; }
00457 
00459   value_type & operator[]( const key_type & key );
00460 
00462   iterator  find(  const key_type & ) const ;
00463 
00465   size_type count( const key_type & ) const ;
00466 
00468   iterator  lower_bound( const key_type & ) const ;
00469 
00471   iterator  upper_bound( const key_type & ) const ;
00472 
00474   bool verify_ordering() const ;
00475 
00477   static
00478   Setv<value_type,key_compare,allocator_type> * container( const value_type & );
00479 
00480 private:
00481 
00482   typedef SetvMember<key_type> MemberType ;
00483 
00484   allocator_type alloc ;
00485   key_compare    key_less ;
00486   value_compare  value_less ;
00487 };
00488 
00489 } // namespace phdmesh
00490 
00491 // ---------------------------------------------------------------------
00492 // ---------------------------------------------------------------------
00493 // Implementation from here forward
00494 
00495 #ifndef DOXYGEN_COMPILE
00496 
00497 namespace phdmesh {
00498 
00499 //----------------------------------------------------------------------
00500 
00501 template<class T,class C,class M>
00502 inline
00503 Setv<T,C,M>::~Setv()
00504 { clear(); }
00505 
00506 template<class T,class C,class M>
00507 inline
00508 std::pair<typename Setv<T,C,M>::iterator,bool>
00509 Setv<T,C,M>::insert( typename Setv<T,C,M>::value_type * v )
00510 {
00511   bool flag = false ;
00512 
00513   if ( v != NULL ) {
00514     const typename Setv<T,C,M>::key_type & k = v->key();
00515 
00516     phdmesh::SetvMember<void> * y = nEnd();
00517     phdmesh::SetvMember<void> * x = nRoot();
00518 
00519     flag = true ;
00520 
00521     while ( x ) {
00522       y = x ;
00523       x = ( flag = key_less( k , static_cast<MemberType*>(x)->key() ) )
00524         ? x->left : x->right ;
00525     }
00526 
00527     /* flag = k < y , check previous value if exists */
00528 
00529     const bool k_lt_y = flag ;
00530 
00531     x = flag && y != nBegin() ? ( flag = false , setv_iterate<false>(y) ) : y ;
00532 
00533     if ( flag || ( flag = key_less(static_cast<MemberType*>(x)->key(),k) ) ) {
00534       x = v ;
00535       Setv<void,void,void>::insert( y , x , k_lt_y );
00536     }
00537     else {
00538       v = static_cast<typename Setv<T,C,M>::value_type*>( x );
00539     }
00540   }
00541   return std::pair<typename Setv<T,C,M>::iterator,bool>( iterator(v), flag );
00542 }
00543 
00544 template<class T,class C,class M>
00545 inline
00546 std::pair<typename Setv<T,C,M>::iterator,bool>
00547 Setv<T,C,M>::insert( const typename Setv<T,C,M>::key_type   & k ,
00548                            typename Setv<T,C,M>::value_type * v )
00549 {
00550   phdmesh::SetvMember<void> * y = nEnd();
00551   phdmesh::SetvMember<void> * x = nRoot();
00552 
00553   bool flag = true ;
00554 
00555   while ( x ) {
00556     y = x ;
00557     x = ( flag = key_less( k , static_cast<MemberType*>(x)->key() ) )
00558       ? x->left : x->right ;
00559   }
00560 
00561   /* flag = k < y , check previous value if exists */
00562 
00563   const bool k_lt_y = flag ;
00564 
00565   x = flag && y != nBegin() ? ( flag = false , setv_iterate<false>(y) ) : y ;
00566 
00567   if ( flag || ( flag = key_less(static_cast<MemberType*>(x)->key(),k) ) ) {
00568     if ( v == NULL ) {
00569       v = alloc.allocate(1);
00570       new(v) value_type();
00571     }
00572     v->SetvMember<key_type>::m_key = k ;
00573     x = v ;
00574     Setv<void,void,void>::insert( y , x , k_lt_y );
00575   }
00576   else {
00577     v = static_cast<typename Setv<T,C,M>::value_type*>( x );
00578   }
00579   return std::pair<typename Setv<T,C,M>::iterator,bool>( iterator(v), flag );
00580 }
00581 
00582 template<class T,class C,class M>
00583 inline
00584 typename Setv<T,C,M>::value_type &
00585 Setv<T,C,M>::operator[]( const key_type & k )
00586 {
00587   std::pair<typename Setv<T,C,M>::iterator,bool> result = insert(k);
00588   return *result.second ;
00589 }
00590 
00591 template<class T,class C,class M>
00592 inline
00593 void Setv<T,C,M>::erase( typename Setv<T,C,M>::value_type * p )
00594 {
00595   Setv<void,void,void>::remove( p );
00596   alloc.destroy(    p );
00597   alloc.deallocate( p , 1 );
00598 }
00599 
00600 template<class T,class C,class M>
00601 inline
00602 void Setv<T,C,M>::erase( typename Setv<T,C,M>::iterator p )
00603 {
00604   if ( p.operator bool() ) { erase( p.n ); }
00605 }
00606 
00607 template<class T,class C,class M>
00608 inline
00609 typename Setv<T,C,M>::size_type
00610 Setv<T,C,M>::erase( const typename Setv<T,C,M>::key_type & k )
00611 {
00612   iterator i = find(k);
00613   return i != end() ? ( erase( i ) , 1 ) : 0 ;
00614 }
00615 
00616 template<class T,class C,class M>
00617 void Setv<T,C,M>::clear()
00618 {
00619   if ( Setv<void,void,void>::size() ) {
00620     phdmesh::SetvMember<void> * n = nBegin();
00621     phdmesh::SetvMember<void> * t ;
00622     while ( ( t = Setv<void,void,void>::unbalancing_removal( &n ) ) ) {
00623       alloc.destroy(    static_cast<value_type*>(t) );
00624       alloc.deallocate( static_cast<value_type*>(t) , 1 );
00625     }
00626   }
00627   Setv<void,void,void>::initialize();
00628 }
00629 
00630 template<class T,class C,class M>
00631 inline
00632 typename Setv<T,C,M>::iterator  
00633 Setv<T,C,M>::lower_bound( const typename Setv<T,C,M>::key_type & k ) const  
00634 {
00635   phdmesh::SetvMember<void> * y = nEnd();
00636   phdmesh::SetvMember<void> * x = nRoot();
00637   while ( x ) x = key_less(static_cast<MemberType*>(x)->key(),k)
00638                 ? x->right : ( y = x )->left ;
00639   return iterator( static_cast<value_type*>(y) );
00640 }
00641 
00642 template<class T,class C,class M>
00643 inline
00644 typename Setv<T,C,M>::iterator  
00645 Setv<T,C,M>::upper_bound( const typename Setv<T,C,M>::key_type & k ) const  
00646 {
00647   phdmesh::SetvMember<void> * y = nEnd();
00648   phdmesh::SetvMember<void> * x = nRoot();
00649   while ( x ) x = key_less(k,static_cast<MemberType*>(x)->key())
00650                 ? ( y = x )->left : x->right ;
00651   return iterator( static_cast<value_type*>(y) );
00652 }
00653 
00654 template<class T,class C,class M>
00655 inline
00656 typename Setv<T,C,M>::iterator  
00657 Setv<T,C,M>::find( const typename Setv<T,C,M>::key_type & k ) const  
00658 {
00659   typename Setv<T,C,M>::iterator i = lower_bound(k); // k <= i->key();
00660 
00661   // If 'end()' or k < y->key() then not found
00662   if ( i != end() && key_less(k,(*i).MemberType::key()) ) i = end();
00663 
00664   return i ;
00665 }
00666 
00667 template<class T,class C,class M>
00668 inline
00669 typename Setv<T,C,M>::size_type
00670 Setv<T,C,M>::count( const typename Setv<T,C,M>::key_type & k ) const  
00671 {
00672   typename Setv<T,C,M>::iterator i = lower_bound(k); // k <= i->key();
00673   return i == end() || key_less(k,(*i).SetvMember<T>::key()) ? 0 : 1 ;
00674 }
00675 
00676 template<class T,class C,class M>
00677 inline
00678 Setv<T,C,M>::Setv( const Setv<T,C,M> & V )
00679   : Setv<void,void,void>()
00680 {
00681   for ( const_iterator i = V.begin() ; i != V.end() ; ++i ) {
00682     pointer a = alloc.allocate(1);
00683     alloc.construct(a,*i);
00684     insert( i->SetvMember<key_type>::key() , a );
00685   }
00686 }
00687 
00688 template<class T,class C,class M>
00689 inline
00690 Setv<T,C,M> &
00691 Setv<T,C,M>::operator = ( const Setv<T,C,M> & V )
00692 {
00693   clear();
00694   for ( const_iterator i = V.begin() ; i != V.end() ; ++i ) {
00695     pointer a = alloc.allocate(1);
00696     alloc.construct(a,*i);
00697     insert( i->SetvMember<key_type>::key() , a );
00698   }
00699 }
00700 
00702 template<class T,class C,class M>
00703 inline
00704 Setv<T,C,M> *
00705 Setv<T,C,M>::container( const typename Setv<T,C,M>::value_type & v )
00706 {
00707   Setv<void,void,void> * const c = Setv<void,void,void>::container(&v);
00708   return c ? static_cast<Setv<T,C,M>*>( c ) :
00709              reinterpret_cast<Setv<T,C,M>*>( NULL );
00710 }
00711 
00712 template<class T,class C,class M>
00713 inline
00714 bool Setv<T,C,M>::verify_ordering() const
00715 {
00716   size_type count = 0 ;
00717   iterator  i = begin();
00718   iterator  j ;
00719 
00720   while ( i != end() &&
00721          ( ++(j=i) == end() || key_less( i->MemberType::key() ,
00722                                          j->MemberType::key() ) )
00723          && --j == i )
00724     { ++i ; ++count ; }
00725 
00726   return ( i == end() && count == size() );
00727 }
00728 
00729 // ---------------------------------------------------------------------
00730 
00731 } // namespace phdmesh
00732 
00733 #endif /* DOXYGEN_COMPILE */
00734 
00735 #endif /* util_Setv_hpp */

Generated on Tue Jul 13 09:22:43 2010 for phdMesh by  doxygen 1.4.7