VectorMap.h

Go to the documentation of this file.

/***********************************************************************************\
* (c) Copyright 1998-2026 CERN for the benefit of the LHCb and ATLAS collaborations *
*                                                                                   *
* This software is distributed under the terms of the Apache version 2 licence,     *
* copied verbatim in the file "LICENSE".                                            *
*                                                                                   *
* In applying this licence, CERN does not waive the privileges and immunities       *
* granted to it by virtue of its status as an Intergovernmental Organization        *
* or submit itself to any jurisdiction.                                             *
\***********************************************************************************/
#pragma once
 
#include <GaudiKernel/MapBase.h>
#include <GaudiKernel/StatusCode.h>
#include <GaudiKernel/StringKey.h>
#include <algorithm>
#include <concepts>
#include <functional>
#include <initializer_list>
#include <ostream>
#include <type_traits>
#include <utility>
#include <vector>
 
namespace GaudiUtils {
 
  namespace detail {
    // Comp must order K with Key in both directions, and be transparent
    template <typename K, typename Key, typename Comp>
    concept key_comparable =
        (std::same_as<std::remove_cvref_t<K>, std::remove_cvref_t<Key>> && std::strict_weak_order<Comp, Key, Key>) ||
        ( requires { typename Comp::is_transparent; } && std::strict_weak_order<Comp, K, Key> &&
          std::strict_weak_order<Comp, Key, K> );
  } // namespace detail
 
  template <typename KEY, typename VALUE, typename KEYCOMPARE = std::less<>,
            typename 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::value_type const& reference;
    typedef typename ALLOCATOR::value_type const& 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:
      using key_compare::key_compare;
      using key_compare::operator();
      bool operator()( const value_type& v1, const value_type& v2 ) const { return operator()( v1.first, v2.first ); }
      template <detail::key_comparable<key_type, key_compare> K>
      bool operator()( const K& k, const value_type& v ) const {
        return operator()( k, v.first );
      }

      template <detail::key_comparable<key_type, key_compare> K>
      bool operator()( const value_type& v, const K& 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 ) { return erase<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    size_type erase( const K& 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, key_type key, mapped_type mapped ) {
      return insert( pos, value_type( std::move( key ), std::move( 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 { return find<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    iterator find( const K& 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 count<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    size_type count( const K& key ) const {
      return end() == find( key ) ? 0 : 1;
    }
    iterator lower_bound( const key_type& key ) const { return lower_bound<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    iterator lower_bound( const K& key ) const {
      return std::lower_bound( begin(), end(), key, compare() );
    }
    iterator upper_bound( const key_type& key ) const { return upper_bound<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    iterator upper_bound( const K& key ) const {
      return std::upper_bound( begin(), end(), key, compare() );
    }
    iterators equal_range( const key_type& key ) const { return equal_range<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    iterators equal_range( const K& 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; }
    auto operator<=>( const VectorMap& other ) const { return m_vct <=> other.m_vct; }
    bool update( const key_type& key, const mapped_type& mapped ) { return update<key_type>( key, mapped ); }
    template <detail::key_comparable<key_type, key_compare> K>
    bool update( const K& 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 { return this->template operator()<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    const mapped_type& operator()( const K& 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 ); }
    template <detail::key_comparable<key_type, key_compare> K>
    const mapped_type& operator[]( const K& key ) const {
      return ( *this )( key );
    }

    const mapped_type& at( const key_type& key ) const { return at<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    const mapped_type& at( const K& key ) const {
      iterator res = find( key );
      if ( end() == res ) this->throw_out_of_range_exception();
      return res->second; // cppcheck-suppress derefInvalidIteratorRedundantCheck; the above throws
    }
 
  public:
    // Constructors, destructors, etc.
    VectorMap( const allocator_type& alloc = allocator_type() ) : m_vct( alloc ) {}
    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( std::initializer_list<value_type> first, const allocator_type& alloc = allocator_type() )
        : m_vct( first, alloc ) {
      std::sort( m_vct.begin(), m_vct.end(), compare() );
    }
 
  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 auto& i : right ) { update( i.first, i.second ); }
      return *this;
    }

    template <class K1, class K2, class K3, class K4>
    inline VectorMap& merge( const VectorMap<K1, K2, K3, K4>& right ) {
      for ( const auto& i : right ) { update( i.first, i.second ); }
      return *this;
    }
 
  public:
    const key_type& key_at( const size_t index ) const {
      if ( index >= size() ) { this->throw_out_of_range_exception(); }
      auto 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(); }
      auto 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 lower_bound<key_type>( key ); }
    template <detail::key_comparable<key_type, key_compare> K>
    _iterator lower_bound( const K& key ) {
      return std::lower_bound( m_vct.begin(), m_vct.end(), key, compare() );
    }

    _iterator iter( iterator p ) {
      auto result = m_vct.begin();
      std::advance( result, std::distance( begin(), p ) );
      return result;
    }

    iterator iter( _iterator p ) {
      auto 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
  };
} // 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 );
  }
} // namespace std
namespace Gaudi {
  namespace Parsers {
    GAUDI_API StatusCode parse( GaudiUtils::VectorMap<std::string, double>& result, std::string_view input );
    GAUDI_API StatusCode parse( GaudiUtils::VectorMap<Gaudi::StringKey, double>& result, std::string_view input );
  } // namespace Parsers
} // namespace Gaudi