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