b311480e |
1 | // Created on: 2002-04-23 |
2 | // Created by: Alexander KARTOMIN (akm) |
973c2be1 |
3 | // Copyright (c) 2002-2014 OPEN CASCADE SAS |
b311480e |
4 | // |
973c2be1 |
5 | // This file is part of Open CASCADE Technology software library. |
b311480e |
6 | // |
d5f74e42 |
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 |
973c2be1 |
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. |
b311480e |
12 | // |
973c2be1 |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
b311480e |
15 | |
7fd59977 |
16 | #ifndef NCollection_Map_HeaderFile |
17 | #define NCollection_Map_HeaderFile |
18 | |
7fd59977 |
19 | #include <NCollection_BaseMap.hxx> |
ab2db9a5 |
20 | #include <NCollection_DataMap.hxx> |
7fd59977 |
21 | #include <NCollection_TListNode.hxx> |
79a35943 |
22 | #include <NCollection_StlIterator.hxx> |
9991c9c2 |
23 | #include <NCollection_DefaultHasher.hxx> |
24 | |
7fd59977 |
25 | #include <Standard_ImmutableObject.hxx> |
7fd59977 |
26 | #include <Standard_NoSuchObject.hxx> |
7fd59977 |
27 | |
7fd59977 |
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 | */ |
9991c9c2 |
55 | |
56 | template < class TheKeyType, |
ddf2fe8e |
57 | class Hasher = NCollection_DefaultHasher<TheKeyType> > |
58 | class NCollection_Map : public NCollection_BaseMap |
7fd59977 |
59 | { |
60 | //! Adaptation of the TListNode to the map notations |
61 | public: |
9991c9c2 |
62 | |
7fd59977 |
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. |
ddf2fe8e |
78 | class Iterator : public NCollection_BaseMap::Iterator |
7fd59977 |
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 |
ddf2fe8e |
88 | Standard_Boolean More(void) const |
7fd59977 |
89 | { return PMore(); } |
90 | //! Make a step along the collection |
ddf2fe8e |
91 | void Next(void) |
7fd59977 |
92 | { PNext(); } |
93 | //! Value inquiry |
ddf2fe8e |
94 | const TheKeyType& Value(void) const |
7fd59977 |
95 | { |
e3a6386d |
96 | Standard_NoSuchObject_Raise_if (!More(), "NCollection_Map::Iterator::Value"); |
7fd59977 |
97 | return ((MapNode *) myNode)->Value(); |
98 | } |
99 | //! Value change access - denied |
ddf2fe8e |
100 | TheKeyType& ChangeValue(void) const |
7fd59977 |
101 | { |
102 | Standard_ImmutableObject::Raise("NCollection_Map::Iterator::ChangeValue"); |
103 | return * (TheKeyType *) NULL; // For compiler |
104 | } |
105 | //! Key |
e3a6386d |
106 | const TheKeyType& Key (void) const |
7fd59977 |
107 | { |
e3a6386d |
108 | Standard_NoSuchObject_Raise_if (!More(), "NCollection_Map::Iterator::Key"); |
7fd59977 |
109 | return ((MapNode *) myNode)->Value(); |
110 | } |
7fd59977 |
111 | }; |
79a35943 |
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(); } |
7fd59977 |
121 | |
122 | public: |
123 | // ---------- PUBLIC METHODS ------------ |
124 | |
125 | //! Constructor |
126 | NCollection_Map (const Standard_Integer NbBuckets = 1, |
ddf2fe8e |
127 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) : |
128 | NCollection_BaseMap (NbBuckets, Standard_True, theAllocator) {} |
7fd59977 |
129 | |
130 | //! Copy constructor |
ddf2fe8e |
131 | NCollection_Map (const NCollection_Map& theOther) : |
132 | NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator) |
7fd59977 |
133 | { *this = theOther; } |
134 | |
ab2db9a5 |
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 | { |
ddf2fe8e |
139 | this->exchangeMapsData (theOther); |
ab2db9a5 |
140 | } |
141 | |
ddf2fe8e |
142 | //! Assign |
143 | NCollection_Map& Assign (const NCollection_Map& theOther) |
7fd59977 |
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 | |
ddf2fe8e |
156 | //! Assign operator |
157 | NCollection_Map& operator= (const NCollection_Map& theOther) |
158 | { |
159 | return Assign(theOther); |
160 | } |
161 | |
7fd59977 |
162 | //! ReSize |
163 | void ReSize (const Standard_Integer N) |
164 | { |
fd03ee4b |
165 | NCollection_ListNode** newdata = 0L; |
166 | NCollection_ListNode** dummy = 0L; |
7fd59977 |
167 | Standard_Integer newBuck; |
ddf2fe8e |
168 | if (BeginResize (N, newBuck, newdata, dummy)) |
7fd59977 |
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 | { |
9991c9c2 |
182 | k = Hasher::HashCode(p->Key(),newBuck); |
7fd59977 |
183 | q = (MapNode*) p->Next(); |
184 | p->Next() = newdata[k]; |
185 | newdata[k] = p; |
186 | p = q; |
187 | } |
188 | } |
189 | } |
190 | } |
ddf2fe8e |
191 | EndResize (N, newBuck, newdata, dummy); |
7fd59977 |
192 | } |
193 | } |
194 | |
195 | //! Add |
196 | Standard_Boolean Add(const TheKeyType& K) |
197 | { |
198 | if (Resizable()) |
199 | ReSize(Extent()); |
200 | MapNode** data = (MapNode**)myData1; |
9991c9c2 |
201 | Standard_Integer k = Hasher::HashCode(K,NbBuckets()); |
7fd59977 |
202 | MapNode* p = data[k]; |
203 | while (p) |
204 | { |
9991c9c2 |
205 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
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; |
9991c9c2 |
221 | Standard_Integer k = Hasher::HashCode(K,NbBuckets()); |
7fd59977 |
222 | MapNode* p = data[k]; |
223 | while (p) |
224 | { |
9991c9c2 |
225 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
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; |
9991c9c2 |
240 | MapNode* p = data[Hasher::HashCode(K,NbBuckets())]; |
7fd59977 |
241 | while (p) |
242 | { |
9991c9c2 |
243 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
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; |
9991c9c2 |
256 | Standard_Integer k = Hasher::HashCode(K,NbBuckets()); |
7fd59977 |
257 | MapNode* p = data[k]; |
258 | MapNode* q = NULL; |
259 | while (p) |
260 | { |
9991c9c2 |
261 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
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) |
ddf2fe8e |
281 | { Destroy (MapNode::delNode, doReleaseMemory); } |
7fd59977 |
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 |
ddf2fe8e |
296 | Standard_Integer Size(void) const |
7fd59977 |
297 | { return Extent(); } |
298 | |
ab2db9a5 |
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 | //!@} |
7fd59977 |
568 | }; |
569 | |
7fd59977 |
570 | #endif |