0024252: GCC warnings on breakage of strict-aliasing rules
[occt.git] / src / NCollection / NCollection_Map.hxx
1 // Created on: 2002-04-23
2 // Created by: Alexander KARTOMIN (akm)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
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.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef NCollection_Map_HeaderFile
17 #define NCollection_Map_HeaderFile
18
19 #include <NCollection_BaseCollection.hxx>
20 #include <NCollection_BaseMap.hxx>
21 #include <NCollection_DataMap.hxx>
22 #include <NCollection_TListNode.hxx>
23
24 #include <NCollection_DefaultHasher.hxx>
25
26 #include <Standard_ImmutableObject.hxx>
27
28 #if !defined No_Exception && !defined No_Standard_NoSuchObject
29 #include <Standard_NoSuchObject.hxx>
30 #endif
31
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  */            
59
60 template < class TheKeyType, 
61            class Hasher = NCollection_DefaultHasher<TheKeyType> > class NCollection_Map 
62   : public NCollection_BaseCollection<TheKeyType>,
63     public NCollection_BaseMap
64 {
65   //!   Adaptation of the TListNode to the map notations
66  public:
67
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     }
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
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
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   {
180     NCollection_ListNode** newdata = 0L;
181     NCollection_ListNode** dummy = 0L;
182     Standard_Integer newBuck;
183     if (BeginResize (N, newBuck, newdata, dummy, this->myAllocator)) 
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             {
197               k = Hasher::HashCode(p->Key(),newBuck);
198               q = (MapNode*) p->Next();
199               p->Next() = newdata[k];
200               newdata[k] = p;
201               p = q;
202             }
203           }
204         }
205       }
206       EndResize (N, newBuck, newdata, dummy, this->myAllocator);
207     }
208   }
209
210   //! Add
211   Standard_Boolean Add(const TheKeyType& K)
212   {
213     if (Resizable()) 
214       ReSize(Extent());
215     MapNode** data = (MapNode**)myData1;
216     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
217     MapNode* p = data[k];
218     while (p) 
219     {
220       if (Hasher::IsEqual(p->Key(),K))
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;
236     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
237     MapNode* p = data[k];
238     while (p) 
239     {
240       if (Hasher::IsEqual(p->Key(),K))
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;
255     MapNode*  p = data[Hasher::HashCode(K,NbBuckets())];
256     while (p) 
257     {
258       if (Hasher::IsEqual(p->Key(),K)) 
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;
271     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
272     MapNode* p = data[k];
273     MapNode* q = NULL;
274     while (p) 
275     {
276       if (Hasher::IsEqual(p->Key(),K)) 
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
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
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
594 #endif