hashtable.h

Go to the documentation of this file.

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <bucketlink.h>
#include <typedefs.h>

template< typename T, typename HFN >
class hashtable
{
public:

  uint bucketsize;
  HFN fn;  

  bucketlink<T> * * vb;   

  typedef bucketlink<T> * blink;

  hashtable
  (
    uintc bucketsize_,
    HFN fn_
  );
  ~hashtable();

  hashtable() { bucketsize=0; };

  void construct(uintc bucketsize_);

  void insert( bucketlink<T>* x );

  bucketlink<T>* insertInverse( T const & key ) const;

  boolc remove( T const & key );

  boolc contains( T const & key ) const
    { return insertInverse(key)!=0; }

};

template< typename H>
class hashtableiterator
{
  uint ci;
  typename H::blink cx;
public:

  H & ht;
  hashtableiterator(H & ht_)
    : ht(ht_) {}

  void reset();
  boolc operator ! ()
    { return (cx!=0); }
  void operator ++ ();
  typename H::blink operator()() const 
    { return cx; };
 
};


//---------------------------------------------------------
//  Implementation

template< typename H >
void hashtableiterator<H>::reset()
{
  ci=0; 
  cx=ht.vb[0]; 
  if (cx==0)
    ++(*this);
}

template< typename H >
void hashtableiterator<H>::operator ++ ()
{
  if (cx)
  {
    cx = cx->next;
    if (cx)
      return;

    ++ci;
  }

  for ( ; ci<ht.bucketsize; ++ci)
  {
    cx = ht.vb[ci];
    if (cx==0)
      continue;

    return;
  }
}

template< typename T, typename HFN >
bucketlink<T>* hashtable<T,HFN>::insertInverse
( 
  T const & key 
) const
{
  assert(bucketsize!=0);

  uint k = fn(key) % bucketsize;

  bucketlink<T> * cp( vb[k] );
  if (cp==0)
    return 0;

  for ( ; cp!=0; cp = cp->next )
  {
    if (*(cp->data) == key)
      return cp;
  }

  return 0;
}

template< typename T, typename HFN >
boolc hashtable<T,HFN>::remove
( 
  T const & key 
) 
{
  assert(bucketsize!=0);

  uint k = fn(key) % bucketsize;

  //bucketlink<T> * cp( vb[k] );
  blink cp( vb[k] );
  if (cp==0)
    return false;

  // Element to be removed at head of list.
  if (*(cp->data) == key)
  {
    vb[k] = cp->next;
    return true;
  }

  blink prev=cp;
  cp=cp->next;
  for ( ; cp!=0; cp = cp->next )
  {
    if (*(cp->data) == key)
    {
      prev->next = cp->next;
      return true;
    }

    prev=cp;
  }

  return false;
}

template< typename T, typename HFN >
void hashtable<T,HFN>::insert( bucketlink<T>* x )
{
  if(x==0)
    return;

  assert(bucketsize!=0);

  uint k = fn( * x->data ) % bucketsize;

  bucketlink<T> * cp( vb[k] );
  if (cp==0)
  {
    vb[k] = x; 
    return;
  }

  // Insert at the head of the list.
  x->next = cp;
  vb[k] = x;
}

template< typename T, typename HFN >
hashtable<T,HFN>::hashtable
(
  uintc bucketsize_,
  HFN fn_
)
  : bucketsize(bucketsize_), fn(fn_)
{
  vb = new bucketlink<T> * [bucketsize];
  for (uint i=0; i<bucketsize; ++i)
    vb[i]=0;
}

template< typename T, typename HFN >
hashtable<T,HFN>::~hashtable()
{
  delete[] vb;
  vb=0;
}

template< typename T, typename HFN >
void hashtable<T,HFN>::construct(uintc bucketsize_)
{
  bucketsize = bucketsize_;
  delete[] vb;
  vb = new bucketlink<T> * [bucketsize];
  for (uint i=0; i<bucketsize; ++i)
    vb[i]=0;
}

#endif