0024252: GCC warnings on breakage of strict-aliasing rules
[occt.git] / src / NCollection / NCollection_IndexedMap.hxx
CommitLineData
b311480e 1// Created on: 2002-04-24
2// Created by: Alexander KARTOMIN (akm)
973c2be1 3// Copyright (c) 2002-2014 OPEN CASCADE SAS
b311480e 4//
973c2be1 5// This file is part of Open CASCADE Technology software library.
b311480e 6//
973c2be1 7// This library is free software; you can redistribute it and / or modify it
8// under the terms of the GNU Lesser General Public 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.
b311480e 12//
973c2be1 13// Alternatively, this file may be used under the terms of Open CASCADE
14// commercial license or contractual agreement.
b311480e 15
7fd59977 16#ifndef NCollection_IndexedMap_HeaderFile
17#define NCollection_IndexedMap_HeaderFile
18
19#include <NCollection_BaseCollection.hxx>
20#include <NCollection_BaseMap.hxx>
21#include <NCollection_TListNode.hxx>
22#include <Standard_NoSuchObject.hxx>
23#include <Standard_ImmutableObject.hxx>
24
9991c9c2 25#include <NCollection_DefaultHasher.hxx>
26
7fd59977 27#if !defined No_Exception && !defined No_Standard_OutOfRange
28#include <Standard_OutOfRange.hxx>
29#endif
30
7fd59977 31/**
32 * Purpose: An indexed map is used to store keys and to bind
33 * an index to them. Each new key stored in the map
34 * gets an index. Index are incremented as keys are
35 * stored in the map. A key can be found by the index
36 * and an index by the key. No key but the last can
37 * be removed so the indices are in the range 1..Extent.
38 * See the class Map from NCollection for a
39 * discussion about the number of buckets.
40 */
9991c9c2 41
42template < class TheKeyType,
43 class Hasher = NCollection_DefaultHasher<TheKeyType> >
44 class NCollection_IndexedMap
7fd59977 45 : public NCollection_BaseCollection<TheKeyType>,
46 public NCollection_BaseMap
47{
48 // **************** Adaptation of the TListNode to the INDEXEDmap
49 private:
50 class IndexedMapNode : public NCollection_TListNode<TheKeyType>
51 {
52 public:
53 //! Constructor with 'Next'
54 IndexedMapNode (const TheKeyType& theKey1,
55 const Standard_Integer theKey2,
56 NCollection_ListNode* theNext1,
57 NCollection_ListNode* theNext2) :
58 NCollection_TListNode<TheKeyType> (theKey1, theNext1)
59 {
60 myKey2 = theKey2;
61 myNext2 = (IndexedMapNode *) theNext2;
62 }
63 //! Key1
64 TheKeyType& Key1 (void)
65 { return this->ChangeValue(); }
66 //! Key2
67 const Standard_Integer& Key2 (void)
68 { return myKey2; }
69 //! Next2
70 IndexedMapNode*& Next2 (void)
71 { return myNext2; }
72
73 //! Static deleter to be passed to BaseList
74 static void delNode (NCollection_ListNode * theNode,
75 Handle(NCollection_BaseAllocator)& theAl)
76 {
77 ((IndexedMapNode *) theNode)->~IndexedMapNode();
78 theAl->Free(theNode);
79 }
80
81 private:
82 Standard_Integer myKey2;
83 IndexedMapNode * myNext2;
84 };
85
86 public:
87 // **************** Implementation of the Iterator interface.
88 class Iterator
89 : public NCollection_BaseCollection<TheKeyType>::Iterator
90 {
91 public:
92 //! Empty constructor
93 Iterator (void) :
94 myMap(NULL),
95 myIndex(0) {}
96 //! Constructor
97 Iterator (const NCollection_IndexedMap& theMap) :
98 myMap((NCollection_IndexedMap *) &theMap),
99 myIndex(1) {}
100 //! Query if the end of collection is reached by iterator
101 virtual Standard_Boolean More(void) const
102 { return (myIndex <= myMap->Extent()); }
103 //! Make a step along the collection
104 virtual void Next(void)
105 { myIndex++; }
106 //! Value access
107 virtual const TheKeyType& Value(void) const
108 {
109#if !defined No_Exception && !defined No_Standard_NoSuchObject
110 if (!More())
111 Standard_NoSuchObject::Raise("NCollection_IndexedMap::Iterator::Value");
112#endif
113 return myMap->FindKey(myIndex);
114 }
115 //! Value change access denied - use Substitute
116 virtual TheKeyType& ChangeValue(void) const
117 {
118 Standard_ImmutableObject::Raise ("impossible to ChangeValue");
119 return * (TheKeyType *) NULL; // This for compiler
120 }
121
7fd59977 122 private:
123 NCollection_IndexedMap * myMap; // Pointer to the map being iterated
124 Standard_Integer myIndex; // Current index
125 };
126
127 public:
128 // ---------- PUBLIC METHODS ------------
129
130 //! Constructor
131 NCollection_IndexedMap (const Standard_Integer NbBuckets=1,
132 const Handle(NCollection_BaseAllocator)& theAllocator=0L) :
133 NCollection_BaseCollection<TheKeyType>(theAllocator),
134 NCollection_BaseMap (NbBuckets, Standard_False) {}
135
136 //! Copy constructor
137 NCollection_IndexedMap (const NCollection_IndexedMap& theOther) :
138 NCollection_BaseCollection<TheKeyType>(theOther.myAllocator),
139 NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
140 { *this = theOther; }
141
142 //! Assign another collection
143 virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther)
144 {
145 if (this == &theOther)
146 return;
147 Clear();
148 ReSize (theOther.Size()-1);
149 TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& anIter =
150 theOther.CreateIterator();
151 for (; anIter.More(); anIter.Next())
152 Add(anIter.Value());
153 }
154
ab2db9a5 155 //! Exchange the content of two maps without re-allocations.
156 //! Notice that allocators will be swapped as well!
157 void Exchange (NCollection_IndexedMap& theOther)
158 {
159 this->exchangeAllocators (theOther);
160 this->exchangeMapsData (theOther);
161 }
162
7fd59977 163 //! = another map
164 NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther)
165 {
166 if (this == &theOther)
167 return *this;
168
169 Clear(theOther.myAllocator);
170 ReSize (theOther.Extent()-1);
171 Standard_Integer i, iLength=theOther.Extent();
172 for (i=1; i<=iLength; i++)
173 {
174 TheKeyType aKey1 = theOther(i);
9991c9c2 175 Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
176 Standard_Integer iK2 = ::HashCode (i, NbBuckets());
7fd59977 177 IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i,
178 myData1[iK1],
179 myData2[iK2]);
180 myData1[iK1] = pNode;
181 myData2[iK2] = pNode;
182 Increment();
183 }
184 return *this;
185 }
186
187 //! ReSize
188 void ReSize (const Standard_Integer N)
189 {
fd03ee4b 190 NCollection_ListNode** ppNewData1 = NULL;
191 NCollection_ListNode** ppNewData2 = NULL;
7fd59977 192 Standard_Integer newBuck;
fd03ee4b 193 if (BeginResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator))
7fd59977 194 {
195 if (myData1)
196 {
197 IndexedMapNode *p, *q;
198 Standard_Integer i, iK1, iK2;
199 for (i = 0; i <= NbBuckets(); i++)
200 {
201 if (myData1[i])
202 {
203 p = (IndexedMapNode *) myData1[i];
204 while (p)
205 {
9991c9c2 206 iK1 =Hasher::HashCode(p->Key1(), newBuck);
7fd59977 207 q = (IndexedMapNode*) p->Next();
208 p->Next() = ppNewData1[iK1];
209 ppNewData1[iK1] = p;
210 if (p->Key2() > 0)
211 {
9991c9c2 212 iK2 = ::HashCode (p->Key2(), newBuck);
fd03ee4b 213 p->Next2() = (IndexedMapNode*)ppNewData2[iK2];
7fd59977 214 ppNewData2[iK2] = p;
215 }
216 p = q;
217 }
218 }
219 }
220 }
fd03ee4b 221 EndResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator);
7fd59977 222 }
223 }
224
225 //! Add
226 Standard_Integer Add (const TheKeyType& theKey1)
227 {
228 if (Resizable())
229 ReSize(Extent());
9991c9c2 230 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
7fd59977 231 IndexedMapNode * pNode;
232 pNode = (IndexedMapNode *) myData1[iK1];
233 while (pNode)
234 {
9991c9c2 235 if (Hasher::IsEqual (pNode->Key1(), theKey1))
7fd59977 236 return pNode->Key2();
237 pNode = (IndexedMapNode *) pNode->Next();
238 }
239 Increment();
9991c9c2 240 Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
7fd59977 241 pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(),
242 myData1[iK1], myData2[iK2]);
243 myData1[iK1] = pNode;
244 myData2[iK2] = pNode;
245 return Extent();
246 }
247
248 //! Contains
249 Standard_Boolean Contains (const TheKeyType& theKey1) const
250 {
251 if (IsEmpty())
252 return Standard_False;
9991c9c2 253 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
7fd59977 254 IndexedMapNode * pNode1;
255 pNode1 = (IndexedMapNode *) myData1[iK1];
256 while (pNode1)
257 {
9991c9c2 258 if (Hasher::IsEqual(pNode1->Key1(), theKey1))
7fd59977 259 return Standard_True;
260 pNode1 = (IndexedMapNode *) pNode1->Next();
261 }
262 return Standard_False;
263 }
264
265 //! Substitute
266 void Substitute (const Standard_Integer theIndex,
267 const TheKeyType& theKey1)
268 {
269#if !defined No_Exception && !defined No_Standard_OutOfRange
270 if (theIndex < 1 || theIndex > Extent())
271 Standard_OutOfRange::Raise ("NCollection_IndexedMap::Substitute");
272#endif
273 IndexedMapNode * p;
274 // check if theKey1 is not already in the map
9991c9c2 275 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
7fd59977 276 p = (IndexedMapNode *) myData1[iK1];
277 while (p)
278 {
9991c9c2 279 if (Hasher::IsEqual (p->Key1(), theKey1))
7fd59977 280 Standard_DomainError::Raise("NCollection_IndexedMap::Substitute");
281 p = (IndexedMapNode *) p->Next();
282 }
283
284 // Find the node for the index I
9991c9c2 285 Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
7fd59977 286 p = (IndexedMapNode *) myData2[iK2];
287 while (p)
288 {
289 if (p->Key2() == theIndex)
290 break;
291 p = (IndexedMapNode*) p->Next2();
292 }
293
294 // remove the old key
9991c9c2 295 Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
7fd59977 296 IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
297 if (q == p)
298 myData1[iK] = (IndexedMapNode *) p->Next();
299 else
300 {
301 while (q->Next() != p)
302 q = (IndexedMapNode *) q->Next();
303 q->Next() = p->Next();
304 }
305
306 // update the node
307 p->Key1() = theKey1;
308 p->Next() = myData1[iK1];
309 myData1[iK1] = p;
310 }
311
312 //! RemoveLast
313 void RemoveLast (void)
314 {
315#if !defined No_Exception && !defined No_Standard_OutOfRange
316 if (Extent() == 0)
317 Standard_OutOfRange::Raise ("NCollection_IndexedMap::RemoveLast");
318#endif
319 IndexedMapNode * p, * q;
320 // Find the node for the last index and remove it
9991c9c2 321 Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
7fd59977 322 p = (IndexedMapNode *) myData2[iK2];
323 q = NULL;
324 while (p)
325 {
326 if (p->Key2() == Extent())
327 break;
328 q = p;
329 p = (IndexedMapNode*) p->Next2();
330 }
331 if (q == NULL)
332 myData2[iK2] = (IndexedMapNode *) p->Next2();
333 else
334 q->Next2() = p->Next2();
335
336 // remove the key
9991c9c2 337 Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
7fd59977 338 q = (IndexedMapNode *) myData1[iK1];
339 if (q == p)
340 myData1[iK1] = (IndexedMapNode *) p->Next();
341 else
342 {
343 while (q->Next() != p)
344 q = (IndexedMapNode *) q->Next();
345 q->Next() = p->Next();
346 }
347 p->~IndexedMapNode();
348 this->myAllocator->Free(p);
349 Decrement();
350 }
351
352 //! FindKey
353 const TheKeyType& FindKey (const Standard_Integer theKey2) const
354 {
355#if !defined No_Exception && !defined No_Standard_OutOfRange
356 if (theKey2 < 1 || theKey2 > Extent())
357 Standard_OutOfRange::Raise ("NCollection_IndexedMap::FindKey");
358#endif
359 IndexedMapNode * pNode2 =
9991c9c2 360 (IndexedMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
7fd59977 361 while (pNode2)
362 {
363 if (pNode2->Key2() == theKey2)
364 return pNode2->Key1();
365 pNode2 = (IndexedMapNode*) pNode2->Next2();
366 }
367 Standard_NoSuchObject::Raise("NCollection_IndexedMap::FindKey");
368 return pNode2->Key1(); // This for compiler
369 }
370
371 //! operator ()
372 const TheKeyType& operator() (const Standard_Integer theKey2) const
373 { return FindKey (theKey2); }
374
375 //! FindIndex
376 Standard_Integer FindIndex(const TheKeyType& theKey1) const
377 {
378 if (IsEmpty()) return 0;
379 IndexedMapNode * pNode1 =
9991c9c2 380 (IndexedMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
7fd59977 381 while (pNode1)
382 {
9991c9c2 383 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
7fd59977 384 return pNode1->Key2();
385 pNode1 = (IndexedMapNode*) pNode1->Next();
386 }
387 return 0;
388 }
389
390 //! Clear data. If doReleaseMemory is false then the table of
391 //! buckets is not released and will be reused.
392 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
393 { Destroy (IndexedMapNode::delNode, this->myAllocator, doReleaseMemory); }
394
395 //! Clear data and reset allocator
396 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
397 {
398 Clear();
399 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
400 NCollection_BaseAllocator::CommonBaseAllocator() );
401 }
402
403 //! Destructor
404 ~NCollection_IndexedMap (void)
405 { Clear(); }
406
407 //! Size
408 virtual Standard_Integer Size(void) const
409 { return Extent(); }
410
411 private:
412 // ----------- PRIVATE METHODS -----------
413
414 //! Creates Iterator for use on BaseCollection
415 virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator&
416 CreateIterator(void) const
417 { return *(new (this->IterAllocator()) Iterator(*this)); }
418
419};
420
7fd59977 421#endif