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_BaseMap.hxx>
20 #include <NCollection_TListNode.hxx>
21 #include <NCollection_StlIterator.hxx>
22 #include <Standard_NoSuchObject.hxx>
23 #include <Standard_ImmutableObject.hxx>
25 #include <NCollection_DefaultHasher.hxx>
27 #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..Extent.
36 * See the class Map from NCollection for a
37 * discussion about the number of buckets.
40 template < class TheKeyType,
41 class Hasher = NCollection_DefaultHasher<TheKeyType> >
42 class NCollection_IndexedMap : public NCollection_BaseMap
44 // **************** Adaptation of the TListNode to the INDEXEDmap
46 class IndexedMapNode : public NCollection_TListNode<TheKeyType>
49 //! Constructor with 'Next'
50 IndexedMapNode (const TheKeyType& theKey1,
51 const Standard_Integer theKey2,
52 NCollection_ListNode* theNext1,
53 NCollection_ListNode* theNext2) :
54 NCollection_TListNode<TheKeyType> (theKey1, theNext1),
56 myNext2((IndexedMapNode*)theNext2)
60 TheKeyType& Key1 (void)
61 { return this->ChangeValue(); }
63 const Standard_Integer& Key2 (void)
66 IndexedMapNode*& Next2 (void)
69 //! Static deleter to be passed to BaseList
70 static void delNode (NCollection_ListNode * theNode,
71 Handle(NCollection_BaseAllocator)& theAl)
73 ((IndexedMapNode *) theNode)->~IndexedMapNode();
78 Standard_Integer myKey2;
79 IndexedMapNode * myNext2;
83 // **************** Implementation of the Iterator interface.
92 Iterator (const NCollection_IndexedMap& theMap) :
93 myMap((NCollection_IndexedMap *) &theMap),
95 //! Query if the end of collection is reached by iterator
96 Standard_Boolean More(void) const
97 { return (myMap != NULL) && (myIndex <= myMap->Extent()); }
98 //! Make a step along the collection
102 const TheKeyType& Value(void) const
104 Standard_NoSuchObject_Raise_if(!More(), "NCollection_IndexedMap::Iterator::Value");
105 return myMap->FindKey(myIndex);
107 //! Value change access denied - use Substitute
108 TheKeyType& ChangeValue(void) const
110 Standard_ImmutableObject::Raise ("impossible to ChangeValue");
111 return * (TheKeyType *) NULL; // This for compiler
113 //! Performs comparison of two iterators.
114 Standard_Boolean IsEqual (const Iterator& theOther) const
116 return myMap == theOther.myMap && myIndex == theOther.myIndex;
120 NCollection_IndexedMap * myMap; // Pointer to the map being iterated
121 Standard_Integer myIndex; // Current index
124 //! Shorthand for a constant iterator type.
125 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheKeyType, true> const_iterator;
127 //! Returns a const iterator pointing to the first element in the map.
128 const_iterator cbegin() const { return Iterator (*this); }
130 //! Returns a const iterator referring to the past-the-end element in the map.
131 const_iterator cend() const { return Iterator(); }
134 // ---------- PUBLIC METHODS ------------
137 NCollection_IndexedMap (const Standard_Integer NbBuckets=1,
138 const Handle(NCollection_BaseAllocator)& theAllocator=0L)
139 : NCollection_BaseMap (NbBuckets, Standard_False, theAllocator) {}
142 NCollection_IndexedMap (const NCollection_IndexedMap& theOther)
143 : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator)
144 { *this = theOther; }
146 //! Exchange the content of two maps without re-allocations.
147 //! Notice that allocators will be swapped as well!
148 void Exchange (NCollection_IndexedMap& theOther)
150 this->exchangeMapsData (theOther);
154 //! This method does not change the internal allocator.
155 NCollection_IndexedMap& Assign (const NCollection_IndexedMap& theOther)
157 if (this == &theOther)
161 ReSize (theOther.Extent()-1);
162 Standard_Integer i, iLength=theOther.Extent();
163 for (i=1; i<=iLength; i++)
165 TheKeyType aKey1 = theOther(i);
166 Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
167 Standard_Integer iK2 = ::HashCode (i, NbBuckets());
168 IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i,
171 myData1[iK1] = pNode;
172 myData2[iK2] = pNode;
178 //! Assignment operator
179 NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther)
181 return Assign (theOther);
185 void ReSize (const Standard_Integer N)
187 NCollection_ListNode** ppNewData1 = NULL;
188 NCollection_ListNode** ppNewData2 = NULL;
189 Standard_Integer newBuck;
190 if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
194 IndexedMapNode *p, *q;
195 Standard_Integer i, iK1, iK2;
196 for (i = 0; i <= NbBuckets(); i++)
200 p = (IndexedMapNode *) myData1[i];
203 iK1 =Hasher::HashCode(p->Key1(), newBuck);
204 q = (IndexedMapNode*) p->Next();
205 p->Next() = ppNewData1[iK1];
209 iK2 = ::HashCode (p->Key2(), newBuck);
210 p->Next2() = (IndexedMapNode*)ppNewData2[iK2];
218 EndResize (N, newBuck, ppNewData1, ppNewData2);
223 Standard_Integer Add (const TheKeyType& theKey1)
227 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
228 IndexedMapNode * pNode;
229 pNode = (IndexedMapNode *) myData1[iK1];
232 if (Hasher::IsEqual (pNode->Key1(), theKey1))
233 return pNode->Key2();
234 pNode = (IndexedMapNode *) pNode->Next();
237 Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
238 pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(),
239 myData1[iK1], myData2[iK2]);
240 myData1[iK1] = pNode;
241 myData2[iK2] = pNode;
246 Standard_Boolean Contains (const TheKeyType& theKey1) const
249 return Standard_False;
250 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
251 IndexedMapNode * pNode1;
252 pNode1 = (IndexedMapNode *) myData1[iK1];
255 if (Hasher::IsEqual(pNode1->Key1(), theKey1))
256 return Standard_True;
257 pNode1 = (IndexedMapNode *) pNode1->Next();
259 return Standard_False;
263 void Substitute (const Standard_Integer theIndex,
264 const TheKeyType& theKey1)
266 Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::Substitute");
269 // check if theKey1 is not already in the map
270 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
271 p = (IndexedMapNode *) myData1[iK1];
274 if (Hasher::IsEqual (p->Key1(), theKey1))
275 Standard_DomainError::Raise("NCollection_IndexedMap::Substitute");
276 p = (IndexedMapNode *) p->Next();
279 // Find the node for the index I
280 Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
281 p = (IndexedMapNode *) myData2[iK2];
284 if (p->Key2() == theIndex)
286 p = (IndexedMapNode*) p->Next2();
289 // remove the old key
290 Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
291 IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
293 myData1[iK] = (IndexedMapNode *) p->Next();
296 while (q->Next() != p)
297 q = (IndexedMapNode *) q->Next();
298 q->Next() = p->Next();
303 p->Next() = myData1[iK1];
308 void RemoveLast (void)
310 Standard_OutOfRange_Raise_if (Extent() == 0, "NCollection_IndexedMap::RemoveLast");
312 IndexedMapNode * p, * q;
313 // Find the node for the last index and remove it
314 Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
315 p = (IndexedMapNode *) myData2[iK2];
319 if (p->Key2() == Extent())
322 p = (IndexedMapNode*) p->Next2();
325 myData2[iK2] = (IndexedMapNode *) p->Next2();
327 q->Next2() = p->Next2();
330 Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
331 q = (IndexedMapNode *) myData1[iK1];
333 myData1[iK1] = (IndexedMapNode *) p->Next();
336 while (q->Next() != p)
337 q = (IndexedMapNode *) q->Next();
338 q->Next() = p->Next();
340 p->~IndexedMapNode();
341 this->myAllocator->Free(p);
346 const TheKeyType& FindKey (const Standard_Integer theKey2) const
348 Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedMap::FindKey");
350 IndexedMapNode * pNode2 =
351 (IndexedMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
354 if (pNode2->Key2() == theKey2)
355 return pNode2->Key1();
356 pNode2 = (IndexedMapNode*) pNode2->Next2();
358 Standard_NoSuchObject::Raise("NCollection_IndexedMap::FindKey");
359 return pNode2->Key1(); // This for compiler
363 const TheKeyType& operator() (const Standard_Integer theKey2) const
364 { return FindKey (theKey2); }
367 Standard_Integer FindIndex(const TheKeyType& theKey1) const
369 if (IsEmpty()) return 0;
370 IndexedMapNode * pNode1 =
371 (IndexedMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
374 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
375 return pNode1->Key2();
376 pNode1 = (IndexedMapNode*) pNode1->Next();
381 //! Clear data. If doReleaseMemory is false then the table of
382 //! buckets is not released and will be reused.
383 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
384 { Destroy (IndexedMapNode::delNode, doReleaseMemory); }
386 //! Clear data and reset allocator
387 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
390 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
391 NCollection_BaseAllocator::CommonBaseAllocator() );
395 ~NCollection_IndexedMap (void)
399 Standard_Integer Size(void) const