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