0025348: Method Assign of NCollection containers must not change own allocator of...
[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_ImmutableObject.hxx>
26 #include <Standard_NoSuchObject.hxx>
27
28 /**
29  * Purpose:     Single hashed Map. This  Map is used  to store and
30  *              retrieve keys in linear time.
31  *              
32  *              The ::Iterator class can be  used to explore  the
33  *              content of the map. It is not  wise to iterate and
34  *              modify a map in parallel.
35  *               
36  *              To compute  the hashcode of  the key the  function
37  *              ::HashCode must be defined in the global namespace
38  *               
39  *              To compare two keys the function ::IsEqual must be
40  *              defined in the global namespace.
41  *               
42  *              The performance of  a Map is conditionned  by  its
43  *              number of buckets that  should be kept greater  to
44  *              the number   of keys.  This  map has  an automatic
45  *              management of the number of buckets. It is resized
46  *              when  the number of Keys  becomes greater than the
47  *              number of buckets.
48  *              
49  *              If you have a fair  idea of the number of  objects
50  *              you  can save on automatic   resizing by giving  a
51  *              number of buckets  at creation or using the ReSize
52  *              method. This should be  consider only for  crucial
53  *              optimisation issues.
54  */            
55
56 template < class TheKeyType, 
57            class Hasher = NCollection_DefaultHasher<TheKeyType> >
58 class NCollection_Map : public NCollection_BaseMap
59 {
60   //!   Adaptation of the TListNode to the map notations
61  public:
62
63   class MapNode : public NCollection_TListNode<TheKeyType>
64   {
65   public:
66     //! Constructor with 'Next'
67     MapNode (const TheKeyType& theKey, 
68              NCollection_ListNode* theNext) :
69       NCollection_TListNode<TheKeyType> (theKey, theNext) {}
70     //! Key
71     const TheKeyType& Key (void)
72     { return this->Value(); }
73
74   };
75
76  public:
77   //!   Implementation of the Iterator interface.
78   class Iterator : public NCollection_BaseMap::Iterator
79   {
80   public:
81     //! Empty constructor
82     Iterator (void) :
83       NCollection_BaseMap::Iterator() {}
84     //! Constructor
85     Iterator (const NCollection_Map& theMap) :
86       NCollection_BaseMap::Iterator(theMap) {}
87     //! Query if the end of collection is reached by iterator
88     Standard_Boolean More(void) const
89     { return PMore(); }
90     //! Make a step along the collection
91     void Next(void)
92     { PNext(); }
93     //! Value inquiry
94     const TheKeyType& Value(void) const
95     {
96       Standard_NoSuchObject_Raise_if (!More(), "NCollection_Map::Iterator::Value");  
97       return ((MapNode *) myNode)->Value();
98     }
99     //! Value change access - denied
100     TheKeyType& ChangeValue(void) const
101     {  
102       Standard_ImmutableObject::Raise("NCollection_Map::Iterator::ChangeValue");
103       return * (TheKeyType *) NULL; // For compiler
104     }
105     //! Key
106     const TheKeyType& Key (void) const
107     { 
108       Standard_NoSuchObject_Raise_if (!More(), "NCollection_Map::Iterator::Key");  
109       return ((MapNode *) myNode)->Value();
110     }
111   };
112   
113   //! Shorthand for a constant iterator type.
114   typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheKeyType, true> const_iterator;
115
116   //! Returns a const iterator pointing to the first element in the map.
117   const_iterator cbegin() const { return Iterator (*this); }
118
119   //! Returns a const iterator referring to the past-the-end element in the map.
120   const_iterator cend() const { return Iterator(); }
121
122  public:
123   // ---------- PUBLIC METHODS ------------
124
125   //! Constructor
126   NCollection_Map (const Standard_Integer NbBuckets = 1,
127                    const Handle(NCollection_BaseAllocator)& theAllocator = 0L) :
128     NCollection_BaseMap (NbBuckets, 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   ~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   //! Sets this Map to be the result of intersection (aka multiplication, common, boolean AND) operation between two given Maps.
387   //! The new Map contains only the values that are contained in both map operands.
388   //! All previous content of this Map is cleared.
389   //! This same map (result of the boolean operation) can also be used as one of operands.
390   void Intersection (const NCollection_Map& theLeft,
391                      const NCollection_Map& theRight)
392   {
393     if (&theLeft == &theRight)
394     {
395       Assign (theLeft);
396       return;
397     }
398
399     if (this == &theLeft)
400     {
401       NCollection_Map aCopy (1, this->myAllocator);
402       Exchange     (aCopy);
403       Intersection (aCopy, theRight);
404       return;
405     }
406     else if (this == &theRight)
407     {
408       NCollection_Map aCopy (1, this->myAllocator);
409       Exchange     (aCopy);
410       Intersection (theLeft, aCopy);
411       return;
412     }
413
414     Clear();
415     if (theLeft.Extent() < theRight.Extent())
416     {
417       for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
418       {
419         if (theRight.Contains (anIter.Key()))
420         {
421           Add (anIter.Key());
422         }
423       }
424     }
425     else
426     {
427       for (Iterator anIter (theRight); anIter.More(); anIter.Next())
428       {
429         if (theLeft.Contains (anIter.Key()))
430         {
431           Add (anIter.Key());
432         }
433       }
434     }
435   }
436
437   //! Apply to this Map the intersection operation (aka multiplication, common, boolean AND) with another (given) Map.
438   //! The result contains only the values that are contained in both this and the given maps.
439   //! This algorithm is similar to method Intersection().
440   //! Returns True if contents of this map is changed.
441   Standard_Boolean Intersect (const NCollection_Map& theOther)
442   {
443     if (this == &theOther
444      || IsEmpty())
445     {
446       return Standard_False;
447     }
448
449     const Standard_Integer anOldExtent = Extent();
450     Intersection (*this, theOther);
451     return anOldExtent != Extent();
452   }
453
454   //! Sets this Map to be the result of subtraction (aka set-theoretic difference, relative complement,
455   //! exclude, cut, boolean NOT) operation between two given Maps.
456   //! The new Map contains only the values that are contained in the first map operands and not contained in the second one.
457   //! All previous content of this Map is cleared.
458   void Subtraction (const NCollection_Map& theLeft,
459                     const NCollection_Map& theRight)
460   {
461     if (this == &theLeft)
462     {
463       Subtract (theRight);
464       return;
465     }
466     else if (this == &theRight)
467     {
468       NCollection_Map aCopy (1, this->myAllocator);
469       Exchange    (aCopy);
470       Subtraction (theLeft, aCopy);
471       return;
472     }
473
474     Assign   (theLeft);
475     Subtract (theRight);
476   }
477
478   //! Apply to this Map the subtraction (aka set-theoretic difference, relative complement,
479   //! exclude, cut, boolean NOT) operation with another (given) Map.
480   //! The result contains only the values that were previously contained in this map and not contained in this map.
481   //! This algorithm is similar to method Subtract() with two operands.
482   //! Returns True if contents of this map is changed.
483   Standard_Boolean Subtract (const NCollection_Map& theOther)
484   {
485     if (this == &theOther)
486     {
487       if (IsEmpty())
488       {
489         return Standard_False;
490       }
491
492       Clear();
493       return Standard_True;
494     }
495
496     const Standard_Integer anOldExtent = Extent();
497     for (Iterator anIter (theOther); anIter.More(); anIter.Next())
498     {
499       Remove (anIter.Key());
500     }
501     return anOldExtent != Extent();
502   }
503
504   //! Sets this Map to be the result of symmetric difference (aka exclusive disjunction, boolean XOR) operation between two given Maps.
505   //! The new Map contains the values that are contained only in the first or the second operand maps but not in both.
506   //! All previous content of this Map is cleared. This map (result of the boolean operation) can also be used as one of operands.
507   void Difference (const NCollection_Map& theLeft,
508                    const NCollection_Map& theRight)
509   {
510     if (&theLeft == &theRight)
511     {
512       Clear();
513       return;
514     }
515     else if (this == &theLeft)
516     {
517       NCollection_Map aCopy (1, this->myAllocator);
518       Exchange   (aCopy);
519       Difference (aCopy, theRight);
520       return;
521     }
522     else if (this == &theRight)
523     {
524       NCollection_Map aCopy (1, this->myAllocator);
525       Exchange   (aCopy);
526       Difference (theLeft, aCopy);
527       return;
528     }
529
530     Clear();
531     for (Iterator anIter (theLeft); anIter.More(); anIter.Next())
532     {
533       if (!theRight.Contains (anIter.Key()))
534       {
535         Add (anIter.Key());
536       }
537     }
538     for (Iterator anIter (theRight); anIter.More(); anIter.Next())
539     {
540       if (!theLeft.Contains (anIter.Key()))
541       {
542         Add (anIter.Key());
543       }
544     }
545   }
546
547   //! Apply to this Map the symmetric difference (aka exclusive disjunction, boolean XOR) operation with another (given) Map.
548   //! The result contains the values that are contained only in this or the operand map, but not in both.
549   //! This algorithm is similar to method Difference().
550   //! Returns True if contents of this map is changed.
551   Standard_Boolean Differ (const NCollection_Map& theOther)
552   {
553     if (this == &theOther)
554     {
555       if (IsEmpty())
556       {
557         return Standard_False;
558       }
559       Clear();
560       return Standard_True;
561     }
562
563     const Standard_Integer anOldExtent = Extent();
564     Difference (*this, theOther);
565     return anOldExtent != Extent();
566   }
567
568   //!@}
569 };
570
571 #endif