0026937: Eliminate NO_CXX_EXCEPTION macro support
[occt.git] / 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   
370   NCollection_SeqNode * p = Find (theIndex);
371   if (p->Previous())
372     p->Previous()->SetNext (p->Next());
373   else
374     myFirstItem = p->Next();
375   if (p->Next())
376     p->Next()->SetPrevious (p->Previous());
377   else
378     myLastItem = p->Previous();
379
380   -- mySize;
381   if      (myCurrentIndex > theIndex) -- myCurrentIndex;
382   else if (myCurrentIndex == theIndex) {
383     if (p->Next()) 
384       myCurrentItem = p->Next();
385     else {
386       myCurrentItem = myLastItem;
387       myCurrentIndex = mySize;
388     }
389   }
390   fDel (p, myAllocator);
391 }
392
393 //=======================================================================
394 //function : Remove
395 //purpose  : remove a set of items
396 //=======================================================================
397
398 void NCollection_BaseSequence::RemoveSeq (const Standard_Integer From,
399                                           const Standard_Integer To, 
400                                           NCollection_DelSeqNode fDel)
401 {
402   Standard_OutOfRange_Raise_if (From <= 0 || To > mySize || From > To, "");
403
404   NCollection_SeqNode * pfrom = Find(From);
405   NCollection_SeqNode * pto   = Find(To);
406   
407   if (pfrom->Previous())
408     pfrom->Previous()->SetNext (pto->Next());
409   else
410     myFirstItem = pto->Next();
411   if (pto->Next())
412     pto->Next()->SetPrevious (pfrom->Previous());
413   else
414     myLastItem = pfrom->Previous();
415   
416   mySize -= To - From + 1;
417   if      (myCurrentIndex > To) 
418     myCurrentIndex -= To - From + 1;
419   else if (myCurrentIndex >= From) {
420     if (pto->Next()) {
421       myCurrentItem = pto->Next();
422       myCurrentIndex = From;                      // AGV fix 24.05.01
423     } else {
424       myCurrentItem = myLastItem;
425       myCurrentIndex = mySize;
426     }
427   }
428   
429   for (Standard_Integer i = From; i <= To; i++) {
430     NCollection_SeqNode * tmp = pfrom;
431     pfrom = pfrom->Next();
432     fDel (tmp, myAllocator);
433   }
434 }
435
436 //=======================================================================
437 //function : Find
438 //purpose  : 
439 //=======================================================================
440
441 NCollection_SeqNode * NCollection_BaseSequence::Find (const Standard_Integer theIndex) const 
442 {
443   Standard_Integer i;
444   NCollection_SeqNode * p;
445   if (theIndex <= myCurrentIndex) {
446     if (theIndex < myCurrentIndex / 2) {
447       p = myFirstItem;
448       for (i = 1; i < theIndex; i++)
449         p = p->Next();
450     } else {
451       p = myCurrentItem;
452       for (i = myCurrentIndex; i > theIndex; i--)
453         p = p->Previous();
454     }
455   } else {
456     if (theIndex < (myCurrentIndex + mySize) / 2) {
457       p = myCurrentItem;
458       for (i = myCurrentIndex; i < theIndex; i++)
459         p = p->Next();
460     } else {
461       p = myLastItem;
462       for (i = mySize; i > theIndex; i--)
463         p = p->Previous();
464     }
465   }
466   return p;
467 }