SALOME - SMESH
SMESH_IndexedMap.hxx
Go to the documentation of this file.
1 // File: NCollection_IndexedMap.hxx
2 // Created: Thu Apr 24 15:02:53 2002
3 // Author: Alexander KARTOMIN (akm)
4 // <akm@opencascade.com>
5 
6 #ifndef SMESH_IndexedMap_HeaderFile
7 #define SMESH_IndexedMap_HeaderFile
8 
9 #include <NCollection_BaseCollection.hxx>
10 #include <NCollection_BaseMap.hxx>
11 #include <NCollection_TListNode.hxx>
12 #include <Standard_NoSuchObject.hxx>
13 #include <Standard_ImmutableObject.hxx>
14 
15 #if !defined No_Exception && !defined No_Standard_OutOfRange
16 #include <Standard_OutOfRange.hxx>
17 #endif
18 
19 #ifdef WNT
20 // Disable the warning "operator new unmatched by delete"
21 #pragma warning (push)
22 #pragma warning (disable:4291)
23 #endif
24 
35 template <class TheKeyType> class SMESH_IndexedMap
36  : public NCollection_BaseCollection<TheKeyType>,
37  public NCollection_BaseMap
38 {
39  // **************** Adaptation of the TListNode to the INDEXEDmap
40  private:
41  class IndexedMapNode : public NCollection_TListNode<TheKeyType>
42  {
43  public:
45  IndexedMapNode (const TheKeyType& theKey1,
46  const Standard_Integer theKey2,
47  NCollection_ListNode* theNext1,
48  NCollection_ListNode* theNext2) :
49  NCollection_TListNode<TheKeyType> (theKey1, theNext1)
50  {
51  myKey2 = theKey2;
52  myNext2 = (IndexedMapNode *) theNext2;
53  }
55  TheKeyType& Key1 (void)
56  { return this->ChangeValue(); }
58  const Standard_Integer& Key2 (void)
59  { return myKey2; }
62  { return myNext2; }
63 
65  static void delNode (NCollection_ListNode * theNode,
66  Handle(NCollection_BaseAllocator)& theAl)
67  {
68  ((IndexedMapNode *) theNode)->~IndexedMapNode();
69  theAl->Free(theNode);
70  }
71 
72  private:
73  Standard_Integer myKey2;
75  };
76 
77  public:
78  // **************** Implementation of the Iterator interface.
79  class Iterator
80  : public NCollection_BaseCollection<TheKeyType>::Iterator
81  {
82  public:
84  Iterator (void) :
85  myMap(NULL),
86  myIndex(0) {}
88  Iterator (const SMESH_IndexedMap& theMap) :
89  myMap(const_cast<SMESH_IndexedMap<TheKeyType>*>(&theMap) /*(SMESH_IndexedMap *) &theMap*/),
90  myIndex(1) {}
92  virtual Standard_Boolean More(void) const
93  { return (myIndex <= myMap->Extent()); }
95  virtual void Next(void)
96  { myIndex++; }
98  virtual const TheKeyType& Value(void) const
99  {
100 #if !defined No_Exception && !defined No_Standard_NoSuchObject
101  if (!More())
102  Standard_NoSuchObject::Raise("SMESH_IndexedMap::Iterator::Value");
103 #endif
104  return myMap->FindKey(myIndex);
105  }
107  virtual TheKeyType& ChangeValue(void) const
108  {
109  Standard_ImmutableObject::Raise ("impossible to ChangeValue");
110  return * (TheKeyType *) NULL; // This for compiler
111  }
112 
114  void* operator new(size_t theSize,
115  const Handle(NCollection_BaseAllocator)& theAllocator)
116  { return theAllocator->Allocate(theSize); }
117 
118  private:
119  SMESH_IndexedMap * myMap; // Pointer to the map being iterated
120  Standard_Integer myIndex; // Current index
121  };
122 
123  public:
124  // ---------- PUBLIC METHODS ------------
125 
127  SMESH_IndexedMap (const Standard_Integer NbBuckets=1,
128  const Handle(NCollection_BaseAllocator)& theAllocator=0L) :
129  NCollection_BaseCollection<TheKeyType>(theAllocator),
130  NCollection_BaseMap (NbBuckets, Standard_False) {}
131 
133  SMESH_IndexedMap (const SMESH_IndexedMap& theOther) :
134  NCollection_BaseCollection<TheKeyType>(theOther.myAllocator),
135  NCollection_BaseMap (theOther.NbBuckets(), Standard_False)
136  { *this = theOther; }
137 
139  virtual void Assign (const NCollection_BaseCollection<TheKeyType>& theOther)
140  {
141  if (this == &theOther)
142  return;
143  Clear();
144  ReSize (theOther.Size());
146  theOther.CreateIterator();
147  for (; anIter.More(); anIter.Next())
148  Add(anIter.Value());
149  }
150 
153  {
154  if (this == &theOther)
155  return *this;
156 
157  Clear();
158  ReSize (theOther.NbBuckets());
159  Standard_Integer i, iLength=theOther.Extent();
160  for (i=1; i<=iLength; i++)
161  {
162  TheKeyType aKey1 = theOther(i);
163  Standard_Integer iK1 = HashCode (aKey1, NbBuckets());
164  Standard_Integer iK2 = HashCode (i, NbBuckets());
165  IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i,
166  myData1[iK1],
167  myData2[iK2]);
168  myData1[iK1] = pNode;
169  myData2[iK2] = pNode;
170  Increment();
171  }
172  return *this;
173  }
174 
176  void ReSize (const Standard_Integer N)
177  {
178  IndexedMapNode** ppNewData1 = NULL;
179  IndexedMapNode** ppNewData2 = NULL;
180  Standard_Integer newBuck;
181  if (BeginResize (N, newBuck,
182  (NCollection_ListNode**&)ppNewData1,
183  (NCollection_ListNode**&)ppNewData2,
184  this->myAllocator))
185  {
186  if (myData1)
187  {
188  IndexedMapNode *p, *q;
189  Standard_Integer i, iK1, iK2;
190  for (i = 0; i <= NbBuckets(); i++)
191  {
192  if (myData1[i])
193  {
194  p = (IndexedMapNode *) myData1[i];
195  while (p)
196  {
197  iK1 = HashCode (p->Key1(), newBuck);
198  q = (IndexedMapNode*) p->Next();
199  p->Next() = ppNewData1[iK1];
200  ppNewData1[iK1] = p;
201  if (p->Key2() > 0)
202  {
203  iK2 = HashCode (p->Key2(), newBuck);
204  p->Next2() = ppNewData2[iK2];
205  ppNewData2[iK2] = p;
206  }
207  p = q;
208  }
209  }
210  }
211  }
212  EndResize(N,newBuck,
213  (NCollection_ListNode**&)ppNewData1,
214  (NCollection_ListNode**&)ppNewData2,
215  this->myAllocator);
216  }
217  }
218 
220  Standard_Integer Add (const TheKeyType& theKey1)
221  {
222  if (Resizable())
223  ReSize(Extent());
224  Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
225  IndexedMapNode * pNode;
226  pNode = (IndexedMapNode *) myData1[iK1];
227  while (pNode)
228  {
229  if (IsEqual (pNode->Key1(), theKey1))
230  return pNode->Key2();
231  pNode = (IndexedMapNode *) pNode->Next();
232  }
233  Increment();
234  Standard_Integer iK2 = HashCode(Extent(),NbBuckets());
235  pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(),
236  myData1[iK1], myData2[iK2]);
237  myData1[iK1] = pNode;
238  myData2[iK2] = pNode;
239  return Extent();
240  }
241 
243  Standard_Boolean Contains (const TheKeyType& theKey1) const
244  {
245  if (IsEmpty())
246  return Standard_False;
247  Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
248  IndexedMapNode * pNode1;
249  pNode1 = (IndexedMapNode *) myData1[iK1];
250  while (pNode1)
251  {
252  if (IsEqual(pNode1->Key1(), theKey1))
253  return Standard_True;
254  pNode1 = (IndexedMapNode *) pNode1->Next();
255  }
256  return Standard_False;
257  }
258 
260  void Substitute (const Standard_Integer theIndex,
261  const TheKeyType& theKey1)
262  {
263 #if !defined No_Exception && !defined No_Standard_OutOfRange
264  if (theIndex < 1 || theIndex > Extent())
265  Standard_OutOfRange::Raise ("SMESH_IndexedMap::Substitute");
266 #endif
267  IndexedMapNode * p;
268  // check if theKey1 is not already in the map
269  Standard_Integer iK1 = HashCode (theKey1, NbBuckets());
270  p = (IndexedMapNode *) myData1[iK1];
271  while (p)
272  {
273  if (IsEqual (p->Key1(), theKey1))
274  Standard_DomainError::Raise("SMESH_IndexedMap::Substitute");
275  p = (IndexedMapNode *) p->Next();
276  }
277 
278  // Find the node for the index I
279  Standard_Integer iK2 = HashCode (theIndex, NbBuckets());
280  p = (IndexedMapNode *) myData2[iK2];
281  while (p)
282  {
283  if (p->Key2() == theIndex)
284  break;
285  p = (IndexedMapNode*) p->Next2();
286  }
287 
288  // remove the old key
289  Standard_Integer iK = HashCode (p->Key1(), NbBuckets());
290  IndexedMapNode * q = (IndexedMapNode *) myData1[iK];
291  if (q == p)
292  myData1[iK] = (IndexedMapNode *) p->Next();
293  else
294  {
295  while (q->Next() != p)
296  q = (IndexedMapNode *) q->Next();
297  q->Next() = p->Next();
298  }
299 
300  // update the node
301  p->Key1() = theKey1;
302  p->Next() = myData1[iK1];
303  myData1[iK1] = p;
304  }
305 
307  void RemoveLast (void)
308  {
309 #if !defined No_Exception && !defined No_Standard_OutOfRange
310  if (Extent() == 0)
311  Standard_OutOfRange::Raise ("SMESH_IndexedMap::RemoveLast");
312 #endif
313  IndexedMapNode * p, * q;
314  // Find the node for the last index and remove it
315  Standard_Integer iK2 = HashCode (Extent(), NbBuckets());
316  p = (IndexedMapNode *) myData2[iK2];
317  q = NULL;
318  while (p)
319  {
320  if (p->Key2() == Extent())
321  break;
322  q = p;
323  p = (IndexedMapNode*) p->Next2();
324  }
325  if (q == NULL)
326  myData2[iK2] = (IndexedMapNode *) p->Next2();
327  else
328  q->Next2() = p->Next2();
329 
330  // remove the key
331  Standard_Integer iK1 = HashCode (p->Key1(), NbBuckets());
332  q = (IndexedMapNode *) myData1[iK1];
333  if (q == p)
334  myData1[iK1] = (IndexedMapNode *) p->Next();
335  else
336  {
337  while (q->Next() != p)
338  q = (IndexedMapNode *) q->Next();
339  q->Next() = p->Next();
340  }
341  p->~IndexedMapNode();
342  this->myAllocator->Free(p);
343  Decrement();
344  }
345 
347  const TheKeyType& FindKey (const Standard_Integer theKey2) const
348  {
349 #if !defined No_Exception && !defined No_Standard_OutOfRange
350  if (theKey2 < 1 || theKey2 > Extent())
351  Standard_OutOfRange::Raise ("SMESH_IndexedMap::FindKey");
352 #endif
353  IndexedMapNode * pNode2 =
354  (IndexedMapNode *) myData2[HashCode(theKey2,NbBuckets())];
355  while (pNode2)
356  {
357  if (pNode2->Key2() == theKey2)
358  return pNode2->Key1();
359  pNode2 = (IndexedMapNode*) pNode2->Next2();
360  }
361  Standard_NoSuchObject::Raise("SMESH_IndexedMap::FindKey");
362  return pNode2->Key1(); // This for compiler
363  }
364 
366  const TheKeyType& operator() (const Standard_Integer theKey2) const
367  { return FindKey (theKey2); }
368 
370  Standard_Integer FindIndex(const TheKeyType& theKey1) const
371  {
372  if (IsEmpty()) return 0;
373  IndexedMapNode * pNode1 =
374  (IndexedMapNode *) myData1[HashCode(theKey1,NbBuckets())];
375  while (pNode1)
376  {
377  if (IsEqual (pNode1->Key1(), theKey1))
378  return pNode1->Key2();
379  pNode1 = (IndexedMapNode*) pNode1->Next();
380  }
381  return 0;
382  }
383 
386  void Clear(const Standard_Boolean doReleaseMemory = Standard_True)
387  { Destroy (IndexedMapNode::delNode, this->myAllocator, doReleaseMemory); }
388 
390  void Clear (const Handle(NCollection_BaseAllocator)& theAllocator)
391  {
392  Clear();
393  this->myAllocator = ( ! theAllocator.IsNull() ? theAllocator :
394  NCollection_BaseAllocator::CommonBaseAllocator() );
395  }
396 
399  { Clear(); }
400 
402  virtual Standard_Integer Size(void) const
403  { return Extent(); }
404 
405  private:
406  // ----------- PRIVATE METHODS -----------
407 
410  CreateIterator(void) const
411  { return *(new (this->IterAllocator()) Iterator(*this)); }
412 
413 };
414 
415 #ifdef WNT
416 #pragma warning (pop)
417 #endif
418 
419 #endif
Standard_Integer HashCode(SMDS_MeshElementPtr theElem, const Standard_Integer theUpper)
virtual void Next(void)
Make a step along the collection.
virtual Standard_Integer Size(void) const
Size.
const TheKeyType & FindKey(const Standard_Integer theKey2) const
FindKey.
Purpose: An indexed map is used to store keys and to bind an index to them.
Iterator(const SMESH_IndexedMap &theMap)
Constructor.
void ReSize(const Standard_Integer N)
ReSize.
TheKeyType & Key1(void)
Key1.
virtual void Assign(const NCollection_BaseCollection< TheKeyType > &theOther)
Assign another collection.
void Substitute(const Standard_Integer theIndex, const TheKeyType &theKey1)
Substitute.
const Standard_Integer & Key2(void)
Key2.
Iterator(void)
Empty constructor.
void Clear(const Handle(NCollection_BaseAllocator)&theAllocator)
Clear data and reset allocator.
virtual const TheKeyType & Value(void) const
Value access.
void RemoveLast(void)
RemoveLast.
IndexedMapNode(const TheKeyType &theKey1, const Standard_Integer theKey2, NCollection_ListNode *theNext1, NCollection_ListNode *theNext2)
Constructor with &#39;Next&#39;.
void Clear(const Standard_Boolean doReleaseMemory=Standard_True)
Clear data. If doReleaseMemory is false then the table of buckets is not released and will be reused...
const TheKeyType & operator()(const Standard_Integer theKey2) const
operator ()
Standard_Boolean IsEqual(SMDS_MeshElementPtr theOne, SMDS_MeshElementPtr theTwo)
SMESH_IndexedMap(const SMESH_IndexedMap &theOther)
Copy constructor.
SMESH_IndexedMap & operator=(const SMESH_IndexedMap &theOther)
= another map
virtual TYPENAME NCollection_BaseCollection< TheKeyType >::Iterator & CreateIterator(void) const
Creates Iterator for use on BaseCollection.
IndexedMapNode *& Next2(void)
Next2.
static void delNode(NCollection_ListNode *theNode, Handle(NCollection_BaseAllocator)&theAl)
Static deleter to be passed to BaseList.
SMESH_IndexedMap(const Standard_Integer NbBuckets=1, const Handle(NCollection_BaseAllocator)&theAllocator=0L)
Constructor.
Standard_Integer FindIndex(const TheKeyType &theKey1) const
FindIndex.
virtual Standard_Boolean More(void) const
Query if the end of collection is reached by iterator.
unsigned long int N
Definition: Rn.h:66
virtual TheKeyType & ChangeValue(void) const
Value change access denied - use Substitute.
Standard_Boolean Contains(const TheKeyType &theKey1) const
Contains.
Standard_Integer Add(const TheKeyType &theKey1)
Add.
~SMESH_IndexedMap(void)
Destructor.