VectorMap.h

Go to the documentation of this file.

// $Id: VectorMap.h,v 1.11 2007/05/24 14:39:11 hmd Exp $
// ============================================================================
// CVS tag $Name:  $, version $Revision: 1.11 $
// ============================================================================
#ifndef GAUDIKERNEL_VECTORMAP_H
#define GAUDIKERNEL_VECTORMAP_H 1
// ============================================================================
// Include files
// ============================================================================
// STD & STL
// ============================================================================
#include <utility>
#include <functional>
#include <vector>
#include <algorithm>
#include <ostream>
// ============================================================================
// GaudiKernel
// ============================================================================
#include "GaudiKernel/MapBase.h"
// ============================================================================
namespace GaudiUtils
{
  // ==========================================================================
  template
  <
    class KEY                                                 ,
    class VALUE                                               ,
    class KEYCOMPARE=std::less<const KEY>                     ,
    class ALLOCATOR=std::allocator<std::pair<KEY,VALUE> >
    >
  class VectorMap : public Gaudi::Utils::MapBase
  {
  public:
    // ========================================================================
    typedef KEY                                    key_type         ;
    typedef VALUE                                  mapped_type      ;
    typedef KEYCOMPARE                             key_compare      ;
    typedef std::pair<key_type,mapped_type>        value_type       ;
    // ========================================================================
  public:
    // ========================================================================
    typedef ALLOCATOR                              allocator_type   ;
    typedef typename ALLOCATOR::const_reference    reference        ;
    typedef typename ALLOCATOR::const_reference    const_reference  ;
    typedef typename ALLOCATOR::size_type          size_type        ;
    typedef typename ALLOCATOR::difference_type    difference_type  ;
    // ========================================================================
  public:
    // ========================================================================
    typedef std::vector<value_type,allocator_type> _vector          ;
    // ========================================================================
  protected:
    // ========================================================================
    typedef typename _vector::iterator             _iterator        ;
    // ========================================================================
  public:
    // ========================================================================
    typedef typename _vector::const_iterator       iterator         ;
    typedef typename _vector::const_iterator       const_iterator   ;
    typedef std::reverse_iterator<iterator>        reverse_iterator ;
    typedef std::reverse_iterator<const_iterator>  const_reverse_iterator ;
    typedef std::pair<iterator,iterator>           iterators        ;
    typedef std::pair<iterator,bool>               result_type      ;
    // ========================================================================
  public:
    // ========================================================================
    struct _compare_type : public key_compare
    {
    public:
      // ======================================================================
      _compare_type ( const key_compare& cmp ) : key_compare ( cmp ) {} ;
      _compare_type ()                         : key_compare (     ) {} ;
      bool operator () ( const key_type&  k1 , const key_type&   k2 ) const
      { return this->key_compare::operator() ( k1 , k2 ) ; }
      bool operator() ( const value_type& v1 , const value_type& v2 ) const
      { return operator() ( v1.first, v2.first ); }
      bool operator() ( const key_type&   k  , const value_type& v  ) const
      { return operator() ( k , v.first ) ; }
      bool operator() ( const value_type& v  , const key_type  & k  ) const
      { return operator() ( v.first , k ) ; }
      // ======================================================================
    };
    // ========================================================================
    typedef _compare_type                            compare_type   ;
    // ========================================================================
  public:
    // ========================================================================
    // sequential access  (only const-versions!)
    // ========================================================================
    iterator         begin  () const { return m_vct . begin  () ; }
    iterator         end    () const { return m_vct . end    () ; }
    reverse_iterator rbegin () const { return m_vct . rbegin () ; }
    reverse_iterator rend   () const { return m_vct . rend   () ; }
    // ========================================================================
    // list operations : erase & insert
    // ========================================================================
    void erase  ( iterator pos ) { m_vct.erase ( iter ( pos ) ) ; }
    // ========================================================================
    size_type erase  ( const key_type&    key    )
    {
      iterator pos = find ( key ) ;
      if ( end() == pos ) { return 0 ; }
      erase ( pos ) ;
      return 1 ;
    }
    // ========================================================================
    size_type erase  ( iterator           first   ,
                       iterator           last    )
    {
      m_vct.erase ( iter ( first ) , iter ( last )  ) ;
      return last - first ;
    }
    // ========================================================================
    template <class TYPE>
    size_type erase  ( TYPE first , TYPE last )
    {
      size_type res = 0 ;
      for ( ; first != last ; ++first ) { res += erase ( *first ) ; }
      return res ;
    }
    // ========================================================================
    result_type insert
    ( const key_type&    key    ,
      const mapped_type& mapped  )
    { return insert ( value_type ( key , mapped ) ) ; }
    // ========================================================================
    result_type insert
    ( const value_type&  value  )
    {
      bool found = true ;
      _iterator result = lower_bound ( value.first ) ;
      if ( end() == result || compare( value.first , result -> first ) )
      { result = m_vct.insert ( result , value ) ; found = false ; }
      return result_type ( iter ( result ) , !found ) ;
    }
    // ========================================================================
    result_type insert
    ( iterator           pos    ,
      const value_type&  value  )
    {
      if ( pos != end() && compare ( *pos , value ) &&
           ( pos == end() - 1 ||
              ( !compare ( value , *( pos + 1 ) )
                && compare ( *( pos + 1 ) , value ) ) ) )
      { return result_type( m_vct.insert ( iter ( pos ) , value ) , true ) ; }
      return insert ( value ) ;
    }
    // ========================================================================
    result_type insert
    ( iterator           pos    ,
      const key_type&    key    ,
      const mapped_type& mapped )
    { return insert ( pos , value_type ( key , mapped ) ) ; }
    // ========================================================================
    template <class PAIRS>
    void insert
    ( PAIRS first ,
      PAIRS last  )
    { for ( ; first != last ; ++first ) { insert ( *first ) ; } }
    // ========================================================================
    template <class KEYS, class VALUES> void insert
    ( KEYS   kf ,
      KEYS   kl ,
      VALUES vf )
    { for ( ; kf != kl ; ++kf, ++vf ) { insert ( *kf , *vf ) ; } }
    // ========================================================================
    // map operations: lookup, count, ...
    // ========================================================================
    iterator find ( const key_type& key ) const
    {
      iterator res = lower_bound ( key ) ;
      if ( end() != res && compare ( key , res->first ) )
      { res = end(); }
      return res ;
    }
    // ========================================================================
    size_type count ( const key_type& key ) const
    { return end() == find ( key ) ? 0 : 1 ; }
    // ========================================================================
    iterator  lower_bound ( const key_type& key ) const
    { return std::lower_bound ( begin () , end () , key , compare () ) ; }
    iterator  upper_bound ( const key_type& key ) const
    { return std::upper_bound ( begin () , end () , key , compare () ) ; }
    iterators equal_range ( const key_type& key ) const
    { return std::equal_range ( begin () , end () , key , compare () ) ; }
    // ========================================================================
    // general container operations :
    // ========================================================================
    bool      empty    () const { return m_vct . empty    () ; }
    size_type size     () const { return m_vct . size     () ; }
    size_type max_size () const { return m_vct . max_size () ; }
    void clear    ()                { m_vct.clear   ()       ; }
    void reserve  ( size_type num ) { m_vct.reserve ( num )  ; }
    // ========================================================================
    void swap     ( VectorMap& other )
    {
      std::swap ( m_vct , other.m_vct ) ;
    }
    // ========================================================================
    // The basic comparison operators for container
    // ========================================================================
    bool operator== ( const VectorMap& other ) const
    { return m_vct == other.m_vct ; }
    bool operator<  ( const VectorMap& other ) const
    { return m_vct <  other.m_vct ; }
    // ========================================================================
    // The derived comparison operators for container
    // ========================================================================
    friend bool operator>  ( const VectorMap& left  ,
                             const VectorMap& right )
    { return    right < left     ; }
    friend bool operator!= ( const VectorMap& left  ,
                             const VectorMap& right )
    { return !( left == right  ) ; }
    friend bool operator>= ( const VectorMap& left  ,
                             const VectorMap& right )
    { return !( left  <  right ) ; }
    friend bool operator<= ( const VectorMap& left  ,
                             const VectorMap& right )
    { return !( right <  left  ) ; }
    // ========================================================================    
    bool update
    ( const key_type&    key    ,
      const mapped_type& mapped )
    {
      _iterator result = lower_bound ( key ) ;
      if ( end() == result || compare ( key , result -> first ) )
      { 
        result = m_vct.insert ( result , value_type(key,mapped) ) ; 
        return false ;
      }
      else { result->second = mapped ; }
      //
      return true ;
    }
    // ========================================================================
    bool update ( const value_type& val )
    { return update ( val.first , val.second ) ; }
    // ========================================================================
    const mapped_type& operator() ( const key_type& key ) const
    {
      static const mapped_type s_default = mapped_type() ;
      iterator res = find ( key ) ;
      if ( end() == res ) { return s_default ; }
      return res->second ;
    }
    // ========================================================================
    const mapped_type& operator[] ( const key_type& key ) const
    { return (*this)( key ) ; }
    // ========================================================================
    const mapped_type& at ( const key_type& key ) const
    {
      iterator res = find ( key ) ;
      if ( end() == res ) { this->throw_out_of_range_exception () ; }
      return res->second ;
    }
    // ========================================================================
  public:
    // ========================================================================
    // Constructors, destructors, etc.
    // ========================================================================
    VectorMap ( const allocator_type& alloc = allocator_type () )
      : m_vct ( alloc )
    {}
    // ========================================================================
    VectorMap ( const VectorMap& right )
      : Gaudi::Utils::MapBase(right), m_vct ( right.m_vct )
    {}
    // ========================================================================
    template <class INPUT>
    VectorMap ( INPUT first ,
                INPUT last  ,
                const allocator_type& alloc = allocator_type () )
      : m_vct ( first , last , alloc )
    { std::sort ( m_vct.begin(), m_vct.end(), compare() ) ; }
    // ========================================================================
    ~VectorMap() { clear() ; }                     // destructor (non-virtual!)
    // ========================================================================
    /* assignement operator
     * @param rigth object to be assigned
     * @return self
     */
    VectorMap& operator= ( const VectorMap& right )
    {
      if ( &right == this ) { return *this ; }
      m_vct = right.m_vct ;
      return *this ;
    }
    // ========================================================================
  public:
    // ========================================================================
    // The specific public accessors
    // ========================================================================
    const compare_type& compare     () const
    {
      static const  compare_type s_cmp = compare_type() ;
      return s_cmp ;
    }
    const key_compare&  compare_key () const { return compare()  ; }
    friend std::ostream& operator<<
      ( std::ostream& str , const VectorMap& /* obj */) { return str ; }
    // ========================================================================
  public:
    // ========================================================================
    inline VectorMap& merge ( const VectorMap& right ) 
    {
      for ( const_iterator it = right.begin() ; right.end() != it ; ++it ) 
      { update ( it->first , it->second ) ; }
      //
      return *this ;
    }
    template <class K1,class K2, class K3,class K4>
    inline VectorMap& merge ( const VectorMap<K1,K2,K3,K4>& right ) 
    {
      for ( typename VectorMap<K1,K2,K3,K4>::const_iterator it = 
              right.begin() ; right.end() != it ; ++it ) 
      { update ( it->first , it->second ) ; }
      //
      return *this ;
    }
    // ========================================================================
  public:
    // ========================================================================
    const key_type&    key_at   ( const size_t index ) const 
    {
      if ( index  >= size() ) 
      { this->throw_out_of_range_exception () ; }
      const_iterator it = this->begin() ;
      std::advance ( it , index ) ;
      return it -> first ;
    }
    const mapped_type& value_at ( const size_t index ) const 
    {
      if ( index  >= size() ) 
      { this->throw_out_of_range_exception () ; }
      const_iterator it = this->begin() ;
      std::advance ( it , index ) ;
      return it -> second ;
    }
    // ========================================================================
  protected:
    // ========================================================================
    // Pure technical helper functions
    // ========================================================================
    template <class TYPE1, class TYPE2>
    bool  compare ( const TYPE1& obj1 ,
                    const TYPE2& obj2 ) const
    {
      return compare() ( obj1 , obj2 )  ;
    }
    // ========================================================================
    _iterator lower_bound ( const key_type& key )
    {
      return std::lower_bound
      ( m_vct.begin() , m_vct.end() , key , compare() ) ;
    } 
    // ========================================================================
    _iterator iter (  iterator p )
    {
      _iterator result = m_vct.begin() ;
      std::advance ( result , std::distance ( begin() , p ) ) ;
      return result ;
    }
    // ========================================================================
    iterator  iter ( _iterator p )
    {
      iterator result ( begin() ) ;
      std::advance ( result , std::distance (  m_vct.begin() , p ) ) ;
      return result ;
    }
    // ========================================================================
  private:
    // ========================================================================
    _vector      m_vct ; // the underlying sorted vector of (key,mapped) pairs
    // ========================================================================
  };
  // ==========================================================================
} //                                               end of namespace GaudiUtils 
// ============================================================================
namespace std
{
  // ==========================================================================
  template
  < class KEY        ,
    class VALUE      ,
    class KEYCOMPARE ,
    class ALLOCATOR  >
  inline void swap
  ( GaudiUtils::VectorMap<KEY,VALUE,KEYCOMPARE,ALLOCATOR>& left  ,
    GaudiUtils::VectorMap<KEY,VALUE,KEYCOMPARE,ALLOCATOR>& right )
  { left.swap( right ) ; }
 // ===========================================================================
} //                                                       end of namespace std 
// ============================================================================

// ============================================================================
// The END
// ============================================================================
#endif // GAUDIKERNEL_MAPS_H
// ============================================================================