b311480e |
1 | // Created on: 2002-04-24 |
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_DoubleMap_HeaderFile |
17 | #define NCollection_DoubleMap_HeaderFile |
18 | |
19 | #include <NCollection_TypeDef.hxx> |
7fd59977 |
20 | #include <NCollection_BaseMap.hxx> |
21 | #include <NCollection_TListNode.hxx> |
22 | #include <Standard_TypeMismatch.hxx> |
23 | #include <Standard_MultiplyDefined.hxx> |
24 | #include <Standard_ImmutableObject.hxx> |
25 | #include <Standard_NoSuchObject.hxx> |
26 | |
9991c9c2 |
27 | #include <NCollection_DefaultHasher.hxx> |
28 | |
7fd59977 |
29 | /** |
30 | * Purpose: The DoubleMap is used to bind pairs (Key1,Key2) |
31 | * and retrieve them in linear time. |
32 | * |
33 | * See Map from NCollection for a discussion about the number |
34 | * of buckets |
35 | */ |
9991c9c2 |
36 | |
37 | template < class TheKey1Type, |
38 | class TheKey2Type, |
39 | class Hasher1 = NCollection_DefaultHasher<TheKey1Type>, |
ddf2fe8e |
40 | class Hasher2 = NCollection_DefaultHasher<TheKey2Type> > |
41 | class NCollection_DoubleMap : public NCollection_BaseMap |
7fd59977 |
42 | { |
43 | // **************** Adaptation of the TListNode to the DOUBLEmap |
44 | public: |
45 | class DoubleMapNode : public NCollection_TListNode<TheKey2Type> |
46 | { |
47 | public: |
48 | //! Constructor with 'Next' |
49 | DoubleMapNode (const TheKey1Type& theKey1, |
50 | const TheKey2Type& theKey2, |
51 | NCollection_ListNode* theNext1, |
52 | NCollection_ListNode* theNext2) : |
e3a6386d |
53 | NCollection_TListNode<TheKey2Type> (theKey2, theNext1), |
54 | myKey1(theKey1), |
55 | myNext2((DoubleMapNode*)theNext2) |
7fd59977 |
56 | { |
7fd59977 |
57 | } |
58 | //! Key1 |
59 | const TheKey1Type& Key1 (void) |
60 | { return myKey1; } |
61 | //! Key2 |
62 | const TheKey2Type& Key2 (void) |
63 | { return this->myValue; } |
64 | //! Next2 |
65 | DoubleMapNode*& Next2 (void) |
66 | { return myNext2; } |
67 | |
68 | //! Static deleter to be passed to BaseList |
69 | static void delNode (NCollection_ListNode * theNode, |
70 | Handle(NCollection_BaseAllocator)& theAl) |
71 | { |
72 | ((DoubleMapNode *) theNode)->~DoubleMapNode(); |
73 | theAl->Free(theNode); |
74 | } |
75 | |
76 | private: |
77 | TheKey1Type myKey1; |
78 | DoubleMapNode *myNext2; |
79 | }; |
80 | |
81 | public: |
82 | // **************** Implementation of the Iterator interface. |
ddf2fe8e |
83 | class Iterator : public NCollection_BaseMap::Iterator |
7fd59977 |
84 | { |
85 | public: |
86 | //! Empty constructor |
ddf2fe8e |
87 | Iterator (void) {} |
7fd59977 |
88 | //! Constructor |
89 | Iterator (const NCollection_DoubleMap& theMap) : |
90 | NCollection_BaseMap::Iterator(theMap) {} |
91 | //! Query if the end of collection is reached by iterator |
ddf2fe8e |
92 | Standard_Boolean More(void) const |
7fd59977 |
93 | { return PMore(); } |
94 | //! Make a step along the collection |
ddf2fe8e |
95 | void Next(void) |
7fd59977 |
96 | { PNext(); } |
97 | //! Key1 inquiry |
98 | const TheKey1Type& Key1(void) const |
99 | { |
e3a6386d |
100 | Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key1"); |
7fd59977 |
101 | return ((DoubleMapNode *) myNode)->Key1(); |
102 | } |
103 | //! Key2 inquiry |
104 | const TheKey2Type& Key2(void) const |
105 | { |
e3a6386d |
106 | Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Key2"); |
7fd59977 |
107 | return ((DoubleMapNode *) myNode)->Key2(); |
108 | } |
109 | //! Value access |
ddf2fe8e |
110 | const TheKey2Type& Value(void) const |
7fd59977 |
111 | { |
e3a6386d |
112 | Standard_NoSuchObject_Raise_if (!More(), "NCollection_DoubleMap::Iterator::Value"); |
7fd59977 |
113 | return ((DoubleMapNode *) myNode)->Value(); |
114 | } |
115 | //! Value change access - denied |
ddf2fe8e |
116 | TheKey2Type& ChangeValue(void) const |
7fd59977 |
117 | { |
118 | Standard_ImmutableObject::Raise("NCollection_DoubleMap::Iterator::ChangeValue"); |
119 | return * (TheKey2Type *) NULL; // For compiler |
120 | } |
7fd59977 |
121 | }; |
122 | |
123 | public: |
124 | // ---------- PUBLIC METHODS ------------ |
125 | |
126 | //! Constructor |
127 | NCollection_DoubleMap (const Standard_Integer NbBuckets=1, |
128 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
ddf2fe8e |
129 | : NCollection_BaseMap (NbBuckets, Standard_False, theAllocator) {} |
7fd59977 |
130 | |
131 | //! Copy constructor |
132 | NCollection_DoubleMap (const NCollection_DoubleMap& theOther) |
ddf2fe8e |
133 | : NCollection_BaseMap (theOther.NbBuckets(), Standard_False, theOther.myAllocator) |
7fd59977 |
134 | { *this = theOther; } |
135 | |
ab2db9a5 |
136 | //! Exchange the content of two maps without re-allocations. |
137 | //! Notice that allocators will be swapped as well! |
138 | void Exchange (NCollection_DoubleMap& theOther) |
139 | { |
ddf2fe8e |
140 | this->exchangeMapsData (theOther); |
ab2db9a5 |
141 | } |
142 | |
5e452c37 |
143 | //! Assignment. |
144 | //! This method does not change the internal allocator. |
ddf2fe8e |
145 | NCollection_DoubleMap& Assign (const NCollection_DoubleMap& theOther) |
7fd59977 |
146 | { |
147 | if (this == &theOther) |
148 | return *this; |
149 | |
5e452c37 |
150 | Clear(); |
7fd59977 |
151 | ReSize (theOther.Extent()-1); |
152 | Iterator anIter(theOther); |
153 | for (; anIter.More(); anIter.Next()) |
154 | { |
155 | TheKey1Type aKey1 = anIter.Key1(); |
156 | TheKey2Type aKey2 = anIter.Key2(); |
9991c9c2 |
157 | Standard_Integer iK1 = Hasher1::HashCode (aKey1, NbBuckets()); |
158 | Standard_Integer iK2 = Hasher2::HashCode (aKey2, NbBuckets()); |
7fd59977 |
159 | DoubleMapNode * pNode = new (this->myAllocator) DoubleMapNode (aKey1, aKey2, |
160 | myData1[iK1], |
161 | myData2[iK2]); |
162 | myData1[iK1] = pNode; |
163 | myData2[iK2] = pNode; |
164 | Increment(); |
165 | } |
166 | return *this; |
167 | } |
168 | |
ddf2fe8e |
169 | //! Assignment operator |
170 | NCollection_DoubleMap& operator= (const NCollection_DoubleMap& theOther) |
5e452c37 |
171 | { |
ddf2fe8e |
172 | return Assign (theOther); |
173 | } |
174 | |
7fd59977 |
175 | //! ReSize |
176 | void ReSize (const Standard_Integer N) |
177 | { |
fd03ee4b |
178 | NCollection_ListNode** ppNewData1 = NULL; |
179 | NCollection_ListNode** ppNewData2 = NULL; |
7fd59977 |
180 | Standard_Integer newBuck; |
ddf2fe8e |
181 | if (BeginResize (N, newBuck, ppNewData1, ppNewData2)) |
7fd59977 |
182 | { |
183 | if (myData1) |
184 | { |
185 | DoubleMapNode *p, *q; |
186 | Standard_Integer i, iK1, iK2; |
187 | for (i = 0; i <= NbBuckets(); i++) |
188 | { |
189 | if (myData1[i]) |
190 | { |
191 | p = (DoubleMapNode *) myData1[i]; |
192 | while (p) |
193 | { |
9991c9c2 |
194 | iK1 = Hasher1::HashCode (p->Key1(), newBuck); |
195 | iK2 = Hasher2::HashCode (p->Key2(), newBuck); |
7fd59977 |
196 | q = (DoubleMapNode*) p->Next(); |
197 | p->Next() = ppNewData1[iK1]; |
fd03ee4b |
198 | p->Next2() = (DoubleMapNode*)ppNewData2[iK2]; |
7fd59977 |
199 | ppNewData1[iK1] = p; |
200 | ppNewData2[iK2] = p; |
201 | p = q; |
202 | } |
203 | } |
204 | } |
205 | } |
ddf2fe8e |
206 | EndResize (N, newBuck, ppNewData1, ppNewData2); |
7fd59977 |
207 | } |
208 | } |
209 | |
210 | //! Bind |
211 | void Bind (const TheKey1Type& theKey1, const TheKey2Type& theKey2) |
212 | { |
213 | if (Resizable()) |
214 | ReSize(Extent()); |
9991c9c2 |
215 | Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); |
216 | Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); |
7fd59977 |
217 | DoubleMapNode * pNode; |
218 | pNode = (DoubleMapNode *) myData1[iK1]; |
219 | while (pNode) |
220 | { |
9991c9c2 |
221 | if (Hasher1::IsEqual (pNode->Key1(), theKey1)) |
7fd59977 |
222 | Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind"); |
223 | pNode = (DoubleMapNode *) pNode->Next(); |
224 | } |
225 | pNode = (DoubleMapNode *) myData2[iK2]; |
226 | while (pNode) |
227 | { |
9991c9c2 |
228 | if (Hasher2::IsEqual (pNode->Key2(), theKey2)) |
7fd59977 |
229 | Standard_MultiplyDefined::Raise("NCollection_DoubleMap:Bind"); |
230 | pNode = (DoubleMapNode *) pNode->Next(); |
231 | } |
232 | pNode = new (this->myAllocator) DoubleMapNode (theKey1, theKey2, |
233 | myData1[iK1], myData2[iK2]); |
234 | myData1[iK1] = pNode; |
235 | myData2[iK2] = pNode; |
236 | Increment(); |
237 | } |
238 | |
239 | //!* AreBound |
240 | Standard_Boolean AreBound (const TheKey1Type& theKey1, |
241 | const TheKey2Type& theKey2) const |
242 | { |
243 | if (IsEmpty()) |
244 | return Standard_False; |
9991c9c2 |
245 | Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); |
246 | Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); |
7fd59977 |
247 | DoubleMapNode * pNode1, * pNode2; |
248 | pNode1 = (DoubleMapNode *) myData1[iK1]; |
249 | while (pNode1) |
250 | { |
9991c9c2 |
251 | if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) |
7fd59977 |
252 | break; |
253 | pNode1 = (DoubleMapNode *) pNode1->Next(); |
254 | } |
255 | if (pNode1 == NULL) |
256 | return Standard_False; |
257 | pNode2 = (DoubleMapNode *) myData2[iK2]; |
258 | while (pNode2) |
259 | { |
9991c9c2 |
260 | if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) |
7fd59977 |
261 | break; |
262 | pNode2 = (DoubleMapNode *) pNode2->Next(); |
263 | } |
264 | if (pNode2 == NULL) |
265 | return Standard_False; |
266 | |
267 | return (pNode1 == pNode2); |
268 | } |
269 | |
270 | //! IsBound1 |
271 | Standard_Boolean IsBound1 (const TheKey1Type& theKey1) const |
272 | { |
273 | if (IsEmpty()) |
274 | return Standard_False; |
9991c9c2 |
275 | Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); |
7fd59977 |
276 | DoubleMapNode * pNode1; |
277 | pNode1 = (DoubleMapNode *) myData1[iK1]; |
278 | while (pNode1) |
279 | { |
9991c9c2 |
280 | if (Hasher1::IsEqual(pNode1->Key1(), theKey1)) |
7fd59977 |
281 | return Standard_True; |
282 | pNode1 = (DoubleMapNode *) pNode1->Next(); |
283 | } |
284 | return Standard_False; |
285 | } |
286 | |
287 | //! IsBound2 |
288 | Standard_Boolean IsBound2 (const TheKey2Type& theKey2) const |
289 | { |
290 | if (IsEmpty()) |
291 | return Standard_False; |
9991c9c2 |
292 | Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); |
7fd59977 |
293 | DoubleMapNode * pNode2; |
294 | pNode2 = (DoubleMapNode *) myData2[iK2]; |
295 | while (pNode2) |
296 | { |
9991c9c2 |
297 | if (Hasher2::IsEqual(pNode2->Key2(), theKey2)) |
7fd59977 |
298 | return Standard_True; |
299 | pNode2 = (DoubleMapNode *) pNode2->Next2(); |
300 | } |
301 | return Standard_False; |
302 | } |
303 | |
304 | //! UnBind1 |
305 | Standard_Boolean UnBind1 (const TheKey1Type& theKey1) |
306 | { |
307 | if (IsEmpty()) |
308 | return Standard_False; |
9991c9c2 |
309 | Standard_Integer iK1 = Hasher1::HashCode (theKey1, NbBuckets()); |
7fd59977 |
310 | DoubleMapNode * p1, * p2, * q1, *q2; |
311 | q1 = q2 = NULL; |
312 | p1 = (DoubleMapNode *) myData1[iK1]; |
313 | while (p1) |
314 | { |
9991c9c2 |
315 | if (Hasher1::IsEqual (p1->Key1(), theKey1)) |
7fd59977 |
316 | { |
317 | // remove from the data1 |
318 | if (q1) |
319 | q1->Next() = p1->Next(); |
320 | else |
321 | myData1[iK1] = (DoubleMapNode*) p1->Next(); |
9991c9c2 |
322 | Standard_Integer iK2 = Hasher2::HashCode (p1->Key2(), NbBuckets()); |
7fd59977 |
323 | p2 = (DoubleMapNode *) myData2[iK2]; |
324 | while (p2) |
325 | { |
326 | if (p2 == p1) |
327 | { |
328 | // remove from the data2 |
329 | if (q2) |
330 | q2->Next2() = p2->Next2(); |
331 | else |
332 | myData2[iK2] = (DoubleMapNode*) p2->Next2(); |
333 | break; |
334 | } |
335 | q2 = p2; |
336 | p2 = (DoubleMapNode*) p2->Next2(); |
337 | } |
338 | p1->~DoubleMapNode(); |
339 | this->myAllocator->Free(p1); |
340 | Decrement(); |
341 | return Standard_True; |
342 | } |
343 | q1 = p1; |
344 | p1 = (DoubleMapNode*) p1->Next(); |
345 | } |
346 | return Standard_False; |
347 | } |
348 | |
349 | //! UnBind2 |
350 | Standard_Boolean UnBind2 (const TheKey2Type& theKey2) |
351 | { |
352 | if (IsEmpty()) |
353 | return Standard_False; |
9991c9c2 |
354 | Standard_Integer iK2 = Hasher2::HashCode (theKey2, NbBuckets()); |
7fd59977 |
355 | DoubleMapNode * p1, * p2, * q1, *q2; |
356 | q1 = q2 = NULL; |
357 | p2 = (DoubleMapNode *) myData2[iK2]; |
358 | while (p2) |
359 | { |
9991c9c2 |
360 | if (Hasher2::IsEqual (p2->Key2(), theKey2)) |
7fd59977 |
361 | { |
362 | // remove from the data2 |
363 | if (q2) |
364 | q2->Next() = p2->Next(); |
365 | else |
366 | myData2[iK2] = (DoubleMapNode*) p2->Next2(); |
9991c9c2 |
367 | Standard_Integer iK1 = Hasher1::HashCode (p2->Key1(), NbBuckets()); |
7fd59977 |
368 | p1 = (DoubleMapNode *) myData1[iK1]; |
369 | while (p1) |
370 | { |
371 | if (p1 == p2) |
372 | { |
373 | // remove from the data1 |
374 | if (q1) |
375 | q1->Next() = p1->Next(); |
376 | else |
377 | myData1[iK1] = (DoubleMapNode*) p1->Next(); |
378 | break; |
379 | } |
380 | q1 = p1; |
381 | p1 = (DoubleMapNode*) p1->Next(); |
382 | } |
383 | p2->~DoubleMapNode(); |
384 | this->myAllocator->Free(p2); |
385 | Decrement(); |
386 | return Standard_True; |
387 | } |
388 | q2 = p2; |
389 | p2 = (DoubleMapNode*) p2->Next2(); |
390 | } |
391 | return Standard_False; |
392 | } |
393 | |
394 | //! Find1 |
395 | const TheKey2Type& Find1(const TheKey1Type& theKey1) const |
396 | { |
e3a6386d |
397 | Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DoubleMap::Find1"); |
7fd59977 |
398 | DoubleMapNode * pNode1 = |
9991c9c2 |
399 | (DoubleMapNode *) myData1[Hasher1::HashCode(theKey1,NbBuckets())]; |
7fd59977 |
400 | while (pNode1) |
401 | { |
9991c9c2 |
402 | if (Hasher1::IsEqual (pNode1->Key1(), theKey1)) |
7fd59977 |
403 | return pNode1->Key2(); |
404 | pNode1 = (DoubleMapNode*) pNode1->Next(); |
405 | } |
406 | Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find1"); |
407 | return pNode1->Key2(); // This for compiler |
408 | } |
409 | |
410 | //! Find2 |
411 | const TheKey1Type& Find2(const TheKey2Type& theKey2) const |
412 | { |
e3a6386d |
413 | Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DoubleMap::Find2"); |
7fd59977 |
414 | DoubleMapNode * pNode2 = |
9991c9c2 |
415 | (DoubleMapNode *) myData2[Hasher2::HashCode(theKey2,NbBuckets())]; |
7fd59977 |
416 | while (pNode2) |
417 | { |
9991c9c2 |
418 | if (Hasher2::IsEqual (pNode2->Key2(), theKey2)) |
7fd59977 |
419 | return pNode2->Key1(); |
420 | pNode2 = (DoubleMapNode*) pNode2->Next2(); |
421 | } |
422 | Standard_NoSuchObject::Raise("NCollection_DoubleMap::Find2"); |
423 | return pNode2->Key1(); // This for compiler |
424 | } |
425 | |
426 | //! Clear data. If doReleaseMemory is false then the table of |
427 | //! buckets is not released and will be reused. |
428 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
ddf2fe8e |
429 | { Destroy (DoubleMapNode::delNode, doReleaseMemory); } |
7fd59977 |
430 | |
431 | //! Clear data and reset allocator |
432 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
433 | { |
434 | Clear(); |
435 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
436 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
437 | } |
438 | |
439 | //! Destructor |
440 | ~NCollection_DoubleMap (void) |
441 | { Clear(); } |
442 | |
443 | //! Size |
ddf2fe8e |
444 | Standard_Integer Size(void) const |
7fd59977 |
445 | { return Extent(); } |
7fd59977 |
446 | }; |
447 | |
7fd59977 |
448 | #endif |