1 // File: NCollection_IndexedDataMap.hxx
2 // Created: Thu Apr 24 15:02:53 2002
3 // Author: Alexander KARTOMIN (akm)
4 // <akm@opencascade.com>
6 #ifndef NCollection_IndexedDataMap_HeaderFile
7 #define NCollection_IndexedDataMap_HeaderFile
9 #include <NCollection_BaseCollection.hxx>
10 #include <NCollection_BaseMap.hxx>
11 #include <NCollection_TListNode.hxx>
12 #include <Standard_TypeMismatch.hxx>
13 #include <Standard_NoSuchObject.hxx>
14 #if !defined No_Exception && !defined No_Standard_OutOfRange
15 #include <Standard_OutOfRange.hxx>
19 // Disable the warning "operator new unmatched by delete"
20 #pragma warning (push)
21 #pragma warning (disable:4291)
25 * Purpose: An indexed map is used to store keys and to bind
26 * an index to them. Each new key stored in the map
27 * gets an index. Index are incremented as keys are
28 * stored in the map. A key can be found by the index
29 * and an index by the key. No key but the last can
30 * be removed so the indices are in the range 1..
31 * Extent. An Item is stored with each key.
33 * This class is similar to IndexedMap from
34 * NCollection with the Item as a new feature. Note
35 * the important difference on the operator (). In
36 * the IndexedMap this operator returns the Key. In
37 * the IndexedDataMap this operator returns the Item.
39 * See the class Map from NCollection for a
40 * discussion about the number of buckets.
42 template <class TheKeyType, class TheItemType> class NCollection_IndexedDataMap
43 : public NCollection_BaseCollection<TheItemType>,
44 public NCollection_BaseMap
46 //! Adaptation of the TListNode to the INDEXEDDatamap
48 class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
51 //! Constructor with 'Next'
52 IndexedDataMapNode (const TheKeyType& theKey1,
53 const Standard_Integer theKey2,
54 const TheItemType& theItem,
55 NCollection_ListNode* theNext1,
56 NCollection_ListNode* theNext2) :
57 NCollection_TListNode<TheItemType>(theItem,theNext1)
61 myNext2 = (IndexedDataMapNode *) theNext2;
64 TheKeyType& Key1 (void)
67 const Standard_Integer& Key2 (void)
70 IndexedDataMapNode*& Next2 (void)
73 //! Static deleter to be passed to BaseList
74 static void delNode (NCollection_ListNode * theNode,
75 Handle(NCollection_BaseAllocator)& theAl)
77 ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
82 Standard_Integer myKey2;
83 IndexedDataMapNode * myNext2;
87 //! Implementation of the Iterator interface.
88 class Iterator : public NCollection_BaseCollection<TheItemType>::Iterator
96 Iterator (const NCollection_IndexedDataMap& theMap) :
97 myMap((NCollection_IndexedDataMap *) &theMap),
99 //! Query if the end of collection is reached by iterator
100 virtual Standard_Boolean More(void) const
101 { return (myIndex <= myMap->Extent()); }
102 //! Make a step along the collection
103 virtual void Next(void)
106 virtual const TheItemType& Value(void) const
108 #if !defined No_Exception && !defined No_Standard_NoSuchObject
110 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::Value");
112 return myMap->FindFromIndex(myIndex);
114 //! ChangeValue access
115 virtual TheItemType& ChangeValue(void) const
117 #if !defined No_Exception && !defined No_Standard_NoSuchObject
119 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::ChangeValue");
121 return myMap->ChangeFromIndex(myIndex);
123 //! Operator new for allocating iterators
124 void* operator new(size_t theSize,
125 const Handle(NCollection_BaseAllocator)& theAllocator)
126 { return theAllocator->Allocate(theSize); }
129 NCollection_IndexedDataMap * myMap; //!< Pointer to the map being iterated
130 Standard_Integer myIndex; //!< Current index
134 // ---------- PUBLIC METHODS ------------
137 NCollection_IndexedDataMap (const Standard_Integer NbBuckets=1,
138 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
139 : NCollection_BaseCollection<TheItemType>(theAllocator),
140 NCollection_BaseMap (NbBuckets, Standard_False) {}
143 NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther)
144 : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
145 NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
146 { *this = theOther; }
148 //! Assign another collection
149 virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
151 if (this == &theOther)
153 Standard_TypeMismatch::Raise("NCollection_IndexedDataMap::Assign");
157 NCollection_IndexedDataMap& operator=
158 (const NCollection_IndexedDataMap& theOther)
160 if (this == &theOther)
163 Clear(theOther.myAllocator);
164 ReSize (theOther.Extent()-1);
166 for (i=1; i<=theOther.Extent(); i++)
168 TheKeyType aKey1 = theOther.FindKey(i);
169 TheItemType anItem = theOther.FindFromIndex(i);
170 Standard_Integer iK1 = HashCode (aKey1, NbBuckets());
171 Standard_Integer iK2 = HashCode (i, NbBuckets());
172 IndexedDataMapNode * pNode =
173 new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
174 myData1[iK1], myData2[iK2]);
175 myData1[iK1] = pNode;
176 myData2[iK2] = pNode;
183 void ReSize (const Standard_Integer N)
185 IndexedDataMapNode** ppNewData1 = NULL;
186 IndexedDataMapNode** ppNewData2 = NULL;
187 Standard_Integer newBuck;
188 if (BeginResize (N, newBuck,
189 (NCollection_ListNode**&)ppNewData1,
190 (NCollection_ListNode**&)ppNewData2,
195 IndexedDataMapNode *p, *q;
196 Standard_Integer i, iK1, iK2;
197 for (i = 0; i <= NbBuckets(); i++)
201 p = (IndexedDataMapNode *) myData1[i];
204 iK1 = HashCode (p->Key1(), newBuck);
205 iK2 = HashCode (p->Key2(), newBuck);
206 q = (IndexedDataMapNode*) p->Next();
207 p->Next() = ppNewData1[iK1];
208 p->Next2() = ppNewData2[iK2];
217 (NCollection_ListNode**&)ppNewData1,
218 (NCollection_ListNode**&)ppNewData2,
224 Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
228 Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
229 IndexedDataMapNode * pNode;
230 pNode = (IndexedDataMapNode *) myData1[iK1];
233 if (IsEqual (pNode->Key1(), theKey1))
234 return pNode->Key2();
235 pNode = (IndexedDataMapNode *) pNode->Next();
238 Standard_Integer iK2 = HashCode(Extent(),NbBuckets());
239 pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
240 myData1[iK1], myData2[iK2]);
241 myData1[iK1] = pNode;
242 myData2[iK2] = pNode;
247 Standard_Boolean Contains (const TheKeyType& theKey1) const
250 return Standard_False;
251 Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
252 IndexedDataMapNode * pNode1;
253 pNode1 = (IndexedDataMapNode *) myData1[iK1];
256 if (IsEqual(pNode1->Key1(), theKey1))
257 return Standard_True;
258 pNode1 = (IndexedDataMapNode *) pNode1->Next();
260 return Standard_False;
264 void Substitute (const Standard_Integer theIndex,
265 const TheKeyType& theKey1,
266 const TheItemType& theItem)
268 #if !defined No_Exception && !defined No_Standard_OutOfRange
269 if (theIndex < 1 || theIndex > Extent())
270 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::Substitute");
272 IndexedDataMapNode * p;
273 // check if theKey1 is not already in the map
274 Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
275 p = (IndexedDataMapNode *) myData1[iK1];
278 if (IsEqual (p->Key1(), theKey1))
279 Standard_DomainError::Raise("NCollection_IndexedDataMap::Substitute");
280 p = (IndexedDataMapNode *) p->Next();
283 // Find the node for the index I
284 Standard_Integer iK2 = HashCode (theIndex, NbBuckets());
285 p = (IndexedDataMapNode *) myData2[iK2];
288 if (p->Key2() == theIndex)
290 p = (IndexedDataMapNode*) p->Next2();
293 // remove the old key
294 Standard_Integer iK = HashCode (p->Key1(), NbBuckets());
295 IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
297 myData1[iK] = (IndexedDataMapNode *) p->Next();
300 while (q->Next() != p)
301 q = (IndexedDataMapNode *) q->Next();
302 q->Next() = p->Next();
307 p->ChangeValue() = theItem;
308 p->Next() = myData1[iK1];
313 void RemoveLast (void)
315 #if !defined No_Exception && !defined No_Standard_OutOfRange
317 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::RemoveLast");
319 IndexedDataMapNode * p, * q;
320 // Find the node for the last index and remove it
321 Standard_Integer iK2 = HashCode (Extent(), NbBuckets());
322 p = (IndexedDataMapNode *) myData2[iK2];
326 if (p->Key2() == Extent())
329 p = (IndexedDataMapNode*) p->Next2();
332 myData2[iK2] = (IndexedDataMapNode *) p->Next2();
334 q->Next2() = p->Next2();
337 Standard_Integer iK1 = HashCode (p->Key1(), NbBuckets());
338 q = (IndexedDataMapNode *) myData1[iK1];
340 myData1[iK1] = (IndexedDataMapNode *) p->Next();
343 while (q->Next() != p)
344 q = (IndexedDataMapNode *) q->Next();
345 q->Next() = p->Next();
347 p->~IndexedDataMapNode();
348 this->myAllocator->Free(p);
353 const TheKeyType& FindKey (const Standard_Integer theKey2) const
355 #if !defined No_Exception && !defined No_Standard_OutOfRange
356 if (theKey2 < 1 || theKey2 > Extent())
357 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindKey");
359 IndexedDataMapNode * pNode2 =
360 (IndexedDataMapNode *) myData2[HashCode(theKey2,NbBuckets())];
363 if (pNode2->Key2() == theKey2)
364 return pNode2->Key1();
365 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
367 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindKey");
368 return pNode2->Key1(); // This for compiler
372 const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
374 #if !defined No_Exception && !defined No_Standard_OutOfRange
375 if (theKey2 < 1 || theKey2 > Extent())
376 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindFromIndex");
378 IndexedDataMapNode * pNode2 =
379 (IndexedDataMapNode *) myData2[HashCode(theKey2,NbBuckets())];
382 if (pNode2->Key2() == theKey2)
383 return pNode2->Value();
384 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
386 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
387 return pNode2->Value(); // This for compiler
391 const TheItemType& operator() (const Standard_Integer theKey2) const
392 { return FindFromIndex (theKey2); }
395 TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
397 #if !defined No_Exception && !defined No_Standard_OutOfRange
398 if (theKey2 < 1 || theKey2 > Extent())
399 Standard_OutOfRange::Raise("NCollection_IndexedDataMap::ChangeFromIndex");
401 IndexedDataMapNode * pNode2 =
402 (IndexedDataMapNode *) myData2[HashCode(theKey2,NbBuckets())];
405 if (pNode2->Key2() == theKey2)
406 return pNode2->ChangeValue();
407 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
409 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
410 return pNode2->ChangeValue(); // This for compiler
414 TheItemType& operator() (const Standard_Integer theKey2)
415 { return ChangeFromIndex (theKey2); }
418 Standard_Integer FindIndex(const TheKeyType& theKey1) const
420 if (IsEmpty()) return 0;
421 IndexedDataMapNode * pNode1 =
422 (IndexedDataMapNode *) myData1[HashCode(theKey1,NbBuckets())];
425 if (IsEqual (pNode1->Key1(), theKey1))
426 return pNode1->Key2();
427 pNode1 = (IndexedDataMapNode*) pNode1->Next();
433 const TheItemType& FindFromKey(const TheKeyType& theKey1) const
435 #if !defined No_Exception && !defined No_Standard_NoSuchObject
437 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromKey");
439 IndexedDataMapNode * pNode1 =
440 (IndexedDataMapNode *) myData1[HashCode(theKey1,NbBuckets())];
443 if (IsEqual (pNode1->Key1(), theKey1))
444 return pNode1->Value();
445 pNode1 = (IndexedDataMapNode*) pNode1->Next();
447 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
448 return pNode1->Value();
452 TheItemType& ChangeFromKey (const TheKeyType& theKey1)
454 #if !defined No_Exception && !defined No_Standard_NoSuchObject
456 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
458 IndexedDataMapNode * pNode1 =
459 (IndexedDataMapNode *) myData1[HashCode(theKey1,NbBuckets())];
462 if (IsEqual (pNode1->Key1(), theKey1))
463 return pNode1->ChangeValue();
464 pNode1 = (IndexedDataMapNode*) pNode1->Next();
466 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
467 return pNode1->ChangeValue();
470 //! Clear data. If doReleaseMemory is false then the table of
471 //! buckets is not released and will be reused.
472 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
473 { Destroy (IndexedDataMapNode::delNode, this->myAllocator, doReleaseMemory); }
475 //! Clear data and reset allocator
476 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
479 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
480 NCollection_BaseAllocator::CommonBaseAllocator() );
484 ~NCollection_IndexedDataMap (void)
488 virtual Standard_Integer Size(void) const
492 // ----------- PRIVATE METHODS -----------
494 //! Creates Iterator for use on BaseCollection
495 virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
496 CreateIterator(void) const
497 { return *(new (this->IterAllocator()) Iterator(*this)); }
502 #pragma warning (pop)