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