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