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