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