0026937: Eliminate NO_CXX_EXCEPTION macro support
[occt.git] / src / TCollection / TCollection_BaseSequence.cxx
1 // Copyright (c) 1998-1999 Matra Datavision
2 // Copyright (c) 1999-2014 OPEN CASCADE SAS
3 //
4 // This file is part of Open CASCADE Technology software library.
5 //
6 // This library is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU Lesser General Public License version 2.1 as published
8 // by the Free Software Foundation, with special exception defined in the file
9 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
10 // distribution for complete text of the license and disclaimer of any warranty.
11 //
12 // Alternatively, this file may be used under the terms of Open CASCADE
13 // commercial license or contractual agreement.
14
15
16 #include <Standard_DomainError.hxx>
17 #include <Standard_NoSuchObject.hxx>
18 #include <Standard_OutOfRange.hxx>
19 #include <TCollection_BaseSequence.hxx>
20 #include <TCollection_SeqNode.hxx>
21
22 typedef void (*DelNode) (TCollection_SeqNode*);
23
24 TCollection_BaseSequence::TCollection_BaseSequence() :
25        FirstItem(NULL),
26        LastItem(NULL),
27        CurrentItem(NULL),
28        CurrentIndex(0),
29        Size(0)
30 {
31 }
32
33
34
35 // ----------------------------------
36 // Clear : Clear the Current Sequence
37 // ----------------------------------
38 void TCollection_BaseSequence::Clear(const Standard_Address delnode)
39 {
40   Size = 0;
41   TCollection_SeqNode* p = (TCollection_SeqNode*) FirstItem;
42   TCollection_SeqNode* q;
43   while (p) {
44     q = p;
45     p = p->Next();
46     ((DelNode)delnode) (q);
47   }
48   LastItem = FirstItem = CurrentItem  = NULL;
49   CurrentIndex = 0;
50 }
51
52 void TCollection_BaseSequence::PAppend(const Standard_Address newnode)
53 {
54   if (Size == 0) {
55     FirstItem = LastItem = CurrentItem = newnode;   
56     CurrentIndex = Size = 1;
57   }
58   else {
59     ((TCollection_SeqNode*)LastItem)->Next() = (TCollection_SeqNode*)newnode;
60     LastItem = newnode;   
61     Size++;               
62   }
63 }
64
65 // ---------------------------------------------------
66 // Append : Push a sequence at the end of the sequence
67 // ---------------------------------------------------
68 void TCollection_BaseSequence::PAppend(TCollection_BaseSequence& Other)
69 {
70   if (Other.Size == 0)
71     return;
72   if (Size == 0) {
73     Size         = Other.Size;
74     FirstItem    = Other.FirstItem;
75     LastItem     = Other.LastItem;
76     CurrentItem  = FirstItem;
77     CurrentIndex = 1;
78   }
79   else {
80     Size += Other.Size;
81     ((TCollection_SeqNode*)LastItem)->Next() = (TCollection_SeqNode*)Other.FirstItem;
82     if (Other.FirstItem) {
83       ((TCollection_SeqNode*)Other.FirstItem)->Previous() = (TCollection_SeqNode*)LastItem;
84       LastItem = Other.LastItem;
85     }
86   }
87   Other.Nullify();
88 }
89
90
91
92 void TCollection_BaseSequence::PPrepend(const Standard_Address newnode)
93 {
94   if (Size == 0) {
95     FirstItem = LastItem = CurrentItem = newnode;
96     CurrentIndex = Size = 1;
97   }
98   else {
99     ((TCollection_SeqNode*)FirstItem)->Previous() = (TCollection_SeqNode*) newnode;
100     ((TCollection_SeqNode*)newnode)->Next() = (TCollection_SeqNode*)FirstItem; 
101     FirstItem = newnode;
102     Size++;
103     CurrentIndex++;
104   }
105 }
106
107 void TCollection_BaseSequence::PPrepend(TCollection_BaseSequence& Other)
108 {
109   if (Other.Size == 0)
110     return;
111   if (Size == 0) {
112     Size         = Other.Size;
113     FirstItem    = Other.FirstItem;
114     LastItem     = Other.LastItem;
115     CurrentIndex = 1;
116     CurrentItem  =  FirstItem;
117   }
118   else {
119     Size += Other.Size;
120     if (Other.LastItem) ((TCollection_SeqNode*)Other.LastItem)->Next() = (TCollection_SeqNode*)FirstItem;
121     ((TCollection_SeqNode*)FirstItem)->Previous() = (TCollection_SeqNode*)Other.LastItem;
122     FirstItem = Other.FirstItem;
123     CurrentIndex += Other.Size;
124   }
125   Other.Nullify();
126 }
127
128 // ---------------------------------------------------------
129 // Reverse : Reverse the order of a given sequence
130 // ---------------------------------------------------------
131 void TCollection_BaseSequence::Reverse()
132 {
133   TCollection_SeqNode* p = (TCollection_SeqNode*) FirstItem;
134   TCollection_SeqNode* tmp;
135   while (p) {
136     tmp = p->Next();
137     p->Next() = p->Previous();
138     p->Previous() = tmp;
139     p = tmp;
140   }
141   tmp = (TCollection_SeqNode*)FirstItem;
142   FirstItem = LastItem;
143   LastItem = tmp;
144   if (Size != 0) CurrentIndex = Size + 1 - CurrentIndex;
145 }
146
147
148 void TCollection_BaseSequence::PInsertAfter(const Standard_Integer Index, const Standard_Address N)
149 {
150   if (Index == 0) 
151     PPrepend(N);
152   else {
153     TCollection_SeqNode* p = (TCollection_SeqNode*) Find(Index);
154     TCollection_SeqNode* newnode = (TCollection_SeqNode*) N;
155     newnode->Next() = p->Next();
156     newnode->Previous() = p;
157     if (Index == Size) LastItem = newnode;
158     else p->Next()->Previous() = newnode;
159     p->Next() = newnode;
160     Size++;
161     if (Index < CurrentIndex) CurrentIndex++;
162   }
163 }
164
165 // -------------------------------------------------------------------
166 // InsertAfter : Insert a sequence after a given index in the sequence
167 // -------------------------------------------------------------------
168
169 void TCollection_BaseSequence::PInsertAfter(const Standard_Integer Index, TCollection_BaseSequence& Other)
170 {
171   if (Index < 0 || Index > Size) throw Standard_OutOfRange();
172   if (Other.Size == 0) return;
173   if (Index == 0) 
174     PPrepend( Other );
175   else {
176     TCollection_SeqNode* p = (TCollection_SeqNode*) Find(Index);
177     ((TCollection_SeqNode*)Other.FirstItem)->Previous() = p;
178     ((TCollection_SeqNode*)Other.LastItem)->Next() = p->Next();
179     if (Index == Size) LastItem = Other.LastItem;
180     else p->Next()->Previous() = (TCollection_SeqNode*)Other.LastItem;
181     p->Next() = (TCollection_SeqNode*)Other.FirstItem;
182     Size += Other.Size;
183     if (Index < CurrentIndex) CurrentIndex += Other.Size;
184     Other.Nullify();
185   }
186 }
187
188 // ----------------------------------------
189 // Exchange : Exchange two elements in the sequence
190 // ----------------------------------------
191 void TCollection_BaseSequence::Exchange(const Standard_Integer I, const Standard_Integer J)
192 {
193    Standard_OutOfRange_Raise_if ( I <= 0 || J <= 0 || I > Size || J > Size,"" ) ;
194
195    // Assume I < J
196    if (I == J) return;
197    if (J < I) {
198      Exchange(J,I);
199      return;
200    }
201
202    TCollection_SeqNode* pi = (TCollection_SeqNode*) Find(I);
203    TCollection_SeqNode* pj = (TCollection_SeqNode*) Find(J);
204
205    // update the node before I
206    if (pi->Previous())
207      pi->Previous()->Next() = pj;
208    else 
209      FirstItem = pj;
210
211    // update the node after J
212    if (pj->Next())
213      pj->Next()->Previous() = pi;
214    else
215      LastItem = pi;
216
217    if (pi->Next() == pj) {          // I and J are consecutives, update them
218      pj->Previous() = pi->Previous();
219      pi->Previous() = pj;
220      pi->Next() = pj->Next();
221      pj->Next() = pi;
222    }
223    else {                        // I and J are not consecutive
224      pi->Next()->Previous() = pj;    // update the node after I
225      pj->Previous()->Next() = pi;    // update the node before J
226      TCollection_SeqNode* tmp = pi->Next();       // update nodes I and J
227      pi->Next() = pj->Next();
228      pj->Next() = tmp;
229      tmp = pi->Previous();
230      pi->Previous() = pj->Previous();
231      pj->Previous() = tmp;
232    }
233
234    if      (CurrentIndex == I) CurrentItem = pj;
235    else if (CurrentIndex == J) CurrentItem = pi;
236 }
237
238 void TCollection_BaseSequence::PSplit(const Standard_Integer Index, TCollection_BaseSequence& Sub)
239 {
240    Standard_OutOfRange_Raise_if( Index <= 0 || Index > Size,"" );
241    Standard_DomainError_Raise_if(this == &Sub,"No Split on myself!!");
242
243    TCollection_SeqNode* p = (TCollection_SeqNode*) Find(Index);
244
245    Sub.LastItem = LastItem;
246    Sub.Size = Size - Index + 1;
247
248    LastItem = p->Previous();
249    if (LastItem) {
250      ((TCollection_SeqNode*)LastItem)->Next() = NULL;
251      Size = Index - 1;
252      if (CurrentIndex >= Index) {
253        CurrentIndex = 1;
254        CurrentItem = (TCollection_SeqNode*) FirstItem;
255      }
256    }
257    else {
258      FirstItem = CurrentItem = NULL;
259      Size = CurrentIndex = 0;
260    }
261
262    Sub.FirstItem = Sub.CurrentItem = p;
263    p->Previous() = NULL;
264    Sub.CurrentIndex = 1;
265 }
266
267 void TCollection_BaseSequence::Remove(const Standard_Integer Index, const Standard_Address delnode)
268 {
269   Standard_OutOfRange_Raise_if(Index <= 0 || Index > Size,"" );
270   
271   TCollection_SeqNode* p = (TCollection_SeqNode*) Find(Index);
272   if (p->Previous())
273     p->Previous()->Next() = p->Next();
274   else
275     FirstItem = p->Next();
276   if (p->Next())
277     p->Next()->Previous() = p->Previous();
278   else
279     LastItem = p->Previous();
280
281   Size--;
282   if      (CurrentIndex > Index) CurrentIndex--;
283   else if (CurrentIndex == Index) {
284     if (p->Next()) 
285       CurrentItem = p->Next();
286     else {
287       CurrentItem = (TCollection_SeqNode*) LastItem;
288       CurrentIndex = Size;
289     }
290   }
291    ((DelNode)delnode) (p);
292 }
293
294 // ---------------------
295 // Remove a set of items
296 // --------------------- 
297 void TCollection_BaseSequence::Remove(const Standard_Integer From, const Standard_Integer To, 
298                                       const Standard_Address delnode)
299 {
300   Standard_OutOfRange_Raise_if (From <= 0 || From > Size || To <= 0 || To > Size || From > To,"" );
301
302   TCollection_SeqNode* pfrom = (TCollection_SeqNode*) Find(From);
303   TCollection_SeqNode* pto   = (TCollection_SeqNode*) Find(To);
304   
305   if (pfrom->Previous())
306     pfrom->Previous()->Next() = pto->Next();
307   else
308     FirstItem = pto->Next();
309   if (pto->Next())
310     pto->Next()->Previous() = pfrom->Previous();
311   else
312     LastItem = pfrom->Previous();
313   
314   Size -= To - From + 1;
315   if      (CurrentIndex > To) 
316     CurrentIndex -= To - From + 1;
317   else if (CurrentIndex >= From) {
318     if (pto->Next()) {
319       CurrentItem = pto->Next();
320       CurrentIndex = From;                      // AGV fix 24.05.01
321     } else {
322       CurrentItem = (TCollection_SeqNode*) LastItem;
323       CurrentIndex = Size;
324     }
325   }
326   
327   Standard_Integer i;
328   for (i = From; i <= To; i++) {
329     pto = pfrom;
330     pfrom = pfrom->Next();
331      ((DelNode)delnode) (pto);
332   }
333 }
334
335 Standard_Address TCollection_BaseSequence::Find(const Standard_Integer Index) const 
336 {
337   Standard_Integer i;
338   TCollection_SeqNode* p;
339   if (Index <= CurrentIndex) {
340     if (Index < CurrentIndex / 2) {
341       p = (TCollection_SeqNode*) FirstItem;
342       for (i = 1; i < Index; i++) p = p->Next();
343     }
344     else {
345       p = (TCollection_SeqNode*) CurrentItem;
346       for (i = CurrentIndex; i > Index; i--) p = p->Previous();
347     }
348   }
349   else {
350     if (Index < (CurrentIndex + Size) / 2) {
351       p = (TCollection_SeqNode*) CurrentItem;
352       for (i = CurrentIndex; i < Index; i++) p = p->Next();
353     }
354     else {
355       p = (TCollection_SeqNode*) LastItem;
356       for (i = Size; i > Index; i--) p = p->Previous();
357     }
358   }
359   return p;
360 }
361
362 //=======================================================================
363 //function : Nullify
364 //purpose  : 
365 //=======================================================================
366
367 void TCollection_BaseSequence::Nullify()
368 {
369   FirstItem = LastItem = CurrentItem = NULL;
370   CurrentIndex = Size = 0;
371 }