0029299: Foundation Classes, NCollection - define explicit empty constructor for...
[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   //! Empty constructor.
123   NCollection_Map() : NCollection_BaseMap (1, Standard_True, Handle(NCollection_BaseAllocator)()) {}
124
125   //! Constructor
126   explicit NCollection_Map (const Standard_Integer theNbBuckets,
127                             const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
128   : NCollection_BaseMap (theNbBuckets, Standard_True, theAllocator) {}
129
130   //! Copy constructor
131   NCollection_Map (const NCollection_Map& theOther) :
132     NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator)
133   { *this = theOther; }
134
135   //! Exchange the content of two maps without re-allocations.
136   //! Notice that allocators will be swapped as well!
137   void Exchange (NCollection_Map& theOther)
138   {
139     this->exchangeMapsData (theOther);
140   }
141
142   //! Assign.
143   //! This method does not change the internal allocator.
144   NCollection_Map& Assign (const NCollection_Map& theOther)
145   { 
146     if (this == &theOther)
147       return *this;
148
149     Clear();
150     ReSize (theOther.Extent()-1);
151     Iterator anIter(theOther);
152     for (; anIter.More(); anIter.Next())
153       Add (anIter.Key());
154     return *this;
155   }
156
157   //! Assign operator
158   NCollection_Map& operator= (const NCollection_Map& theOther)
159   {
160     return Assign(theOther);
161   }
162
163   //! ReSize
164   void ReSize (const Standard_Integer N)
165   {
166     NCollection_ListNode** newdata = 0L;
167     NCollection_ListNode** dummy = 0L;
168     Standard_Integer newBuck;
169     if (BeginResize (N, newBuck, newdata, dummy))
170     {
171       if (myData1) 
172       {
173         MapNode** olddata = (MapNode**) myData1;
174         MapNode *p, *q;
175         Standard_Integer i,k;
176         for (i = 0; i <= NbBuckets(); i++) 
177         {
178           if (olddata[i]) 
179           {
180             p = olddata[i];
181             while (p) 
182             {
183               k = Hasher::HashCode(p->Key(),newBuck);
184               q = (MapNode*) p->Next();
185               p->Next() = newdata[k];
186               newdata[k] = p;
187               p = q;
188             }
189           }
190         }
191       }
192       EndResize (N, newBuck, newdata, dummy);
193     }
194   }
195
196   //! Add
197   Standard_Boolean Add(const TheKeyType& K)
198   {
199     if (Resizable()) 
200       ReSize(Extent());
201     MapNode** data = (MapNode**)myData1;
202     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
203     MapNode* p = data[k];
204     while (p) 
205     {
206       if (Hasher::IsEqual(p->Key(),K))
207         return Standard_False;
208       p = (MapNode *) p->Next();
209     }
210     data[k] = new (this->myAllocator) MapNode(K,data[k]);
211     Increment();
212     return Standard_True;
213   }
214
215   //! Added: add a new key if not yet in the map, and return 
216   //! reference to either newly added or previously existing object
217   const TheKeyType& Added(const TheKeyType& K)
218   {
219     if (Resizable()) 
220       ReSize(Extent());
221     MapNode** data = (MapNode**)myData1;
222     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
223     MapNode* p = data[k];
224     while (p) 
225     {
226       if (Hasher::IsEqual(p->Key(),K))
227         return p->Key();
228       p = (MapNode *) p->Next();
229     }
230     data[k] = new (this->myAllocator) MapNode(K,data[k]);
231     Increment();
232     return data[k]->Key();
233   }
234
235   //! Contains
236   Standard_Boolean Contains(const TheKeyType& K) const
237   {
238     if (IsEmpty()) 
239       return Standard_False;
240     MapNode** data = (MapNode**) myData1;
241     MapNode*  p = data[Hasher::HashCode(K,NbBuckets())];
242     while (p) 
243     {
244       if (Hasher::IsEqual(p->Key(),K)) 
245         return Standard_True;
246       p = (MapNode *) p->Next();
247     }
248     return Standard_False;
249   }
250
251   //! Remove
252   Standard_Boolean Remove(const TheKeyType& K)
253   {
254     if (IsEmpty()) 
255       return Standard_False;
256     MapNode** data = (MapNode**) myData1;
257     Standard_Integer k = Hasher::HashCode(K,NbBuckets());
258     MapNode* p = data[k];
259     MapNode* q = NULL;
260     while (p) 
261     {
262       if (Hasher::IsEqual(p->Key(),K)) 
263       {
264         Decrement();
265         if (q) 
266           q->Next() = p->Next();
267         else
268           data[k] = (MapNode*) p->Next();
269         p->~MapNode();
270         this->myAllocator->Free(p);
271         return Standard_True;
272       }
273       q = p;
274       p = (MapNode*) p->Next();
275     }
276     return Standard_False;
277   }
278
279   //! Clear data. If doReleaseMemory is false then the table of
280   //! buckets is not released and will be reused.
281   void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
282   { Destroy (MapNode::delNode, doReleaseMemory); }
283
284   //! Clear data and reset allocator
285   void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
286   { 
287     Clear();
288     this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
289                     NCollection_BaseAllocator::CommonBaseAllocator() );
290   }
291
292   //! Destructor
293   virtual ~NCollection_Map (void)
294   { Clear(); }
295
296   //! Size
297   Standard_Integer Size(void) const
298   { return Extent(); }
299
300  public:
301   //!@name Boolean operations with maps as sets of keys
302   //!@{
303
304   //! @return true if two maps contains exactly the same keys
305   Standard_Boolean IsEqual (const NCollection_Map& theOther) const
306   {
307     return Extent() == theOther.Extent()
308         && Contains (theOther);
309   }
310
311   //! @return true if this map contains ALL keys of another map.
312   Standard_Boolean Contains (const NCollection_Map& theOther) const
313   {
314     if (this == &theOther
315      || theOther.IsEmpty())
316     {
317       return Standard_True;
318     }
319     else if (Extent() < theOther.Extent())
320     {
321       return Standard_False;
322     }
323
324     for (Iterator anIter (theOther); anIter.More(); anIter.Next())
325     {
326       if (!Contains (anIter.Key()))
327       {
328         return Standard_False;
329       }
330     }
331
332     return Standard_True;
333   }
334
335   //! Sets this Map to be the result of union (aka addition, fuse, merge, boolean OR) operation between two given Maps
336   //! The new Map contains the values that are contained either in the first map or in the second map or in both.
337   //! All previous content of this Map is cleared.
338   //! This map (result of the boolean operation) can also be passed as one of operands.
339   void Union (const NCollection_Map& theLeft,
340               const NCollection_Map& theRight)
341   {
342     if (&theLeft == &theRight)
343     {
344       Assign (theLeft);
345       return;
346     }
347
348     if (this != &theLeft
349      && this != &theRight)
350     {
351       Clear();
352     }
353
354     if (this != &theLeft)
355     {
356       for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
357       {
358         Add (anIter.Key());
359       }
360     }
361     if (this != &theRight)
362     {
363       for (Iterator anIter (theRight); anIter.More(); anIter.Next())
364       {
365         Add (anIter.Key());
366       }
367     }
368   }
369
370   //! Apply to this Map the boolean operation union (aka addition, fuse, merge, boolean OR) with another (given) Map.
371   //! The result contains the values that were previously contained in this map or contained in the given (operand) map.
372   //! This algorithm is similar to method Union().
373   //! Returns True if contents of this map is changed.
374   Standard_Boolean Unite (const NCollection_Map& theOther)
375   {
376     if (this == &theOther)
377     {
378       return Standard_False;
379     }
380
381     const Standard_Integer anOldExtent = Extent();
382     Union (*this, theOther);
383     return anOldExtent != Extent();
384   }
385
386   //! Returns true if this and theMap have common elements.
387   Standard_Boolean HasIntersection (const NCollection_Map& theMap) const
388   {
389     const NCollection_Map* aMap1 = this;
390     const NCollection_Map* aMap2 = &theMap;
391     if (theMap.Size() < Size())
392     {
393       aMap1 = &theMap;
394       aMap2 = this;
395     }
396
397     for (NCollection_Map::Iterator aIt(*aMap1); aIt.More(); aIt.Next())
398     {
399       if (aMap2->Contains(aIt.Value()))
400       {
401         return Standard_True;
402       }
403     }
404
405     return Standard_False;
406   }
407
408   //! Sets this Map to be the result of intersection (aka multiplication, common, boolean AND) operation between two given Maps.
409   //! The new Map contains only the values that are contained in both map operands.
410   //! All previous content of this Map is cleared.
411   //! This same map (result of the boolean operation) can also be used as one of operands.
412   void Intersection (const NCollection_Map& theLeft,
413                      const NCollection_Map& theRight)
414   {
415     if (&theLeft == &theRight)
416     {
417       Assign (theLeft);
418       return;
419     }
420
421     if (this == &theLeft)
422     {
423       NCollection_Map aCopy (1, this->myAllocator);
424       Exchange     (aCopy);
425       Intersection (aCopy, theRight);
426       return;
427     }
428     else if (this == &theRight)
429     {
430       NCollection_Map aCopy (1, this->myAllocator);
431       Exchange     (aCopy);
432       Intersection (theLeft, aCopy);
433       return;
434     }
435
436     Clear();
437     if (theLeft.Extent() < theRight.Extent())
438     {
439       for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
440       {
441         if (theRight.Contains (anIter.Key()))
442         {
443           Add (anIter.Key());
444         }
445       }
446     }
447     else
448     {
449       for (Iterator anIter (theRight); anIter.More(); anIter.Next())
450       {
451         if (theLeft.Contains (anIter.Key()))
452         {
453           Add (anIter.Key());
454         }
455       }
456     }
457   }
458
459   //! Apply to this Map the intersection operation (aka multiplication, common, boolean AND) with another (given) Map.
460   //! The result contains only the values that are contained in both this and the given maps.
461   //! This algorithm is similar to method Intersection().
462   //! Returns True if contents of this map is changed.
463   Standard_Boolean Intersect (const NCollection_Map& theOther)
464   {
465     if (this == &theOther
466      || IsEmpty())
467     {
468       return Standard_False;
469     }
470
471     const Standard_Integer anOldExtent = Extent();
472     Intersection (*this, theOther);
473     return anOldExtent != Extent();
474   }
475
476   //! Sets this Map to be the result of subtraction (aka set-theoretic difference, relative complement,
477   //! exclude, cut, boolean NOT) operation between two given Maps.
478   //! The new Map contains only the values that are contained in the first map operands and not contained in the second one.
479   //! All previous content of this Map is cleared.
480   void Subtraction (const NCollection_Map& theLeft,
481                     const NCollection_Map& theRight)
482   {
483     if (this == &theLeft)
484     {
485       Subtract (theRight);
486       return;
487     }
488     else if (this == &theRight)
489     {
490       NCollection_Map aCopy (1, this->myAllocator);
491       Exchange    (aCopy);
492       Subtraction (theLeft, aCopy);
493       return;
494     }
495
496     Assign   (theLeft);
497     Subtract (theRight);
498   }
499
500   //! Apply to this Map the subtraction (aka set-theoretic difference, relative complement,
501   //! exclude, cut, boolean NOT) operation with another (given) Map.
502   //! The result contains only the values that were previously contained in this map and not contained in this map.
503   //! This algorithm is similar to method Subtract() with two operands.
504   //! Returns True if contents of this map is changed.
505   Standard_Boolean Subtract (const NCollection_Map& theOther)
506   {
507     if (this == &theOther)
508     {
509       if (IsEmpty())
510       {
511         return Standard_False;
512       }
513
514       Clear();
515       return Standard_True;
516     }
517
518     const Standard_Integer anOldExtent = Extent();
519     for (Iterator anIter (theOther); anIter.More(); anIter.Next())
520     {
521       Remove (anIter.Key());
522     }
523     return anOldExtent != Extent();
524   }
525
526   //! Sets this Map to be the result of symmetric difference (aka exclusive disjunction, boolean XOR) operation between two given Maps.
527   //! The new Map contains the values that are contained only in the first or the second operand maps but not in both.
528   //! All previous content of this Map is cleared. This map (result of the boolean operation) can also be used as one of operands.
529   void Difference (const NCollection_Map& theLeft,
530                    const NCollection_Map& theRight)
531   {
532     if (&theLeft == &theRight)
533     {
534       Clear();
535       return;
536     }
537     else if (this == &theLeft)
538     {
539       NCollection_Map aCopy (1, this->myAllocator);
540       Exchange   (aCopy);
541       Difference (aCopy, theRight);
542       return;
543     }
544     else if (this == &theRight)
545     {
546       NCollection_Map aCopy (1, this->myAllocator);
547       Exchange   (aCopy);
548       Difference (theLeft, aCopy);
549       return;
550     }
551
552     Clear();
553     for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
554     {
555       if (!theRight.Contains (anIter.Key()))
556       {
557         Add (anIter.Key());
558       }
559     }
560     for (Iterator anIter (theRight); anIter.More(); anIter.Next())
561     {
562       if (!theLeft.Contains (anIter.Key()))
563       {
564         Add (anIter.Key());
565       }
566     }
567   }
568
569   //! Apply to this Map the symmetric difference (aka exclusive disjunction, boolean XOR) operation with another (given) Map.
570   //! The result contains the values that are contained only in this or the operand map, but not in both.
571   //! This algorithm is similar to method Difference().
572   //! Returns True if contents of this map is changed.
573   Standard_Boolean Differ (const NCollection_Map& theOther)
574   {
575     if (this == &theOther)
576     {
577       if (IsEmpty())
578       {
579         return Standard_False;
580       }
581       Clear();
582       return Standard_True;
583     }
584
585     const Standard_Integer anOldExtent = Extent();
586     Difference (*this, theOther);
587     return anOldExtent != Extent();
588   }
589
590   //!@}
591 };
592
593 #endif