0024252: GCC warnings on breakage of strict-aliasing rules
[occt.git] / src / NCollection / NCollection_Map.hxx
CommitLineData
b311480e 1// Created on: 2002-04-23
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_Map_HeaderFile
17#define NCollection_Map_HeaderFile
18
19#include <NCollection_BaseCollection.hxx>
20#include <NCollection_BaseMap.hxx>
ab2db9a5 21#include <NCollection_DataMap.hxx>
7fd59977 22#include <NCollection_TListNode.hxx>
9991c9c2 23
24#include <NCollection_DefaultHasher.hxx>
25
7fd59977 26#include <Standard_ImmutableObject.hxx>
27
28#if !defined No_Exception && !defined No_Standard_NoSuchObject
29#include <Standard_NoSuchObject.hxx>
30#endif
31
7fd59977 32/**
33 * Purpose: Single hashed Map. This Map is used to store and
34 * retrieve keys in linear time.
35 *
36 * The ::Iterator class can be used to explore the
37 * content of the map. It is not wise to iterate and
38 * modify a map in parallel.
39 *
40 * To compute the hashcode of the key the function
41 * ::HashCode must be defined in the global namespace
42 *
43 * To compare two keys the function ::IsEqual must be
44 * defined in the global namespace.
45 *
46 * The performance of a Map is conditionned by its
47 * number of buckets that should be kept greater to
48 * the number of keys. This map has an automatic
49 * management of the number of buckets. It is resized
50 * when the number of Keys becomes greater than the
51 * number of buckets.
52 *
53 * If you have a fair idea of the number of objects
54 * you can save on automatic resizing by giving a
55 * number of buckets at creation or using the ReSize
56 * method. This should be consider only for crucial
57 * optimisation issues.
58 */
9991c9c2 59
60template < class TheKeyType,
61 class Hasher = NCollection_DefaultHasher<TheKeyType> > class NCollection_Map
7fd59977 62 : public NCollection_BaseCollection<TheKeyType>,
63 public NCollection_BaseMap
64{
65 //! Adaptation of the TListNode to the map notations
66 public:
9991c9c2 67
7fd59977 68 class MapNode : public NCollection_TListNode<TheKeyType>
69 {
70 public:
71 //! Constructor with 'Next'
72 MapNode (const TheKeyType& theKey,
73 NCollection_ListNode* theNext) :
74 NCollection_TListNode<TheKeyType> (theKey, theNext) {}
75 //! Key
76 const TheKeyType& Key (void)
77 { return this->Value(); }
78
79 };
80
81 public:
82 //! Implementation of the Iterator interface.
83 class Iterator
84 : public NCollection_BaseCollection<TheKeyType>::Iterator,
85 public NCollection_BaseMap::Iterator
86 {
87 public:
88 //! Empty constructor
89 Iterator (void) :
90 NCollection_BaseMap::Iterator() {}
91 //! Constructor
92 Iterator (const NCollection_Map& theMap) :
93 NCollection_BaseMap::Iterator(theMap) {}
94 //! Query if the end of collection is reached by iterator
95 virtual Standard_Boolean More(void) const
96 { return PMore(); }
97 //! Make a step along the collection
98 virtual void Next(void)
99 { PNext(); }
100 //! Value inquiry
101 virtual const TheKeyType& Value(void) const
102 {
103#if !defined No_Exception && !defined No_Standard_NoSuchObject
104 if (!More())
105 Standard_NoSuchObject::Raise ("NCollection_Map::Iterator::Value");
106#endif
107 return ((MapNode *) myNode)->Value();
108 }
109 //! Value change access - denied
110 virtual TheKeyType& ChangeValue(void) const
111 {
112 Standard_ImmutableObject::Raise("NCollection_Map::Iterator::ChangeValue");
113 return * (TheKeyType *) NULL; // For compiler
114 }
115 //! Key
116 const TheKeyType& Key (void)
117 {
118#if !defined No_Exception && !defined No_Standard_NoSuchObject
119 if (!More())
120 Standard_NoSuchObject::Raise ("NCollection_Map::Iterator::Key");
121#endif
122 return ((MapNode *) myNode)->Value();
123 }
7fd59977 124 };
125
126 public:
127 // ---------- PUBLIC METHODS ------------
128
129 //! Constructor
130 NCollection_Map (const Standard_Integer NbBuckets = 1,
131 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
132 : NCollection_BaseCollection<TheKeyType>(theAllocator),
133 NCollection_BaseMap (NbBuckets, Standard_True) {}
134
135 //! Copy constructor
136 NCollection_Map (const NCollection_Map& theOther)
137 : NCollection_BaseCollection<TheKeyType>(theOther.myAllocator),
138 NCollection_BaseMap (theOther.NbBuckets(), Standard_True)
139 { *this = theOther; }
140
141 //! Assign another collection
142 virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther)
143 {
144 if (this == &theOther)
145 return;
146
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_Map& theOther)
158 {
159 this->exchangeAllocators (theOther);
160 this->exchangeMapsData (theOther);
161 }
162
7fd59977 163 //! = another map
164 NCollection_Map& operator= (const NCollection_Map& theOther)
165 {
166 if (this == &theOther)
167 return *this;
168
169 Clear(theOther.myAllocator);
170 ReSize (theOther.Extent()-1);
171 Iterator anIter(theOther);
172 for (; anIter.More(); anIter.Next())
173 Add (anIter.Key());
174 return *this;
175 }
176
177 //! ReSize
178 void ReSize (const Standard_Integer N)
179 {
fd03ee4b 180 NCollection_ListNode** newdata = 0L;
181 NCollection_ListNode** dummy = 0L;
7fd59977 182 Standard_Integer newBuck;
fd03ee4b 183 if (BeginResize (N, newBuck, newdata, dummy, this->myAllocator))
7fd59977 184 {
185 if (myData1)
186 {
187 MapNode** olddata = (MapNode**) myData1;
188 MapNode *p, *q;
189 Standard_Integer i,k;
190 for (i = 0; i <= NbBuckets(); i++)
191 {
192 if (olddata[i])
193 {
194 p = olddata[i];
195 while (p)
196 {
9991c9c2 197 k = Hasher::HashCode(p->Key(),newBuck);
7fd59977 198 q = (MapNode*) p->Next();
199 p->Next() = newdata[k];
200 newdata[k] = p;
201 p = q;
202 }
203 }
204 }
205 }
fd03ee4b 206 EndResize (N, newBuck, newdata, dummy, this->myAllocator);
7fd59977 207 }
208 }
209
210 //! Add
211 Standard_Boolean Add(const TheKeyType& K)
212 {
213 if (Resizable())
214 ReSize(Extent());
215 MapNode** data = (MapNode**)myData1;
9991c9c2 216 Standard_Integer k = Hasher::HashCode(K,NbBuckets());
7fd59977 217 MapNode* p = data[k];
218 while (p)
219 {
9991c9c2 220 if (Hasher::IsEqual(p->Key(),K))
7fd59977 221 return Standard_False;
222 p = (MapNode *) p->Next();
223 }
224 data[k] = new (this->myAllocator) MapNode(K,data[k]);
225 Increment();
226 return Standard_True;
227 }
228
229 //! Added: add a new key if not yet in the map, and return
230 //! reference to either newly added or previously existing object
231 const TheKeyType& Added(const TheKeyType& K)
232 {
233 if (Resizable())
234 ReSize(Extent());
235 MapNode** data = (MapNode**)myData1;
9991c9c2 236 Standard_Integer k = Hasher::HashCode(K,NbBuckets());
7fd59977 237 MapNode* p = data[k];
238 while (p)
239 {
9991c9c2 240 if (Hasher::IsEqual(p->Key(),K))
7fd59977 241 return p->Key();
242 p = (MapNode *) p->Next();
243 }
244 data[k] = new (this->myAllocator) MapNode(K,data[k]);
245 Increment();
246 return data[k]->Key();
247 }
248
249 //! Contains
250 Standard_Boolean Contains(const TheKeyType& K) const
251 {
252 if (IsEmpty())
253 return Standard_False;
254 MapNode** data = (MapNode**) myData1;
9991c9c2 255 MapNode* p = data[Hasher::HashCode(K,NbBuckets())];
7fd59977 256 while (p)
257 {
9991c9c2 258 if (Hasher::IsEqual(p->Key(),K))
7fd59977 259 return Standard_True;
260 p = (MapNode *) p->Next();
261 }
262 return Standard_False;
263 }
264
265 //! Remove
266 Standard_Boolean Remove(const TheKeyType& K)
267 {
268 if (IsEmpty())
269 return Standard_False;
270 MapNode** data = (MapNode**) myData1;
9991c9c2 271 Standard_Integer k = Hasher::HashCode(K,NbBuckets());
7fd59977 272 MapNode* p = data[k];
273 MapNode* q = NULL;
274 while (p)
275 {
9991c9c2 276 if (Hasher::IsEqual(p->Key(),K))
7fd59977 277 {
278 Decrement();
279 if (q)
280 q->Next() = p->Next();
281 else
282 data[k] = (MapNode*) p->Next();
283 p->~MapNode();
284 this->myAllocator->Free(p);
285 return Standard_True;
286 }
287 q = p;
288 p = (MapNode*) p->Next();
289 }
290 return Standard_False;
291 }
292
293 //! Clear data. If doReleaseMemory is false then the table of
294 //! buckets is not released and will be reused.
295 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
296 { Destroy (MapNode::delNode, this->myAllocator, doReleaseMemory); }
297
298 //! Clear data and reset allocator
299 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
300 {
301 Clear();
302 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
303 NCollection_BaseAllocator::CommonBaseAllocator() );
304 }
305
306 //! Destructor
307 ~NCollection_Map (void)
308 { Clear(); }
309
310 //! Size
311 virtual Standard_Integer Size(void) const
312 { return Extent(); }
313
ab2db9a5 314 public:
315 //!@name Boolean operations with maps as sets of keys
316 //!@{
317
318 //! @return true if two maps contains exactly the same keys
319 Standard_Boolean IsEqual (const NCollection_Map& theOther) const
320 {
321 return Extent() == theOther.Extent()
322 && Contains (theOther);
323 }
324
325 //! @return true if this map contains ALL keys of another map.
326 Standard_Boolean Contains (const NCollection_Map& theOther) const
327 {
328 if (this == &theOther
329 || theOther.IsEmpty())
330 {
331 return Standard_True;
332 }
333 else if (Extent() < theOther.Extent())
334 {
335 return Standard_False;
336 }
337
338 for (Iterator anIter (theOther); anIter.More(); anIter.Next())
339 {
340 if (!Contains (anIter.Key()))
341 {
342 return Standard_False;
343 }
344 }
345
346 return Standard_True;
347 }
348
349 //! Sets this Map to be the result of union (aka addition, fuse, merge, boolean OR) operation between two given Maps
350 //! The new Map contains the values that are contained either in the first map or in the second map or in both.
351 //! All previous content of this Map is cleared.
352 //! This map (result of the boolean operation) can also be passed as one of operands.
353 void Union (const NCollection_Map& theLeft,
354 const NCollection_Map& theRight)
355 {
356 if (&theLeft == &theRight)
357 {
358 Assign (theLeft);
359 return;
360 }
361
362 if (this != &theLeft
363 && this != &theRight)
364 {
365 Clear();
366 }
367
368 if (this != &theLeft)
369 {
370 for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
371 {
372 Add (anIter.Key());
373 }
374 }
375 if (this != &theRight)
376 {
377 for (Iterator anIter (theRight); anIter.More(); anIter.Next())
378 {
379 Add (anIter.Key());
380 }
381 }
382 }
383
384 //! Apply to this Map the boolean operation union (aka addition, fuse, merge, boolean OR) with another (given) Map.
385 //! The result contains the values that were previously contained in this map or contained in the given (operand) map.
386 //! This algorithm is similar to method Union().
387 //! Returns True if contents of this map is changed.
388 Standard_Boolean Unite (const NCollection_Map& theOther)
389 {
390 if (this == &theOther)
391 {
392 return Standard_False;
393 }
394
395 const Standard_Integer anOldExtent = Extent();
396 Union (*this, theOther);
397 return anOldExtent != Extent();
398 }
399
400 //! Sets this Map to be the result of intersection (aka multiplication, common, boolean AND) operation between two given Maps.
401 //! The new Map contains only the values that are contained in both map operands.
402 //! All previous content of this Map is cleared.
403 //! This same map (result of the boolean operation) can also be used as one of operands.
404 void Intersection (const NCollection_Map& theLeft,
405 const NCollection_Map& theRight)
406 {
407 if (&theLeft == &theRight)
408 {
409 Assign (theLeft);
410 return;
411 }
412
413 if (this == &theLeft)
414 {
415 NCollection_Map aCopy (1, this->myAllocator);
416 Exchange (aCopy);
417 Intersection (aCopy, theRight);
418 return;
419 }
420 else if (this == &theRight)
421 {
422 NCollection_Map aCopy (1, this->myAllocator);
423 Exchange (aCopy);
424 Intersection (theLeft, aCopy);
425 return;
426 }
427
428 Clear();
429 if (theLeft.Extent() < theRight.Extent())
430 {
431 for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
432 {
433 if (theRight.Contains (anIter.Key()))
434 {
435 Add (anIter.Key());
436 }
437 }
438 }
439 else
440 {
441 for (Iterator anIter (theRight); anIter.More(); anIter.Next())
442 {
443 if (theLeft.Contains (anIter.Key()))
444 {
445 Add (anIter.Key());
446 }
447 }
448 }
449 }
450
451 //! Apply to this Map the intersection operation (aka multiplication, common, boolean AND) with another (given) Map.
452 //! The result contains only the values that are contained in both this and the given maps.
453 //! This algorithm is similar to method Intersection().
454 //! Returns True if contents of this map is changed.
455 Standard_Boolean Intersect (const NCollection_Map& theOther)
456 {
457 if (this == &theOther
458 || IsEmpty())
459 {
460 return Standard_False;
461 }
462
463 const Standard_Integer anOldExtent = Extent();
464 Intersection (*this, theOther);
465 return anOldExtent != Extent();
466 }
467
468 //! Sets this Map to be the result of subtraction (aka set-theoretic difference, relative complement,
469 //! exclude, cut, boolean NOT) operation between two given Maps.
470 //! The new Map contains only the values that are contained in the first map operands and not contained in the second one.
471 //! All previous content of this Map is cleared.
472 void Subtraction (const NCollection_Map& theLeft,
473 const NCollection_Map& theRight)
474 {
475 if (this == &theLeft)
476 {
477 Subtract (theRight);
478 return;
479 }
480 else if (this == &theRight)
481 {
482 NCollection_Map aCopy (1, this->myAllocator);
483 Exchange (aCopy);
484 Subtraction (theLeft, aCopy);
485 return;
486 }
487
488 Assign (theLeft);
489 Subtract (theRight);
490 }
491
492 //! Apply to this Map the subtraction (aka set-theoretic difference, relative complement,
493 //! exclude, cut, boolean NOT) operation with another (given) Map.
494 //! The result contains only the values that were previously contained in this map and not contained in this map.
495 //! This algorithm is similar to method Subtract() with two operands.
496 //! Returns True if contents of this map is changed.
497 Standard_Boolean Subtract (const NCollection_Map& theOther)
498 {
499 if (this == &theOther)
500 {
501 if (IsEmpty())
502 {
503 return Standard_False;
504 }
505
506 Clear();
507 return Standard_True;
508 }
509
510 const Standard_Integer anOldExtent = Extent();
511 for (Iterator anIter (theOther); anIter.More(); anIter.Next())
512 {
513 Remove (anIter.Key());
514 }
515 return anOldExtent != Extent();
516 }
517
518 //! Sets this Map to be the result of symmetric difference (aka exclusive disjunction, boolean XOR) operation between two given Maps.
519 //! The new Map contains the values that are contained only in the first or the second operand maps but not in both.
520 //! All previous content of this Map is cleared. This map (result of the boolean operation) can also be used as one of operands.
521 void Difference (const NCollection_Map& theLeft,
522 const NCollection_Map& theRight)
523 {
524 if (&theLeft == &theRight)
525 {
526 Clear();
527 return;
528 }
529 else if (this == &theLeft)
530 {
531 NCollection_Map aCopy (1, this->myAllocator);
532 Exchange (aCopy);
533 Difference (aCopy, theRight);
534 return;
535 }
536 else if (this == &theRight)
537 {
538 NCollection_Map aCopy (1, this->myAllocator);
539 Exchange (aCopy);
540 Difference (theLeft, aCopy);
541 return;
542 }
543
544 Clear();
545 for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
546 {
547 if (!theRight.Contains (anIter.Key()))
548 {
549 Add (anIter.Key());
550 }
551 }
552 for (Iterator anIter (theRight); anIter.More(); anIter.Next())
553 {
554 if (!theLeft.Contains (anIter.Key()))
555 {
556 Add (anIter.Key());
557 }
558 }
559 }
560
561 //! Apply to this Map the symmetric difference (aka exclusive disjunction, boolean XOR) operation with another (given) Map.
562 //! The result contains the values that are contained only in this or the operand map, but not in both.
563 //! This algorithm is similar to method Difference().
564 //! Returns True if contents of this map is changed.
565 Standard_Boolean Differ (const NCollection_Map& theOther)
566 {
567 if (this == &theOther)
568 {
569 if (IsEmpty())
570 {
571 return Standard_False;
572 }
573 Clear();
574 return Standard_True;
575 }
576
577 const Standard_Integer anOldExtent = Extent();
578 Difference (*this, theOther);
579 return anOldExtent != Extent();
580 }
581
582 //!@}
583
7fd59977 584 private:
585 // ----------- PRIVATE METHODS -----------
586
587 //! Creates Iterator for use on BaseCollection
588 virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator&
589 CreateIterator(void) const
590 { return *(new (this->IterAllocator()) Iterator(*this)); }
591
592};
593
7fd59977 594#endif