JHashCollection.hh

Go to the documentation of this file.

#ifndef __JTOOLS__JHASHCOLLECTION__
#define __JTOOLS__JHASHCOLLECTION__

#include <vector>

#include "JLang/JException.hh"
#include "JLang/JVectorize.hh"
#include "JTools/JHashEvaluator.hh"
#include "JTools/JRouter.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::JIndexOutOfRange;
  using JLANG::array_type;
  using JLANG::make_array;
  

  /**
   * General purpose class for hash collection of unique elements.
   *
   * The elements in a hash collection are unique according to the specified evaluation.\n
   * The evaluation of elements corresponds to a unary method returning an integer value for a given element;\n
   * The default evaluator is JHashEvaluator. 
   */
  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;


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


    /**
     * Constructor.
     *
     * \param  buffer          input data
     * \param  evaluator       evaluator
     */
    template<class JAllocator_t>
    JHashCollection(const array_type<JElement_t, JAllocator_t>& buffer,
                    const JEvaluator_t& evaluator = JEvaluator_t()) :
      getValue(evaluator)
    {
      for (typename array_type<JElement_t, JAllocator_t>::const_iterator i = buffer.begin(); i != buffer.end(); ++i) {
        insert(*i);
      }
    }


    /**
     * Assignment operator.
     *
     * \param  collection      hash collection
     * \return                 this hash collection
     */
    JHashCollection& operator=(const JHashCollection& collection)
    {
      for (const_iterator i = this->begin(); i != this->end(); ++i) {
        router.put(this->getValue(*i), router.getDefaultAddress());
      }

      container_type::assign(collection.begin(), collection.end());

      router.align(collection.router);

      getValue = collection.getValue;

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

      return *this;
    }


    /**
     * Clear.
     */
    void clear() 
    {
      for (const_iterator i = this->begin(); i != this->end(); ++i) {
        router.put(this->getValue(*i), router.getDefaultAddress());
      }

      container_type::clear();
    }


    /**
     * Swap hash collection.
     *
     * \param  collection      hash collection
     */
    void swap(JHashCollection& collection)
    {
      router.swap(collection.router);

      container_type::swap(collection);
    }


    /**
     * 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))
        return this->begin() + router.get(ival);
      else
        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))
        return this->begin() + router.get(ival);
      else
        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 (!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;
      }

      THROW(JIndexOutOfRange, "JHasCollection::get(): invalid value.");
    }
    

    /**
     * Insert element.
     *
     * \param  element         element
     * \return                 true if inserted; else false
     */
    virtual bool insert(const value_type& element)
    {
      const int ival = this->getValue(element);

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

        router.put(ival, this->size() - 1);

        return true;
      }

      return false;
    }


    /**
     * Insert values.
     *
     * \param  __begin         begin of values
     * \param  __end           end   of values
     */
    template<class T>
    void insert(T __begin, T __end)
    {
      for (T i = __begin; i != __end; ++i) {
        insert(*i);
      }
    }


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

      for (iterator i = container_type::erase(pos); i != this->end(); ++i) {
        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) {
        router.put(this->getValue(*i), router.getDefaultAddress());
      }

      for (iterator i = container_type::erase(__begin, __end); i != this->end(); ++i) {
        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 (router.has(ival)) {

        this->erase(this->begin() + router.get(ival)); 

        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));
    }


    /**
     * Get index of given value.
     *
     * \param  value           value
     * \return                 indecx
     */
    template<class T>
    int getIndex(const T& value) const
    {
      return router.get(this->getValue(value));
    }


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


  protected:
    /**
     * Internal router.
     */
    struct router_type :
      public JRouter<int>
    {
      /**
       * Default constructor.
       */
      router_type() :
        JRouter<int>(-1)             // default address
      {}
    } router;
    
  private:
    void operator[](int);
    void assign();
    void resize();
    void push_back();
    void pop_back();
  };
}

#endif