0024428: Implementation of LGPL license
[occt.git] / src / BOPCol / BOPCol_Array1.hxx
1 // Created by: Peter KURNEV
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
7 // under the terms of the GNU Lesser General Public 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 #ifndef BOPCol_Array1_HeaderFile
16 #define BOPCol_Array1_HeaderFile
17
18 #include <NCollection_List.hxx>
19 #include <Standard.hxx>
20 #include <NCollection_BaseAllocator.hxx>
21
22 /**
23 * Class BOPCol_Array1 (dynamic array of objects)
24 *
25 *   1. The Array1 uses the allocator (in terms of NCollection_BaseAllocator)
26 *      to allocate the memory.
27 *   2. The memory is allocated as a list of memory blocks. The size of the first
28 *      block is myStartSize. The size of the other blocks is myIncrement  
29 *   3  The Array1 is  created with 0 length. 
30 *   4. The Array1 must be initiated by invoke the method Init(). 
31 *      Init() allocates the memory block for initial myStartSize elements. 
32 *   5. The elements can be added by the method Append(theElement). the method 
33 *      Append(theElement) arranges theElement in 
34 *       a) previously allocated memory block (if it is possible)     
35 *       b) new allocated memory block (otherwise). The size of new blocks to 
36 *          allocate can be set [once only] by the method SetIncrement(theSize). 
37 *   6. The contents of the element with index "i" can be queried or modified 
38 *      by the methods  
39 *      SetValue(i, theElement), Value(i), ChangeValue(i), operator()(i)
40 */
41
42 //=======================================================================
43 //class : MemBlock
44 //
45 //=======================================================================
46 template <class Type> class BOPCol_MemBlock {
47  
48  public:
49   // Ctor
50   BOPCol_MemBlock(const Handle(NCollection_BaseAllocator)& theAllocator) {
51     myI1=0;
52     myI2=0;
53     mySize=0;
54     myData=NULL;
55     myAllocator=theAllocator;
56     myNext=NULL;
57   }
58   // ~
59   ~BOPCol_MemBlock(){
60     Clear();
61   }
62   // Clear
63   void Clear() {
64     if (myData) {
65       //Standard_Integer i;
66       Standard_Size i;
67       //
68       for (i=0; i<mySize; ++i) {
69         myData[i].~Type();
70       }
71       myAllocator->Free((Standard_Address&)myData); 
72       //
73       myData=NULL;
74       mySize=0;
75       myNext=NULL;
76     }
77   }
78   // Allocate
79   void Allocate(const Standard_Size theSize) { 
80     //Standard_Integer i;
81     Standard_Size i;
82     //
83     Clear();
84     mySize=theSize;
85     myData=(Type*)myAllocator->Allocate(theSize*sizeof(Type));
86     for (i=0; i<mySize; ++i) {
87 #ifdef BOPCol_Array1_Use_Allocator
88       new (myData+i) Type (myAllocator);
89 #else
90       new (myData+i) Type;
91 #endif
92     }
93   }
94   // SetRange
95   void SetRange(const Standard_Integer theI1,
96                 const Standard_Integer theI2) {
97     myI1=theI1;
98     myI2=theI2;
99   }
100   // Range
101   void Range(Standard_Integer& theI1,
102              Standard_Integer& theI2) const {
103     theI1=myI1;
104     theI2=myI2;
105   }
106   // Contains
107   Standard_Boolean Contains(const Standard_Integer theIndex)const {
108     return (theIndex>=myI1 && theIndex<=myI2);
109   }
110   // SetValue
111   void SetValue(const Standard_Integer theIndex,
112                 const Type& theValue) {
113     *(myData+theIndex-myI1)=theValue;
114   }
115   // Value
116   const Type& Value(const Standard_Integer theIndex)const {
117     return *(myData+theIndex-myI1);
118   }
119   // ChangeValue
120   Type& ChangeValue(const Standard_Integer theIndex) {
121     return *(myData+theIndex-myI1);
122   }
123   // SetNext
124   void SetNext(BOPCol_MemBlock<Type>* pNext) {
125     myNext=pNext;
126   }
127   // Next
128   BOPCol_MemBlock<Type>* Next() {
129     return myNext;
130   }
131   //
132  public:
133   BOPCol_MemBlock<Type>* myNext;
134  protected:
135   Standard_Integer myI1;
136   Standard_Integer myI2;
137   Standard_Size mySize;
138   Type *myData;
139   Handle(NCollection_BaseAllocator) myAllocator;
140 };
141
142 //=======================================================================
143 //class  : BOPCol_Array1
144 //
145 //=======================================================================
146 template <class Type> class BOPCol_Array1 {
147
148  public:
149   typedef BOPCol_MemBlock<Type>*  BOPCol_PMemBlock;
150   typedef BOPCol_MemBlock<Type>   BOPCol_XMemBlock;
151   //=========
152   // Ctor
153   BOPCol_Array1(const Handle(NCollection_BaseAllocator)& theAllocator=0L) {
154     myStartSize=32;
155     myIncrement=8;
156     myExtent=0;
157     myPBlock=NULL;
158     myPBlock1=NULL;
159     //
160     if (theAllocator.IsNull()) {
161       myAllocator = NCollection_BaseAllocator::CommonBaseAllocator();
162     }
163     else {
164       myAllocator=theAllocator;
165     }
166   }
167   // ~
168   ~BOPCol_Array1() {
169     Clear();
170   }
171   //===========
172   // Clear
173   void Clear() {
174     BOPCol_PMemBlock pBlock, pNext;
175     //
176     pBlock=myPBlock1;
177     while(pBlock) {
178       pNext=pBlock->Next();
179       //
180       //pBlock->~BOPCol_MemBlock<Type> ();
181       pBlock->~BOPCol_XMemBlock();
182       //pBlock->Clear();
183       myAllocator->Free((Standard_Address&)pBlock);
184       //
185       pBlock=pNext;
186     }
187     myPBlock1=NULL;
188     myPBlock=NULL;
189     myExtent=0;
190   }
191   // SetStartSize
192   void SetStartSize(const Standard_Integer theSize) {
193     if (theSize>0) {
194       myStartSize=theSize;
195     }
196   }
197   // SetIncrement
198   void SetIncrement(const Standard_Integer theSize){
199     if (theSize>0) {
200       myIncrement=theSize;
201     }
202   }
203   // Increment
204   Standard_Integer Increment()const {
205     return myIncrement;
206   }
207   // Extent
208   Standard_Integer Extent()const {
209     return myExtent;
210   }
211   // Size
212   Standard_Integer Size()const {
213     return myExtent;
214   }
215   // Size
216   Standard_Integer Length()const {
217     return myExtent;
218   }
219   // Init
220   void Init();
221   // Append(const Type& theValue)
222   Standard_Integer Append(const Type& theValue);
223   // Append()
224   Standard_Integer Append();
225   // SetValue
226   void SetValue(const Standard_Integer theIndex,
227                 const Type& theValue);
228   // Value
229   const Type& operator()(const Standard_Integer theIndex)const;
230   //
231   const Type& Value(const Standard_Integer theIndex)const;
232   // ChangeValue
233   Type& operator()(const Standard_Integer theIndex);
234   //
235   Type& ChangeValue(const Standard_Integer theIndex);
236  //
237  // protected
238  protected:
239   //===========
240   //FindBlock
241   Standard_Boolean FindBlock(const Standard_Integer theIndex)const ;
242   //Copy ctor
243   BOPCol_Array1(const BOPCol_Array1&);
244   //Assign operator
245   BOPCol_Array1& operator =(const BOPCol_Array1& theOther);
246   //==========
247   // fields
248  protected:
249   Standard_Integer myStartSize;
250   Standard_Integer myIncrement;
251   Standard_Integer myExtent;
252   Type myDfltItem;
253   BOPCol_MemBlock<Type> * myPBlock; 
254   BOPCol_MemBlock<Type> * myPBlock1; 
255   Handle(NCollection_BaseAllocator) myAllocator;
256 };
257 //
258 //=======================================================================
259 //function : Init
260 //purpose  : 
261 //=======================================================================
262 template <class Type> 
263   void BOPCol_Array1<Type>::Init() {
264     BOPCol_PMemBlock pBlock;
265     //
266     pBlock=(BOPCol_PMemBlock)myAllocator->Allocate(sizeof(BOPCol_MemBlock<Type>));
267     new (pBlock) BOPCol_MemBlock<Type>(myAllocator);
268     //
269     pBlock->Allocate(myStartSize);
270     pBlock->SetRange(0, myStartSize-1);
271     myPBlock1=pBlock;
272     myPBlock=pBlock;
273   }
274 //=======================================================================
275 //function : Append
276 //purpose  : 
277 //=======================================================================
278 template <class Type> 
279   Standard_Integer BOPCol_Array1<Type>::Append(const Type& theValue) {
280     BOPCol_PMemBlock pBlock, pNext;
281     //
282     pBlock=myPBlock1;
283     for(;;) {
284       pNext=pBlock->myNext;
285       if(!pNext) {
286         myPBlock=pBlock;
287         break;
288       }
289       pBlock=pNext;
290     }
291     //
292     if (!myPBlock->Contains(myExtent)) {
293       //
294       pBlock=(BOPCol_PMemBlock)myAllocator->Allocate(sizeof(BOPCol_MemBlock<Type>));
295       new (pBlock) BOPCol_MemBlock<Type>(myAllocator);
296       //
297       pBlock->Allocate(myIncrement);
298       pBlock->SetRange(myExtent, myExtent+myIncrement-1);
299       //
300       myPBlock->myNext=pBlock;
301       //
302       myPBlock=pBlock;
303     }
304     //
305     myPBlock->SetValue(myExtent, theValue);
306     //
307     ++myExtent;
308     //
309     return myExtent;
310   }
311 //=======================================================================
312 //function : Append
313 //purpose  : 
314 //=======================================================================
315 template <class Type> 
316   Standard_Integer BOPCol_Array1<Type>::Append() {
317     BOPCol_PMemBlock pBlock, pNext;
318     //
319     pBlock=myPBlock1;
320     for(;;) {
321       pNext=pBlock->myNext;
322       if(!pNext) {
323         myPBlock=pBlock;
324         break;
325       }
326       pBlock=pNext;
327     }
328     //
329     if (!myPBlock->Contains(myExtent)) {
330       //
331       pBlock=(BOPCol_PMemBlock)myAllocator->Allocate(sizeof(BOPCol_MemBlock<Type>));
332       new (pBlock) BOPCol_MemBlock<Type>(myAllocator);
333       //
334       pBlock->Allocate(myIncrement);
335       pBlock->SetRange(myExtent, myExtent+myIncrement-1);
336       //
337       myPBlock->myNext=pBlock;
338       //
339       myPBlock=pBlock;
340     }
341     ++myExtent;
342     //
343     return myExtent;
344   }
345 //=======================================================================
346 //function : SetValue
347 //purpose  : 
348 //=======================================================================
349 template <class Type> 
350   void BOPCol_Array1<Type>::SetValue(const Standard_Integer theIndex,
351                                      const Type& theValue) {
352     if (FindBlock(theIndex)) {
353       myPBlock->SetValue(theIndex, theValue);
354     }
355   }
356 //=======================================================================
357 //function : operator()
358 //purpose  : 
359 //=======================================================================
360 template <class Type> 
361   const Type& BOPCol_Array1<Type>::operator()(const Standard_Integer theIndex)const {
362     if (FindBlock(theIndex)) {
363       return myPBlock->Value(theIndex);
364     }
365     return myDfltItem;
366   }
367 //=======================================================================
368 //function : Value
369 //purpose  : 
370 //=======================================================================
371 template <class Type> 
372   const Type& BOPCol_Array1<Type>::Value(const Standard_Integer theIndex)const {
373     return operator()(theIndex);
374   }
375 //=======================================================================
376 //function : operator
377 //purpose  : 
378 //=======================================================================
379 template <class Type> 
380   Type& BOPCol_Array1<Type>::operator()(const Standard_Integer theIndex) {
381     if (FindBlock(theIndex)) {
382       return myPBlock->ChangeValue(theIndex);
383     }
384     return myDfltItem;
385   }
386 //=======================================================================
387 //function : ChangeValue
388 //purpose  : 
389 //=======================================================================
390 template <class Type> 
391   Type& BOPCol_Array1<Type>::ChangeValue(const Standard_Integer theIndex) {
392     return operator()(theIndex);
393   }
394 //=======================================================================
395 //function : FindBlock
396 //purpose  : 
397 //=======================================================================
398 template <class Type> 
399   Standard_Boolean BOPCol_Array1<Type>::FindBlock(const Standard_Integer theIndex)const {
400     Standard_Boolean bRet;
401     //
402     bRet=myPBlock->Contains(theIndex);
403     if(bRet) {
404       return bRet;
405     }
406     //
407     Standard_Integer i1, i2;
408     BOPCol_PMemBlock pBlock, *xPBlock;
409     //
410     xPBlock=(BOPCol_PMemBlock*)&myPBlock;
411     pBlock=myPBlock1;
412     //
413     i1=0;
414     i2=myStartSize-1;
415     do {
416       if (theIndex>=i1 && theIndex<=i2) {
417         *xPBlock=pBlock;
418         return !bRet;
419       }
420       //
421       i1=i2+1;
422       i2=i1+myIncrement-1;
423       pBlock=pBlock->myNext;
424     } while(pBlock);
425     //
426     return bRet;
427   }
428
429 #endif