tpl_dynSetHash.H

# ifndef TPL_DYNSETHASH_H
# define TPL_DYNSETHASH_H

# include <algorithm>
# include <typeinfo>
# include <ahDry.H>
# include <primes.H>
# include <htlist.H>
# include <tpl_dynArray.H>
# include <tpl_dynSetOhash.H>
# include <tpl_lhash.H>
# include <tpl_linHash.H>


namespace Aleph  
{

  template <typename                          Key, 
            class                             Cmp       = Aleph::equal_to<Key>,
            template <typename,  class> class HashTable = LhashTable>
class DynHashTable : public HashTable<Key, Cmp>
{
protected:

  typedef HashTable<Key, Cmp> Base;

  typedef typename HashTable<Key, Cmp>::Bucket Bucket;

public:

  typedef typename Base::Hash_Fct Hash_Fct;

  typedef Key Key_Type;

  typedef Key Item_Type;

  DynHashTable(Hash_Fct hash_fct        = Aleph::dft_hash_fct<Key>,
               const size_t len         = Primes::DefaultPrime,
               const float  lower_alpha = hash_default_lower_alpha,
               const float  upper_alpha = hash_default_upper_alpha) 
    : Base(hash_fct, len, lower_alpha, upper_alpha, true, true)
  {
    // empty
  }

private:

  void copy(const DynHashTable & other)
  {
    for (typename Base::Iterator it(other); it.has_curr(); it.next())
      {
        Bucket * bucket = (Bucket*) it.get_curr();
        insert(bucket->get_key());
        I(*search(bucket->get_key()) == bucket->get_key());
      }
  }

public:

  DynHashTable(const DynHashTable & other)
    : Base(other.hash_fct, other.len, 
           other.lower_alpha, other.upper_alpha, true, true)
  {
    copy(other);
  }
  
  DynHashTable(DynHashTable && other)
    : Base(other.hash_fct, other.len, 
           other.lower_alpha, other.upper_alpha, true, true)
  {
    this->swap(other);
  }

  ~DynHashTable()
  {
    this->empty();
  }

  DynHashTable & operator = (const DynHashTable & other)
  {
    if (this == &other)
      return *this;

    this->empty();
    copy(other);

    return *this;
  }

  DynHashTable & operator = (DynHashTable && other)
  {
    this->swap(other);
    return *this;
  }

protected:

  Key * insert_bucket(Bucket * bucket)
  {
    Bucket * ret_val = (Bucket*) this->Base::insert(bucket);
    if (ret_val == NULL) // is the key in the table?
      {    // yes! ==> free bucket
        delete bucket;
        return NULL;
      }

    return &ret_val->get_key();
  }

public:

  Key * insert(const Key & key)
  {
    return insert_bucket(new Bucket (key));
  }

  Key * insert(Key && key)
  {
    return insert_bucket(new Bucket (std::move(key)));
  }

  Key * add(const Key & key)
  {
    return insert_bucket(new Bucket (key));
  }
 
  Key * add(Key && key)
  {
    return insert_bucket(new Bucket (std::move(key)));
  }

  Key * search(const Key & key) const
  {
    Bucket * bucket = (Bucket*) this->Base::search(key);

    return bucket != NULL ? &bucket->get_key() : NULL;
  }

  bool has(const Key & key) const 
  {
    return this->Base::search(key) != NULL;
  }

  bool contains(const Key & key) const { return has(key); }

  Key & find(const Key & key)
  {
    Bucket * bucket = (Bucket*) this->Base::search(key);

    if (bucket == NULL)
      throw std::domain_error("Key not found in hash");

    return bucket->get_key();
  }

  Generic_Keys(Key);

protected:

  static Bucket * key_to_bucket(Key * key)
  {
    Bucket * ret_val = 0;
    size_t offset = reinterpret_cast<size_t>(&ret_val->get_key());
    
    return reinterpret_cast<Bucket*>(reinterpret_cast<size_t>(key) - offset);
  }

public:

  void remove(Key * key)
  {
    Bucket * bucket = key_to_bucket(key);
    this->Base::remove(bucket);
    delete bucket;
  }

  void remove(const Key & key)
  {
    Bucket * bucket = (Bucket*) this->Base::search(key);
    if (bucket == NULL)
      throw std::domain_error("Key not in hash table");

    this->Base::remove(bucket);
    delete bucket;
  }


  Generic_Traverse(Key);
  Functional_Methods(Key);
  Equal_To_Method(DynHashTable);

  class Iterator : public Base::Iterator
  { 
  public: 

    Iterator(const DynHashTable & table) : Base::Iterator(table) {} 

    const Key & get_curr() 
    { 
      return this->Base::Iterator::get_curr()->get_key(); 
    } 
    
    void del() { delete this->Base::Iterator::del(); } 
  }; 
};


  template <typename Key, class Cmp = Aleph::equal_to<Key>>
struct DynSetHash : public DynHashTable<Key, Cmp, LhashTable>
{
  typedef DynHashTable<Key, Cmp, LhashTable> Base;

  using Base::Base;
}; 

  template <typename Key, class Cmp = Aleph::equal_to<Key>>
struct DynSetLinHash : public DynHashTable<Key, Cmp, LinearHashTable>
{
  typedef DynHashTable<Key, Cmp, LinearHashTable> Base;

  using Base::Base;
}; 


template <typename Key, typename Data, 
          class Cmp = Dft_Pair_Cmp<Key, Data, Aleph::equal_to<Key>>,
          template <class, class> class HashTable = LinearHashTable>
class DynMapHashTable 
  : public DynHashTable<std::pair<Key, Data>, Cmp, HashTable>
{
  typedef std::pair<Key, Data> Pair;

  typedef DynHashTable<std::pair<Key, Data>, Cmp, HashTable> Base;

  typedef typename Base::Bucket Bucket;

  public:

  // given a valid reference to key, given from find or through iterator
  // or other functional primitives, get_data() retrieves the data
  // associated to the key inside the table.
  Data & get_data(const Key & key)
  {
    return key_to_pair<Key, Data>(&const_cast<Key&>(key))->second;    
  }

  const Key & get_key(Data * data_ptr)
  {
    return data_to_pair<Key, Data>(data_ptr)->first;
  }

  typedef Data Value_Type;

  typedef size_t (*Hash_Fct)(const Key&);

  using Base::Base;

  template <size_t (*fct)(const Key & k)> static
  size_t wrapper(const std::pair<Key, Data> & p)
  {
    return (*fct)(p.first);
  }

  DynMapHashTable
  (typename Base::Hash_Fct hash_fct = wrapper<Aleph::dft_hash_fct<Key>>,
   const size_t len                 = Primes::DefaultPrime,
   const float  lower_alpha         = hash_default_lower_alpha,
   const float  upper_alpha         = hash_default_upper_alpha) 
    : Base(hash_fct, len, lower_alpha, upper_alpha)
  {
    // empty
  }

  Key * insert(const Key & key, const Data & data)
  {
    Pair * p = this->insert_bucket(new typename Base::Bucket (Pair(key, data)));

    return p != NULL ? &p->first : NULL;
  }

  Key * insert(const Key & key, Data && data)
  {
    Pair * p = this->insert_bucket
      (new typename Base::Bucket (Pair(key, std::move(data))));

    return p != NULL ? &p->first : NULL;
  }

  Key * insert(Key && key, Data && data)
  {
    Pair * p = this->insert_bucket
      (new typename Base::Bucket (Pair(std::move(key), std::move(data))));

    return p != NULL ? &p->first : NULL;
  }

  Key * insert(Key && key, const Data & data)
  {
    Pair * p= this->insert_bucket
      (new typename Base::Bucket (Pair(std::move(key), data)));

    return p != NULL ? &p->first : NULL;
  }

  Data * search(const Key & key) const
  {
    Pair * p = this->Base::search(Pair(key, Data()));
    return p != NULL ? &p->second : NULL;
  }

  bool has(const Key & key)
  {
    return this->Base::search(Pair(key, Data())) != NULL;
  }

  Data & find(const Key & key)
  {
    return Base::find(Pair(key, Data())).second;
  }

  void remove_by_data(Data & data)
  {
    Base::remove(data_to_pair<Key, Data>(&data));
  }

  void remove(const Key & key)
  {
    Base::remove(Pair(key, Data()));
  }

  Map_Sequences_Methods();

  Generate_Proxy_Operator(DynMapHashTable);
};

template <typename Key,
          typename Data,
          class    Cmp = Dft_Pair_Cmp<Key, Data, Aleph::equal_to<Key>>>
struct DynMapLinHash : public DynMapHashTable<Key, Data, Cmp, LinearHashTable>
{
  typedef DynMapHashTable<Key, Data, Cmp, LinearHashTable> Base;

  using Base::Base;
};

template <typename Key,
          typename Data,
          class    Cmp = Dft_Pair_Cmp<Key,Data, Aleph::equal_to<Key>>>
struct DynMapHash : public DynMapHashTable<Key, Data, Cmp, LhashTable>
{
  typedef DynMapHashTable<Key, Data, Cmp, LhashTable> Base;

  using Base::Base;
};



} // end namespace Aleph

# endif // TPL_DYNSETHASH_H