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