VectorMap.h

Go to the documentation of this file.

#ifndef Utilities_VectorMap_H
#define Utilities_VectorMap_H

#include <cstddef>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
#include <stdexcept> // std::out_of_range

namespace util {

  // Start with the same template terms as used for a map (copied from
  // GNU C++'s stl_map.h).  In general, if you see variables that begin
  // with underscores ("_"), it means I copied the code directly from
  // GNU C++, either from stl_map.h or stl_vector.h.
  template < typename _Key, typename _Tp, typename _Compare = std::less<_Key> > 
  class VectorMap {
  public:
    // Define lots of handy types.

    typedef _Key                                       key_type;
    typedef _Tp                                        mapped_type;
    typedef std::pair<_Key, _Tp>                       value_type;
    typedef _Compare                                   key_compare;
    typedef std::allocator< std::pair<_Key, _Tp> >     allocator_type;

    typedef std::vector<value_type>                    vector_type;

    typedef typename vector_type::pointer              pointer;
    typedef typename vector_type::const_pointer        const_pointer;
    typedef typename vector_type::reference            reference;
    typedef typename vector_type::const_reference      const_reference;
    typedef typename vector_type::iterator             iterator;
    typedef typename vector_type::const_iterator       const_iterator;
    typedef std::reverse_iterator<const_iterator>      const_reverse_iterator;
    typedef std::reverse_iterator<iterator>            reverse_iterator;
    typedef size_t                                     size_type;
    typedef ptrdiff_t                                  difference_type;

  public:

    // The "value_compare" class is an internal utility class for
    // VectorMap.  It extends the "_Compare" template entry (the
    // name of a class that compares the keys) to a binary operator that
    // compares two entries in the "sortedVectorMap" private member.

    // Note that because of the context-based multiple definitions of
    // operator(), this class cannot inherit from the STL
    // binary_function template.  This means that it's not "adaptable";
    // e.g., you can't use it as an argument to bind2nd.

    // If you're getting confused by all this, just think of it as a
    // fancy way of defining "less than" and ignore it.
    class value_compare
    {
      friend class VectorMap<_Key, _Tp, _Compare>;
    protected:

      value_compare(_Compare __c = _Compare())
        : comp(__c) { }
      _Compare GetCompare() const {  return comp; }
      _Compare comp;
    
    public:

      // From an idea suggested by item 23 in "Effective STL" by Scott
      // Meyers:
      bool operator()(const value_type& __x, 
                      const value_type& __y) const
      { return keyLess(__x.first, __y.first); }
      bool operator()(const value_type& __x, 
                      const key_type& __y) const
      { return keyLess(__x.first, __y); }
      bool operator()(const key_type& __x, 
                      const value_type& __y) const
      { return keyLess(__x, __y.first); }
    private:
      bool keyLess(const key_type& __x, 
                   const key_type& __y) const
      { return comp(__x, __y); }
    };

  private:
    // The vector that contains the sorted pair<Key,Value> entries.
    vector_type sortedVectorMap; // The sorted <key,data> pairs.

    // The actual key-comparison object.
    value_compare valueCompare; 
  
  public:
    // After copying a lot of stuff from GNU C++, here's where I start
    // implementing some methods on my own.  I'm trying to be complete,
    // and implementing all the methods that STL map supports, even if I
    // don't think I'll ever use them.

    allocator_type get_allocator() const
    {
      return sortedVectorMap.get_allocator();
    }
 
    iterator begin()
    {
      return sortedVectorMap.begin();
    }

    const_iterator begin() const
    {
      return sortedVectorMap.begin();
    }

    iterator end()
    {
      return sortedVectorMap.end();
    }

    const_iterator end() const
    {
      return sortedVectorMap.end();
    }

    reverse_iterator rbegin()
    {
      return sortedVectorMap.rbegin();
    }

    const_reverse_iterator rbegin() const
    {
      return sortedVectorMap.rbegin();
    }

    reverse_iterator rend()
    {
      return sortedVectorMap.rend();
    }

    const_reverse_iterator rend() const
    {
      return sortedVectorMap.rend();
    }

    bool empty() const
    {
      return sortedVectorMap.empty();
    }

    size_t size() const
    {
      return sortedVectorMap.size();
    }

    size_t max_size() const
    {
      return sortedVectorMap.max_size();
    }

    mapped_type& operator[](const key_type& key)
    {
      // Do a binary search for the key.
      iterator i = lower_bound(key);

      // If the key is not found, or i->first is less than key, then
      // the key is not found.
      if (i == end() || key_comp()(key, (*i).first))
        // Insert this key into the map, with a default value.  Thanks
        // to the lower_bound call above, i already points to correct
        // place to insert the value in the sorted vector.
        i = sortedVectorMap.insert(i, value_type(key, mapped_type() ));

      return (*i).second;
    }

    // Not part of STL, even in a GNU extension, but something I always
    // wanted: operator[] in a const context.  Derived from the at()
    // method below.
    const mapped_type& operator[](const key_type& __k) const
    {
      const_iterator __i = lower_bound(__k);
      if (__i == end() || key_comp()(__k, (*__i).first))
        throw std::out_of_range("Utilities/VectorMap::operator[]");
      return (*__i).second;
    }

    // at(), equivalent to operator[] except that it can throw an
    // exception.
    mapped_type& at(const key_type& __k)
    {
      iterator __i = lower_bound(__k);
      if (__i == end() || key_comp()(__k, (*__i).first))
        throw std::out_of_range("Utilities/VectorMap::at");
      return (*__i).second;
    }

    const mapped_type& at(const key_type& __k) const
    {
      const_iterator __i = lower_bound(__k);
      if (__i == end() || key_comp()(__k, (*__i).first))
        throw std::out_of_range("Utilities/VectorMap::at");
      return (*__i).second;
    }

    // One of the key members of this adapted class.  Attempt to insert
    // the entry (a pair<key,value>) into the map.  Since this is a
    // unique insert, the map will only be changed if the key is not
    // already present.  In the returned pair, the iterator points to
    // the map entry that contains the key; the bool indicates whether
    // the insertion succeeded or failed.  Note the combination of a
    // binary search (lower_bound) with an insert-in-the-middle
    // ("sortedVectorMap.insert()"); that what's makes this method so
    // slow.
    std::pair<iterator,bool> insert(const value_type& entry)
    {
      const key_type& key = entry.first;
      iterator i = lower_bound(key);
      if (i == end() || key_comp()(key, (*i).first))
        {
          // The entry was not found.  In that case, lower_bound has
          // already found the correct point at which we want to insert
          // the entry to maintain the sort.
          i = sortedVectorMap.insert(i, entry);
          return std::make_pair( i, true);
        }

      // If we get here, the entry was found.  Return failure.
      return std::make_pair( i, false );
    }

    // In this form of insert(), the iterator in the argument is
    // supposed to give us a hint about where to insert the item.
    // Actually, this hint is useless (since lower_bound doesn't take a
    // hint <heh, heh>).  So just do a regular insert instead.
    iterator insert(iterator, const value_type& entry)
    { 
      std::pair<iterator,bool> result = insert(entry);
      return result.first;
    }

    // Mass insertion.
    template <typename _InputIterator>
    void insert(_InputIterator __first, _InputIterator __last)
    { 
      for ( ; __first != __last; ++__first)
        insert(*__first);
    }

    void erase(iterator __position)
    { 
      sortedVectorMap.erase(__position);
    }

    // Erases all the entries with the key, and returns the number of
    // erasures.
    size_type erase(const key_type& key)
    { 
      iterator i = find(key);
      if ( i == end() ) return 0;
      erase(i);
      return 1;
    }

    // Erase a range.
    void erase(iterator __first, iterator __last)
    { 
      sortedVectorMap.erase(__first, __last); 
    }

    // Swap two maps. For VectorMap, this is pretty simple: use
    // the standard vector mechanism for swapping the vector portion of
    // the maps, then swap the value_compare objects (if any) by the
    // usual "temp" method.
    void swap(VectorMap& other)
    { 
      sortedVectorMap.swap(other.sortedVectorMap);
      value_compare temp(valueCompare);
      valueCompare = other.valueCompare;
      other.valueCompare = temp;
    }

    void clear()
    { 
      sortedVectorMap.clear(); 
    }

    // Returns the key-comparison object used for this VectorMap.
    key_compare key_comp() const
    { 
      return valueCompare.GetCompare(); 
    }

    // Returns the value-comparison object, which just compares the
    // entry.first of the two pairs.
    value_compare value_comp() const
    { 
      return valueCompare; 
    }

    iterator find(const key_type& key)
    { 
      iterator i = lower_bound(key); 
      if (i == end() || key_comp()(key, (*i).first))
        return end();

      return i;
    }

    const_iterator find(const key_type& key) const
    { 
      const_iterator i = lower_bound(key); 
      if (i == end() || key_comp()(key, (*i).first))
        return end();

      return i;
    }

    // Count the number of entries with a given key (which will be 0 or
    // 1 for a map).
    size_type count(const key_type& __x) const
    { 
      return find(__x) == end() ? 0 : 1; 
    }

    iterator lower_bound(const key_type& __x)
    { 
      return std::lower_bound(begin(),end(),__x,valueCompare); 
    }

    const_iterator lower_bound(const key_type& __x) const
    { 
      return std::lower_bound(begin(),end(),__x,valueCompare); 
    }

    iterator upper_bound(const key_type& __x)
    { 
      return std::upper_bound(begin(),end(),__x,valueCompare); 
    }

    const_iterator upper_bound(const key_type& __x) const
    { 
      return std::upper_bound(begin(),end(),__x,valueCompare); 
    }

    std::pair<iterator, iterator> equal_range(const key_type& key)
    { 
      return std::equal_range(begin(),end(),key,valueCompare); 
    }

    // The following code does not compile when processed by ROOT's
    // dictionary.  For now, this is not a big deal; no one is likely to
    // use equal_range on a map anyway.  If we ever have to implement a
    // multimap or multiset using the same scheme, this could be a
    // problem.
    /*
      std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
      { 
      return std::equal_range(begin(),end(),key,valueCompare); 
      }
    */

    // My own little extras, as described near the top of this header
    // file's comments:

    const mapped_type& operator()(const size_type& index) const
    {
      return sortedVectorMap[index].second;
    }

    const mapped_type& Data(const size_type& index) const
    {
      return sortedVectorMap[index].second;
    }

    const key_type& Key(const size_type& index) const
    {
      return sortedVectorMap[index].first;
    }


    // Vector-based memory management.
    void reserve( size_type i )
    {
      sortedVectorMap.reserve(i);
    }
    size_type capacity()
    {
      return sortedVectorMap.capacity();
    }

  
    // Friend definitions for comparison operators.
    template <typename _K1, typename _T1, typename _C1>
    friend bool operator== (const VectorMap<_K1, _T1, _C1>&,
                            const VectorMap<_K1, _T1, _C1>&);

    template <typename _K1, typename _T1, typename _C1>
    friend bool operator< (const VectorMap<_K1, _T1, _C1>&,
                           const VectorMap<_K1, _T1, _C1>&);

  public:

  };

} // namespace util

namespace util {

  // Comparison operators.
  template <typename _Key, typename _Tp, typename _Compare>
  inline bool operator==(const VectorMap<_Key, _Tp, _Compare>& __x,
                         const VectorMap<_Key, _Tp, _Compare>& __y)
  { 
    return __x.sortedVectorMap == __y.sortedVectorMap; 
  }

  template <typename _Key, typename _Tp, typename _Compare>
  inline bool operator<(const VectorMap<_Key, _Tp, _Compare>& __x,
                        const VectorMap<_Key, _Tp, _Compare>& __y)
  { 
    return std::lexicographical_compare(__x.sortedVectorMap.begin(),
                                        __x.sortedVectorMap.end(),
                                        __y.sortedVectorMap.begin(),
                                        __y.sortedVectorMap.end(),
                                        __x.valueCompare);
  }

  template <typename _Key, typename _Tp, typename _Compare>
  inline bool operator!=(const VectorMap<_Key, _Tp, _Compare>& __x,
                         const VectorMap<_Key, _Tp, _Compare>& __y)
  { 
    return !(__x == __y); 
  }

  template <typename _Key, typename _Tp, typename _Compare>
  inline bool operator>(const VectorMap<_Key, _Tp, _Compare>& __x,
                        const VectorMap<_Key, _Tp, _Compare>& __y)
  { 
    return __y < __x; 
  }

  template <typename _Key, typename _Tp, typename _Compare>
  inline bool operator<=(const VectorMap<_Key, _Tp, _Compare>& __x,
                         const VectorMap<_Key, _Tp, _Compare>& __y)
  { 
    return !(__y < __x); 
  }

  template <typename _Key, typename _Tp, typename _Compare>
  inline bool operator>=(const VectorMap<_Key, _Tp, _Compare>& __x,
                         const VectorMap<_Key, _Tp, _Compare>& __y)
  { 
    return !(__x < __y); 
  }

  template <typename _Key, typename _Tp, typename _Compare>
  inline void swap(VectorMap<_Key, _Tp, _Compare>& __x,
                   VectorMap<_Key, _Tp, _Compare>& __y)
  { 
    __x.swap(__y); 
  }

} // namespace util

#endif // Utilities_VectorMap_H