JHashSet.hh

Go to the documentation of this file.

#ifndef __JTOOLS__JHASHSET__
#define __JTOOLS__JHASHSET__

#include <algorithm>

#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 {


  /**
   * 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>          collection_type;
    typedef typename collection_type::container_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;

    
    /**
     * 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()(const value_type& first, const value_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()) :
      JHashCollection<JElement_t, JEvaluator_t>(evaluator),
      compare(evaluator)
    {}


    /**
     * Insert element.
     *
     * \param  element         element
     * \return                 true if inserted; else false
     */
    virtual bool insert(const value_type& element) override 
    {
      const int ival = this->getValue(element);
      
      if (!this->router.has(ival)) {
        
        iterator p = container_type::insert(lower_bound(this->begin(), this->end(), element, compare), element);

        this->router.put(ival, std::distance(this->begin(), p));

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

      return false;
    }


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


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

#endif