1 // Created on: 2002-04-24
2 // Created by: Alexander KARTOMIN (akm)
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef NCollection_DataMap_HeaderFile
17 #define NCollection_DataMap_HeaderFile
19 #include <NCollection_BaseMap.hxx>
20 #include <NCollection_TListNode.hxx>
21 #include <NCollection_StlIterator.hxx>
22 #include <NCollection_DefaultHasher.hxx>
24 #include <Standard_TypeMismatch.hxx>
25 #include <Standard_NoSuchObject.hxx>
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.
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 :
37 * anItem = aMap(aKey);
38 * aMap(aKey) = anItem;
40 * This analogy has its limit. aMap(aKey) = anItem
41 * can be done only if aKey was previously bound to
45 template < class TheKeyType,
47 class Hasher = NCollection_DefaultHasher<TheKeyType> >
48 class NCollection_DataMap : public NCollection_BaseMap
51 //! STL-compliant typedef for key type
52 typedef TheKeyType key_type;
53 //! STL-compliant typedef for value type
54 typedef TheItemType value_type;
57 // **************** Adaptation of the TListNode to the DATAmap
58 class DataMapNode : public NCollection_TListNode<TheItemType>
61 //! Constructor with 'Next'
62 DataMapNode (const TheKeyType& theKey,
63 const TheItemType& theItem,
64 NCollection_ListNode* theNext) :
65 NCollection_TListNode<TheItemType> (theItem, theNext),
70 const TheKeyType& Key (void) const
73 //! Static deleter to be passed to BaseMap
74 static void delNode (NCollection_ListNode * theNode,
75 Handle(NCollection_BaseAllocator)& theAl)
77 ((DataMapNode *) theNode)->~DataMapNode();
86 // **************** Implementation of the Iterator interface.
87 class Iterator : public NCollection_BaseMap::Iterator
92 NCollection_BaseMap::Iterator() {}
94 Iterator (const NCollection_DataMap& theMap) :
95 NCollection_BaseMap::Iterator(theMap) {}
96 //! Query if the end of collection is reached by iterator
97 Standard_Boolean More(void) const
99 //! Make a step along the collection
103 const TheItemType& Value(void) const
105 Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Value");
106 return ((DataMapNode *) myNode)->Value();
108 //! Value change access
109 TheItemType& ChangeValue(void) const
111 Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::ChangeValue");
112 return ((DataMapNode *) myNode)->ChangeValue();
115 const TheKeyType& Key (void) const
117 Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Key");
118 return ((DataMapNode *) myNode)->Key();
122 //! Shorthand for a regular iterator type.
123 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
125 //! Shorthand for a constant iterator type.
126 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
128 //! Returns an iterator pointing to the first element in the map.
129 iterator begin() const { return Iterator (*this); }
131 //! Returns an iterator referring to the past-the-end element in the map.
132 iterator end() const { return Iterator(); }
134 //! Returns a const iterator pointing to the first element in the map.
135 const_iterator cbegin() const { return Iterator (*this); }
137 //! Returns a const iterator referring to the past-the-end element in the map.
138 const_iterator cend() const { return Iterator(); }
141 // ---------- PUBLIC METHODS ------------
143 //! Empty Constructor.
144 NCollection_DataMap() : NCollection_BaseMap (1, Standard_True, Handle(NCollection_BaseAllocator)()) {}
147 explicit NCollection_DataMap (const Standard_Integer theNbBuckets,
148 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
149 : NCollection_BaseMap (theNbBuckets, Standard_True, theAllocator) {}
152 NCollection_DataMap (const NCollection_DataMap& theOther)
153 : NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator)
154 { *this = theOther; }
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)
160 this->exchangeMapsData (theOther);
164 //! This method does not change the internal allocator.
165 NCollection_DataMap& Assign (const NCollection_DataMap& theOther)
167 if (this == &theOther)
171 Standard_Integer anExt = theOther.Extent();
175 Iterator anIter(theOther);
176 for (; anIter.More(); anIter.Next())
177 Bind (anIter.Key(), anIter.Value());
182 //! Assignment operator
183 NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
185 return Assign (theOther);
189 void ReSize (const Standard_Integer N)
191 NCollection_ListNode** newdata = NULL;
192 NCollection_ListNode** dummy = NULL;
193 Standard_Integer newBuck;
194 if (BeginResize (N, newBuck, newdata, dummy))
198 DataMapNode** olddata = (DataMapNode**) myData1;
200 Standard_Integer i,k;
201 for (i = 0; i <= NbBuckets(); i++)
208 k = Hasher::HashCode(p->Key(),newBuck);
209 q = (DataMapNode*) p->Next();
210 p->Next() = newdata[k];
217 EndResize (N, newBuck, newdata, dummy);
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
225 Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
229 DataMapNode** data = (DataMapNode**)myData1;
230 Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
231 DataMapNode* p = data[k];
234 if (Hasher::IsEqual(p->Key(), theKey))
236 p->ChangeValue() = theItem;
237 return Standard_False;
239 p = (DataMapNode *) p->Next();
241 data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
243 return Standard_True;
246 //! Bound binds Item to Key in map. Returns modifiable Item
247 TheItemType* Bound (const TheKeyType& theKey, const TheItemType& theItem)
251 DataMapNode** data = (DataMapNode**)myData1;
252 Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
253 DataMapNode* p = data[k];
256 if (Hasher::IsEqual(p->Key(), theKey))
258 p->ChangeValue() = theItem;
259 return &p->ChangeValue();
261 p = (DataMapNode*)p->Next();
263 data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
265 return &data[k]->ChangeValue();
269 Standard_Boolean IsBound(const TheKeyType& theKey) const
272 return lookup(theKey, p);
275 //! UnBind removes Item Key pair from map
276 Standard_Boolean UnBind(const TheKeyType& theKey)
279 return Standard_False;
280 DataMapNode** data = (DataMapNode**) myData1;
281 Standard_Integer k = Hasher::HashCode(theKey,NbBuckets());
282 DataMapNode* p = data[k];
283 DataMapNode* q = NULL;
286 if (Hasher::IsEqual(p->Key(), theKey))
290 q->Next() = p->Next();
292 data[k] = (DataMapNode*) p->Next();
294 this->myAllocator->Free(p);
295 return Standard_True;
298 p = (DataMapNode*) p->Next();
300 return Standard_False;
303 //! Seek returns pointer to Item by Key. Returns
304 //! NULL is Key was not bound.
305 const TheItemType* Seek(const TheKeyType& theKey) const
308 if (!lookup(theKey, p))
313 //! Find returns the Item for Key. Raises if Key was not bound
314 const TheItemType& Find(const TheKeyType& theKey) const
317 if (!lookup(theKey, p))
318 throw Standard_NoSuchObject("NCollection_DataMap::Find");
322 //! Find Item for key with copying.
323 //! @return true if key was found
324 Standard_Boolean Find (const TheKeyType& theKey,
325 TheItemType& theValue) const
328 if (!lookup(theKey, p))
329 return Standard_False;
331 theValue = p->Value();
332 return Standard_True;
336 const TheItemType& operator() (const TheKeyType& theKey) const
337 { return Find(theKey); }
339 //! ChangeSeek returns modifiable pointer to Item by Key. Returns
340 //! NULL is Key was not bound.
341 TheItemType* ChangeSeek(const TheKeyType& theKey)
344 if (!lookup(theKey, p))
346 return &p->ChangeValue();
349 //! ChangeFind returns mofifiable Item by Key. Raises if Key was not bound
350 TheItemType& ChangeFind (const TheKeyType& theKey)
353 if (!lookup(theKey, p))
354 throw Standard_NoSuchObject("NCollection_DataMap::Find");
355 return p->ChangeValue();
359 TheItemType& operator() (const TheKeyType& theKey)
360 { return ChangeFind(theKey); }
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)
365 { Destroy (DataMapNode::delNode, doReleaseMemory); }
367 //! Clear data and reset allocator
368 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
371 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
372 NCollection_BaseAllocator::CommonBaseAllocator() );
376 virtual ~NCollection_DataMap (void)
380 Standard_Integer Size(void) const
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
392 return Standard_False; // Not found
393 for (thepNode = (DataMapNode*)myData1[Hasher::HashCode(theKey, NbBuckets())];
394 thepNode; thepNode = (DataMapNode*)thepNode->Next())
396 if (Hasher::IsEqual(thepNode->Key(), theKey))
397 return Standard_True;
399 return Standard_False; // Not found