// @(#)root/cont:$Id$
// Author: Fons Rademakers   26/05/99

/*************************************************************************
 * 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_TExMap
#define ROOT_TExMap


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TExMap                                                               //
//                                                                      //
// This class stores a (key,value) pair using an external hash.         //
// The (key,value) are Long64_t's and therefore can contain object      //
// pointers or any longs. The map uses an open addressing hashing       //
// method (linear probing).                                             //
//                                                                      //
//////////////////////////////////////////////////////////////////////////


#ifndef ROOT_TObject
#include "TObject.h"
#endif

class TExMapIter;


class TExMap : public TObject {

friend class TExMapIter;

private:
   struct Assoc_t {
   private:
      ULong64_t  fHash;
   public:
      Long64_t   fKey;
      Long64_t   fValue;
      void       SetHash(ULong64_t h) { fHash = (h | 1); } // bit(0) is "1" when in use
      ULong64_t  GetHash() const { return fHash; }
      Bool_t     InUse() const { return fHash & 1; }
      void       Clear() { fHash = 0x0; }
   };

   Assoc_t    *fTable;
   Int_t       fSize;
   Int_t       fTally;

   Bool_t      HighWaterMark() { return (Bool_t) (fTally >= ((3*fSize)/4)); }
   Int_t       FindElement(ULong64_t hash, Long64_t key);
   void        FixCollisions(Int_t index);


public:
   TExMap(Int_t mapSize = 100);
   TExMap(const TExMap &map);
   TExMap& operator=(const TExMap&);
   ~TExMap();

   void      Add(ULong64_t hash, Long64_t key, Long64_t value);
   void      Add(Long64_t key, Long64_t value) { Add(key, key, value); }
   void      AddAt(UInt_t slot, ULong64_t hash, Long64_t key, Long64_t value);
   void      Delete(Option_t *opt = "");
   Int_t     Capacity() const { return fSize; }
   void      Expand(Int_t newsize);
   Int_t     GetSize() const { return fTally; }
   Long64_t  GetValue(ULong64_t hash, Long64_t key);
   Long64_t  GetValue(Long64_t key) { return GetValue(key, key); }
   Long64_t  GetValue(ULong64_t hash, Long64_t key, UInt_t &slot);
   void      Remove(ULong64_t hash, Long64_t key);
   void      Remove(Long64_t key) { Remove(key, key); }

   Long64_t &operator()(ULong64_t hash, Long64_t key);
   Long64_t &operator()(Long64_t key) { return operator()(key, key); }

   ClassDef(TExMap,3)  //Map with external hash
};


class TExMapIter {

private:
   const TExMap   *fMap;
   Int_t           fCursor;

public:
   TExMapIter(const TExMap *map);
   TExMapIter(const TExMapIter& tei) : fMap(tei.fMap), fCursor(tei.fCursor) { }
   TExMapIter& operator=(const TExMapIter&);
   virtual ~TExMapIter() { }

   const TExMap  *GetCollection() const { return fMap; }
   Bool_t         Next(ULong64_t &hash, Long64_t &key, Long64_t &value);
   Bool_t         Next(Long64_t &key, Long64_t &value);
   void           Reset() { fCursor = 0; }

   ClassDef(TExMapIter,0)  // TExMap iterator
};

#endif
 TExMap.h:1
 TExMap.h:2
 TExMap.h:3
 TExMap.h:4
 TExMap.h:5
 TExMap.h:6
 TExMap.h:7
 TExMap.h:8
 TExMap.h:9
 TExMap.h:10
 TExMap.h:11
 TExMap.h:12
 TExMap.h:13
 TExMap.h:14
 TExMap.h:15
 TExMap.h:16
 TExMap.h:17
 TExMap.h:18
 TExMap.h:19
 TExMap.h:20
 TExMap.h:21
 TExMap.h:22
 TExMap.h:23
 TExMap.h:24
 TExMap.h:25
 TExMap.h:26
 TExMap.h:27
 TExMap.h:28
 TExMap.h:29
 TExMap.h:30
 TExMap.h:31
 TExMap.h:32
 TExMap.h:33
 TExMap.h:34
 TExMap.h:35
 TExMap.h:36
 TExMap.h:37
 TExMap.h:38
 TExMap.h:39
 TExMap.h:40
 TExMap.h:41
 TExMap.h:42
 TExMap.h:43
 TExMap.h:44
 TExMap.h:45
 TExMap.h:46
 TExMap.h:47
 TExMap.h:48
 TExMap.h:49
 TExMap.h:50
 TExMap.h:51
 TExMap.h:52
 TExMap.h:53
 TExMap.h:54
 TExMap.h:55
 TExMap.h:56
 TExMap.h:57
 TExMap.h:58
 TExMap.h:59
 TExMap.h:60
 TExMap.h:61
 TExMap.h:62
 TExMap.h:63
 TExMap.h:64
 TExMap.h:65
 TExMap.h:66
 TExMap.h:67
 TExMap.h:68
 TExMap.h:69
 TExMap.h:70
 TExMap.h:71
 TExMap.h:72
 TExMap.h:73
 TExMap.h:74
 TExMap.h:75
 TExMap.h:76
 TExMap.h:77
 TExMap.h:78
 TExMap.h:79
 TExMap.h:80
 TExMap.h:81
 TExMap.h:82
 TExMap.h:83
 TExMap.h:84
 TExMap.h:85
 TExMap.h:86
 TExMap.h:87
 TExMap.h:88
 TExMap.h:89
 TExMap.h:90
 TExMap.h:91
 TExMap.h:92
 TExMap.h:93
 TExMap.h:94
 TExMap.h:95
 TExMap.h:96
 TExMap.h:97
 TExMap.h:98
 TExMap.h:99
 TExMap.h:100
 TExMap.h:101
 TExMap.h:102
 TExMap.h:103
 TExMap.h:104
 TExMap.h:105
 TExMap.h:106
 TExMap.h:107