src/NCollection/NCollection_Array1.hxx

   1 // Created on: 2002-04-15
   2 // Created by: Alexander Kartomin (akm)
   3 // Copyright (c) 2002-2014 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_Array1_HeaderFile
  17 #define NCollection_Array1_HeaderFile
  18
  19 #include <Standard_DimensionMismatch.hxx>
  20 #include <Standard_OutOfMemory.hxx>
  21 #include <Standard_OutOfRange.hxx>
  22
  23 #include <NCollection_DefineAlloc.hxx>
  24 #include <NCollection_StlIterator.hxx>
  25
  26 // *********************************************** Template for Array1 class
  27
  28 /**
  29 * Purpose:     The class Array1 represents unidimensional arrays
  30 *              of fixed size known at run time.
  31 *              The range of the index is user defined.
  32 *              An array1 can be constructed with a "C array".
  33 *              This functionality is useful to call methods expecting
  34 *              an Array1. It allows to carry the bounds inside the arrays.
  35 *
  36 * Examples:    Item tab[100]; //  An example with a C array
  37 *              Array1OfItem ttab (tab[0],1,100);
  38 *
  39 *              Array1OfItem tttab (ttab(10),10,20); // a slice of ttab
  40 *
  41 *              If you want to reindex an array from 1 to Length do :
  42 *
  43 *              Array1 tab1(tab(tab.Lower()),1,tab.Length());
  44 *
  45 * Warning:     Programs client of such a class must be independant
  46 *              of the range of the first element. Then, a C++ for
  47 *              loop must be written like this
  48 *
  49 *              for (i = A.Lower(); i <= A.Upper(); i++)
  50 *
  51 * Changes:     In  comparison  to  TCollection  the  flag  isAllocated  was
  52 *              renamed into myDeletable (alike in  the Array2).  For naming
  53 *              compatibility the method IsAllocated remained in class along
  54 *              with IsDeletable.
  55 */
  56 template <class TheItemType>
  57 class NCollection_Array1
  58 {
  59 public:
  60   //! STL-compliant typedef for value type
  61   typedef TheItemType value_type;
  62
  63 public:
  64   //! Implementation of the Iterator interface.
  65   class Iterator
  66   {
  67   public:
  68
  69     //! Empty constructor - for later Init
  70     Iterator (void) :
  71       myPtrCur (NULL),
  72       myPtrEnd (NULL)
  73     {
  74       //
  75     }
  76
  77     //! Constructor with initialization
  78     Iterator (const NCollection_Array1& theArray, Standard_Boolean theToEnd = Standard_False) :
  79       myPtrEnd (const_cast<TheItemType*> (&theArray.Last() + 1))
  80     {
  81       myPtrCur = theToEnd ? myPtrEnd : const_cast<TheItemType*> (&theArray.First());
  82     }
  83
  84     //! Initialisation
  85     void Init (const NCollection_Array1& theArray)
  86     {
  87       myPtrCur = const_cast<TheItemType*> (&theArray.First());
  88       myPtrEnd = const_cast<TheItemType*> (&theArray.Last() + 1);
  89     }
  90
  91     //! Assignment
  92     Iterator& operator= (const Iterator& theOther)
  93     {
  94       myPtrCur = theOther.myPtrCur;
  95       myPtrEnd = theOther.myPtrEnd;
  96       return *this;
  97     }
  98
  99     //! Check end
 100     Standard_Boolean More (void) const
 101     { return myPtrCur < myPtrEnd; }
 102
 103     //! Increment operator
 104     void Next (void)
 105     { ++myPtrCur; }
 106
 107     //! Decrement operator
 108     void Previous()
 109     { --myPtrCur; }
 110
 111     //! Offset operator.
 112     void Offset (ptrdiff_t theOffset)
 113     { myPtrCur += theOffset; }
 114
 115     //! Difference operator.
 116     ptrdiff_t Differ (const Iterator& theOther) const
 117     { return myPtrCur - theOther.myPtrCur; }
 118
 119     //! Constant value access
 120     const TheItemType& Value (void) const
 121     { return *myPtrCur; }
 122
 123     //! Variable value access
 124     TheItemType& ChangeValue (void) const
 125     { return *myPtrCur; }
 126
 127     //! Performs comparison of two iterators
 128     Standard_Boolean IsEqual (const Iterator& theOther) const
 129     { return myPtrCur == theOther.myPtrCur; }
 130
 131   private:
 132     TheItemType* myPtrCur; //!< Pointer to the current element in the array
 133     TheItemType* myPtrEnd; //!< Pointer to the past-the-end element in the array
 134   }; // End of the nested class Iterator
 135
 136   //! Shorthand for a regular iterator type.
 137   typedef NCollection_StlIterator<std::random_access_iterator_tag, Iterator, TheItemType, false> iterator;
 138
 139   //! Shorthand for a constant iterator type.
 140   typedef NCollection_StlIterator<std::random_access_iterator_tag, Iterator, TheItemType, true> const_iterator;
 141
 142   //! Returns an iterator pointing to the first element in the array.
 143   iterator begin() const { return Iterator (*this, false); }
 144
 145   //! Returns an iterator referring to the past-the-end element in the array.
 146   iterator end() const { return Iterator (*this, true); }
 147
 148   //! Returns a const iterator pointing to the first element in the array.
 149   const_iterator cbegin() const { return Iterator (*this, false); }
 150
 151   //! Returns a const iterator referring to the past-the-end element in the array.
 152   const_iterator cend() const { return Iterator (*this, true); }
 153
 154  public:
 155   // ---------- PUBLIC METHODS ------------
 156
 157   //! Empty constructor; should be used with caution.
 158   //! @sa methods Resize() and Move().
 159   NCollection_Array1()
 160   : myLowerBound (1),
 161     myUpperBound (0),
 162     myDeletable  (Standard_False),
 163     myData (NULL)
 164   {
 165     //
 166   }
 167
 168   //! Constructor
 169   NCollection_Array1(const Standard_Integer theLower,
 170                      const Standard_Integer theUpper) :
 171                 myLowerBound                             (theLower),
 172                 myUpperBound                             (theUpper),
 173                 myDeletable                              (Standard_True)
 174   {
 175     Standard_RangeError_Raise_if (theUpper < theLower, "NCollection_Array1::Create");
 176     TheItemType* pBegin = new TheItemType[Length()];
 177     Standard_OutOfMemory_Raise_if (!pBegin, "NCollection_Array1 : Allocation failed");
 178
 179     myData = pBegin - theLower;
 180   }
 181
 182   //! Copy constructor
 183   NCollection_Array1 (const NCollection_Array1& theOther) :
 184     myLowerBound                                (theOther.Lower()),
 185     myUpperBound                                (theOther.Upper()),
 186     myDeletable                                 (Standard_True)
 187   {
 188     TheItemType* pBegin = new TheItemType[Length()];
 189     Standard_OutOfMemory_Raise_if (!pBegin, "NCollection_Array1 : Allocation failed");
 190     myData = pBegin - myLowerBound;
 191
 192     Assign (theOther);
 193   }
 194
 195 #ifndef OCCT_NO_RVALUE_REFERENCE
 196   //! Move constructor
 197   NCollection_Array1 (NCollection_Array1&& theOther)
 198   : myLowerBound (theOther.myLowerBound),
 199     myUpperBound (theOther.myUpperBound),
 200     myDeletable  (theOther.myDeletable),
 201     myData       (theOther.myData)
 202   {
 203     theOther.myDeletable  = false;
 204   }
 205 #endif
 206
 207   //! C array-based constructor.
 208   //!
 209   //! Makes this array to use the buffer pointed by theBegin
 210   //! instead of allocating it dynamically.
 211   //! Argument theBegin should be a reference to the first element
 212   //! of the pre-allocated buffer (usually local C array buffer),
 213   //! with size at least theUpper - theLower + 1 items.
 214   //!
 215   //! Warning: returning array object created using this constructor
 216   //! from function by value will result in undefined behavior
 217   //! if compiler performs return value optimization (this is likely
 218   //! to be true for all modern compilers in release mode).
 219   //! The same happens if array is copied using Move() function
 220   //! or move constructor and target object's lifespan is longer
 221   //! than that of the buffer.
 222   NCollection_Array1 (const TheItemType& theBegin,
 223                       const Standard_Integer theLower,
 224                       const Standard_Integer theUpper) :
 225     myLowerBound                                (theLower),
 226     myUpperBound                                (theUpper),
 227     myDeletable                                 (Standard_False)
 228   {
 229     Standard_RangeError_Raise_if (theUpper < theLower, "NCollection_Array1::Create");
 230   #if (defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6))
 231     // gcc emits -Warray-bounds warning when NCollection_Array1 is initialized
 232     // from local array with lower index 1 (so that (&theBegin - 1) points out of array bounds).
 233     // NCollection_Array1 initializes myData with a shift to avoid this shift within per-element access.
 234     // It is undesired changing this logic, and -Warray-bounds is not useful here.
 235     #pragma GCC diagnostic push
 236     #pragma GCC diagnostic ignored "-Warray-bounds"
 237   #endif
 238     myData = (TheItemType *) &theBegin - theLower;
 239   #if (defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6))
 240     #pragma GCC diagnostic pop
 241   #endif
 242   }
 243
 244   //! Initialise the items with theValue
 245   void Init (const TheItemType& theValue)
 246   {
 247     TheItemType *pCur = &myData[myLowerBound], *pEnd=&myData[myUpperBound];
 248     for(; pCur <= pEnd; pCur++)
 249       *pCur = (TheItemType&) theValue;
 250   }
 251
 252   //! Size query
 253   Standard_Integer Size (void) const
 254   { return Length(); }
 255   //! Length query (the same)
 256   Standard_Integer Length (void) const
 257   { return (myUpperBound-myLowerBound+1); }
 258
 259   //! Return TRUE if array has zero length.
 260   Standard_Boolean IsEmpty() const { return myUpperBound < myLowerBound; }
 261
 262   //! Lower bound
 263   Standard_Integer Lower (void) const
 264   { return myLowerBound; }
 265   //! Upper bound
 266   Standard_Integer Upper (void) const
 267   { return myUpperBound; }
 268
 269   //! myDeletable flag
 270   Standard_Boolean IsDeletable (void) const
 271   { return myDeletable; }
 272
 273   //! IsAllocated flag - for naming compatibility
 274   Standard_Boolean IsAllocated (void) const
 275   { return myDeletable; }
 276
 277   //! Copies data of theOther array to this.
 278   //! This array should be pre-allocated and have the same length as theOther;
 279   //! otherwise exception Standard_DimensionMismatch is thrown.
 280   NCollection_Array1& Assign (const NCollection_Array1& theOther)
 281   {
 282     if (&theOther == this)
 283       return *this;
 284
 285     Standard_DimensionMismatch_Raise_if (Length() != theOther.Length(), "NCollection_Array1::operator=");
 286     if (myData == NULL)
 287     {
 288       return *this;
 289     }
 290
 291     TheItemType * pMyItem        = &myData[myLowerBound];
 292     TheItemType * const pEndItem = &(theOther.myData)[theOther.myUpperBound];
 293     TheItemType * pItem          = &(theOther.myData)[theOther.myLowerBound];
 294     while (pItem <= pEndItem) * pMyItem ++ = * pItem ++;
 295     return *this;
 296   }
 297
 298   //! Move assignment.
 299   //! This array will borrow all the data from theOther.
 300   //! The moved object will keep pointer to the memory buffer and
 301   //! range, but it will not free the buffer on destruction.
 302   NCollection_Array1& Move (NCollection_Array1& theOther)
 303   {
 304     if (&theOther == this)
 305     {
 306       return *this;
 307     }
 308
 309     if (myDeletable)
 310     {
 311       delete[] &myData[myLowerBound];
 312     }
 313
 314     myLowerBound = theOther.myLowerBound;
 315     myUpperBound = theOther.myUpperBound;
 316     myDeletable  = theOther.myDeletable;
 317     myData       = theOther.myData;
 318
 319     theOther.myDeletable = Standard_False;
 320
 321     return *this;
 322   }
 323
 324   //! Assignment operator; @sa Assign()
 325   NCollection_Array1& operator= (const NCollection_Array1& theOther)
 326   {
 327     return Assign (theOther);
 328   }
 329
 330 #ifndef OCCT_NO_RVALUE_REFERENCE
 331   //! Move assignment operator; @sa Move()
 332   NCollection_Array1& operator= (NCollection_Array1&& theOther)
 333   {
 334     return Move (theOther);
 335   }
 336 #endif
 337
 338   //! @return first element
 339   const TheItemType& First() const
 340   {
 341     return myData[myLowerBound];
 342   }
 343
 344   //! @return first element
 345   TheItemType& ChangeFirst()
 346   {
 347     return myData[myLowerBound];
 348   }
 349
 350   //! @return last element
 351   const TheItemType& Last() const
 352   {
 353     return myData[myUpperBound];
 354   }
 355
 356   //! @return last element
 357   TheItemType& ChangeLast()
 358   {
 359     return myData[myUpperBound];
 360   }
 361
 362   //! Constant value access
 363   const TheItemType& Value (const Standard_Integer theIndex) const
 364   {
 365     Standard_OutOfRange_Raise_if (theIndex < myLowerBound || theIndex > myUpperBound, "NCollection_Array1::Value");
 366     return myData[theIndex];
 367   }
 368
 369   //! operator() - alias to Value
 370   const TheItemType& operator() (const Standard_Integer theIndex) const
 371   { return Value (theIndex); }
 372
 373   //! operator[] - alias to Value
 374   const TheItemType& operator[] (Standard_Integer theIndex) const { return Value (theIndex); }
 375
 376   //! Variable value access
 377   TheItemType& ChangeValue (const Standard_Integer theIndex)
 378   {
 379     Standard_OutOfRange_Raise_if (theIndex < myLowerBound || theIndex > myUpperBound, "NCollection_Array1::ChangeValue");
 380     return myData[theIndex];
 381   }
 382
 383   //! operator() - alias to ChangeValue
 384   TheItemType& operator() (const Standard_Integer theIndex)
 385   { return ChangeValue (theIndex); }
 386
 387   //! operator[] - alias to ChangeValue
 388   TheItemType& operator[] (Standard_Integer theIndex) { return ChangeValue (theIndex); }
 389
 390   //! Set value
 391   void SetValue (const Standard_Integer theIndex,
 392                  const TheItemType&     theItem)
 393   {
 394     Standard_OutOfRange_Raise_if (theIndex < myLowerBound || theIndex > myUpperBound, "NCollection_Array1::SetValue");
 395     myData[theIndex] = theItem;
 396   }
 397
 398   //! Resizes the array to specified bounds.
 399   //! No re-allocation will be done if length of array does not change,
 400   //! but existing values will not be discarded if theToCopyData set to FALSE.
 401   //! @param theLower new lower bound of array
 402   //! @param theUpper new upper bound of array
 403   //! @param theToCopyData flag to copy existing data into new array
 404   void Resize (const Standard_Integer theLower,
 405                const Standard_Integer theUpper,
 406                const Standard_Boolean theToCopyData)
 407   {
 408     Standard_RangeError_Raise_if (theUpper < theLower, "NCollection_Array1::Resize");
 409     const Standard_Integer anOldLen   = Length();
 410     const Standard_Integer aNewLen    = theUpper - theLower + 1;
 411     const Standard_Integer aLowerOld  = myLowerBound;
 412
 413     TheItemType* aBeginOld = &myData[aLowerOld];
 414     myLowerBound = theLower;
 415     myUpperBound = theUpper;
 416     if (aNewLen == anOldLen)
 417     {
 418       myData = aBeginOld - theLower;
 419       return;
 420     }
 421
 422     if (!theToCopyData && myDeletable)
 423     {
 424       delete[] aBeginOld;
 425     }
 426     TheItemType* aBeginNew = new TheItemType[aNewLen];
 427     Standard_OutOfMemory_Raise_if (aBeginNew == NULL, "NCollection_Array1 : Allocation failed");
 428     myData = aBeginNew - theLower;
 429     if (!theToCopyData)
 430     {
 431       myDeletable = Standard_True;
 432       return;
 433     }
 434
 435     const Standard_Integer aLenCopy = Min (anOldLen, aNewLen);
 436     for (Standard_Integer anIter = 0; anIter < aLenCopy; ++anIter)
 437     {
 438       aBeginNew[anIter] = aBeginOld[anIter];
 439     }
 440     if (myDeletable)
 441     {
 442       delete[] aBeginOld;
 443     }
 444     myDeletable = Standard_True;
 445   }
 446
 447   //! Destructor - releases the memory
 448   ~NCollection_Array1 (void)
 449   {
 450     if (myDeletable)
 451       delete [] &(myData[myLowerBound]);
 452   }
 453
 454  protected:
 455   // ---------- PROTECTED FIELDS -----------
 456   Standard_Integer     myLowerBound;
 457   Standard_Integer     myUpperBound;
 458   Standard_Boolean     myDeletable; //!< Flag showing who allocated the array
 459   TheItemType*         myData;      //!< Pointer to '0'th array item
 460 };
 461
 462 #endif