src/TCollection/TCollection_BaseSequence.cxx

   1 // Copyright (c) 1998-1999 Matra Datavision
   2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
   3 //
   4 // This file is part of Open CASCADE Technology software library.
   5 //
   6 // This library is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU Lesser General Public License version 2.1 as published
   8 // by the Free Software Foundation, with special exception defined in the file
   9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
  10 // distribution for complete text of the license and disclaimer of any warranty.
  11 //
  12 // Alternatively, this file may be used under the terms of Open CASCADE
  13 // commercial license or contractual agreement.
  14
  15
  16 #include <Standard_DomainError.hxx>
  17 #include <Standard_NoSuchObject.hxx>
  18 #include <Standard_OutOfRange.hxx>
  19 #include <TCollection_BaseSequence.hxx>
  20 #include <TCollection_SeqNode.hxx>
  21
  22 typedef void (*DelNode) (TCollection_SeqNode*);
  23
  24 TCollection_BaseSequence::TCollection_BaseSequence() :
  25        FirstItem(NULL),
  26        LastItem(NULL),
  27        CurrentItem(NULL),
  28        CurrentIndex(0),
  29        Size(0)
  30 {
  31 }
  32
  33
  34
  35 // ----------------------------------
  36 // Clear : Clear the Current Sequence
  37 // ----------------------------------
  38 void TCollection_BaseSequence::Clear(const Standard_Address delnode)
  39 {
  40   Size = 0;
  41   TCollection_SeqNode* p = (TCollection_SeqNode*) FirstItem;
  42   TCollection_SeqNode* q;
  43   while (p) {
  44     q = p;
  45     p = p->Next();
  46     ((DelNode)delnode) (q);
  47   }
  48   LastItem = FirstItem = CurrentItem  = NULL;
  49   CurrentIndex = 0;
  50 }
  51
  52 void TCollection_BaseSequence::PAppend(const Standard_Address newnode)
  53 {
  54   if (Size == 0) {
  55     FirstItem = LastItem = CurrentItem = newnode;
  56     CurrentIndex = Size = 1;
  57   }
  58   else {
  59     ((TCollection_SeqNode*)LastItem)->Next() = (TCollection_SeqNode*)newnode;
  60     LastItem = newnode;
  61     Size++;
  62   }
  63 }
  64
  65 // ---------------------------------------------------
  66 // Append : Push a sequence at the end of the sequence
  67 // ---------------------------------------------------
  68 void TCollection_BaseSequence::PAppend(TCollection_BaseSequence& Other)
  69 {
  70   if (Other.Size == 0)
  71     return;
  72   if (Size == 0) {
  73     Size         = Other.Size;
  74     FirstItem    = Other.FirstItem;
  75     LastItem     = Other.LastItem;
  76     CurrentItem  = FirstItem;
  77     CurrentIndex = 1;
  78   }
  79   else {
  80     Size += Other.Size;
  81     ((TCollection_SeqNode*)LastItem)->Next() = (TCollection_SeqNode*)Other.FirstItem;
  82     if (Other.FirstItem) {
  83       ((TCollection_SeqNode*)Other.FirstItem)->Previous() = (TCollection_SeqNode*)LastItem;
  84       LastItem = Other.LastItem;
  85     }
  86   }
  87   Other.Nullify();
  88 }
  89
  90
  91
  92 void TCollection_BaseSequence::PPrepend(const Standard_Address newnode)
  93 {
  94   if (Size == 0) {
  95     FirstItem = LastItem = CurrentItem = newnode;
  96     CurrentIndex = Size = 1;
  97   }
  98   else {
  99     ((TCollection_SeqNode*)FirstItem)->Previous() = (TCollection_SeqNode*) newnode;
 100     ((TCollection_SeqNode*)newnode)->Next() = (TCollection_SeqNode*)FirstItem;
 101     FirstItem = newnode;
 102     Size++;
 103     CurrentIndex++;
 104   }
 105 }
 106
 107 void TCollection_BaseSequence::PPrepend(TCollection_BaseSequence& Other)
 108 {
 109   if (Other.Size == 0)
 110     return;
 111   if (Size == 0) {
 112     Size         = Other.Size;
 113     FirstItem    = Other.FirstItem;
 114     LastItem     = Other.LastItem;
 115     CurrentIndex = 1;
 116     CurrentItem  =  FirstItem;
 117   }
 118   else {
 119     Size += Other.Size;
 120     if (Other.LastItem) ((TCollection_SeqNode*)Other.LastItem)->Next() = (TCollection_SeqNode*)FirstItem;
 121     ((TCollection_SeqNode*)FirstItem)->Previous() = (TCollection_SeqNode*)Other.LastItem;
 122     FirstItem = Other.FirstItem;
 123     CurrentIndex += Other.Size;
 124   }
 125   Other.Nullify();
 126 }
 127
 128 // ---------------------------------------------------------
 129 // Reverse : Reverse the order of a given sequence
 130 // ---------------------------------------------------------
 131 void TCollection_BaseSequence::Reverse()
 132 {
 133   TCollection_SeqNode* p = (TCollection_SeqNode*) FirstItem;
 134   TCollection_SeqNode* tmp;
 135   while (p) {
 136     tmp = p->Next();
 137     p->Next() = p->Previous();
 138     p->Previous() = tmp;
 139     p = tmp;
 140   }
 141   tmp = (TCollection_SeqNode*)FirstItem;
 142   FirstItem = LastItem;
 143   LastItem = tmp;
 144   if (Size != 0) CurrentIndex = Size + 1 - CurrentIndex;
 145 }
 146
 147
 148 void TCollection_BaseSequence::PInsertAfter(const Standard_Integer Index, const Standard_Address N)
 149 {
 150   if (Index == 0)
 151     PPrepend(N);
 152   else {
 153     TCollection_SeqNode* p = (TCollection_SeqNode*) Find(Index);
 154     TCollection_SeqNode* newnode = (TCollection_SeqNode*) N;
 155     newnode->Next() = p->Next();
 156     newnode->Previous() = p;
 157     if (Index == Size) LastItem = newnode;
 158     else p->Next()->Previous() = newnode;
 159     p->Next() = newnode;
 160     Size++;
 161     if (Index < CurrentIndex) CurrentIndex++;
 162   }
 163 }
 164
 165 // -------------------------------------------------------------------
 166 // InsertAfter : Insert a sequence after a given index in the sequence
 167 // -------------------------------------------------------------------
 168
 169 void TCollection_BaseSequence::PInsertAfter(const Standard_Integer Index, TCollection_BaseSequence& Other)
 170 {
 171   if (Index < 0 || Index > Size) Standard_OutOfRange::Raise();
 172   if (Other.Size == 0) return;
 173   if (Index == 0)
 174     PPrepend( Other );
 175   else {
 176     TCollection_SeqNode* p = (TCollection_SeqNode*) Find(Index);
 177     ((TCollection_SeqNode*)Other.FirstItem)->Previous() = p;
 178     ((TCollection_SeqNode*)Other.LastItem)->Next() = p->Next();
 179     if (Index == Size) LastItem = Other.LastItem;
 180     else p->Next()->Previous() = (TCollection_SeqNode*)Other.LastItem;
 181     p->Next() = (TCollection_SeqNode*)Other.FirstItem;
 182     Size += Other.Size;
 183     if (Index < CurrentIndex) CurrentIndex += Other.Size;
 184     Other.Nullify();
 185   }
 186 }
 187
 188 // ----------------------------------------
 189 // Exchange : Exchange two elements in the sequence
 190 // ----------------------------------------
 191 void TCollection_BaseSequence::Exchange(const Standard_Integer I, const Standard_Integer J)
 192 {
 193    Standard_OutOfRange_Raise_if ( I <= 0 || J <= 0 || I > Size || J > Size,"" ) ;
 194
 195    // Assume I < J
 196    if (I == J) return;
 197    if (J < I) {
 198      Exchange(J,I);
 199      return;
 200    }
 201
 202    TCollection_SeqNode* pi = (TCollection_SeqNode*) Find(I);
 203    TCollection_SeqNode* pj = (TCollection_SeqNode*) Find(J);
 204
 205    // update the node before I
 206    if (pi->Previous())
 207      pi->Previous()->Next() = pj;
 208    else
 209      FirstItem = pj;
 210
 211    // update the node after J
 212    if (pj->Next())
 213      pj->Next()->Previous() = pi;
 214    else
 215      LastItem = pi;
 216
 217    if (pi->Next() == pj) {          // I and J are consecutives, update them
 218      pj->Previous() = pi->Previous();
 219      pi->Previous() = pj;
 220      pi->Next() = pj->Next();
 221      pj->Next() = pi;
 222    }
 223    else {                        // I and J are not consecutive
 224      pi->Next()->Previous() = pj;    // update the node after I
 225      pj->Previous()->Next() = pi;    // update the node before J
 226      TCollection_SeqNode* tmp = pi->Next();       // update nodes I and J
 227      pi->Next() = pj->Next();
 228      pj->Next() = tmp;
 229      tmp = pi->Previous();
 230      pi->Previous() = pj->Previous();
 231      pj->Previous() = tmp;
 232    }
 233
 234    if      (CurrentIndex == I) CurrentItem = pj;
 235    else if (CurrentIndex == J) CurrentItem = pi;
 236 }
 237
 238 void TCollection_BaseSequence::PSplit(const Standard_Integer Index, TCollection_BaseSequence& Sub)
 239 {
 240    Standard_OutOfRange_Raise_if( Index <= 0 || Index > Size,"" );
 241    Standard_DomainError_Raise_if(this == &Sub,"No Split on myself!!");
 242
 243    TCollection_SeqNode* p = (TCollection_SeqNode*) Find(Index);
 244
 245    Sub.LastItem = LastItem;
 246    Sub.Size = Size - Index + 1;
 247
 248    LastItem = p->Previous();
 249    if (LastItem) {
 250      ((TCollection_SeqNode*)LastItem)->Next() = NULL;
 251      Size = Index - 1;
 252      if (CurrentIndex >= Index) {
 253        CurrentIndex = 1;
 254        CurrentItem = (TCollection_SeqNode*) FirstItem;
 255      }
 256    }
 257    else {
 258      FirstItem = CurrentItem = NULL;
 259      Size = CurrentIndex = 0;
 260    }
 261
 262    Sub.FirstItem = Sub.CurrentItem = p;
 263    p->Previous() = NULL;
 264    Sub.CurrentIndex = 1;
 265 }
 266
 267 void TCollection_BaseSequence::Remove(const Standard_Integer Index, const Standard_Address delnode)
 268 {
 269   Standard_OutOfRange_Raise_if(Index <= 0 || Index > Size,"" );
 270
 271   TCollection_SeqNode* p = (TCollection_SeqNode*) Find(Index);
 272   if (p->Previous())
 273     p->Previous()->Next() = p->Next();
 274   else
 275     FirstItem = p->Next();
 276   if (p->Next())
 277     p->Next()->Previous() = p->Previous();
 278   else
 279     LastItem = p->Previous();
 280
 281   Size--;
 282   if      (CurrentIndex > Index) CurrentIndex--;
 283   else if (CurrentIndex == Index) {
 284     if (p->Next())
 285       CurrentItem = p->Next();
 286     else {
 287       CurrentItem = (TCollection_SeqNode*) LastItem;
 288       CurrentIndex = Size;
 289     }
 290   }
 291    ((DelNode)delnode) (p);
 292 }
 293
 294 // ---------------------
 295 // Remove a set of items
 296 // ---------------------
 297 void TCollection_BaseSequence::Remove(const Standard_Integer From, const Standard_Integer To,
 298                                       const Standard_Address delnode)
 299 {
 300   Standard_OutOfRange_Raise_if (From <= 0 || From > Size || To <= 0 || To > Size || From > To,"" );
 301
 302   TCollection_SeqNode* pfrom = (TCollection_SeqNode*) Find(From);
 303   TCollection_SeqNode* pto   = (TCollection_SeqNode*) Find(To);
 304
 305   if (pfrom->Previous())
 306     pfrom->Previous()->Next() = pto->Next();
 307   else
 308     FirstItem = pto->Next();
 309   if (pto->Next())
 310     pto->Next()->Previous() = pfrom->Previous();
 311   else
 312     LastItem = pfrom->Previous();
 313
 314   Size -= To - From + 1;
 315   if      (CurrentIndex > To)
 316     CurrentIndex -= To - From + 1;
 317   else if (CurrentIndex >= From) {
 318     if (pto->Next()) {
 319       CurrentItem = pto->Next();
 320       CurrentIndex = From;                      // AGV fix 24.05.01
 321     } else {
 322       CurrentItem = (TCollection_SeqNode*) LastItem;
 323       CurrentIndex = Size;
 324     }
 325   }
 326
 327   Standard_Integer i;
 328   for (i = From; i <= To; i++) {
 329     pto = pfrom;
 330     pfrom = pfrom->Next();
 331      ((DelNode)delnode) (pto);
 332   }
 333 }
 334
 335 Standard_Address TCollection_BaseSequence::Find(const Standard_Integer Index) const
 336 {
 337   Standard_Integer i;
 338   TCollection_SeqNode* p;
 339   if (Index <= CurrentIndex) {
 340     if (Index < CurrentIndex / 2) {
 341       p = (TCollection_SeqNode*) FirstItem;
 342       for (i = 1; i < Index; i++) p = p->Next();
 343     }
 344     else {
 345       p = (TCollection_SeqNode*) CurrentItem;
 346       for (i = CurrentIndex; i > Index; i--) p = p->Previous();
 347     }
 348   }
 349   else {
 350     if (Index < (CurrentIndex + Size) / 2) {
 351       p = (TCollection_SeqNode*) CurrentItem;
 352       for (i = CurrentIndex; i < Index; i++) p = p->Next();
 353     }
 354     else {
 355       p = (TCollection_SeqNode*) LastItem;
 356       for (i = Size; i > Index; i--) p = p->Previous();
 357     }
 358   }
 359   return p;
 360 }
 361
 362 //=======================================================================
 363 //function : Nullify
 364 //purpose  :
 365 //=======================================================================
 366
 367 void TCollection_BaseSequence::Nullify()
 368 {
 369   FirstItem = LastItem = CurrentItem = NULL;
 370   CurrentIndex = Size = 0;
 371 }