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