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_IndexedMap_HeaderFile
17 #define NCollection_IndexedMap_HeaderFile
19 #include <NCollection_BaseCollection.hxx>
20 #include <NCollection_BaseMap.hxx>
21 #include <NCollection_TListNode.hxx>
22 #include <NCollection_StlIterator.hxx>
23 #include <Standard_NoSuchObject.hxx>
24 #include <Standard_ImmutableObject.hxx>
26 #include <NCollection_DefaultHasher.hxx>
28 #if !defined No_Exception && !defined No_Standard_OutOfRange
29 #include <Standard_OutOfRange.hxx>
33 * Purpose: An indexed map is used to store keys and to bind
34 * an index to them. Each new key stored in the map
35 * gets an index. Index are incremented as keys are
36 * stored in the map. A key can be found by the index
37 * and an index by the key. No key but the last can
38 * be removed so the indices are in the range 1..Extent.
39 * See the class Map from NCollection for a
40 * discussion about the number of buckets.
43 template < class TheKeyType,
44 class Hasher = NCollection_DefaultHasher<TheKeyType> >
45 class NCollection_IndexedMap
46 : public NCollection_BaseCollection<TheKeyType>,
47 public NCollection_BaseMap
49 // **************** Adaptation of the TListNode to the INDEXEDmap
51 class IndexedMapNode : public NCollection_TListNode<TheKeyType>
54 //! Constructor with 'Next'
55 IndexedMapNode (const TheKeyType& theKey1,
56 const Standard_Integer theKey2,
57 NCollection_ListNode* theNext1,
58 NCollection_ListNode* theNext2) :
59 NCollection_TListNode<TheKeyType> (theKey1, theNext1)
62 myNext2 = (IndexedMapNode *) theNext2;
65 TheKeyType& Key1 (void)
66 { return this->ChangeValue(); }
68 const Standard_Integer& Key2 (void)
71 IndexedMapNode*& Next2 (void)
74 //! Static deleter to be passed to BaseList
75 static void delNode (NCollection_ListNode * theNode,
76 Handle(NCollection_BaseAllocator)& theAl)
78 ((IndexedMapNode *) theNode)->~IndexedMapNode();
83 Standard_Integer myKey2;
84 IndexedMapNode * myNext2;
88 // **************** Implementation of the Iterator interface.
90 : public NCollection_BaseCollection<TheKeyType>::Iterator
98 Iterator (const NCollection_IndexedMap& theMap) :
99 myMap((NCollection_IndexedMap *) &theMap),
101 //! Query if the end of collection is reached by iterator
102 virtual Standard_Boolean More(void) const
103 { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
104 //! Make a step along the collection
105 virtual void Next(void)
108 virtual const TheKeyType& Value(void) const
110 #if !defined No_Exception && !defined No_Standard_NoSuchObject
112 Standard_NoSuchObject::Raise("NCollection_IndexedMap::Iterator::Value");
114 return myMap->FindKey(myIndex);
116 //! Value change access denied - use Substitute
117 virtual TheKeyType& ChangeValue(void) const
119 Standard_ImmutableObject::Raise ("impossible to ChangeValue");
120 return * (TheKeyType *) NULL; // This for compiler
122 //! Performs comparison of two iterators.
123 virtual Standard_Boolean IsEqual (const Iterator& theOther) const
125 return myMap == theOther.myMap && myIndex == theOther.myIndex;
129 NCollection_IndexedMap * myMap; // Pointer to the map being iterated
130 Standard_Integer myIndex; // Current index
133 //! Shorthand for a constant iterator type.
134 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheKeyType, true> const_iterator;
136 //! Returns a const iterator pointing to the first element in the map.
137 const_iterator cbegin() const { return Iterator (*this); }
139 //! Returns a const iterator referring to the past-the-end element in the map.
140 const_iterator cend() const { return Iterator(); }
143 // ---------- PUBLIC METHODS ------------
146 NCollection_IndexedMap (const Standard_Integer NbBuckets=1,
147 const Handle(NCollection_BaseAllocator)& theAllocator=0L) :
148 NCollection_BaseCollection<TheKeyType>(theAllocator),
149 NCollection_BaseMap (NbBuckets, Standard_False) {}
152 NCollection_IndexedMap (const NCollection_IndexedMap& theOther) :
153 NCollection_BaseCollection<TheKeyType>(theOther.myAllocator),
154 NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
155 { *this = theOther; }
157 //! Assign another collection
158 virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther)
160 if (this == &theOther)
163 ReSize (theOther.Size()-1);
164 TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& anIter =
165 theOther.CreateIterator();
166 for (; anIter.More(); anIter.Next())
170 //! Exchange the content of two maps without re-allocations.
171 //! Notice that allocators will be swapped as well!
172 void Exchange (NCollection_IndexedMap& theOther)
174 this->exchangeAllocators (theOther);
175 this->exchangeMapsData (theOther);
179 NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther)
181 if (this == &theOther)
184 Clear(theOther.myAllocator);
185 ReSize (theOther.Extent()-1);
186 Standard_Integer i, iLength=theOther.Extent();
187 for (i=1; i<=iLength; i++)
189 TheKeyType aKey1 = theOther(i);
190 Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
191 Standard_Integer iK2 = ::HashCode (i, NbBuckets());
192 IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i,
195 myData1[iK1] = pNode;
196 myData2[iK2] = pNode;
203 void ReSize (const Standard_Integer N)
205 NCollection_ListNode** ppNewData1 = NULL;
206 NCollection_ListNode** ppNewData2 = NULL;
207 Standard_Integer newBuck;
208 if (BeginResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator))
212 IndexedMapNode *p, *q;
213 Standard_Integer i, iK1, iK2;
214 for (i = 0; i <= NbBuckets(); i++)
218 p = (IndexedMapNode *) myData1[i];
221 iK1 =Hasher::HashCode(p->Key1(), newBuck);
222 q = (IndexedMapNode*) p->Next();
223 p->Next() = ppNewData1[iK1];
227 iK2 = ::HashCode (p->Key2(), newBuck);
228 p->Next2() = (IndexedMapNode*)ppNewData2[iK2];
236 EndResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator);
241 Standard_Integer Add (const TheKeyType& theKey1)
245 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
246 IndexedMapNode * pNode;
247 pNode = (IndexedMapNode *) myData1[iK1];
250 if (Hasher::IsEqual (pNode->Key1(), theKey1))
251 return pNode->Key2();
252 pNode = (IndexedMapNode *) pNode->Next();
255 Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
256 pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(),
257 myData1[iK1], myData2[iK2]);
258 myData1[iK1] = pNode;
259 myData2[iK2] = pNode;
264 Standard_Boolean Contains (const TheKeyType& theKey1) const
267 return Standard_False;
268 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
269 IndexedMapNode * pNode1;
270 pNode1 = (IndexedMapNode *) myData1[iK1];
273 if (Hasher::IsEqual(pNode1->Key1(), theKey1))
274 return Standard_True;
275 pNode1 = (IndexedMapNode *) pNode1->Next();
277 return Standard_False;
281 void Substitute (const Standard_Integer theIndex,
282 const TheKeyType& theKey1)
284 #if !defined No_Exception && !defined No_Standard_OutOfRange
285 if (theIndex < 1 || theIndex > Extent())
286 Standard_OutOfRange::Raise ("NCollection_IndexedMap::Substitute");
289 // check if theKey1 is not already in the map
290 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
291 p = (IndexedMapNode *) myData1[iK1];
294 if (Hasher::IsEqual (p->Key1(), theKey1))
295 Standard_DomainError::Raise("NCollection_IndexedMap::Substitute");
296 p = (IndexedMapNode *) p->Next();
299 // Find the node for the index I
300 Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
301 p = (IndexedMapNode *) myData2[iK2];
304 if (p->Key2() == theIndex)
306 p = (IndexedMapNode*) p->Next2();
309 // remove the old key
310 Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
311 IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
313 myData1[iK] = (IndexedMapNode *) p->Next();
316 while (q->Next() != p)
317 q = (IndexedMapNode *) q->Next();
318 q->Next() = p->Next();
323 p->Next() = myData1[iK1];
328 void RemoveLast (void)
330 #if !defined No_Exception && !defined No_Standard_OutOfRange
332 Standard_OutOfRange::Raise ("NCollection_IndexedMap::RemoveLast");
334 IndexedMapNode * p, * q;
335 // Find the node for the last index and remove it
336 Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
337 p = (IndexedMapNode *) myData2[iK2];
341 if (p->Key2() == Extent())
344 p = (IndexedMapNode*) p->Next2();
347 myData2[iK2] = (IndexedMapNode *) p->Next2();
349 q->Next2() = p->Next2();
352 Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
353 q = (IndexedMapNode *) myData1[iK1];
355 myData1[iK1] = (IndexedMapNode *) p->Next();
358 while (q->Next() != p)
359 q = (IndexedMapNode *) q->Next();
360 q->Next() = p->Next();
362 p->~IndexedMapNode();
363 this->myAllocator->Free(p);
368 const TheKeyType& FindKey (const Standard_Integer theKey2) const
370 #if !defined No_Exception && !defined No_Standard_OutOfRange
371 if (theKey2 < 1 || theKey2 > Extent())
372 Standard_OutOfRange::Raise ("NCollection_IndexedMap::FindKey");
374 IndexedMapNode * pNode2 =
375 (IndexedMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
378 if (pNode2->Key2() == theKey2)
379 return pNode2->Key1();
380 pNode2 = (IndexedMapNode*) pNode2->Next2();
382 Standard_NoSuchObject::Raise("NCollection_IndexedMap::FindKey");
383 return pNode2->Key1(); // This for compiler
387 const TheKeyType& operator() (const Standard_Integer theKey2) const
388 { return FindKey (theKey2); }
391 Standard_Integer FindIndex(const TheKeyType& theKey1) const
393 if (IsEmpty()) return 0;
394 IndexedMapNode * pNode1 =
395 (IndexedMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
398 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
399 return pNode1->Key2();
400 pNode1 = (IndexedMapNode*) pNode1->Next();
405 //! Clear data. If doReleaseMemory is false then the table of
406 //! buckets is not released and will be reused.
407 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
408 { Destroy (IndexedMapNode::delNode, this->myAllocator, doReleaseMemory); }
410 //! Clear data and reset allocator
411 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
414 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
415 NCollection_BaseAllocator::CommonBaseAllocator() );
419 ~NCollection_IndexedMap (void)
423 virtual Standard_Integer Size(void) const
427 // ----------- PRIVATE METHODS -----------
429 //! Creates Iterator for use on BaseCollection
430 virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator&
431 CreateIterator(void) const
432 { return *(new (this->IterAllocator()) Iterator(*this)); }