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     throw Standard_DomainError("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(), "IndexedDataMap::Substitute : "
 170                                                       "Index is out of range");
 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       if (p->Key2() != I)
 180         throw Standard_DomainError("IndexedDataMap::Substitute : "
 181                                    "Attempt to substitute existing key");
 182       p->Key1() = K1;
 183       p->Value() = T;
 184       return;
 185     }
 186     p = (TCollection_IndexedDataMapNode*) p->Next();
 187   }
 188
 189   // Find the node for the index I
 190   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 191   Standard_Integer k2 = ::HashCode(I,NbBuckets());
 192   p = data2[k2];
 193   while (p) {
 194     if (p->Key2() == I)
 195       break;
 196     p = (TCollection_IndexedDataMapNode*) p->Next2();
 197   }
 198
 199   // remove the old key
 200   Standard_Integer k = Hasher::HashCode(p->Key1(),NbBuckets());
 201   TCollection_IndexedDataMapNode* q = data1[k];
 202   if (q == p) data1[k] = (TCollection_IndexedDataMapNode*) p->Next();
 203   else {
 204     while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next();
 205     q->Next() = p->Next();
 206   }
 207
 208   // update the node
 209   p->Key1() = K1;
 210   p->Value() = T;
 211   p->Next() = data1[k1];
 212   data1[k1] = p;
 213 }
 214
 215 //=======================================================================
 216 //function : RemoveLast
 217 //purpose  :
 218 //=======================================================================
 219
 220 void TCollection_IndexedDataMap::RemoveLast()
 221 {
 222   Standard_OutOfRange_Raise_if(Extent() == 0,
 223                                "IndexedMap::RemoveLast");
 224   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 225   TCollection_IndexedDataMapNode* p;
 226   TCollection_IndexedDataMapNode* q;
 227
 228   // Find the node for the last index and remove it
 229   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)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_IndexedDataMapNode*) p->Next2();
 238   }
 239   if (q == NULL)
 240     data2[k2] = (TCollection_IndexedDataMapNode*)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_IndexedDataMapNode*) p->Next();
 248   else {
 249     while(q->Next() != p) q = (TCollection_IndexedDataMapNode*) q->Next();
 250     q->Next() = p->Next();
 251   }
 252
 253   Decrement();
 254   delete p;
 255 }
 256
 257
 258 //=======================================================================
 259 //function : FindKey
 260 //purpose  :
 261 //=======================================================================
 262
 263 const TheKey& TCollection_IndexedDataMap::FindKey(const Standard_Integer K2) const
 264 {
 265   Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
 266   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 267   Standard_Integer k2 = ::HashCode(K2,NbBuckets());
 268   TCollection_IndexedDataMapNode *p2;
 269   p2 = data2[k2];
 270   while (p2) {
 271     if (p2->Key2() == K2) return p2->Key1();
 272     p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
 273   }
 274   throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
 275   return p2->Key1();
 276 }
 277
 278 //=======================================================================
 279 //function : FindFromIndex
 280 //purpose  :
 281 //=======================================================================
 282
 283 const TheItem& TCollection_IndexedDataMap::FindFromIndex
 284   (const Standard_Integer K2) const
 285 {
 286   Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
 287   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 288   Standard_Integer k2 = ::HashCode(K2,NbBuckets());
 289   TCollection_IndexedDataMapNode *p2;
 290   p2 = data2[k2];
 291   while (p2) {
 292     if (p2->Key2() == K2) return p2->Value();
 293     p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
 294   }
 295   throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
 296   return p2->Value();
 297 }
 298
 299 //=======================================================================
 300 //function : ChangeFromIndex
 301 //purpose  :
 302 //=======================================================================
 303
 304 TheItem& TCollection_IndexedDataMap::ChangeFromIndex(const Standard_Integer K2)
 305 {
 306   Standard_OutOfRange_Raise_if(K2 < 1 || K2 > Extent(), "IndexedDataMap");
 307   TCollection_IndexedDataMapNode** data2 = (TCollection_IndexedDataMapNode**)myData2;
 308   Standard_Integer k2 = ::HashCode(K2,NbBuckets());
 309   TCollection_IndexedDataMapNode *p2;
 310   p2 = data2[k2];
 311   while (p2) {
 312     if (p2->Key2() == K2) return p2->Value();
 313     p2 = (TCollection_IndexedDataMapNode*)p2->Next2();
 314   }
 315   throw Standard_OutOfRange("IndexedDataMap : missing index !!!");
 316   return p2->Value();
 317 }
 318
 319 //=======================================================================
 320 //function : FindIndex
 321 //purpose  :
 322 //=======================================================================
 323
 324 Standard_Integer TCollection_IndexedDataMap::FindIndex(const TheKey& K1) const
 325 {
 326   if (IsEmpty()) return 0;
 327   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 328   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 329   TCollection_IndexedDataMapNode *p1;
 330   p1 = data1[k1];
 331   while (p1) {
 332     if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Key2();
 333     p1 = (TCollection_IndexedDataMapNode*)p1->Next();
 334   }
 335   return 0;
 336 }
 337 //=======================================================================
 338 //function : Contains
 339 //purpose  :
 340 //=======================================================================
 341 Standard_Boolean TCollection_IndexedDataMap::Contains(const TheKey& K1) const
 342 {
 343   if (IsEmpty()) return Standard_False;
 344   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 345   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 346   TCollection_IndexedDataMapNode *p1;
 347   p1 = data1[k1];
 348   while (p1) {
 349     if (Hasher::IsEqual(p1->Key1(),K1)) return Standard_True;
 350     p1 = (TCollection_IndexedDataMapNode*) p1->Next();
 351   }
 352   return Standard_False;
 353 }
 354 //=======================================================================
 355 //function : FindFromKey
 356 //purpose  :
 357 //=======================================================================
 358 const TheItem& TCollection_IndexedDataMap::FindFromKey(const TheKey& K1) const
 359 {
 360   Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::FindFromKey");
 361   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 362   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 363   TCollection_IndexedDataMapNode *p1;
 364   p1 = data1[k1];
 365   while (p1) {
 366     if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value();
 367     p1 = (TCollection_IndexedDataMapNode*) p1->Next();
 368   }
 369   throw Standard_OutOfRange("TCollection_IndexedDataMap::FindFromKey");
 370   return p1->Value();
 371 }
 372 //=======================================================================
 373 //function : ChangeFromKey
 374 //purpose  :
 375 //=======================================================================
 376 TheItem& TCollection_IndexedDataMap::ChangeFromKey(const TheKey& K1)
 377 {
 378   Standard_OutOfRange_Raise_if(IsEmpty(),"TCollection_IndexedDataMap::ChangeFromKey");
 379   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 380   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 381   TCollection_IndexedDataMapNode *p1;
 382   p1 = data1[k1];
 383   while (p1) {
 384     if (Hasher::IsEqual(p1->Key1(),K1)) return p1->Value();
 385     p1 = (TCollection_IndexedDataMapNode*)p1->Next();
 386   }
 387   throw Standard_OutOfRange("TCollection_IndexedDataMap::ChangeFromKey");
 388   return p1->Value();
 389 }
 390 //modified by NIZNHY-PKV Tue Jul 05 08:37:03 2011f
 391 //=======================================================================
 392 //function : FindFromKey1
 393 //purpose  :
 394 //=======================================================================
 395 Standard_Address TCollection_IndexedDataMap::FindFromKey1(const TheKey& K1) const
 396 {
 397   TCollection_IndexedDataMap *pMap=(TCollection_IndexedDataMap *)this;
 398   return pMap->ChangeFromKey1(K1);
 399 }
 400 //=======================================================================
 401 //function : ChangeFromKey1
 402 //purpose  :
 403 //=======================================================================
 404 Standard_Address TCollection_IndexedDataMap::ChangeFromKey1(const TheKey& K1)
 405 {
 406   if (IsEmpty()) {
 407     return NULL;
 408   }
 409   TCollection_IndexedDataMapNode** data1 = (TCollection_IndexedDataMapNode**)myData1;
 410   Standard_Integer k1 = Hasher::HashCode(K1,NbBuckets());
 411   TCollection_IndexedDataMapNode *p1;
 412   p1 = data1[k1];
 413   while (p1) {
 414     if (Hasher::IsEqual(p1->Key1(),K1)) {
 415       return (Standard_Address)&p1->Value();
 416     }
 417     p1 = (TCollection_IndexedDataMapNode*) p1->Next();
 418   }
 419   return NULL;
 420 }