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_IndexedMap_HeaderFile |
17 | #define NCollection_IndexedMap_HeaderFile |
18 | |
7fd59977 |
19 | #include <NCollection_BaseMap.hxx> |
20 | #include <NCollection_TListNode.hxx> |
79a35943 |
21 | #include <NCollection_StlIterator.hxx> |
7fd59977 |
22 | #include <Standard_NoSuchObject.hxx> |
7fd59977 |
23 | |
9991c9c2 |
24 | #include <NCollection_DefaultHasher.hxx> |
25 | |
7fd59977 |
26 | #include <Standard_OutOfRange.hxx> |
7fd59977 |
27 | |
7fd59977 |
28 | /** |
29 | * Purpose: An indexed map is used to store keys and to bind |
30 | * an index to them. Each new key stored in the map |
31 | * gets an index. Index are incremented as keys are |
32 | * stored in the map. A key can be found by the index |
33 | * and an index by the key. No key but the last can |
34 | * be removed so the indices are in the range 1..Extent. |
35 | * See the class Map from NCollection for a |
36 | * discussion about the number of buckets. |
37 | */ |
9991c9c2 |
38 | |
39 | template < class TheKeyType, |
40 | class Hasher = NCollection_DefaultHasher<TheKeyType> > |
ddf2fe8e |
41 | class NCollection_IndexedMap : public NCollection_BaseMap |
7fd59977 |
42 | { |
3f5aa017 |
43 | public: |
44 | //! STL-compliant typedef for key type |
45 | typedef TheKeyType key_type; |
46 | |
7fd59977 |
47 | private: |
3f5aa017 |
48 | // **************** Adaptation of the TListNode to the INDEXEDmap |
49 | class IndexedMapNode : public NCollection_TListNode<TheKeyType> |
7fd59977 |
50 | { |
51 | public: |
52 | //! Constructor with 'Next' |
53 | IndexedMapNode (const TheKeyType& theKey1, |
54 | const Standard_Integer theKey2, |
55 | NCollection_ListNode* theNext1, |
56 | NCollection_ListNode* theNext2) : |
e3a6386d |
57 | NCollection_TListNode<TheKeyType> (theKey1, theNext1), |
58 | myKey2(theKey2), |
59 | myNext2((IndexedMapNode*)theNext2) |
7fd59977 |
60 | { |
7fd59977 |
61 | } |
62 | //! Key1 |
63 | TheKeyType& Key1 (void) |
64 | { return this->ChangeValue(); } |
65 | //! Key2 |
9e506120 |
66 | Standard_Integer& Key2 (void) |
7fd59977 |
67 | { return myKey2; } |
68 | //! Next2 |
69 | IndexedMapNode*& Next2 (void) |
70 | { return myNext2; } |
71 | |
72 | //! Static deleter to be passed to BaseList |
73 | static void delNode (NCollection_ListNode * theNode, |
74 | Handle(NCollection_BaseAllocator)& theAl) |
75 | { |
76 | ((IndexedMapNode *) theNode)->~IndexedMapNode(); |
77 | theAl->Free(theNode); |
78 | } |
79 | |
80 | private: |
81 | Standard_Integer myKey2; |
82 | IndexedMapNode * myNext2; |
83 | }; |
84 | |
85 | public: |
86 | // **************** Implementation of the Iterator interface. |
ddf2fe8e |
87 | class Iterator |
7fd59977 |
88 | { |
89 | public: |
90 | //! Empty constructor |
91 | Iterator (void) : |
92 | myMap(NULL), |
93 | myIndex(0) {} |
94 | //! Constructor |
95 | Iterator (const NCollection_IndexedMap& theMap) : |
96 | myMap((NCollection_IndexedMap *) &theMap), |
97 | myIndex(1) {} |
98 | //! Query if the end of collection is reached by iterator |
ddf2fe8e |
99 | Standard_Boolean More(void) const |
79a35943 |
100 | { return (myMap != NULL) && (myIndex <= myMap->Extent()); } |
7fd59977 |
101 | //! Make a step along the collection |
ddf2fe8e |
102 | void Next(void) |
7fd59977 |
103 | { myIndex++; } |
104 | //! Value access |
ddf2fe8e |
105 | const TheKeyType& Value(void) const |
7fd59977 |
106 | { |
e3a6386d |
107 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedMap::Iterator::Value"); |
7fd59977 |
108 | return myMap->FindKey(myIndex); |
109 | } |
9775fa61 |
110 | |
79a35943 |
111 | //! Performs comparison of two iterators. |
ddf2fe8e |
112 | Standard_Boolean IsEqual (const Iterator& theOther) const |
79a35943 |
113 | { |
114 | return myMap == theOther.myMap && myIndex == theOther.myIndex; |
115 | } |
7fd59977 |
116 | |
7fd59977 |
117 | private: |
118 | NCollection_IndexedMap * myMap; // Pointer to the map being iterated |
119 | Standard_Integer myIndex; // Current index |
120 | }; |
121 | |
79a35943 |
122 | //! Shorthand for a constant iterator type. |
123 | typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheKeyType, true> const_iterator; |
124 | |
125 | //! Returns a const iterator pointing to the first element in the map. |
126 | const_iterator cbegin() const { return Iterator (*this); } |
127 | |
128 | //! Returns a const iterator referring to the past-the-end element in the map. |
129 | const_iterator cend() const { return Iterator(); } |
130 | |
7fd59977 |
131 | public: |
132 | // ---------- PUBLIC METHODS ------------ |
133 | |
134 | //! Constructor |
135 | NCollection_IndexedMap (const Standard_Integer NbBuckets=1, |
ddf2fe8e |
136 | const Handle(NCollection_BaseAllocator)& theAllocator=0L) |
137 | : NCollection_BaseMap (NbBuckets, Standard_False, theAllocator) {} |
7fd59977 |
138 | |
139 | //! Copy constructor |
ddf2fe8e |
140 | NCollection_IndexedMap (const NCollection_IndexedMap& theOther) |
141 | : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) |
7fd59977 |
142 | { *this = theOther; } |
143 | |
ab2db9a5 |
144 | //! Exchange the content of two maps without re-allocations. |
145 | //! Notice that allocators will be swapped as well! |
146 | void Exchange (NCollection_IndexedMap& theOther) |
147 | { |
ddf2fe8e |
148 | this->exchangeMapsData (theOther); |
ab2db9a5 |
149 | } |
150 | |
5e452c37 |
151 | //! Assign. |
152 | //! This method does not change the internal allocator. |
ddf2fe8e |
153 | NCollection_IndexedMap& Assign (const NCollection_IndexedMap& theOther) |
7fd59977 |
154 | { |
155 | if (this == &theOther) |
156 | return *this; |
157 | |
5e452c37 |
158 | Clear(); |
7fd59977 |
159 | ReSize (theOther.Extent()-1); |
160 | Standard_Integer i, iLength=theOther.Extent(); |
161 | for (i=1; i<=iLength; i++) |
162 | { |
163 | TheKeyType aKey1 = theOther(i); |
9991c9c2 |
164 | Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets()); |
165 | Standard_Integer iK2 = ::HashCode (i, NbBuckets()); |
7fd59977 |
166 | IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i, |
167 | myData1[iK1], |
168 | myData2[iK2]); |
169 | myData1[iK1] = pNode; |
170 | myData2[iK2] = pNode; |
171 | Increment(); |
172 | } |
173 | return *this; |
174 | } |
175 | |
ddf2fe8e |
176 | //! Assignment operator |
177 | NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther) |
178 | { |
179 | return Assign (theOther); |
180 | } |
181 | |
7fd59977 |
182 | //! ReSize |
183 | void ReSize (const Standard_Integer N) |
184 | { |
fd03ee4b |
185 | NCollection_ListNode** ppNewData1 = NULL; |
186 | NCollection_ListNode** ppNewData2 = NULL; |
7fd59977 |
187 | Standard_Integer newBuck; |
ddf2fe8e |
188 | if (BeginResize (N, newBuck, ppNewData1, ppNewData2)) |
7fd59977 |
189 | { |
190 | if (myData1) |
191 | { |
192 | IndexedMapNode *p, *q; |
193 | Standard_Integer i, iK1, iK2; |
194 | for (i = 0; i <= NbBuckets(); i++) |
195 | { |
196 | if (myData1[i]) |
197 | { |
198 | p = (IndexedMapNode *) myData1[i]; |
199 | while (p) |
200 | { |
9991c9c2 |
201 | iK1 =Hasher::HashCode(p->Key1(), newBuck); |
7fd59977 |
202 | q = (IndexedMapNode*) p->Next(); |
203 | p->Next() = ppNewData1[iK1]; |
204 | ppNewData1[iK1] = p; |
205 | if (p->Key2() > 0) |
206 | { |
9991c9c2 |
207 | iK2 = ::HashCode (p->Key2(), newBuck); |
fd03ee4b |
208 | p->Next2() = (IndexedMapNode*)ppNewData2[iK2]; |
7fd59977 |
209 | ppNewData2[iK2] = p; |
210 | } |
211 | p = q; |
212 | } |
213 | } |
214 | } |
215 | } |
ddf2fe8e |
216 | EndResize (N, newBuck, ppNewData1, ppNewData2); |
7fd59977 |
217 | } |
218 | } |
219 | |
220 | //! Add |
221 | Standard_Integer Add (const TheKeyType& theKey1) |
222 | { |
223 | if (Resizable()) |
224 | ReSize(Extent()); |
9991c9c2 |
225 | Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); |
7fd59977 |
226 | IndexedMapNode * pNode; |
227 | pNode = (IndexedMapNode *) myData1[iK1]; |
228 | while (pNode) |
229 | { |
9991c9c2 |
230 | if (Hasher::IsEqual (pNode->Key1(), theKey1)) |
7fd59977 |
231 | return pNode->Key2(); |
232 | pNode = (IndexedMapNode *) pNode->Next(); |
233 | } |
234 | Increment(); |
9991c9c2 |
235 | Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets()); |
7fd59977 |
236 | pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(), |
237 | myData1[iK1], myData2[iK2]); |
238 | myData1[iK1] = pNode; |
239 | myData2[iK2] = pNode; |
240 | return Extent(); |
241 | } |
242 | |
243 | //! Contains |
244 | Standard_Boolean Contains (const TheKeyType& theKey1) const |
245 | { |
246 | if (IsEmpty()) |
247 | return Standard_False; |
9991c9c2 |
248 | Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); |
7fd59977 |
249 | IndexedMapNode * pNode1; |
250 | pNode1 = (IndexedMapNode *) myData1[iK1]; |
251 | while (pNode1) |
252 | { |
9991c9c2 |
253 | if (Hasher::IsEqual(pNode1->Key1(), theKey1)) |
7fd59977 |
254 | return Standard_True; |
255 | pNode1 = (IndexedMapNode *) pNode1->Next(); |
256 | } |
257 | return Standard_False; |
258 | } |
259 | |
260 | //! Substitute |
261 | void Substitute (const Standard_Integer theIndex, |
262 | const TheKeyType& theKey1) |
263 | { |
985aed12 |
264 | Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), |
265 | "NCollection_IndexedMap::Substitute : " |
266 | "Index is out of range"); |
e3a6386d |
267 | |
7fd59977 |
268 | IndexedMapNode * p; |
269 | // check if theKey1 is not already in the map |
9991c9c2 |
270 | Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); |
7fd59977 |
271 | p = (IndexedMapNode *) myData1[iK1]; |
985aed12 |
272 | while (p) |
7fd59977 |
273 | { |
985aed12 |
274 | if (Hasher::IsEqual (p->Key1(), theKey1)) |
275 | { |
276 | if (p->Key2() != theIndex) |
277 | { |
9775fa61 |
278 | throw Standard_DomainError ("NCollection_IndexedMap::Substitute : " |
279 | "Attempt to substitute existing key"); |
985aed12 |
280 | } |
281 | p->Key1() = theKey1; |
282 | return; |
283 | } |
7fd59977 |
284 | p = (IndexedMapNode *) p->Next(); |
285 | } |
286 | |
287 | // Find the node for the index I |
9991c9c2 |
288 | Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets()); |
7fd59977 |
289 | p = (IndexedMapNode *) myData2[iK2]; |
290 | while (p) |
291 | { |
292 | if (p->Key2() == theIndex) |
293 | break; |
294 | p = (IndexedMapNode*) p->Next2(); |
295 | } |
296 | |
297 | // remove the old key |
9991c9c2 |
298 | Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets()); |
7fd59977 |
299 | IndexedMapNode * q = (IndexedMapNode *) myData1[iK]; |
300 | if (q == p) |
301 | myData1[iK] = (IndexedMapNode *) p->Next(); |
302 | else |
303 | { |
304 | while (q->Next() != p) |
305 | q = (IndexedMapNode *) q->Next(); |
306 | q->Next() = p->Next(); |
307 | } |
308 | |
309 | // update the node |
310 | p->Key1() = theKey1; |
311 | p->Next() = myData1[iK1]; |
312 | myData1[iK1] = p; |
313 | } |
314 | |
9e506120 |
315 | //! Swaps two elements with the given indices. |
316 | void Swap (const Standard_Integer theIndex1, |
317 | const Standard_Integer theIndex2) |
318 | { |
319 | Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent() |
320 | || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedMap::Swap"); |
321 | |
322 | if (theIndex1 == theIndex2) |
323 | { |
324 | return; |
325 | } |
326 | |
327 | const Standard_Integer aK1 = ::HashCode (theIndex1, NbBuckets()); |
328 | const Standard_Integer aK2 = ::HashCode (theIndex2, NbBuckets()); |
329 | |
330 | IndexedMapNode* aP1 = (IndexedMapNode*) myData2[aK1]; |
331 | IndexedMapNode* aP2 = (IndexedMapNode*) myData2[aK2]; |
332 | |
333 | if (aP1->Key2() == theIndex1) |
334 | { |
335 | myData2[aK1] = (IndexedMapNode *) aP1->Next2(); |
336 | } |
337 | else |
338 | { |
339 | IndexedMapNode* aQ = aP1; |
340 | for (aP1 = aQ->Next2(); aP1->Key2() != theIndex1; aQ = aP1, aP1 = aQ->Next2()) { } |
341 | |
342 | aQ->Next2() = aP1->Next2(); |
343 | } |
344 | |
345 | if (aP2->Key2() == theIndex2) |
346 | { |
347 | myData2[aK2] = (IndexedMapNode *) aP2->Next2(); |
348 | } |
349 | else |
350 | { |
351 | IndexedMapNode* aQ = aP2; |
352 | for (aP2 = aQ->Next2(); aP2->Key2() != theIndex2; aQ = aP2, aP2 = aQ->Next2()) { } |
353 | |
354 | aQ->Next2() = aP2->Next2(); |
355 | } |
356 | |
357 | std::swap (aP1->Key2(), |
358 | aP2->Key2()); |
359 | |
360 | aP1->Next2() = (IndexedMapNode*) myData2[aK2]; |
361 | myData2[aK2] = aP1; |
362 | |
363 | aP2->Next2() = (IndexedMapNode*) myData2[aK1]; |
364 | myData2[aK1] = aP2; |
365 | } |
366 | |
7fd59977 |
367 | //! RemoveLast |
368 | void RemoveLast (void) |
369 | { |
e3a6386d |
370 | Standard_OutOfRange_Raise_if (Extent() == 0, "NCollection_IndexedMap::RemoveLast"); |
371 | |
7fd59977 |
372 | IndexedMapNode * p, * q; |
373 | // Find the node for the last index and remove it |
9991c9c2 |
374 | Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets()); |
7fd59977 |
375 | p = (IndexedMapNode *) myData2[iK2]; |
376 | q = NULL; |
377 | while (p) |
378 | { |
379 | if (p->Key2() == Extent()) |
380 | break; |
381 | q = p; |
382 | p = (IndexedMapNode*) p->Next2(); |
383 | } |
384 | if (q == NULL) |
385 | myData2[iK2] = (IndexedMapNode *) p->Next2(); |
386 | else |
387 | q->Next2() = p->Next2(); |
388 | |
389 | // remove the key |
9991c9c2 |
390 | Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets()); |
7fd59977 |
391 | q = (IndexedMapNode *) myData1[iK1]; |
392 | if (q == p) |
393 | myData1[iK1] = (IndexedMapNode *) p->Next(); |
394 | else |
395 | { |
396 | while (q->Next() != p) |
397 | q = (IndexedMapNode *) q->Next(); |
398 | q->Next() = p->Next(); |
399 | } |
400 | p->~IndexedMapNode(); |
401 | this->myAllocator->Free(p); |
402 | Decrement(); |
403 | } |
404 | |
3f5aa017 |
405 | //! Remove the key of the given index. |
406 | //! Caution! The index of the last key can be changed. |
407 | void RemoveFromIndex(const Standard_Integer theKey2) |
408 | { |
409 | Standard_OutOfRange_Raise_if(theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedMap::Remove"); |
410 | Standard_Integer aLastInd = Extent(); |
411 | if (theKey2 != aLastInd) |
412 | Swap(theKey2, aLastInd); |
413 | RemoveLast(); |
414 | } |
415 | |
416 | //! Remove the given key. |
417 | //! Caution! The index of the last key can be changed. |
418 | void RemoveKey(const TheKeyType& theKey1) |
419 | { |
420 | Standard_Integer anIndToRemove = FindIndex(theKey1); |
421 | if (anIndToRemove > 0) { |
422 | RemoveFromIndex(anIndToRemove); |
423 | } |
424 | } |
425 | |
7fd59977 |
426 | //! FindKey |
427 | const TheKeyType& FindKey (const Standard_Integer theKey2) const |
428 | { |
e3a6386d |
429 | Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedMap::FindKey"); |
430 | |
7fd59977 |
431 | IndexedMapNode * pNode2 = |
9991c9c2 |
432 | (IndexedMapNode *) myData2[::HashCode(theKey2,NbBuckets())]; |
7fd59977 |
433 | while (pNode2) |
434 | { |
435 | if (pNode2->Key2() == theKey2) |
436 | return pNode2->Key1(); |
437 | pNode2 = (IndexedMapNode*) pNode2->Next2(); |
438 | } |
9775fa61 |
439 | throw Standard_NoSuchObject("NCollection_IndexedMap::FindKey"); |
7fd59977 |
440 | } |
441 | |
442 | //! operator () |
443 | const TheKeyType& operator() (const Standard_Integer theKey2) const |
444 | { return FindKey (theKey2); } |
445 | |
446 | //! FindIndex |
447 | Standard_Integer FindIndex(const TheKeyType& theKey1) const |
448 | { |
449 | if (IsEmpty()) return 0; |
450 | IndexedMapNode * pNode1 = |
9991c9c2 |
451 | (IndexedMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())]; |
7fd59977 |
452 | while (pNode1) |
453 | { |
9991c9c2 |
454 | if (Hasher::IsEqual (pNode1->Key1(), theKey1)) |
7fd59977 |
455 | return pNode1->Key2(); |
456 | pNode1 = (IndexedMapNode*) pNode1->Next(); |
457 | } |
458 | return 0; |
459 | } |
460 | |
461 | //! Clear data. If doReleaseMemory is false then the table of |
462 | //! buckets is not released and will be reused. |
463 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
ddf2fe8e |
464 | { Destroy (IndexedMapNode::delNode, doReleaseMemory); } |
7fd59977 |
465 | |
466 | //! Clear data and reset allocator |
467 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
468 | { |
469 | Clear(); |
470 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
471 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
472 | } |
473 | |
474 | //! Destructor |
6928e351 |
475 | virtual ~NCollection_IndexedMap (void) |
7fd59977 |
476 | { Clear(); } |
477 | |
478 | //! Size |
ddf2fe8e |
479 | Standard_Integer Size(void) const |
7fd59977 |
480 | { return Extent(); } |
7fd59977 |
481 | }; |
482 | |
7fd59977 |
483 | #endif |