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