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