1 // @(#)root/cont:$Id$
2 // Author: Fons Rademakers 12/11/95
3
4 /*************************************************************************
5 * Copyright (C) 1995-2000, Rene Brun and Fons Rademakers. *
6 * All rights reserved. *
7 * *
8 * For the licensing terms see $ROOTSYS/LICENSE. *
9 * For the list of contributors see $ROOTSYS/README/CREDITS. *
10 *************************************************************************/
11
12 #ifndef ROOT_TMap
13 #define ROOT_TMap
14
15
16 //////////////////////////////////////////////////////////////////////////
17 // //
18 // TMap //
19 // //
20 // TMap implements an associative array of (key,value) pairs using a //
21 // hash table for efficient retrieval (therefore TMap does not conserve //
22 // the order of the entries). The hash value is calculated //
23 // using the value returned by the keys Hash() function. Both key and //
24 // value need to inherit from TObject. //
25 // //
26 //////////////////////////////////////////////////////////////////////////
27
28 #ifndef ROOT_TCollection
29 #include "TCollection.h"
30 #endif
31 #ifndef ROOT_THashTable
32 #include "THashTable.h"
33 #endif
34
35 #include <iterator>
36
37
38 class THashTableIter;
39 class TMapIter;
40 class TPair;
41 class TBrowser;
42
43
44 class TMap : public TCollection {
45
46 friend class TMapIter;
47
48 private:
49 THashTable *fTable; //Hash table used to store TPair's
50
51 TMap(const TMap& map); // not implemented
52 TMap& operator=(const TMap& map); // not implemented
53
54 protected:
55 enum { kIsOwnerValue = BIT(15) };
56
57 virtual void PrintCollectionEntry(TObject* entry, Option_t* option, Int_t recurse) const;
58
59 public:
60 typedef TMapIter Iterator_t;
61
62 TMap(Int_t capacity = TCollection::kInitHashTableCapacity, Int_t rehash = 0);
63 virtual ~TMap();
64 void Add(TObject *obj);
65 void Add(TObject *key, TObject *value);
66 Float_t AverageCollisions() const;
67 Int_t Capacity() const;
68 void Clear(Option_t *option="");
69 Int_t Collisions(const char *keyname) const;
70 Int_t Collisions(TObject *key) const;
71 void Delete(Option_t *option="");
72 void DeleteKeys() { Delete(); }
73 void DeleteValues();
74 void DeleteAll();
75 Bool_t DeleteEntry(TObject *key);
76 TObject *FindObject(const char *keyname) const;
77 TObject *FindObject(const TObject *key) const;
78 TObject **GetObjectRef(const TObject *obj) const { return fTable->GetObjectRef(obj); }
79 const THashTable *GetTable() const { return fTable; }
80 TObject *GetValue(const char *keyname) const;
81 TObject *GetValue(const TObject *key) const;
82 Bool_t IsOwnerValue() const { return TestBit(kIsOwnerValue); }
83 TObject *operator()(const char *keyname) const { return GetValue(keyname); }
84 TObject *operator()(const TObject *key) const { return GetValue(key); }
85 TIterator *MakeIterator(Bool_t dir = kIterForward) const;
86 void Rehash(Int_t newCapacity, Bool_t checkObjValidity = kTRUE);
87 TObject *Remove(TObject *key);
88 TPair *RemoveEntry(TObject *key);
89 virtual void SetOwnerValue(Bool_t enable = kTRUE);
90 virtual void SetOwnerKeyValue(Bool_t ownkeys = kTRUE, Bool_t ownvals = kTRUE);
91 virtual Int_t Write(const char *name=0, Int_t option=0, Int_t bufsize=0);
92 virtual Int_t Write(const char *name=0, Int_t option=0, Int_t bufsize=0) const;
93
94 ClassDef(TMap,3) //A (key,value) map
95 };
96
97
98 //////////////////////////////////////////////////////////////////////////
99 // //
100 // TPair //
101 // //
102 // Class used by TMap to store (key,value) pairs. //
103 // //
104 //////////////////////////////////////////////////////////////////////////
105
106 class TPair : public TObject {
107
108 private:
109 TObject *fKey;
110 TObject *fValue;
111
112 TPair& operator=(const TPair&); // Not implemented
113
114 public:
115 TPair(TObject *key, TObject *value) : fKey(key), fValue(value) { }
116 TPair(const TPair &a) : TObject(), fKey(a.fKey), fValue(a.fValue) { }
117 virtual ~TPair() { }
118 Bool_t IsFolder() const { return kTRUE;}
119 virtual void Browse(TBrowser *b);
120 const char *GetName() const { return fKey->GetName(); }
121 const char *GetTitle() const { return fKey->GetTitle(); }
122 ULong_t Hash() const { return fKey->Hash(); }
123 Bool_t IsEqual(const TObject *obj) const { return fKey->IsEqual(obj); }
124 TObject *Key() const { return fKey; }
125 TObject *Value() const { return fValue; }
126 void SetValue(TObject *val) { fValue = val; }
127
128 ClassDef(TPair,0); // Pair TObject*, TObject*
129 };
130
131 typedef TPair TAssoc; // for backward compatibility
132
133
134 // Preventing warnings with -Weffc++ in GCC since it is a false positive for the TMapIter destructor.
135 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
136 #pragma GCC diagnostic push
137 #pragma GCC diagnostic ignored "-Weffc++"
138 #endif
139
140 //////////////////////////////////////////////////////////////////////////
141 // //
142 // TMapIter //
143 // //
144 // Iterator of a map. //
145 // //
146 //////////////////////////////////////////////////////////////////////////
147
148 class TMapIter : public TIterator,
149 public std::iterator<std::bidirectional_iterator_tag,
150 TObject*, std::ptrdiff_t,
151 const TObject**, const TObject*&> {
152
153 private:
154 const TMap *fMap; //map being iterated
155 THashTableIter *fCursor; //current position in map
156 Bool_t fDirection; //iteration direction
157
158 TMapIter() : fMap(0), fCursor(0), fDirection(kIterForward) { }
159
160 public:
161 TMapIter(const TMap *map, Bool_t dir = kIterForward);
162 TMapIter(const TMapIter &iter);
163 ~TMapIter();
164 TIterator &operator=(const TIterator &rhs);
165 TMapIter &operator=(const TMapIter &rhs);
166
167 const TCollection *GetCollection() const { return fMap; }
168 TObject *Next();
169 void Reset();
170 Bool_t operator!=(const TIterator &aIter) const;
171 Bool_t operator!=(const TMapIter &aIter) const;
172 TObject *operator*() const;
173
174 ClassDef(TMapIter,0) //Map iterator
175 };
176
177 #if (__GNUC__ * 10000 + __GNUC_MINOR__ * 100 + __GNUC_PATCHLEVEL__) >= 40600
178 #pragma GCC diagnostic pop
179 #endif
180
181 #endif
182