src/TCollection/TCollection_IndexedMap.gxx

   1 // Created on: 1993-01-08
   2 // Created by: Remi LEQUETTE
   3 // Copyright (c) 1993-1999 Matra Datavision
   4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   5 //
   6 // This file is part of Open CASCADE Technology software library.
   7 //
   8 // This library is free software; you can redistribute it and/or modify it under
   9 // the terms of the GNU Lesser General Public License version 2.1 as published
  10 // by the Free Software Foundation, with special exception defined in the file
  11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  12 // distribution for complete text of the license and disclaimer of any warranty.
  13 //
  14 // Alternatively, this file may be used under the terms of Open CASCADE
  15 // commercial license or contractual agreement.
  16
  17 #include <Standard_DomainError.hxx>
  18 #include <Standard_MultiplyDefined.hxx>
  19 #include <Standard_NoSuchObject.hxx>
  20 #include <Standard_OutOfRange.hxx>
  21 #include <TCollection_BasicMapIterator.hxx>
  22
  23
  24 //=======================================================================
  25 //function : TCollection_IndexedMap
  26 //purpose  :
  27 //=======================================================================
  28
  29 TCollection_IndexedMap::TCollection_IndexedMap
  30   (const Standard_Integer NbBuckets):
  31   TCollection_BasicMap(NbBuckets,Standard_False)
  32 {
  33 }
  34
  35 //=======================================================================
  36 //function : TCollection_IndexedMap
  37 //purpose  :
  38 //=======================================================================
  39
  40 TCollection_IndexedMap::TCollection_IndexedMap
  41   (const TCollection_IndexedMap& Other) :
  42   TCollection_BasicMap(Other.NbBuckets(),Standard_False)
  43 {
  44   if  (!Other.IsEmpty()) {
  45     ReSize(Other.Extent());
  46     for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
  47       Add(Other(i));
  48     }
  49   }
  50 }
  51
  52 //=======================================================================
  53 //function : Assign
  54 //purpose  :
  55 //=======================================================================
  56
  57 TCollection_IndexedMap& TCollection_IndexedMap::Assign
  58   (const TCollection_IndexedMap& Other)
  59 {
  60   // very simple implementation
  61   // not optimal (recompute the hashcode values)
  62
  63   if (this == &Other) return *this;
  64   Clear();
  65 //  ReSize(Other.NbBuckets());
  66   if  (!Other.IsEmpty()) {
  67     ReSize(Other.Extent());
  68     for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
  69       Add(Other(i));
  70     }
  71   }
  72   return *this;
  73 }
  74
  75 //=======================================================================
  76 //function : ReSize
  77 //purpose  :
  78 //=======================================================================
  79
  80 void TCollection_IndexedMap::ReSize(const Standard_Integer N)
  81 {
  82   Standard_Integer newBuck;
  83   Standard_Address newData1, newData2;
  84   if (BeginResize(N,newBuck,newData1,newData2)) {
  85     if (myData1) {
  86       TCollection_IndexedMapNode** newdata1 = (TCollection_IndexedMapNode**)newData1;
  87       TCollection_IndexedMapNode** newdata2 = (TCollection_IndexedMapNode**)newData2;
  88       TCollection_IndexedMapNode** olddata1 = (TCollection_IndexedMapNode**) myData1;
  89       TCollection_IndexedMapNode *p, *q;
  90       Standard_Integer i,k1,k2;
  91       for (i = 0; i <= NbBuckets(); i++) {
  92         if (olddata1[i]) {
  93           p = olddata1[i];
  94           while (p) {
  95             k1 = Hasher::HashCode(p->Key1(),newBuck);
  96             q = (TCollection_IndexedMapNode*) p->Next();
  97             p->Next() = newdata1[k1];
  98             newdata1[k1] = p;
  99             if (p->Key2() > 0) {
 100               k2 = ::HashCode(p->Key2(),newBuck);
 101               p->Next2() = newdata2[k2];
 102               newdata2[k2] = p;
 103             }
 104             p = q;
 105           }
 106         }
 107       }
 108     }
 109     EndResize(N,newBuck,newData1,newData2);
 110   }
 111 }
 112
 113 //=======================================================================
 114 //function : Clear
 115 //purpose  :
 116 //=======================================================================
 117
 118 void TCollection_IndexedMap::Clear()
 119 {
 120   if (!IsEmpty()) {
 121     Standard_Integer i;
 122     TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**) myData1;
 123 //    TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**) myData2;
 124     TCollection_IndexedMapNode *p,*q;
 125     for (i = 0; i <= NbBuckets(); i++) {
 126       p = data1[i];
 127       while (p) {
 128         q = (TCollection_IndexedMapNode*) p->Next();
 129         delete p;
 130         p = q;
 131       }
 132     }
 133   }
 134   TCollection_BasicMap::Destroy();
 135 }
 136
 137 //=======================================================================
 138 //function : Add
 139 //purpose  :
 140 //=======================================================================
 141
 142 Standard_Integer TCollection_IndexedMap::Add(const TheKey& K1)
 143 {
 144   if (Resizable())  ReSize(Extent());
 145   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
 146   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 147   TCollection_IndexedMapNode* p;
 148   p = data1[k1];
 149   while (p) {
 150     if (Hasher::IsEqual(p->Key1(),K1))
 151       return p->Key2();
 152     p = (TCollection_IndexedMapNode*) p->Next();
 153   }
 154   Increment();
 155   TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
 156   Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
 157   p = new TCollection_IndexedMapNode(K1,Extent(),data1[k1],data2[k2]);
 158   data1[k1] = p;
 159   data2[k2] = p;
 160   return Extent();
 161 }
 162
 163 //=======================================================================
 164 //function : Substitute
 165 //purpose  :
 166 //=======================================================================
 167
 168 void TCollection_IndexedMap::Substitute(const Standard_Integer I,
 169                                         const TheKey& K1)
 170 {
 171   Standard_OutOfRange_Raise_if(I < 1 || I > Extent(), "IndexedMap::Substitute : "
 172                                                       "Index is out of range");
 173   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
 174   TCollection_IndexedMapNode* p;
 175
 176   // check if K1 is not already in the map
 177   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 178   p = data1[k1];
 179   while (p) {
 180     if (Hasher::IsEqual(p->Key1(),K1)) {
 181       if (p->Key2() != I)
 182         Standard_DomainError::Raise("IndexedMap::Substitute : "
 183                                     "Attempt to substitute existing key");
 184       p->Key1() = K1;
 185       return;
 186     }
 187     p = (TCollection_IndexedMapNode*) p->Next();
 188   }
 189
 190   // Find the node for the index I
 191   TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
 192   Standard_Integer k2 = ::HashCode(I,NbBuckets());
 193   p = data2[k2];
 194   while (p) {
 195     if (p->Key2() == I)
 196       break;
 197     p = (TCollection_IndexedMapNode*) p->Next2();
 198   }
 199
 200   // remove the old key
 201   Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
 202   TCollection_IndexedMapNode* q = data1[k];
 203   if (q == p) data1[k] = (TCollection_IndexedMapNode*) p->Next();
 204   else {
 205     while(q->Next() != p) q = (TCollection_IndexedMapNode*) q->Next();
 206     q->Next() = p->Next();
 207   }
 208
 209   // update the node
 210   p->Key1() = K1;
 211   p->Next() = data1[k1];
 212   data1[k1] = p;
 213 }
 214
 215 //=======================================================================
 216 //function : RemoveLast
 217 //purpose  :
 218 //=======================================================================
 219
 220 void TCollection_IndexedMap::RemoveLast()
 221 {
 222   Standard_OutOfRange_Raise_if(Extent() == 0,
 223                                "IndexedMap::RemoveLast");
 224   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
 225   TCollection_IndexedMapNode* p;
 226   TCollection_IndexedMapNode* q;
 227
 228   // Find the node for the last index and remove it
 229   TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
 230   Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
 231   p = data2[k2];
 232   q = NULL;
 233   while (p) {
 234     if (p->Key2() == Extent())
 235       break;
 236     q = p;
 237     p = (TCollection_IndexedMapNode*) p->Next2();
 238   }
 239   if (q == NULL)
 240     data2[k2] = (TCollection_IndexedMapNode*)p->Next2();
 241   else
 242     q->Next2() = p->Next2();
 243
 244   // remove the key
 245   Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
 246   q = data1[k];
 247   if (q == p) data1[k] = (TCollection_IndexedMapNode*) p->Next();
 248   else {
 249     while(q->Next() != p) q = (TCollection_IndexedMapNode*) q->Next();
 250     q->Next() = p->Next();
 251   }
 252
 253   Decrement();
 254   delete p;
 255 }
 256
 257 //=======================================================================
 258 //function : Contains
 259 //purpose  :
 260 //=======================================================================
 261
 262 Standard_Boolean TCollection_IndexedMap::Contains(const TheKey& K1) const
 263 {
 264   if (IsEmpty()) return Standard_False;
 265   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
 266   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 267   TCollection_IndexedMapNode *p1;
 268   p1 = data1[k1];
 269   while (p1) {
 270     if (Hasher::IsEqual(p1->Key1(),K1)) return Standard_True;
 271     p1 = (TCollection_IndexedMapNode*) p1->Next();
 272   }
 273   return Standard_False;
 274 }
 275
 276 //=======================================================================
 277 //function : FindKey
 278 //purpose  :
 279 //=======================================================================
 280
 281 const TheKey& TCollection_IndexedMap::FindKey(const Standard_Integer K2) const
 282 {
 283   Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedMap");
 284   TCollection_IndexedMapNode** data2 = (TCollection_IndexedMapNode**)myData2;
 285   Standard_Integer k2 = ::HashCode(K2,NbBuckets());
 286   TCollection_IndexedMapNode *p2;
 287   p2 = data2[k2];
 288   while (p2) {
 289     if (p2->Key2() == K2) return p2->Key1();
 290     p2 = (TCollection_IndexedMapNode*)p2->Next2();
 291   }
 292   Standard_OutOfRange::Raise("IndexedMap : missing index !!!");
 293   return p2->Key1();
 294 }
 295
 296 //=======================================================================
 297 //function : FindIndex
 298 //purpose  :
 299 //=======================================================================
 300
 301 Standard_Integer TCollection_IndexedMap::FindIndex(const TheKey& K1) const
 302 {
 303   if (IsEmpty()) return 0;
 304   TCollection_IndexedMapNode** data1 = (TCollection_IndexedMapNode**)myData1;
 305   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 306   TCollection_IndexedMapNode *p1;
 307   p1 = data1[k1];
 308   while (p1) {
 309     if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Key2();
 310     p1 = (TCollection_IndexedMapNode*) p1->Next();
 311   }
 312   return 0;
 313 }