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
50 // **************** Adaptation of the TListNode to the DATAmap
52 class DataMapNode : public NCollection_TListNode<TheItemType>
55 //! Constructor with 'Next'
56 DataMapNode (const TheKeyType& theKey,
57 const TheItemType& theItem,
58 NCollection_ListNode* theNext) :
59 NCollection_TListNode<TheItemType> (theItem, theNext),
64 const TheKeyType& Key (void) const
67 //! Static deleter to be passed to BaseMap
68 static void delNode (NCollection_ListNode * theNode,
69 Handle(NCollection_BaseAllocator)& theAl)
71 ((DataMapNode *) theNode)->~DataMapNode();
80 // **************** Implementation of the Iterator interface.
81 class Iterator : public NCollection_BaseMap::Iterator
86 NCollection_BaseMap::Iterator() {}
88 Iterator (const NCollection_DataMap& theMap) :
89 NCollection_BaseMap::Iterator(theMap) {}
90 //! Query if the end of collection is reached by iterator
91 Standard_Boolean More(void) const
93 //! Make a step along the collection
97 const TheItemType& Value(void) const
99 Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Value");
100 return ((DataMapNode *) myNode)->Value();
102 //! Value change access
103 TheItemType& ChangeValue(void) const
105 Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::ChangeValue");
106 return ((DataMapNode *) myNode)->ChangeValue();
109 const TheKeyType& Key (void) const
111 Standard_NoSuchObject_Raise_if(!More(), "NCollection_DataMap::Iterator::Key");
112 return ((DataMapNode *) myNode)->Key();
116 //! Shorthand for a regular iterator type.
117 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, false> iterator;
119 //! Shorthand for a constant iterator type.
120 typedef NCollection_StlIterator<std::forward_iterator_tag, Iterator, TheItemType, true> const_iterator;
122 //! Returns an iterator pointing to the first element in the map.
123 iterator begin() const { return Iterator (*this); }
125 //! Returns an iterator referring to the past-the-end element in the map.
126 iterator end() const { return Iterator(); }
128 //! Returns a const iterator pointing to the first element in the map.
129 const_iterator cbegin() const { return Iterator (*this); }
131 //! Returns a const iterator referring to the past-the-end element in the map.
132 const_iterator cend() const { return Iterator(); }
135 // ---------- PUBLIC METHODS ------------
138 NCollection_DataMap (const Standard_Integer NbBuckets=1,
139 const Handle(NCollection_BaseAllocator)& theAllocator = 0L)
140 : NCollection_BaseMap (NbBuckets, Standard_True, theAllocator) {}
143 NCollection_DataMap (const NCollection_DataMap& theOther)
144 : NCollection_BaseMap (theOther.NbBuckets(), Standard_True, theOther.myAllocator)
145 { *this = theOther; }
147 //! Exchange the content of two maps without re-allocations.
148 //! Notice that allocators will be swapped as well!
149 void Exchange (NCollection_DataMap& theOther)
151 this->exchangeMapsData (theOther);
155 NCollection_DataMap& Assign (const NCollection_DataMap& theOther)
157 if (this == &theOther)
160 Clear(theOther.myAllocator);
161 ReSize (theOther.Extent()-1);
162 Iterator anIter(theOther);
163 for (; anIter.More(); anIter.Next())
164 Bind (anIter.Key(), anIter.Value());
168 //! Assignment operator
169 NCollection_DataMap& operator= (const NCollection_DataMap& theOther)
171 return Assign (theOther);
175 void ReSize (const Standard_Integer N)
177 NCollection_ListNode** newdata = NULL;
178 NCollection_ListNode** dummy = NULL;
179 Standard_Integer newBuck;
180 if (BeginResize (N, newBuck, newdata, dummy))
184 DataMapNode** olddata = (DataMapNode**) myData1;
186 Standard_Integer i,k;
187 for (i = 0; i <= NbBuckets(); i++)
194 k = Hasher::HashCode(p->Key(),newBuck);
195 q = (DataMapNode*) p->Next();
196 p->Next() = newdata[k];
203 EndResize (N, newBuck, newdata, dummy);
208 Standard_Boolean Bind (const TheKeyType& theKey, const TheItemType& theItem)
212 DataMapNode** data = (DataMapNode**)myData1;
213 Standard_Integer k = Hasher::HashCode (theKey, NbBuckets());
214 DataMapNode* p = data[k];
217 if (Hasher::IsEqual(p->Key(), theKey))
219 p->ChangeValue() = theItem;
220 return Standard_False;
222 p = (DataMapNode *) p->Next();
224 data[k] = new (this->myAllocator) DataMapNode (theKey, theItem, data[k]);
226 return Standard_True;
230 Standard_Boolean IsBound(const TheKeyType& K) const
233 return Standard_False;
234 DataMapNode** data = (DataMapNode**) myData1;
235 DataMapNode* p = data[Hasher::HashCode(K,NbBuckets())];
238 if (Hasher::IsEqual(p->Key(),K))
239 return Standard_True;
240 p = (DataMapNode *) p->Next();
242 return Standard_False;
246 Standard_Boolean UnBind(const TheKeyType& K)
249 return Standard_False;
250 DataMapNode** data = (DataMapNode**) myData1;
251 Standard_Integer k = Hasher::HashCode(K,NbBuckets());
252 DataMapNode* p = data[k];
253 DataMapNode* q = NULL;
256 if (Hasher::IsEqual(p->Key(),K))
260 q->Next() = p->Next();
262 data[k] = (DataMapNode*) p->Next();
264 this->myAllocator->Free(p);
265 return Standard_True;
268 p = (DataMapNode*) p->Next();
270 return Standard_False;
274 const TheItemType& Find(const TheKeyType& theKey) const
276 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DataMap::Find");
277 DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
280 if (Hasher::IsEqual(p->Key(),theKey))
282 p = (DataMapNode*) p->Next();
284 Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
285 return p->Value(); // This for compiler
288 //! Find value for key with copying.
289 //! @return true if key was found
290 Standard_Boolean Find (const TheKeyType& theKey,
291 TheItemType& theValue) const
295 return Standard_False;
298 for (DataMapNode* aNodeIter = (DataMapNode* )myData1[Hasher::HashCode (theKey, NbBuckets())];
300 aNodeIter = (DataMapNode* )aNodeIter->Next())
302 if (Hasher::IsEqual (aNodeIter->Key(), theKey))
304 theValue = aNodeIter->Value();
305 return Standard_True;
308 return Standard_False;
312 const TheItemType& operator() (const TheKeyType& theKey) const
313 { return Find(theKey); }
316 TheItemType& ChangeFind (const TheKeyType& theKey)
318 Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_DataMap::Find");
319 DataMapNode* p = (DataMapNode*) myData1[Hasher::HashCode(theKey,NbBuckets())];
322 if (Hasher::IsEqual(p->Key(),theKey))
323 return p->ChangeValue();
324 p = (DataMapNode*) p->Next();
326 Standard_NoSuchObject::Raise("NCollection_DataMap::Find");
327 return p->ChangeValue(); // This for compiler
331 TheItemType& operator() (const TheKeyType& theKey)
332 { return ChangeFind(theKey); }
334 //! Clear data. If doReleaseMemory is false then the table of
335 //! buckets is not released and will be reused.
336 void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
337 { Destroy (DataMapNode::delNode, doReleaseMemory); }
339 //! Clear data and reset allocator
340 void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
343 this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
344 NCollection_BaseAllocator::CommonBaseAllocator() );
348 ~NCollection_DataMap (void)
352 Standard_Integer Size(void) const