7fd59977 |
1 | // File: NCollection_Map.hxx |
2 | // Created: Thu Apr 23 15:02:53 2002 |
3 | // Author: Alexander KARTOMIN (akm) |
4 | // <a-kartomin@opencascade.com> |
5 | |
6 | #ifndef NCollection_Map_HeaderFile |
7 | #define NCollection_Map_HeaderFile |
8 | |
9 | #include <NCollection_BaseCollection.hxx> |
10 | #include <NCollection_BaseMap.hxx> |
11 | #include <NCollection_TListNode.hxx> |
12 | #include <Standard_ImmutableObject.hxx> |
13 | |
14 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
15 | #include <Standard_NoSuchObject.hxx> |
16 | #endif |
17 | |
18 | #ifdef WNT |
19 | // Disable the warning "operator new unmatched by delete" |
20 | #pragma warning (push) |
21 | #pragma warning (disable:4291) |
22 | #endif |
23 | |
24 | /** |
25 | * Purpose: Single hashed Map. This Map is used to store and |
26 | * retrieve keys in linear time. |
27 | * |
28 | * The ::Iterator class can be used to explore the |
29 | * content of the map. It is not wise to iterate and |
30 | * modify a map in parallel. |
31 | * |
32 | * To compute the hashcode of the key the function |
33 | * ::HashCode must be defined in the global namespace |
34 | * |
35 | * To compare two keys the function ::IsEqual must be |
36 | * defined in the global namespace. |
37 | * |
38 | * The performance of a Map is conditionned by its |
39 | * number of buckets that should be kept greater to |
40 | * the number of keys. This map has an automatic |
41 | * management of the number of buckets. It is resized |
42 | * when the number of Keys becomes greater than the |
43 | * number of buckets. |
44 | * |
45 | * If you have a fair idea of the number of objects |
46 | * you can save on automatic resizing by giving a |
47 | * number of buckets at creation or using the ReSize |
48 | * method. This should be consider only for crucial |
49 | * optimisation issues. |
50 | */ |
51 | template <class TheKeyType> class NCollection_Map |
52 | : public NCollection_BaseCollection<TheKeyType>, |
53 | public NCollection_BaseMap |
54 | { |
55 | //! Adaptation of the TListNode to the map notations |
56 | public: |
57 | class MapNode : public NCollection_TListNode<TheKeyType> |
58 | { |
59 | public: |
60 | //! Constructor with 'Next' |
61 | MapNode (const TheKeyType& theKey, |
62 | NCollection_ListNode* theNext) : |
63 | NCollection_TListNode<TheKeyType> (theKey, theNext) {} |
64 | //! Key |
65 | const TheKeyType& Key (void) |
66 | { return this->Value(); } |
67 | |
68 | }; |
69 | |
70 | public: |
71 | //! Implementation of the Iterator interface. |
72 | class Iterator |
73 | : public NCollection_BaseCollection<TheKeyType>::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_Map& 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 TheKeyType& Value(void) const |
91 | { |
92 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
93 | if (!More()) |
94 | Standard_NoSuchObject::Raise ("NCollection_Map::Iterator::Value"); |
95 | #endif |
96 | return ((MapNode *) myNode)->Value(); |
97 | } |
98 | //! Value change access - denied |
99 | virtual TheKeyType& ChangeValue(void) const |
100 | { |
101 | Standard_ImmutableObject::Raise("NCollection_Map::Iterator::ChangeValue"); |
102 | return * (TheKeyType *) NULL; // For compiler |
103 | } |
104 | //! Key |
105 | const TheKeyType& Key (void) |
106 | { |
107 | #if !defined No_Exception && !defined No_Standard_NoSuchObject |
108 | if (!More()) |
109 | Standard_NoSuchObject::Raise ("NCollection_Map::Iterator::Key"); |
110 | #endif |
111 | return ((MapNode *) myNode)->Value(); |
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 | |
119 | public: |
120 | // ---------- PUBLIC METHODS ------------ |
121 | |
122 | //! Constructor |
123 | NCollection_Map (const Standard_Integer NbBuckets = 1, |
124 | const Handle(NCollection_BaseAllocator)& theAllocator = 0L) |
125 | : NCollection_BaseCollection<TheKeyType>(theAllocator), |
126 | NCollection_BaseMap (NbBuckets, Standard_True) {} |
127 | |
128 | //! Copy constructor |
129 | NCollection_Map (const NCollection_Map& theOther) |
130 | : NCollection_BaseCollection<TheKeyType>(theOther.myAllocator), |
131 | NCollection_BaseMap (theOther.NbBuckets(), Standard_True) |
132 | { *this = theOther; } |
133 | |
134 | //! Assign another collection |
135 | virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther) |
136 | { |
137 | if (this == &theOther) |
138 | return; |
139 | |
140 | Clear(); |
141 | ReSize (theOther.Size()-1); |
142 | TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& anIter = |
143 | theOther.CreateIterator(); |
144 | for (; anIter.More(); anIter.Next()) |
145 | Add (anIter.Value()); |
146 | } |
147 | |
148 | //! = another map |
149 | NCollection_Map& operator= (const NCollection_Map& theOther) |
150 | { |
151 | if (this == &theOther) |
152 | return *this; |
153 | |
154 | Clear(theOther.myAllocator); |
155 | ReSize (theOther.Extent()-1); |
156 | Iterator anIter(theOther); |
157 | for (; anIter.More(); anIter.Next()) |
158 | Add (anIter.Key()); |
159 | return *this; |
160 | } |
161 | |
162 | //! ReSize |
163 | void ReSize (const Standard_Integer N) |
164 | { |
165 | MapNode** newdata = 0L; |
166 | MapNode** dummy = 0L; |
167 | Standard_Integer newBuck; |
168 | if (BeginResize (N, newBuck, |
169 | (NCollection_ListNode**&)newdata, |
170 | (NCollection_ListNode**&)dummy, |
171 | this->myAllocator)) |
172 | { |
173 | if (myData1) |
174 | { |
175 | MapNode** olddata = (MapNode**) myData1; |
176 | MapNode *p, *q; |
177 | Standard_Integer i,k; |
178 | for (i = 0; i <= NbBuckets(); i++) |
179 | { |
180 | if (olddata[i]) |
181 | { |
182 | p = olddata[i]; |
183 | while (p) |
184 | { |
185 | k = HashCode(p->Key(),newBuck); |
186 | q = (MapNode*) p->Next(); |
187 | p->Next() = newdata[k]; |
188 | newdata[k] = p; |
189 | p = q; |
190 | } |
191 | } |
192 | } |
193 | } |
194 | EndResize(N,newBuck, |
195 | (NCollection_ListNode**&)newdata, |
196 | (NCollection_ListNode**&)dummy, |
197 | this->myAllocator); |
198 | } |
199 | } |
200 | |
201 | //! Add |
202 | Standard_Boolean Add(const TheKeyType& K) |
203 | { |
204 | if (Resizable()) |
205 | ReSize(Extent()); |
206 | MapNode** data = (MapNode**)myData1; |
207 | Standard_Integer k = HashCode(K,NbBuckets()); |
208 | MapNode* p = data[k]; |
209 | while (p) |
210 | { |
211 | if (IsEqual(p->Key(),K)) |
212 | return Standard_False; |
213 | p = (MapNode *) p->Next(); |
214 | } |
215 | data[k] = new (this->myAllocator) MapNode(K,data[k]); |
216 | Increment(); |
217 | return Standard_True; |
218 | } |
219 | |
220 | //! Added: add a new key if not yet in the map, and return |
221 | //! reference to either newly added or previously existing object |
222 | const TheKeyType& Added(const TheKeyType& K) |
223 | { |
224 | if (Resizable()) |
225 | ReSize(Extent()); |
226 | MapNode** data = (MapNode**)myData1; |
227 | Standard_Integer k = HashCode(K,NbBuckets()); |
228 | MapNode* p = data[k]; |
229 | while (p) |
230 | { |
231 | if (IsEqual(p->Key(),K)) |
232 | return p->Key(); |
233 | p = (MapNode *) p->Next(); |
234 | } |
235 | data[k] = new (this->myAllocator) MapNode(K,data[k]); |
236 | Increment(); |
237 | return data[k]->Key(); |
238 | } |
239 | |
240 | //! Contains |
241 | Standard_Boolean Contains(const TheKeyType& K) const |
242 | { |
243 | if (IsEmpty()) |
244 | return Standard_False; |
245 | MapNode** data = (MapNode**) myData1; |
246 | MapNode* p = data[HashCode(K,NbBuckets())]; |
247 | while (p) |
248 | { |
249 | if (IsEqual(p->Key(),K)) |
250 | return Standard_True; |
251 | p = (MapNode *) p->Next(); |
252 | } |
253 | return Standard_False; |
254 | } |
255 | |
256 | //! Remove |
257 | Standard_Boolean Remove(const TheKeyType& K) |
258 | { |
259 | if (IsEmpty()) |
260 | return Standard_False; |
261 | MapNode** data = (MapNode**) myData1; |
262 | Standard_Integer k = HashCode(K,NbBuckets()); |
263 | MapNode* p = data[k]; |
264 | MapNode* q = NULL; |
265 | while (p) |
266 | { |
267 | if (IsEqual(p->Key(),K)) |
268 | { |
269 | Decrement(); |
270 | if (q) |
271 | q->Next() = p->Next(); |
272 | else |
273 | data[k] = (MapNode*) p->Next(); |
274 | p->~MapNode(); |
275 | this->myAllocator->Free(p); |
276 | return Standard_True; |
277 | } |
278 | q = p; |
279 | p = (MapNode*) p->Next(); |
280 | } |
281 | return Standard_False; |
282 | } |
283 | |
284 | //! Clear data. If doReleaseMemory is false then the table of |
285 | //! buckets is not released and will be reused. |
286 | void Clear(const Standard_Boolean doReleaseMemory = Standard_True) |
287 | { Destroy (MapNode::delNode, this->myAllocator, doReleaseMemory); } |
288 | |
289 | //! Clear data and reset allocator |
290 | void Clear (const Handle(NCollection_BaseAllocator)& theAllocator) |
291 | { |
292 | Clear(); |
293 | this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator : |
294 | NCollection_BaseAllocator::CommonBaseAllocator() ); |
295 | } |
296 | |
297 | //! Destructor |
298 | ~NCollection_Map (void) |
299 | { Clear(); } |
300 | |
301 | //! Size |
302 | virtual Standard_Integer Size(void) const |
303 | { return Extent(); } |
304 | |
305 | private: |
306 | // ----------- PRIVATE METHODS ----------- |
307 | |
308 | //! Creates Iterator for use on BaseCollection |
309 | virtual TYPENAME NCollection_BaseCollection<TheKeyType>::Iterator& |
310 | CreateIterator(void) const |
311 | { return *(new (this->IterAllocator()) Iterator(*this)); } |
312 | |
313 | }; |
314 | |
315 | #ifdef WNT |
316 | #pragma warning (pop) |
317 | #endif |
318 | |
319 | #endif |