7fd59977 |
1 | // File: NCollection_DataMap.hxx |
2 | // Created: Thu Apr 24 15:02:53 2002 |
3 | // Author: Alexander KARTOMIN (akm) |
4 | // <akm@opencascade.com> |
5 | |
6 | #ifndef NCollection_DataMap_HeaderFile |
7 | #define NCollection_DataMap_HeaderFile |
8 | |
9 | #include <NCollection_BaseCollection.hxx> |
10 | #include <NCollection_BaseMap.hxx> |
11 | #include <NCollection_TListNode.hxx> |
12 | |
13 | #include <Standard_TypeMismatch.hxx> |
14 | #include <Standard_NoSuchObject.hxx> |
15 | |
16 | #ifdef WNT |
17 | // Disable the warning "operator new unmatched by delete" |
18 | #pragma warning (push) |
19 | #pragma warning (disable:4291) |
20 | #endif |
21 | |
22 | /** |
23 | * Purpose: The DataMap is a Map to store keys with associated |
24 | * Items. See Map from NCollection for a discussion |
25 | * about the number of buckets. |
26 | * |
27 | * The DataMap can be seen as an extended array where |
28 | * the Keys are the indices. For this reason the |
29 | * operator () is defined on DataMap to fetch an Item |
30 | * from a Key. So the following syntax can be used : |
31 | * |
32 | * anItem = aMap(aKey); |
33 | * aMap(aKey) = anItem; |
34 | * |
35 | * This analogy has its limit. aMap(aKey) = anItem |
36 | * can be done only if aKey was previously bound to |
37 | * an item in the map. |
38 | */ |
39 | template <class TheKeyType, class TheItemType> class NCollection_DataMap |
40 | : public NCollection_BaseCollection<TheItemType>, |
41 | public NCollection_BaseMap |
42 | { |
43 | // **************** Adaptation of the TListNode to the DATAmap |
44 | public: |
45 | class DataMapNode : public NCollection_TListNode<TheItemType> |
46 | { |
47 | public: |
48 | //! Constructor with 'Next' |
49 | DataMapNode (const TheKeyType& theKey, |
50 | const TheItemType& theItem, |
51 | NCollection_ListNode* theNext) : |
52 | NCollection_TListNode<TheItemType> (theItem, theNext) |
53 | { myKey = theKey; } |
54 | //! Key |
55 | const TheKeyType& Key (void) const |
56 | { return myKey; } |
57 | |
58 | //! Static deleter to be passed to BaseList |
59 | static void delNode (NCollection_ListNode * theNode, |
60 | Handle(NCollection_BaseAllocator)& theAl) |
61 | { |
62 | ((DataMapNode *) theNode)->~DataMapNode(); |
63 | theAl->Free(theNode); |
64 | } |
65 | |
66 | private: |
67 | TheKeyType myKey; |
68 | }; |
69 | |
70 | public: |
71 | // **************** Implementation of the Iterator interface. |
72 | class Iterator |
73 | : public NCollection_BaseCollection<TheItemType>::Iterator, |
74 | public NCollection_BaseMap::Iterator |
75 | { |
76 | public: |
77 | //! Empty constructor |
78 | Iterator (void) : |
79 | NCollection_BaseMap::Iterator() {} |
80 | //! Constructor |
81 | Iterator (const NCollection_DataMap& theMap) : |
82 | NCollection_BaseMap::Iterator(theMap) {} |
83 | //! Query if the end of collection is reached by iterator |
84 | virtual Standard_Boolean More(void) const |
85 | { return PMore(); } |
86 | //! Make a step along the collection |
87 | virtual void Next(void) |
88 | { PNext(); } |
89 | //! Value inquiry |
90 | virtual const TheItemType& Value(void) const |
91 | { |
92 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
93 | if (!More()) |
94 | Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Value"); |
95 | #endif |
96 | return ((DataMapNode *) myNode)->Value(); |
97 | } |
98 | //! Value change access |
99 | virtual TheItemType& ChangeValue(void) const |
100 | { |
101 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
102 | if (!More()) |
103 | Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::ChangeValue"); |
104 | #endif |
105 | return ((DataMapNode *) myNode)->ChangeValue(); |
106 | } |
107 | //! Key |
108 | const TheKeyType& Key (void) const |
109 | { |
110 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
111 | if (!More()) |
112 | Standard_NoSuchObject::Raise("NCollection_DataMap::Iterator::Key"); |
113 | #endif |
114 | return ((DataMapNode *) myNode)->Key(); |
115 | } |
116 | //! Operator new for allocating iterators |
117 | void* operator new(size_t theSize, |
118 | const Handle(NCollection_BaseAllocator)& theAllocator) |
119 | { return theAllocator->Allocate(theSize); } |
120 | }; |
121 | |
122 | public: |
123 | // ---------- PUBLIC METHODS ------------ |
124 | |
125 | //! Constructor |
126 | NCollection_DataMap (const Standard_Integer NbBuckets=1, |
127 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
128 | : NCollection_BaseCollection<TheItemType>(theAllocator), |
129 | NCollection_BaseMap (NbBuckets, Standard_True) {} |
130 | |
131 | //! Copy constructor |
132 | NCollection_DataMap (const NCollection_DataMap& theOther) |
133 | : NCollection_BaseCollection<TheItemType>(theOther.myAllocator), |
134 | NCollection_BaseMap (theOther.NbBuckets(), Standard_True) |
135 | { *this = theOther; } |
136 | |
137 | //! Assign another collection |
138 | virtual void Assign(const NCollection_BaseCollection<TheItemType>& theOther) |
139 | { |
140 | if (this == &theOther) |
141 | return; |
142 | Standard_TypeMismatch::Raise ("NCollection_DataMap::Assign impossible"); |
143 | } |
144 | |
145 | //! = another map |
146 | NCollection_DataMap& operator= (const NCollection_DataMap& theOther) |
147 | { |
148 | if (this == &theOther) |
149 | return *this; |
150 | |
151 | Clear(theOther.myAllocator); |
152 | ReSize (theOther.Extent()-1); |
153 | Iterator anIter(theOther); |
154 | for (; anIter.More(); anIter.Next()) |
155 | Bind (anIter.Key(), anIter.Value()); |
156 | return *this; |
157 | } |
158 | |
159 | //! ReSize |
160 | void ReSize (const Standard_Integer N) |
161 | { |
162 | DataMapNode** newdata = NULL; |
163 | DataMapNode** dummy = NULL; |
164 | Standard_Integer newBuck; |
165 | if (BeginResize (N, newBuck, |
166 | (NCollection_ListNode**&)newdata, |
167 | (NCollection_ListNode**&)dummy, |
168 | this->myAllocator)) |
169 | { |
170 | if (myData1) |
171 | { |
172 | DataMapNode** olddata = (DataMapNode**) myData1; |
173 | DataMapNode *p, *q; |
174 | Standard_Integer i,k; |
175 | for (i = 0; i <= NbBuckets(); i++) |
176 | { |
177 | if (olddata[i]) |
178 | { |
179 | p = olddata[i]; |
180 | while (p) |
181 | { |
182 | k = HashCode(p->Key(),newBuck); |
183 | q = (DataMapNode*) p->Next(); |
184 | p->Next() = newdata[k]; |
185 | newdata[k] = p; |
186 | p = q; |
187 | } |
188 | } |
189 | } |
190 | } |
191 | EndResize(N,newBuck, |
192 | (NCollection_ListNode**&)newdata, |
193 | (NCollection_ListNode**&)dummy, |
194 | this->myAllocator); |
195 | } |
196 | } |
197 | |
198 | //! Bind |
199 | Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem) |
200 | { |
201 | if (Resizable()) |
202 | ReSize(Extent()); |
203 | DataMapNode** data = (DataMapNode**)myData1; |
204 | Standard_Integer k = HashCode (theKey, NbBuckets()); |
205 | DataMapNode* p = data[k]; |
206 | while (p) |
207 | { |
208 | if (IsEqual(p->Key(), theKey)) |
209 | { |
210 | p->ChangeValue() = theItem; |
211 | return Standard_False; |
212 | } |
213 | p = (DataMapNode *) p->Next(); |
214 | } |
215 | data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]); |
216 | Increment(); |
217 | return Standard_True; |
218 | } |
219 | |
220 | //! IsBound |
221 | Standard_Boolean IsBound(const TheKeyType& K) const |
222 | { |
223 | if (IsEmpty()) |
224 | return Standard_False; |
225 | DataMapNode** data = (DataMapNode**) myData1; |
226 | DataMapNode* p = data[HashCode(K,NbBuckets())]; |
227 | while (p) |
228 | { |
229 | if (IsEqual(p->Key(),K)) |
230 | return Standard_True; |
231 | p = (DataMapNode *) p->Next(); |
232 | } |
233 | return Standard_False; |
234 | } |
235 | |
236 | //! UnBind |
237 | Standard_Boolean UnBind(const TheKeyType& K) |
238 | { |
239 | if (IsEmpty()) |
240 | return Standard_False; |
241 | DataMapNode** data = (DataMapNode**) myData1; |
242 | Standard_Integer k = HashCode(K,NbBuckets()); |
243 | DataMapNode* p = data[k]; |
244 | DataMapNode* q = NULL; |
245 | while (p) |
246 | { |
247 | if (IsEqual(p->Key(),K)) |
248 | { |
249 | Decrement(); |
250 | if (q) |
251 | q->Next() = p->Next(); |
252 | else |
253 | data[k] = (DataMapNode*) p->Next(); |
254 | p->~DataMapNode(); |
255 | this->myAllocator->Free(p); |
256 | return Standard_True; |
257 | } |
258 | q = p; |
259 | p = (DataMapNode*) p->Next(); |
260 | } |
261 | return Standard_False; |
262 | } |
263 | |
264 | //! Find |
265 | const TheItemType& Find(const TheKeyType& theKey) const |
266 | { |
267 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
268 | if (IsEmpty()) |
269 | Standard_NoSuchObject::Raise ("NCollection_DataMap::Find"); |
270 | #endif |
271 | DataMapNode* p = (DataMapNode*) myData1[HashCode(theKey,NbBuckets())]; |
272 | while (p) |
273 | { |
274 | if (IsEqual(p->Key(),theKey)) |
275 | return p->Value(); |
276 | p = (DataMapNode*) p->Next(); |
277 | } |
278 | Standard_NoSuchObject::Raise("NCollection_DataMap::Find"); |
279 | return p->Value(); // This for compiler |
280 | } |
281 | |
282 | //! operator () |
283 | const TheItemType& operator() (const TheKeyType& theKey) const |
284 | { return Find(theKey); } |
285 | |
286 | //! ChangeFind |
287 | TheItemType& ChangeFind (const TheKeyType& theKey) |
288 | { |
289 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
290 | if (IsEmpty()) |
291 | Standard_NoSuchObject::Raise ("NCollection_DataMap::Find"); |
292 | #endif |
293 | DataMapNode* p = (DataMapNode*) myData1[HashCode(theKey,NbBuckets())]; |
294 | while (p) |
295 | { |
296 | if (IsEqual(p->Key(),theKey)) |
297 | return p->ChangeValue(); |
298 | p = (DataMapNode*) p->Next(); |
299 | } |
300 | Standard_NoSuchObject::Raise("NCollection_DataMap::Find"); |
301 | return p->ChangeValue(); // This for compiler |
302 | } |
303 | |
304 | //! operator () |
305 | TheItemType& operator() (const TheKeyType& theKey) |
306 | { return ChangeFind(theKey); } |
307 | |
308 | //! Clear data. If doReleaseMemory is false then the table of |
309 | //! buckets is not released and will be reused. |
310 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
311 | { Destroy (DataMapNode::delNode, this->myAllocator, doReleaseMemory); } |
312 | |
313 | //! Clear data and reset allocator |
314 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
315 | { |
316 | Clear(); |
317 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
318 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
319 | } |
320 | |
321 | //! Destructor |
322 | ~NCollection_DataMap (void) |
323 | { Clear(); } |
324 | |
325 | //! Size |
326 | virtual Standard_Integer Size(void) const |
327 | { return Extent(); } |
328 | |
329 | private: |
330 | // ----------- PRIVATE METHODS ----------- |
331 | |
332 | //! Creates Iterator for use on BaseCollection |
333 | virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator& |
334 | CreateIterator(void) const |
335 | { return *(new (this->IterAllocator()) Iterator(*this)); } |
336 | |
337 | }; |
338 | |
339 | #ifdef WNT |
340 | #pragma warning (pop) |
341 | #endif |
342 | |
343 | #endif |