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