JHashMap.hh

Go to the documentation of this file.

#ifndef __JTOOLS__JHASHMAP__
#define __JTOOLS__JHASHMAP__

#include <vector>
#include <utility>
#include <algorithm>

#include "JLang/JNullType.hh"
#include "JLang/JTypeList.hh"
#include "JLang/JSinglePointer.hh"
#include "JLang/JEquals.hh"
#include "JLang/JForwardIterator.hh"
#include "JLang/JException.hh"
#include "JTools/JMappableCollection.hh"
#include "JTools/JHashEvaluator.hh"
#include "JTools/JRouter.hh"
#include "JTools/JTuple.hh"
#include "JTools/JPair.hh"
#include "JIO/JSerialisable.hh"
#include "JIO/JSTDIO.hh"


/**
 * \file
 *
 * General purpose classes for (multidimensional) hash maps.
 * \author mdejong
 */
namespace JTOOLS {}
namespace JPP { using namespace JTOOLS; }

namespace JTOOLS {

  using JLANG::JNullType;
  using JLANG::JTypeList;
  using JLANG::JTYPELIST;
  using JLANG::JClass;
  using JLANG::JIndexOutOfRange;
  using JIO::JReader;
  using JIO::JWriter;
  

  /**
   * General purpose class for hash map of (key, value) pairs.
   *
   * The elements in a hash map are sorted according to the specified evaluation.
   * The evaluation of elements corresponds to a unary method returning an integer value for a given key;
   * The default evaluator is JHashEvaluator. 
   *
   * This class implements the JMappableCollection interface.
   */
  template<class JKey_t, class JValue_t, class JEvaluator_t = JHashEvaluator>
  struct JHashMap :
    public std::vector< std::pair<JKey_t, JValue_t> >,
    public JMappableCollection<JKey_t, JValue_t>
  {
  public:

    typedef JKey_t                                               key_type;
    typedef JValue_t                                             mapped_type;
    typedef std::pair<JKey_t, JValue_t>                          value_type;
    typedef JEvaluator_t                                         evaluator_type;
    
    typedef std::vector<value_type>                              container_type;

    typedef typename container_type::const_iterator              const_iterator;
    typedef typename container_type::const_reverse_iterator      const_reverse_iterator;
    typedef typename container_type::iterator                    iterator;
    typedef typename container_type::reverse_iterator            reverse_iterator;

    typedef std::pair<const_iterator, bool>                      pair_type;

    using JMappableCollection<key_type, mapped_type>::operator[];

    
    /**
     * Auxiliary class for ordering of objects in the collection by the hash value of their keys.
     */
    struct JComparator {

      /**
       * Constructor.
       *
       * \param  evaluator       evaluator
       */
      JComparator(const JEvaluator_t& evaluator = JEvaluator_t()) :
        getValue(evaluator)
      {}

      
      /**
       * Comparison of elements.
       *
       * \param  first           first  element
       * \param  second          second element
       * \return                 true if first element less than second element; else false
       */
      inline bool operator()(typename JClass<value_type>::argument_type first,
                             typename JClass<value_type>::argument_type second) const
      {
        return this->getValue(first.first) < this->getValue(second.first);
      }
      
      
      /**
       * Comparison of element and key value.
       *
       * \param  element         element
       * \param  x               key value
       * \return                 true if element less than key value; else false
       */
      inline bool operator()(typename JClass<value_type>::argument_type element,
                             typename JClass<key_type>::argument_type x) const
      {
        return this->getValue(element.first) < this->getValue(x);
      }


      /**
       * Function object for evaluation of key.
       */
      JEvaluator_t getValue;
    };


    /**
     * Constructor.
     *
     * \param  evaluator       evaluator
     */
    JHashMap(const JEvaluator_t& evaluator = JEvaluator_t()) :
      getValue(evaluator),
      compare (evaluator),
      router  (-1)             // default address
    {}


    /**
     * Clear.
     */
    virtual void clear() 
    {
      // reset internal router
      
      for (iterator i = this->begin(); i != this->end(); ++i) {
        router.put(this->getValue(i->first), router.getDefaultAddress());
      }
      
      container_type::clear();
    }


    /**
     * Get mapped value.
     *
     * \param  key             key
     * \return                 mapped value
     */
    virtual mapped_type& get(typename JClass<key_type>::argument_type key) 
    {
      const int ival = this->getValue(key);
      
      if (!router.has(ival)) {
        insert(value_type(key, mapped_type()));
      }

      return container_type::operator[](router.get(ival)).second;
    }


    /**
     * Get mapped value.
     *
     * This method will throw an exception if given key is not present following the prerequisite of constness.
     *
     * \param  key             key
     * \return                 mapped value
     */
    const mapped_type& get(typename JClass<key_type>::argument_type key) const
    {
      const int ival = this->getValue(key);

      if (router.has(ival))
        return container_type::operator[](router.get(ival)).second;
      else
        THROW(JIndexOutOfRange, "JHasMap::get(): invalid key.");
    }


    /**
     * Insert element.
     *
     * \param  element         element
     * \return                 (position, status), where status is true if inserted; else false
     */
    pair_type insert(const value_type& element)
    {
      using namespace std;

      const int ival = this->getValue(element.first);

      if (!router.has(ival)) {
        
        iterator i = container_type::insert(lower_bound(this->begin(), this->end(), element.first, compare), element);
        
        router.put(ival, distance(this->begin(), i));
        
        for (iterator __i = i; ++__i != this->end(); ) {
          router.put(this->getValue(__i->first), distance(this->begin(), __i));
        }
        
        return pair_type(i, true);
        
      } else {

        return pair_type(this->end(), false);
      }
    }


    /**
     * Erase element at given position.
     *
     * \param  pos             valid position
     */
    void erase(iterator pos)
    {
      this->router.put(this->getValue(*pos), this->router.getDefaultAddress());

      iterator i = pos;

      container_type::erase(i++);

      for ( ; i != this->end(); ++i) {
        this->router.put(this->getValue(*i), distance(this->begin(), i));
      }
    }


    /**
     * Erase elements in given range.
     *
     * \param  __begin         begin position (included)
     * \param  __end           end   position (excluded)
     */
    void erase(iterator __begin, iterator __end)
    {
      iterator i = __begin;

      while (i != __end) {

        this->router.put(this->getValue(*i), this->router.getDefaultAddress());

        container_type::erase(i++);
      }

      for ( ; i != this->end(); ++i) {
        this->router.put(this->getValue(*i), distance(this->begin(), i));
      }
    }
    
    
    /**
     * Erase element.
     *
     * \param  key             key
     * \return                 true if element with given key has been erased; else false
     */
    bool erase(typename JClass<key_type>::argument_type key) const
    {
      const int ival = this->getValue(key);

      if (router.has(ival)) {

        iterator pos = this->begin();

        std::advance(pos, this->router.get(ival));

        iterator i = container_type::erase(pos);

        for ( ; i != this->end(); ++i) {
          this->router.put(this->getValue(*i), distance(this->begin(), i));
        }

        return true;
      }

      return false;
    }
    

    /**
     * Test whether key is present.
     *
     * \param  key             key
     * \return                 true if present; else false
     */
    bool has(typename JClass<key_type>::argument_type key) const
    {
      return router.has(this->getValue(key));
    }


    /**
     * Get comparator.
     *
     * \return                 comparator
     */
    const JComparator& getComparator() const
    {
      return compare;
    }

    
    /**
     * Read hash map from input.
     *
     * \param  in              reader
     * \param  object          hash map
     * \return                 reader
     */
    friend inline JReader& operator>>(JReader& in, JHashMap& object)
    {
      using namespace JIO;
      
      int n;

      in >> n;

      object.resize(n);

      for (value_type element; n != 0 && in >> element; --n) {
        object.insert(element);
      }

      return in;
    }


    /**
     * Write hash map to output.
     *
     * \param  out             writer
     * \param  object          hash map
     * \return                 writer
     */
    friend inline JWriter& operator<<(JWriter& out, const JHashMap& object)
    {
      using namespace JIO;

      int n = object.size();

      out << n;

      for (typename JHashMap::const_iterator i = object.begin(); i != object.end(); ++i) {
        out << *i;
      }

      return out;
    }


    /**
     * Function object for evaluation of key.
     */
    JEvaluator_t getValue;


  protected:
    /**
     * Function object for comparison.
     */
    JComparator  compare;

    JRouter<int> router;
    
  private:
    void resize();
    void push_back();
    void pop_back();
  };
  

  /**
   * Multi-dimensional hash map.
   */
  template<class JHead_t, class JTail_t, class JValue_t, class JEvaluator_t>
  struct JHashMap<JTypeList<JHead_t, JTail_t>, JValue_t, JEvaluator_t> :
    public JHashMap<JHead_t, JHashMap<JTail_t, JValue_t, JEvaluator_t>, JEvaluator_t>
  {

    typedef JHead_t                                                    key_type;
    typedef JHashMap<JTail_t, JValue_t, JEvaluator_t>                  mapped_type;
    typedef std::pair<key_type, mapped_type>                           value_type;
    typedef JEvaluator_t                                               evaluator_type;
    typedef JTuple< JTypeList<JHead_t, JTail_t> >                      multikey_type;
    typedef JHashMap<key_type, mapped_type, evaluator_type>            map_type;
   
    typedef typename map_type::const_iterator                          const_iterator;
    typedef typename map_type::const_reverse_iterator                  const_reverse_iterator;
    typedef typename map_type::iterator                                iterator;
    typedef typename map_type::reverse_iterator                        reverse_iterator;

    using map_type::get;
    using map_type::put;
    using map_type::has;
    using map_type::erase;
    
    
    /**
     * Constructor.
     *
     * \param  evaluator       evaluator
     */
    JHashMap(const JEvaluator_t& evaluator = JEvaluator_t()) :
      JHashMap<JHead_t, JHashMap<JTail_t, JValue_t, JEvaluator_t>, JEvaluator_t>(evaluator)
    {}

    
    class super_const_iterator;  // forward declaration

    
    /**
     * Multidimensional iterator. 
     */
    class super_iterator :
      public JLANG::JEquals         <super_iterator>,
      public JLANG::JForwardIterator<super_iterator>
    {

      typedef JPair<const key_type&, typename mapped_type::super_iterator&>            value_type;
      typedef JLANG::JSinglePointer<value_type>                                        pointer_type;
      typedef JTuple< JTypeList<multikey_type, JValue_t&> >                            reference_type;

      friend class JHashMap;
      
    public:

      /**
       * Default constructor.
       */
      super_iterator()
      {}


      /**
       * Smart pointer operator.
       *
       * \return                 pointer to pair of iterators
       */
      pointer_type operator->()
      { 
        return pointer_type(new value_type(i->first, second));
      }


      /**
       * Dereference operator.
       *
       * \return                 multidimensional pair
       */
      reference_type operator*()
      { 
        return reference_type(i->first, *second);
      }


      /**
       * Equality of super iterator.
       *
       * \param  cursor          super iterator
       * \return                 true if equal; else false
       */
      virtual bool equals(const super_iterator& cursor) const
      {
        return i == cursor.i && (i == range.second || second.equals(cursor.second));
      }


      /**
       * Increment super_iterator.
       *
       * \return                 true if valid; else false
       */
      virtual bool increment()
      {
        if (!second.increment()) {

          while (++i != range.second) {

            second = i->second.super_begin();
            
            if (second != i->second.super_end()) {
              break;
            }
          }
        }

        return i != range.second;
      }

      
      /**
       * Get multi-dimensional key.
       *
       * \return                 key
       */
      multikey_type getKey() const
      {
        return multikey_type(i->first, second.getKey());
      }

      
      /**
       * Get value.
       *
       * \return                 value
       */
      JValue_t& getValue() 
      {
        return second.getValue();
      }


    private:
      /**
       * Constructor.
       *
       * \param  __begin         begin of data
       * \param  __end           end   of data
       */
      super_iterator(iterator __begin,
                     iterator __end) :
        range(__begin, __end)
      {
        for (i = range.first; i != range.second; ++i) {

          second = i->second.super_begin();

          if (second != i->second.super_end()) {
            break;
          }
        }
      }


      std::pair<iterator, iterator> range;
      iterator i;
      typename mapped_type::super_iterator second;
    };

    
    /**
     * Multidimensional const_iterator. 
     */
    class super_const_iterator :
      public JLANG::JEquals         <super_const_iterator>,
      public JLANG::JForwardIterator<super_const_iterator>
    {

      typedef JPair<const key_type&, typename mapped_type::super_const_iterator&>      value_type;
      typedef JLANG::JSinglePointer<value_type>                                        pointer_type;
      typedef JTuple< JTypeList<multikey_type, const JValue_t&> >                      reference_type;

      friend class JHashMap;
      
    public:

      /**
       * Default constructor.
       */
      super_const_iterator()
      {}


      /**
       * Copy constructor.
       *
       * \param  cursor          super_iterator
       */
      super_const_iterator(super_iterator cursor) :
        range (cursor.range),
        i     (cursor.i),
        second(cursor.second)
      {}


      /**
       * Smart pointer operator.
       *
       * \return                 pointer to pair of iterators
       */
      pointer_type operator->()
      { 
        return pointer_type(new value_type(i->first, second));
      }


      /**
       * Dereference operator.
       *
       * \return                 multidimensional pair
       */
      reference_type operator*()
      { 
        return reference_type(i->first, *second);
      }


      /**
       * Equality of super iterator.
       *
       * \param  cursor          super iterator
       * \return                 true if equal; else false
       */
      virtual bool equals(const super_const_iterator& cursor) const
      {
        return i == cursor.i && (i == range.second || second.equals(cursor.second));
      }


      /**
       * Increment super_iterator.
       *
       * \return                 true if valid; else false
       */
      virtual bool increment()
      {
        if (!second.increment()) {

          while (++i != range.second) {

            second = i->second.super_begin();
            
            if (second != i->second.super_end()) {
              break;
            }
          }
        }

        return i != range.second;
      }

      
      /**
       * Get multi-dimensional key.
       *
       * \return                 key
       */
      multikey_type getKey() const
      {
        return multikey_type(i->first, second.getKey());
      }

      
      /**
       * Get value.
       *
       * \return                 value
       */
      const JValue_t& getValue() 
      {
        return second.getValue();
      }


    private:
      /**
       * Constructor.
       *
       * \param  __begin         begin of data
       * \param  __end           end   of data
       */
      super_const_iterator(const_iterator __begin,
                           const_iterator __end) :
        range(__begin, __end)
      {
        for (i = range.first; i != range.second; ++i) {

          second = i->second.super_begin();

          if (second != i->second.super_end()) {
            break;
          }
        }
      }


      std::pair<const_iterator, const_iterator> range;
      const_iterator i;
      typename mapped_type::super_const_iterator second;
    };


    /**
     * Get super_iterator to begin of data.
     * 
     * \return                 super iterator
     */
    super_const_iterator super_begin() const
    {
      return super_const_iterator(this->begin(), this->end());
    }
 
   
    /**
     * Get super_iterator to end of data.
     *
     * \return                 super iterator
     */
    super_const_iterator super_end() const
    {
      return super_const_iterator(this->end(), this->end());
    }


    /**
     * Get super_iterator to begin of data.
     * 
     * \return                 super iterator
     */
    super_iterator super_begin()
    {
      return super_iterator(this->begin(), this->end());
    }
 
   
    /**
     * Get super_iterator to end of data.
     *
     * \return                 super iterator
     */
    super_iterator super_end()
    {
      return super_iterator(this->end(), this->end());
    }


    /**
     * Get mapped value.
     *
     * \param  key             key
     * \return                 value
     */
    JValue_t& get(const multikey_type& key)
    {
      this->get(key.first).get(key.second);
    }


    /**
     * Get mapped value.
     *
     * This method will throw an exception if given key is not present following the prerequisite of constness.
     *
     * \param  key             key
     * \return                 value
     */
    const JValue_t& get(const multikey_type& key) const
    {
      this->get(key.first).get(key.second);
    }


    /**
     * Put tuple-wise element (key,value) into collection. 
     *
     * \param  key             key
     * \param  value           value
     */
    void put(const multikey_type& key, const JValue_t& value)
    {
      this->get(key.first).put(key.second, value);
    }


    /**
     * Erase element.
     *
     * \param  key             key
     * \return                 true if element with given key has been erased; else false
     */
    bool erase(const multikey_type& key)
    {
      if (this->has(key.first))
        return this->get(key.first).erase(key.second);
      else
        return false;
    }


    /**
     * Test whether key is present.
     *
     * \param  key             key
     * \return                 true if present; else false
     */
    bool has(const multikey_type& key) const
    {
      return map_type::has(key.first) && this->get(key.first).has(key.second);
    }
  };


  /**
   * Terminator class of recursive class JHashMap.
   */
  template<class JHead_t, class JValue_t, class JEvaluator_t>
  struct JHashMap<JTypeList<JHead_t, JNullType>, JValue_t, JEvaluator_t> :
    public JHashMap<JHead_t, JValue_t, JEvaluator_t>
  {

    typedef JHead_t                                                    key_type;
    typedef JValue_t                                                   mapped_type;
    typedef std::pair<key_type, mapped_type>                           value_type;
    typedef JEvaluator_t                                               evaluator_type;
    typedef JHead_t                                                    multikey_type;
    typedef JHashMap<key_type, mapped_type, evaluator_type>            map_type;
    
    typedef typename map_type::const_iterator                          const_iterator;
    typedef typename map_type::const_reverse_iterator                  const_reverse_iterator;
    typedef typename map_type::iterator                                iterator;
    typedef typename map_type::reverse_iterator                        reverse_iterator;

    
    /**
     * Constructor.
     *
     * \param  evaluator       evaluator
     */
    JHashMap(const JEvaluator_t& evaluator = JEvaluator_t()) :
      JHashMap<JHead_t, JValue_t, JEvaluator_t>(evaluator)
    {}

    
    class super_const_iterator;  // forward declaration


    /**
     * Terminator class of multidimensional iterator. 
     */
    class super_iterator :
      public JLANG::JEquals         <super_iterator>,
      public JLANG::JForwardIterator<super_iterator>
    {

      typedef JPair<const key_type&, const mapped_type&>            value_type;
      typedef JLANG::JSinglePointer<value_type>                     pointer_type;
      typedef JTuple< JTypeList<multikey_type, const JValue_t&> >   reference_type;

      friend class JHashMap;

    public:

      /**
       * Default constructor.
       */
      super_iterator()
      {}


      /**
       * Smart pointer operator.
       *
       * \return                 pointer to pair of iterators
       */
      pointer_type operator->()
      {
        return pointer_type(new value_type(i->first, i->second));
      }


      /**
       * Dereference operator.
       *
       * \return                 multidimensional pair
       */
      reference_type operator*()
      { 
        return reference_type(i->first, i->second);
      }


      /**
       * Equality of super iterator.
       *
       * \param  cursor          super iterator
       * \return                 true if equal; else false
       */
      virtual bool equals(const super_iterator& cursor) const
      {
        return i == cursor.i;
      }


      /**
       * Increment super_iterator.
       *
       * \return                 true if valid; else false
       */
      virtual bool increment()
      {
        return ++i != range.second;
      }

      
      /**
       * Get multi-dimensional key.
       *
       * \return                 key
       */
      multikey_type getKey() const
      {
        return multikey_type(i->first);
      }

      
      /**
       * Get value.
       *
       * \return                 value
       */
      JValue_t& getValue() 
      {
        return i->second;
      }

    private:
      /**
       * Constructor.
       *
       * \param  __begin         begin of data
       * \param  __end           end   of data
       */
      super_iterator(iterator __begin,
                     iterator __end) :
        range(__begin, __end),
        i    (__begin)
      {}


      std::pair<iterator, iterator> range;
      iterator i;
    };

    
    /**
     * Terminator class of multidimensional const_iterator. 
     */
    class super_const_iterator :
      public JLANG::JEquals         <super_const_iterator>,
      public JLANG::JForwardIterator<super_const_iterator>
    {

      typedef JPair<const key_type&, const mapped_type&>            value_type;
      typedef JLANG::JSinglePointer<value_type>                     pointer_type;
      typedef JTuple< JTypeList<multikey_type, const JValue_t&> >   reference_type;

      friend class JHashMap;

    public:

      /**
       * Default constructor.
       */
      super_const_iterator()
      {}


      /**
       * Copy constructor.
       *
       * \param  cursor          super_iterator
       */
      super_const_iterator(super_iterator cursor) :
        range(cursor.range),
        i    (cursor.i)
      {}


      /**
       * Smart pointer operator.
       *
       * \return                 pointer to pair of iterators
       */
      pointer_type operator->()
      {
        return pointer_type(new value_type(i->first, i->second));
      }


      /**
       * Dereference operator.
       *
       * \return                 multidimensional pair
       */
      reference_type operator*()
      { 
        return reference_type(i->first, i->second);
      }


      /**
       * Equality of super iterator.
       *
       * \param  cursor          super iterator
       * \return                 true if equal; else false
       */
      virtual bool equals(const super_const_iterator& cursor) const
      {
        return i == cursor.i;
      }


      /**
       * Increment super_iterator.
       *
       * \return                 true if valid; else false
       */
      virtual bool increment()
      {
        return ++i != range.second;
      }

      
      /**
       * Get multi-dimensional key.
       *
       * \return                 key
       */
      multikey_type getKey() const
      {
        return multikey_type(i->first);
      }

      
      /**
       * Get value.
       *
       * \return                 value
       */
      const JValue_t& getValue() 
      {
        return i->second;
      }

    private:
      /**
       * Constructor.
       *
       * \param  __begin         begin of data
       * \param  __end           end   of data
       */
      super_const_iterator(const_iterator __begin,
                           const_iterator __end) :
        range(__begin, __end),
        i    (__begin)
      {}


      std::pair<const_iterator, const_iterator> range;
      const_iterator i;
    };

    
    /**
     * Get super_iterator to begin of data.
     *
     * \return             super_iterator
     */
    super_const_iterator super_begin() const
    {
      return super_const_iterator(this->begin(), this->end());
    }
 
   
    /**
     * Get super_iterator to end of data.
     *
     * \return             super_iterator
     */
    super_const_iterator super_end() const
    {
      return super_const_iterator(this->end(), this->end());
    }

    
    /**
     * Get super_iterator to begin of data.
     *
     * \return             super_iterator
     */
    super_iterator super_begin()
    {
      return super_iterator(this->begin(), this->end());
    }
 
   
    /**
     * Get super_iterator to end of data.
     *
     * \return             super_iterator
     */
    super_iterator super_end()
    {
      return super_iterator(this->end(), this->end());
    }    
  };
}

#endif