0029492: Coding Rules. NCollection_IndexedDataMap - add missing documentation to...
[occt.git] / src / NCollection / NCollection_DataMap.hxx
CommitLineData
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
45template < class TheKeyType,
46 class TheItemType,
ddf2fe8e 47 class Hasher = NCollection_DefaultHasher<TheKeyType> >
48class NCollection_DataMap : public NCollection_BaseMap
7fd59977 49{
3f5aa017 50public:
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
56public:
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();
7fd59977 171 ReSize (theOther.Extent()-1);
172 Iterator anIter(theOther);
173 for (; anIter.More(); anIter.Next())
174 Bind (anIter.Key(), anIter.Value());
175 return *this;
176 }
177
ddf2fe8e 178 //! Assignment operator
179 NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
180 {
181 return Assign (theOther);
182 }
183
7fd59977 184 //! ReSize
185 void ReSize (const Standard_Integer N)
186 {
fd03ee4b 187 NCollection_ListNode** newdata = NULL;
188 NCollection_ListNode** dummy = NULL;
7fd59977 189 Standard_Integer newBuck;
ddf2fe8e 190 if (BeginResize (N, newBuck, newdata, dummy))
7fd59977 191 {
192 if (myData1)
193 {
194 DataMapNode** olddata = (DataMapNode**) myData1;
195 DataMapNode *p, *q;
196 Standard_Integer i,k;
197 for (i = 0; i <= NbBuckets(); i++)
198 {
199 if (olddata[i])
200 {
201 p = olddata[i];
202 while (p)
203 {
9991c9c2 204 k = Hasher::HashCode(p->Key(),newBuck);
7fd59977 205 q = (DataMapNode*) p->Next();
206 p->Next() = newdata[k];
207 newdata[k] = p;
208 p = q;
209 }
210 }
211 }
212 }
ddf2fe8e 213 EndResize (N, newBuck, newdata, dummy);
7fd59977 214 }
215 }
216
94807a7d 217 //! Bind binds Item to Key in map.
218 //! @param theKey key to add/update
219 //! @param theItem new item; overrides value previously bound to the key, if any
220 //! @return Standard_True if Key was not bound already
7fd59977 221 Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
222 {
223 if (Resizable())
224 ReSize(Extent());
225 DataMapNode** data = (DataMapNode**)myData1;
9991c9c2 226 Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
7fd59977 227 DataMapNode* p = data[k];
228 while (p)
229 {
9991c9c2 230 if (Hasher::IsEqual(p->Key(), theKey))
7fd59977 231 {
232 p->ChangeValue() = theItem;
233 return Standard_False;
234 }
235 p = (DataMapNode *) p->Next();
236 }
237 data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
238 Increment();
239 return Standard_True;
240 }
241
9df7f429 242 //! Bound binds Item to Key in map. Returns modifiable Item
243 TheItemType* Bound (const TheKeyType& theKey, const TheItemType& theItem)
7fd59977 244 {
9df7f429 245 if (Resizable())
246 ReSize(Extent());
247 DataMapNode** data = (DataMapNode**)myData1;
248 Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
249 DataMapNode* p = data[k];
250 while (p)
7fd59977 251 {
9df7f429 252 if (Hasher::IsEqual(p->Key(), theKey))
253 {
254 p->ChangeValue() = theItem;
255 return &p->ChangeValue();
256 }
257 p = (DataMapNode*)p->Next();
7fd59977 258 }
9df7f429 259 data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
260 Increment();
261 return &data[k]->ChangeValue();
7fd59977 262 }
263
9df7f429 264 //! IsBound
997e128f 265 Standard_Boolean IsBound(const TheKeyType& theKey) const
9df7f429 266 {
267 DataMapNode* p;
997e128f 268 return lookup(theKey, p);
9df7f429 269 }
270
271 //! UnBind removes Item Key pair from map
997e128f 272 Standard_Boolean UnBind(const TheKeyType& theKey)
7fd59977 273 {
274 if (IsEmpty())
275 return Standard_False;
276 DataMapNode** data = (DataMapNode**) myData1;
997e128f 277 Standard_Integer k = Hasher::HashCode(theKey,NbBuckets());
7fd59977 278 DataMapNode* p = data[k];
279 DataMapNode* q = NULL;
280 while (p)
281 {
997e128f 282 if (Hasher::IsEqual(p->Key(), theKey))
7fd59977 283 {
284 Decrement();
285 if (q)
286 q->Next() = p->Next();
287 else
288 data[k] = (DataMapNode*) p->Next();
289 p->~DataMapNode();
290 this->myAllocator->Free(p);
291 return Standard_True;
292 }
293 q = p;
294 p = (DataMapNode*) p->Next();
295 }
296 return Standard_False;
297 }
298
9df7f429 299 //! Seek returns pointer to Item by Key. Returns
300 //! NULL is Key was not bound.
301 const TheItemType* Seek(const TheKeyType& theKey) const
302 {
303 DataMapNode* p = 0;
304 if (!lookup(theKey, p))
305 return 0L;
306 return &p->Value();
307 }
308
309 //! Find returns the Item for Key. Raises if Key was not bound
7fd59977 310 const TheItemType& Find(const TheKeyType& theKey) const
311 {
9df7f429 312 DataMapNode* p = 0;
313 if (!lookup(theKey, p))
9775fa61 314 throw Standard_NoSuchObject("NCollection_DataMap::Find");
9df7f429 315 return p->Value();
7fd59977 316 }
317
9df7f429 318 //! Find Item for key with copying.
a174a3c5 319 //! @return true if key was found
320 Standard_Boolean Find (const TheKeyType& theKey,
321 TheItemType& theValue) const
322 {
9df7f429 323 DataMapNode* p = 0;
324 if (!lookup(theKey, p))
a174a3c5 325 return Standard_False;
a174a3c5 326
9df7f429 327 theValue = p->Value();
328 return Standard_True;
a174a3c5 329 }
330
7fd59977 331 //! operator ()
332 const TheItemType& operator() (const TheKeyType& theKey) const
333 { return Find(theKey); }
334
9df7f429 335 //! ChangeSeek returns modifiable pointer to Item by Key. Returns
336 //! NULL is Key was not bound.
337 TheItemType* ChangeSeek(const TheKeyType& theKey)
338 {
339 DataMapNode* p = 0;
340 if (!lookup(theKey, p))
341 return 0L;
342 return &p->ChangeValue();
343 }
344
345 //! ChangeFind returns mofifiable Item by Key. Raises if Key was not bound
7fd59977 346 TheItemType& ChangeFind (const TheKeyType& theKey)
347 {
9df7f429 348 DataMapNode* p = 0;
349 if (!lookup(theKey, p))
9775fa61 350 throw Standard_NoSuchObject("NCollection_DataMap::Find");
9df7f429 351 return p->ChangeValue();
7fd59977 352 }
353
354 //! operator ()
355 TheItemType& operator() (const TheKeyType& theKey)
356 { return ChangeFind(theKey); }
357
358 //! Clear data. If doReleaseMemory is false then the table of
359 //! buckets is not released and will be reused.
360 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
ddf2fe8e 361 { Destroy (DataMapNode::delNode, doReleaseMemory); }
7fd59977 362
363 //! Clear data and reset allocator
364 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
365 {
366 Clear();
367 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
368 NCollection_BaseAllocator::CommonBaseAllocator() );
369 }
370
371 //! Destructor
6928e351 372 virtual ~NCollection_DataMap (void)
7fd59977 373 { Clear(); }
374
375 //! Size
ddf2fe8e 376 Standard_Integer Size(void) const
7fd59977 377 { return Extent(); }
9df7f429 378
379
380 protected:
381 // ---------- PROTECTED METHODS ----------
382 //! Lookup for particular key in map. Returns true if key is found and
383 //! thepNode points to binded node. Returns false if key is not found,
384 //! thehNode value is this case is not usable.
385 Standard_Boolean lookup(const TheKeyType& theKey,DataMapNode*& thepNode) const
386 {
387 if (IsEmpty())
388 return Standard_False; // Not found
389 for (thepNode = (DataMapNode*)myData1[Hasher::HashCode(theKey, NbBuckets())];
390 thepNode; thepNode = (DataMapNode*)thepNode->Next())
391 {
392 if (Hasher::IsEqual(thepNode->Key(), theKey))
393 return Standard_True;
394 }
395 return Standard_False; // Not found
396 }
397
7fd59977 398};
399
7fd59977 400#endif
9991c9c2 401