// @(#)root/cont:$Name:  $:$Id: THashTable.h,v 1.13 2006/07/26 13:36:42 rdm Exp $
// Author: Fons Rademakers   27/09/95

/*************************************************************************
 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers.               *
 * All rights reserved.                                                  *
 *                                                                       *
 * For the licensing terms see $ROOTSYS/LICENSE.                         *
 * For the list of contributors see $ROOTSYS/README/CREDITS.             *
 *************************************************************************/

#ifndef ROOT_THashTable
#define ROOT_THashTable


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// THashTable                                                           //
//                                                                      //
// THashTable implements a hash table to store TObject's. The hash      //
// value is calculated using the value returned by the TObject's        //
// Hash() function. Each class inheriting from TObject can override     //
// Hash() as it sees fit.                                               //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#ifndef ROOT_TCollection
#include "TCollection.h"
#endif
#ifndef ROOT_TString
#include "TString.h"
#endif

class TList;
class TListIter;
class THashTableIter;


class THashTable : public TCollection {

friend class  THashTableIter;

private:
   TList     **fCont;          //Hash table (table of lists)
   Int_t       fEntries;       //Number of objects in table
   Int_t       fUsedSlots;     //Number of used slots
   Int_t       fRehashLevel;   //Average collision rate which triggers rehash

   Int_t       GetHashValue(const TObject *obj) const;
   Int_t       GetHashValue(TString &s) const { return s.Hash() % fSize; }
   Int_t       GetHashValue(const char *str) const { return ::Hash(str) % fSize; }

   THashTable(const THashTable&);             // not implemented
   THashTable& operator=(const THashTable&);  // not implemented

public:
   THashTable(Int_t capacity = TCollection::kInitHashTableCapacity, Int_t rehash = 0);
   virtual       ~THashTable();
   void          Add(TObject *obj);
   virtual void  AddAll(const TCollection *col);
   Float_t       AverageCollisions() const;
   void          Clear(Option_t *option="");
   Int_t         Collisions(const char *name) const;
   Int_t         Collisions(TObject *obj) const;
   void          Delete(Option_t *option="");
   TObject      *FindObject(const char *name) const;
   TObject      *FindObject(const TObject *obj) const;
   TList        *GetListForObject(const char *name) const;
   TList        *GetListForObject(const TObject *obj) const;
   TObject     **GetObjectRef(const TObject *obj) const;
   Int_t         GetRehashLevel() const { return fRehashLevel; }
   Int_t         GetSize() const { return fEntries; }
   TIterator    *MakeIterator(Bool_t dir = kIterForward) const;
   void          Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
   TObject      *Remove(TObject *obj);
   TObject      *RemoveSlow(TObject *obj);
   void          SetRehashLevel(Int_t rehash) { fRehashLevel = rehash; }

   ClassDef(THashTable,0)  //A hash table
};

inline Float_t THashTable::AverageCollisions() const
{
   if (fUsedSlots)
      return ((Float_t)fEntries)/fUsedSlots;
   else
      return 0.0;
}

inline Int_t THashTable::GetHashValue(const TObject *obj) const
{
   Int_t i = Int_t(obj->Hash() % fSize);  // need intermediary i for Linux g++
   return i;
}


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// THashTableIter                                                       //
//                                                                      //
// Iterator of hash table.                                              //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

class THashTableIter : public TIterator {

private:
   const THashTable *fTable;       //hash table being iterated
   Int_t             fCursor;      //current position in table
   TListIter        *fListCursor;  //current position in collision list
   Bool_t            fDirection;   //iteration direction

   THashTableIter() : fTable(0), fCursor(0), fListCursor(0), fDirection(kIterForward) { }
   Int_t             NextSlot();

public:
   THashTableIter(const THashTable *ht, Bool_t dir = kIterForward);
   THashTableIter(const THashTableIter &iter);
   ~THashTableIter();
   TIterator      &operator=(const TIterator &rhs);
   THashTableIter &operator=(const THashTableIter &rhs);

   const TCollection *GetCollection() const { return fTable; }
   TObject           *Next();
   void               Reset();

   ClassDef(THashTableIter,0)  //Hash table iterator
};

#endif