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