0024831: Make iterators of NCollection classes STL-compatible
[occt.git] / src / NCollection / NCollection_Vector.hxx
1 // Created on: 2002-04-23
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2002-2013 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 #ifndef NCollection_Vector_HeaderFile
17 #define NCollection_Vector_HeaderFile
18
19 #include <NCollection_BaseVector.hxx>
20 #include <NCollection_BaseCollection.hxx>
21 #include <NCollection_StlIterator.hxx>
22
23 //! Class NCollection_Vector (dynamic array of objects)
24 //!
25 //! This class is similar to NCollection_Array1  though the indices always start
26 //! at 0 (in Array1 the first index must be specified)
27 //!
28 //! The Vector is always created with 0 length. It can be enlarged by two means:
29 //!  1. Calling the method Append (val) - then "val" is added to the end of the
30 //!     vector (the vector length is incremented)
31 //!  2. Calling the method SetValue (i, val)  - if "i" is greater than or equal
32 //!     to the current length of the vector,  the vector is enlarged to accomo-
33 //!     date this index
34 //!
35 //! The methods Append and SetValue return  a non-const reference  to the copied
36 //! object  inside  the vector.  This reference  is guaranteed to be valid until
37 //! the vector is destroyed. It can be used to access the vector member directly
38 //! or to pass its address to other data structures.
39 //!
40 //! The vector iterator remembers the length of the vector  at the moment of the
41 //! creation or initialisation of the iterator.   Therefore the iteration begins
42 //! at index 0  and stops at the index equal to (remembered_length-1).  It is OK
43 //! to enlarge the vector during the iteration.
44 template <class TheItemType> class NCollection_Vector
45 : public NCollection_BaseCollection<TheItemType>,
46   public NCollection_BaseVector
47 {
48 public:
49   //! STL-compliant typedef for value type
50   typedef TheItemType value_type;
51
52 public:
53
54   //! Nested class Iterator
55   class Iterator : public NCollection_BaseCollection<TheItemType>::Iterator,
56                    public NCollection_BaseVector::Iterator
57   {
58   public:
59
60     //! Empty constructor - for later Init
61     Iterator() {}
62
63     //! Constructor with initialisation
64     Iterator (const NCollection_Vector& theVector, Standard_Boolean theToEnd = Standard_False)
65     : NCollection_BaseVector::Iterator (theVector, theToEnd) {}
66
67     //! Copy constructor
68     Iterator (const Iterator& theOther)
69     : NCollection_BaseVector::Iterator (theOther) {}
70
71     //! Initialisation
72     void Init (const NCollection_Vector& theVector)
73     {
74       initV (theVector);
75     }
76
77     //! Assignment
78     Iterator& operator= (const Iterator& theOther)
79     {
80       copyV (theOther);
81       return *this;
82     }
83
84     //! Check end
85     virtual Standard_Boolean More() const
86     {
87       return moreV();
88     }
89
90     //! Increment operator.
91     virtual void Next()
92     {
93       nextV();
94     }
95
96     //! Decrement operator.
97     virtual void Previous()
98     {
99       prevV();
100     }
101
102     //! Offset operator.
103     virtual void Offset (ptrdiff_t theOffset)
104     {
105       offsetV ((int)theOffset);
106     }
107
108     //! Difference operator.
109     virtual ptrdiff_t Differ (const Iterator& theOther) const
110     {
111       return differV (theOther);
112     }
113
114     //! Constant value access
115     virtual const TheItemType& Value() const
116     {
117       return ((const TheItemType* )curBlockV()->DataPtr)[myCurIndex];
118     }
119
120     //! Variable value access
121     virtual TheItemType& ChangeValue() const
122     {
123       return ((TheItemType* )curBlockV()->DataPtr)[myCurIndex];
124     }
125
126     //! Performs comparison of two iterators.
127     virtual Standard_Boolean IsEqual (const Iterator& theOther) const
128     {
129       return myVector    == theOther.myVector
130           && myCurIndex  == theOther.myCurIndex
131           && myEndIndex  == theOther.myEndIndex  
132           && myICurBlock == theOther.myICurBlock
133           && myIEndBlock == theOther.myIEndBlock;
134     }
135   };
136
137   //! Shorthand for a regular iterator type.
138   typedef NCollection_StlIterator<std::random_access_iterator_tag, Iterator, TheItemType, false> iterator;
139
140   //! Shorthand for a constant iterator type.
141   typedef NCollection_StlIterator<std::random_access_iterator_tag, Iterator, TheItemType, true> const_iterator;
142
143   //! Returns an iterator pointing to the first element in the vector.
144   iterator begin() const { return Iterator (*this, false); }
145
146   //! Returns an iterator referring to the past-the-end element in the vector.
147   iterator end() const { return Iterator (*this, true); }
148
149   //! Returns a const iterator pointing to the first element in the vector.
150   const_iterator cbegin() const { return Iterator (*this, false); }
151
152   //! Returns a const iterator referring to the past-the-end element in the vector.
153   const_iterator cend() const { return Iterator (*this, true); }
154
155 public: //! @name public methods
156
157   //! Constructor
158   NCollection_Vector (const Standard_Integer theIncrement              = 256,
159                       const Handle(NCollection_BaseAllocator)& theAlloc = NULL)
160   : NCollection_BaseCollection<TheItemType> (theAlloc),
161     NCollection_BaseVector (NCollection_BaseCollection<TheItemType>::myAllocator, initMemBlocks, sizeof(TheItemType), theIncrement) {}
162
163   //! Copy constructor
164   NCollection_Vector (const NCollection_Vector& theOther)
165   : NCollection_BaseCollection<TheItemType> (theOther.myAllocator),
166     NCollection_BaseVector (NCollection_BaseCollection<TheItemType>::myAllocator, initMemBlocks, theOther)
167   {
168     copyData (theOther);
169   }
170
171   //! Destructor
172   ~NCollection_Vector()
173   {
174     for (Standard_Integer anItemIter = 0; anItemIter < myCapacity; ++anItemIter)
175     {
176       initMemBlocks (*this, myData[anItemIter], 0, 0);
177     }
178     NCollection_BaseCollection<TheItemType>::myAllocator->Free (myData);
179   }
180
181   //! Operator=
182   NCollection_Vector& operator= (const NCollection_Vector& theOther)
183   {
184     Assign (theOther, Standard_False);
185     return *this;
186   }
187
188   //! Total number of items
189   Standard_Integer Length() const
190   {
191     return myLength;
192   }
193
194   //! Total number of items in the vector
195   virtual Standard_Integer Size() const
196   {
197     return myLength;
198   }
199
200   //! Method for consistency with other collections.
201   //! @return Lower bound (inclusive) for iteration.
202   Standard_Integer Lower() const
203   {
204     return 0;
205   }
206
207   //! Method for consistency with other collections.
208   //! @return Upper bound (inclusive) for iteration.
209   Standard_Integer Upper() const
210   {
211     return myLength - 1;
212   }
213
214   //! Empty query
215   Standard_Boolean IsEmpty() const
216   {
217     return (myLength == 0);
218   }
219
220   //! Virtual assignment (any collection to this array)
221   virtual void Assign (const NCollection_BaseCollection<TheItemType>& theOther)
222   {
223     if (this != &theOther)
224     {
225       TYPENAME NCollection_BaseCollection<TheItemType>::Iterator& anIter2 = theOther.CreateIterator();
226       while (anIter2.More())
227       {
228         Append (anIter2.Value());
229         anIter2.Next();
230       }
231     }
232   }
233
234   //! Assignment to the collection of the same type
235   inline void Assign (const NCollection_Vector& theOther,
236                       const Standard_Boolean    theOwnAllocator = Standard_True);
237
238   //! Method to create iterators for base collections
239   virtual TYPENAME NCollection_BaseCollection<TheItemType>::Iterator& CreateIterator() const
240   {
241     return *(new (this->IterAllocator()) Iterator(*this));
242   }
243
244   //! Append
245   TheItemType& Append (const TheItemType& theValue)
246   {
247     TheItemType& anAppended = *(TheItemType* )expandV (NCollection_BaseCollection<TheItemType>::myAllocator, myLength);
248     anAppended = theValue;
249     return anAppended;
250   }
251
252   //! Operator() - query the const value
253   const TheItemType& operator() (const Standard_Integer theIndex) const
254   {
255     return Value (theIndex);
256   }
257
258   const TheItemType& Value (const Standard_Integer theIndex) const
259   {
260     return *(const TheItemType* )findV (theIndex);
261   }
262
263   //! @return first element
264   const TheItemType& First() const
265   {
266     return *(const TheItemType* )findV (Lower());
267   }
268
269   //! @return first element
270   TheItemType& ChangeFirst()
271   {
272     return *(TheItemType* )findV (Lower());
273   }
274
275   //! @return last element
276   const TheItemType& Last() const
277   {
278     return *(const TheItemType* )findV (Upper());
279   }
280
281   //! @return last element
282   TheItemType& ChangeLast()
283   {
284     return *(TheItemType* )findV (Upper());
285   }
286
287   //! Operator() - query the value
288   TheItemType& operator() (const Standard_Integer theIndex)
289   {
290     return ChangeValue (theIndex);
291   }
292
293   TheItemType& ChangeValue (const Standard_Integer theIndex)
294   {
295     return *(TheItemType* )findV (theIndex);
296   }
297
298   //! SetValue () - set or append a value
299   TheItemType& SetValue (const Standard_Integer theIndex,
300                          const TheItemType&     theValue)
301   {
302     Standard_OutOfRange_Raise_if (theIndex < 0, "NCollection_Vector::SetValue");
303     TheItemType* const aVecValue = (TheItemType* )(theIndex < myLength ? findV (theIndex) : expandV (NCollection_BaseCollection<TheItemType>::myAllocator, theIndex));
304     *aVecValue = theValue;
305     return *aVecValue;
306   }
307
308 private: //! @name private methods
309
310   void copyData (const NCollection_Vector& theOther)
311   {
312     Standard_Integer iBlock = 0;
313     /*NCollection_Vector::*/Iterator anIter (theOther);
314     for (Standard_Integer aLength = 0; aLength < myLength; aLength += myIncrement)
315     {
316       MemBlock& aBlock = myData[iBlock];
317       initMemBlocks (*this, aBlock, aLength, myIncrement);
318       Standard_Integer anItemIter = 0;
319       for (; anItemIter < myIncrement; ++anItemIter)
320       {
321         if (!anIter.More())
322         {
323           break;
324         }
325
326         ((TheItemType* )aBlock.DataPtr)[anItemIter] = anIter.Value();
327         anIter.Next();
328       }
329       aBlock.Length = anItemIter;
330       iBlock++;
331     }
332   }
333
334   //! Method to initialize memory block content
335   static void initMemBlocks (NCollection_BaseVector&           theVector,
336                              NCollection_BaseVector::MemBlock& theBlock,
337                              const Standard_Integer            theFirst,
338                              const Standard_Integer            theSize)
339   {
340     NCollection_Vector& aSelf = static_cast<NCollection_Vector&> (theVector);
341     Handle(NCollection_BaseAllocator)& anAllocator = aSelf.myAllocator;
342
343     // release current content
344     if (theBlock.DataPtr != NULL)
345     {
346       for (Standard_Integer anItemIter = 0; anItemIter < theBlock.Size; ++anItemIter)
347       {
348         ((TheItemType* )theBlock.DataPtr)[anItemIter].~TheItemType();
349       }
350       anAllocator->Free (theBlock.DataPtr);
351       theBlock.DataPtr = NULL;
352     }
353
354     // allocate new content if requested
355     if (theSize > 0)
356     {
357       theBlock.DataPtr = anAllocator->Allocate (theSize * sizeof(TheItemType));
358       for (Standard_Integer anItemIter = 0; anItemIter < theSize; ++anItemIter)
359       {
360         new (&((TheItemType* )theBlock.DataPtr)[anItemIter]) TheItemType;
361       }
362     }
363     theBlock.FirstIndex = theFirst;
364     theBlock.Size       = theSize;
365     theBlock.Length     = 0;
366   }
367
368   friend class Iterator;
369
370 };
371
372 //! Assignment to the collection of the same type
373 template <class TheItemType> inline
374 void NCollection_Vector<TheItemType>::Assign (const NCollection_Vector& theOther,
375                                               const Standard_Boolean    theOwnAllocator)
376 {
377   if (this == &theOther)
378   {
379     return;
380   }
381
382   // destroy current data using current allocator
383   for (Standard_Integer anItemIter = 0; anItemIter < myCapacity; ++anItemIter)
384   {
385     initMemBlocks (*this, myData[anItemIter], 0, 0);
386   }
387   NCollection_BaseCollection<TheItemType>::myAllocator->Free (myData);
388
389   // allocate memory blocks with new allocator
390   if (!theOwnAllocator)
391   {
392     NCollection_BaseCollection<TheItemType>::myAllocator = theOther.myAllocator;
393   }
394   myIncrement = theOther.myIncrement;
395   myLength    = theOther.myLength;
396   myNBlocks   = (myLength == 0) ? 0 : (1 + (myLength - 1)/myIncrement);
397   myCapacity  = GetCapacity (myIncrement) + myLength / myIncrement;
398   myData      = allocMemBlocks (NCollection_BaseCollection<TheItemType>::myAllocator, myCapacity);
399
400   // copy data
401   copyData (theOther);
402 }
403
404 #endif // NCollection_Vector_HeaderFile