0024171: Eliminate CLang compiler warning -Wreorder
[occt.git] / src / NCollection / NCollection_BaseSequence.cxx
1 // Created on: 2002-03-29
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2002-2012 OPEN CASCADE SAS
4 //
5 // The content of this file is subject to the Open CASCADE Technology Public
6 // License Version 6.5 (the "License"). You may not use the content of this file
7 // except in compliance with the License. Please obtain a copy of the License
8 // at http://www.opencascade.org and read it completely before using this file.
9 //
10 // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its
11 // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France.
12 //
13 // The Original Code and all software distributed under the License is
14 // distributed on an "AS IS" basis, without warranty of any kind, and the
15 // Initial Developer hereby disclaims all such warranties, including without
16 // limitation, any warranties of merchantability, fitness for a particular
17 // purpose or non-infringement. Please see the License for the specific terms
18 // and conditions governing the rights and limitations under the License.
19
20 // Purpose:   Implementation of the BaseSequence class
21
22 #include <NCollection_BaseSequence.hxx>
23 #include <Standard_NoSuchObject.hxx>
24 #include <Standard_OutOfRange.hxx>
25 #include <Standard_DomainError.hxx>
26
27 //=======================================================================
28 //function : ClearSeq
29 //purpose  : removes all items from the current sequence
30 //=======================================================================
31
32 void NCollection_BaseSequence::ClearSeq 
33   (NCollection_DelSeqNode fDel, Handle(NCollection_BaseAllocator)& theAl)
34 {
35   const NCollection_SeqNode * p = myFirstItem;
36   NCollection_SeqNode * q;
37   while (p) {
38     q = (NCollection_SeqNode *) p;
39     p = p->Next();
40     fDel (q, theAl);
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     ((NCollection_SeqNode *) 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 (mySize == 0) {
72     mySize         = Other.mySize;
73     myFirstItem    = Other.myFirstItem;
74     myLastItem     = Other.myLastItem;
75     myCurrentItem  = myFirstItem;
76     myCurrentIndex = 1;
77   } else {
78     mySize += Other.mySize;
79     ((NCollection_SeqNode *) myLastItem)->SetNext(Other.myFirstItem);
80     if (Other.myFirstItem) {
81       ((NCollection_SeqNode *) Other.myFirstItem)->SetPrevious(myLastItem);
82       myLastItem = Other.myLastItem;
83     }
84   }
85   Other.Nullify();
86 }
87
88 //=======================================================================
89 //function : PPrepend
90 //purpose  : prepend an item to sequence
91 //=======================================================================
92
93 void NCollection_BaseSequence::PPrepend (NCollection_SeqNode * theItem)
94 {
95   if (mySize == 0) {
96     myFirstItem = myLastItem = myCurrentItem = theItem;
97     myCurrentIndex = mySize = 1;
98   } else {
99     ((NCollection_SeqNode *) myFirstItem)->SetPrevious (theItem);
100     ((NCollection_SeqNode *) theItem)->SetNext (myFirstItem); 
101     theItem->SetPrevious(NULL);
102     theItem->SetNext(myFirstItem);
103     myFirstItem = theItem;
104     ++ mySize;
105     ++ myCurrentIndex;
106   }
107 }
108
109 //=======================================================================
110 //function : PPrepend
111 //purpose  : push a sequence in the beginning of the sequence
112 //=======================================================================
113
114 void NCollection_BaseSequence::PPrepend (NCollection_BaseSequence& Other)
115 {
116   if (mySize == 0) {
117     mySize         = Other.mySize;
118     myFirstItem    = Other.myFirstItem;
119     myLastItem     = Other.myLastItem;
120     myCurrentIndex = 1;
121     myCurrentItem  = myFirstItem;
122   } else {
123     mySize += Other.mySize;
124     if (Other.myLastItem)
125       ((NCollection_SeqNode *) Other.myLastItem)->SetNext (myFirstItem);
126     ((NCollection_SeqNode *) myFirstItem)->SetPrevious(Other.myLastItem);
127     myFirstItem = Other.myFirstItem;
128     myCurrentIndex += Other.mySize;
129   }
130   Other.Nullify();
131 }
132
133 //=======================================================================
134 //function : PReverse
135 //purpose  : reverse the order of a given sequence
136 //=======================================================================
137
138 void NCollection_BaseSequence::PReverse()
139 {
140   const NCollection_SeqNode * p = myFirstItem;
141   const NCollection_SeqNode * tmp;
142   while (p) {
143     tmp = p->Next();
144     ((NCollection_SeqNode *) p)->SetNext (p->Previous());
145     ((NCollection_SeqNode *) p)->SetPrevious (tmp);
146     p = tmp;
147   }
148   tmp = myFirstItem;
149   myFirstItem = myLastItem;
150   myLastItem = tmp;
151   if (mySize != 0) myCurrentIndex = mySize + 1 - myCurrentIndex;
152 }
153
154
155 //=======================================================================
156 //function : PInsertAfter
157 //purpose  : 
158 //=======================================================================
159
160 void NCollection_BaseSequence::PInsertAfter
161                              (NCollection_BaseSequence::Iterator& thePosition,
162                               NCollection_SeqNode                 * theItem)
163 {
164   NCollection_SeqNode * aPos = thePosition.myCurrent;
165   if (aPos == NULL)
166     PPrepend (theItem);
167   else {
168     theItem->SetNext (aPos->Next());
169     theItem->SetPrevious (aPos);
170     if (aPos->Next() == NULL) myLastItem = theItem;
171     else ((NCollection_SeqNode *) aPos->Next())->SetPrevious(theItem);
172     aPos->SetNext(theItem);
173     ++ mySize;
174     myCurrentItem = myFirstItem;
175     myCurrentIndex = 1;
176   }
177 }
178
179 //=======================================================================
180 //function : PInsertAfter
181 //purpose  : 
182 //=======================================================================
183
184 void NCollection_BaseSequence::PInsertAfter(const Standard_Integer theIndex,
185                                             NCollection_SeqNode * theItem)
186 {
187   if (theIndex == 0)
188     PPrepend (theItem);
189   else {
190     const NCollection_SeqNode * p = Find (theIndex);
191     theItem->SetNext(p->Next());
192     theItem->SetPrevious(p);
193     if (theIndex == mySize) myLastItem = theItem;
194     else ((NCollection_SeqNode *) p->Next())->SetPrevious(theItem);
195     ((NCollection_SeqNode *) p)->SetNext(theItem);
196     ++ mySize;
197     if (theIndex < myCurrentIndex)
198       ++ myCurrentIndex;
199   }
200 }
201
202 //=======================================================================
203 //function : PInsertAfter
204 //purpose  : insert a sequence after a given index in the sequence
205 //=======================================================================
206
207 void NCollection_BaseSequence::PInsertAfter (const Standard_Integer theIndex,
208                                              NCollection_BaseSequence& Other)
209 {
210   if (theIndex < 0 || theIndex > mySize)
211     Standard_OutOfRange::Raise();
212   if (Other.mySize != 0) {
213     if (theIndex == 0) 
214       PPrepend (Other);
215     else {
216       const NCollection_SeqNode * p = Find (theIndex);
217       ((NCollection_SeqNode *) Other.myFirstItem)->SetPrevious (p);
218       ((NCollection_SeqNode *) Other.myLastItem)->SetNext (p->Next());
219       if (theIndex == mySize)
220         myLastItem = Other.myLastItem;
221       else
222         ((NCollection_SeqNode *) p->Next())->SetPrevious (Other.myLastItem);
223       ((NCollection_SeqNode *) p)->SetNext (Other.myFirstItem);
224       mySize += Other.mySize;
225       if (theIndex < myCurrentIndex)
226         myCurrentIndex += Other.mySize;
227       Other.Nullify();
228     }
229   }
230 }
231
232 //=======================================================================
233 //function : PExchange
234 //purpose  : exchange two elements in the sequence
235 //=======================================================================
236
237 void NCollection_BaseSequence::PExchange (const Standard_Integer I,
238                                           const Standard_Integer J)
239 {
240   Standard_OutOfRange_Raise_if (I <= 0 || J <= 0 || I > mySize || J > mySize,
241                                 "" );
242
243   // Assume I < J
244   if (J < I)
245     PExchange(J,I);
246   else if (I < J) {
247     const NCollection_SeqNode * pi = Find(I);
248     const NCollection_SeqNode * pj = Find(J);
249
250     // update the node before I
251     if (pi->Previous())
252       ((NCollection_SeqNode *) pi->Previous())->SetNext (pj);
253     else 
254       myFirstItem = pj;
255
256     // update the node after J
257     if (pj->Next())
258       ((NCollection_SeqNode *) pj->Next())->SetPrevious(pi);
259     else
260       myLastItem = pi;
261
262     if (pi->Next() == pj) {          // I and J are consecutives, update them
263       ((NCollection_SeqNode *) pj)->SetPrevious (pi->Previous());
264       ((NCollection_SeqNode *) pi)->SetPrevious (pj);
265       ((NCollection_SeqNode *) pi)->SetNext (pj->Next());
266       ((NCollection_SeqNode *) pj)->SetNext (pi);
267     }
268     else {                        // I and J are not consecutive
269       // update the node after I
270       ((NCollection_SeqNode *) pi->Next())->SetPrevious (pj);
271       // update the node before J
272       ((NCollection_SeqNode *) pj->Previous())->SetNext (pi);
273       // update nodes I and J
274       const NCollection_SeqNode* tmp = pi->Next();       
275       ((NCollection_SeqNode *) pi)->SetNext (pj->Next());
276       ((NCollection_SeqNode *) pj)->SetNext (tmp);
277       tmp = pi->Previous();
278       ((NCollection_SeqNode *) pi)->SetPrevious (pj->Previous());
279       ((NCollection_SeqNode *) pj)->SetPrevious (tmp);
280     }
281
282     if      (myCurrentIndex == I) myCurrentItem = pj;
283     else if (myCurrentIndex == J) myCurrentItem = pi;
284   }
285 }
286
287 //=======================================================================
288 //function : PSplit
289 //purpose  : 
290 //=======================================================================
291
292 void NCollection_BaseSequence::PSplit (const Standard_Integer theIndex,
293                                        NCollection_BaseSequence& Sub)
294 {
295   Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize,"" );
296   Standard_DomainError_Raise_if (this == &Sub, "No Split on myself!!");
297
298   const NCollection_SeqNode * p = Find (theIndex);
299
300   Sub.myLastItem = myLastItem;
301   Sub.mySize = mySize - theIndex + 1;
302
303   myLastItem = p->Previous();
304   if (myLastItem) {
305     ((NCollection_SeqNode *) myLastItem)->SetNext(NULL);
306     mySize = theIndex - 1;
307     if (myCurrentIndex >= theIndex) {
308       myCurrentIndex = 1;
309       myCurrentItem  = myFirstItem;
310     }
311   } else {
312     myFirstItem = myCurrentItem = NULL;
313     mySize = myCurrentIndex = 0;
314   }
315
316   Sub.myFirstItem = Sub.myCurrentItem = p;
317   ((NCollection_SeqNode *) p)->SetPrevious (NULL);
318   Sub.myCurrentIndex = 1;
319 }
320
321 //=======================================================================
322 //function : Remove
323 //purpose  : 
324 //=======================================================================
325
326 void NCollection_BaseSequence::RemoveSeq 
327                               (NCollection_BaseSequence::Iterator& thePosition,
328                                NCollection_DelSeqNode              fDel, 
329                                Handle(NCollection_BaseAllocator)&  theAl)
330 {
331   NCollection_SeqNode * aPos = thePosition.myCurrent;
332   if (aPos == NULL)
333     return;
334   thePosition.myCurrent = (NCollection_SeqNode *) aPos -> Next();
335
336   if (aPos->Previous())
337     ((NCollection_SeqNode *) aPos->Previous())->SetNext (aPos->Next());
338   else
339     myFirstItem = aPos->Next();
340
341   if (aPos->Next())
342     ((NCollection_SeqNode *) aPos->Next())->SetPrevious (aPos->Previous());
343   else
344     myLastItem = aPos->Previous();
345
346   -- mySize;
347   myCurrentItem  = myLastItem;
348   myCurrentIndex = mySize;
349
350   fDel (aPos, theAl);
351 }
352
353 //=======================================================================
354 //function : Remove
355 //purpose  : 
356 //=======================================================================
357
358 void NCollection_BaseSequence::RemoveSeq 
359                               (const Standard_Integer theIndex,
360                                NCollection_DelSeqNode fDel, 
361                                Handle(NCollection_BaseAllocator)& theAl)
362 {
363   Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize, "");
364   
365   const NCollection_SeqNode * p = Find (theIndex);
366   if (p->Previous())
367     ((NCollection_SeqNode *) p->Previous())->SetNext (p->Next());
368   else
369     myFirstItem = p->Next();
370   if (p->Next())
371     ((NCollection_SeqNode *) p->Next())->SetPrevious (p->Previous());
372   else
373     myLastItem = p->Previous();
374
375   -- mySize;
376   if      (myCurrentIndex > theIndex) -- myCurrentIndex;
377   else if (myCurrentIndex == theIndex) {
378     if (p->Next()) 
379       myCurrentItem = p->Next();
380     else {
381       myCurrentItem = myLastItem;
382       myCurrentIndex = mySize;
383     }
384   }
385   fDel ((NCollection_SeqNode *) p, theAl);
386 }
387
388 //=======================================================================
389 //function : Remove
390 //purpose  : remove a set of items
391 //=======================================================================
392
393 void NCollection_BaseSequence::RemoveSeq 
394                               (const Standard_Integer From,
395                                const Standard_Integer To, 
396                                NCollection_DelSeqNode fDel,
397                                Handle(NCollection_BaseAllocator)& theAl)
398 {
399   Standard_OutOfRange_Raise_if (From <= 0 || To > mySize || From > To, "");
400
401   const NCollection_SeqNode * pfrom = Find(From);
402   const NCollection_SeqNode * pto   = Find(To);
403   
404   if (pfrom->Previous())
405     ((NCollection_SeqNode *) pfrom->Previous())->SetNext (pto->Next());
406   else
407     myFirstItem = pto->Next();
408   if (pto->Next())
409     ((NCollection_SeqNode *) pto->Next())->SetPrevious (pfrom->Previous());
410   else
411     myLastItem = pfrom->Previous();
412   
413   mySize -= To - From + 1;
414   if      (myCurrentIndex > To) 
415     myCurrentIndex -= To - From + 1;
416   else if (myCurrentIndex >= From) {
417     if (pto->Next()) {
418       myCurrentItem = pto->Next();
419       myCurrentIndex = From;                      // AGV fix 24.05.01
420     } else {
421       myCurrentItem = myLastItem;
422       myCurrentIndex = mySize;
423     }
424   }
425   
426   for (Standard_Integer i = From; i <= To; i++) {
427     NCollection_SeqNode * tmp = (NCollection_SeqNode *)pfrom;
428     pfrom = pfrom->Next();
429     fDel (tmp, theAl);
430   }
431 }
432
433 //=======================================================================
434 //function : Find
435 //purpose  : 
436 //=======================================================================
437
438 const NCollection_SeqNode * NCollection_BaseSequence::Find
439                                         (const Standard_Integer theIndex) const 
440 {
441   Standard_Integer i;
442   const NCollection_SeqNode * p;
443   if (theIndex <= myCurrentIndex) {
444     if (theIndex < myCurrentIndex / 2) {
445       p = myFirstItem;
446       for (i = 1; i < theIndex; i++) p = p->Next();
447     } else {
448       p = myCurrentItem;
449       for (i = myCurrentIndex; i > theIndex; i--) p = p->Previous();
450     }
451   } else {
452     if (theIndex < (myCurrentIndex + mySize) / 2) {
453       p = myCurrentItem;
454       for (i = myCurrentIndex; i < theIndex; i++) p = p->Next();
455     } else {
456       p = myLastItem;
457       for (i = mySize; i > theIndex; i--) p = p->Previous();
458     }
459   }
460   return p;
461 }