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