#ifndef HASHTABLE_H
#define HASHTABLE_H

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

/*!  
\brief General hash table where the client manages the memory
       of the bucket links.  The client defines the hash function 
       of type HFN.

\verbatim
Interface for template HFN parameter
class HFN
{
  public:

    uintc operator()(uintc key) const;

};
\endverbatim

\par Example
\verbatim
  string dict[] = { "abc", "nogo", "python" };
  uintc n(3);
  vector< bucketlink<string> > v(n);
  for (uint i=0; i<n; ++i)
    v[i] = bucketlink<string>(&dict[i]);

  uintc hashtablesize(70);
  stringhash h(32,8);
  hashtable<string,stringhash&> H(hashtablesize,h);

  for (uint i=0; i<n; ++i)
    H.insert( & v[i] );
\endverbatim
*/
template< typename T, typename HFN >
class hashtable
{
public:

  /** Size of vb. */
  uint bucketsize;
  /** Hash function. */
  HFN fn;  

  /** Public if the client wishes to iterate linearly 
      through the hash data structure, another 
      property of hash tables. */
  bucketlink<T> * * vb;   

  typedef bucketlink<T> * blink;

  /** Pre allocate memory requirements before use, 
      do not put this class in a loop. */
  hashtable
  (
    uintc bucketsize_,
    HFN fn_
  );
  /** Destructor releases the memory used. */
  ~hashtable();

  /** Construct in a bad state. */
  hashtable() { bucketsize=0; };

  /** Resize the container - invalidates previous memory. */
  void construct(uintc bucketsize_);

  /** Put a value into the hash table.
      The client manages the memory of x. */
  void insert( bucketlink<T>* x );

  /** Get the link to the data if it exists, else 0 returned.
      The client can potentially modify the data (and corrupt
      this entry), so only modify non-key attributes. */
  bucketlink<T>* insertInverse( T const & key ) const;

  /** Removes the bucket link which compared == with d. */
  boolc remove( T const & key );

  /** Is the element in the hash table? */
  boolc contains( T const & key ) const
    { return insertInverse(key)!=0; }

};

/*!
\brief Iterate over the hash table.
*/
template< typename H>
class hashtableiterator
{
  /** Current integer index. */
  uint ci;
  /** Current link. */
  typename H::blink cx;
public:

  /** Hash table. */
  H & ht;
  /** Pass the hash table */
  hashtableiterator(H & ht_)
    : ht(ht_) {}

  /** Initialize */
  void reset();
  /** Is the iterator valid? */
  boolc operator ! ()
    { return (cx!=0); }
  /** Increment */
  void operator ++ ();
  /** Access */
  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