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_DataMap_HeaderFile |
17 | #define NCollection_DataMap_HeaderFile |
18 | |
7fd59977 |
19 | #include <NCollection_BaseMap.hxx> |
20 | #include <NCollection_TListNode.hxx> |
79a35943 |
21 | #include <NCollection_StlIterator.hxx> |
9991c9c2 |
22 | #include <NCollection_DefaultHasher.hxx> |
23 | |
7fd59977 |
24 | #include <Standard_TypeMismatch.hxx> |
25 | #include <Standard_NoSuchObject.hxx> |
26 | |
7fd59977 |
27 | /** |
28 | * Purpose: The DataMap is a Map to store keys with associated |
29 | * Items. See Map from NCollection for a discussion |
30 | * about the number of buckets. |
31 | * |
32 | * The DataMap can be seen as an extended array where |
33 | * the Keys are the indices. For this reason the |
34 | * operator () is defined on DataMap to fetch an Item |
35 | * from a Key. So the following syntax can be used : |
36 | * |
37 | * anItem = aMap(aKey); |
38 | * aMap(aKey) = anItem; |
39 | * |
40 | * This analogy has its limit. aMap(aKey) = anItem |
41 | * can be done only if aKey was previously bound to |
42 | * an item in the map. |
43 | */ |
9991c9c2 |
44 | |
45 | template < class TheKeyType, |
46 | class TheItemType, |
ddf2fe8e |
47 | class Hasher = NCollection_DefaultHasher<TheKeyType> > |
48 | class NCollection_DataMap : public NCollection_BaseMap |
7fd59977 |
49 | { |
3f5aa017 |
50 | public: |
51 | //! STL-compliant typedef for key type |
52 | typedef TheKeyType key_type; |
53 | //! STL-compliant typedef for value type |
54 | typedef TheItemType value_type; |
55 | |
56 | public: |
7fd59977 |
57 | // **************** Adaptation of the TListNode to the DATAmap |
7fd59977 |
58 | class DataMapNode : public NCollection_TListNode<TheItemType> |
59 | { |
60 | public: |
61 | //! Constructor with 'Next' |
62 | DataMapNode (const TheKeyType& theKey, |
63 | const TheItemType& theItem, |
64 | NCollection_ListNode* theNext) : |
e3a6386d |
65 | NCollection_TListNode<TheItemType> (theItem, theNext), |
66 | myKey(theKey) |
67 | {} |
68 | |
7fd59977 |
69 | //! Key |
70 | const TheKeyType& Key (void) const |
71 | { return myKey; } |
72 | |
ddf2fe8e |
73 | //! Static deleter to be passed to BaseMap |
7fd59977 |
74 | static void delNode (NCollection_ListNode * theNode, |
75 | Handle(NCollection_BaseAllocator)& theAl) |
76 | { |
77 | ((DataMapNode *) theNode)->~DataMapNode(); |
78 | theAl->Free(theNode); |
79 | } |
80 | |
81 | private: |
82 | TheKeyType myKey; |
83 | }; |
84 | |
85 | public: |
86 | // **************** Implementation of the Iterator interface. |
ddf2fe8e |
87 | class Iterator : public NCollection_BaseMap::Iterator |
7fd59977 |
88 | { |
89 | public: |
90 | //! Empty constructor |
91 | Iterator (void) : |
92 | NCollection_BaseMap::Iterator() {} |
93 | //! Constructor |
94 | Iterator (const NCollection_DataMap& theMap) : |
95 | NCollection_BaseMap::Iterator(theMap) {} |
96 | //! Query if the end of collection is reached by iterator |
ddf2fe8e |
97 | Standard_Boolean More(void) const |
7fd59977 |
98 | { return PMore(); } |
99 | //! Make a step along the collection |
ddf2fe8e |
100 | void Next(void) |
7fd59977 |
101 | { PNext(); } |
102 | //! Value inquiry |
ddf2fe8e |
103 | const TheItemType& Value(void) const |
7fd59977 |
104 | { |
e3a6386d |
105 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Value"); |
7fd59977 |
106 | return ((DataMapNode *) myNode)->Value(); |
107 | } |
108 | //! Value change access |
ddf2fe8e |
109 | TheItemType& ChangeValue(void) const |
7fd59977 |
110 | { |
e3a6386d |
111 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::ChangeValue"); |
7fd59977 |
112 | return ((DataMapNode *) myNode)->ChangeValue(); |
113 | } |
114 | //! Key |
115 | const TheKeyType& Key (void) const |
116 | { |
e3a6386d |
117 | Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Key"); |
7fd59977 |
118 | return ((DataMapNode *) myNode)->Key(); |
119 | } |
7fd59977 |
120 | }; |
79a35943 |
121 | |
122 | //! Shorthand for a regular iterator type. |
123 | typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator; |
124 | |
125 | //! Shorthand for a constant iterator type. |
126 | typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator; |
127 | |
128 | //! Returns an iterator pointing to the first element in the map. |
129 | iterator begin() const { return Iterator (*this); } |
130 | |
131 | //! Returns an iterator referring to the past-the-end element in the map. |
132 | iterator end() const { return Iterator(); } |
133 | |
134 | //! Returns a const iterator pointing to the first element in the map. |
135 | const_iterator cbegin() const { return Iterator (*this); } |
136 | |
137 | //! Returns a const iterator referring to the past-the-end element in the map. |
138 | const_iterator cend() const { return Iterator(); } |
7fd59977 |
139 | |
140 | public: |
141 | // ---------- PUBLIC METHODS ------------ |
142 | |
b6a0525b |
143 | //! Empty Constructor. |
144 | NCollection_DataMap() : NCollection_BaseMap (1, Standard_True, Handle(NCollection_BaseAllocator)()) {} |
145 | |
7fd59977 |
146 | //! Constructor |
b6a0525b |
147 | explicit NCollection_DataMap (const Standard_Integer theNbBuckets, |
148 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
149 | : NCollection_BaseMap (theNbBuckets, Standard_True, theAllocator) {} |
7fd59977 |
150 | |
151 | //! Copy constructor |
152 | NCollection_DataMap (const NCollection_DataMap& theOther) |
ddf2fe8e |
153 | : NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator) |
7fd59977 |
154 | { *this = theOther; } |
155 | |
ab2db9a5 |
156 | //! Exchange the content of two maps without re-allocations. |
157 | //! Notice that allocators will be swapped as well! |
158 | void Exchange (NCollection_DataMap& theOther) |
159 | { |
ddf2fe8e |
160 | this->exchangeMapsData (theOther); |
ab2db9a5 |
161 | } |
162 | |
5e452c37 |
163 | //! Assignment. |
164 | //! This method does not change the internal allocator. |
ddf2fe8e |
165 | NCollection_DataMap& Assign (const NCollection_DataMap& theOther) |
7fd59977 |
166 | { |
167 | if (this == &theOther) |
168 | return *this; |
169 | |
5e452c37 |
170 | Clear(); |
229add78 |
171 | Standard_Integer anExt = theOther.Extent(); |
172 | if (anExt) |
173 | { |
174 | ReSize (anExt-1); |
175 | Iterator anIter(theOther); |
176 | for (; anIter.More(); anIter.Next()) |
177 | Bind (anIter.Key(), anIter.Value()); |
178 | } |
7fd59977 |
179 | return *this; |
180 | } |
181 | |
ddf2fe8e |
182 | //! Assignment operator |
183 | NCollection_DataMap& operator= (const NCollection_DataMap& theOther) |
184 | { |
185 | return Assign (theOther); |
186 | } |
187 | |
7fd59977 |
188 | //! ReSize |
189 | void ReSize (const Standard_Integer N) |
190 | { |
fd03ee4b |
191 | NCollection_ListNode** newdata = NULL; |
192 | NCollection_ListNode** dummy = NULL; |
7fd59977 |
193 | Standard_Integer newBuck; |
ddf2fe8e |
194 | if (BeginResize (N, newBuck, newdata, dummy)) |
7fd59977 |
195 | { |
196 | if (myData1) |
197 | { |
198 | DataMapNode** olddata = (DataMapNode**) myData1; |
199 | DataMapNode *p, *q; |
200 | Standard_Integer i,k; |
201 | for (i = 0; i <= NbBuckets(); i++) |
202 | { |
203 | if (olddata[i]) |
204 | { |
205 | p = olddata[i]; |
206 | while (p) |
207 | { |
9991c9c2 |
208 | k = Hasher::HashCode(p->Key(),newBuck); |
7fd59977 |
209 | q = (DataMapNode*) p->Next(); |
210 | p->Next() = newdata[k]; |
211 | newdata[k] = p; |
212 | p = q; |
213 | } |
214 | } |
215 | } |
216 | } |
ddf2fe8e |
217 | EndResize (N, newBuck, newdata, dummy); |
7fd59977 |
218 | } |
219 | } |
220 | |
94807a7d |
221 | //! Bind binds Item to Key in map. |
222 | //! @param theKey key to add/update |
223 | //! @param theItem new item; overrides value previously bound to the key, if any |
224 | //! @return Standard_True if Key was not bound already |
7fd59977 |
225 | Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem) |
226 | { |
227 | if (Resizable()) |
228 | ReSize(Extent()); |
229 | DataMapNode** data = (DataMapNode**)myData1; |
9991c9c2 |
230 | Standard_Integer k = Hasher::HashCode (theKey, NbBuckets()); |
7fd59977 |
231 | DataMapNode* p = data[k]; |
232 | while (p) |
233 | { |
9991c9c2 |
234 | if (Hasher::IsEqual(p->Key(), theKey)) |
7fd59977 |
235 | { |
236 | p->ChangeValue() = theItem; |
237 | return Standard_False; |
238 | } |
239 | p = (DataMapNode *) p->Next(); |
240 | } |
241 | data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]); |
242 | Increment(); |
243 | return Standard_True; |
244 | } |
245 | |
9df7f429 |
246 | //! Bound binds Item to Key in map. Returns modifiable Item |
247 | TheItemType* Bound (const TheKeyType& theKey, const TheItemType& theItem) |
7fd59977 |
248 | { |
9df7f429 |
249 | if (Resizable()) |
250 | ReSize(Extent()); |
251 | DataMapNode** data = (DataMapNode**)myData1; |
252 | Standard_Integer k = Hasher::HashCode (theKey, NbBuckets()); |
253 | DataMapNode* p = data[k]; |
254 | while (p) |
7fd59977 |
255 | { |
9df7f429 |
256 | if (Hasher::IsEqual(p->Key(), theKey)) |
257 | { |
258 | p->ChangeValue() = theItem; |
259 | return &p->ChangeValue(); |
260 | } |
261 | p = (DataMapNode*)p->Next(); |
7fd59977 |
262 | } |
9df7f429 |
263 | data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]); |
264 | Increment(); |
265 | return &data[k]->ChangeValue(); |
7fd59977 |
266 | } |
267 | |
9df7f429 |
268 | //! IsBound |
997e128f |
269 | Standard_Boolean IsBound(const TheKeyType& theKey) const |
9df7f429 |
270 | { |
271 | DataMapNode* p; |
997e128f |
272 | return lookup(theKey, p); |
9df7f429 |
273 | } |
274 | |
275 | //! UnBind removes Item Key pair from map |
997e128f |
276 | Standard_Boolean UnBind(const TheKeyType& theKey) |
7fd59977 |
277 | { |
278 | if (IsEmpty()) |
279 | return Standard_False; |
280 | DataMapNode** data = (DataMapNode**) myData1; |
997e128f |
281 | Standard_Integer k = Hasher::HashCode(theKey,NbBuckets()); |
7fd59977 |
282 | DataMapNode* p = data[k]; |
283 | DataMapNode* q = NULL; |
284 | while (p) |
285 | { |
997e128f |
286 | if (Hasher::IsEqual(p->Key(), theKey)) |
7fd59977 |
287 | { |
288 | Decrement(); |
289 | if (q) |
290 | q->Next() = p->Next(); |
291 | else |
292 | data[k] = (DataMapNode*) p->Next(); |
293 | p->~DataMapNode(); |
294 | this->myAllocator->Free(p); |
295 | return Standard_True; |
296 | } |
297 | q = p; |
298 | p = (DataMapNode*) p->Next(); |
299 | } |
300 | return Standard_False; |
301 | } |
302 | |
9df7f429 |
303 | //! Seek returns pointer to Item by Key. Returns |
304 | //! NULL is Key was not bound. |
305 | const TheItemType* Seek(const TheKeyType& theKey) const |
306 | { |
307 | DataMapNode* p = 0; |
308 | if (!lookup(theKey, p)) |
309 | return 0L; |
310 | return &p->Value(); |
311 | } |
312 | |
313 | //! Find returns the Item for Key. Raises if Key was not bound |
7fd59977 |
314 | const TheItemType& Find(const TheKeyType& theKey) const |
315 | { |
9df7f429 |
316 | DataMapNode* p = 0; |
317 | if (!lookup(theKey, p)) |
9775fa61 |
318 | throw Standard_NoSuchObject("NCollection_DataMap::Find"); |
9df7f429 |
319 | return p->Value(); |
7fd59977 |
320 | } |
321 | |
9df7f429 |
322 | //! Find Item for key with copying. |
a174a3c5 |
323 | //! @return true if key was found |
324 | Standard_Boolean Find (const TheKeyType& theKey, |
325 | TheItemType& theValue) const |
326 | { |
9df7f429 |
327 | DataMapNode* p = 0; |
328 | if (!lookup(theKey, p)) |
a174a3c5 |
329 | return Standard_False; |
a174a3c5 |
330 | |
9df7f429 |
331 | theValue = p->Value(); |
332 | return Standard_True; |
a174a3c5 |
333 | } |
334 | |
7fd59977 |
335 | //! operator () |
336 | const TheItemType& operator() (const TheKeyType& theKey) const |
337 | { return Find(theKey); } |
338 | |
9df7f429 |
339 | //! ChangeSeek returns modifiable pointer to Item by Key. Returns |
340 | //! NULL is Key was not bound. |
341 | TheItemType* ChangeSeek(const TheKeyType& theKey) |
342 | { |
343 | DataMapNode* p = 0; |
344 | if (!lookup(theKey, p)) |
345 | return 0L; |
346 | return &p->ChangeValue(); |
347 | } |
348 | |
349 | //! ChangeFind returns mofifiable Item by Key. Raises if Key was not bound |
7fd59977 |
350 | TheItemType& ChangeFind (const TheKeyType& theKey) |
351 | { |
9df7f429 |
352 | DataMapNode* p = 0; |
353 | if (!lookup(theKey, p)) |
9775fa61 |
354 | throw Standard_NoSuchObject("NCollection_DataMap::Find"); |
9df7f429 |
355 | return p->ChangeValue(); |
7fd59977 |
356 | } |
357 | |
358 | //! operator () |
359 | TheItemType& operator() (const TheKeyType& theKey) |
360 | { return ChangeFind(theKey); } |
361 | |
362 | //! Clear data. If doReleaseMemory is false then the table of |
363 | //! buckets is not released and will be reused. |
364 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
ddf2fe8e |
365 | { Destroy (DataMapNode::delNode, doReleaseMemory); } |
7fd59977 |
366 | |
367 | //! Clear data and reset allocator |
368 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
369 | { |
370 | Clear(); |
371 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
372 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
373 | } |
374 | |
375 | //! Destructor |
6928e351 |
376 | virtual ~NCollection_DataMap (void) |
7fd59977 |
377 | { Clear(); } |
378 | |
379 | //! Size |
ddf2fe8e |
380 | Standard_Integer Size(void) const |
7fd59977 |
381 | { return Extent(); } |
9df7f429 |
382 | |
383 | |
384 | protected: |
385 | // ---------- PROTECTED METHODS ---------- |
386 | //! Lookup for particular key in map. Returns true if key is found and |
387 | //! thepNode points to binded node. Returns false if key is not found, |
388 | //! thehNode value is this case is not usable. |
389 | Standard_Boolean lookup(const TheKeyType& theKey,DataMapNode*& thepNode) const |
390 | { |
391 | if (IsEmpty()) |
392 | return Standard_False; // Not found |
393 | for (thepNode = (DataMapNode*)myData1[Hasher::HashCode(theKey, NbBuckets())]; |
394 | thepNode; thepNode = (DataMapNode*)thepNode->Next()) |
395 | { |
396 | if (Hasher::IsEqual(thepNode->Key(), theKey)) |
397 | return Standard_True; |
398 | } |
399 | return Standard_False; // Not found |
400 | } |
401 | |
7fd59977 |
402 | }; |
403 | |
7fd59977 |
404 | #endif |
9991c9c2 |
405 | |