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 const 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 NCollection_IndexedDataMap& Assign (const NCollection_IndexedDataMap& theOther)
186 if (this == &theOther)
189 Clear(theOther.myAllocator);
190 ReSize (theOther.Extent()-1);
192 for (i=1; i<=theOther.Extent(); i++)
194 TheKeyType aKey1 = theOther.FindKey(i);
195 TheItemType anItem = theOther.FindFromIndex(i);
196 Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
197 Standard_Integer iK2 = ::HashCode (i, NbBuckets());
198 IndexedDataMapNode * pNode =
199 new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
200 myData1[iK1], myData2[iK2]);
201 myData1[iK1] = pNode;
202 myData2[iK2] = pNode;
208 //! Assignment operator
209 NCollection_IndexedDataMap& operator= (const NCollection_IndexedDataMap& theOther)
211 return Assign (theOther);
215 void ReSize (const Standard_Integer N)
217 NCollection_ListNode** ppNewData1 = NULL;
218 NCollection_ListNode** ppNewData2 = NULL;
219 Standard_Integer newBuck;
220 if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
224 IndexedDataMapNode *p, *q;
225 Standard_Integer i, iK1, iK2;
226 for (i = 0; i <= NbBuckets(); i++)
230 p = (IndexedDataMapNode *) myData1[i];
233 iK1 = Hasher::HashCode (p->Key1(), newBuck);
234 iK2 = ::HashCode (p->Key2(), newBuck);
235 q = (IndexedDataMapNode*) p->Next();
236 p->Next() = ppNewData1[iK1];
237 p->Next2() = (IndexedDataMapNode*)ppNewData2[iK2];
245 EndResize (N, newBuck, ppNewData1, ppNewData2);
250 Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
254 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
255 IndexedDataMapNode * pNode;
256 pNode = (IndexedDataMapNode *) myData1[iK1];
259 if (Hasher::IsEqual (pNode->Key1(), theKey1))
260 return pNode->Key2();
261 pNode = (IndexedDataMapNode *) pNode->Next();
264 Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
265 pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
266 myData1[iK1], myData2[iK2]);
267 myData1[iK1] = pNode;
268 myData2[iK2] = pNode;
273 Standard_Boolean Contains (const TheKeyType& theKey1) const
276 return Standard_False;
277 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
278 IndexedDataMapNode * pNode1;
279 pNode1 = (IndexedDataMapNode *) myData1[iK1];
282 if (Hasher::IsEqual(pNode1->Key1(), theKey1))
283 return Standard_True;
284 pNode1 = (IndexedDataMapNode *) pNode1->Next();
286 return Standard_False;
290 void Substitute (const Standard_Integer theIndex,
291 const TheKeyType& theKey1,
292 const TheItemType& theItem)
294 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::Substitute");
296 IndexedDataMapNode * p;
297 // check if theKey1 is not already in the map
298 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
299 p = (IndexedDataMapNode *) myData1[iK1];
302 if (Hasher::IsEqual (p->Key1(), theKey1))
303 Standard_DomainError::Raise("NCollection_IndexedDataMap::Substitute");
304 p = (IndexedDataMapNode *) p->Next();
307 // Find the node for the index I
308 Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
309 p = (IndexedDataMapNode *) myData2[iK2];
312 if (p->Key2() == theIndex)
314 p = (IndexedDataMapNode*) p->Next2();
317 // remove the old key
318 Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
319 IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
321 myData1[iK] = (IndexedDataMapNode *) p->Next();
324 while (q->Next() != p)
325 q = (IndexedDataMapNode *) q->Next();
326 q->Next() = p->Next();
331 p->ChangeValue() = theItem;
332 p->Next() = myData1[iK1];
337 void RemoveLast (void)
339 Standard_OutOfRange_Raise_if (Extent() == 0, "NCollection_IndexedDataMap::RemoveLast");
341 IndexedDataMapNode * p, * q;
342 // Find the node for the last index and remove it
343 Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
344 p = (IndexedDataMapNode *) myData2[iK2];
348 if (p->Key2() == Extent())
351 p = (IndexedDataMapNode*) p->Next2();
354 myData2[iK2] = (IndexedDataMapNode *) p->Next2();
356 q->Next2() = p->Next2();
359 Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
360 q = (IndexedDataMapNode *) myData1[iK1];
362 myData1[iK1] = (IndexedDataMapNode *) p->Next();
365 while (q->Next() != p)
366 q = (IndexedDataMapNode *) q->Next();
367 q->Next() = p->Next();
369 p->~IndexedDataMapNode();
370 this->myAllocator->Free(p);
375 const TheKeyType& FindKey (const Standard_Integer theKey2) const
377 Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindKey");
379 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
382 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindKey");
384 return aNode->Key1();
388 const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
390 Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindFromIndex");
392 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
395 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromIndex");
397 return aNode->Value();
401 const TheItemType& operator() (const Standard_Integer theKey2) const
402 { return FindFromIndex (theKey2); }
405 TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
407 Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex");
409 IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
412 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::ChangeFromIndex");
414 return aNode->ChangeValue();
418 TheItemType& operator() (const Standard_Integer theKey2)
419 { return ChangeFromIndex (theKey2); }
422 Standard_Integer FindIndex(const TheKeyType& theKey1) const
424 if (IsEmpty()) return 0;
425 IndexedDataMapNode * pNode1 =
426 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
429 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
430 return pNode1->Key2();
431 pNode1 = (IndexedDataMapNode*) pNode1->Next();
437 const TheItemType& FindFromKey(const TheKeyType& theKey1) const
439 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey");
441 IndexedDataMapNode * pNode1 =
442 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
445 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
446 return pNode1->Value();
447 pNode1 = (IndexedDataMapNode*) pNode1->Next();
449 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
450 return pNode1->Value();
454 TheItemType& ChangeFromKey (const TheKeyType& theKey1)
456 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey");
458 IndexedDataMapNode * pNode1 =
459 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
462 if (Hasher::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 //! Find value for key with copying.
471 //! @return true if key was found
472 Standard_Boolean FindFromKey (const TheKeyType& theKey1,
473 TheItemType& theValue) const
477 return Standard_False;
479 for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData1[Hasher::HashCode (theKey1, NbBuckets())];
480 aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next())
482 if (Hasher::IsEqual (aNode->Key1(), theKey1))
484 theValue = aNode->Value();
485 return Standard_True;
488 return Standard_False;
491 //! Clear data. If doReleaseMemory is false then the table of
492 //! buckets is not released and will be reused.
493 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
494 { Destroy (IndexedDataMapNode::delNode, doReleaseMemory); }
496 //! Clear data and reset allocator
497 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
500 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
501 NCollection_BaseAllocator::CommonBaseAllocator() );
505 ~NCollection_IndexedDataMap (void)
509 Standard_Integer Size(void) const
513 // ----------- PRIVATE METHODS -----------
515 //! Find map node associated with specified index.
516 //! Return NULL if not found (exception-free internal implementation).
517 IndexedDataMapNode* nodeFromIndex (const Standard_Integer theKey2) const
523 for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[::HashCode (theKey2, NbBuckets())];
524 aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next2())
526 if (aNode->Key2() == theKey2)