src/TCollection/TCollection_IndexedDataMap.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 //function : TCollection_IndexedDataMap
  25 //purpose  :
  26 //=======================================================================
  27
  28 TCollection_IndexedDataMap::TCollection_IndexedDataMap
  29   (const Standard_Integer NbBuckets):
  30   TCollection_BasicMap(NbBuckets,Standard_False)
  31 {
  32 }
  33
  34 //=======================================================================
  35 //function : TCollection_IndexedDataMap
  36 //purpose  :
  37 //=======================================================================
  38
  39 TCollection_IndexedDataMap::TCollection_IndexedDataMap
  40   (const TCollection_IndexedDataMap& Other) :
  41   TCollection_BasicMap(Other.NbBuckets(),Standard_False)
  42 {
  43   if (Other.Extent() != 0)
  44     Standard_DomainError::Raise("TCollection:Copy of non empty IndexedDataMap");
  45 }
  46
  47 //=======================================================================
  48 //function : Assign
  49 //purpose  :
  50 //=======================================================================
  51
  52 TCollection_IndexedDataMap& TCollection_IndexedDataMap::Assign
  53   (const TCollection_IndexedDataMap& Other)
  54 {
  55   // very simple implementation
  56   // not optimal (recompute the hashcode values)
  57
  58   if (this == &Other) return *this;
  59   Clear();
  60 //  ReSize(Other.NbBuckets());
  61   if  (!Other.IsEmpty()) {
  62     ReSize(Other.Extent());
  63     for (Standard_Integer i = 1; i <= Other.Extent(); i++) {
  64       Add(Other.FindKey(i),Other(i));
  65     }
  66   }
  67   return *this;
  68 }
  69
  70
  71
  72 //=======================================================================
  73 //function : ReSize
  74 //purpose  :
  75 //=======================================================================
  76
  77 void TCollection_IndexedDataMap::ReSize(const Standard_Integer N)
  78 {
  79   Standard_Integer newBuck;
  80   Standard_Address newData1=NULL, newData2=NULL;
  81   if (BeginResize(N,newBuck,newData1,newData2)) {
  82     if (myData1) {
  83       TCollection_IndexedDataMapNode** newdata1 = (TCollection_IndexedDataMapNode**)newData1;
  84       TCollection_IndexedDataMapNode** newdata2 = (TCollection_IndexedDataMapNode**)newData2;
  85       TCollection_IndexedDataMapNode** olddata1 = (TCollection_IndexedDataMapNode**) myData1;
  86       TCollection_IndexedDataMapNode *p, *q;
  87       Standard_Integer i,k1,k2;
  88       for (i = 0; i <= NbBuckets(); i++) {
  89         if (olddata1[i]) {
  90           p = olddata1[i];
  91           while (p) {
  92             k1 = Hasher::HashCode(p->Key1(),newBuck);
  93             k2 = ::HashCode(p->Key2(),newBuck);
  94             q = (TCollection_IndexedDataMapNode*)p->Next();
  95             p->Next() = newdata1[k1];
  96             p->Next2() = newdata2[k2];
  97             newdata1[k1] = p;
  98             newdata2[k2] = p;
  99             p = q;
 100           }
 101         }
 102       }
 103     }
 104     EndResize(N,newBuck,newData1,newData2);
 105   }
 106 }
 107
 108 //=======================================================================
 109 //function : Clear
 110 //purpose  :
 111 //=======================================================================
 112
 113 void TCollection_IndexedDataMap::Clear()
 114 {
 115   if (!IsEmpty()) {
 116     Standard_Integer i;
 117     TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**) myData1;
 118     TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**) myData2;
 119     TCollection_IndexedDataMapNode *p,*q;
 120     for (i = 0; i <= NbBuckets(); i++) {
 121       p = data1[i];
 122       while (p) {
 123         q = (TCollection_IndexedDataMapNode*) p->Next();
 124         delete p;
 125         p = q;
 126       }
 127       data1[i] = data2[i] = NULL;
 128     }
 129   }
 130   TCollection_BasicMap::Destroy();
 131 }
 132
 133 //=======================================================================
 134 //function : Add
 135 //purpose  :
 136 //=======================================================================
 137
 138 Standard_Integer TCollection_IndexedDataMap::Add(const TheKey& K1, const TheItem& I)
 139 {
 140   if (Resizable())  ReSize(Extent());
 141   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 142   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 143   TCollection_IndexedDataMapNode* p;
 144   p = data1[k1];
 145   while (p) {
 146     if (Hasher::IsEqual(p->Key1(),K1))
 147       return p->Key2();
 148     p = (TCollection_IndexedDataMapNode*) p->Next();
 149   }
 150   Increment();
 151   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 152   Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
 153   p = new TCollection_IndexedDataMapNode(K1,Extent(),I,data1[k1],data2[k2]);
 154   data1[k1] = p;
 155   data2[k2] = p;
 156   return Extent();
 157 }
 158
 159
 160 //=======================================================================
 161 //function : Substitute
 162 //purpose  :
 163 //=======================================================================
 164
 165 void TCollection_IndexedDataMap::Substitute(const Standard_Integer I,
 166                                             const TheKey& K1,
 167                                             const TheItem& T)
 168 {
 169   Standard_OutOfRange_Raise_if(I < 1 || I > Extent(),
 170                                "IndexedMap::Substitute");
 171   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 172   TCollection_IndexedDataMapNode* p;
 173
 174   // check if K1 is not already in the map
 175   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 176   p = data1[k1];
 177   while (p) {
 178     if (Hasher::IsEqual(p->Key1(),K1))
 179       Standard_DomainError::Raise("IndexedMap::Substitute");
 180     p = (TCollection_IndexedDataMapNode*) p->Next();
 181   }
 182
 183   // Find the node for the index I
 184   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 185   Standard_Integer k2 = ::HashCode(I,NbBuckets());
 186   p = data2[k2];
 187   while (p) {
 188     if (p->Key2() == I)
 189       break;
 190     p = (TCollection_IndexedDataMapNode*) p->Next2();
 191   }
 192
 193   // remove the old key
 194   Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
 195   TCollection_IndexedDataMapNode* q = data1[k];
 196   if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next();
 197   else {
 198     while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next();
 199     q->Next() = p->Next();
 200   }
 201
 202   // update the node
 203   p->Key1() = K1;
 204   p->Value() = T;
 205   p->Next() = data1[k1];
 206   data1[k1] = p;
 207 }
 208
 209 //=======================================================================
 210 //function : RemoveLast
 211 //purpose  :
 212 //=======================================================================
 213
 214 void TCollection_IndexedDataMap::RemoveLast()
 215 {
 216   Standard_OutOfRange_Raise_if(Extent() == 0,
 217                                "IndexedMap::RemoveLast");
 218   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 219   TCollection_IndexedDataMapNode* p;
 220   TCollection_IndexedDataMapNode* q;
 221
 222   // Find the node for the last index and remove it
 223   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 224   Standard_Integer k2 = ::HashCode(Extent(),NbBuckets());
 225   p = data2[k2];
 226   q = NULL;
 227   while (p) {
 228     if (p->Key2() == Extent())
 229       break;
 230     q = p;
 231     p = (TCollection_IndexedDataMapNode*) p->Next2();
 232   }
 233   if (q == NULL)
 234     data2[k2] = (TCollection_IndexedDataMapNode*)p->Next2();
 235   else
 236     q->Next2() = p->Next2();
 237
 238   // remove the key
 239   Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
 240   q = data1[k];
 241   if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next();
 242   else {
 243     while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next();
 244     q->Next() = p->Next();
 245   }
 246
 247   Decrement();
 248   delete p;
 249 }
 250
 251
 252 //=======================================================================
 253 //function : FindKey
 254 //purpose  :
 255 //=======================================================================
 256
 257 const TheKey& TCollection_IndexedDataMap::FindKey(const Standard_Integer K2) const
 258 {
 259   Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
 260   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 261   Standard_Integer k2 = ::HashCode(K2,NbBuckets());
 262   TCollection_IndexedDataMapNode *p2;
 263   p2 = data2[k2];
 264   while (p2) {
 265     if (p2->Key2() == K2) return p2->Key1();
 266     p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
 267   }
 268   Standard_OutOfRange::Raise("IndexedDataMap : missing index !!!");
 269   return p2->Key1();
 270 }
 271
 272 //=======================================================================
 273 //function : FindFromIndex
 274 //purpose  :
 275 //=======================================================================
 276
 277 const TheItem& TCollection_IndexedDataMap::FindFromIndex
 278   (const Standard_Integer K2) const
 279 {
 280   Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
 281   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 282   Standard_Integer k2 = ::HashCode(K2,NbBuckets());
 283   TCollection_IndexedDataMapNode *p2;
 284   p2 = data2[k2];
 285   while (p2) {
 286     if (p2->Key2() == K2) return p2->Value();
 287     p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
 288   }
 289   Standard_OutOfRange::Raise("IndexedDataMap : missing index !!!");
 290   return p2->Value();
 291 }
 292
 293 //=======================================================================
 294 //function : ChangeFromIndex
 295 //purpose  :
 296 //=======================================================================
 297
 298 TheItem& TCollection_IndexedDataMap::ChangeFromIndex(const Standard_Integer K2)
 299 {
 300   Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
 301   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 302   Standard_Integer k2 = ::HashCode(K2,NbBuckets());
 303   TCollection_IndexedDataMapNode *p2;
 304   p2 = data2[k2];
 305   while (p2) {
 306     if (p2->Key2() == K2) return p2->Value();
 307     p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
 308   }
 309   Standard_OutOfRange::Raise("IndexedDataMap : missing index !!!");
 310   return p2->Value();
 311 }
 312
 313 //=======================================================================
 314 //function : FindIndex
 315 //purpose  :
 316 //=======================================================================
 317
 318 Standard_Integer TCollection_IndexedDataMap::FindIndex(const TheKey& K1) const
 319 {
 320   if (IsEmpty()) return 0;
 321   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 322   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 323   TCollection_IndexedDataMapNode *p1;
 324   p1 = data1[k1];
 325   while (p1) {
 326     if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Key2();
 327     p1 = (TCollection_IndexedDataMapNode*)p1->Next();
 328   }
 329   return 0;
 330 }
 331 //=======================================================================
 332 //function : Contains
 333 //purpose  :
 334 //=======================================================================
 335 Standard_Boolean TCollection_IndexedDataMap::Contains(const TheKey& K1) const
 336 {
 337   if (IsEmpty()) return Standard_False;
 338   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 339   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 340   TCollection_IndexedDataMapNode *p1;
 341   p1 = data1[k1];
 342   while (p1) {
 343     if (Hasher::IsEqual(p1->Key1(),K1)) return Standard_True;
 344     p1 = (TCollection_IndexedDataMapNode*) p1->Next();
 345   }
 346   return Standard_False;
 347 }
 348 //=======================================================================
 349 //function : FindFromKey
 350 //purpose  :
 351 //=======================================================================
 352 const TheItem& TCollection_IndexedDataMap::FindFromKey(const TheKey& K1) const
 353 {
 354   Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::FindFromKey");
 355   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 356   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 357   TCollection_IndexedDataMapNode *p1;
 358   p1 = data1[k1];
 359   while (p1) {
 360     if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value();
 361     p1 = (TCollection_IndexedDataMapNode*) p1->Next();
 362   }
 363   Standard_OutOfRange::Raise("TCollection_IndexedDataMap::FindFromKey");
 364   return p1->Value();
 365 }
 366 //=======================================================================
 367 //function : ChangeFromKey
 368 //purpose  :
 369 //=======================================================================
 370 TheItem& TCollection_IndexedDataMap::ChangeFromKey(const TheKey& K1)
 371 {
 372   Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::ChangeFromKey");
 373   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 374   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 375   TCollection_IndexedDataMapNode *p1;
 376   p1 = data1[k1];
 377   while (p1) {
 378     if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value();
 379     p1 = (TCollection_IndexedDataMapNode*)p1->Next();
 380   }
 381   Standard_OutOfRange::Raise("TCollection_IndexedDataMap::ChangeFromKey");
 382   return p1->Value();
 383 }
 384 //modified by NIZNHY-PKV Tue Jul 05 08:37:03 2011f
 385 //=======================================================================
 386 //function : FindFromKey1
 387 //purpose  :
 388 //=======================================================================
 389 Standard_Address TCollection_IndexedDataMap::FindFromKey1(const TheKey& K1) const
 390 {
 391   TCollection_IndexedDataMap *pMap=(TCollection_IndexedDataMap *)this;
 392   return pMap->ChangeFromKey1(K1);
 393 }
 394 //=======================================================================
 395 //function : ChangeFromKey1
 396 //purpose  :
 397 //=======================================================================
 398 Standard_Address TCollection_IndexedDataMap::ChangeFromKey1(const TheKey& K1)
 399 {
 400   if (IsEmpty()) {
 401     return NULL;
 402   }
 403   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 404   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 405   TCollection_IndexedDataMapNode *p1;
 406   p1 = data1[k1];
 407   while (p1) {
 408     if (Hasher::IsEqual(p1->Key1(),K1)) {
 409       return (Standard_Address)&p1->Value();
 410     }
 411     p1 = (TCollection_IndexedDataMapNode*) p1->Next();
 412   }
 413   return NULL;
 414 }