| # Gaudi Framework, version v20r4
Generated: 8 Jan 2009

# 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:  $, 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 ||
    00321               ( !compare ( value , *( pos + 1 ) )
    00322                 && compare ( *( pos + 1 ) , value ) ) ) )
    00323       { return result_type( m_vct.insert ( iter ( pos ) , value ) , true ) ; }
    00324       return insert ( value ) ;
    00325     }
    00326
    00336     result_type insert
    00337     ( iterator           pos    ,
    00338       const key_type&    key    ,
    00339       const mapped_type& mapped )
    00340     { return insert ( pos , value_type ( key , mapped ) ) ; }
    00341
    00347     template <class PAIRS>
    00348     void insert
    00349     ( PAIRS first ,
    00350       PAIRS last  )
    00351     { for ( ; first != last ; ++first ) { insert ( *first ) ; } }
    00359     template <class KEYS, class VALUES> void insert
    00360     ( KEYS   kf ,
    00361       KEYS   kl ,
    00362       VALUES vf )
    00363     { for ( ; kf != kl ; ++kf, ++vf ) { insert ( *kf , *vf ) ; } }
    00364
    00365     //
    00366     // map operations: lookup, count, ...
    00367     //
    00368
    00392     iterator find ( const key_type& key ) const
    00393     {
    00394       iterator res = lower_bound ( key ) ;
    00395       if ( end() != res && compare ( key , res->first ) )
    00396       { res = end(); }
    00397       return res ;
    00398     }
    00399
    00415     size_type count ( const key_type& key ) const
    00416     { return end() == find ( key ) ? 0 : 1 ; }
    00417
    00418     iterator  lower_bound ( const key_type& key ) const
    00419     { return std::lower_bound ( begin () , end () , key , compare () ) ; }
    00420     iterator  upper_bound ( const key_type& key ) const
    00421     { return std::upper_bound ( begin () , end () , key , compare () ) ; }
    00422     iterators equal_range ( const key_type& key ) const
    00423     { return std::equal_range ( begin () , end () , key , compare () ) ; }
    00424
    00425     //
    00426     // general container operations :
    00427     //
    00428
    00430     bool      empty    () const { return m_vct . empty    () ; }
    00432     size_type size     () const { return m_vct . size     () ; }
    00434     size_type max_size () const { return m_vct . max_size () ; }
    00435
    00437     void clear    ()                { m_vct.clear   ()       ; }
    00439     void reserve  ( size_type num ) { m_vct.reserve ( num )  ; }
    00440
    00442     void swap     ( VectorMap& other )
    00443     {
    00444       std::swap ( m_vct , other.m_vct ) ;
    00445     }
    00446
    00447     //
    00448     // The basic comparison operators for container
    00449     //
    00450
    00452     bool operator== ( const VectorMap& other ) const
    00453     { return m_vct == other.m_vct ; }
    00454
    00456     bool operator<  ( const VectorMap& other ) const
    00457     { return m_vct <  other.m_vct ; }
    00458
    00459     //
    00460     // The derived comparison operators for container
    00461     //
    00462
    00463     friend bool operator>  ( const VectorMap& left  ,
    00464                              const VectorMap& right )
    00465     { return    right < left     ; }
    00466
    00467     friend bool operator!= ( const VectorMap& left  ,
    00468                              const VectorMap& right )
    00469     { return !( left == right  ) ; }
    00470
    00471     friend bool operator>= ( const VectorMap& left  ,
    00472                              const VectorMap& right )
    00473     { return !( left  <  right ) ; }
    00474
    00475     friend bool operator<= ( const VectorMap& left  ,
    00476                              const VectorMap& right )
    00477     { return !( right <  left  ) ; }
    00478
    00479
    00509     iterator update
    00510     ( const key_type&    key    ,
    00511       const mapped_type& mapped )
    00512     {
    00513       _iterator result = lower_bound ( key ) ;
    00514       if ( end() == result || compare ( key , result -> first ) )
    00515       { result = m_vct.insert ( result , value_type(key,mapped) ) ; }
    00516       else
    00517       { result->second = mapped ; }
    00518       return iter ( result ) ;
    00519     }
    00520
    00549     iterator update ( const value_type& val )
    00550     { return update ( val.first , val.second ) ; }
    00551
    00583     const mapped_type& operator() ( const key_type& key ) const
    00584     {
    00585       static const mapped_type s_default = mapped_type() ;
    00586       iterator res = find ( key ) ;
    00587       if ( end() == res ) { return s_default ; }
    00588       return res->second ;
    00589     }
    00620     const mapped_type& operator[] ( const key_type& key ) const
    00621     { return (*this)( key ) ; }
    00622
    00640     const mapped_type& at ( const key_type& key ) const
    00641     {
    00642       iterator res = find ( key ) ;
    00643       if ( end() == res )
    00644       { GaudiUtils::_throw_out_of_range_exception_() ; }
    00645       return res->second ;
    00646     }
    00647
    00648   public:
    00649
    00650     //
    00651     // Constructors, destructors, etc.
    00652     //
    00653
    00658     VectorMap ( const allocator_type& alloc = allocator_type () )
    00659       : m_vct ( alloc )
    00660     {}
    00661
    00665     VectorMap ( const VectorMap& right )
    00666       : m_vct ( right.m_vct )
    00667     {}
    00668
    00675     template <class INPUT>
    00676     VectorMap ( INPUT first ,
    00677                 INPUT last  ,
    00678                 const allocator_type& alloc = allocator_type () )
    00679       : m_vct ( first , last , alloc )
    00680     { std::sort ( m_vct.begin(), m_vct.end(), compare() ) ; }
    00681
    00683     ~VectorMap() { clear() ; }
    00684
    00685     /* assignement operator
    00686      * @param rigth object to be assigned
    00687      * @return self
    00688      */
    00689     VectorMap& operator= ( const VectorMap& right )
    00690     {
    00691       if ( &right == this ) { return *this ; }
    00692       m_vct = right.m_vct ;
    00693       return *this ;
    00694     }
    00695
    00696   public:
    00697
    00698     //
    00699     // The specific public accessors
    00700     //
    00701
    00703     const compare_type& compare     () const
    00704     {
    00705       static const  compare_type s_cmp = compare_type() ;
    00706       return s_cmp ;
    00707     }
    00709     const key_compare&  compare_key () const { return compare()  ; }
    00710
    00712     friend std::ostream& operator<<
    00713       ( std::ostream& str , const VectorMap& /* obj */) { return str ; }
    00714
    00715   protected:
    00716
    00717     //
    00718     // Pure technical helper functions
    00719     //
    00720
    00726     template <class TYPE1, class TYPE2>
    00727     bool  compare ( const TYPE1& obj1 ,
    00728                     const TYPE2& obj2 ) const
    00729     {
    00730       return compare() ( obj1 , obj2 )  ;
    00731     }
    00732
    00734     _iterator lower_bound ( const key_type& key )
    00735     {
    00736       return std::lower_bound
    00737       ( m_vct.begin() , m_vct.end() , key , compare() ) ;
    00738     } ;
    00740     _iterator iter (  iterator p )
    00741     {
    00742       _iterator result = m_vct.begin() ;
    00743       std::advance ( result , std::distance ( begin() , p ) ) ;
    00744       return result ;
    00745     };
    00747     iterator  iter ( _iterator p )
    00748     {
    00749       iterator result ( begin() ) ;
    00750       std::advance ( result , std::distance (  m_vct.begin() , p ) ) ;
    00751       return result ;
    00752     }
    00753
    00754   private:
    00755     // the underlying sorted vector of (key,mapped) pairs
    00756     _vector      m_vct ;
    00757   };
    00758 }
    00759
    00760 namespace std
    00761 {
    00766   template
    00767   < class KEY        ,
    00768     class VALUE      ,
    00769     class KEYCOMPARE ,
    00770     class ALLOCATOR  >
    00771   inline void swap
    00772   ( GaudiUtils::VectorMap<KEY,VALUE,KEYCOMPARE,ALLOCATOR>& left  ,
    00773     GaudiUtils::VectorMap<KEY,VALUE,KEYCOMPARE,ALLOCATOR>& right )
    00774   { left.swap( right ) ; }
    00775 }
    00776
    00777 // ============================================================================
    00778 // The END
    00779 // ============================================================================
    00780 #endif // GAUDIKERNEL_MAPS_H
    00781 // ============================================================================