0024252: GCC warnings on breakage of strict-aliasing rules
[occt.git] / src / NCollection / NCollection_IndexedDataMap.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.
7fd59977 15
16#ifndef NCollection_IndexedDataMap_HeaderFile
17#define NCollection_IndexedDataMap_HeaderFile
18
19#include <NCollection_BaseCollection.hxx>
20#include <NCollection_BaseMap.hxx>
21#include <NCollection_TListNode.hxx>
22#include <Standard_TypeMismatch.hxx>
23#include <Standard_NoSuchObject.hxx>
9991c9c2 24
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..
38 * Extent. An Item is stored with each key.
39 *
40 * This class is similar to IndexedMap from
41 * NCollection with the Item as a new feature. Note
42 * the important difference on the operator (). In
43 * the IndexedMap this operator returns the Key. In
44 * the IndexedDataMap this operator returns the Item.
45 *
46 * See the class Map from NCollection for a
47 * discussion about the number of buckets.
48 */
9991c9c2 49
50template < class TheKeyType,
51 class TheItemType,
52 class Hasher = NCollection_DefaultHasher<TheKeyType> >
53 class NCollection_IndexedDataMap
7fd59977 54 : public NCollection_BaseCollection<TheItemType>,
55 public NCollection_BaseMap
56{
57 //! Adaptation of the TListNode to the INDEXEDDatamap
58 private:
59 class IndexedDataMapNode : public NCollection_TListNode<TheItemType>
60 {
61 public:
62 //! Constructor with 'Next'
63 IndexedDataMapNode (const TheKeyType& theKey1,
64 const Standard_Integer theKey2,
65 const TheItemType& theItem,
66 NCollection_ListNode* theNext1,
67 NCollection_ListNode* theNext2) :
68 NCollection_TListNode<TheItemType>(theItem,theNext1)
69 {
70 myKey1 = theKey1;
71 myKey2 = theKey2;
72 myNext2 = (IndexedDataMapNode *) theNext2;
73 }
74 //! Key1
75 TheKeyType& Key1 (void)
76 { return myKey1; }
77 //! Key2
78 const Standard_Integer& Key2 (void)
79 { return myKey2; }
80 //! Next2
81 IndexedDataMapNode*& Next2 (void)
82 { return myNext2; }
83
84 //! Static deleter to be passed to BaseList
85 static void delNode (NCollection_ListNode * theNode,
86 Handle(NCollection_BaseAllocator)& theAl)
87 {
88 ((IndexedDataMapNode *) theNode)->~IndexedDataMapNode();
89 theAl->Free(theNode);
90 }
91 private:
92 TheKeyType myKey1;
93 Standard_Integer myKey2;
94 IndexedDataMapNode * myNext2;
95 };
96
97 public:
98 //! Implementation of the Iterator interface.
99 class Iterator : public NCollection_BaseCollection<TheItemType>::Iterator
100 {
101 public:
102 //! Empty constructor
103 Iterator (void) :
104 myMap(NULL),
105 myIndex(0) {}
106 //! Constructor
107 Iterator (const NCollection_IndexedDataMap& theMap) :
108 myMap((NCollection_IndexedDataMap *) &theMap),
109 myIndex(1) {}
110 //! Query if the end of collection is reached by iterator
111 virtual Standard_Boolean More(void) const
112 { return (myIndex <= myMap->Extent()); }
113 //! Make a step along the collection
114 virtual void Next(void)
115 { myIndex++; }
116 //! Value access
117 virtual const TheItemType& Value(void) const
118 {
119#if !defined No_Exception && !defined No_Standard_NoSuchObject
120 if (!More())
121 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::Value");
122#endif
123 return myMap->FindFromIndex(myIndex);
124 }
125 //! ChangeValue access
126 virtual TheItemType& ChangeValue(void) const
127 {
128#if !defined No_Exception && !defined No_Standard_NoSuchObject
129 if (!More())
130 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::Iterator::ChangeValue");
131#endif
132 return myMap->ChangeFromIndex(myIndex);
133 }
7fd59977 134
135 private:
136 NCollection_IndexedDataMap * myMap; //!< Pointer to the map being iterated
137 Standard_Integer myIndex; //!< Current index
138 };
139
140 public:
141 // ---------- PUBLIC METHODS ------------
142
143 //! Constructor
144 NCollection_IndexedDataMap (const Standard_Integer NbBuckets=1,
145 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
146 : NCollection_BaseCollection<TheItemType>(theAllocator),
147 NCollection_BaseMap (NbBuckets, Standard_False) {}
148
149 //! Copy constructor
150 NCollection_IndexedDataMap (const NCollection_IndexedDataMap& theOther)
151 : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
152 NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
153 { *this = theOther; }
154
155 //! Assign another collection
156 virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
157 {
158 if (this == &theOther)
159 return;
160 Standard_TypeMismatch::Raise("NCollection_IndexedDataMap::Assign");
161 }
162
ab2db9a5 163 //! Exchange the content of two maps without re-allocations.
164 //! Notice that allocators will be swapped as well!
165 void Exchange (NCollection_IndexedDataMap& theOther)
166 {
167 this->exchangeAllocators (theOther);
168 this->exchangeMapsData (theOther);
169 }
170
7fd59977 171 //! = another map
172 NCollection_IndexedDataMap& operator=
173 (const NCollection_IndexedDataMap& theOther)
174 {
175 if (this == &theOther)
176 return *this;
177
178 Clear(theOther.myAllocator);
179 ReSize (theOther.Extent()-1);
180 Standard_Integer i;
181 for (i=1; i<=theOther.Extent(); i++)
182 {
183 TheKeyType aKey1 = theOther.FindKey(i);
184 TheItemType anItem = theOther.FindFromIndex(i);
9991c9c2 185 Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
186 Standard_Integer iK2 = ::HashCode (i, NbBuckets());
7fd59977 187 IndexedDataMapNode * pNode =
188 new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
189 myData1[iK1], myData2[iK2]);
190 myData1[iK1] = pNode;
191 myData2[iK2] = pNode;
192 Increment();
193 }
194 return *this;
195 }
196
197 //! ReSize
198 void ReSize (const Standard_Integer N)
199 {
fd03ee4b 200 NCollection_ListNode** ppNewData1 = NULL;
201 NCollection_ListNode** ppNewData2 = NULL;
7fd59977 202 Standard_Integer newBuck;
fd03ee4b 203 if (BeginResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator))
7fd59977 204 {
205 if (myData1)
206 {
207 IndexedDataMapNode *p, *q;
208 Standard_Integer i, iK1, iK2;
209 for (i = 0; i <= NbBuckets(); i++)
210 {
211 if (myData1[i])
212 {
213 p = (IndexedDataMapNode *) myData1[i];
214 while (p)
215 {
9991c9c2 216 iK1 = Hasher::HashCode (p->Key1(), newBuck);
217 iK2 = ::HashCode (p->Key2(), newBuck);
7fd59977 218 q = (IndexedDataMapNode*) p->Next();
219 p->Next() = ppNewData1[iK1];
fd03ee4b 220 p->Next2() = (IndexedDataMapNode*)ppNewData2[iK2];
7fd59977 221 ppNewData1[iK1] = p;
222 ppNewData2[iK2] = p;
223 p = q;
224 }
225 }
226 }
227 }
fd03ee4b 228 EndResize (N, newBuck, ppNewData1, ppNewData2, this->myAllocator);
7fd59977 229 }
230 }
231
232 //! Add
233 Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
234 {
235 if (Resizable())
236 ReSize(Extent());
9991c9c2 237 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
7fd59977 238 IndexedDataMapNode * pNode;
239 pNode = (IndexedDataMapNode *) myData1[iK1];
240 while (pNode)
241 {
9991c9c2 242 if (Hasher::IsEqual (pNode->Key1(), theKey1))
7fd59977 243 return pNode->Key2();
244 pNode = (IndexedDataMapNode *) pNode->Next();
245 }
246 Increment();
9991c9c2 247 Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
7fd59977 248 pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
249 myData1[iK1], myData2[iK2]);
250 myData1[iK1] = pNode;
251 myData2[iK2] = pNode;
252 return Extent();
253 }
254
255 //! Contains
256 Standard_Boolean Contains (const TheKeyType& theKey1) const
257 {
258 if (IsEmpty())
259 return Standard_False;
9991c9c2 260 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
7fd59977 261 IndexedDataMapNode * pNode1;
262 pNode1 = (IndexedDataMapNode *) myData1[iK1];
263 while (pNode1)
264 {
9991c9c2 265 if (Hasher::IsEqual(pNode1->Key1(), theKey1))
7fd59977 266 return Standard_True;
267 pNode1 = (IndexedDataMapNode *) pNode1->Next();
268 }
269 return Standard_False;
270 }
271
272 //! Substitute
273 void Substitute (const Standard_Integer theIndex,
274 const TheKeyType& theKey1,
275 const TheItemType& theItem)
276 {
277#if !defined No_Exception && !defined No_Standard_OutOfRange
278 if (theIndex < 1 || theIndex > Extent())
279 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::Substitute");
280#endif
281 IndexedDataMapNode * p;
282 // check if theKey1 is not already in the map
9991c9c2 283 Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
7fd59977 284 p = (IndexedDataMapNode *) myData1[iK1];
285 while (p)
286 {
9991c9c2 287 if (Hasher::IsEqual (p->Key1(), theKey1))
7fd59977 288 Standard_DomainError::Raise("NCollection_IndexedDataMap::Substitute");
289 p = (IndexedDataMapNode *) p->Next();
290 }
291
292 // Find the node for the index I
9991c9c2 293 Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
7fd59977 294 p = (IndexedDataMapNode *) myData2[iK2];
295 while (p)
296 {
297 if (p->Key2() == theIndex)
298 break;
299 p = (IndexedDataMapNode*) p->Next2();
300 }
301
302 // remove the old key
9991c9c2 303 Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
7fd59977 304 IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
305 if (q == p)
306 myData1[iK] = (IndexedDataMapNode *) p->Next();
307 else
308 {
309 while (q->Next() != p)
310 q = (IndexedDataMapNode *) q->Next();
311 q->Next() = p->Next();
312 }
313
314 // update the node
315 p->Key1() = theKey1;
316 p->ChangeValue() = theItem;
317 p->Next() = myData1[iK1];
318 myData1[iK1] = p;
319 }
320
321 //! RemoveLast
322 void RemoveLast (void)
323 {
324#if !defined No_Exception && !defined No_Standard_OutOfRange
325 if (Extent() == 0)
326 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::RemoveLast");
327#endif
328 IndexedDataMapNode * p, * q;
329 // Find the node for the last index and remove it
9991c9c2 330 Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
7fd59977 331 p = (IndexedDataMapNode *) myData2[iK2];
332 q = NULL;
333 while (p)
334 {
335 if (p->Key2() == Extent())
336 break;
337 q = p;
338 p = (IndexedDataMapNode*) p->Next2();
339 }
340 if (q == NULL)
341 myData2[iK2] = (IndexedDataMapNode *) p->Next2();
342 else
343 q->Next2() = p->Next2();
344
345 // remove the key
9991c9c2 346 Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
7fd59977 347 q = (IndexedDataMapNode *) myData1[iK1];
348 if (q == p)
349 myData1[iK1] = (IndexedDataMapNode *) p->Next();
350 else
351 {
352 while (q->Next() != p)
353 q = (IndexedDataMapNode *) q->Next();
354 q->Next() = p->Next();
355 }
356 p->~IndexedDataMapNode();
357 this->myAllocator->Free(p);
358 Decrement();
359 }
360
361 //! FindKey
362 const TheKeyType& FindKey (const Standard_Integer theKey2) const
363 {
364#if !defined No_Exception && !defined No_Standard_OutOfRange
365 if (theKey2 < 1 || theKey2 > Extent())
366 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindKey");
367#endif
368 IndexedDataMapNode * pNode2 =
9991c9c2 369 (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
7fd59977 370 while (pNode2)
371 {
372 if (pNode2->Key2() == theKey2)
373 return pNode2->Key1();
374 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
375 }
376 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindKey");
377 return pNode2->Key1(); // This for compiler
378 }
379
380 //! FindFromIndex
381 const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
382 {
383#if !defined No_Exception && !defined No_Standard_OutOfRange
384 if (theKey2 < 1 || theKey2 > Extent())
385 Standard_OutOfRange::Raise ("NCollection_IndexedDataMap::FindFromIndex");
386#endif
387 IndexedDataMapNode * pNode2 =
9991c9c2 388 (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
7fd59977 389 while (pNode2)
390 {
391 if (pNode2->Key2() == theKey2)
392 return pNode2->Value();
393 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
394 }
395 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
396 return pNode2->Value(); // This for compiler
397 }
398
399 //! operator ()
400 const TheItemType& operator() (const Standard_Integer theKey2) const
401 { return FindFromIndex (theKey2); }
402
403 //! ChangeFromIndex
404 TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
405 {
406#if !defined No_Exception && !defined No_Standard_OutOfRange
407 if (theKey2 < 1 || theKey2 > Extent())
408 Standard_OutOfRange::Raise("NCollection_IndexedDataMap::ChangeFromIndex");
409#endif
410 IndexedDataMapNode * pNode2 =
9991c9c2 411 (IndexedDataMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
7fd59977 412 while (pNode2)
413 {
414 if (pNode2->Key2() == theKey2)
415 return pNode2->ChangeValue();
416 pNode2 = (IndexedDataMapNode*) pNode2->Next2();
417 }
418 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromIndex");
419 return pNode2->ChangeValue(); // This for compiler
420 }
421
422 //! operator ()
423 TheItemType& operator() (const Standard_Integer theKey2)
424 { return ChangeFromIndex (theKey2); }
425
426 //! FindIndex
427 Standard_Integer FindIndex(const TheKeyType& theKey1) const
428 {
429 if (IsEmpty()) return 0;
430 IndexedDataMapNode * pNode1 =
9991c9c2 431 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
7fd59977 432 while (pNode1)
433 {
9991c9c2 434 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
7fd59977 435 return pNode1->Key2();
436 pNode1 = (IndexedDataMapNode*) pNode1->Next();
437 }
438 return 0;
439 }
440
441 //! FindFromKey
442 const TheItemType& FindFromKey(const TheKeyType& theKey1) const
443 {
444#if !defined No_Exception && !defined No_Standard_NoSuchObject
445 if (IsEmpty())
446 Standard_NoSuchObject::Raise ("NCollection_IndexedDataMap::FindFromKey");
447#endif
448 IndexedDataMapNode * pNode1 =
9991c9c2 449 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
7fd59977 450 while (pNode1)
451 {
9991c9c2 452 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
7fd59977 453 return pNode1->Value();
454 pNode1 = (IndexedDataMapNode*) pNode1->Next();
455 }
456 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::FindFromKey");
457 return pNode1->Value();
458 }
459
460 //! ChangeFromKey
461 TheItemType& ChangeFromKey (const TheKeyType& theKey1)
462 {
463#if !defined No_Exception && !defined No_Standard_NoSuchObject
464 if (IsEmpty())
465 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
466#endif
467 IndexedDataMapNode * pNode1 =
9991c9c2 468 (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
7fd59977 469 while (pNode1)
470 {
9991c9c2 471 if (Hasher::IsEqual (pNode1->Key1(), theKey1))
7fd59977 472 return pNode1->ChangeValue();
473 pNode1 = (IndexedDataMapNode*) pNode1->Next();
474 }
475 Standard_NoSuchObject::Raise("NCollection_IndexedDataMap::ChangeFromKey");
476 return pNode1->ChangeValue();
477 }
478
479 //! Clear data. If doReleaseMemory is false then the table of
480 //! buckets is not released and will be reused.
481 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
482 { Destroy (IndexedDataMapNode::delNode, this->myAllocator, doReleaseMemory); }
483
484 //! Clear data and reset allocator
485 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
486 {
487 Clear();
488 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
489 NCollection_BaseAllocator::CommonBaseAllocator() );
490 }
491
492 //! Destructor
493 ~NCollection_IndexedDataMap (void)
494 { Clear(); }
495
496 //! Size
497 virtual Standard_Integer Size(void) const
498 { return Extent(); }
499
500 private:
501 // ----------- PRIVATE METHODS -----------
502
503 //! Creates Iterator for use on BaseCollection
504 virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
505 CreateIterator(void) const
506 { return *(new (this->IterAllocator()) Iterator(*this)); }
507
508};
509
7fd59977 510#endif