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_BaseMap.hxx>
20 #include <NCollection_TListNode.hxx>
21 #include <Standard_TypeMismatch.hxx>
22 #include <Standard_NoSuchObject.hxx>
23 #include <NCollection_StlIterator.hxx>
24 #include <NCollection_DefaultHasher.hxx>
26 #include <Standard_OutOfRange.hxx>
29 * Purpose: An indexed map is used to store keys and to bind
30 * an index to them. Each new key stored in the map
31 * gets an index. Index are incremented as keys are
32 * stored in the map. A key can be found by the index
33 * and an index by the key. No key but the last can
34 * be removed so the indices are in the range 1..
35 * Extent. An Item is stored with each key.
37 * This class is similar to IndexedMap from
38 * NCollection with the Item as a new feature. Note
39 * the important difference on the operator (). In
40 * the IndexedMap this operator returns the Key. In
41 * the IndexedDataMap this operator returns the Item.
43 * See the class Map from NCollection for a
44 * discussion about the number of buckets.
47 template < class TheKeyType,
49 class Hasher = NCollection_DefaultHasher<TheKeyType> >
50 class NCollection_IndexedDataMap : public NCollection_BaseMap
52 //! Adaptation of the TListNode to the INDEXEDDatamap
54 class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
57 //! Constructor with 'Next'
58 IndexedDataMapNode (const TheKeyType& theKey1,
59 const Standard_Integer theKey2,
60 const TheItemType& theItem,
61 NCollection_ListNode* theNext1,
62 NCollection_ListNode* theNext2) :
63 NCollection_TListNode<TheItemType>(theItem,theNext1),
66 myNext2((IndexedDataMapNode*)theNext2)
70 TheKeyType& Key1 (void)
73 Standard_Integer& Key2 (void)
76 IndexedDataMapNode*& Next2 (void)
79 //! Static deleter to be passed to BaseList
80 static void delNode (NCollection_ListNode * theNode,
81 Handle(NCollection_BaseAllocator)& theAl)
83 ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
88 Standard_Integer myKey2;
89 IndexedDataMapNode * myNext2;
93 //! Implementation of the Iterator interface.
102 Iterator (const NCollection_IndexedDataMap& theMap)
103 : myMap ((NCollection_IndexedDataMap* )&theMap),
104 myNode (myMap->nodeFromIndex (1)),
106 //! Query if the end of collection is reached by iterator
107 Standard_Boolean More(void) const
108 { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
109 //! Make a step along the collection
112 myNode = myMap->nodeFromIndex (++myIndex);
115 const TheItemType& Value(void) const
117 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Value");
118 return myNode->Value();
120 //! ChangeValue access
121 TheItemType& ChangeValue(void) const
123 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::ChangeValue");
124 return myNode->ChangeValue();
127 const TheKeyType& Key() const
129 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Key");
130 return myNode->Key1();
132 //! Performs comparison of two iterators.
133 Standard_Boolean IsEqual (const Iterator& theOther) const
135 return myMap == theOther.myMap &&
136 myNode == theOther.myNode &&
137 myIndex == theOther.myIndex;
140 NCollection_IndexedDataMap* myMap; //!< Pointer to the map being iterated
141 IndexedDataMapNode* myNode; //!< Current node
142 Standard_Integer myIndex; //!< Current index
145 //! Shorthand for a regular iterator type.
146 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
148 //! Shorthand for a constant iterator type.
149 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
151 //! Returns an iterator pointing to the first element in the map.
152 iterator begin() const { return Iterator (*this); }
154 //! Returns an iterator referring to the past-the-end element in the map.
155 iterator end() const { return Iterator(); }
157 //! Returns a const iterator pointing to the first element in the map.
158 const_iterator cbegin() const { return Iterator (*this); }
160 //! Returns a const iterator referring to the past-the-end element in the map.
161 const_iterator cend() const { return Iterator(); }
164 // ---------- PUBLIC METHODS ------------
167 NCollection_IndexedDataMap (const Standard_Integer NbBuckets=1,
168 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
169 : NCollection_BaseMap (NbBuckets, Standard_False, theAllocator) {}
172 NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther)
173 : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator)
174 { *this = theOther; }
176 //! Exchange the content of two maps without re-allocations.
177 //! Notice that allocators will be swapped as well!
178 void Exchange (NCollection_IndexedDataMap& theOther)
180 this->exchangeMapsData (theOther);
184 //! This method does not change the internal allocator.
185 NCollection_IndexedDataMap& Assign (const NCollection_IndexedDataMap& theOther)
187 if (this == &theOther)
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;
209 //! Assignment operator
210 NCollection_IndexedDataMap& operator= (const NCollection_IndexedDataMap& theOther)
212 return Assign (theOther);
216 void ReSize (const Standard_Integer N)
218 NCollection_ListNode** ppNewData1 = NULL;
219 NCollection_ListNode** ppNewData2 = NULL;
220 Standard_Integer newBuck;
221 if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
225 IndexedDataMapNode *p, *q;
226 Standard_Integer i, iK1, iK2;
227 for (i = 0; i <= NbBuckets(); i++)
231 p = (IndexedDataMapNode *) myData1[i];
234 iK1 = Hasher::HashCode (p->Key1(), newBuck);
235 iK2 = ::HashCode (p->Key2(), newBuck);
236 q = (IndexedDataMapNode*) p->Next();
237 p->Next() = ppNewData1[iK1];
238 p->Next2() = (IndexedDataMapNode*)ppNewData2[iK2];
246 EndResize (N, newBuck, ppNewData1, ppNewData2);
251 Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
255 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
256 IndexedDataMapNode * pNode;
257 pNode = (IndexedDataMapNode *) myData1[iK1];
260 if (Hasher::IsEqual (pNode->Key1(), theKey1))
261 return pNode->Key2();
262 pNode = (IndexedDataMapNode *) pNode->Next();
265 Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
266 pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
267 myData1[iK1], myData2[iK2]);
268 myData1[iK1] = pNode;
269 myData2[iK2] = pNode;
274 Standard_Boolean Contains (const TheKeyType& theKey1) const
277 return Standard_False;
278 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
279 IndexedDataMapNode * pNode1;
280 pNode1 = (IndexedDataMapNode *) myData1[iK1];
283 if (Hasher::IsEqual(pNode1->Key1(), theKey1))
284 return Standard_True;
285 pNode1 = (IndexedDataMapNode *) pNode1->Next();
287 return Standard_False;
291 void Substitute (const Standard_Integer theIndex,
292 const TheKeyType& theKey1,
293 const TheItemType& theItem)
295 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(),
296 "NCollection_IndexedDataMap::Substitute : "
297 "Index is out of range");
299 IndexedDataMapNode * p;
300 // check if theKey1 is not already in the map
301 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
302 p = (IndexedDataMapNode *) myData1[iK1];
305 if (Hasher::IsEqual (p->Key1(), theKey1))
307 if (p->Key2() != theIndex)
309 throw Standard_DomainError ("NCollection_IndexedDataMap::Substitute : "
310 "Attempt to substitute existing key");
313 p->ChangeValue() = theItem;
316 p = (IndexedDataMapNode *) p->Next();
319 // Find the node for the index I
320 Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
321 p = (IndexedDataMapNode *) myData2[iK2];
324 if (p->Key2() == theIndex)
326 p = (IndexedDataMapNode*) p->Next2();
329 // remove the old key
330 Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
331 IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
333 myData1[iK] = (IndexedDataMapNode *) p->Next();
336 while (q->Next() != p)
337 q = (IndexedDataMapNode *) q->Next();
338 q->Next() = p->Next();
343 p->ChangeValue() = theItem;
344 p->Next() = myData1[iK1];
348 //! Swaps two elements with the given indices.
349 void Swap (const Standard_Integer theIndex1,
350 const Standard_Integer theIndex2)
352 Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent()
353 || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedDataMap::Swap");
355 if (theIndex1 == theIndex2)
360 const Standard_Integer aK1 = ::HashCode (theIndex1, NbBuckets());
361 const Standard_Integer aK2 = ::HashCode (theIndex2, NbBuckets());
363 IndexedDataMapNode* aP1 = (IndexedDataMapNode*) myData2[aK1];
364 IndexedDataMapNode* aP2 = (IndexedDataMapNode*) myData2[aK2];
366 if (aP1->Key2() == theIndex1)
368 myData2[aK1] = (IndexedDataMapNode *) aP1->Next2();
372 IndexedDataMapNode* aQ = aP1;
373 for (aP1 = aQ->Next2(); aP1->Key2() != theIndex1; aQ = aP1, aP1 = aQ->Next2()) { }
375 aQ->Next2() = aP1->Next2();
378 if (aP2->Key2() == theIndex2)
380 myData2[aK2] = (IndexedDataMapNode *) aP2->Next2();
384 IndexedDataMapNode* aQ = aP2;
385 for (aP2 = aQ->Next2(); aP2->Key2() != theIndex2; aQ = aP2, aP2 = aQ->Next2()) { }
387 aQ->Next2() = aP2->Next2();
390 std::swap (aP1->Key2(),
393 aP1->Next2() = (IndexedDataMapNode*) myData2[aK2];
396 aP2->Next2() = (IndexedDataMapNode*) myData2[aK1];
401 void RemoveLast (void)
403 Standard_OutOfRange_Raise_if (Extent() == 0, "NCollection_IndexedDataMap::RemoveLast");
405 IndexedDataMapNode * p, * q;
406 // Find the node for the last index and remove it
407 Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
408 p = (IndexedDataMapNode *) myData2[iK2];
412 if (p->Key2() == Extent())
415 p = (IndexedDataMapNode*) p->Next2();
418 myData2[iK2] = (IndexedDataMapNode *) p->Next2();
420 q->Next2() = p->Next2();
423 Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
424 q = (IndexedDataMapNode *) myData1[iK1];
426 myData1[iK1] = (IndexedDataMapNode *) p->Next();
429 while (q->Next() != p)
430 q = (IndexedDataMapNode *) q->Next();
431 q->Next() = p->Next();
433 p->~IndexedDataMapNode();
434 this->myAllocator->Free(p);
439 const TheKeyType& FindKey (const Standard_Integer theKey2) const
441 Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindKey");
443 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
446 throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindKey");
448 return aNode->Key1();
452 const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
454 Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindFromIndex");
456 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
459 throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindFromIndex");
461 return aNode->Value();
465 const TheItemType& operator() (const Standard_Integer theKey2) const
466 { return FindFromIndex (theKey2); }
469 TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
471 Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex");
473 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
476 throw Standard_NoSuchObject("NCollection_IndexedDataMap::ChangeFromIndex");
478 return aNode->ChangeValue();
482 TheItemType& operator() (const Standard_Integer theKey2)
483 { return ChangeFromIndex (theKey2); }
486 Standard_Integer FindIndex(const TheKeyType& theKey1) const
488 if (IsEmpty()) return 0;
489 IndexedDataMapNode * pNode1 =
490 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
493 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
494 return pNode1->Key2();
495 pNode1 = (IndexedDataMapNode*) pNode1->Next();
501 const TheItemType& FindFromKey(const TheKeyType& theKey1) const
503 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey");
505 IndexedDataMapNode * pNode1 =
506 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
509 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
510 return pNode1->Value();
511 pNode1 = (IndexedDataMapNode*) pNode1->Next();
513 throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindFromKey");
517 TheItemType& ChangeFromKey (const TheKeyType& theKey1)
519 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey");
521 IndexedDataMapNode * pNode1 =
522 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
525 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
526 return pNode1->ChangeValue();
527 pNode1 = (IndexedDataMapNode*) pNode1->Next();
529 throw Standard_NoSuchObject("NCollection_IndexedDataMap::ChangeFromKey");
532 //! Seek returns pointer to Item by Key. Returns
533 //! NULL if Key was not found.
534 const TheItemType* Seek(const TheKeyType& theKey1) const
536 return const_cast< NCollection_IndexedDataMap * >( this )->ChangeSeek(theKey1);
537 //NCollection_IndexedDataMap *pMap=(NCollection_IndexedDataMap *)this;
538 //return pMap->ChangeSeek(theKey1);
541 //! ChangeSeek returns modifiable pointer to Item by Key. Returns
542 //! NULL if Key was not found.
543 TheItemType* ChangeSeek (const TheKeyType& theKey1)
547 IndexedDataMapNode * pNode1 =
548 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
551 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
552 return &pNode1->ChangeValue();
553 pNode1 = (IndexedDataMapNode*) pNode1->Next();
559 //! Find value for key with copying.
560 //! @return true if key was found
561 Standard_Boolean FindFromKey (const TheKeyType& theKey1,
562 TheItemType& theValue) const
566 return Standard_False;
568 for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData1[Hasher::HashCode (theKey1, NbBuckets())];
569 aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next())
571 if (Hasher::IsEqual (aNode->Key1(), theKey1))
573 theValue = aNode->Value();
574 return Standard_True;
577 return Standard_False;
580 //! Clear data. If doReleaseMemory is false then the table of
581 //! buckets is not released and will be reused.
582 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
583 { Destroy (IndexedDataMapNode::delNode, doReleaseMemory); }
585 //! Clear data and reset allocator
586 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
589 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
590 NCollection_BaseAllocator::CommonBaseAllocator() );
594 virtual ~NCollection_IndexedDataMap (void)
598 Standard_Integer Size(void) const
602 // ----------- PRIVATE METHODS -----------
604 //! Find map node associated with specified index.
605 //! Return NULL if not found (exception-free internal implementation).
606 IndexedDataMapNode* nodeFromIndex (const Standard_Integer theKey2) const
612 for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[::HashCode (theKey2, NbBuckets())];
613 aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next2())
615 if (aNode->Key2() == theKey2)