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>
15 #include <NCollection_DefaultHasher.hxx>
17 #if !defined No_Exception && !defined No_Standard_OutOfRange
18 #include <Standard_OutOfRange.hxx>
22 // Disable the warning "operator new unmatched by delete"
23 #pragma warning (push)
24 #pragma warning (disable:4291)
28 * Purpose: An indexed map is used to store keys and to bind
29 * an index to them. Each new key stored in the map
30 * gets an index. Index are incremented as keys are
31 * stored in the map. A key can be found by the index
32 * and an index by the key. No key but the last can
33 * be removed so the indices are in the range 1..
34 * Extent. An Item is stored with each key.
36 * This class is similar to IndexedMap from
37 * NCollection with the Item as a new feature. Note
38 * the important difference on the operator (). In
39 * the IndexedMap this operator returns the Key. In
40 * the IndexedDataMap this operator returns the Item.
42 * See the class Map from NCollection for a
43 * discussion about the number of buckets.
46 template < class TheKeyType,
48 class Hasher = NCollection_DefaultHasher<TheKeyType> >
49 class NCollection_IndexedDataMap
50 : public NCollection_BaseCollection<TheItemType>,
51 public NCollection_BaseMap
53 //! Adaptation of the TListNode to the INDEXEDDatamap
55 class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
58 //! Constructor with 'Next'
59 IndexedDataMapNode (const TheKeyType& theKey1,
60 const Standard_Integer theKey2,
61 const TheItemType& theItem,
62 NCollection_ListNode* theNext1,
63 NCollection_ListNode* theNext2) :
64 NCollection_TListNode<TheItemType>(theItem,theNext1)
68 myNext2 = (IndexedDataMapNode *) theNext2;
71 TheKeyType& Key1 (void)
74 const Standard_Integer& Key2 (void)
77 IndexedDataMapNode*& Next2 (void)
80 //! Static deleter to be passed to BaseList
81 static void delNode (NCollection_ListNode * theNode,
82 Handle(NCollection_BaseAllocator)& theAl)
84 ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
89 Standard_Integer myKey2;
90 IndexedDataMapNode * myNext2;
94 //! Implementation of the Iterator interface.
95 class Iterator : public NCollection_BaseCollection<TheItemType>::Iterator
103 Iterator (const NCollection_IndexedDataMap& theMap) :
104 myMap((NCollection_IndexedDataMap *) &theMap),
106 //! Query if the end of collection is reached by iterator
107 virtual Standard_Boolean More(void) const
108 { return (myIndex <= myMap->Extent()); }
109 //! Make a step along the collection
110 virtual void Next(void)
113 virtual const TheItemType& Value(void) const
115 #if !defined No_Exception && !defined No_Standard_NoSuchObject
117 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::Value");
119 return myMap->FindFromIndex(myIndex);
121 //! ChangeValue access
122 virtual TheItemType& ChangeValue(void) const
124 #if !defined No_Exception && !defined No_Standard_NoSuchObject
126 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::ChangeValue");
128 return myMap->ChangeFromIndex(myIndex);
130 //! Operator new for allocating iterators
131 void* operator new(size_t theSize,
132 const Handle(NCollection_BaseAllocator)& theAllocator)
133 { return theAllocator->Allocate(theSize); }
136 NCollection_IndexedDataMap * myMap; //!< Pointer to the map being iterated
137 Standard_Integer myIndex; //!< Current index
141 // ---------- PUBLIC METHODS ------------
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) {}
150 NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther)
151 : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
152 NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
153 { *this = theOther; }
155 //! Assign another collection
156 virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
158 if (this == &theOther)
160 Standard_TypeMismatch::Raise("NCollection_IndexedDataMap::Assign");
164 NCollection_IndexedDataMap& operator=
165 (const NCollection_IndexedDataMap& theOther)
167 if (this == &theOther)
170 Clear(theOther.myAllocator);
171 ReSize (theOther.Extent()-1);
173 for (i=1; i<=theOther.Extent(); i++)
175 TheKeyType aKey1 = theOther.FindKey(i);
176 TheItemType anItem = theOther.FindFromIndex(i);
177 Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
178 Standard_Integer iK2 = ::HashCode (i, NbBuckets());
179 IndexedDataMapNode * pNode =
180 new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
181 myData1[iK1], myData2[iK2]);
182 myData1[iK1] = pNode;
183 myData2[iK2] = pNode;
190 void ReSize (const Standard_Integer N)
192 IndexedDataMapNode** ppNewData1 = NULL;
193 IndexedDataMapNode** ppNewData2 = NULL;
194 Standard_Integer newBuck;
195 if (BeginResize (N, newBuck,
196 (NCollection_ListNode**&)ppNewData1,
197 (NCollection_ListNode**&)ppNewData2,
202 IndexedDataMapNode *p, *q;
203 Standard_Integer i, iK1, iK2;
204 for (i = 0; i <= NbBuckets(); i++)
208 p = (IndexedDataMapNode *) myData1[i];
211 iK1 = Hasher::HashCode (p->Key1(), newBuck);
212 iK2 = ::HashCode (p->Key2(), newBuck);
213 q = (IndexedDataMapNode*) p->Next();
214 p->Next() = ppNewData1[iK1];
215 p->Next2() = ppNewData2[iK2];
224 (NCollection_ListNode**&)ppNewData1,
225 (NCollection_ListNode**&)ppNewData2,
231 Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
235 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
236 IndexedDataMapNode * pNode;
237 pNode = (IndexedDataMapNode *) myData1[iK1];
240 if (Hasher::IsEqual (pNode->Key1(), theKey1))
241 return pNode->Key2();
242 pNode = (IndexedDataMapNode *) pNode->Next();
245 Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
246 pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
247 myData1[iK1], myData2[iK2]);
248 myData1[iK1] = pNode;
249 myData2[iK2] = pNode;
254 Standard_Boolean Contains (const TheKeyType& theKey1) const
257 return Standard_False;
258 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
259 IndexedDataMapNode * pNode1;
260 pNode1 = (IndexedDataMapNode *) myData1[iK1];
263 if (Hasher::IsEqual(pNode1->Key1(), theKey1))
264 return Standard_True;
265 pNode1 = (IndexedDataMapNode *) pNode1->Next();
267 return Standard_False;
271 void Substitute (const Standard_Integer theIndex,
272 const TheKeyType& theKey1,
273 const TheItemType& theItem)
275 #if !defined No_Exception && !defined No_Standard_OutOfRange
276 if (theIndex < 1 || theIndex > Extent())
277 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::Substitute");
279 IndexedDataMapNode * p;
280 // check if theKey1 is not already in the map
281 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
282 p = (IndexedDataMapNode *) myData1[iK1];
285 if (Hasher::IsEqual (p->Key1(), theKey1))
286 Standard_DomainError::Raise("NCollection_IndexedDataMap::Substitute");
287 p = (IndexedDataMapNode *) p->Next();
290 // Find the node for the index I
291 Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
292 p = (IndexedDataMapNode *) myData2[iK2];
295 if (p->Key2() == theIndex)
297 p = (IndexedDataMapNode*) p->Next2();
300 // remove the old key
301 Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
302 IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
304 myData1[iK] = (IndexedDataMapNode *) p->Next();
307 while (q->Next() != p)
308 q = (IndexedDataMapNode *) q->Next();
309 q->Next() = p->Next();
314 p->ChangeValue() = theItem;
315 p->Next() = myData1[iK1];
320 void RemoveLast (void)
322 #if !defined No_Exception && !defined No_Standard_OutOfRange
324 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::RemoveLast");
326 IndexedDataMapNode * p, * q;
327 // Find the node for the last index and remove it
328 Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
329 p = (IndexedDataMapNode *) myData2[iK2];
333 if (p->Key2() == Extent())
336 p = (IndexedDataMapNode*) p->Next2();
339 myData2[iK2] = (IndexedDataMapNode *) p->Next2();
341 q->Next2() = p->Next2();
344 Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
345 q = (IndexedDataMapNode *) myData1[iK1];
347 myData1[iK1] = (IndexedDataMapNode *) p->Next();
350 while (q->Next() != p)
351 q = (IndexedDataMapNode *) q->Next();
352 q->Next() = p->Next();
354 p->~IndexedDataMapNode();
355 this->myAllocator->Free(p);
360 const TheKeyType& FindKey (const Standard_Integer theKey2) const
362 #if !defined No_Exception && !defined No_Standard_OutOfRange
363 if (theKey2 < 1 || theKey2 > Extent())
364 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindKey");
366 IndexedDataMapNode * pNode2 =
367 (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
370 if (pNode2->Key2() == theKey2)
371 return pNode2->Key1();
372 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
374 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindKey");
375 return pNode2->Key1(); // This for compiler
379 const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
381 #if !defined No_Exception && !defined No_Standard_OutOfRange
382 if (theKey2 < 1 || theKey2 > Extent())
383 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindFromIndex");
385 IndexedDataMapNode * pNode2 =
386 (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
389 if (pNode2->Key2() == theKey2)
390 return pNode2->Value();
391 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
393 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
394 return pNode2->Value(); // This for compiler
398 const TheItemType& operator() (const Standard_Integer theKey2) const
399 { return FindFromIndex (theKey2); }
402 TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
404 #if !defined No_Exception && !defined No_Standard_OutOfRange
405 if (theKey2 < 1 || theKey2 > Extent())
406 Standard_OutOfRange::Raise("NCollection_IndexedDataMap::ChangeFromIndex");
408 IndexedDataMapNode * pNode2 =
409 (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
412 if (pNode2->Key2() == theKey2)
413 return pNode2->ChangeValue();
414 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
416 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
417 return pNode2->ChangeValue(); // This for compiler
421 TheItemType& operator() (const Standard_Integer theKey2)
422 { return ChangeFromIndex (theKey2); }
425 Standard_Integer FindIndex(const TheKeyType& theKey1) const
427 if (IsEmpty()) return 0;
428 IndexedDataMapNode * pNode1 =
429 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
432 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
433 return pNode1->Key2();
434 pNode1 = (IndexedDataMapNode*) pNode1->Next();
440 const TheItemType& FindFromKey(const TheKeyType& theKey1) const
442 #if !defined No_Exception && !defined No_Standard_NoSuchObject
444 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromKey");
446 IndexedDataMapNode * pNode1 =
447 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
450 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
451 return pNode1->Value();
452 pNode1 = (IndexedDataMapNode*) pNode1->Next();
454 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
455 return pNode1->Value();
459 TheItemType& ChangeFromKey (const TheKeyType& theKey1)
461 #if !defined No_Exception && !defined No_Standard_NoSuchObject
463 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
465 IndexedDataMapNode * pNode1 =
466 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
469 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
470 return pNode1->ChangeValue();
471 pNode1 = (IndexedDataMapNode*) pNode1->Next();
473 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
474 return pNode1->ChangeValue();
477 //! Clear data. If doReleaseMemory is false then the table of
478 //! buckets is not released and will be reused.
479 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
480 { Destroy (IndexedDataMapNode::delNode, this->myAllocator, doReleaseMemory); }
482 //! Clear data and reset allocator
483 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
486 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
487 NCollection_BaseAllocator::CommonBaseAllocator() );
491 ~NCollection_IndexedDataMap (void)
495 virtual Standard_Integer Size(void) const
499 // ----------- PRIVATE METHODS -----------
501 //! Creates Iterator for use on BaseCollection
502 virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
503 CreateIterator(void) const
504 { return *(new (this->IterAllocator()) Iterator(*this)); }
509 #pragma warning (pop)