7fd59977 |
1 | // File: NCollection_DataMap.hxx |
2 | // Created: Thu Apr 24 15:02:53 2002 |
3 | // Author: Alexander KARTOMIN (akm) |
4 | // <akm@opencascade.com> |
5 | |
6 | #ifndef NCollection_DataMap_HeaderFile |
7 | #define NCollection_DataMap_HeaderFile |
8 | |
9 | #include <NCollection_BaseCollection.hxx> |
10 | #include <NCollection_BaseMap.hxx> |
11 | #include <NCollection_TListNode.hxx> |
12 | |
9991c9c2 |
13 | #include <NCollection_DefaultHasher.hxx> |
14 | |
7fd59977 |
15 | #include <Standard_TypeMismatch.hxx> |
16 | #include <Standard_NoSuchObject.hxx> |
17 | |
7fd59977 |
18 | /** |
19 | * Purpose: The DataMap is a Map to store keys with associated |
20 | * Items. See Map from NCollection for a discussion |
21 | * about the number of buckets. |
22 | * |
23 | * The DataMap can be seen as an extended array where |
24 | * the Keys are the indices. For this reason the |
25 | * operator () is defined on DataMap to fetch an Item |
26 | * from a Key. So the following syntax can be used : |
27 | * |
28 | * anItem = aMap(aKey); |
29 | * aMap(aKey) = anItem; |
30 | * |
31 | * This analogy has its limit. aMap(aKey) = anItem |
32 | * can be done only if aKey was previously bound to |
33 | * an item in the map. |
34 | */ |
9991c9c2 |
35 | |
36 | template < class TheKeyType, |
37 | class TheItemType, |
38 | class Hasher = NCollection_DefaultHasher<TheKeyType> > class NCollection_DataMap |
39 | |
7fd59977 |
40 | : public NCollection_BaseCollection<TheItemType>, |
41 | public NCollection_BaseMap |
42 | { |
43 | // **************** Adaptation of the TListNode to the DATAmap |
44 | public: |
45 | class DataMapNode : public NCollection_TListNode<TheItemType> |
46 | { |
47 | public: |
48 | //! Constructor with 'Next' |
49 | DataMapNode (const TheKeyType& theKey, |
50 | const TheItemType& theItem, |
51 | NCollection_ListNode* theNext) : |
52 | NCollection_TListNode<TheItemType> (theItem, theNext) |
53 | { myKey = theKey; } |
54 | //! Key |
55 | const TheKeyType& Key (void) const |
56 | { return myKey; } |
57 | |
58 | //! Static deleter to be passed to BaseList |
59 | static void delNode (NCollection_ListNode * theNode, |
60 | Handle(NCollection_BaseAllocator)& theAl) |
61 | { |
62 | ((DataMapNode *) theNode)->~DataMapNode(); |
63 | theAl->Free(theNode); |
64 | } |
65 | |
66 | private: |
67 | TheKeyType myKey; |
68 | }; |
69 | |
70 | public: |
71 | // **************** Implementation of the Iterator interface. |
72 | class Iterator |
73 | : public NCollection_BaseCollection<TheItemType>::Iterator, |
74 | public NCollection_BaseMap::Iterator |
75 | { |
76 | public: |
77 | //! Empty constructor |
78 | Iterator (void) : |
79 | NCollection_BaseMap::Iterator() {} |
80 | //! Constructor |
81 | Iterator (const NCollection_DataMap& theMap) : |
82 | NCollection_BaseMap::Iterator(theMap) {} |
83 | //! Query if the end of collection is reached by iterator |
84 | virtual Standard_Boolean More(void) const |
85 | { return PMore(); } |
86 | //! Make a step along the collection |
87 | virtual void Next(void) |
88 | { PNext(); } |
89 | //! Value inquiry |
90 | virtual const TheItemType& Value(void) const |
91 | { |
92 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
93 | if (!More()) |
94 | Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Value"); |
95 | #endif |
96 | return ((DataMapNode *) myNode)->Value(); |
97 | } |
98 | //! Value change access |
99 | virtual TheItemType& ChangeValue(void) const |
100 | { |
101 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
102 | if (!More()) |
103 | Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::ChangeValue"); |
104 | #endif |
105 | return ((DataMapNode *) myNode)->ChangeValue(); |
106 | } |
107 | //! Key |
108 | const TheKeyType& Key (void) const |
109 | { |
110 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
111 | if (!More()) |
112 | Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Key"); |
113 | #endif |
114 | return ((DataMapNode *) myNode)->Key(); |
115 | } |
7fd59977 |
116 | }; |
117 | |
118 | public: |
119 | // ---------- PUBLIC METHODS ------------ |
120 | |
121 | //! Constructor |
122 | NCollection_DataMap (const Standard_Integer NbBuckets=1, |
123 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
124 | : NCollection_BaseCollection<TheItemType>(theAllocator), |
125 | NCollection_BaseMap (NbBuckets, Standard_True) {} |
126 | |
127 | //! Copy constructor |
128 | NCollection_DataMap (const NCollection_DataMap& theOther) |
129 | : NCollection_BaseCollection<TheItemType>(theOther.myAllocator), |
130 | NCollection_BaseMap (theOther.NbBuckets(), Standard_True) |
131 | { *this = theOther; } |
132 | |
133 | //! Assign another collection |
134 | virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther) |
135 | { |
136 | if (this == &theOther) |
137 | return; |
138 | Standard_TypeMismatch::Raise ("NCollection_DataMap::Assign impossible"); |
139 | } |
140 | |
141 | //! = another map |
142 | NCollection_DataMap& operator= (const NCollection_DataMap& theOther) |
143 | { |
144 | if (this == &theOther) |
145 | return *this; |
146 | |
147 | Clear(theOther.myAllocator); |
148 | ReSize (theOther.Extent()-1); |
149 | Iterator anIter(theOther); |
150 | for (; anIter.More(); anIter.Next()) |
151 | Bind (anIter.Key(), anIter.Value()); |
152 | return *this; |
153 | } |
154 | |
155 | //! ReSize |
156 | void ReSize (const Standard_Integer N) |
157 | { |
158 | DataMapNode** newdata = NULL; |
159 | DataMapNode** dummy = NULL; |
160 | Standard_Integer newBuck; |
161 | if (BeginResize (N, newBuck, |
162 | (NCollection_ListNode**&)newdata, |
163 | (NCollection_ListNode**&)dummy, |
164 | this->myAllocator)) |
165 | { |
166 | if (myData1) |
167 | { |
168 | DataMapNode** olddata = (DataMapNode**) myData1; |
169 | DataMapNode *p, *q; |
170 | Standard_Integer i,k; |
171 | for (i = 0; i <= NbBuckets(); i++) |
172 | { |
173 | if (olddata[i]) |
174 | { |
175 | p = olddata[i]; |
176 | while (p) |
177 | { |
9991c9c2 |
178 | k = Hasher::HashCode(p->Key(),newBuck); |
7fd59977 |
179 | q = (DataMapNode*) p->Next(); |
180 | p->Next() = newdata[k]; |
181 | newdata[k] = p; |
182 | p = q; |
183 | } |
184 | } |
185 | } |
186 | } |
187 | EndResize(N,newBuck, |
188 | (NCollection_ListNode**&)newdata, |
189 | (NCollection_ListNode**&)dummy, |
190 | this->myAllocator); |
191 | } |
192 | } |
193 | |
194 | //! Bind |
195 | Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem) |
196 | { |
197 | if (Resizable()) |
198 | ReSize(Extent()); |
199 | DataMapNode** data = (DataMapNode**)myData1; |
9991c9c2 |
200 | Standard_Integer k = Hasher::HashCode (theKey, NbBuckets()); |
7fd59977 |
201 | DataMapNode* p = data[k]; |
202 | while (p) |
203 | { |
9991c9c2 |
204 | if (Hasher::IsEqual(p->Key(), theKey)) |
7fd59977 |
205 | { |
206 | p->ChangeValue() = theItem; |
207 | return Standard_False; |
208 | } |
209 | p = (DataMapNode *) p->Next(); |
210 | } |
211 | data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]); |
212 | Increment(); |
213 | return Standard_True; |
214 | } |
215 | |
216 | //! IsBound |
217 | Standard_Boolean IsBound(const TheKeyType& K) const |
218 | { |
219 | if (IsEmpty()) |
220 | return Standard_False; |
221 | DataMapNode** data = (DataMapNode**) myData1; |
9991c9c2 |
222 | DataMapNode* p = data[Hasher::HashCode(K,NbBuckets())]; |
7fd59977 |
223 | while (p) |
224 | { |
9991c9c2 |
225 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
226 | return Standard_True; |
227 | p = (DataMapNode *) p->Next(); |
228 | } |
229 | return Standard_False; |
230 | } |
231 | |
232 | //! UnBind |
233 | Standard_Boolean UnBind(const TheKeyType& K) |
234 | { |
235 | if (IsEmpty()) |
236 | return Standard_False; |
237 | DataMapNode** data = (DataMapNode**) myData1; |
9991c9c2 |
238 | Standard_Integer k = Hasher::HashCode(K,NbBuckets()); |
7fd59977 |
239 | DataMapNode* p = data[k]; |
240 | DataMapNode* q = NULL; |
241 | while (p) |
242 | { |
9991c9c2 |
243 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
244 | { |
245 | Decrement(); |
246 | if (q) |
247 | q->Next() = p->Next(); |
248 | else |
249 | data[k] = (DataMapNode*) p->Next(); |
250 | p->~DataMapNode(); |
251 | this->myAllocator->Free(p); |
252 | return Standard_True; |
253 | } |
254 | q = p; |
255 | p = (DataMapNode*) p->Next(); |
256 | } |
257 | return Standard_False; |
258 | } |
259 | |
260 | //! Find |
261 | const TheItemType& Find(const TheKeyType& theKey) const |
262 | { |
263 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
264 | if (IsEmpty()) |
265 | Standard_NoSuchObject::Raise ("NCollection_DataMap::Find"); |
266 | #endif |
9991c9c2 |
267 | DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())]; |
7fd59977 |
268 | while (p) |
269 | { |
9991c9c2 |
270 | if (Hasher::IsEqual(p->Key(),theKey)) |
7fd59977 |
271 | return p->Value(); |
272 | p = (DataMapNode*) p->Next(); |
273 | } |
274 | Standard_NoSuchObject::Raise("NCollection_DataMap::Find"); |
275 | return p->Value(); // This for compiler |
276 | } |
277 | |
278 | //! operator () |
279 | const TheItemType& operator() (const TheKeyType& theKey) const |
280 | { return Find(theKey); } |
281 | |
282 | //! ChangeFind |
283 | TheItemType& ChangeFind (const TheKeyType& theKey) |
284 | { |
285 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
286 | if (IsEmpty()) |
287 | Standard_NoSuchObject::Raise ("NCollection_DataMap::Find"); |
288 | #endif |
9991c9c2 |
289 | DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())]; |
7fd59977 |
290 | while (p) |
291 | { |
9991c9c2 |
292 | if (Hasher::IsEqual(p->Key(),theKey)) |
7fd59977 |
293 | return p->ChangeValue(); |
294 | p = (DataMapNode*) p->Next(); |
295 | } |
296 | Standard_NoSuchObject::Raise("NCollection_DataMap::Find"); |
297 | return p->ChangeValue(); // This for compiler |
298 | } |
299 | |
300 | //! operator () |
301 | TheItemType& operator() (const TheKeyType& theKey) |
302 | { return ChangeFind(theKey); } |
303 | |
304 | //! Clear data. If doReleaseMemory is false then the table of |
305 | //! buckets is not released and will be reused. |
306 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
307 | { Destroy (DataMapNode::delNode, this->myAllocator, doReleaseMemory); } |
308 | |
309 | //! Clear data and reset allocator |
310 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
311 | { |
312 | Clear(); |
313 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
314 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
315 | } |
316 | |
317 | //! Destructor |
318 | ~NCollection_DataMap (void) |
319 | { Clear(); } |
320 | |
321 | //! Size |
322 | virtual Standard_Integer Size(void) const |
323 | { return Extent(); } |
324 | |
325 | private: |
326 | // ----------- PRIVATE METHODS ----------- |
327 | |
328 | //! Creates Iterator for use on BaseCollection |
329 | virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator& |
330 | CreateIterator(void) const |
331 | { return *(new (this->IterAllocator()) Iterator(*this)); } |
332 | |
333 | }; |
334 | |
7fd59977 |
335 | #endif |
9991c9c2 |
336 | |