0024271: Provide Boolean operations for NCollection_Map
[occt.git] / src / NCollection / NCollection_DataMap.hxx
CommitLineData
b311480e 1// Created on: 2002-04-24
2// Created by: Alexander KARTOMIN (akm)
3// Copyright (c) 2002-2012 OPEN CASCADE SAS
4//
5// The content of this file is subject to the Open CASCADE Technology Public
6// License Version 6.5 (the "License"). You may not use the content of this file
7// except in compliance with the License. Please obtain a copy of the License
8// at http://www.opencascade.org and read it completely before using this file.
9//
10// The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
11// main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
12//
13// The Original Code and all software distributed under the License is
14// distributed on an "AS IS" basis, without warranty of any kind, and the
15// Initial Developer hereby disclaims all such warranties, including without
16// limitation, any warranties of merchantability, fitness for a particular
17// purpose or non-infringement. Please see the License for the specific terms
18// and conditions governing the rights and limitations under the License.
19
7fd59977 20#ifndef NCollection_DataMap_HeaderFile
21#define NCollection_DataMap_HeaderFile
22
23#include <NCollection_BaseCollection.hxx>
24#include <NCollection_BaseMap.hxx>
25#include <NCollection_TListNode.hxx>
26
9991c9c2 27#include <NCollection_DefaultHasher.hxx>
28
7fd59977 29#include <Standard_TypeMismatch.hxx>
30#include <Standard_NoSuchObject.hxx>
31
7fd59977 32/**
33* Purpose: The DataMap is a Map to store keys with associated
34* Items. See Map from NCollection for a discussion
35* about the number of buckets.
36*
37* The DataMap can be seen as an extended array where
38* the Keys are the indices. For this reason the
39* operator () is defined on DataMap to fetch an Item
40* from a Key. So the following syntax can be used :
41*
42* anItem = aMap(aKey);
43* aMap(aKey) = anItem;
44*
45* This analogy has its limit. aMap(aKey) = anItem
46* can be done only if aKey was previously bound to
47* an item in the map.
48*/
9991c9c2 49
50template < class TheKeyType,
51 class TheItemType,
52 class Hasher = NCollection_DefaultHasher<TheKeyType> > class NCollection_DataMap
53
7fd59977 54 : public NCollection_BaseCollection<TheItemType>,
55 public NCollection_BaseMap
56{
57 // **************** Adaptation of the TListNode to the DATAmap
58 public:
59 class DataMapNode : public NCollection_TListNode<TheItemType>
60 {
61 public:
62 //! Constructor with 'Next'
63 DataMapNode (const TheKeyType& theKey,
64 const TheItemType& theItem,
65 NCollection_ListNode* theNext) :
66 NCollection_TListNode<TheItemType> (theItem, theNext)
67 { myKey = theKey; }
68 //! Key
69 const TheKeyType& Key (void) const
70 { return myKey; }
71
72 //! Static deleter to be passed to BaseList
73 static void delNode (NCollection_ListNode * theNode,
74 Handle(NCollection_BaseAllocator)& theAl)
75 {
76 ((DataMapNode *) theNode)->~DataMapNode();
77 theAl->Free(theNode);
78 }
79
80 private:
81 TheKeyType myKey;
82 };
83
84 public:
85 // **************** Implementation of the Iterator interface.
86 class Iterator
87 : public NCollection_BaseCollection<TheItemType>::Iterator,
88 public NCollection_BaseMap::Iterator
89 {
90 public:
91 //! Empty constructor
92 Iterator (void) :
93 NCollection_BaseMap::Iterator() {}
94 //! Constructor
95 Iterator (const NCollection_DataMap& theMap) :
96 NCollection_BaseMap::Iterator(theMap) {}
97 //! Query if the end of collection is reached by iterator
98 virtual Standard_Boolean More(void) const
99 { return PMore(); }
100 //! Make a step along the collection
101 virtual void Next(void)
102 { PNext(); }
103 //! Value inquiry
104 virtual const TheItemType& Value(void) const
105 {
106#if !defined No_Exception && !defined No_Standard_NoSuchObject
107 if (!More())
108 Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Value");
109#endif
110 return ((DataMapNode *) myNode)->Value();
111 }
112 //! Value change access
113 virtual TheItemType& ChangeValue(void) const
114 {
115#if !defined No_Exception && !defined No_Standard_NoSuchObject
116 if (!More())
117 Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::ChangeValue");
118#endif
119 return ((DataMapNode *) myNode)->ChangeValue();
120 }
121 //! Key
122 const TheKeyType& Key (void) const
123 {
124#if !defined No_Exception && !defined No_Standard_NoSuchObject
125 if (!More())
126 Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Key");
127#endif
128 return ((DataMapNode *) myNode)->Key();
129 }
7fd59977 130 };
131
132 public:
133 // ---------- PUBLIC METHODS ------------
134
135 //! Constructor
136 NCollection_DataMap (const Standard_Integer NbBuckets=1,
137 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
138 : NCollection_BaseCollection<TheItemType>(theAllocator),
139 NCollection_BaseMap (NbBuckets, Standard_True) {}
140
141 //! Copy constructor
142 NCollection_DataMap (const NCollection_DataMap& theOther)
143 : NCollection_BaseCollection<TheItemType>(theOther.myAllocator),
144 NCollection_BaseMap (theOther.NbBuckets(), Standard_True)
145 { *this = theOther; }
146
147 //! Assign another collection
148 virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther)
149 {
150 if (this == &theOther)
151 return;
152 Standard_TypeMismatch::Raise ("NCollection_DataMap::Assign impossible");
153 }
154
ab2db9a5 155 //! Exchange the content of two maps without re-allocations.
156 //! Notice that allocators will be swapped as well!
157 void Exchange (NCollection_DataMap& theOther)
158 {
159 this->exchangeAllocators (theOther);
160 this->exchangeMapsData (theOther);
161 }
162
7fd59977 163 //! = another map
164 NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
165 {
166 if (this == &theOther)
167 return *this;
168
169 Clear(theOther.myAllocator);
170 ReSize (theOther.Extent()-1);
171 Iterator anIter(theOther);
172 for (; anIter.More(); anIter.Next())
173 Bind (anIter.Key(), anIter.Value());
174 return *this;
175 }
176
177 //! ReSize
178 void ReSize (const Standard_Integer N)
179 {
180 DataMapNode** newdata = NULL;
181 DataMapNode** dummy = NULL;
182 Standard_Integer newBuck;
183 if (BeginResize (N, newBuck,
184 (NCollection_ListNode**&)newdata,
185 (NCollection_ListNode**&)dummy,
186 this->myAllocator))
187 {
188 if (myData1)
189 {
190 DataMapNode** olddata = (DataMapNode**) myData1;
191 DataMapNode *p, *q;
192 Standard_Integer i,k;
193 for (i = 0; i <= NbBuckets(); i++)
194 {
195 if (olddata[i])
196 {
197 p = olddata[i];
198 while (p)
199 {
9991c9c2 200 k = Hasher::HashCode(p->Key(),newBuck);
7fd59977 201 q = (DataMapNode*) p->Next();
202 p->Next() = newdata[k];
203 newdata[k] = p;
204 p = q;
205 }
206 }
207 }
208 }
209 EndResize(N,newBuck,
210 (NCollection_ListNode**&)newdata,
211 (NCollection_ListNode**&)dummy,
212 this->myAllocator);
213 }
214 }
215
216 //! Bind
217 Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
218 {
219 if (Resizable())
220 ReSize(Extent());
221 DataMapNode** data = (DataMapNode**)myData1;
9991c9c2 222 Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
7fd59977 223 DataMapNode* p = data[k];
224 while (p)
225 {
9991c9c2 226 if (Hasher::IsEqual(p->Key(), theKey))
7fd59977 227 {
228 p->ChangeValue() = theItem;
229 return Standard_False;
230 }
231 p = (DataMapNode *) p->Next();
232 }
233 data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
234 Increment();
235 return Standard_True;
236 }
237
238 //! IsBound
239 Standard_Boolean IsBound(const TheKeyType& K) const
240 {
241 if (IsEmpty())
242 return Standard_False;
243 DataMapNode** data = (DataMapNode**) myData1;
9991c9c2 244 DataMapNode* p = data[Hasher::HashCode(K,NbBuckets())];
7fd59977 245 while (p)
246 {
9991c9c2 247 if (Hasher::IsEqual(p->Key(),K))
7fd59977 248 return Standard_True;
249 p = (DataMapNode *) p->Next();
250 }
251 return Standard_False;
252 }
253
254 //! UnBind
255 Standard_Boolean UnBind(const TheKeyType& K)
256 {
257 if (IsEmpty())
258 return Standard_False;
259 DataMapNode** data = (DataMapNode**) myData1;
9991c9c2 260 Standard_Integer k = Hasher::HashCode(K,NbBuckets());
7fd59977 261 DataMapNode* p = data[k];
262 DataMapNode* q = NULL;
263 while (p)
264 {
9991c9c2 265 if (Hasher::IsEqual(p->Key(),K))
7fd59977 266 {
267 Decrement();
268 if (q)
269 q->Next() = p->Next();
270 else
271 data[k] = (DataMapNode*) p->Next();
272 p->~DataMapNode();
273 this->myAllocator->Free(p);
274 return Standard_True;
275 }
276 q = p;
277 p = (DataMapNode*) p->Next();
278 }
279 return Standard_False;
280 }
281
282 //! Find
283 const TheItemType& Find(const TheKeyType& theKey) const
284 {
285#if !defined No_Exception && !defined No_Standard_NoSuchObject
286 if (IsEmpty())
287 Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
288#endif
9991c9c2 289 DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
7fd59977 290 while (p)
291 {
9991c9c2 292 if (Hasher::IsEqual(p->Key(),theKey))
7fd59977 293 return p->Value();
294 p = (DataMapNode*) p->Next();
295 }
296 Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
297 return p->Value(); // This for compiler
298 }
299
a174a3c5 300 //! Find value for key with copying.
301 //! @return true if key was found
302 Standard_Boolean Find (const TheKeyType& theKey,
303 TheItemType& theValue) const
304 {
305 if (IsEmpty())
306 {
307 return Standard_False;
308 }
309
310 for (DataMapNode* aNodeIter = (DataMapNode* )myData1[Hasher::HashCode (theKey, NbBuckets())];
311 aNodeIter != NULL;
312 aNodeIter = (DataMapNode* )aNodeIter->Next())
313 {
314 if (Hasher::IsEqual (aNodeIter->Key(), theKey))
315 {
316 theValue = aNodeIter->Value();
317 return Standard_True;
318 }
319 }
320 return Standard_False;
321 }
322
7fd59977 323 //! operator ()
324 const TheItemType& operator() (const TheKeyType& theKey) const
325 { return Find(theKey); }
326
327 //! ChangeFind
328 TheItemType& ChangeFind (const TheKeyType& theKey)
329 {
330#if !defined No_Exception && !defined No_Standard_NoSuchObject
331 if (IsEmpty())
332 Standard_NoSuchObject::Raise ("NCollection_DataMap::Find");
333#endif
9991c9c2 334 DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
7fd59977 335 while (p)
336 {
9991c9c2 337 if (Hasher::IsEqual(p->Key(),theKey))
7fd59977 338 return p->ChangeValue();
339 p = (DataMapNode*) p->Next();
340 }
341 Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
342 return p->ChangeValue(); // This for compiler
343 }
344
345 //! operator ()
346 TheItemType& operator() (const TheKeyType& theKey)
347 { return ChangeFind(theKey); }
348
349 //! Clear data. If doReleaseMemory is false then the table of
350 //! buckets is not released and will be reused.
351 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
352 { Destroy (DataMapNode::delNode, this->myAllocator, doReleaseMemory); }
353
354 //! Clear data and reset allocator
355 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
356 {
357 Clear();
358 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
359 NCollection_BaseAllocator::CommonBaseAllocator() );
360 }
361
362 //! Destructor
363 ~NCollection_DataMap (void)
364 { Clear(); }
365
366 //! Size
367 virtual Standard_Integer Size(void) const
368 { return Extent(); }
369
370 private:
371 // ----------- PRIVATE METHODS -----------
372
373 //! Creates Iterator for use on BaseCollection
374 virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator&
375 CreateIterator(void) const
376 { return *(new (this->IterAllocator()) Iterator(*this)); }
377
378};
379
7fd59977 380#endif
9991c9c2 381