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> |
26 | |
27 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
28 | #include <Standard_NoSuchObject.hxx> |
29 | #endif |
30 | |
7fd59977 |
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 | */ |
9991c9c2 |
58 | |
59 | template < class TheKeyType, |
ddf2fe8e |
60 | class Hasher = NCollection_DefaultHasher<TheKeyType> > |
61 | class NCollection_Map : public NCollection_BaseMap |
7fd59977 |
62 | { |
63 | //! Adaptation of the TListNode to the map notations |
64 | public: |
9991c9c2 |
65 | |
7fd59977 |
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. |
ddf2fe8e |
81 | class Iterator : public NCollection_BaseMap::Iterator |
7fd59977 |
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 |
ddf2fe8e |
91 | Standard_Boolean More(void) const |
7fd59977 |
92 | { return PMore(); } |
93 | //! Make a step along the collection |
ddf2fe8e |
94 | void Next(void) |
7fd59977 |
95 | { PNext(); } |
96 | //! Value inquiry |
ddf2fe8e |
97 | const TheKeyType& Value(void) const |
7fd59977 |
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 |
ddf2fe8e |
106 | TheKeyType& ChangeValue(void) const |
7fd59977 |
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 | } |
7fd59977 |
120 | }; |
79a35943 |
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(); } |
7fd59977 |
130 | |
131 | public: |
132 | // ---------- PUBLIC METHODS ------------ |
133 | |
134 | //! Constructor |
135 | NCollection_Map (const Standard_Integer NbBuckets = 1, |
ddf2fe8e |
136 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) : |
137 | NCollection_BaseMap (NbBuckets, Standard_True, theAllocator) {} |
7fd59977 |
138 | |
139 | //! Copy constructor |
ddf2fe8e |
140 | NCollection_Map (const NCollection_Map& theOther) : |
141 | NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator) |
7fd59977 |
142 | { *this = theOther; } |
143 | |
ab2db9a5 |
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 | { |
ddf2fe8e |
148 | this->exchangeMapsData (theOther); |
ab2db9a5 |
149 | } |
150 | |
ddf2fe8e |
151 | //! Assign |
152 | NCollection_Map& Assign (const NCollection_Map& theOther) |
7fd59977 |
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 | |
ddf2fe8e |
165 | //! Assign operator |
166 | NCollection_Map& operator= (const NCollection_Map& theOther) |
167 | { |
168 | return Assign(theOther); |
169 | } |
170 | |
7fd59977 |
171 | //! ReSize |
172 | void ReSize (const Standard_Integer N) |
173 | { |
fd03ee4b |
174 | NCollection_ListNode** newdata = 0L; |
175 | NCollection_ListNode** dummy = 0L; |
7fd59977 |
176 | Standard_Integer newBuck; |
ddf2fe8e |
177 | if (BeginResize (N, newBuck, newdata, dummy)) |
7fd59977 |
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 | { |
9991c9c2 |
191 | k = Hasher::HashCode(p->Key(),newBuck); |
7fd59977 |
192 | q = (MapNode*) p->Next(); |
193 | p->Next() = newdata[k]; |
194 | newdata[k] = p; |
195 | p = q; |
196 | } |
197 | } |
198 | } |
199 | } |
ddf2fe8e |
200 | EndResize (N, newBuck, newdata, dummy); |
7fd59977 |
201 | } |
202 | } |
203 | |
204 | //! Add |
205 | Standard_Boolean Add(const TheKeyType& K) |
206 | { |
207 | if (Resizable()) |
208 | ReSize(Extent()); |
209 | MapNode** data = (MapNode**)myData1; |
9991c9c2 |
210 | Standard_Integer k = Hasher::HashCode(K,NbBuckets()); |
7fd59977 |
211 | MapNode* p = data[k]; |
212 | while (p) |
213 | { |
9991c9c2 |
214 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
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; |
9991c9c2 |
230 | Standard_Integer k = Hasher::HashCode(K,NbBuckets()); |
7fd59977 |
231 | MapNode* p = data[k]; |
232 | while (p) |
233 | { |
9991c9c2 |
234 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
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; |
9991c9c2 |
249 | MapNode* p = data[Hasher::HashCode(K,NbBuckets())]; |
7fd59977 |
250 | while (p) |
251 | { |
9991c9c2 |
252 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
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; |
9991c9c2 |
265 | Standard_Integer k = Hasher::HashCode(K,NbBuckets()); |
7fd59977 |
266 | MapNode* p = data[k]; |
267 | MapNode* q = NULL; |
268 | while (p) |
269 | { |
9991c9c2 |
270 | if (Hasher::IsEqual(p->Key(),K)) |
7fd59977 |
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) |
ddf2fe8e |
290 | { Destroy (MapNode::delNode, doReleaseMemory); } |
7fd59977 |
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 |
ddf2fe8e |
305 | Standard_Integer Size(void) const |
7fd59977 |
306 | { return Extent(); } |
307 | |
ab2db9a5 |
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 | //!@} |
7fd59977 |
577 | }; |
578 | |
7fd59977 |
579 | #endif |