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