1 // Created on: 2002-04-24
2 // Created by: Alexander KARTOMIN (akm)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef NCollection_IndexedDataMap_HeaderFile
17 #define NCollection_IndexedDataMap_HeaderFile
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>
25 #include <NCollection_DefaultHasher.hxx>
27 #if !defined No_Exception && !defined No_Standard_OutOfRange
28 #include <Standard_OutOfRange.hxx>
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.
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.
46 * See the class Map from NCollection for a
47 * discussion about the number of buckets.
50 template < class TheKeyType,
52 class Hasher = NCollection_DefaultHasher<TheKeyType> >
53 class NCollection_IndexedDataMap
54 : public NCollection_BaseCollection<TheItemType>,
55 public NCollection_BaseMap
57 //! Adaptation of the TListNode to the INDEXEDDatamap
59 class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
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)
72 myNext2 = (IndexedDataMapNode *) theNext2;
75 TheKeyType& Key1 (void)
78 const Standard_Integer& Key2 (void)
81 IndexedDataMapNode*& Next2 (void)
84 //! Static deleter to be passed to BaseList
85 static void delNode (NCollection_ListNode * theNode,
86 Handle(NCollection_BaseAllocator)& theAl)
88 ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
93 Standard_Integer myKey2;
94 IndexedDataMapNode * myNext2;
98 //! Implementation of the Iterator interface.
99 class Iterator : public NCollection_BaseCollection<TheItemType>::Iterator
102 //! Empty constructor
107 Iterator (const NCollection_IndexedDataMap& theMap)
108 : myMap ((NCollection_IndexedDataMap* )&theMap),
109 myNode (myMap->nodeFromIndex (1)),
111 //! Query if the end of collection is reached by iterator
112 virtual Standard_Boolean More(void) const
113 { return (myIndex <= myMap->Extent()); }
114 //! Make a step along the collection
115 virtual void Next(void)
117 myNode = myMap->nodeFromIndex (++myIndex);
120 virtual const TheItemType& Value(void) const
122 #if !defined No_Exception && !defined No_Standard_NoSuchObject
124 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::Value");
126 return myNode->Value();
128 //! ChangeValue access
129 virtual TheItemType& ChangeValue(void) const
131 #if !defined No_Exception && !defined No_Standard_NoSuchObject
133 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::ChangeValue");
135 return myNode->ChangeValue();
138 const TheKeyType& Key() const
140 #if !defined No_Exception && !defined No_Standard_NoSuchObject
142 Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Key");
144 return myNode->Key1();
147 NCollection_IndexedDataMap* myMap; //!< Pointer to the map being iterated
148 IndexedDataMapNode* myNode; //!< Current node
149 Standard_Integer myIndex; //!< Current index
153 // ---------- PUBLIC METHODS ------------
156 NCollection_IndexedDataMap (const Standard_Integer NbBuckets=1,
157 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
158 : NCollection_BaseCollection<TheItemType>(theAllocator),
159 NCollection_BaseMap (NbBuckets, Standard_False) {}
162 NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther)
163 : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
164 NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
165 { *this = theOther; }
167 //! Assign another collection
168 virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
170 if (this == &theOther)
172 Standard_TypeMismatch::Raise("NCollection_IndexedDataMap::Assign");
175 //! Exchange the content of two maps without re-allocations.
176 //! Notice that allocators will be swapped as well!
177 void Exchange (NCollection_IndexedDataMap& theOther)
179 this->exchangeAllocators (theOther);
180 this->exchangeMapsData (theOther);
184 NCollection_IndexedDataMap& operator=
185 (const NCollection_IndexedDataMap& theOther)
187 if (this == &theOther)
190 Clear(theOther.myAllocator);
191 ReSize (theOther.Extent()-1);
193 for (i=1; i<=theOther.Extent(); i++)
195 TheKeyType aKey1 = theOther.FindKey(i);
196 TheItemType anItem = theOther.FindFromIndex(i);
197 Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
198 Standard_Integer iK2 = ::HashCode (i, NbBuckets());
199 IndexedDataMapNode * pNode =
200 new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
201 myData1[iK1], myData2[iK2]);
202 myData1[iK1] = pNode;
203 myData2[iK2] = pNode;
210 void ReSize (const Standard_Integer N)
212 NCollection_ListNode** ppNewData1 = NULL;
213 NCollection_ListNode** ppNewData2 = NULL;
214 Standard_Integer newBuck;
215 if (BeginResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator))
219 IndexedDataMapNode *p, *q;
220 Standard_Integer i, iK1, iK2;
221 for (i = 0; i <= NbBuckets(); i++)
225 p = (IndexedDataMapNode *) myData1[i];
228 iK1 = Hasher::HashCode (p->Key1(), newBuck);
229 iK2 = ::HashCode (p->Key2(), newBuck);
230 q = (IndexedDataMapNode*) p->Next();
231 p->Next() = ppNewData1[iK1];
232 p->Next2() = (IndexedDataMapNode*)ppNewData2[iK2];
240 EndResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator);
245 Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
249 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
250 IndexedDataMapNode * pNode;
251 pNode = (IndexedDataMapNode *) myData1[iK1];
254 if (Hasher::IsEqual (pNode->Key1(), theKey1))
255 return pNode->Key2();
256 pNode = (IndexedDataMapNode *) pNode->Next();
259 Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
260 pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
261 myData1[iK1], myData2[iK2]);
262 myData1[iK1] = pNode;
263 myData2[iK2] = pNode;
268 Standard_Boolean Contains (const TheKeyType& theKey1) const
271 return Standard_False;
272 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
273 IndexedDataMapNode * pNode1;
274 pNode1 = (IndexedDataMapNode *) myData1[iK1];
277 if (Hasher::IsEqual(pNode1->Key1(), theKey1))
278 return Standard_True;
279 pNode1 = (IndexedDataMapNode *) pNode1->Next();
281 return Standard_False;
285 void Substitute (const Standard_Integer theIndex,
286 const TheKeyType& theKey1,
287 const TheItemType& theItem)
289 #if !defined No_Exception && !defined No_Standard_OutOfRange
290 if (theIndex < 1 || theIndex > Extent())
291 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::Substitute");
293 IndexedDataMapNode * p;
294 // check if theKey1 is not already in the map
295 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
296 p = (IndexedDataMapNode *) myData1[iK1];
299 if (Hasher::IsEqual (p->Key1(), theKey1))
300 Standard_DomainError::Raise("NCollection_IndexedDataMap::Substitute");
301 p = (IndexedDataMapNode *) p->Next();
304 // Find the node for the index I
305 Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
306 p = (IndexedDataMapNode *) myData2[iK2];
309 if (p->Key2() == theIndex)
311 p = (IndexedDataMapNode*) p->Next2();
314 // remove the old key
315 Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
316 IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
318 myData1[iK] = (IndexedDataMapNode *) p->Next();
321 while (q->Next() != p)
322 q = (IndexedDataMapNode *) q->Next();
323 q->Next() = p->Next();
328 p->ChangeValue() = theItem;
329 p->Next() = myData1[iK1];
334 void RemoveLast (void)
336 #if !defined No_Exception && !defined No_Standard_OutOfRange
338 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::RemoveLast");
340 IndexedDataMapNode * p, * q;
341 // Find the node for the last index and remove it
342 Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
343 p = (IndexedDataMapNode *) myData2[iK2];
347 if (p->Key2() == Extent())
350 p = (IndexedDataMapNode*) p->Next2();
353 myData2[iK2] = (IndexedDataMapNode *) p->Next2();
355 q->Next2() = p->Next2();
358 Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
359 q = (IndexedDataMapNode *) myData1[iK1];
361 myData1[iK1] = (IndexedDataMapNode *) p->Next();
364 while (q->Next() != p)
365 q = (IndexedDataMapNode *) q->Next();
366 q->Next() = p->Next();
368 p->~IndexedDataMapNode();
369 this->myAllocator->Free(p);
374 const TheKeyType& FindKey (const Standard_Integer theKey2) const
376 #if !defined No_Exception && !defined No_Standard_OutOfRange
377 if (theKey2 < 1 || theKey2 > Extent())
378 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindKey");
380 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
383 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindKey");
385 return aNode->Key1();
389 const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
391 #if !defined No_Exception && !defined No_Standard_OutOfRange
392 if (theKey2 < 1 || theKey2 > Extent())
393 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindFromIndex");
395 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
398 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromIndex");
400 return aNode->Value();
404 const TheItemType& operator() (const Standard_Integer theKey2) const
405 { return FindFromIndex (theKey2); }
408 TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
410 #if !defined No_Exception && !defined No_Standard_OutOfRange
411 if (theKey2 < 1 || theKey2 > Extent())
412 Standard_OutOfRange::Raise("NCollection_IndexedDataMap::ChangeFromIndex");
414 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
417 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::ChangeFromIndex");
419 return aNode->ChangeValue();
423 TheItemType& operator() (const Standard_Integer theKey2)
424 { return ChangeFromIndex (theKey2); }
427 Standard_Integer FindIndex(const TheKeyType& theKey1) const
429 if (IsEmpty()) return 0;
430 IndexedDataMapNode * pNode1 =
431 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
434 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
435 return pNode1->Key2();
436 pNode1 = (IndexedDataMapNode*) pNode1->Next();
442 const TheItemType& FindFromKey(const TheKeyType& theKey1) const
444 #if !defined No_Exception && !defined No_Standard_NoSuchObject
446 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromKey");
448 IndexedDataMapNode * pNode1 =
449 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
452 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
453 return pNode1->Value();
454 pNode1 = (IndexedDataMapNode*) pNode1->Next();
456 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
457 return pNode1->Value();
461 TheItemType& ChangeFromKey (const TheKeyType& theKey1)
463 #if !defined No_Exception && !defined No_Standard_NoSuchObject
465 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
467 IndexedDataMapNode * pNode1 =
468 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
471 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
472 return pNode1->ChangeValue();
473 pNode1 = (IndexedDataMapNode*) pNode1->Next();
475 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
476 return pNode1->ChangeValue();
479 //! Find value for key with copying.
480 //! @return true if key was found
481 Standard_Boolean FindFromKey (const TheKeyType& theKey1,
482 TheItemType& theValue) const
486 return Standard_False;
488 for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData1[Hasher::HashCode (theKey1, NbBuckets())];
489 aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next())
491 if (Hasher::IsEqual (aNode->Key1(), theKey1))
493 theValue = aNode->Value();
494 return Standard_True;
497 return Standard_False;
500 //! Clear data. If doReleaseMemory is false then the table of
501 //! buckets is not released and will be reused.
502 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
503 { Destroy (IndexedDataMapNode::delNode, this->myAllocator, doReleaseMemory); }
505 //! Clear data and reset allocator
506 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
509 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
510 NCollection_BaseAllocator::CommonBaseAllocator() );
514 ~NCollection_IndexedDataMap (void)
518 virtual Standard_Integer Size(void) const
522 // ----------- PRIVATE METHODS -----------
524 //! Creates Iterator for use on BaseCollection
525 virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
526 CreateIterator(void) const
527 { return *(new (this->IterAllocator()) Iterator(*this)); }
529 //! Find map node associated with specified index.
530 //! Return NULL if not found (exception-free internal implementation).
531 IndexedDataMapNode* nodeFromIndex (const Standard_Integer theKey2) const
537 for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[::HashCode (theKey2, NbBuckets())];
538 aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next2())
540 if (aNode->Key2() == theKey2)