b311480e |
1 | // Created on: 2002-04-24 |
2 | // Created by: Alexander KARTOMIN (akm) |
3 | // Copyright (c) 2002-2012 OPEN CASCADE SAS |
4 | // |
5 | // The content of this file is subject to the Open CASCADE Technology Public |
6 | // License Version 6.5 (the "License"). You may not use the content of this file |
7 | // except in compliance with the License. Please obtain a copy of the License |
8 | // at http://www.opencascade.org and read it completely before using this file. |
9 | // |
10 | // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its |
11 | // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. |
12 | // |
13 | // The Original Code and all software distributed under the License is |
14 | // distributed on an "AS IS" basis, without warranty of any kind, and the |
15 | // Initial Developer hereby disclaims all such warranties, including without |
16 | // limitation, any warranties of merchantability, fitness for a particular |
17 | // purpose or non-infringement. Please see the License for the specific terms |
18 | // and conditions governing the rights and limitations under the License. |
19 | |
7fd59977 |
20 | |
21 | #ifndef NCollection_IndexedMap_HeaderFile |
22 | #define NCollection_IndexedMap_HeaderFile |
23 | |
24 | #include <NCollection_BaseCollection.hxx> |
25 | #include <NCollection_BaseMap.hxx> |
26 | #include <NCollection_TListNode.hxx> |
27 | #include <Standard_NoSuchObject.hxx> |
28 | #include <Standard_ImmutableObject.hxx> |
29 | |
9991c9c2 |
30 | #include <NCollection_DefaultHasher.hxx> |
31 | |
7fd59977 |
32 | #if !defined No_Exception && !defined No_Standard_OutOfRange |
33 | #include <Standard_OutOfRange.hxx> |
34 | #endif |
35 | |
7fd59977 |
36 | /** |
37 | * Purpose: An indexed map is used to store keys and to bind |
38 | * an index to them. Each new key stored in the map |
39 | * gets an index. Index are incremented as keys are |
40 | * stored in the map. A key can be found by the index |
41 | * and an index by the key. No key but the last can |
42 | * be removed so the indices are in the range 1..Extent. |
43 | * See the class Map from NCollection for a |
44 | * discussion about the number of buckets. |
45 | */ |
9991c9c2 |
46 | |
47 | template < class TheKeyType, |
48 | class Hasher = NCollection_DefaultHasher<TheKeyType> > |
49 | class NCollection_IndexedMap |
7fd59977 |
50 | : public NCollection_BaseCollection<TheKeyType>, |
51 | public NCollection_BaseMap |
52 | { |
53 | // **************** Adaptation of the TListNode to the INDEXEDmap |
54 | private: |
55 | class IndexedMapNode : public NCollection_TListNode<TheKeyType> |
56 | { |
57 | public: |
58 | //! Constructor with 'Next' |
59 | IndexedMapNode (const TheKeyType& theKey1, |
60 | const Standard_Integer theKey2, |
61 | NCollection_ListNode* theNext1, |
62 | NCollection_ListNode* theNext2) : |
63 | NCollection_TListNode<TheKeyType> (theKey1, theNext1) |
64 | { |
65 | myKey2 = theKey2; |
66 | myNext2 = (IndexedMapNode *) theNext2; |
67 | } |
68 | //! Key1 |
69 | TheKeyType& Key1 (void) |
70 | { return this->ChangeValue(); } |
71 | //! Key2 |
72 | const Standard_Integer& Key2 (void) |
73 | { return myKey2; } |
74 | //! Next2 |
75 | IndexedMapNode*& Next2 (void) |
76 | { return myNext2; } |
77 | |
78 | //! Static deleter to be passed to BaseList |
79 | static void delNode (NCollection_ListNode * theNode, |
80 | Handle(NCollection_BaseAllocator)& theAl) |
81 | { |
82 | ((IndexedMapNode *) theNode)->~IndexedMapNode(); |
83 | theAl->Free(theNode); |
84 | } |
85 | |
86 | private: |
87 | Standard_Integer myKey2; |
88 | IndexedMapNode * myNext2; |
89 | }; |
90 | |
91 | public: |
92 | // **************** Implementation of the Iterator interface. |
93 | class Iterator |
94 | : public NCollection_BaseCollection<TheKeyType>::Iterator |
95 | { |
96 | public: |
97 | //! Empty constructor |
98 | Iterator (void) : |
99 | myMap(NULL), |
100 | myIndex(0) {} |
101 | //! Constructor |
102 | Iterator (const NCollection_IndexedMap& theMap) : |
103 | myMap((NCollection_IndexedMap *) &theMap), |
104 | myIndex(1) {} |
105 | //! Query if the end of collection is reached by iterator |
106 | virtual Standard_Boolean More(void) const |
107 | { return (myIndex <= myMap->Extent()); } |
108 | //! Make a step along the collection |
109 | virtual void Next(void) |
110 | { myIndex++; } |
111 | //! Value access |
112 | virtual const TheKeyType& Value(void) const |
113 | { |
114 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
115 | if (!More()) |
116 | Standard_NoSuchObject::Raise("NCollection_IndexedMap::Iterator::Value"); |
117 | #endif |
118 | return myMap->FindKey(myIndex); |
119 | } |
120 | //! Value change access denied - use Substitute |
121 | virtual TheKeyType& ChangeValue(void) const |
122 | { |
123 | Standard_ImmutableObject::Raise ("impossible to ChangeValue"); |
124 | return * (TheKeyType *) NULL; // This for compiler |
125 | } |
126 | |
7fd59977 |
127 | private: |
128 | NCollection_IndexedMap * myMap; // Pointer to the map being iterated |
129 | Standard_Integer myIndex; // Current index |
130 | }; |
131 | |
132 | public: |
133 | // ---------- PUBLIC METHODS ------------ |
134 | |
135 | //! Constructor |
136 | NCollection_IndexedMap (const Standard_Integer NbBuckets=1, |
137 | const Handle(NCollection_BaseAllocator)& theAllocator=0L) : |
138 | NCollection_BaseCollection<TheKeyType>(theAllocator), |
139 | NCollection_BaseMap (NbBuckets, Standard_False) {} |
140 | |
141 | //! Copy constructor |
142 | NCollection_IndexedMap (const NCollection_IndexedMap& theOther) : |
143 | NCollection_BaseCollection<TheKeyType>(theOther.myAllocator), |
144 | NCollection_BaseMap (theOther.NbBuckets(), Standard_False) |
145 | { *this = theOther; } |
146 | |
147 | //! Assign another collection |
148 | virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther) |
149 | { |
150 | if (this == &theOther) |
151 | return; |
152 | Clear(); |
153 | ReSize (theOther.Size()-1); |
154 | TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& anIter = |
155 | theOther.CreateIterator(); |
156 | for (; anIter.More(); anIter.Next()) |
157 | Add(anIter.Value()); |
158 | } |
159 | |
160 | //! = another map |
161 | NCollection_IndexedMap& operator= (const NCollection_IndexedMap& theOther) |
162 | { |
163 | if (this == &theOther) |
164 | return *this; |
165 | |
166 | Clear(theOther.myAllocator); |
167 | ReSize (theOther.Extent()-1); |
168 | Standard_Integer i, iLength=theOther.Extent(); |
169 | for (i=1; i<=iLength; i++) |
170 | { |
171 | TheKeyType aKey1 = theOther(i); |
9991c9c2 |
172 | Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets()); |
173 | Standard_Integer iK2 = ::HashCode (i, NbBuckets()); |
7fd59977 |
174 | IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i, |
175 | myData1[iK1], |
176 | myData2[iK2]); |
177 | myData1[iK1] = pNode; |
178 | myData2[iK2] = pNode; |
179 | Increment(); |
180 | } |
181 | return *this; |
182 | } |
183 | |
184 | //! ReSize |
185 | void ReSize (const Standard_Integer N) |
186 | { |
187 | IndexedMapNode** ppNewData1 = NULL; |
188 | IndexedMapNode** ppNewData2 = NULL; |
189 | Standard_Integer newBuck; |
190 | if (BeginResize (N, newBuck, |
191 | (NCollection_ListNode**&)ppNewData1, |
192 | (NCollection_ListNode**&)ppNewData2, |
193 | this->myAllocator)) |
194 | { |
195 | if (myData1) |
196 | { |
197 | IndexedMapNode *p, *q; |
198 | Standard_Integer i, iK1, iK2; |
199 | for (i = 0; i <= NbBuckets(); i++) |
200 | { |
201 | if (myData1[i]) |
202 | { |
203 | p = (IndexedMapNode *) myData1[i]; |
204 | while (p) |
205 | { |
9991c9c2 |
206 | iK1 =Hasher::HashCode(p->Key1(), newBuck); |
7fd59977 |
207 | q = (IndexedMapNode*) p->Next(); |
208 | p->Next() = ppNewData1[iK1]; |
209 | ppNewData1[iK1] = p; |
210 | if (p->Key2() > 0) |
211 | { |
9991c9c2 |
212 | iK2 = ::HashCode (p->Key2(), newBuck); |
7fd59977 |
213 | p->Next2() = ppNewData2[iK2]; |
214 | ppNewData2[iK2] = p; |
215 | } |
216 | p = q; |
217 | } |
218 | } |
219 | } |
220 | } |
221 | EndResize(N,newBuck, |
222 | (NCollection_ListNode**&)ppNewData1, |
223 | (NCollection_ListNode**&)ppNewData2, |
224 | this->myAllocator); |
225 | } |
226 | } |
227 | |
228 | //! Add |
229 | Standard_Integer Add (const TheKeyType& theKey1) |
230 | { |
231 | if (Resizable()) |
232 | ReSize(Extent()); |
9991c9c2 |
233 | Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); |
7fd59977 |
234 | IndexedMapNode * pNode; |
235 | pNode = (IndexedMapNode *) myData1[iK1]; |
236 | while (pNode) |
237 | { |
9991c9c2 |
238 | if (Hasher::IsEqual (pNode->Key1(), theKey1)) |
7fd59977 |
239 | return pNode->Key2(); |
240 | pNode = (IndexedMapNode *) pNode->Next(); |
241 | } |
242 | Increment(); |
9991c9c2 |
243 | Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets()); |
7fd59977 |
244 | pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(), |
245 | myData1[iK1], myData2[iK2]); |
246 | myData1[iK1] = pNode; |
247 | myData2[iK2] = pNode; |
248 | return Extent(); |
249 | } |
250 | |
251 | //! Contains |
252 | Standard_Boolean Contains (const TheKeyType& theKey1) const |
253 | { |
254 | if (IsEmpty()) |
255 | return Standard_False; |
9991c9c2 |
256 | Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); |
7fd59977 |
257 | IndexedMapNode * pNode1; |
258 | pNode1 = (IndexedMapNode *) myData1[iK1]; |
259 | while (pNode1) |
260 | { |
9991c9c2 |
261 | if (Hasher::IsEqual(pNode1->Key1(), theKey1)) |
7fd59977 |
262 | return Standard_True; |
263 | pNode1 = (IndexedMapNode *) pNode1->Next(); |
264 | } |
265 | return Standard_False; |
266 | } |
267 | |
268 | //! Substitute |
269 | void Substitute (const Standard_Integer theIndex, |
270 | const TheKeyType& theKey1) |
271 | { |
272 | #if !defined No_Exception && !defined No_Standard_OutOfRange |
273 | if (theIndex < 1 || theIndex > Extent()) |
274 | Standard_OutOfRange::Raise ("NCollection_IndexedMap::Substitute"); |
275 | #endif |
276 | IndexedMapNode * p; |
277 | // check if theKey1 is not already in the map |
9991c9c2 |
278 | Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets()); |
7fd59977 |
279 | p = (IndexedMapNode *) myData1[iK1]; |
280 | while (p) |
281 | { |
9991c9c2 |
282 | if (Hasher::IsEqual (p->Key1(), theKey1)) |
7fd59977 |
283 | Standard_DomainError::Raise("NCollection_IndexedMap::Substitute"); |
284 | p = (IndexedMapNode *) p->Next(); |
285 | } |
286 | |
287 | // Find the node for the index I |
9991c9c2 |
288 | Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets()); |
7fd59977 |
289 | p = (IndexedMapNode *) myData2[iK2]; |
290 | while (p) |
291 | { |
292 | if (p->Key2() == theIndex) |
293 | break; |
294 | p = (IndexedMapNode*) p->Next2(); |
295 | } |
296 | |
297 | // remove the old key |
9991c9c2 |
298 | Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets()); |
7fd59977 |
299 | IndexedMapNode * q = (IndexedMapNode *) myData1[iK]; |
300 | if (q == p) |
301 | myData1[iK] = (IndexedMapNode *) p->Next(); |
302 | else |
303 | { |
304 | while (q->Next() != p) |
305 | q = (IndexedMapNode *) q->Next(); |
306 | q->Next() = p->Next(); |
307 | } |
308 | |
309 | // update the node |
310 | p->Key1() = theKey1; |
311 | p->Next() = myData1[iK1]; |
312 | myData1[iK1] = p; |
313 | } |
314 | |
315 | //! RemoveLast |
316 | void RemoveLast (void) |
317 | { |
318 | #if !defined No_Exception && !defined No_Standard_OutOfRange |
319 | if (Extent() == 0) |
320 | Standard_OutOfRange::Raise ("NCollection_IndexedMap::RemoveLast"); |
321 | #endif |
322 | IndexedMapNode * p, * q; |
323 | // Find the node for the last index and remove it |
9991c9c2 |
324 | Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets()); |
7fd59977 |
325 | p = (IndexedMapNode *) myData2[iK2]; |
326 | q = NULL; |
327 | while (p) |
328 | { |
329 | if (p->Key2() == Extent()) |
330 | break; |
331 | q = p; |
332 | p = (IndexedMapNode*) p->Next2(); |
333 | } |
334 | if (q == NULL) |
335 | myData2[iK2] = (IndexedMapNode *) p->Next2(); |
336 | else |
337 | q->Next2() = p->Next2(); |
338 | |
339 | // remove the key |
9991c9c2 |
340 | Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets()); |
7fd59977 |
341 | q = (IndexedMapNode *) myData1[iK1]; |
342 | if (q == p) |
343 | myData1[iK1] = (IndexedMapNode *) p->Next(); |
344 | else |
345 | { |
346 | while (q->Next() != p) |
347 | q = (IndexedMapNode *) q->Next(); |
348 | q->Next() = p->Next(); |
349 | } |
350 | p->~IndexedMapNode(); |
351 | this->myAllocator->Free(p); |
352 | Decrement(); |
353 | } |
354 | |
355 | //! FindKey |
356 | const TheKeyType& FindKey (const Standard_Integer theKey2) const |
357 | { |
358 | #if !defined No_Exception && !defined No_Standard_OutOfRange |
359 | if (theKey2 < 1 || theKey2 > Extent()) |
360 | Standard_OutOfRange::Raise ("NCollection_IndexedMap::FindKey"); |
361 | #endif |
362 | IndexedMapNode * pNode2 = |
9991c9c2 |
363 | (IndexedMapNode *) myData2[::HashCode(theKey2,NbBuckets())]; |
7fd59977 |
364 | while (pNode2) |
365 | { |
366 | if (pNode2->Key2() == theKey2) |
367 | return pNode2->Key1(); |
368 | pNode2 = (IndexedMapNode*) pNode2->Next2(); |
369 | } |
370 | Standard_NoSuchObject::Raise("NCollection_IndexedMap::FindKey"); |
371 | return pNode2->Key1(); // This for compiler |
372 | } |
373 | |
374 | //! operator () |
375 | const TheKeyType& operator() (const Standard_Integer theKey2) const |
376 | { return FindKey (theKey2); } |
377 | |
378 | //! FindIndex |
379 | Standard_Integer FindIndex(const TheKeyType& theKey1) const |
380 | { |
381 | if (IsEmpty()) return 0; |
382 | IndexedMapNode * pNode1 = |
9991c9c2 |
383 | (IndexedMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())]; |
7fd59977 |
384 | while (pNode1) |
385 | { |
9991c9c2 |
386 | if (Hasher::IsEqual (pNode1->Key1(), theKey1)) |
7fd59977 |
387 | return pNode1->Key2(); |
388 | pNode1 = (IndexedMapNode*) pNode1->Next(); |
389 | } |
390 | return 0; |
391 | } |
392 | |
393 | //! Clear data. If doReleaseMemory is false then the table of |
394 | //! buckets is not released and will be reused. |
395 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
396 | { Destroy (IndexedMapNode::delNode, this->myAllocator, doReleaseMemory); } |
397 | |
398 | //! Clear data and reset allocator |
399 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
400 | { |
401 | Clear(); |
402 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
403 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
404 | } |
405 | |
406 | //! Destructor |
407 | ~NCollection_IndexedMap (void) |
408 | { Clear(); } |
409 | |
410 | //! Size |
411 | virtual Standard_Integer Size(void) const |
412 | { return Extent(); } |
413 | |
414 | private: |
415 | // ----------- PRIVATE METHODS ----------- |
416 | |
417 | //! Creates Iterator for use on BaseCollection |
418 | virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& |
419 | CreateIterator(void) const |
420 | { return *(new (this->IterAllocator()) Iterator(*this)); } |
421 | |
422 | }; |
423 | |
7fd59977 |
424 | #endif |