ROOT logo
// @(#)root/cont:$Id: TMap.h 25128 2008-08-12 17:59:19Z pcanal $
// Author: Fons Rademakers   12/11/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_TMap
#define ROOT_TMap


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TMap                                                                 //
//                                                                      //
// TMap implements an associative array of (key,value) pairs using a    //
// hash table for efficient retrieval (therefore TMap does not conserve //
// the order of the entries). The hash value is calculated              //
// using the value returned by the keys Hash() function. Both key and   //
// value need to inherit from TObject.                                  //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

#ifndef ROOT_TCollection
#include "TCollection.h"
#endif
#ifndef ROOT_THashTable
#include "THashTable.h"
#endif

#include <iterator>


class THashTableIter;
class TMapIter;
class TPair;
class TBrowser;


class TMap : public TCollection {

friend class  TMapIter;

private:
   THashTable   *fTable;     //Hash table used to store TPair's

   TMap(const TMap& map);             // not implemented
   TMap& operator=(const TMap& map);  // not implemented

protected:
   enum { kIsOwnerValue = BIT(15) };

   virtual void        PrintCollectionEntry(TObject* entry, Option_t* option, Int_t recurse) const;

public:
   typedef TMapIter Iterator_t;

   TMap(Int_t capacity = TCollection::kInitHashTableCapacity, Int_t rehash = 0);
   virtual           ~TMap();
   void              Add(TObject *obj);
   void              Add(TObject *key, TObject *value);
   Float_t           AverageCollisions() const;
   Int_t             Capacity() const;
   void              Clear(Option_t *option="");
   Int_t             Collisions(const char *keyname) const;
   Int_t             Collisions(TObject *key) const;
   void              Delete(Option_t *option="");
   void              DeleteKeys() { Delete(); }
   void              DeleteValues();
   void              DeleteAll();
   Bool_t            DeleteEntry(TObject *key);
   TObject          *FindObject(const char *keyname) const;
   TObject          *FindObject(const TObject *key) const;
   TObject         **GetObjectRef(const TObject *obj) const { return fTable->GetObjectRef(obj); }
   const THashTable *GetTable() const { return fTable; }
   TObject          *GetValue(const char *keyname) const;
   TObject          *GetValue(const TObject *key) const;
   Bool_t            IsOwnerValue() const { return TestBit(kIsOwnerValue); }
   TObject          *operator()(const char *keyname) const { return GetValue(keyname); }
   TObject          *operator()(const TObject *key) const { return GetValue(key); }
   TIterator        *MakeIterator(Bool_t dir = kIterForward) const;
   void              Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
   TObject          *Remove(TObject *key);
   TPair            *RemoveEntry(TObject *key);
   virtual void      SetOwnerValue(Bool_t enable = kTRUE);
   virtual void      SetOwnerKeyValue(Bool_t ownkeys = kTRUE, Bool_t ownvals = kTRUE);

   ClassDef(TMap,3)  //A (key,value) map
};


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TPair                                                                //
//                                                                      //
// Class used by TMap to store (key,value) pairs.                       //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

class TPair : public TObject {

private:
   TObject  *fKey;
   TObject  *fValue;

   TPair& operator=(const TPair&); // Not implemented

public:
   TPair(TObject *key, TObject *value) : fKey(key), fValue(value) { }
   TPair(const TPair &a) : TObject(), fKey(a.fKey), fValue(a.fValue) { }
   virtual               ~TPair() { }
   Bool_t                IsFolder() const { return kTRUE;}
   virtual void          Browse(TBrowser *b);
   const char           *GetName() const { return fKey->GetName(); }
   const char           *GetTitle() const { return fKey->GetTitle(); }
   ULong_t               Hash() const { return fKey->Hash(); }
   Bool_t                IsEqual(const TObject *obj) const { return fKey->IsEqual(obj); }
   TObject              *Key() const { return fKey; }
   TObject              *Value() const { return fValue; }
   void                  SetValue(TObject *val) { fValue = val; }

   ClassDef(TPair,0); // Pair TObject*, TObject*
};

typedef TPair   TAssoc;     // for backward compatibility


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// TMapIter                                                             //
//                                                                      //
// Iterator of a map.                                                   //
//                                                                      //
//////////////////////////////////////////////////////////////////////////

class TMapIter : public TIterator,
                 public std::iterator<std::bidirectional_iterator_tag,
                                      TObject*, std::ptrdiff_t,
                                      const TObject**, const TObject*&> {

private:
   const TMap       *fMap;         //map being iterated
   THashTableIter   *fCursor;      //current position in map
   Bool_t            fDirection;   //iteration direction

   TMapIter() : fMap(0), fCursor(0), fDirection(kIterForward) { }

public:
   TMapIter(const TMap *map, Bool_t dir = kIterForward);
   TMapIter(const TMapIter &iter);
   ~TMapIter();
   TIterator &operator=(const TIterator &rhs);
   TMapIter  &operator=(const TMapIter &rhs);

   const TCollection *GetCollection() const { return fMap; }
   TObject           *Next();
   void               Reset();
   bool               operator!=(const TIterator &aIter) const;
   bool               operator!=(const TMapIter &aIter) const;
   TObject           *operator*() const;

   ClassDef(TMapIter,0)  //Map iterator
};

#endif
 TMap.h:1
 TMap.h:2
 TMap.h:3
 TMap.h:4
 TMap.h:5
 TMap.h:6
 TMap.h:7
 TMap.h:8
 TMap.h:9
 TMap.h:10
 TMap.h:11
 TMap.h:12
 TMap.h:13
 TMap.h:14
 TMap.h:15
 TMap.h:16
 TMap.h:17
 TMap.h:18
 TMap.h:19
 TMap.h:20
 TMap.h:21
 TMap.h:22
 TMap.h:23
 TMap.h:24
 TMap.h:25
 TMap.h:26
 TMap.h:27
 TMap.h:28
 TMap.h:29
 TMap.h:30
 TMap.h:31
 TMap.h:32
 TMap.h:33
 TMap.h:34
 TMap.h:35
 TMap.h:36
 TMap.h:37
 TMap.h:38
 TMap.h:39
 TMap.h:40
 TMap.h:41
 TMap.h:42
 TMap.h:43
 TMap.h:44
 TMap.h:45
 TMap.h:46
 TMap.h:47
 TMap.h:48
 TMap.h:49
 TMap.h:50
 TMap.h:51
 TMap.h:52
 TMap.h:53
 TMap.h:54
 TMap.h:55
 TMap.h:56
 TMap.h:57
 TMap.h:58
 TMap.h:59
 TMap.h:60
 TMap.h:61
 TMap.h:62
 TMap.h:63
 TMap.h:64
 TMap.h:65
 TMap.h:66
 TMap.h:67
 TMap.h:68
 TMap.h:69
 TMap.h:70
 TMap.h:71
 TMap.h:72
 TMap.h:73
 TMap.h:74
 TMap.h:75
 TMap.h:76
 TMap.h:77
 TMap.h:78
 TMap.h:79
 TMap.h:80
 TMap.h:81
 TMap.h:82
 TMap.h:83
 TMap.h:84
 TMap.h:85
 TMap.h:86
 TMap.h:87
 TMap.h:88
 TMap.h:89
 TMap.h:90
 TMap.h:91
 TMap.h:92
 TMap.h:93
 TMap.h:94
 TMap.h:95
 TMap.h:96
 TMap.h:97
 TMap.h:98
 TMap.h:99
 TMap.h:100
 TMap.h:101
 TMap.h:102
 TMap.h:103
 TMap.h:104
 TMap.h:105
 TMap.h:106
 TMap.h:107
 TMap.h:108
 TMap.h:109
 TMap.h:110
 TMap.h:111
 TMap.h:112
 TMap.h:113
 TMap.h:114
 TMap.h:115
 TMap.h:116
 TMap.h:117
 TMap.h:118
 TMap.h:119
 TMap.h:120
 TMap.h:121
 TMap.h:122
 TMap.h:123
 TMap.h:124
 TMap.h:125
 TMap.h:126
 TMap.h:127
 TMap.h:128
 TMap.h:129
 TMap.h:130
 TMap.h:131
 TMap.h:132
 TMap.h:133
 TMap.h:134
 TMap.h:135
 TMap.h:136
 TMap.h:137
 TMap.h:138
 TMap.h:139
 TMap.h:140
 TMap.h:141
 TMap.h:142
 TMap.h:143
 TMap.h:144
 TMap.h:145
 TMap.h:146
 TMap.h:147
 TMap.h:148
 TMap.h:149
 TMap.h:150
 TMap.h:151
 TMap.h:152
 TMap.h:153
 TMap.h:154
 TMap.h:155
 TMap.h:156
 TMap.h:157
 TMap.h:158
 TMap.h:159
 TMap.h:160
 TMap.h:161
 TMap.h:162
 TMap.h:163
 TMap.h:164
 TMap.h:165
 TMap.h:166
 TMap.h:167
 TMap.h:168
 TMap.h:169