src/TCollection/TCollection_DoubleMap.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
  21
  22 //=======================================================================
  23 //function : TCollection_DoubleMap
  24 //purpose  :
  25 //=======================================================================
  26
  27 TCollection_DoubleMap::TCollection_DoubleMap(const Standard_Integer NbBuckets):
  28        TCollection_BasicMap(NbBuckets,Standard_False)
  29 {
  30 }
  31
  32 //=======================================================================
  33 //function : TCollection_DoubleMap
  34 //purpose  :
  35 //=======================================================================
  36
  37 TCollection_DoubleMap::TCollection_DoubleMap
  38   (const TCollection_DoubleMap& Other) :
  39        TCollection_BasicMap(Other.NbBuckets(),Standard_False)
  40 {
  41   if (Other.Extent() != 0)
  42     Standard_DomainError::Raise("TCollection:Copy of DoubleMap");
  43 }
  44
  45 //=======================================================================
  46 //function : Assign
  47 //purpose  :
  48 //=======================================================================
  49
  50 TCollection_DoubleMap& TCollection_DoubleMap::Assign
  51   (const TCollection_DoubleMap& Other)
  52 {
  53   if (this == &Other) return *this;
  54   Clear();
  55 //  ReSize(Other.NbBuckets());
  56   if  (!Other.IsEmpty()) {
  57     ReSize(Other.Extent());
  58     for (TCollection_DoubleMapIterator It(Other); It.More(); It.Next()) {
  59       Bind(It.Key1(),It.Key2());
  60     }
  61   }
  62   return *this;
  63 }
  64
  65
  66 //=======================================================================
  67 //function : ReSize
  68 //purpose  :
  69 //=======================================================================
  70
  71 void TCollection_DoubleMap::ReSize(const Standard_Integer N)
  72 {
  73   Standard_Integer newBuck;
  74   Standard_Address newData1=NULL, newData2=NULL;
  75   if (BeginResize(N,newBuck,newData1,newData2)) {
  76     if (myData1) {
  77       TCollection_DoubleMapNode** newdata1 = (TCollection_DoubleMapNode**) newData1;
  78       TCollection_DoubleMapNode** newdata2 = (TCollection_DoubleMapNode**) newData2;
  79       TCollection_DoubleMapNode** olddata1 = (TCollection_DoubleMapNode**) myData1;
  80       TCollection_DoubleMapNode *p, *q;
  81       Standard_Integer i,k1,k2;
  82       for (i = 0; i <= NbBuckets(); i++) {
  83         if (olddata1[i]) {
  84           p = olddata1[i];
  85           while (p) {
  86             k1 = Hasher1::HashCode(p->Key1(),newBuck);
  87             k2 = Hasher2::HashCode(p->Key2(),newBuck);
  88             q = (TCollection_DoubleMapNode*) p->Next();
  89             p->Next() = newdata1[k1];
  90             p->Next2() = newdata2[k2];
  91             newdata1[k1] = p;
  92             newdata2[k2] = p;
  93             p = q;
  94           }
  95         }
  96       }
  97     }
  98     EndResize(N,newBuck,newData1,newData2);
  99   }
 100 }
 101
 102 //=======================================================================
 103 //function : Clear
 104 //purpose  :
 105 //=======================================================================
 106
 107 void TCollection_DoubleMap::Clear()
 108 {
 109   if (!IsEmpty()) {
 110     Standard_Integer i;
 111     TCollection_DoubleMapNode** data1 = (TCollection_DoubleMapNode**) myData1;
 112 //    TCollection_DoubleMapNode** data2 = (TCollection_DoubleMapNode**) myData2;
 113     TCollection_DoubleMapNode *p,*q;
 114     for (i = 0; i <= NbBuckets(); i++) {
 115       p = data1[i];
 116       while (p) {
 117         q = (TCollection_DoubleMapNode*) p->Next();
 118         delete p;
 119         p = q;
 120       }
 121     }
 122   }
 123   TCollection_BasicMap::Destroy();
 124 }
 125
 126 //=======================================================================
 127 //function : Bind
 128 //purpose  :
 129 //=======================================================================
 130
 131 void TCollection_DoubleMap::Bind(const TheKey1& K1, const TheKey2& K2)
 132 {
 133   if (Resizable()) ReSize(Extent());
 134   TCollection_DoubleMapNode** data1 = (TCollection_DoubleMapNode**)myData1;
 135   TCollection_DoubleMapNode** data2 = (TCollection_DoubleMapNode**)myData2;
 136   Standard_Integer k1 = Hasher1::HashCode(K1,NbBuckets());
 137   Standard_Integer k2 = Hasher2::HashCode(K2,NbBuckets());
 138   TCollection_DoubleMapNode* p;
 139   p = data1[k1];
 140   while (p) {
 141     if (Hasher1::IsEqual(p->Key1(),K1))
 142       Standard_MultiplyDefined::Raise("DoubleMap:Bind");
 143     p = (TCollection_DoubleMapNode*) p->Next();
 144   }
 145   p = data2[k2];
 146   while (p) {
 147     if (Hasher2::IsEqual(p->Key2(),K2))
 148       Standard_MultiplyDefined::Raise("DoubleMap:Bind");
 149     p = (TCollection_DoubleMapNode*)p->Next2();
 150   }
 151   p = new TCollection_DoubleMapNode(K1,K2,data1[k1],data2[k2]);
 152   data1[k1] = p;
 153   data2[k2] = p;
 154   Increment();
 155 }
 156
 157 //=======================================================================
 158 //function : AreBound
 159 //purpose  :
 160 //=======================================================================
 161
 162 Standard_Boolean TCollection_DoubleMap::AreBound(const TheKey1& K1,
 163                                                  const TheKey2& K2) const
 164 {
 165   if (IsEmpty()) return Standard_False;
 166   TCollection_DoubleMapNode** data1 = (TCollection_DoubleMapNode**)myData1;
 167   TCollection_DoubleMapNode** data2 = (TCollection_DoubleMapNode**)myData2;
 168   Standard_Integer k1 = Hasher1::HashCode(K1,NbBuckets());
 169   Standard_Integer k2 = Hasher2::HashCode(K2,NbBuckets());
 170   TCollection_DoubleMapNode *p1, *p2;
 171   p1 = data1[k1];
 172   while (p1) {
 173     if (Hasher1::IsEqual(p1->Key1(),K1)) break;
 174     p1 = (TCollection_DoubleMapNode*) p1->Next();
 175   }
 176   if (p1 == NULL) return Standard_False;
 177   p2 = data2[k2];
 178   while (p2) {
 179     if (Hasher2::IsEqual(p2->Key2(),K2))
 180       break;
 181     p2 = (TCollection_DoubleMapNode*)p2->Next2();
 182   }
 183   if (p2 == NULL) return Standard_False;
 184   return p1 == p2;
 185 }
 186
 187 //=======================================================================
 188 //function : IsBound1
 189 //purpose  :
 190 //=======================================================================
 191
 192 Standard_Boolean TCollection_DoubleMap::IsBound1(const TheKey1& K1) const
 193 {
 194   if (IsEmpty()) return Standard_False;
 195   TCollection_DoubleMapNode** data1 = (TCollection_DoubleMapNode**)myData1;
 196   Standard_Integer k1 = Hasher1::HashCode(K1,NbBuckets());
 197   TCollection_DoubleMapNode *p1;
 198   p1 = data1[k1];
 199   while (p1) {
 200     if (Hasher1::IsEqual(p1->Key1(),K1)) return Standard_True;
 201     p1 = (TCollection_DoubleMapNode*)  p1->Next();
 202   }
 203   return Standard_False;
 204 }
 205
 206 //=======================================================================
 207 //function : IsBound2
 208 //purpose  :
 209 //=======================================================================
 210
 211 Standard_Boolean TCollection_DoubleMap::IsBound2(const TheKey2& K2) const
 212 {
 213   if (IsEmpty()) return Standard_False;
 214   TCollection_DoubleMapNode** data2 = (TCollection_DoubleMapNode**)myData2;
 215   Standard_Integer k2 = Hasher2::HashCode(K2,NbBuckets());
 216   TCollection_DoubleMapNode *p2;
 217   p2 = data2[k2];
 218   while (p2) {
 219     if (Hasher2::IsEqual(p2->Key2(),K2)) return Standard_True;
 220     p2 = (TCollection_DoubleMapNode*)p2->Next2();
 221   }
 222   return Standard_False;
 223 }
 224
 225 //=======================================================================
 226 //function : Find1
 227 //purpose  :
 228 //=======================================================================
 229
 230 const TheKey2& TCollection_DoubleMap::Find1(const TheKey1& K1) const
 231 {
 232   Standard_NoSuchObject_Raise_if(IsEmpty(),"TCollection_DoubleMap::Find1");
 233   TCollection_DoubleMapNode** data1 = (TCollection_DoubleMapNode**)myData1;
 234   Standard_Integer k1 = Hasher1::HashCode(K1,NbBuckets());
 235   TCollection_DoubleMapNode *p1;
 236   p1 = data1[k1];
 237   while (p1) {
 238     if (Hasher1::IsEqual(p1->Key1(),K1)) return p1->Key2();
 239     p1 = (TCollection_DoubleMapNode*) p1->Next();
 240   }
 241   Standard_NoSuchObject::Raise("TCollection_DoubleMap::Find1");
 242   return p1->Key2();
 243 }
 244
 245 //=======================================================================
 246 //function : Find2
 247 //purpose  :
 248 //=======================================================================
 249
 250 const TheKey1& TCollection_DoubleMap::Find2(const TheKey2& K2) const
 251 {
 252   Standard_NoSuchObject_Raise_if(IsEmpty(),"TCollection_DoubleMap::Find2");
 253   TCollection_DoubleMapNode** data2 = (TCollection_DoubleMapNode**)myData2;
 254   Standard_Integer k2 = Hasher2::HashCode(K2,NbBuckets());
 255   TCollection_DoubleMapNode *p2;
 256   p2 = data2[k2];
 257   while (p2) {
 258     if (Hasher2::IsEqual(p2->Key2(),K2)) return p2->Key1();
 259     p2 = (TCollection_DoubleMapNode*)p2->Next2();
 260   }
 261   Standard_NoSuchObject::Raise("TCollection_DoubleMap::Find2");
 262   return p2->Key1();
 263 }
 264
 265 //=======================================================================
 266 //function : UnBind1
 267 //purpose  :
 268 //=======================================================================
 269
 270 Standard_Boolean TCollection_DoubleMap::UnBind1(const TheKey1& K1)
 271 {
 272   if (IsEmpty()) return Standard_False;
 273   TCollection_DoubleMapNode** data1 = (TCollection_DoubleMapNode**)myData1;
 274   TCollection_DoubleMapNode** data2 = (TCollection_DoubleMapNode**)myData2;
 275   Standard_Integer k1 = Hasher1::HashCode(K1,NbBuckets());
 276   Standard_Integer k2;
 277   TCollection_DoubleMapNode *p1, *p2, *q1, *q2;
 278   q1 = q2 = NULL;
 279   p1 = data1[k1];
 280   while (p1) {
 281     if (Hasher1::IsEqual(p1->Key1(),K1)) {
 282       // remove from the first
 283       if (q1)
 284         q1->Next() = p1->Next();
 285       else
 286         data1[k1] = (TCollection_DoubleMapNode*) p1->Next();
 287       // remove from the second
 288       k2 = Hasher2::HashCode(p1->Key2(),NbBuckets());
 289       p2 = data2[k2];
 290       while (p2) {
 291         if (p2 == p1) {
 292           if (q2)
 293             q2->Next2() = p2->Next2();
 294           else
 295             data2[k2] = (TCollection_DoubleMapNode*)p2->Next2();
 296           break;
 297         }
 298         q2 = p2;
 299         p2 = (TCollection_DoubleMapNode*)p2->Next2();
 300       }
 301       delete p1;
 302       Decrement();
 303       return Standard_True;
 304     }
 305     q1 = p1;
 306     p1 = (TCollection_DoubleMapNode*) p1->Next();
 307   }
 308   return Standard_False;
 309 }
 310
 311 //=======================================================================
 312 //function : UnBind2
 313 //purpose  :
 314 //=======================================================================
 315
 316 Standard_Boolean TCollection_DoubleMap::UnBind2(const TheKey2& K2)
 317 {
 318   if (IsEmpty()) return Standard_False;
 319   TCollection_DoubleMapNode** data1 = (TCollection_DoubleMapNode**)myData1;
 320   TCollection_DoubleMapNode** data2 = (TCollection_DoubleMapNode**)myData2;
 321   Standard_Integer k2 = Hasher2::HashCode(K2,NbBuckets());
 322   Standard_Integer k1;
 323   TCollection_DoubleMapNode *p1, *p2, *q1, *q2;
 324   q1 = q2 = NULL;
 325   p2 = data2[k2];
 326   while (p2) {
 327     if (Hasher2::IsEqual(p2->Key2(),K2)) {
 328       // remove from the second
 329       if (q2)
 330         q2->Next2() = p2->Next2();
 331       else
 332         data2[k2] = (TCollection_DoubleMapNode*)p2->Next2();
 333       // remove from the first
 334       k1 = Hasher1::HashCode(p2->Key1(),NbBuckets());
 335       p1 = data1[k1];
 336       while (p1) {
 337         if (p2 == p1) {
 338           if (q1)
 339             q1->Next() = p1->Next();
 340           else
 341             data1[k1] = (TCollection_DoubleMapNode*) p1->Next();
 342           break;
 343         }
 344         q1 = p1;
 345         p1 = (TCollection_DoubleMapNode*)  p1->Next();
 346       }
 347       delete p2;
 348       Decrement();
 349       return Standard_True;
 350     }
 351     q2 = p2;
 352     p2 = (TCollection_DoubleMapNode*)p2->Next2();
 353   }
 354   return Standard_False;
 355 }
 356
 357 // method of the iterator
 358
 359 //=======================================================================
 360 //function : Key1
 361 //purpose  :
 362 //=======================================================================
 363
 364 const TheKey1& TCollection_DoubleMapIterator::Key1() const
 365 {
 366   Standard_NoSuchObject_Raise_if(!More(),"TCollection_DoubleMapIterator::Key1");
 367   return ((TCollection_DoubleMapNode*) myNode)->Key1();
 368 }
 369
 370 //=======================================================================
 371 //function : Key2
 372 //purpose  :
 373 //=======================================================================
 374
 375 const TheKey2& TCollection_DoubleMapIterator::Key2() const
 376 {
 377   Standard_NoSuchObject_Raise_if(!More(),"TCollection_DoubleMapIterator::Key2");
 378   return ((TCollection_DoubleMapNode*) myNode)->Key2();
 379 }