JHashCollection.hh

Go to the documentation of this file.

#ifndef __JTOOLS__JHASHCOLLECTION__
#define __JTOOLS__JHASHCOLLECTION__

#include <vector>
#include <utility>

#include "JLang/JClass.hh"
#include "JLang/JException.hh"
#include "JTools/JHashEvaluator.hh"
#include "JTools/JRouter.hh"
#include "JIO/JSerialisable.hh"


/**
 * \file
 *
 * General purpose class for a hash collection of unique elements.
 * \author mdejong
 */
namespace JTOOLS {}
namespace JPP { using namespace JTOOLS; }

namespace JTOOLS {

  using JLANG::JClass;
  using JLANG::JIndexOutOfRange;
  using JIO::JReader;
  using JIO::JWriter;
  

  /**
   * General purpose class for hash collection of unique elements.
   *
   * The elements in a hash collection are unique according to the specified evaluation.
   * The evaluation of elements corresponds to a unary method returning an integer value for a given element;
   * The default evaluator is JHashEvaluator. 
   *
   * For the binary I/O of a collection of elements, the data structure of the elements
   * should provide for an implementation of the following operators:
   * <pre>
   *       JReader& operator>>(JReader& in);
   *       JWriter& operator<<(JWriter& out);
   * </pre>
   */
  template<class JElement_t, class JEvaluator_t = JHashEvaluator>
  class JHashCollection :
    public std::vector<JElement_t>
  {
  public:

    typedef JElement_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;


    /**
     * Constructor.
     *
     * \param  evaluator       evaluator
     */
    JHashCollection(const JEvaluator_t& evaluator = JEvaluator_t()) :
      getValue(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), router.getDefaultAddress());
      }
      
      container_type::clear();
    }


    /**
     * Find element with given value.
     *
     * \param  value           value
     * \return                 position of element with given value or end()
     */
    template<class T>
    const_iterator find(const T& value) const
    {
      const int ival = this->getValue(value);
      
      if (router.has(ival)) {
        
        const_iterator i = this->begin();

        std::advance(i, router.get(ival));

        return i;
      }

      return this->end();
    }


    /**
     * Find element with given value.
     *
     * \param  value           value
     * \return                 position of element with given value or end()
     */
    template<class T>
    iterator find(const T& value)
    {
      const int ival = this->getValue(value);
      
      if (router.has(ival)) {
        
        iterator i = this->begin();

        std::advance(i, router.get(ival));

        return i;
      }

      return this->end();
    }

    
    /**
     * Get element with given value.
     *
     * This method will throw an exception if given value is not present following the prerequisite of constness.
     *
     * \param  value           value
     * \return                 element
     */
    template<class T>
    value_type& get(const T value)
    {
      const int ival = this->getValue(value);

      if (!this->router.has(ival)) {
        this->insert(value);
      }

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

    
    /**
     * Get element with given value.
     *
     * This method will throw an exception if given value is not present following the prerequisite of constness.
     *
     * \param  value           value
     * \return                 element
     */
    template<class T>
    const value_type& get(const T value) const
    {
      const int ival = this->getValue(value);

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

    /**
     * Insert element.
     *
     * \param  element         element
     * \return                 (position, status), where status is true if inserted; else false
     */
    virtual pair_type insert(typename JClass<value_type>::argument_type element)
    {
      using namespace std;

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

      if (!this->router.has(ival)) {
        
        container_type::push_back(element);

        iterator i = this->rbegin().base();

        router.put(ival, 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 = container_type::erase(pos);

      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)
    {
      for (iterator i = __begin; i != __end; ++i) {
        this->router.put(this->getValue(*i), this->router.getDefaultAddress());
      }

      iterator i = container_type::erase(__begin, __end);

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

    
    /**
     * Erase element with given value.
     *
     * \param  value           value
     * \return                 true if element has been erased; else false
     */
    template<class T>
    bool erase(const T& value)
    {
      const int ival = this->getValue(value);

      if (this->router.has(ival)) {
        
        iterator pos = this->begin();

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

        this->erase(pos);

        return true;
      }

      return false;
    }

    
    /**
     * Test whether given value is present.
     *
     * \param  value           value
     * \return                 true if present; else false
     */    
    template<class T>
    bool has(const T& value) const
    {
      return router.has(this->getValue(value));
    }

    
    /**
     * Read hash collection from input.
     *
     * \param  in              reader
     * \param  object          hash collection
     * \return                 reader
     */
    friend inline JReader& operator>>(JReader& in, JHashCollection& object)
    {
      int n;

      in >> n;

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

      return in;
    }


    /**
     * Write hash collection to output.
     *
     * \param  out             writer
     * \param  object          hash collection
     * \return                 writer
     */
    friend inline JWriter& operator<<(JWriter& out, const JHashCollection& object)
    {
      int n = object.size();

      out << n;

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

      return out;
    }


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


  protected:
    /**
     * Insert element.
     *
     * \param  pos             position
     * \param  element         element
     * \return                 position
     */
    iterator insert(iterator pos, typename JClass<value_type>::argument_type element)
    {
      return container_type::insert(pos, element);
    }
    
    JRouter<int> router;
    
  private:
    void operator[](int);
    void resize();
    void push_back();
    void pop_back();
  };
}

#endif