// @(#)root/cont:$Id$
// 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);
   void          AddBefore(const TObject *before, 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();
   Bool_t             operator!=(const TIterator &aIter) const;
   Bool_t             operator!=(const THashTableIter &aIter) const;
   TObject           *operator*() const;

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

#endif
 THashTable.h:1
 THashTable.h:2
 THashTable.h:3
 THashTable.h:4
 THashTable.h:5
 THashTable.h:6
 THashTable.h:7
 THashTable.h:8
 THashTable.h:9
 THashTable.h:10
 THashTable.h:11
 THashTable.h:12
 THashTable.h:13
 THashTable.h:14
 THashTable.h:15
 THashTable.h:16
 THashTable.h:17
 THashTable.h:18
 THashTable.h:19
 THashTable.h:20
 THashTable.h:21
 THashTable.h:22
 THashTable.h:23
 THashTable.h:24
 THashTable.h:25
 THashTable.h:26
 THashTable.h:27
 THashTable.h:28
 THashTable.h:29
 THashTable.h:30
 THashTable.h:31
 THashTable.h:32
 THashTable.h:33
 THashTable.h:34
 THashTable.h:35
 THashTable.h:36
 THashTable.h:37
 THashTable.h:38
 THashTable.h:39
 THashTable.h:40
 THashTable.h:41
 THashTable.h:42
 THashTable.h:43
 THashTable.h:44
 THashTable.h:45
 THashTable.h:46
 THashTable.h:47
 THashTable.h:48
 THashTable.h:49
 THashTable.h:50
 THashTable.h:51
 THashTable.h:52
 THashTable.h:53
 THashTable.h:54
 THashTable.h:55
 THashTable.h:56
 THashTable.h:57
 THashTable.h:58
 THashTable.h:59
 THashTable.h:60
 THashTable.h:61
 THashTable.h:62
 THashTable.h:63
 THashTable.h:64
 THashTable.h:65
 THashTable.h:66
 THashTable.h:67
 THashTable.h:68
 THashTable.h:69
 THashTable.h:70
 THashTable.h:71
 THashTable.h:72
 THashTable.h:73
 THashTable.h:74
 THashTable.h:75
 THashTable.h:76
 THashTable.h:77
 THashTable.h:78
 THashTable.h:79
 THashTable.h:80
 THashTable.h:81
 THashTable.h:82
 THashTable.h:83
 THashTable.h:84
 THashTable.h:85
 THashTable.h:86
 THashTable.h:87
 THashTable.h:88
 THashTable.h:89
 THashTable.h:90
 THashTable.h:91
 THashTable.h:92
 THashTable.h:93
 THashTable.h:94
 THashTable.h:95
 THashTable.h:96
 THashTable.h:97
 THashTable.h:98
 THashTable.h:99
 THashTable.h:100
 THashTable.h:101
 THashTable.h:102
 THashTable.h:103
 THashTable.h:104
 THashTable.h:105
 THashTable.h:106
 THashTable.h:107
 THashTable.h:108
 THashTable.h:109
 THashTable.h:110
 THashTable.h:111
 THashTable.h:112
 THashTable.h:113
 THashTable.h:114
 THashTable.h:115
 THashTable.h:116
 THashTable.h:117
 THashTable.h:118
 THashTable.h:119
 THashTable.h:120
 THashTable.h:121
 THashTable.h:122
 THashTable.h:123
 THashTable.h:124
 THashTable.h:125
 THashTable.h:126
 THashTable.h:127
 THashTable.h:128
 THashTable.h:129
 THashTable.h:130
 THashTable.h:131
 THashTable.h:132
 THashTable.h:133
 THashTable.h:134