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     //! Check end
  92     Standard_Boolean More (void) const
  93     { return myPtrCur < myPtrEnd; }
  94
  95     //! Increment operator
  96     void Next (void)
  97     { ++myPtrCur; }
  98
  99     //! Decrement operator
 100     void Previous()
 101     { --myPtrCur; }
 102
 103     //! Offset operator.
 104     void Offset (ptrdiff_t theOffset)
 105     { myPtrCur += theOffset; }
 106
 107     //! Difference operator.
 108     ptrdiff_t Differ (const Iterator& theOther) const
 109     { return myPtrCur - theOther.myPtrCur; }
 110
 111     //! Constant value access
 112     const TheItemType& Value (void) const
 113     { return *myPtrCur; }
 114
 115     //! Variable value access
 116     TheItemType& ChangeValue (void) const
 117     { return *myPtrCur; }
 118
 119     //! Performs comparison of two iterators
 120     Standard_Boolean IsEqual (const Iterator& theOther) const
 121     { return myPtrCur == theOther.myPtrCur; }
 122
 123   private:
 124     TheItemType* myPtrCur; //!< Pointer to the current element in the array
 125     TheItemType* myPtrEnd; //!< Pointer to the past-the-end element in the array
 126   }; // End of the nested class Iterator
 127
 128   //! Shorthand for a regular iterator type.
 129   typedef NCollection_StlIterator<std::random_access_iterator_tag, Iterator, TheItemType, false> iterator;
 130
 131   //! Shorthand for a constant iterator type.
 132   typedef NCollection_StlIterator<std::random_access_iterator_tag, Iterator, TheItemType, true> const_iterator;
 133
 134   //! Returns an iterator pointing to the first element in the array.
 135   iterator begin() const { return Iterator (*this, false); }
 136
 137   //! Returns an iterator referring to the past-the-end element in the array.
 138   iterator end() const { return Iterator (*this, true); }
 139
 140   //! Returns a const iterator pointing to the first element in the array.
 141   const_iterator cbegin() const { return Iterator (*this, false); }
 142
 143   //! Returns a const iterator referring to the past-the-end element in the array.
 144   const_iterator cend() const { return Iterator (*this, true); }
 145
 146  public:
 147   // ---------- PUBLIC METHODS ------------
 148
 149   //! Empty constructor; should be used with caution.
 150   //! @sa methods Resize() and Move().
 151   NCollection_Array1()
 152   : myLowerBound (1),
 153     myUpperBound (0),
 154     myDeletable  (Standard_False),
 155     myData (NULL)
 156   {
 157     //
 158   }
 159
 160   //! Constructor
 161   NCollection_Array1(const Standard_Integer theLower,
 162                      const Standard_Integer theUpper) :
 163                 myLowerBound                             (theLower),
 164                 myUpperBound                             (theUpper),
 165                 myDeletable                              (Standard_True)
 166   {
 167     Standard_RangeError_Raise_if (theUpper < theLower, "NCollection_Array1::Create");
 168     TheItemType* pBegin = new TheItemType[Length()];
 169     Standard_OutOfMemory_Raise_if (!pBegin, "NCollection_Array1 : Allocation failed");
 170
 171     myData = pBegin - theLower;
 172   }
 173
 174   //! Copy constructor
 175   NCollection_Array1 (const NCollection_Array1& theOther) :
 176     myLowerBound                                (theOther.Lower()),
 177     myUpperBound                                (theOther.Upper()),
 178     myDeletable                                 (Standard_True)
 179   {
 180     TheItemType* pBegin = new TheItemType[Length()];
 181     Standard_OutOfMemory_Raise_if (!pBegin, "NCollection_Array1 : Allocation failed");
 182     myData = pBegin - myLowerBound;
 183
 184     Assign (theOther);
 185   }
 186
 187 #ifndef OCCT_NO_RVALUE_REFERENCE
 188   //! Move constructor
 189   NCollection_Array1 (NCollection_Array1&& theOther)
 190   : myLowerBound (theOther.myLowerBound),
 191     myUpperBound (theOther.myUpperBound),
 192     myDeletable  (theOther.myDeletable),
 193     myData       (theOther.myData)
 194   {
 195     theOther.myDeletable  = false;
 196   }
 197 #endif
 198
 199   //! C array-based constructor.
 200   //!
 201   //! Makes this array to use the buffer pointed by theBegin
 202   //! instead of allocating it dynamically.
 203   //! Argument theBegin should be a reference to the first element
 204   //! of the pre-allocated buffer (usually local C array buffer),
 205   //! with size at least theUpper - theLower + 1 items.
 206   //!
 207   //! Warning: returning array object created using this constructor
 208   //! from function by value will result in undefined behavior
 209   //! if compiler performs return value optimization (this is likely
 210   //! to be true for all modern compilers in release mode).
 211   //! The same happens if array is copied using Move() function
 212   //! or move constructor and target object's lifespan is longer
 213   //! than that of the buffer.
 214   NCollection_Array1 (const TheItemType& theBegin,
 215                       const Standard_Integer theLower,
 216                       const Standard_Integer theUpper) :
 217     myLowerBound                                (theLower),
 218     myUpperBound                                (theUpper),
 219     myDeletable                                 (Standard_False)
 220   {
 221     Standard_RangeError_Raise_if (theUpper < theLower, "NCollection_Array1::Create");
 222   #if (defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6))
 223     // gcc emits -Warray-bounds warning when NCollection_Array1 is initialized
 224     // from local array with lower index 1 (so that (&theBegin - 1) points out of array bounds).
 225     // NCollection_Array1 initializes myData with a shift to avoid this shift within per-element access.
 226     // It is undesired changing this logic, and -Warray-bounds is not useful here.
 227     #pragma GCC diagnostic push
 228     #pragma GCC diagnostic ignored "-Warray-bounds"
 229   #endif
 230     myData = (TheItemType *) &theBegin - theLower;
 231   #if (defined(__GNUC__) && __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6))
 232     #pragma GCC diagnostic pop
 233   #endif
 234   }
 235
 236   //! Initialise the items with theValue
 237   void Init (const TheItemType& theValue)
 238   {
 239     TheItemType *pCur = &myData[myLowerBound], *pEnd=&myData[myUpperBound];
 240     for(; pCur <= pEnd; pCur++)
 241       *pCur = (TheItemType&) theValue;
 242   }
 243
 244   //! Size query
 245   Standard_Integer Size (void) const
 246   { return Length(); }
 247   //! Length query (the same)
 248   Standard_Integer Length (void) const
 249   { return (myUpperBound-myLowerBound+1); }
 250
 251   //! Return TRUE if array has zero length.
 252   Standard_Boolean IsEmpty() const { return myUpperBound < myLowerBound; }
 253
 254   //! Lower bound
 255   Standard_Integer Lower (void) const
 256   { return myLowerBound; }
 257   //! Upper bound
 258   Standard_Integer Upper (void) const
 259   { return myUpperBound; }
 260
 261   //! myDeletable flag
 262   Standard_Boolean IsDeletable (void) const
 263   { return myDeletable; }
 264
 265   //! IsAllocated flag - for naming compatibility
 266   Standard_Boolean IsAllocated (void) const
 267   { return myDeletable; }
 268
 269   //! Copies data of theOther array to this.
 270   //! This array should be pre-allocated and have the same length as theOther;
 271   //! otherwise exception Standard_DimensionMismatch is thrown.
 272   NCollection_Array1& Assign (const NCollection_Array1& theOther)
 273   {
 274     if (&theOther == this)
 275       return *this;
 276
 277     Standard_DimensionMismatch_Raise_if (Length() != theOther.Length(), "NCollection_Array1::operator=");
 278     if (myData == NULL)
 279     {
 280       return *this;
 281     }
 282
 283     TheItemType * pMyItem        = &myData[myLowerBound];
 284     TheItemType * const pEndItem = &(theOther.myData)[theOther.myUpperBound];
 285     TheItemType * pItem          = &(theOther.myData)[theOther.myLowerBound];
 286     while (pItem <= pEndItem) * pMyItem ++ = * pItem ++;
 287     return *this;
 288   }
 289
 290   //! Move assignment.
 291   //! This array will borrow all the data from theOther.
 292   //! The moved object will keep pointer to the memory buffer and
 293   //! range, but it will not free the buffer on destruction.
 294   NCollection_Array1& Move (NCollection_Array1& theOther)
 295   {
 296     if (&theOther == this)
 297     {
 298       return *this;
 299     }
 300
 301     if (myDeletable)
 302     {
 303       delete[] &myData[myLowerBound];
 304     }
 305
 306     myLowerBound = theOther.myLowerBound;
 307     myUpperBound = theOther.myUpperBound;
 308     myDeletable  = theOther.myDeletable;
 309     myData       = theOther.myData;
 310
 311     theOther.myDeletable = Standard_False;
 312
 313     return *this;
 314   }
 315
 316   //! Assignment operator; @sa Assign()
 317   NCollection_Array1& operator= (const NCollection_Array1& theOther)
 318   {
 319     return Assign (theOther);
 320   }
 321
 322 #ifndef OCCT_NO_RVALUE_REFERENCE
 323   //! Move assignment operator; @sa Move()
 324   NCollection_Array1& operator= (NCollection_Array1&& theOther)
 325   {
 326     return Move (theOther);
 327   }
 328 #endif
 329
 330   //! @return first element
 331   const TheItemType& First() const
 332   {
 333     return myData[myLowerBound];
 334   }
 335
 336   //! @return first element
 337   TheItemType& ChangeFirst()
 338   {
 339     return myData[myLowerBound];
 340   }
 341
 342   //! @return last element
 343   const TheItemType& Last() const
 344   {
 345     return myData[myUpperBound];
 346   }
 347
 348   //! @return last element
 349   TheItemType& ChangeLast()
 350   {
 351     return myData[myUpperBound];
 352   }
 353
 354   //! Constant value access
 355   const TheItemType& Value (const Standard_Integer theIndex) const
 356   {
 357     Standard_OutOfRange_Raise_if (theIndex < myLowerBound || theIndex > myUpperBound, "NCollection_Array1::Value");
 358     return myData[theIndex];
 359   }
 360
 361   //! operator() - alias to Value
 362   const TheItemType& operator() (const Standard_Integer theIndex) const
 363   { return Value (theIndex); }
 364
 365   //! operator[] - alias to Value
 366   const TheItemType& operator[] (Standard_Integer theIndex) const { return Value (theIndex); }
 367
 368   //! Variable value access
 369   TheItemType& ChangeValue (const Standard_Integer theIndex)
 370   {
 371     Standard_OutOfRange_Raise_if (theIndex < myLowerBound || theIndex > myUpperBound, "NCollection_Array1::ChangeValue");
 372     return myData[theIndex];
 373   }
 374
 375   //! operator() - alias to ChangeValue
 376   TheItemType& operator() (const Standard_Integer theIndex)
 377   { return ChangeValue (theIndex); }
 378
 379   //! operator[] - alias to ChangeValue
 380   TheItemType& operator[] (Standard_Integer theIndex) { return ChangeValue (theIndex); }
 381
 382   //! Set value
 383   void SetValue (const Standard_Integer theIndex,
 384                  const TheItemType&     theItem)
 385   {
 386     Standard_OutOfRange_Raise_if (theIndex < myLowerBound || theIndex > myUpperBound, "NCollection_Array1::SetValue");
 387     myData[theIndex] = theItem;
 388   }
 389
 390   //! Resizes the array to specified bounds.
 391   //! No re-allocation will be done if length of array does not change,
 392   //! but existing values will not be discarded if theToCopyData set to FALSE.
 393   //! @param theLower new lower bound of array
 394   //! @param theUpper new upper bound of array
 395   //! @param theToCopyData flag to copy existing data into new array
 396   void Resize (const Standard_Integer theLower,
 397                const Standard_Integer theUpper,
 398                const Standard_Boolean theToCopyData)
 399   {
 400     Standard_RangeError_Raise_if (theUpper < theLower, "NCollection_Array1::Resize");
 401     const Standard_Integer anOldLen   = Length();
 402     const Standard_Integer aNewLen    = theUpper - theLower + 1;
 403     const Standard_Integer aLowerOld  = myLowerBound;
 404
 405     TheItemType* aBeginOld = &myData[aLowerOld];
 406     myLowerBound = theLower;
 407     myUpperBound = theUpper;
 408     if (aNewLen == anOldLen)
 409     {
 410       myData = aBeginOld - theLower;
 411       return;
 412     }
 413
 414     if (!theToCopyData && myDeletable)
 415     {
 416       delete[] aBeginOld;
 417     }
 418     TheItemType* aBeginNew = new TheItemType[aNewLen];
 419     Standard_OutOfMemory_Raise_if (aBeginNew == NULL, "NCollection_Array1 : Allocation failed");
 420     myData = aBeginNew - theLower;
 421     if (!theToCopyData)
 422     {
 423       myDeletable = Standard_True;
 424       return;
 425     }
 426
 427     const Standard_Integer aLenCopy = Min (anOldLen, aNewLen);
 428     for (Standard_Integer anIter = 0; anIter < aLenCopy; ++anIter)
 429     {
 430       aBeginNew[anIter] = aBeginOld[anIter];
 431     }
 432     if (myDeletable)
 433     {
 434       delete[] aBeginOld;
 435     }
 436     myDeletable = Standard_True;
 437   }
 438
 439   //! Destructor - releases the memory
 440   ~NCollection_Array1 (void)
 441   {
 442     if (myDeletable)
 443       delete [] &(myData[myLowerBound]);
 444   }
 445
 446  protected:
 447   // ---------- PROTECTED FIELDS -----------
 448   Standard_Integer     myLowerBound;
 449   Standard_Integer     myUpperBound;
 450   Standard_Boolean     myDeletable; //!< Flag showing who allocated the array
 451   TheItemType*         myData;      //!< Pointer to '0'th array item
 452 };
 453
 454 #endif