b311480e |
1 | // Created on: 2002-03-29 |
2 | // Created by: Alexander GRIGORIEV |
973c2be1 |
3 | // Copyright (c) 2002-2014 OPEN CASCADE SAS |
b311480e |
4 | // |
973c2be1 |
5 | // This file is part of Open CASCADE Technology software library. |
b311480e |
6 | // |
d5f74e42 |
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 |
973c2be1 |
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. |
b311480e |
12 | // |
973c2be1 |
13 | // Alternatively, this file may be used under the terms of Open CASCADE |
14 | // commercial license or contractual agreement. |
b311480e |
15 | |
7fd59977 |
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 | |
ddf2fe8e |
23 | inline void NCollection_BaseSequence::Nullify () |
24 | { |
25 | myFirstItem = myLastItem = myCurrentItem = NULL; |
26 | myCurrentIndex = mySize = 0; |
27 | } |
28 | |
7fd59977 |
29 | //======================================================================= |
30 | //function : ClearSeq |
31 | //purpose : removes all items from the current sequence |
32 | //======================================================================= |
33 | |
ddf2fe8e |
34 | void NCollection_BaseSequence::ClearSeq (NCollection_DelSeqNode fDel) |
7fd59977 |
35 | { |
79a35943 |
36 | NCollection_SeqNode* p = myFirstItem; |
7fd59977 |
37 | while (p) { |
79a35943 |
38 | NCollection_SeqNode* q = p; |
7fd59977 |
39 | p = p->Next(); |
ddf2fe8e |
40 | fDel (q, myAllocator); |
7fd59977 |
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 { |
79a35943 |
56 | myLastItem->SetNext(theItem); |
7fd59977 |
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; |
79a35943 |
79 | myLastItem->SetNext(Other.myFirstItem); |
7fd59977 |
80 | if (Other.myFirstItem) { |
79a35943 |
81 | Other.myFirstItem->SetPrevious(myLastItem); |
7fd59977 |
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 { |
79a35943 |
99 | myFirstItem->SetPrevious (theItem); |
100 | theItem->SetNext (myFirstItem); |
7fd59977 |
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) |
79a35943 |
125 | Other.myLastItem->SetNext (myFirstItem); |
126 | myFirstItem->SetPrevious(Other.myLastItem); |
7fd59977 |
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 | { |
79a35943 |
140 | NCollection_SeqNode* p = myFirstItem; |
7fd59977 |
141 | while (p) { |
79a35943 |
142 | NCollection_SeqNode* tmp = p->Next(); |
143 | p->SetNext (p->Previous()); |
144 | p->SetPrevious (tmp); |
7fd59977 |
145 | p = tmp; |
146 | } |
79a35943 |
147 | NCollection_SeqNode* tmp = myFirstItem; |
7fd59977 |
148 | myFirstItem = myLastItem; |
149 | myLastItem = tmp; |
79a35943 |
150 | if (mySize != 0) |
151 | myCurrentIndex = mySize + 1 - myCurrentIndex; |
7fd59977 |
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); |
79a35943 |
170 | if (aPos->Next() == NULL) |
171 | myLastItem = theItem; |
172 | else |
173 | aPos->Next()->SetPrevious(theItem); |
7fd59977 |
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 { |
79a35943 |
192 | NCollection_SeqNode * p = Find (theIndex); |
7fd59977 |
193 | theItem->SetNext(p->Next()); |
194 | theItem->SetPrevious(p); |
79a35943 |
195 | if (theIndex == mySize) |
196 | myLastItem = theItem; |
197 | else |
198 | p->Next()->SetPrevious(theItem); |
199 | p->SetNext(theItem); |
7fd59977 |
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(); |
eafb234b |
216 | if (Other.mySize != 0) { |
7fd59977 |
217 | if (theIndex == 0) |
218 | PPrepend (Other); |
219 | else { |
79a35943 |
220 | NCollection_SeqNode * p = Find (theIndex); |
221 | Other.myFirstItem->SetPrevious (p); |
222 | Other.myLastItem->SetNext (p->Next()); |
7fd59977 |
223 | if (theIndex == mySize) |
224 | myLastItem = Other.myLastItem; |
225 | else |
79a35943 |
226 | p->Next()->SetPrevious (Other.myLastItem); |
227 | p->SetNext (Other.myFirstItem); |
7fd59977 |
228 | mySize += Other.mySize; |
229 | if (theIndex < myCurrentIndex) |
230 | myCurrentIndex += Other.mySize; |
231 | Other.Nullify(); |
232 | } |
eafb234b |
233 | } |
7fd59977 |
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) { |
79a35943 |
251 | NCollection_SeqNode * pi = Find(I); |
252 | NCollection_SeqNode * pj = Find(J); |
7fd59977 |
253 | |
254 | // update the node before I |
255 | if (pi->Previous()) |
79a35943 |
256 | pi->Previous()->SetNext (pj); |
7fd59977 |
257 | else |
258 | myFirstItem = pj; |
259 | |
260 | // update the node after J |
261 | if (pj->Next()) |
79a35943 |
262 | pj->Next()->SetPrevious(pi); |
7fd59977 |
263 | else |
264 | myLastItem = pi; |
265 | |
266 | if (pi->Next() == pj) { // I and J are consecutives, update them |
79a35943 |
267 | pj->SetPrevious (pi->Previous()); |
268 | pi->SetPrevious (pj); |
269 | pi->SetNext (pj->Next()); |
270 | pj->SetNext (pi); |
7fd59977 |
271 | } |
272 | else { // I and J are not consecutive |
273 | // update the node after I |
79a35943 |
274 | pi->Next()->SetPrevious (pj); |
7fd59977 |
275 | // update the node before J |
79a35943 |
276 | pj->Previous()->SetNext (pi); |
7fd59977 |
277 | // update nodes I and J |
79a35943 |
278 | NCollection_SeqNode* tmp = pi->Next(); |
279 | pi->SetNext (pj->Next()); |
280 | pj->SetNext (tmp); |
7fd59977 |
281 | tmp = pi->Previous(); |
79a35943 |
282 | pi->SetPrevious (pj->Previous()); |
283 | pj->SetPrevious (tmp); |
7fd59977 |
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 | |
79a35943 |
302 | NCollection_SeqNode * p = Find (theIndex); |
7fd59977 |
303 | |
304 | Sub.myLastItem = myLastItem; |
305 | Sub.mySize = mySize - theIndex + 1; |
306 | |
307 | myLastItem = p->Previous(); |
308 | if (myLastItem) { |
79a35943 |
309 | myLastItem->SetNext(NULL); |
7fd59977 |
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; |
79a35943 |
321 | p->SetPrevious (NULL); |
7fd59977 |
322 | Sub.myCurrentIndex = 1; |
323 | } |
324 | |
325 | //======================================================================= |
326 | //function : Remove |
327 | //purpose : |
328 | //======================================================================= |
329 | |
330 | void NCollection_BaseSequence::RemoveSeq |
331 | (NCollection_BaseSequence::Iterator& thePosition, |
ddf2fe8e |
332 | NCollection_DelSeqNode fDel) |
7fd59977 |
333 | { |
334 | NCollection_SeqNode * aPos = thePosition.myCurrent; |
335 | if (aPos == NULL) |
336 | return; |
79a35943 |
337 | thePosition.myCurrent = aPos -> Next(); |
7fd59977 |
338 | |
339 | if (aPos->Previous()) |
79a35943 |
340 | aPos->Previous()->SetNext (aPos->Next()); |
7fd59977 |
341 | else |
342 | myFirstItem = aPos->Next(); |
343 | |
344 | if (aPos->Next()) |
79a35943 |
345 | aPos->Next()->SetPrevious (aPos->Previous()); |
7fd59977 |
346 | else |
347 | myLastItem = aPos->Previous(); |
348 | |
349 | -- mySize; |
350 | myCurrentItem = myLastItem; |
351 | myCurrentIndex = mySize; |
352 | |
ddf2fe8e |
353 | fDel (aPos, myAllocator); |
7fd59977 |
354 | } |
355 | |
356 | //======================================================================= |
357 | //function : Remove |
358 | //purpose : |
359 | //======================================================================= |
360 | |
ddf2fe8e |
361 | void NCollection_BaseSequence::RemoveSeq (const Standard_Integer theIndex, |
362 | NCollection_DelSeqNode fDel) |
7fd59977 |
363 | { |
364 | Standard_OutOfRange_Raise_if (theIndex <= 0 || theIndex > mySize, ""); |
365 | |
79a35943 |
366 | NCollection_SeqNode * p = Find (theIndex); |
7fd59977 |
367 | if (p->Previous()) |
79a35943 |
368 | p->Previous()->SetNext (p->Next()); |
7fd59977 |
369 | else |
370 | myFirstItem = p->Next(); |
371 | if (p->Next()) |
79a35943 |
372 | p->Next()->SetPrevious (p->Previous()); |
7fd59977 |
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 | } |
ddf2fe8e |
386 | fDel (p, myAllocator); |
7fd59977 |
387 | } |
388 | |
389 | //======================================================================= |
390 | //function : Remove |
391 | //purpose : remove a set of items |
392 | //======================================================================= |
393 | |
ddf2fe8e |
394 | void NCollection_BaseSequence::RemoveSeq (const Standard_Integer From, |
395 | const Standard_Integer To, |
396 | NCollection_DelSeqNode fDel) |
7fd59977 |
397 | { |
398 | Standard_OutOfRange_Raise_if (From <= 0 || To > mySize || From > To, ""); |
399 | |
79a35943 |
400 | NCollection_SeqNode * pfrom = Find(From); |
401 | NCollection_SeqNode * pto = Find(To); |
7fd59977 |
402 | |
403 | if (pfrom->Previous()) |
79a35943 |
404 | pfrom->Previous()->SetNext (pto->Next()); |
7fd59977 |
405 | else |
406 | myFirstItem = pto->Next(); |
407 | if (pto->Next()) |
79a35943 |
408 | pto->Next()->SetPrevious (pfrom->Previous()); |
7fd59977 |
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++) { |
79a35943 |
426 | NCollection_SeqNode * tmp = pfrom; |
7fd59977 |
427 | pfrom = pfrom->Next(); |
ddf2fe8e |
428 | fDel (tmp, myAllocator); |
7fd59977 |
429 | } |
430 | } |
431 | |
432 | //======================================================================= |
433 | //function : Find |
434 | //purpose : |
435 | //======================================================================= |
436 | |
79a35943 |
437 | NCollection_SeqNode * NCollection_BaseSequence::Find (const Standard_Integer theIndex) const |
7fd59977 |
438 | { |
439 | Standard_Integer i; |
79a35943 |
440 | NCollection_SeqNode * p; |
7fd59977 |
441 | if (theIndex <= myCurrentIndex) { |
442 | if (theIndex < myCurrentIndex / 2) { |
443 | p = myFirstItem; |
79a35943 |
444 | for (i = 1; i < theIndex; i++) |
445 | p = p->Next(); |
7fd59977 |
446 | } else { |
447 | p = myCurrentItem; |
79a35943 |
448 | for (i = myCurrentIndex; i > theIndex; i--) |
449 | p = p->Previous(); |
7fd59977 |
450 | } |
451 | } else { |
452 | if (theIndex < (myCurrentIndex + mySize) / 2) { |
453 | p = myCurrentItem; |
79a35943 |
454 | for (i = myCurrentIndex; i < theIndex; i++) |
455 | p = p->Next(); |
7fd59977 |
456 | } else { |
457 | p = myLastItem; |
79a35943 |
458 | for (i = mySize; i > theIndex; i--) |
459 | p = p->Previous(); |
7fd59977 |
460 | } |
461 | } |
462 | return p; |
463 | } |