JHashSet.hh

Go to the documentation of this file.

#ifndef __JTOOLS__JHASHSET__
#define __JTOOLS__JHASHSET__

#include <utility>
#include <algorithm>

#include "JLang/JClass.hh"
#include "JTools/JHashEvaluator.hh"
#include "JTools/JHashCollection.hh"


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

namespace JTOOLS {

  using JLANG::JClass;
  

  /**
   * General purpose class for hash set of elements.
   *
   * The elements in a hash set are sorted 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. 
   */
  template<class JElement_t, class JEvaluator_t = JHashEvaluator>
  class JHashSet :
    public JHashCollection<JElement_t, JEvaluator_t>
  {
  public:

    typedef JElement_t                                           value_type;
    typedef JEvaluator_t                                         evaluator_type;
    
    typedef JHashCollection<value_type, evaluator_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;

    
    /**
     * Auxiliary class for ordering of objects in the set by the hash value.
     */
    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) < this->getValue(second);
      }


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


    /**
     * Constructor.
     *
     * \param  evaluator       evaluator
     */
    JHashSet(const JEvaluator_t& evaluator = JEvaluator_t()) :
      container_type(evaluator),
      compare       (evaluator)
    {}


    /**
     * 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)) {
        
        iterator i = container_type::insert(lower_bound(this->begin(), this->end(), element, compare), element);

        this->router.put(ival, distance(this->begin(), i));

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

      } else {

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


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


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

#endif