src/NCollection/NCollection_BaseSequence.cxx

   1 // Created on: 2002-03-29
   2 // Created by: Alexander GRIGORIEV
   3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   7 // This library is free software; you can redistribute it and/or modify it under
   8 // the terms of the GNU Lesser General Public License version 2.1 as published
   9 // by the Free Software Foundation, with special exception defined in the file
  10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  11 // distribution for complete text of the license and disclaimer of any warranty.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  15
  16 // Purpose:   Implementation of the BaseSequence class
  17
  18 #include <NCollection_BaseSequence.hxx>
  19 #include <Standard_NoSuchObject.hxx>
  20 #include <Standard_OutOfRange.hxx>
  21 #include <Standard_DomainError.hxx>
  22
  23 inline void NCollection_BaseSequence::Nullify ()
  24 {
  25   myFirstItem = myLastItem = myCurrentItem = NULL;
  26   myCurrentIndex = mySize = 0;
  27 }
  28
  29 //=======================================================================
  30 //function : ClearSeq
  31 //purpose  : removes all items from the current sequence
  32 //=======================================================================
  33
  34 void NCollection_BaseSequence::ClearSeq (NCollection_DelSeqNode fDel)
  35 {
  36   NCollection_SeqNode* p = myFirstItem;
  37   while (p) {
  38     NCollection_SeqNode* q = p;
  39     p = p->Next();
  40     fDel (q, myAllocator);
  41   }
  42   Nullify();
  43 }
  44
  45 //=======================================================================
  46 //function : PAppend
  47 //purpose  : append an item to sequence
  48 //=======================================================================
  49
  50 void NCollection_BaseSequence::PAppend (NCollection_SeqNode * theItem)
  51 {
  52   if (mySize == 0) {
  53     myFirstItem = myLastItem = myCurrentItem = theItem;
  54     myCurrentIndex = mySize = 1;
  55   } else {
  56     myLastItem->SetNext(theItem);
  57     theItem->SetPrevious(myLastItem);
  58     theItem->SetNext(NULL);
  59     myLastItem = theItem;
  60     ++ mySize;
  61   }
  62 }
  63
  64 //=======================================================================
  65 //function : PAppend
  66 //purpose  : push a sequence at the end of the sequence
  67 //=======================================================================
  68
  69 void NCollection_BaseSequence::PAppend(NCollection_BaseSequence& Other)
  70 {
  71   if (Other.mySize == 0)
  72     return;
  73   if (mySize == 0) {
  74     mySize         = Other.mySize;
  75     myFirstItem    = Other.myFirstItem;
  76     myLastItem     = Other.myLastItem;
  77     myCurrentItem  = myFirstItem;
  78     myCurrentIndex = 1;
  79   } else {
  80     mySize += Other.mySize;
  81     myLastItem->SetNext(Other.myFirstItem);
  82     if (Other.myFirstItem) {
  83       Other.myFirstItem->SetPrevious(myLastItem);
  84       myLastItem = Other.myLastItem;
  85     }
  86   }
  87   Other.Nullify();
  88 }
  89
  90 //=======================================================================
  91 //function : PPrepend
  92 //purpose  : prepend an item to sequence
  93 //=======================================================================
  94
  95 void NCollection_BaseSequence::PPrepend (NCollection_SeqNode * theItem)
  96 {
  97   if (mySize == 0) {
  98     myFirstItem = myLastItem = myCurrentItem = theItem;
  99     myCurrentIndex = mySize = 1;
 100   } else {
 101     myFirstItem->SetPrevious (theItem);
 102     theItem->SetNext (myFirstItem);
 103     theItem->SetPrevious(NULL);
 104     theItem->SetNext(myFirstItem);
 105     myFirstItem = theItem;
 106     ++ mySize;
 107     ++ myCurrentIndex;
 108   }
 109 }
 110
 111 //=======================================================================
 112 //function : PPrepend
 113 //purpose  : push a sequence in the beginning of the sequence
 114 //=======================================================================
 115
 116 void NCollection_BaseSequence::PPrepend (NCollection_BaseSequence& Other)
 117 {
 118   if (Other.mySize == 0)
 119     return;
 120   if (mySize == 0) {
 121     mySize         = Other.mySize;
 122     myFirstItem    = Other.myFirstItem;
 123     myLastItem     = Other.myLastItem;
 124     myCurrentIndex = 1;
 125     myCurrentItem  = myFirstItem;
 126   } else {
 127     mySize += Other.mySize;
 128     if (Other.myLastItem)
 129       Other.myLastItem->SetNext (myFirstItem);
 130     myFirstItem->SetPrevious(Other.myLastItem);
 131     myFirstItem = Other.myFirstItem;
 132     myCurrentIndex += Other.mySize;
 133   }
 134   Other.Nullify();
 135 }
 136
 137 //=======================================================================
 138 //function : PReverse
 139 //purpose  : reverse the order of a given sequence
 140 //=======================================================================
 141
 142 void NCollection_BaseSequence::PReverse()
 143 {
 144   NCollection_SeqNode* p = myFirstItem;
 145   while (p) {
 146     NCollection_SeqNode* tmp = p->Next();
 147     p->SetNext (p->Previous());
 148     p->SetPrevious (tmp);
 149     p = tmp;
 150   }
 151   NCollection_SeqNode* tmp = myFirstItem;
 152   myFirstItem = myLastItem;
 153   myLastItem = tmp;
 154   if (mySize != 0)
 155     myCurrentIndex = mySize + 1 - myCurrentIndex;
 156 }
 157
 158
 159 //=======================================================================
 160 //function : PInsertAfter
 161 //purpose  :
 162 //=======================================================================
 163
 164 void NCollection_BaseSequence::PInsertAfter
 165                              (NCollection_BaseSequence::Iterator& thePosition,
 166                               NCollection_SeqNode                 * theItem)
 167 {
 168   NCollection_SeqNode * aPos = thePosition.myCurrent;
 169   if (aPos == NULL)
 170     PPrepend (theItem);
 171   else {
 172     theItem->SetNext (aPos->Next());
 173     theItem->SetPrevious (aPos);
 174     if (aPos->Next() == NULL)
 175       myLastItem = theItem;
 176     else
 177       aPos->Next()->SetPrevious(theItem);
 178     aPos->SetNext(theItem);
 179     ++ mySize;
 180     myCurrentItem = myFirstItem;
 181     myCurrentIndex = 1;
 182   }
 183 }
 184
 185 //=======================================================================
 186 //function : PInsertAfter
 187 //purpose  :
 188 //=======================================================================
 189
 190 void NCollection_BaseSequence::PInsertAfter(const Standard_Integer theIndex,
 191                                             NCollection_SeqNode * theItem)
 192 {
 193   if (theIndex == 0)
 194     PPrepend (theItem);
 195   else {
 196     NCollection_SeqNode * p = Find (theIndex);
 197     theItem->SetNext(p->Next());
 198     theItem->SetPrevious(p);
 199     if (theIndex == mySize)
 200       myLastItem = theItem;
 201     else
 202       p->Next()->SetPrevious(theItem);
 203     p->SetNext(theItem);
 204     ++ mySize;
 205     if (theIndex < myCurrentIndex)
 206       ++ myCurrentIndex;
 207   }
 208 }
 209
 210 //=======================================================================
 211 //function : PInsertAfter
 212 //purpose  : insert a sequence after a given index in the sequence
 213 //=======================================================================
 214
 215 void NCollection_BaseSequence::PInsertAfter (const Standard_Integer theIndex,
 216                                              NCollection_BaseSequence& Other)
 217 {
 218   if (theIndex < 0 || theIndex > mySize)
 219     throw Standard_OutOfRange();
 220   if (Other.mySize != 0) {
 221     if (theIndex == 0)
 222       PPrepend (Other);
 223     else {
 224       NCollection_SeqNode * p = Find (theIndex);
 225       Other.myFirstItem->SetPrevious (p);
 226       Other.myLastItem->SetNext (p->Next());
 227       if (theIndex == mySize)
 228         myLastItem = Other.myLastItem;
 229       else
 230         p->Next()->SetPrevious (Other.myLastItem);
 231       p->SetNext (Other.myFirstItem);
 232       mySize += Other.mySize;
 233       if (theIndex < myCurrentIndex)
 234         myCurrentIndex += Other.mySize;
 235       Other.Nullify();
 236     }
 237   }
 238 }
 239
 240 //=======================================================================
 241 //function : PExchange
 242 //purpose  : exchange two elements in the sequence
 243 //=======================================================================
 244
 245 void NCollection_BaseSequence::PExchange (const Standard_Integer I,
 246                                           const Standard_Integer J)
 247 {
 248   Standard_OutOfRange_Raise_if (I <= 0 || J <= 0 || I > mySize || J > mySize,
 249                                 "" );
 250
 251   // Assume I < J
 252   if (J < I)
 253     PExchange(J,I);
 254   else if (I < J) {
 255     NCollection_SeqNode * pi = Find(I);
 256     NCollection_SeqNode * pj = Find(J);
 257
 258     // update the node before I
 259     if (pi->Previous())
 260       pi->Previous()->SetNext (pj);
 261     else
 262       myFirstItem = pj;
 263
 264     // update the node after J
 265     if (pj->Next())
 266       pj->Next()->SetPrevious(pi);
 267     else
 268       myLastItem = pi;
 269
 270     if (pi->Next() == pj) {          // I and J are consecutives, update them
 271       pj->SetPrevious (pi->Previous());
 272       pi->SetPrevious (pj);
 273       pi->SetNext (pj->Next());
 274       pj->SetNext (pi);
 275     }
 276     else {                        // I and J are not consecutive
 277       // update the node after I
 278       pi->Next()->SetPrevious (pj);
 279       // update the node before J
 280       pj->Previous()->SetNext (pi);
 281       // update nodes I and J
 282       NCollection_SeqNode* tmp = pi->Next();
 283       pi->SetNext (pj->Next());
 284       pj->SetNext (tmp);
 285       tmp = pi->Previous();
 286       pi->SetPrevious (pj->Previous());
 287       pj->SetPrevious (tmp);
 288     }
 289
 290     if      (myCurrentIndex == I) myCurrentItem = pj;
 291     else if (myCurrentIndex == J) myCurrentItem = pi;
 292   }
 293 }
 294
 295 //=======================================================================
 296 //function : PSplit
 297 //purpose  :
 298 //=======================================================================
 299
 300 void NCollection_BaseSequence::PSplit (const Standard_Integer theIndex,
 301                                        NCollection_BaseSequence& Sub)
 302 {
 303   Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize,"" );
 304   Standard_DomainError_Raise_if (this == &Sub, "No Split on myself!!");
 305
 306   NCollection_SeqNode * p = Find (theIndex);
 307
 308   Sub.myLastItem = myLastItem;
 309   Sub.mySize = mySize - theIndex + 1;
 310
 311   myLastItem = p->Previous();
 312   if (myLastItem) {
 313     myLastItem->SetNext(NULL);
 314     mySize = theIndex - 1;
 315     if (myCurrentIndex >= theIndex) {
 316       myCurrentIndex = 1;
 317       myCurrentItem  = myFirstItem;
 318     }
 319   } else {
 320     myFirstItem = myCurrentItem = NULL;
 321     mySize = myCurrentIndex = 0;
 322   }
 323
 324   Sub.myFirstItem = Sub.myCurrentItem = p;
 325   p->SetPrevious (NULL);
 326   Sub.myCurrentIndex = 1;
 327 }
 328
 329 //=======================================================================
 330 //function : Remove
 331 //purpose  :
 332 //=======================================================================
 333
 334 void NCollection_BaseSequence::RemoveSeq
 335                               (NCollection_BaseSequence::Iterator& thePosition,
 336                                NCollection_DelSeqNode              fDel)
 337 {
 338   NCollection_SeqNode * aPos = thePosition.myCurrent;
 339   if (aPos == NULL)
 340     return;
 341   thePosition.myCurrent = aPos -> Next();
 342
 343   if (aPos->Previous())
 344     aPos->Previous()->SetNext (aPos->Next());
 345   else
 346     myFirstItem = aPos->Next();
 347
 348   if (aPos->Next())
 349     aPos->Next()->SetPrevious (aPos->Previous());
 350   else
 351     myLastItem = aPos->Previous();
 352
 353   -- mySize;
 354   myCurrentItem  = myLastItem;
 355   myCurrentIndex = mySize;
 356
 357   fDel (aPos, myAllocator);
 358 }
 359
 360 //=======================================================================
 361 //function : Remove
 362 //purpose  :
 363 //=======================================================================
 364
 365 void NCollection_BaseSequence::RemoveSeq (const Standard_Integer theIndex,
 366                                           NCollection_DelSeqNode fDel)
 367 {
 368   Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize,
 369                                 "NCollection_BaseSequence::RemoveSeq() - index is out of range");
 370
 371   NCollection_SeqNode * p = Find (theIndex);
 372   if (p->Previous())
 373     p->Previous()->SetNext (p->Next());
 374   else
 375     myFirstItem = p->Next();
 376   if (p->Next())
 377     p->Next()->SetPrevious (p->Previous());
 378   else
 379     myLastItem = p->Previous();
 380
 381   -- mySize;
 382   if      (myCurrentIndex > theIndex) -- myCurrentIndex;
 383   else if (myCurrentIndex == theIndex) {
 384     if (p->Next())
 385       myCurrentItem = p->Next();
 386     else {
 387       myCurrentItem = myLastItem;
 388       myCurrentIndex = mySize;
 389     }
 390   }
 391   fDel (p, myAllocator);
 392 }
 393
 394 //=======================================================================
 395 //function : Remove
 396 //purpose  : remove a set of items
 397 //=======================================================================
 398
 399 void NCollection_BaseSequence::RemoveSeq (const Standard_Integer From,
 400                                           const Standard_Integer To,
 401                                           NCollection_DelSeqNode fDel)
 402 {
 403   Standard_OutOfRange_Raise_if (From <= 0 || To > mySize || From > To,
 404                                 "NCollection_BaseSequence::RemoveSeq() - invalid input range");
 405
 406   NCollection_SeqNode * pfrom = Find(From);
 407   NCollection_SeqNode * pto   = Find(To);
 408
 409   if (pfrom->Previous())
 410     pfrom->Previous()->SetNext (pto->Next());
 411   else
 412     myFirstItem = pto->Next();
 413   if (pto->Next())
 414     pto->Next()->SetPrevious (pfrom->Previous());
 415   else
 416     myLastItem = pfrom->Previous();
 417
 418   mySize -= To - From + 1;
 419   if      (myCurrentIndex > To)
 420     myCurrentIndex -= To - From + 1;
 421   else if (myCurrentIndex >= From) {
 422     if (pto->Next()) {
 423       myCurrentItem = pto->Next();
 424       myCurrentIndex = From;                      // AGV fix 24.05.01
 425     } else {
 426       myCurrentItem = myLastItem;
 427       myCurrentIndex = mySize;
 428     }
 429   }
 430
 431   for (Standard_Integer i = From; i <= To; i++) {
 432     NCollection_SeqNode * tmp = pfrom;
 433     pfrom = pfrom->Next();
 434     fDel (tmp, myAllocator);
 435   }
 436 }
 437
 438 //=======================================================================
 439 //function : Find
 440 //purpose  :
 441 //=======================================================================
 442
 443 NCollection_SeqNode * NCollection_BaseSequence::Find (const Standard_Integer theIndex) const
 444 {
 445   Standard_Integer i;
 446   NCollection_SeqNode * p;
 447   if (theIndex <= myCurrentIndex) {
 448     if (theIndex < myCurrentIndex / 2) {
 449       p = myFirstItem;
 450       for (i = 1; i < theIndex; i++)
 451         p = p->Next();
 452     } else {
 453       p = myCurrentItem;
 454       for (i = myCurrentIndex; i > theIndex; i--)
 455         p = p->Previous();
 456     }
 457   } else {
 458     if (theIndex < (myCurrentIndex + mySize) / 2) {
 459       p = myCurrentItem;
 460       for (i = myCurrentIndex; i < theIndex; i++)
 461         p = p->Next();
 462     } else {
 463       p = myLastItem;
 464       for (i = mySize; i > theIndex; i--)
 465         p = p->Previous();
 466     }
 467   }
 468   return p;
 469 }