1 // Created on: 2002-03-29
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2002-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 // Purpose: Implementation of the BaseSequence class
18 #include <NCollection_BaseSequence.hxx>
19 #include <Standard_NoSuchObject.hxx>
20 #include <Standard_OutOfRange.hxx>
21 #include <Standard_DomainError.hxx>
23 inline void NCollection_BaseSequence::Nullify ()
25 myFirstItem = myLastItem = myCurrentItem = NULL;
26 myCurrentIndex = mySize = 0;
29 //=======================================================================
31 //purpose : removes all items from the current sequence
32 //=======================================================================
34 void NCollection_BaseSequence::ClearSeq (NCollection_DelSeqNode fDel)
36 NCollection_SeqNode* p = myFirstItem;
38 NCollection_SeqNode* q = p;
40 fDel (q, myAllocator);
45 //=======================================================================
47 //purpose : append an item to sequence
48 //=======================================================================
50 void NCollection_BaseSequence::PAppend (NCollection_SeqNode * theItem)
53 myFirstItem = myLastItem = myCurrentItem = theItem;
54 myCurrentIndex = mySize = 1;
56 myLastItem->SetNext(theItem);
57 theItem->SetPrevious(myLastItem);
58 theItem->SetNext(NULL);
64 //=======================================================================
66 //purpose : push a sequence at the end of the sequence
67 //=======================================================================
69 void NCollection_BaseSequence::PAppend(NCollection_BaseSequence& Other)
71 if (Other.mySize == 0)
74 mySize = Other.mySize;
75 myFirstItem = Other.myFirstItem;
76 myLastItem = Other.myLastItem;
77 myCurrentItem = myFirstItem;
80 mySize += Other.mySize;
81 myLastItem->SetNext(Other.myFirstItem);
82 if (Other.myFirstItem) {
83 Other.myFirstItem->SetPrevious(myLastItem);
84 myLastItem = Other.myLastItem;
90 //=======================================================================
92 //purpose : prepend an item to sequence
93 //=======================================================================
95 void NCollection_BaseSequence::PPrepend (NCollection_SeqNode * theItem)
98 myFirstItem = myLastItem = myCurrentItem = theItem;
99 myCurrentIndex = mySize = 1;
101 myFirstItem->SetPrevious (theItem);
102 theItem->SetNext (myFirstItem);
103 theItem->SetPrevious(NULL);
104 theItem->SetNext(myFirstItem);
105 myFirstItem = theItem;
111 //=======================================================================
112 //function : PPrepend
113 //purpose : push a sequence in the beginning of the sequence
114 //=======================================================================
116 void NCollection_BaseSequence::PPrepend (NCollection_BaseSequence& Other)
118 if (Other.mySize == 0)
121 mySize = Other.mySize;
122 myFirstItem = Other.myFirstItem;
123 myLastItem = Other.myLastItem;
125 myCurrentItem = myFirstItem;
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;
137 //=======================================================================
138 //function : PReverse
139 //purpose : reverse the order of a given sequence
140 //=======================================================================
142 void NCollection_BaseSequence::PReverse()
144 NCollection_SeqNode* p = myFirstItem;
146 NCollection_SeqNode* tmp = p->Next();
147 p->SetNext (p->Previous());
148 p->SetPrevious (tmp);
151 NCollection_SeqNode* tmp = myFirstItem;
152 myFirstItem = myLastItem;
155 myCurrentIndex = mySize + 1 - myCurrentIndex;
159 //=======================================================================
160 //function : PInsertAfter
162 //=======================================================================
164 void NCollection_BaseSequence::PInsertAfter
165 (NCollection_BaseSequence::Iterator& thePosition,
166 NCollection_SeqNode * theItem)
168 NCollection_SeqNode * aPos = thePosition.myCurrent;
172 theItem->SetNext (aPos->Next());
173 theItem->SetPrevious (aPos);
174 if (aPos->Next() == NULL)
175 myLastItem = theItem;
177 aPos->Next()->SetPrevious(theItem);
178 aPos->SetNext(theItem);
180 myCurrentItem = myFirstItem;
185 //=======================================================================
186 //function : PInsertAfter
188 //=======================================================================
190 void NCollection_BaseSequence::PInsertAfter(const Standard_Integer theIndex,
191 NCollection_SeqNode * theItem)
196 NCollection_SeqNode * p = Find (theIndex);
197 theItem->SetNext(p->Next());
198 theItem->SetPrevious(p);
199 if (theIndex == mySize)
200 myLastItem = theItem;
202 p->Next()->SetPrevious(theItem);
205 if (theIndex < myCurrentIndex)
210 //=======================================================================
211 //function : PInsertAfter
212 //purpose : insert a sequence after a given index in the sequence
213 //=======================================================================
215 void NCollection_BaseSequence::PInsertAfter (const Standard_Integer theIndex,
216 NCollection_BaseSequence& Other)
218 if (theIndex < 0 || theIndex > mySize)
219 throw Standard_OutOfRange();
220 if (Other.mySize != 0) {
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;
230 p->Next()->SetPrevious (Other.myLastItem);
231 p->SetNext (Other.myFirstItem);
232 mySize += Other.mySize;
233 if (theIndex < myCurrentIndex)
234 myCurrentIndex += Other.mySize;
240 //=======================================================================
241 //function : PExchange
242 //purpose : exchange two elements in the sequence
243 //=======================================================================
245 void NCollection_BaseSequence::PExchange (const Standard_Integer I,
246 const Standard_Integer J)
248 Standard_OutOfRange_Raise_if (I <= 0 || J <= 0 || I > mySize || J > mySize,
255 NCollection_SeqNode * pi = Find(I);
256 NCollection_SeqNode * pj = Find(J);
258 // update the node before I
260 pi->Previous()->SetNext (pj);
264 // update the node after J
266 pj->Next()->SetPrevious(pi);
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());
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());
285 tmp = pi->Previous();
286 pi->SetPrevious (pj->Previous());
287 pj->SetPrevious (tmp);
290 if (myCurrentIndex == I) myCurrentItem = pj;
291 else if (myCurrentIndex == J) myCurrentItem = pi;
295 //=======================================================================
298 //=======================================================================
300 void NCollection_BaseSequence::PSplit (const Standard_Integer theIndex,
301 NCollection_BaseSequence& Sub)
303 Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize,"" );
304 Standard_DomainError_Raise_if (this == &Sub, "No Split on myself!!");
306 NCollection_SeqNode * p = Find (theIndex);
308 Sub.myLastItem = myLastItem;
309 Sub.mySize = mySize - theIndex + 1;
311 myLastItem = p->Previous();
313 myLastItem->SetNext(NULL);
314 mySize = theIndex - 1;
315 if (myCurrentIndex >= theIndex) {
317 myCurrentItem = myFirstItem;
320 myFirstItem = myCurrentItem = NULL;
321 mySize = myCurrentIndex = 0;
324 Sub.myFirstItem = Sub.myCurrentItem = p;
325 p->SetPrevious (NULL);
326 Sub.myCurrentIndex = 1;
329 //=======================================================================
332 //=======================================================================
334 void NCollection_BaseSequence::RemoveSeq
335 (NCollection_BaseSequence::Iterator& thePosition,
336 NCollection_DelSeqNode fDel)
338 NCollection_SeqNode * aPos = thePosition.myCurrent;
341 thePosition.myCurrent = aPos -> Next();
343 if (aPos->Previous())
344 aPos->Previous()->SetNext (aPos->Next());
346 myFirstItem = aPos->Next();
349 aPos->Next()->SetPrevious (aPos->Previous());
351 myLastItem = aPos->Previous();
354 myCurrentItem = myLastItem;
355 myCurrentIndex = mySize;
357 fDel (aPos, myAllocator);
360 //=======================================================================
363 //=======================================================================
365 void NCollection_BaseSequence::RemoveSeq (const Standard_Integer theIndex,
366 NCollection_DelSeqNode fDel)
368 Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize,
369 "NCollection_BaseSequence::RemoveSeq() - index is out of range");
371 NCollection_SeqNode * p = Find (theIndex);
373 p->Previous()->SetNext (p->Next());
375 myFirstItem = p->Next();
377 p->Next()->SetPrevious (p->Previous());
379 myLastItem = p->Previous();
382 if (myCurrentIndex > theIndex) -- myCurrentIndex;
383 else if (myCurrentIndex == theIndex) {
385 myCurrentItem = p->Next();
387 myCurrentItem = myLastItem;
388 myCurrentIndex = mySize;
391 fDel (p, myAllocator);
394 //=======================================================================
396 //purpose : remove a set of items
397 //=======================================================================
399 void NCollection_BaseSequence::RemoveSeq (const Standard_Integer From,
400 const Standard_Integer To,
401 NCollection_DelSeqNode fDel)
403 Standard_OutOfRange_Raise_if (From <= 0 || To > mySize || From > To,
404 "NCollection_BaseSequence::RemoveSeq() - invalid input range");
406 NCollection_SeqNode * pfrom = Find(From);
407 NCollection_SeqNode * pto = Find(To);
409 if (pfrom->Previous())
410 pfrom->Previous()->SetNext (pto->Next());
412 myFirstItem = pto->Next();
414 pto->Next()->SetPrevious (pfrom->Previous());
416 myLastItem = pfrom->Previous();
418 mySize -= To - From + 1;
419 if (myCurrentIndex > To)
420 myCurrentIndex -= To - From + 1;
421 else if (myCurrentIndex >= From) {
423 myCurrentItem = pto->Next();
424 myCurrentIndex = From; // AGV fix 24.05.01
426 myCurrentItem = myLastItem;
427 myCurrentIndex = mySize;
431 for (Standard_Integer i = From; i <= To; i++) {
432 NCollection_SeqNode * tmp = pfrom;
433 pfrom = pfrom->Next();
434 fDel (tmp, myAllocator);
438 //=======================================================================
441 //=======================================================================
443 NCollection_SeqNode * NCollection_BaseSequence::Find (const Standard_Integer theIndex) const
446 NCollection_SeqNode * p;
447 if (theIndex <= myCurrentIndex) {
448 if (theIndex < myCurrentIndex / 2) {
450 for (i = 1; i < theIndex; i++)
454 for (i = myCurrentIndex; i > theIndex; i--)
458 if (theIndex < (myCurrentIndex + mySize) / 2) {
460 for (i = myCurrentIndex; i < theIndex; i++)
464 for (i = mySize; i > theIndex; i--)