#ifndef BHASH_HEADER
#define BHASH_HEADER 1
//////////////////////////////////////////////
//! file="amma/Contain/Branch/BHash.hh"
//! lib=Branch
//! author="Charles Galambos"
//! docentry="Containers.Hash Tables"
//! rcsid="$Id: BHash.hh,v 1.12 2000/02/27 19:15:24 ees1cg Exp $"
//! date="26/02/97"

#include "amma/SArray1d.hh"
#include "amma/KPair.hh"
#include "amma/BList.hh"
#include "amma/HashAR.hh"  // Needed for the hash functions..
#include "amma/Empty.hh"

//! userlevel=Develop
//: Branching Hash table.
// Not finised yet.
// !!!! Big object !!!!

template<class K,class T>
class BHashC {
public:
  inline BHashC();
  // Default constructor.
  
  inline BHashC(const BHashC<K,T> &Oth);
  //: Copy constructor.
  // This creates a new handle.
  
  inline BHashC(const BHashC<K,T> &Oth,BooleanT doResize);
  // Copy constructor.
  // Creates a copy of the list table. if 'doResize' is
  // true it will also check if a table resize is needed.
  
  inline void Insert(const K &Key,const T &Data);
  // Insert element into table.
  // This will override value if key already exists.
  
  inline const T *Lookup(const K &Key) const;
  // Lookup by key.
  
  void Add(const BHashC<K,T> &oth);
  //: Add contents of another table into this one.
  
private:
  typedef HashElemT<K,T> HashElem;
  
  SArray1dC<BListC<HashElemT<K,T> > > table;
  IntT elements;
};

//: Branching Hash table.
// !!!! Small object !!!!

template<class K,class T>
class BHashIterC {
public:
  inline BHashIterC()
    {}
  //: Default constructor.
  
  BHashIterC(const BHashC<K,T> &Oth);
  // Constructor.

  inline BooleanT First();
  //: Goto first element in table.
  
  BooleanT IsElm() const 
    { it.IsElm(); }
  //: At valid element ?
  
  inline BooleanT Next();
  //: Goto next element.
  
  T &Data()
    { return it.Data().Data(); }
  //: Access data.
  
  const T &Data() const
    { return it.Data().Data(); }
  //: Access data.
  
  const K &Key() const
    { return it.Data().Key(); }
  //: Access key.

private:
  BooleanT NextValid();
  //: Skip forward to the next valid element.
  
  SArray1dC<BListC<HashElemT<K,T> > > table;
  int tp; // Position in table.
  BListIterC<HashElemT<K,T> > it;
  HashARC<K,EmptyC> done;
};


////////////////////////////////////////////////////////////////////
// Default constructor.

template<class K,class T>
inline 
BHashC<K,T>::BHashC() 
  : table(10),
    elements(0)
{}

/////////////////////
// Copy constructor.

template<class K,class T>
inline 
BHashC<K,T>::BHashC(const BHashC<K,T> &oth) 
  : table(oth.table),
    elements(oth.elements)
{}

// Copy constructor.
// Creates a copy of the list table. if 'doResize' is
// true it will also check if a table resize is needed.

template<class K,class T>
inline BHashC<K,T>::BHashC(const BHashC<K,T> &oth,BooleanT doResize) 
  : table(table.Copy()),
    elements(oth.elements)
{ }

/////////////////////
// Insert element into table.

template<class K,class T>
inline 
void BHashC<K,T>::Insert(const K &key,const T &data) 
{ 
  table[StdHash(key) % table.Size()].InsFirst(HashElem(key,data)); 
  elements++;
}

/////////////////////
// Lookup by key.

template<class K,class T>
inline 
const T *BHashC<K,T>::Lookup(const K &key) const {
  for(BListIterC<T> it(table[StdHash(key) % table.Size()]);it.IsElm();it.Next()) {
    if(it.Data().GetKey() == key)
      return it.Data().Data();
  }
  return 0;
}

/////////////////////////////////////////////////////


//: Skip forward to the next valid element.

template<class K,class T>
BooleanT BHashIterC<K,T>::NextValid() {
  while(!it.IsElm()) {
    do {
      tp++;
      if(tp >= tableSize()) 
	return false;
      it = table[tp];
    } while(!it.IsElm()) ;
    if(!done.IsMember(it.Data().Key())) 
      break;
    it.Next();
  }
  return true;
}

//: Goto first element in table.

template<class K,class T>
BooleanT BHashIterC<K,T>::First()
{
  done.Empty();
  tp = 0;
  it = table[0];
  return NextValid();
}

//: Constructor.

template<class K,class T>
BHashIterC<K,T>::BHashIterC(const BHashC<K,T> &Oth)
{ First(); }

//: Goto next element.

template<class K,class T>
BooleanT BHashIterC<K,T>::Next() {
  it.Next();
  return NextValid();
}


////////////////////////////////////////////////

//: Add contents of another table into this one.
template<class K,class T>
void BHashC<K,T>::Add(const BHashC<K,T> &oth) {
  for(BHashIterC<K,T> it(*this);it.IsElm();it.Next())
    Insert(it.Data());
}



#endif