// @(#)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