0024911: Avoid using virtual functions in NCollection classes
[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 (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     myLastItem->SetNext(Other.myFirstItem);
80     if (Other.myFirstItem) {
81       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     myFirstItem->SetPrevious (theItem);
100     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       Other.myLastItem->SetNext (myFirstItem);
126     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   NCollection_SeqNode* p = myFirstItem;
141   while (p) {
142     NCollection_SeqNode* tmp = p->Next();
143     p->SetNext (p->Previous());
144     p->SetPrevious (tmp);
145     p = tmp;
146   }
147   NCollection_SeqNode* tmp = myFirstItem;
148   myFirstItem = myLastItem;
149   myLastItem = tmp;
150   if (mySize != 0)
151     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)
171       myLastItem = theItem;
172     else
173       aPos->Next()->SetPrevious(theItem);
174     aPos->SetNext(theItem);
175     ++ mySize;
176     myCurrentItem = myFirstItem;
177     myCurrentIndex = 1;
178   }
179 }
180
181 //=======================================================================
182 //function : PInsertAfter
183 //purpose  : 
184 //=======================================================================
185
186 void NCollection_BaseSequence::PInsertAfter(const Standard_Integer theIndex,
187                                             NCollection_SeqNode * theItem)
188 {
189   if (theIndex == 0)
190     PPrepend (theItem);
191   else {
192     NCollection_SeqNode * p = Find (theIndex);
193     theItem->SetNext(p->Next());
194     theItem->SetPrevious(p);
195     if (theIndex == mySize)
196       myLastItem = theItem;
197     else
198       p->Next()->SetPrevious(theItem);
199     p->SetNext(theItem);
200     ++ mySize;
201     if (theIndex < myCurrentIndex)
202       ++ myCurrentIndex;
203   }
204 }
205
206 //=======================================================================
207 //function : PInsertAfter
208 //purpose  : insert a sequence after a given index in the sequence
209 //=======================================================================
210
211 void NCollection_BaseSequence::PInsertAfter (const Standard_Integer theIndex,
212                                              NCollection_BaseSequence& Other)
213 {
214   if (theIndex < 0 || theIndex > mySize)
215     Standard_OutOfRange::Raise();
216   if (Other.mySize != 0) {
217     if (theIndex == 0) 
218       PPrepend (Other);
219     else {
220       NCollection_SeqNode * p = Find (theIndex);
221       Other.myFirstItem->SetPrevious (p);
222       Other.myLastItem->SetNext (p->Next());
223       if (theIndex == mySize)
224         myLastItem = Other.myLastItem;
225       else
226         p->Next()->SetPrevious (Other.myLastItem);
227       p->SetNext (Other.myFirstItem);
228       mySize += Other.mySize;
229       if (theIndex < myCurrentIndex)
230         myCurrentIndex += Other.mySize;
231       Other.Nullify();
232     }
233   }
234 }
235
236 //=======================================================================
237 //function : PExchange
238 //purpose  : exchange two elements in the sequence
239 //=======================================================================
240
241 void NCollection_BaseSequence::PExchange (const Standard_Integer I,
242                                           const Standard_Integer J)
243 {
244   Standard_OutOfRange_Raise_if (I <= 0 || J <= 0 || I > mySize || J > mySize,
245                                 "" );
246
247   // Assume I < J
248   if (J < I)
249     PExchange(J,I);
250   else if (I < J) {
251     NCollection_SeqNode * pi = Find(I);
252     NCollection_SeqNode * pj = Find(J);
253
254     // update the node before I
255     if (pi->Previous())
256       pi->Previous()->SetNext (pj);
257     else 
258       myFirstItem = pj;
259
260     // update the node after J
261     if (pj->Next())
262       pj->Next()->SetPrevious(pi);
263     else
264       myLastItem = pi;
265
266     if (pi->Next() == pj) {          // I and J are consecutives, update them
267       pj->SetPrevious (pi->Previous());
268       pi->SetPrevious (pj);
269       pi->SetNext (pj->Next());
270       pj->SetNext (pi);
271     }
272     else {                        // I and J are not consecutive
273       // update the node after I
274       pi->Next()->SetPrevious (pj);
275       // update the node before J
276       pj->Previous()->SetNext (pi);
277       // update nodes I and J
278       NCollection_SeqNode* tmp = pi->Next();       
279       pi->SetNext (pj->Next());
280       pj->SetNext (tmp);
281       tmp = pi->Previous();
282       pi->SetPrevious (pj->Previous());
283       pj->SetPrevious (tmp);
284     }
285
286     if      (myCurrentIndex == I) myCurrentItem = pj;
287     else if (myCurrentIndex == J) myCurrentItem = pi;
288   }
289 }
290
291 //=======================================================================
292 //function : PSplit
293 //purpose  : 
294 //=======================================================================
295
296 void NCollection_BaseSequence::PSplit (const Standard_Integer theIndex,
297                                        NCollection_BaseSequence& Sub)
298 {
299   Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize,"" );
300   Standard_DomainError_Raise_if (this == &Sub, "No Split on myself!!");
301
302   NCollection_SeqNode * p = Find (theIndex);
303
304   Sub.myLastItem = myLastItem;
305   Sub.mySize = mySize - theIndex + 1;
306
307   myLastItem = p->Previous();
308   if (myLastItem) {
309     myLastItem->SetNext(NULL);
310     mySize = theIndex - 1;
311     if (myCurrentIndex >= theIndex) {
312       myCurrentIndex = 1;
313       myCurrentItem  = myFirstItem;
314     }
315   } else {
316     myFirstItem = myCurrentItem = NULL;
317     mySize = myCurrentIndex = 0;
318   }
319
320   Sub.myFirstItem = Sub.myCurrentItem = p;
321   p->SetPrevious (NULL);
322   Sub.myCurrentIndex = 1;
323 }
324
325 //=======================================================================
326 //function : Remove
327 //purpose  : 
328 //=======================================================================
329
330 void NCollection_BaseSequence::RemoveSeq 
331                               (NCollection_BaseSequence::Iterator& thePosition,
332                                NCollection_DelSeqNode              fDel)
333 {
334   NCollection_SeqNode * aPos = thePosition.myCurrent;
335   if (aPos == NULL)
336     return;
337   thePosition.myCurrent = aPos -> Next();
338
339   if (aPos->Previous())
340     aPos->Previous()->SetNext (aPos->Next());
341   else
342     myFirstItem = aPos->Next();
343
344   if (aPos->Next())
345     aPos->Next()->SetPrevious (aPos->Previous());
346   else
347     myLastItem = aPos->Previous();
348
349   -- mySize;
350   myCurrentItem  = myLastItem;
351   myCurrentIndex = mySize;
352
353   fDel (aPos, myAllocator);
354 }
355
356 //=======================================================================
357 //function : Remove
358 //purpose  : 
359 //=======================================================================
360
361 void NCollection_BaseSequence::RemoveSeq (const Standard_Integer theIndex,
362                                           NCollection_DelSeqNode fDel)
363 {
364   Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize, "");
365   
366   NCollection_SeqNode * p = Find (theIndex);
367   if (p->Previous())
368     p->Previous()->SetNext (p->Next());
369   else
370     myFirstItem = p->Next();
371   if (p->Next())
372     p->Next()->SetPrevious (p->Previous());
373   else
374     myLastItem = p->Previous();
375
376   -- mySize;
377   if      (myCurrentIndex > theIndex) -- myCurrentIndex;
378   else if (myCurrentIndex == theIndex) {
379     if (p->Next()) 
380       myCurrentItem = p->Next();
381     else {
382       myCurrentItem = myLastItem;
383       myCurrentIndex = mySize;
384     }
385   }
386   fDel (p, myAllocator);
387 }
388
389 //=======================================================================
390 //function : Remove
391 //purpose  : remove a set of items
392 //=======================================================================
393
394 void NCollection_BaseSequence::RemoveSeq (const Standard_Integer From,
395                                           const Standard_Integer To, 
396                                           NCollection_DelSeqNode fDel)
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, myAllocator);
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 }