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. |
7fd59977 |
15 | |
16 | #ifndef NCollection_IndexedDataMap_HeaderFile |
17 | #define NCollection_IndexedDataMap_HeaderFile |
18 | |
7fd59977 |
19 | #include <NCollection_BaseMap.hxx> |
20 | #include <NCollection_TListNode.hxx> |
21 | #include <Standard_TypeMismatch.hxx> |
22 | #include <Standard_NoSuchObject.hxx> |
79a35943 |
23 | #include <NCollection_StlIterator.hxx> |
9991c9c2 |
24 | #include <NCollection_DefaultHasher.hxx> |
25 | |
7fd59977 |
26 | #include <Standard_OutOfRange.hxx> |
1103eb60 |
27 | #include <utility> |
7fd59977 |
28 | |
7fd59977 |
29 | /** |
30 | * Purpose: An indexed map is used to store keys and to bind |
31 | * an index to them. Each new key stored in the map |
32 | * gets an index. Index are incremented as keys are |
33 | * stored in the map. A key can be found by the index |
34 | * and an index by the key. No key but the last can |
35 | * be removed so the indices are in the range 1.. |
36 | * Extent. An Item is stored with each key. |
37 | * |
38 | * This class is similar to IndexedMap from |
39 | * NCollection with the Item as a new feature. Note |
40 | * the important difference on the operator (). In |
41 | * the IndexedMap this operator returns the Key. In |
42 | * the IndexedDataMap this operator returns the Item. |
43 | * |
44 | * See the class Map from NCollection for a |
45 | * discussion about the number of buckets. |
46 | */ |
9991c9c2 |
47 | |
48 | template < class TheKeyType, |
49 | class TheItemType, |
50 | class Hasher = NCollection_DefaultHasher<TheKeyType> > |
ddf2fe8e |
51 | class NCollection_IndexedDataMap : public NCollection_BaseMap |
7fd59977 |
52 | { |
3f5aa017 |
53 | public: |
54 | //! STL-compliant typedef for key type |
55 | typedef TheKeyType key_type; |
56 | //! STL-compliant typedef for value type |
57 | typedef TheItemType value_type; |
1103eb60 |
58 | typedef Hasher hasher; |
3f5aa017 |
59 | |
60 | private: |
7fd59977 |
61 | //! Adaptation of the TListNode to the INDEXEDDatamap |
7fd59977 |
62 | class IndexedDataMapNode : public NCollection_TListNode<TheItemType> |
63 | { |
64 | public: |
65 | //! Constructor with 'Next' |
66 | IndexedDataMapNode (const TheKeyType& theKey1, |
510cb852 |
67 | const Standard_Integer theIndex, |
7fd59977 |
68 | const TheItemType& theItem, |
510cb852 |
69 | NCollection_ListNode* theNext1) |
70 | : NCollection_TListNode<TheItemType>(theItem,theNext1), |
71 | myKey1 (theKey1), |
72 | myIndex (theIndex) |
1103eb60 |
73 | {} |
74 | //! Constructor with 'Next' |
75 | IndexedDataMapNode (TheKeyType&& theKey1, |
76 | const Standard_Integer theIndex, |
77 | const TheItemType& theItem, |
78 | NCollection_ListNode* theNext1) |
79 | : NCollection_TListNode<TheItemType>(theItem,theNext1), |
80 | myKey1 (std::forward<TheKeyType>(theKey1)), |
81 | myIndex (theIndex) |
82 | {} |
83 | //! Constructor with 'Next' |
84 | IndexedDataMapNode (const TheKeyType& theKey1, |
85 | const Standard_Integer theIndex, |
86 | TheItemType&& theItem, |
87 | NCollection_ListNode* theNext1) |
88 | : NCollection_TListNode<TheItemType>(std::forward<TheItemType>(theItem),theNext1), |
89 | myKey1 (theKey1), |
90 | myIndex (theIndex) |
91 | {} |
92 | //! Constructor with 'Next' |
93 | IndexedDataMapNode (TheKeyType&& theKey1, |
94 | const Standard_Integer theIndex, |
95 | TheItemType&& theItem, |
96 | NCollection_ListNode* theNext1) |
97 | : NCollection_TListNode<TheItemType>(std::forward<TheItemType>(theItem),theNext1), |
98 | myKey1 (std::forward<TheKeyType>(theKey1)), |
99 | myIndex (theIndex) |
100 | {} |
7fd59977 |
101 | //! Key1 |
510cb852 |
102 | TheKeyType& Key1() { return myKey1; } |
103 | //! Index |
104 | Standard_Integer& Index() { return myIndex; } |
105 | |
7fd59977 |
106 | //! Static deleter to be passed to BaseList |
107 | static void delNode (NCollection_ListNode * theNode, |
108 | Handle(NCollection_BaseAllocator)& theAl) |
109 | { |
110 | ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode(); |
111 | theAl->Free(theNode); |
112 | } |
113 | private: |
510cb852 |
114 | TheKeyType myKey1; |
115 | Standard_Integer myIndex; |
7fd59977 |
116 | }; |
117 | |
118 | public: |
119 | //! Implementation of the Iterator interface. |
ddf2fe8e |
120 | class Iterator |
7fd59977 |
121 | { |
122 | public: |
123 | //! Empty constructor |
510cb852 |
124 | Iterator() |
125 | : myMap (NULL), |
510cb852 |
126 | myIndex (0) {} |
eb62cbc4 |
127 | |
7fd59977 |
128 | //! Constructor |
ad3217cd |
129 | Iterator (const NCollection_IndexedDataMap& theMap) |
eb62cbc4 |
130 | : myMap ((NCollection_IndexedDataMap*)&theMap), |
ad3217cd |
131 | myIndex (1) {} |
eb62cbc4 |
132 | |
7fd59977 |
133 | //! Query if the end of collection is reached by iterator |
ddf2fe8e |
134 | Standard_Boolean More(void) const |
79a35943 |
135 | { return (myMap != NULL) && (myIndex <= myMap->Extent()); } |
eb62cbc4 |
136 | |
7fd59977 |
137 | //! Make a step along the collection |
ddf2fe8e |
138 | void Next(void) |
eb62cbc4 |
139 | { ++myIndex; } |
140 | |
7fd59977 |
141 | //! Value access |
ddf2fe8e |
142 | const TheItemType& Value(void) const |
7fd59977 |
143 | { |
e3a6386d |
144 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Value"); |
eb62cbc4 |
145 | return myMap->FindFromIndex(myIndex); |
7fd59977 |
146 | } |
eb62cbc4 |
147 | |
7fd59977 |
148 | //! ChangeValue access |
ddf2fe8e |
149 | TheItemType& ChangeValue(void) const |
7fd59977 |
150 | { |
e3a6386d |
151 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::ChangeValue"); |
eb62cbc4 |
152 | return myMap->ChangeFromIndex(myIndex); |
ad3217cd |
153 | } |
eb62cbc4 |
154 | |
ad3217cd |
155 | //! Key |
156 | const TheKeyType& Key() const |
157 | { |
e3a6386d |
158 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Key"); |
eb62cbc4 |
159 | return myMap->FindKey(myIndex); |
7fd59977 |
160 | } |
eb62cbc4 |
161 | |
79a35943 |
162 | //! Performs comparison of two iterators. |
ddf2fe8e |
163 | Standard_Boolean IsEqual (const Iterator& theOther) const |
79a35943 |
164 | { |
165 | return myMap == theOther.myMap && |
79a35943 |
166 | myIndex == theOther.myIndex; |
167 | } |
eb62cbc4 |
168 | |
7fd59977 |
169 | private: |
eb62cbc4 |
170 | NCollection_IndexedDataMap* myMap; //!< Pointer to current node |
ad3217cd |
171 | Standard_Integer myIndex; //!< Current index |
7fd59977 |
172 | }; |
173 | |
79a35943 |
174 | //! Shorthand for a regular iterator type. |
175 | typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator; |
176 | |
177 | //! Shorthand for a constant iterator type. |
178 | typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator; |
179 | |
180 | //! Returns an iterator pointing to the first element in the map. |
181 | iterator begin() const { return Iterator (*this); } |
182 | |
183 | //! Returns an iterator referring to the past-the-end element in the map. |
184 | iterator end() const { return Iterator(); } |
185 | |
186 | //! Returns a const iterator pointing to the first element in the map. |
187 | const_iterator cbegin() const { return Iterator (*this); } |
188 | |
189 | //! Returns a const iterator referring to the past-the-end element in the map. |
190 | const_iterator cend() const { return Iterator(); } |
191 | |
7fd59977 |
192 | public: |
193 | // ---------- PUBLIC METHODS ------------ |
194 | |
b6a0525b |
195 | //! Empty constructor. |
1103eb60 |
196 | NCollection_IndexedDataMap() : NCollection_BaseMap (1, true, Handle(NCollection_BaseAllocator)()) {} |
b6a0525b |
197 | |
7fd59977 |
198 | //! Constructor |
b6a0525b |
199 | explicit NCollection_IndexedDataMap (const Standard_Integer theNbBuckets, |
200 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
1103eb60 |
201 | : NCollection_BaseMap (theNbBuckets, true, theAllocator) {} |
7fd59977 |
202 | |
203 | //! Copy constructor |
204 | NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther) |
1103eb60 |
205 | : NCollection_BaseMap (theOther.NbBuckets(), true, theOther.myAllocator) |
7fd59977 |
206 | { *this = theOther; } |
207 | |
1103eb60 |
208 | //! Move constructor |
209 | NCollection_IndexedDataMap(NCollection_IndexedDataMap&& theOther) noexcept : |
210 | NCollection_BaseMap(std::forward<NCollection_BaseMap>(theOther)) |
211 | {} |
212 | |
ab2db9a5 |
213 | //! Exchange the content of two maps without re-allocations. |
214 | //! Notice that allocators will be swapped as well! |
215 | void Exchange (NCollection_IndexedDataMap& theOther) |
216 | { |
ddf2fe8e |
217 | this->exchangeMapsData (theOther); |
ab2db9a5 |
218 | } |
219 | |
5e452c37 |
220 | //! Assignment. |
221 | //! This method does not change the internal allocator. |
ddf2fe8e |
222 | NCollection_IndexedDataMap& Assign (const NCollection_IndexedDataMap& theOther) |
7fd59977 |
223 | { |
224 | if (this == &theOther) |
225 | return *this; |
226 | |
5e452c37 |
227 | Clear(); |
229add78 |
228 | Standard_Integer anExt = theOther.Extent(); |
229 | if (anExt) |
7fd59977 |
230 | { |
229add78 |
231 | ReSize (anExt-1); //mySize is same after resize |
232 | for (Standard_Integer anIndexIter = 1; anIndexIter <= anExt; ++anIndexIter) |
233 | { |
234 | const TheKeyType& aKey1 = theOther.FindKey (anIndexIter); |
235 | const TheItemType& anItem = theOther.FindFromIndex(anIndexIter); |
1103eb60 |
236 | const size_t iK1 = HashCode (aKey1, NbBuckets()); |
229add78 |
237 | IndexedDataMapNode* pNode = new (this->myAllocator) IndexedDataMapNode (aKey1, anIndexIter, anItem, myData1[iK1]); |
238 | myData1[iK1] = pNode; |
239 | myData2[anIndexIter - 1] = pNode; |
240 | Increment(); |
241 | } |
7fd59977 |
242 | } |
243 | return *this; |
244 | } |
245 | |
ddf2fe8e |
246 | //! Assignment operator |
247 | NCollection_IndexedDataMap& operator= (const NCollection_IndexedDataMap& theOther) |
5e452c37 |
248 | { |
ddf2fe8e |
249 | return Assign (theOther); |
250 | } |
251 | |
1103eb60 |
252 | //! Move operator |
253 | NCollection_IndexedDataMap& operator= (NCollection_IndexedDataMap&& theOther) noexcept |
254 | { |
255 | if (this == &theOther) |
256 | return *this; |
257 | exchangeMapsData(theOther); |
258 | return *this; |
259 | } |
260 | |
7fd59977 |
261 | //! ReSize |
262 | void ReSize (const Standard_Integer N) |
263 | { |
fd03ee4b |
264 | NCollection_ListNode** ppNewData1 = NULL; |
265 | NCollection_ListNode** ppNewData2 = NULL; |
7fd59977 |
266 | Standard_Integer newBuck; |
ddf2fe8e |
267 | if (BeginResize (N, newBuck, ppNewData1, ppNewData2)) |
7fd59977 |
268 | { |
269 | if (myData1) |
270 | { |
510cb852 |
271 | for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter) |
7fd59977 |
272 | { |
510cb852 |
273 | if (myData1[aBucketIter]) |
7fd59977 |
274 | { |
510cb852 |
275 | IndexedDataMapNode* p = (IndexedDataMapNode *) myData1[aBucketIter]; |
7fd59977 |
276 | while (p) |
277 | { |
1103eb60 |
278 | const size_t iK1 = HashCode (p->Key1(), newBuck); |
510cb852 |
279 | IndexedDataMapNode* q = (IndexedDataMapNode* )p->Next(); |
280 | p->Next() = ppNewData1[iK1]; |
7fd59977 |
281 | ppNewData1[iK1] = p; |
7fd59977 |
282 | p = q; |
283 | } |
284 | } |
285 | } |
286 | } |
1103eb60 |
287 | EndResize (N, newBuck, ppNewData1, (NCollection_ListNode**) |
288 | Standard::Reallocate(myData2, (newBuck + 1) * sizeof(NCollection_ListNode*))); |
7fd59977 |
289 | } |
290 | } |
291 | |
94807a7d |
292 | //! Returns the Index of already bound Key or appends new Key with specified Item value. |
293 | //! @param theKey1 Key to search (and to bind, if it was not bound already) |
294 | //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound |
295 | //! @return index of Key |
7fd59977 |
296 | Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem) |
297 | { |
510cb852 |
298 | if (Resizable()) |
299 | { |
7fd59977 |
300 | ReSize(Extent()); |
510cb852 |
301 | } |
1103eb60 |
302 | IndexedDataMapNode* aNode; |
303 | size_t aHash; |
304 | if (lookup(theKey1, aNode, aHash)) |
305 | { |
306 | return aNode->Index(); |
307 | } |
308 | const Standard_Integer aNewIndex = Increment(); |
309 | aNode = new (this->myAllocator) IndexedDataMapNode (theKey1, aNewIndex, theItem, myData1[aHash]); |
310 | myData1[aHash] = aNode; |
311 | myData2[aNewIndex - 1] = aNode; |
312 | return aNewIndex; |
313 | } |
510cb852 |
314 | |
1103eb60 |
315 | //! Returns the Index of already bound Key or appends new Key with specified Item value. |
316 | //! @param theKey1 Key to search (and to bind, if it was not bound already) |
317 | //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound |
318 | //! @return index of Key |
319 | Standard_Integer Add (TheKeyType&& theKey1, const TheItemType& theItem) |
320 | { |
321 | if (Resizable()) |
7fd59977 |
322 | { |
1103eb60 |
323 | ReSize(Extent()); |
7fd59977 |
324 | } |
1103eb60 |
325 | IndexedDataMapNode* aNode; |
326 | size_t aHash; |
327 | if (lookup(theKey1, aNode, aHash)) |
328 | { |
329 | return aNode->Index(); |
330 | } |
331 | const Standard_Integer aNewIndex = Increment(); |
332 | aNode = new (this->myAllocator) IndexedDataMapNode (std::forward<TheKeyType>(theKey1), aNewIndex, theItem, myData1[aHash]); |
333 | myData1[aHash] = aNode; |
334 | myData2[aNewIndex - 1] = aNode; |
335 | return aNewIndex; |
336 | } |
510cb852 |
337 | |
1103eb60 |
338 | //! Returns the Index of already bound Key or appends new Key with specified Item value. |
339 | //! @param theKey1 Key to search (and to bind, if it was not bound already) |
340 | //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound |
341 | //! @return index of Key |
342 | Standard_Integer Add (const TheKeyType& theKey1, TheItemType&& theItem) |
343 | { |
344 | if (Resizable()) |
345 | { |
346 | ReSize(Extent()); |
347 | } |
348 | IndexedDataMapNode* aNode; |
349 | size_t aHash; |
350 | if (lookup(theKey1, aNode, aHash)) |
351 | { |
352 | return aNode->Index(); |
353 | } |
510cb852 |
354 | const Standard_Integer aNewIndex = Increment(); |
1103eb60 |
355 | aNode = new (this->myAllocator) IndexedDataMapNode (theKey1, aNewIndex, std::forward<TheItemType>(theItem), myData1[aHash]); |
356 | myData1[aHash] = aNode; |
357 | myData2[aNewIndex - 1] = aNode; |
358 | return aNewIndex; |
359 | } |
360 | |
361 | //! Returns the Index of already bound Key or appends new Key with specified Item value. |
362 | //! @param theKey1 Key to search (and to bind, if it was not bound already) |
363 | //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound |
364 | //! @return index of Key |
365 | Standard_Integer Add (TheKeyType&& theKey1, TheItemType&& theItem) |
366 | { |
367 | if (Resizable()) |
368 | { |
369 | ReSize(Extent()); |
370 | } |
371 | IndexedDataMapNode* aNode; |
372 | size_t aHash; |
373 | if (lookup(theKey1, aNode, aHash)) |
374 | { |
375 | return aNode->Index(); |
376 | } |
377 | const Standard_Integer aNewIndex = Increment(); |
378 | aNode = new (this->myAllocator) IndexedDataMapNode (std::forward<TheKeyType>(theKey1), aNewIndex, |
379 | std::forward<TheItemType>(theItem), myData1[aHash]); |
380 | myData1[aHash] = aNode; |
381 | myData2[aNewIndex - 1] = aNode; |
510cb852 |
382 | return aNewIndex; |
7fd59977 |
383 | } |
384 | |
385 | //! Contains |
386 | Standard_Boolean Contains (const TheKeyType& theKey1) const |
387 | { |
1103eb60 |
388 | IndexedDataMapNode* aNode; |
389 | if (lookup(theKey1, aNode)) |
7fd59977 |
390 | { |
1103eb60 |
391 | return true; |
7fd59977 |
392 | } |
1103eb60 |
393 | return false; |
7fd59977 |
394 | } |
395 | |
396 | //! Substitute |
397 | void Substitute (const Standard_Integer theIndex, |
398 | const TheKeyType& theKey1, |
399 | const TheItemType& theItem) |
400 | { |
985aed12 |
401 | Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), |
402 | "NCollection_IndexedDataMap::Substitute : " |
403 | "Index is out of range"); |
e3a6386d |
404 | |
7fd59977 |
405 | // check if theKey1 is not already in the map |
1103eb60 |
406 | size_t aHash; |
407 | IndexedDataMapNode* aNode; |
408 | if (lookup(theKey1, aNode, aHash)) |
7fd59977 |
409 | { |
1103eb60 |
410 | if (aNode->Index() != theIndex) |
985aed12 |
411 | { |
1103eb60 |
412 | throw Standard_DomainError("NCollection_IndexedDataMap::Substitute : " |
413 | "Attempt to substitute existing key"); |
985aed12 |
414 | } |
1103eb60 |
415 | aNode->Key1() = theKey1; |
416 | aNode->ChangeValue() = theItem; |
417 | return; |
7fd59977 |
418 | } |
419 | |
420 | // Find the node for the index I |
1103eb60 |
421 | aNode = (IndexedDataMapNode* )myData2[theIndex - 1]; |
7fd59977 |
422 | |
423 | // remove the old key |
1103eb60 |
424 | const size_t iK = HashCode (aNode->Key1(), NbBuckets()); |
7fd59977 |
425 | IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK]; |
1103eb60 |
426 | if (q == aNode) |
427 | myData1[iK] = (IndexedDataMapNode *)aNode->Next(); |
7fd59977 |
428 | else |
429 | { |
1103eb60 |
430 | while (q->Next() != aNode) |
7fd59977 |
431 | q = (IndexedDataMapNode *) q->Next(); |
1103eb60 |
432 | q->Next() = aNode->Next(); |
7fd59977 |
433 | } |
434 | |
435 | // update the node |
1103eb60 |
436 | aNode->Key1() = theKey1; |
437 | aNode->ChangeValue() = theItem; |
438 | aNode->Next() = myData1[aHash]; |
439 | myData1[aHash] = aNode; |
7fd59977 |
440 | } |
441 | |
9e506120 |
442 | //! Swaps two elements with the given indices. |
443 | void Swap (const Standard_Integer theIndex1, |
444 | const Standard_Integer theIndex2) |
445 | { |
446 | Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent() |
447 | || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedDataMap::Swap"); |
448 | |
449 | if (theIndex1 == theIndex2) |
450 | { |
451 | return; |
452 | } |
453 | |
510cb852 |
454 | IndexedDataMapNode* aP1 = (IndexedDataMapNode* )myData2[theIndex1 - 1]; |
455 | IndexedDataMapNode* aP2 = (IndexedDataMapNode* )myData2[theIndex2 - 1]; |
456 | std::swap (aP1->Index(), aP2->Index()); |
457 | myData2[theIndex2 - 1] = aP1; |
458 | myData2[theIndex1 - 1] = aP2; |
9e506120 |
459 | } |
460 | |
7fd59977 |
461 | //! RemoveLast |
462 | void RemoveLast (void) |
463 | { |
510cb852 |
464 | const Standard_Integer aLastIndex = Extent(); |
465 | Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedDataMap::RemoveLast"); |
e3a6386d |
466 | |
7fd59977 |
467 | // Find the node for the last index and remove it |
510cb852 |
468 | IndexedDataMapNode* p = (IndexedDataMapNode* )myData2[aLastIndex - 1]; |
469 | myData2[aLastIndex - 1] = NULL; |
7fd59977 |
470 | |
471 | // remove the key |
1103eb60 |
472 | const size_t iK1 = HashCode (p->Key1(), NbBuckets()); |
510cb852 |
473 | IndexedDataMapNode* q = (IndexedDataMapNode *) myData1[iK1]; |
7fd59977 |
474 | if (q == p) |
475 | myData1[iK1] = (IndexedDataMapNode *) p->Next(); |
476 | else |
477 | { |
478 | while (q->Next() != p) |
479 | q = (IndexedDataMapNode *) q->Next(); |
480 | q->Next() = p->Next(); |
481 | } |
482 | p->~IndexedDataMapNode(); |
483 | this->myAllocator->Free(p); |
484 | Decrement(); |
485 | } |
486 | |
3f5aa017 |
487 | //! Remove the key of the given index. |
488 | //! Caution! The index of the last key can be changed. |
510cb852 |
489 | void RemoveFromIndex(const Standard_Integer theIndex) |
3f5aa017 |
490 | { |
510cb852 |
491 | const Standard_Integer aLastInd = Extent(); |
492 | Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > aLastInd, "NCollection_IndexedDataMap::Remove"); |
493 | if (theIndex != aLastInd) |
494 | { |
495 | Swap (theIndex, aLastInd); |
496 | } |
3f5aa017 |
497 | RemoveLast(); |
498 | } |
499 | |
500 | //! Remove the given key. |
501 | //! Caution! The index of the last key can be changed. |
502 | void RemoveKey(const TheKeyType& theKey1) |
503 | { |
504 | Standard_Integer anIndToRemove = FindIndex(theKey1); |
505 | if (anIndToRemove > 0) { |
506 | RemoveFromIndex(anIndToRemove); |
507 | } |
508 | } |
509 | |
7fd59977 |
510 | //! FindKey |
510cb852 |
511 | const TheKeyType& FindKey (const Standard_Integer theIndex) const |
7fd59977 |
512 | { |
510cb852 |
513 | Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindKey"); |
514 | IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1]; |
ad3217cd |
515 | return aNode->Key1(); |
7fd59977 |
516 | } |
517 | |
518 | //! FindFromIndex |
510cb852 |
519 | const TheItemType& FindFromIndex (const Standard_Integer theIndex) const |
7fd59977 |
520 | { |
510cb852 |
521 | Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindFromIndex"); |
522 | IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1]; |
ad3217cd |
523 | return aNode->Value(); |
7fd59977 |
524 | } |
525 | |
526 | //! operator () |
510cb852 |
527 | const TheItemType& operator() (const Standard_Integer theIndex) const { return FindFromIndex (theIndex); } |
7fd59977 |
528 | |
529 | //! ChangeFromIndex |
510cb852 |
530 | TheItemType& ChangeFromIndex (const Standard_Integer theIndex) |
7fd59977 |
531 | { |
510cb852 |
532 | Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex"); |
533 | IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1]; |
ad3217cd |
534 | return aNode->ChangeValue(); |
7fd59977 |
535 | } |
536 | |
537 | //! operator () |
510cb852 |
538 | TheItemType& operator() (const Standard_Integer theIndex) { return ChangeFromIndex (theIndex); } |
7fd59977 |
539 | |
540 | //! FindIndex |
541 | Standard_Integer FindIndex(const TheKeyType& theKey1) const |
542 | { |
1103eb60 |
543 | IndexedDataMapNode* aNode; |
544 | if (lookup(theKey1, aNode)) |
7fd59977 |
545 | { |
1103eb60 |
546 | return aNode->Index(); |
7fd59977 |
547 | } |
548 | return 0; |
549 | } |
550 | |
551 | //! FindFromKey |
552 | const TheItemType& FindFromKey(const TheKeyType& theKey1) const |
553 | { |
e3a6386d |
554 | Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey"); |
1103eb60 |
555 | IndexedDataMapNode* aNode; |
556 | if (lookup(theKey1, aNode)) |
7fd59977 |
557 | { |
1103eb60 |
558 | return aNode->Value(); |
7fd59977 |
559 | } |
9775fa61 |
560 | throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindFromKey"); |
7fd59977 |
561 | } |
562 | |
563 | //! ChangeFromKey |
564 | TheItemType& ChangeFromKey (const TheKeyType& theKey1) |
565 | { |
e3a6386d |
566 | Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey"); |
1103eb60 |
567 | IndexedDataMapNode* aNode; |
568 | if (lookup(theKey1, aNode)) |
7fd59977 |
569 | { |
1103eb60 |
570 | return aNode->ChangeValue(); |
7fd59977 |
571 | } |
9775fa61 |
572 | throw Standard_NoSuchObject("NCollection_IndexedDataMap::ChangeFromKey"); |
7fd59977 |
573 | } |
574 | |
031d5ab7 |
575 | //! Seek returns pointer to Item by Key. Returns |
576 | //! NULL if Key was not found. |
577 | const TheItemType* Seek(const TheKeyType& theKey1) const |
578 | { |
579 | return const_cast< NCollection_IndexedDataMap * >( this )->ChangeSeek(theKey1); |
031d5ab7 |
580 | } |
581 | |
582 | //! ChangeSeek returns modifiable pointer to Item by Key. Returns |
583 | //! NULL if Key was not found. |
584 | TheItemType* ChangeSeek (const TheKeyType& theKey1) |
585 | { |
1103eb60 |
586 | IndexedDataMapNode* aNode; |
587 | if (lookup(theKey1, aNode)) |
031d5ab7 |
588 | { |
1103eb60 |
589 | return &aNode->ChangeValue(); |
031d5ab7 |
590 | } |
1103eb60 |
591 | return nullptr; |
031d5ab7 |
592 | } |
593 | |
ad3217cd |
594 | //! Find value for key with copying. |
595 | //! @return true if key was found |
596 | Standard_Boolean FindFromKey (const TheKeyType& theKey1, |
597 | TheItemType& theValue) const |
598 | { |
1103eb60 |
599 | IndexedDataMapNode* aNode; |
600 | if (lookup(theKey1, aNode)) |
ad3217cd |
601 | { |
ad3217cd |
602 | theValue = aNode->Value(); |
603 | return Standard_True; |
ad3217cd |
604 | } |
605 | return Standard_False; |
606 | } |
607 | |
7fd59977 |
608 | //! Clear data. If doReleaseMemory is false then the table of |
609 | //! buckets is not released and will be reused. |
1103eb60 |
610 | void Clear(const Standard_Boolean doReleaseMemory = Standard_False) |
ddf2fe8e |
611 | { Destroy (IndexedDataMapNode::delNode, doReleaseMemory); } |
7fd59977 |
612 | |
613 | //! Clear data and reset allocator |
614 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
615 | { |
1103eb60 |
616 | Clear(theAllocator != this->myAllocator); |
7fd59977 |
617 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
618 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
619 | } |
620 | |
621 | //! Destructor |
6928e351 |
622 | virtual ~NCollection_IndexedDataMap (void) |
1103eb60 |
623 | { Clear(true); } |
7fd59977 |
624 | |
625 | //! Size |
ddf2fe8e |
626 | Standard_Integer Size(void) const |
7fd59977 |
627 | { return Extent(); } |
628 | |
1103eb60 |
629 | protected: |
630 | |
631 | //! Lookup for particular key in map. |
632 | //! @param[in] theKey key to compute hash |
633 | //! @param[out] theNode the detected node with equal key. Can be null. |
634 | //! @param[out] theHash computed bounded hash code for current key. |
635 | //! @return true if key is found |
636 | Standard_Boolean lookup(const TheKeyType& theKey, IndexedDataMapNode*& theNode, size_t& theHash) const |
637 | { |
638 | theHash = HashCode(theKey, NbBuckets()); |
639 | if (IsEmpty()) |
640 | return Standard_False; // Not found |
641 | for (theNode = (IndexedDataMapNode*)myData1[theHash]; |
642 | theNode; theNode = (IndexedDataMapNode*)theNode->Next()) |
643 | { |
644 | if (IsEqual(theNode->Key1(), theKey)) |
645 | return Standard_True; |
646 | } |
647 | return Standard_False; // Not found |
648 | } |
649 | |
650 | //! Lookup for particular key in map. |
651 | //! @param[in] theKey key to compute hash |
652 | //! @param[out] theNode the detected node with equal key. Can be null. |
653 | //! @return true if key is found |
654 | Standard_Boolean lookup(const TheKeyType& theKey, IndexedDataMapNode*& theNode) const |
655 | { |
656 | if (IsEmpty()) |
657 | return Standard_False; // Not found |
658 | for (theNode = (IndexedDataMapNode*)myData1[HashCode(theKey, NbBuckets())]; |
659 | theNode; theNode = (IndexedDataMapNode*)theNode->Next()) |
660 | { |
661 | if (IsEqual(theNode->Key1(), theKey)) |
662 | { |
663 | return Standard_True; |
664 | } |
665 | } |
666 | return Standard_False; // Not found |
667 | } |
668 | |
669 | bool IsEqual(const TheKeyType& theKey1, |
670 | const TheKeyType& theKey2) const |
671 | { |
672 | return myHasher(theKey1, theKey2); |
673 | } |
674 | |
675 | size_t HashCode(const TheKeyType& theKey, |
676 | const int theUpperBound) const |
677 | { |
678 | return myHasher(theKey) % theUpperBound + 1; |
679 | } |
680 | |
681 | protected: |
7fd59977 |
682 | |
1103eb60 |
683 | Hasher myHasher; |
7fd59977 |
684 | }; |
685 | |
7fd59977 |
686 | #endif |