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>
30 * Purpose: An indexed map is used to store keys and to bind
31 * an index to them. Each new key stored in the map
32 * gets an index. Index are incremented as keys are
33 * stored in the map. A key can be found by the index
34 * and an index by the key. No key but the last can
35 * be removed so the indices are in the range 1..
36 * Extent. An Item is stored with each key.
38 * This class is similar to IndexedMap from
39 * NCollection with the Item as a new feature. Note
40 * the important difference on the operator (). In
41 * the IndexedMap this operator returns the Key. In
42 * the IndexedDataMap this operator returns the Item.
44 * See the class Map from NCollection for a
45 * discussion about the number of buckets.
48 template < class TheKeyType,
50 class Hasher = NCollection_DefaultHasher<TheKeyType> >
51 class NCollection_IndexedDataMap : public NCollection_BaseMap
54 //! STL-compliant typedef for key type
55 typedef TheKeyType key_type;
56 //! STL-compliant typedef for value type
57 typedef TheItemType value_type;
58 typedef Hasher hasher;
61 //! Adaptation of the TListNode to the INDEXEDDatamap
62 class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
65 //! Constructor with 'Next'
66 IndexedDataMapNode (const TheKeyType& theKey1,
67 const Standard_Integer theIndex,
68 const TheItemType& theItem,
69 NCollection_ListNode* theNext1)
70 : NCollection_TListNode<TheItemType>(theItem,theNext1),
74 //! Constructor with 'Next'
75 IndexedDataMapNode (TheKeyType&& theKey1,
76 const Standard_Integer theIndex,
77 const TheItemType& theItem,
78 NCollection_ListNode* theNext1)
79 : NCollection_TListNode<TheItemType>(theItem,theNext1),
80 myKey1 (std::forward<TheKeyType>(theKey1)),
83 //! Constructor with 'Next'
84 IndexedDataMapNode (const TheKeyType& theKey1,
85 const Standard_Integer theIndex,
86 TheItemType&& theItem,
87 NCollection_ListNode* theNext1)
88 : NCollection_TListNode<TheItemType>(std::forward<TheItemType>(theItem),theNext1),
92 //! Constructor with 'Next'
93 IndexedDataMapNode (TheKeyType&& theKey1,
94 const Standard_Integer theIndex,
95 TheItemType&& theItem,
96 NCollection_ListNode* theNext1)
97 : NCollection_TListNode<TheItemType>(std::forward<TheItemType>(theItem),theNext1),
98 myKey1 (std::forward<TheKeyType>(theKey1)),
102 TheKeyType& Key1() { return myKey1; }
104 Standard_Integer& Index() { return myIndex; }
106 //! Static deleter to be passed to BaseList
107 static void delNode (NCollection_ListNode * theNode,
108 Handle(NCollection_BaseAllocator)& theAl)
110 ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
111 theAl->Free(theNode);
115 Standard_Integer myIndex;
119 //! Implementation of the Iterator interface.
123 //! Empty constructor
129 Iterator (const NCollection_IndexedDataMap& theMap)
130 : myMap ((NCollection_IndexedDataMap*)&theMap),
133 //! Query if the end of collection is reached by iterator
134 Standard_Boolean More(void) const
135 { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
137 //! Make a step along the collection
142 const TheItemType& Value(void) const
144 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Value");
145 return myMap->FindFromIndex(myIndex);
148 //! ChangeValue access
149 TheItemType& ChangeValue(void) const
151 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::ChangeValue");
152 return myMap->ChangeFromIndex(myIndex);
156 const TheKeyType& Key() const
158 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedDataMap::Iterator::Key");
159 return myMap->FindKey(myIndex);
162 //! Performs comparison of two iterators.
163 Standard_Boolean IsEqual (const Iterator& theOther) const
165 return myMap == theOther.myMap &&
166 myIndex == theOther.myIndex;
170 NCollection_IndexedDataMap* myMap; //!< Pointer to current node
171 Standard_Integer myIndex; //!< Current index
174 //! Shorthand for a regular iterator type.
175 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
177 //! Shorthand for a constant iterator type.
178 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
180 //! Returns an iterator pointing to the first element in the map.
181 iterator begin() const { return Iterator (*this); }
183 //! Returns an iterator referring to the past-the-end element in the map.
184 iterator end() const { return Iterator(); }
186 //! Returns a const iterator pointing to the first element in the map.
187 const_iterator cbegin() const { return Iterator (*this); }
189 //! Returns a const iterator referring to the past-the-end element in the map.
190 const_iterator cend() const { return Iterator(); }
193 // ---------- PUBLIC METHODS ------------
195 //! Empty constructor.
196 NCollection_IndexedDataMap() : NCollection_BaseMap (1, true, Handle(NCollection_BaseAllocator)()) {}
199 explicit NCollection_IndexedDataMap (const Standard_Integer theNbBuckets,
200 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
201 : NCollection_BaseMap (theNbBuckets, true, theAllocator) {}
204 NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther)
205 : NCollection_BaseMap (theOther.NbBuckets(), true, theOther.myAllocator)
206 { *this = theOther; }
209 NCollection_IndexedDataMap(NCollection_IndexedDataMap&& theOther) noexcept :
210 NCollection_BaseMap(std::forward<NCollection_BaseMap>(theOther))
213 //! Exchange the content of two maps without re-allocations.
214 //! Notice that allocators will be swapped as well!
215 void Exchange (NCollection_IndexedDataMap& theOther)
217 this->exchangeMapsData (theOther);
221 //! This method does not change the internal allocator.
222 NCollection_IndexedDataMap& Assign (const NCollection_IndexedDataMap& theOther)
224 if (this == &theOther)
228 Standard_Integer anExt = theOther.Extent();
231 ReSize (anExt-1); //mySize is same after resize
232 for (Standard_Integer anIndexIter = 1; anIndexIter <= anExt; ++anIndexIter)
234 const TheKeyType& aKey1 = theOther.FindKey (anIndexIter);
235 const TheItemType& anItem = theOther.FindFromIndex(anIndexIter);
236 const size_t iK1 = HashCode (aKey1, NbBuckets());
237 IndexedDataMapNode* pNode = new (this->myAllocator) IndexedDataMapNode (aKey1, anIndexIter, anItem, myData1[iK1]);
238 myData1[iK1] = pNode;
239 myData2[anIndexIter - 1] = pNode;
246 //! Assignment operator
247 NCollection_IndexedDataMap& operator= (const NCollection_IndexedDataMap& theOther)
249 return Assign (theOther);
253 NCollection_IndexedDataMap& operator= (NCollection_IndexedDataMap&& theOther) noexcept
255 if (this == &theOther)
257 exchangeMapsData(theOther);
262 void ReSize (const Standard_Integer N)
264 NCollection_ListNode** ppNewData1 = NULL;
265 NCollection_ListNode** ppNewData2 = NULL;
266 Standard_Integer newBuck;
267 if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
271 for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter)
273 if (myData1[aBucketIter])
275 IndexedDataMapNode* p = (IndexedDataMapNode *) myData1[aBucketIter];
278 const size_t iK1 = HashCode (p->Key1(), newBuck);
279 IndexedDataMapNode* q = (IndexedDataMapNode* )p->Next();
280 p->Next() = ppNewData1[iK1];
287 EndResize (N, newBuck, ppNewData1, (NCollection_ListNode**)
288 Standard::Reallocate(myData2, (newBuck + 1) * sizeof(NCollection_ListNode*)));
292 //! Returns the Index of already bound Key or appends new Key with specified Item value.
293 //! @param theKey1 Key to search (and to bind, if it was not bound already)
294 //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound
295 //! @return index of Key
296 Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
302 IndexedDataMapNode* aNode;
304 if (lookup(theKey1, aNode, aHash))
306 return aNode->Index();
308 const Standard_Integer aNewIndex = Increment();
309 aNode = new (this->myAllocator) IndexedDataMapNode (theKey1, aNewIndex, theItem, myData1[aHash]);
310 myData1[aHash] = aNode;
311 myData2[aNewIndex - 1] = aNode;
315 //! Returns the Index of already bound Key or appends new Key with specified Item value.
316 //! @param theKey1 Key to search (and to bind, if it was not bound already)
317 //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound
318 //! @return index of Key
319 Standard_Integer Add (TheKeyType&& theKey1, const TheItemType& theItem)
325 IndexedDataMapNode* aNode;
327 if (lookup(theKey1, aNode, aHash))
329 return aNode->Index();
331 const Standard_Integer aNewIndex = Increment();
332 aNode = new (this->myAllocator) IndexedDataMapNode (std::forward<TheKeyType>(theKey1), aNewIndex, theItem, myData1[aHash]);
333 myData1[aHash] = aNode;
334 myData2[aNewIndex - 1] = aNode;
338 //! Returns the Index of already bound Key or appends new Key with specified Item value.
339 //! @param theKey1 Key to search (and to bind, if it was not bound already)
340 //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound
341 //! @return index of Key
342 Standard_Integer Add (const TheKeyType& theKey1, TheItemType&& theItem)
348 IndexedDataMapNode* aNode;
350 if (lookup(theKey1, aNode, aHash))
352 return aNode->Index();
354 const Standard_Integer aNewIndex = Increment();
355 aNode = new (this->myAllocator) IndexedDataMapNode (theKey1, aNewIndex, std::forward<TheItemType>(theItem), myData1[aHash]);
356 myData1[aHash] = aNode;
357 myData2[aNewIndex - 1] = aNode;
361 //! Returns the Index of already bound Key or appends new Key with specified Item value.
362 //! @param theKey1 Key to search (and to bind, if it was not bound already)
363 //! @param theItem Item value to set for newly bound Key; ignored if Key was already bound
364 //! @return index of Key
365 Standard_Integer Add (TheKeyType&& theKey1, TheItemType&& theItem)
371 IndexedDataMapNode* aNode;
373 if (lookup(theKey1, aNode, aHash))
375 return aNode->Index();
377 const Standard_Integer aNewIndex = Increment();
378 aNode = new (this->myAllocator) IndexedDataMapNode (std::forward<TheKeyType>(theKey1), aNewIndex,
379 std::forward<TheItemType>(theItem), myData1[aHash]);
380 myData1[aHash] = aNode;
381 myData2[aNewIndex - 1] = aNode;
386 Standard_Boolean Contains (const TheKeyType& theKey1) const
388 IndexedDataMapNode* aNode;
389 if (lookup(theKey1, aNode))
397 void Substitute (const Standard_Integer theIndex,
398 const TheKeyType& theKey1,
399 const TheItemType& theItem)
401 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(),
402 "NCollection_IndexedDataMap::Substitute : "
403 "Index is out of range");
405 // check if theKey1 is not already in the map
407 IndexedDataMapNode* aNode;
408 if (lookup(theKey1, aNode, aHash))
410 if (aNode->Index() != theIndex)
412 throw Standard_DomainError("NCollection_IndexedDataMap::Substitute : "
413 "Attempt to substitute existing key");
415 aNode->Key1() = theKey1;
416 aNode->ChangeValue() = theItem;
420 // Find the node for the index I
421 aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
423 // remove the old key
424 const size_t iK = HashCode (aNode->Key1(), NbBuckets());
425 IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
427 myData1[iK] = (IndexedDataMapNode *)aNode->Next();
430 while (q->Next() != aNode)
431 q = (IndexedDataMapNode *) q->Next();
432 q->Next() = aNode->Next();
436 aNode->Key1() = theKey1;
437 aNode->ChangeValue() = theItem;
438 aNode->Next() = myData1[aHash];
439 myData1[aHash] = aNode;
442 //! Swaps two elements with the given indices.
443 void Swap (const Standard_Integer theIndex1,
444 const Standard_Integer theIndex2)
446 Standard_OutOfRange_Raise_if (theIndex1 < 1 || theIndex1 > Extent()
447 || theIndex2 < 1 || theIndex2 > Extent(), "NCollection_IndexedDataMap::Swap");
449 if (theIndex1 == theIndex2)
454 IndexedDataMapNode* aP1 = (IndexedDataMapNode* )myData2[theIndex1 - 1];
455 IndexedDataMapNode* aP2 = (IndexedDataMapNode* )myData2[theIndex2 - 1];
456 std::swap (aP1->Index(), aP2->Index());
457 myData2[theIndex2 - 1] = aP1;
458 myData2[theIndex1 - 1] = aP2;
462 void RemoveLast (void)
464 const Standard_Integer aLastIndex = Extent();
465 Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedDataMap::RemoveLast");
467 // Find the node for the last index and remove it
468 IndexedDataMapNode* p = (IndexedDataMapNode* )myData2[aLastIndex - 1];
469 myData2[aLastIndex - 1] = NULL;
472 const size_t iK1 = HashCode (p->Key1(), NbBuckets());
473 IndexedDataMapNode* q = (IndexedDataMapNode *) myData1[iK1];
475 myData1[iK1] = (IndexedDataMapNode *) p->Next();
478 while (q->Next() != p)
479 q = (IndexedDataMapNode *) q->Next();
480 q->Next() = p->Next();
482 p->~IndexedDataMapNode();
483 this->myAllocator->Free(p);
487 //! Remove the key of the given index.
488 //! Caution! The index of the last key can be changed.
489 void RemoveFromIndex(const Standard_Integer theIndex)
491 const Standard_Integer aLastInd = Extent();
492 Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > aLastInd, "NCollection_IndexedDataMap::Remove");
493 if (theIndex != aLastInd)
495 Swap (theIndex, aLastInd);
500 //! Remove the given key.
501 //! Caution! The index of the last key can be changed.
502 void RemoveKey(const TheKeyType& theKey1)
504 Standard_Integer anIndToRemove = FindIndex(theKey1);
505 if (anIndToRemove > 0) {
506 RemoveFromIndex(anIndToRemove);
511 const TheKeyType& FindKey (const Standard_Integer theIndex) const
513 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindKey");
514 IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
515 return aNode->Key1();
519 const TheItemType& FindFromIndex (const Standard_Integer theIndex) const
521 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindFromIndex");
522 IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
523 return aNode->Value();
527 const TheItemType& operator() (const Standard_Integer theIndex) const { return FindFromIndex (theIndex); }
530 TheItemType& ChangeFromIndex (const Standard_Integer theIndex)
532 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex");
533 IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
534 return aNode->ChangeValue();
538 TheItemType& operator() (const Standard_Integer theIndex) { return ChangeFromIndex (theIndex); }
541 Standard_Integer FindIndex(const TheKeyType& theKey1) const
543 IndexedDataMapNode* aNode;
544 if (lookup(theKey1, aNode))
546 return aNode->Index();
552 const TheItemType& FindFromKey(const TheKeyType& theKey1) const
554 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey");
555 IndexedDataMapNode* aNode;
556 if (lookup(theKey1, aNode))
558 return aNode->Value();
560 throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindFromKey");
564 TheItemType& ChangeFromKey (const TheKeyType& theKey1)
566 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey");
567 IndexedDataMapNode* aNode;
568 if (lookup(theKey1, aNode))
570 return aNode->ChangeValue();
572 throw Standard_NoSuchObject("NCollection_IndexedDataMap::ChangeFromKey");
575 //! Seek returns pointer to Item by Key. Returns
576 //! NULL if Key was not found.
577 const TheItemType* Seek(const TheKeyType& theKey1) const
579 return const_cast< NCollection_IndexedDataMap * >( this )->ChangeSeek(theKey1);
582 //! ChangeSeek returns modifiable pointer to Item by Key. Returns
583 //! NULL if Key was not found.
584 TheItemType* ChangeSeek (const TheKeyType& theKey1)
586 IndexedDataMapNode* aNode;
587 if (lookup(theKey1, aNode))
589 return &aNode->ChangeValue();
594 //! Find value for key with copying.
595 //! @return true if key was found
596 Standard_Boolean FindFromKey (const TheKeyType& theKey1,
597 TheItemType& theValue) const
599 IndexedDataMapNode* aNode;
600 if (lookup(theKey1, aNode))
602 theValue = aNode->Value();
603 return Standard_True;
605 return Standard_False;
608 //! Clear data. If doReleaseMemory is false then the table of
609 //! buckets is not released and will be reused.
610 void Clear(const Standard_Boolean doReleaseMemory = Standard_False)
611 { Destroy (IndexedDataMapNode::delNode, doReleaseMemory); }
613 //! Clear data and reset allocator
614 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
616 Clear(theAllocator != this->myAllocator);
617 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
618 NCollection_BaseAllocator::CommonBaseAllocator() );
622 virtual ~NCollection_IndexedDataMap (void)
626 Standard_Integer Size(void) const
631 //! Lookup for particular key in map.
632 //! @param[in] theKey key to compute hash
633 //! @param[out] theNode the detected node with equal key. Can be null.
634 //! @param[out] theHash computed bounded hash code for current key.
635 //! @return true if key is found
636 Standard_Boolean lookup(const TheKeyType& theKey, IndexedDataMapNode*& theNode, size_t& theHash) const
638 theHash = HashCode(theKey, NbBuckets());
640 return Standard_False; // Not found
641 for (theNode = (IndexedDataMapNode*)myData1[theHash];
642 theNode; theNode = (IndexedDataMapNode*)theNode->Next())
644 if (IsEqual(theNode->Key1(), theKey))
645 return Standard_True;
647 return Standard_False; // Not found
650 //! Lookup for particular key in map.
651 //! @param[in] theKey key to compute hash
652 //! @param[out] theNode the detected node with equal key. Can be null.
653 //! @return true if key is found
654 Standard_Boolean lookup(const TheKeyType& theKey, IndexedDataMapNode*& theNode) const
657 return Standard_False; // Not found
658 for (theNode = (IndexedDataMapNode*)myData1[HashCode(theKey, NbBuckets())];
659 theNode; theNode = (IndexedDataMapNode*)theNode->Next())
661 if (IsEqual(theNode->Key1(), theKey))
663 return Standard_True;
666 return Standard_False; // Not found
669 bool IsEqual(const TheKeyType& theKey1,
670 const TheKeyType& theKey2) const
672 return myHasher(theKey1, theKey2);
675 size_t HashCode(const TheKeyType& theKey,
676 const int theUpperBound) const
678 return myHasher(theKey) % theUpperBound + 1;