| # Gaudi Framework, version v20r3
Generated: 24 Nov 2008

# VectorMap.h

Go to the documentation of this file.

    00001 // $Id: VectorMap.h,v 1.11 2007/05/24 14:39:11 hmd Exp $
    00002 // ============================================================================
    00003 // CVS tag $Name: v26r0 $, version $Revision: 1.11 $
    00004 // ============================================================================
    00005 #ifndef GAUDIKERNEL_VECTORMAP_H
    00006 #define GAUDIKERNEL_VECTORMAP_H 1
    00007 // ============================================================================
    00008 // Include files
    00009 // ============================================================================
    00010 // STD & STL
    00011 // ============================================================================
    00012 #include <utility>
    00013 #include <functional>
    00014 #include <vector>
    00015 #include <algorithm>
    00016 #include <ostream>
    00017 // ============================================================================
    00018
    00019 namespace GaudiUtils
    00020 {
    00021
    00023   void _throw_out_of_range_exception_() ;
    00024
    00048   template
    00049   <
    00050     class KEY                                                 ,
    00051     class VALUE                                               ,
    00052     class KEYCOMPARE=std::less<const KEY>                     ,
    00053     class ALLOCATOR=std::allocator<std::pair<KEY,VALUE> >
    00054   >
    00055   class VectorMap
    00056   {
    00057   public:
    00059     typedef KEY                                    key_type         ;
    00061     typedef VALUE                                  mapped_type      ;
    00063     typedef KEYCOMPARE                             key_compare      ;
    00065     typedef std::pair<key_type,mapped_type>        value_type       ;
    00066   public:
    00068     typedef ALLOCATOR                              allocator_type   ;
    00070     typedef typename ALLOCATOR::const_reference    reference        ;
    00072     typedef typename ALLOCATOR::const_reference    const_reference  ;
    00074     typedef typename ALLOCATOR::size_type          size_type        ;
    00076     typedef typename ALLOCATOR::difference_type    difference_type  ;
    00077   public:
    00079     typedef std::vector<value_type,allocator_type> _vector          ;
    00080   protected:
    00082     typedef typename _vector::iterator             _iterator        ;
    00083   public:
    00085     typedef typename _vector::const_iterator       iterator         ;
    00087     typedef typename _vector::const_iterator       const_iterator   ;
    00089     typedef std::reverse_iterator<iterator>        reverse_iterator ;
    00091     typedef std::reverse_iterator<const_iterator>  const_reverse_iterator ;
    00093     typedef std::pair<iterator,iterator>           iterators        ;
    00095     typedef std::pair<iterator,bool>               result_type      ;
    00096   public:
    00101     struct _compare_type : public key_compare
    00102     {
    00103     public:
    00105       _compare_type ( const key_compare& cmp ) : key_compare ( cmp ) {} ;
    00107       _compare_type ()                         : key_compare (     ) {} ;
    00109       bool operator () ( const key_type&  k1 , const key_type&   k2 ) const
    00110       { return this->key_compare::operator() ( k1 , k2 ) ; }
    00112       bool operator() ( const value_type& v1 , const value_type& v2 ) const
    00113       { return operator() ( v1.first, v2.first ); }
    00115       bool operator() ( const key_type&   k  , const value_type& v  ) const
    00116       { return operator() ( k , v.first ) ; }
    00118       bool operator() ( const value_type& v  , const key_type  & k  ) const
    00119       { return operator() ( v.first , k ) ; }
    00120     };
    00122     typedef _compare_type                            compare_type   ;
    00123   public:
    00124
    00125     //
    00126     // sequential access  (only const-versions!)
    00127     //
    00128
    00130     iterator         begin  () const { return m_vct . begin  () ; }
    00132     iterator         end    () const { return m_vct . end    () ; }
    00134     reverse_iterator rbegin () const { return m_vct . rbegin () ; }
    00136     reverse_iterator rend   () const { return m_vct . rend   () ; }
    00137
    00138     // ========================================================================
    00139     // list operations : erase & insert
    00140     // ========================================================================
    00141
    00145     void erase  ( iterator pos ) { m_vct.erase ( iter ( pos ) ) ; }
    00146
    00163     size_type erase  ( const key_type&    key    )
    00164     {
    00165       iterator pos = find ( key ) ;
    00166       if ( end() == pos ) { return 0 ; }
    00167       erase ( pos ) ;
    00168       return 1 ;
    00169     } ;
    00170
    00176     size_type erase  ( iterator           first   ,
    00177                        iterator           last    )
    00178     {
    00179       m_vct.erase ( iter ( first ) , iter ( last )  ) ;
    00180       return last - first ;
    00181     } ;
    00182
    00203     template <class TYPE>
    00204     size_type erase  ( TYPE first , TYPE last )
    00205     {
    00206       size_type res = 0 ;
    00207       for ( ; first != last ; ++first ) { res += erase ( *first ) ; }
    00208       return res ;
    00209     }
    00210
    00252     result_type insert
    00253     ( const key_type&    key    ,
    00254       const mapped_type& mapped  )
    00255     { return insert ( value_type ( key , mapped ) ) ; }
    00256
    00297     result_type insert
    00298     ( const value_type&  value  )
    00299     {
    00300       bool found = true ;
    00301       _iterator result = lower_bound ( value.first ) ;
    00302       if ( end() == result || compare( value.first , result -> first ) )
    00303       { result = m_vct.insert ( result , value ) ; found = false ; }
    00304       return result_type ( iter ( result ) , !found ) ;
    00305     } ;
    00306
    00315     result_type insert
    00316     ( iterator           pos    ,
    00317       const value_type&  value  )
    00318     {
    00319       if ( pos != end() && compare ( *pos , value ) &&
    00320            ( pos == end() - 1 || !compare ( value , *( pos + 1 ) )
    00321              && compare ( *( pos + 1 ) , value ) ) )
    00322       { return result_type( m_vct.insert ( iter ( pos ) , value ) , true ) ; }
    00323       return insert ( value ) ;
    00324     } ;
    00325
    00335     result_type insert
    00336     ( iterator           pos    ,
    00337       const key_type&    key    ,
    00338       const mapped_type& mapped )
    00339     { return insert ( pos , value_type ( key , mapped ) ) ; }
    00340
    00346     template <class PAIRS>
    00347     void insert
    00348     ( PAIRS first ,
    00349       PAIRS last  )
    00350     { for ( ; first != last ; ++first ) { insert ( *first ) ; } }
    00358     template <class KEYS, class VALUES> void insert
    00359     ( KEYS   kf ,
    00360       KEYS   kl ,
    00361       VALUES vf )
    00362     { for ( ; kf != kl ; ++kf, ++vf ) { insert ( *kf , *vf ) ; } }
    00363
    00364     //
    00365     // map operations: lookup, count, ...
    00366     //
    00367
    00391     iterator find ( const key_type& key ) const
    00392     {
    00393       iterator res = lower_bound ( key ) ;
    00394       if ( end() != res && compare ( key , res->first ) )
    00395       { res = end(); }
    00396       return res ;
    00397     } ;
    00398
    00414     size_type count ( const key_type& key ) const
    00415     { return end() == find ( key ) ? 0 : 1 ; }
    00416
    00417     iterator  lower_bound ( const key_type& key ) const
    00418     { return std::lower_bound ( begin () , end () , key , compare () ) ; }
    00419     iterator  upper_bound ( const key_type& key ) const
    00420     { return std::upper_bound ( begin () , end () , key , compare () ) ; }
    00421     iterators equal_range ( const key_type& key ) const
    00422     { return std::equal_range ( begin () , end () , key , compare () ) ; }
    00423
    00424     //
    00425     // general container operations :
    00426     //
    00427
    00429     bool      empty    () const { return m_vct . empty    () ; }
    00431     size_type size     () const { return m_vct . size     () ; }
    00433     size_type max_size () const { return m_vct . max_size () ; }
    00434
    00436     void clear    ()                { m_vct.clear   ()       ; }
    00438     void reserve  ( size_type num ) { m_vct.reserve ( num )  ; }
    00439
    00441     void swap     ( VectorMap& other )
    00442     {
    00443       std::swap ( m_vct , other.m_vct ) ;
    00444     } ;
    00445
    00446     //
    00447     // The basic comparison operators for container
    00448     //
    00449
    00451     bool operator== ( const VectorMap& other ) const
    00452     { return m_vct == other.m_vct ; } ;
    00453
    00455     bool operator<  ( const VectorMap& other ) const
    00456     { return m_vct <  other.m_vct ; } ;
    00457
    00458     //
    00459     // The derived comparison operators for container
    00460     //
    00461
    00462     friend bool operator>  ( const VectorMap& left  ,
    00463                              const VectorMap& right )
    00464     { return    right < left     ; }
    00465
    00466     friend bool operator!= ( const VectorMap& left  ,
    00467                              const VectorMap& right )
    00468     { return !( left == right  ) ; }
    00469
    00470     friend bool operator>= ( const VectorMap& left  ,
    00471                              const VectorMap& right )
    00472     { return !( left  <  right ) ; }
    00473
    00474     friend bool operator<= ( const VectorMap& left  ,
    00475                              const VectorMap& right )
    00476     { return !( right <  left  ) ; }
    00477
    00478
    00508     iterator update
    00509     ( const key_type&    key    ,
    00510       const mapped_type& mapped )
    00511     {
    00512       _iterator result = lower_bound ( key ) ;
    00513       if ( end() == result || compare ( key , result -> first ) )
    00514       { result = m_vct.insert ( result , value_type(key,mapped) ) ; }
    00515       else
    00516       { result->second = mapped ; }
    00517       return iter ( result ) ;
    00518     } ;
    00519
    00548     iterator update ( const value_type& val )
    00549     { return update ( val.first , val.second ) ; }
    00550
    00582     const mapped_type& operator() ( const key_type& key ) const
    00583     {
    00584       static const mapped_type s_default = mapped_type() ;
    00585       iterator res = find ( key ) ;
    00586       if ( end() == res ) { return s_default ; }
    00587       return res->second ;
    00588     } ;
    00619     const mapped_type& operator[] ( const key_type& key ) const
    00620     { return (*this)( key ) ; } ;
    00621
    00639     const mapped_type& at ( const key_type& key ) const
    00640     {
    00641       iterator res = find ( key ) ;
    00642       if ( end() == res )
    00643       { GaudiUtils::_throw_out_of_range_exception_() ; }
    00644       return res->second ;
    00645     } ;
    00646
    00647   public:
    00648
    00649     //
    00650     // Constructors, destructors, etc.
    00651     //
    00652
    00657     VectorMap ( const allocator_type& alloc = allocator_type () )
    00658       : m_vct ( alloc )
    00659     {} ;
    00660
    00664     VectorMap ( const VectorMap& right )
    00665       : m_vct ( right.m_vct )
    00666     {}
    00667
    00674     template <class INPUT>
    00675     VectorMap ( INPUT first ,
    00676                 INPUT last  ,
    00677                 const allocator_type& alloc = allocator_type () )
    00678       : m_vct ( first , last , alloc )
    00679     { std::sort ( m_vct.begin(), m_vct.end(), compare() ) ; }
    00680
    00682     ~VectorMap() { clear() ; }
    00683
    00684     /* assignement operator
    00685      * @param rigth object to be assigned
    00686      * @return self
    00687      */
    00688     VectorMap& operator= ( const VectorMap& right )
    00689     {
    00690       if ( &right == this ) { return *this ; }
    00691       m_vct = right.m_vct ;
    00692       return *this ;
    00693     }
    00694
    00695   public:
    00696
    00697     //
    00698     // The specific public accessors
    00699     //
    00700
    00702     const compare_type& compare     () const
    00703     {
    00704       static const  compare_type s_cmp = compare_type() ;
    00705       return s_cmp ;
    00706     }
    00708     const key_compare&  compare_key () const { return compare()  ; }
    00709
    00711     friend std::ostream& operator<<
    00712       ( std::ostream& str , const VectorMap& /* obj */) { return str ; }
    00713
    00714   protected:
    00715
    00716     //
    00717     // Pure technical helper functions
    00718     //
    00719
    00725     template <class TYPE1, class TYPE2>
    00726     bool  compare ( const TYPE1& obj1 ,
    00727                     const TYPE2& obj2 ) const
    00728     {
    00729       return compare() ( obj1 , obj2 )  ;
    00730     }
    00731
    00733     _iterator lower_bound ( const key_type& key )
    00734     {
    00735       return std::lower_bound
    00736       ( m_vct.begin() , m_vct.end() , key , compare() ) ;
    00737     } ;
    00739     _iterator iter (  iterator p )
    00740     {
    00741       _iterator result = m_vct.begin() ;
    00742       std::advance ( result , std::distance ( begin() , p ) ) ;
    00743       return result ;
    00744     };
    00746     iterator  iter ( _iterator p )
    00747     {
    00748       iterator result ( begin() ) ;
    00749       std::advance ( result , std::distance (  m_vct.begin() , p ) ) ;
    00750       return result ;
    00751     }
    00752
    00753   private:
    00754     // the underlying sorted vector of (key,mapped) pairs
    00755     _vector      m_vct ;
    00756   };
    00757 }
    00758
    00759 namespace std
    00760 {
    00765   template
    00766   < class KEY        ,
    00767     class VALUE      ,
    00768     class KEYCOMPARE ,
    00769     class ALLOCATOR  >
    00770   inline void swap
    00771   ( GaudiUtils::VectorMap<KEY,VALUE,KEYCOMPARE,ALLOCATOR>& left  ,
    00772     GaudiUtils::VectorMap<KEY,VALUE,KEYCOMPARE,ALLOCATOR>& right )
    00773   { left.swap( right ) ; }
    00774 }
    00775
    00776 // ============================================================================
    00777 // The END
    00778 // ============================================================================
    00779 #endif // GAUDIKERNEL_MAPS_H
    00780 // ============================================================================