b311480e |
1 | // Created on: 2002-04-24 |
2 | // Created by: Alexander KARTOMIN (akm) |
973c2be1 |
3 | // Copyright (c) 2002-2014 OPEN CASCADE SAS |
b311480e |
4 | // |
973c2be1 |
5 | // This file is part of Open CASCADE Technology software library. |
b311480e |
6 | // |
d5f74e42 |
7 | // This library is free software; you can redistribute it and/or modify it under |
8 | // the terms of the GNU Lesser General Public License version 2.1 as published |
973c2be1 |
9 | // by the Free Software Foundation, with special exception defined in the file |
10 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT |
11 | // distribution for complete text of the license and disclaimer of any warranty. |
b311480e |
12 | // |
973c2be1 |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
b311480e |
15 | |
7fd59977 |
16 | #ifndef NCollection_DataMap_HeaderFile |
17 | #define NCollection_DataMap_HeaderFile |
18 | |
7fd59977 |
19 | #include <NCollection_BaseMap.hxx> |
20 | #include <NCollection_TListNode.hxx> |
79a35943 |
21 | #include <NCollection_StlIterator.hxx> |
9991c9c2 |
22 | #include <NCollection_DefaultHasher.hxx> |
23 | |
7fd59977 |
24 | #include <Standard_TypeMismatch.hxx> |
25 | #include <Standard_NoSuchObject.hxx> |
26 | |
7fd59977 |
27 | /** |
28 | * Purpose: The DataMap is a Map to store keys with associated |
29 | * Items. See Map from NCollection for a discussion |
30 | * about the number of buckets. |
31 | * |
32 | * The DataMap can be seen as an extended array where |
33 | * the Keys are the indices. For this reason the |
34 | * operator () is defined on DataMap to fetch an Item |
35 | * from a Key. So the following syntax can be used : |
36 | * |
37 | * anItem = aMap(aKey); |
38 | * aMap(aKey) = anItem; |
39 | * |
40 | * This analogy has its limit. aMap(aKey) = anItem |
41 | * can be done only if aKey was previously bound to |
42 | * an item in the map. |
43 | */ |
9991c9c2 |
44 | |
45 | template < class TheKeyType, |
46 | class TheItemType, |
ddf2fe8e |
47 | class Hasher = NCollection_DefaultHasher<TheKeyType> > |
48 | class NCollection_DataMap : public NCollection_BaseMap |
7fd59977 |
49 | { |
50 | // **************** Adaptation of the TListNode to the DATAmap |
51 | public: |
52 | class DataMapNode : public NCollection_TListNode<TheItemType> |
53 | { |
54 | public: |
55 | //! Constructor with 'Next' |
56 | DataMapNode (const TheKeyType& theKey, |
57 | const TheItemType& theItem, |
58 | NCollection_ListNode* theNext) : |
e3a6386d |
59 | NCollection_TListNode<TheItemType> (theItem, theNext), |
60 | myKey(theKey) |
61 | {} |
62 | |
7fd59977 |
63 | //! Key |
64 | const TheKeyType& Key (void) const |
65 | { return myKey; } |
66 | |
ddf2fe8e |
67 | //! Static deleter to be passed to BaseMap |
7fd59977 |
68 | static void delNode (NCollection_ListNode * theNode, |
69 | Handle(NCollection_BaseAllocator)& theAl) |
70 | { |
71 | ((DataMapNode *) theNode)->~DataMapNode(); |
72 | theAl->Free(theNode); |
73 | } |
74 | |
75 | private: |
76 | TheKeyType myKey; |
77 | }; |
78 | |
79 | public: |
80 | // **************** Implementation of the Iterator interface. |
ddf2fe8e |
81 | class Iterator : public NCollection_BaseMap::Iterator |
7fd59977 |
82 | { |
83 | public: |
84 | //! Empty constructor |
85 | Iterator (void) : |
86 | NCollection_BaseMap::Iterator() {} |
87 | //! Constructor |
88 | Iterator (const NCollection_DataMap& theMap) : |
89 | NCollection_BaseMap::Iterator(theMap) {} |
90 | //! Query if the end of collection is reached by iterator |
ddf2fe8e |
91 | Standard_Boolean More(void) const |
7fd59977 |
92 | { return PMore(); } |
93 | //! Make a step along the collection |
ddf2fe8e |
94 | void Next(void) |
7fd59977 |
95 | { PNext(); } |
96 | //! Value inquiry |
ddf2fe8e |
97 | const TheItemType& Value(void) const |
7fd59977 |
98 | { |
e3a6386d |
99 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Value"); |
7fd59977 |
100 | return ((DataMapNode *) myNode)->Value(); |
101 | } |
102 | //! Value change access |
ddf2fe8e |
103 | TheItemType& ChangeValue(void) const |
7fd59977 |
104 | { |
e3a6386d |
105 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::ChangeValue"); |
7fd59977 |
106 | return ((DataMapNode *) myNode)->ChangeValue(); |
107 | } |
108 | //! Key |
109 | const TheKeyType& Key (void) const |
110 | { |
e3a6386d |
111 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Key"); |
7fd59977 |
112 | return ((DataMapNode *) myNode)->Key(); |
113 | } |
7fd59977 |
114 | }; |
79a35943 |
115 | |
116 | //! Shorthand for a regular iterator type. |
117 | typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator; |
118 | |
119 | //! Shorthand for a constant iterator type. |
120 | typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator; |
121 | |
122 | //! Returns an iterator pointing to the first element in the map. |
123 | iterator begin() const { return Iterator (*this); } |
124 | |
125 | //! Returns an iterator referring to the past-the-end element in the map. |
126 | iterator end() const { return Iterator(); } |
127 | |
128 | //! Returns a const iterator pointing to the first element in the map. |
129 | const_iterator cbegin() const { return Iterator (*this); } |
130 | |
131 | //! Returns a const iterator referring to the past-the-end element in the map. |
132 | const_iterator cend() const { return Iterator(); } |
7fd59977 |
133 | |
134 | public: |
135 | // ---------- PUBLIC METHODS ------------ |
136 | |
137 | //! Constructor |
138 | NCollection_DataMap (const Standard_Integer NbBuckets=1, |
139 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
ddf2fe8e |
140 | : NCollection_BaseMap (NbBuckets, Standard_True, theAllocator) {} |
7fd59977 |
141 | |
142 | //! Copy constructor |
143 | NCollection_DataMap (const NCollection_DataMap& theOther) |
ddf2fe8e |
144 | : NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator) |
7fd59977 |
145 | { *this = theOther; } |
146 | |
ab2db9a5 |
147 | //! Exchange the content of two maps without re-allocations. |
148 | //! Notice that allocators will be swapped as well! |
149 | void Exchange (NCollection_DataMap& theOther) |
150 | { |
ddf2fe8e |
151 | this->exchangeMapsData (theOther); |
ab2db9a5 |
152 | } |
153 | |
5e452c37 |
154 | //! Assignment. |
155 | //! This method does not change the internal allocator. |
ddf2fe8e |
156 | NCollection_DataMap& Assign (const NCollection_DataMap& theOther) |
7fd59977 |
157 | { |
158 | if (this == &theOther) |
159 | return *this; |
160 | |
5e452c37 |
161 | Clear(); |
7fd59977 |
162 | ReSize (theOther.Extent()-1); |
163 | Iterator anIter(theOther); |
164 | for (; anIter.More(); anIter.Next()) |
165 | Bind (anIter.Key(), anIter.Value()); |
166 | return *this; |
167 | } |
168 | |
ddf2fe8e |
169 | //! Assignment operator |
170 | NCollection_DataMap& operator= (const NCollection_DataMap& theOther) |
171 | { |
172 | return Assign (theOther); |
173 | } |
174 | |
7fd59977 |
175 | //! ReSize |
176 | void ReSize (const Standard_Integer N) |
177 | { |
fd03ee4b |
178 | NCollection_ListNode** newdata = NULL; |
179 | NCollection_ListNode** dummy = NULL; |
7fd59977 |
180 | Standard_Integer newBuck; |
ddf2fe8e |
181 | if (BeginResize (N, newBuck, newdata, dummy)) |
7fd59977 |
182 | { |
183 | if (myData1) |
184 | { |
185 | DataMapNode** olddata = (DataMapNode**) myData1; |
186 | DataMapNode *p, *q; |
187 | Standard_Integer i,k; |
188 | for (i = 0; i <= NbBuckets(); i++) |
189 | { |
190 | if (olddata[i]) |
191 | { |
192 | p = olddata[i]; |
193 | while (p) |
194 | { |
9991c9c2 |
195 | k = Hasher::HashCode(p->Key(),newBuck); |
7fd59977 |
196 | q = (DataMapNode*) p->Next(); |
197 | p->Next() = newdata[k]; |
198 | newdata[k] = p; |
199 | p = q; |
200 | } |
201 | } |
202 | } |
203 | } |
ddf2fe8e |
204 | EndResize (N, newBuck, newdata, dummy); |
7fd59977 |
205 | } |
206 | } |
207 | |
9df7f429 |
208 | //! Bind binds Item to Key in map. Returns Standard_True if Key was not |
209 | //! exist in the map. If the Key was already bound, the Item will be rebinded |
210 | //! and Standard_False will be returned. |
7fd59977 |
211 | Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem) |
212 | { |
213 | if (Resizable()) |
214 | ReSize(Extent()); |
215 | DataMapNode** data = (DataMapNode**)myData1; |
9991c9c2 |
216 | Standard_Integer k = Hasher::HashCode (theKey, NbBuckets()); |
7fd59977 |
217 | DataMapNode* p = data[k]; |
218 | while (p) |
219 | { |
9991c9c2 |
220 | if (Hasher::IsEqual(p->Key(), theKey)) |
7fd59977 |
221 | { |
222 | p->ChangeValue() = theItem; |
223 | return Standard_False; |
224 | } |
225 | p = (DataMapNode *) p->Next(); |
226 | } |
227 | data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]); |
228 | Increment(); |
229 | return Standard_True; |
230 | } |
231 | |
9df7f429 |
232 | //! Bound binds Item to Key in map. Returns modifiable Item |
233 | TheItemType* Bound (const TheKeyType& theKey, const TheItemType& theItem) |
7fd59977 |
234 | { |
9df7f429 |
235 | if (Resizable()) |
236 | ReSize(Extent()); |
237 | DataMapNode** data = (DataMapNode**)myData1; |
238 | Standard_Integer k = Hasher::HashCode (theKey, NbBuckets()); |
239 | DataMapNode* p = data[k]; |
240 | while (p) |
7fd59977 |
241 | { |
9df7f429 |
242 | if (Hasher::IsEqual(p->Key(), theKey)) |
243 | { |
244 | p->ChangeValue() = theItem; |
245 | return &p->ChangeValue(); |
246 | } |
247 | p = (DataMapNode*)p->Next(); |
7fd59977 |
248 | } |
9df7f429 |
249 | data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]); |
250 | Increment(); |
251 | return &data[k]->ChangeValue(); |
7fd59977 |
252 | } |
253 | |
9df7f429 |
254 | //! IsBound |
255 | Standard_Boolean IsBound(const TheKeyType& K) const |
256 | { |
257 | DataMapNode* p; |
258 | return lookup(K, p); |
259 | } |
260 | |
261 | //! UnBind removes Item Key pair from map |
7fd59977 |
262 | Standard_Boolean UnBind(const TheKeyType& K) |
263 | { |
264 | if (IsEmpty()) |
265 | return Standard_False; |
266 | DataMapNode** data = (DataMapNode**) myData1; |
9991c9c2 |
267 | Standard_Integer k = Hasher::HashCode(K,NbBuckets()); |
7fd59977 |
268 | DataMapNode* p = data[k]; |
269 | DataMapNode* q = NULL; |
270 | while (p) |
271 | { |
9991c9c2 |
272 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
273 | { |
274 | Decrement(); |
275 | if (q) |
276 | q->Next() = p->Next(); |
277 | else |
278 | data[k] = (DataMapNode*) p->Next(); |
279 | p->~DataMapNode(); |
280 | this->myAllocator->Free(p); |
281 | return Standard_True; |
282 | } |
283 | q = p; |
284 | p = (DataMapNode*) p->Next(); |
285 | } |
286 | return Standard_False; |
287 | } |
288 | |
9df7f429 |
289 | //! Seek returns pointer to Item by Key. Returns |
290 | //! NULL is Key was not bound. |
291 | const TheItemType* Seek(const TheKeyType& theKey) const |
292 | { |
293 | DataMapNode* p = 0; |
294 | if (!lookup(theKey, p)) |
295 | return 0L; |
296 | return &p->Value(); |
297 | } |
298 | |
299 | //! Find returns the Item for Key. Raises if Key was not bound |
7fd59977 |
300 | const TheItemType& Find(const TheKeyType& theKey) const |
301 | { |
9df7f429 |
302 | DataMapNode* p = 0; |
303 | if (!lookup(theKey, p)) |
304 | Standard_NoSuchObject::Raise("NCollection_DataMap::Find"); |
305 | return p->Value(); |
7fd59977 |
306 | } |
307 | |
9df7f429 |
308 | //! Find Item for key with copying. |
a174a3c5 |
309 | //! @return true if key was found |
310 | Standard_Boolean Find (const TheKeyType& theKey, |
311 | TheItemType& theValue) const |
312 | { |
9df7f429 |
313 | DataMapNode* p = 0; |
314 | if (!lookup(theKey, p)) |
a174a3c5 |
315 | return Standard_False; |
a174a3c5 |
316 | |
9df7f429 |
317 | theValue = p->Value(); |
318 | return Standard_True; |
a174a3c5 |
319 | } |
320 | |
7fd59977 |
321 | //! operator () |
322 | const TheItemType& operator() (const TheKeyType& theKey) const |
323 | { return Find(theKey); } |
324 | |
9df7f429 |
325 | //! ChangeSeek returns modifiable pointer to Item by Key. Returns |
326 | //! NULL is Key was not bound. |
327 | TheItemType* ChangeSeek(const TheKeyType& theKey) |
328 | { |
329 | DataMapNode* p = 0; |
330 | if (!lookup(theKey, p)) |
331 | return 0L; |
332 | return &p->ChangeValue(); |
333 | } |
334 | |
335 | //! ChangeFind returns mofifiable Item by Key. Raises if Key was not bound |
7fd59977 |
336 | TheItemType& ChangeFind (const TheKeyType& theKey) |
337 | { |
9df7f429 |
338 | DataMapNode* p = 0; |
339 | if (!lookup(theKey, p)) |
340 | Standard_NoSuchObject::Raise("NCollection_DataMap::Find"); |
341 | return p->ChangeValue(); |
7fd59977 |
342 | } |
343 | |
344 | //! operator () |
345 | TheItemType& operator() (const TheKeyType& theKey) |
346 | { return ChangeFind(theKey); } |
347 | |
348 | //! Clear data. If doReleaseMemory is false then the table of |
349 | //! buckets is not released and will be reused. |
350 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
ddf2fe8e |
351 | { Destroy (DataMapNode::delNode, doReleaseMemory); } |
7fd59977 |
352 | |
353 | //! Clear data and reset allocator |
354 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
355 | { |
356 | Clear(); |
357 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
358 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
359 | } |
360 | |
361 | //! Destructor |
362 | ~NCollection_DataMap (void) |
363 | { Clear(); } |
364 | |
365 | //! Size |
ddf2fe8e |
366 | Standard_Integer Size(void) const |
7fd59977 |
367 | { return Extent(); } |
9df7f429 |
368 | |
369 | |
370 | protected: |
371 | // ---------- PROTECTED METHODS ---------- |
372 | //! Lookup for particular key in map. Returns true if key is found and |
373 | //! thepNode points to binded node. Returns false if key is not found, |
374 | //! thehNode value is this case is not usable. |
375 | Standard_Boolean lookup(const TheKeyType& theKey,DataMapNode*& thepNode) const |
376 | { |
377 | if (IsEmpty()) |
378 | return Standard_False; // Not found |
379 | for (thepNode = (DataMapNode*)myData1[Hasher::HashCode(theKey, NbBuckets())]; |
380 | thepNode; thepNode = (DataMapNode*)thepNode->Next()) |
381 | { |
382 | if (Hasher::IsEqual(thepNode->Key(), theKey)) |
383 | return Standard_True; |
384 | } |
385 | return Standard_False; // Not found |
386 | } |
387 | |
7fd59977 |
388 | }; |
389 | |
7fd59977 |
390 | #endif |
9991c9c2 |
391 | |