GL Studio C++ Runtime API
dynamic_array.h
Go to the documentation of this file.
1 /// \file
2 /// \brief The disti::DynamicArray class. A templated array of objects capable of dynamically growing.
3 ///
4 /// \par Copyright Information
5 ///
6 /// Copyright (c) 2020 by The DiSTI Corporation.<br>
7 /// 11301 Corporate Blvd., Suite 100<br>
8 /// Orlando, Florida 32817<br>
9 /// USA<br>
10 /// <br>
11 /// All rights reserved.<br>
12 ///
13 /// This Software contains proprietary trade secrets of DiSTI and may not be
14 /// reproduced, in whole or part, in any form, or by any means of electronic,
15 /// mechanical, or otherwise, without the written permission of DiSTI. Said
16 /// permission may be derived through the purchase of applicable DiSTI product
17 /// licenses which detail the distribution rights of this content and any
18 /// Derivative Works based on this or other copyrighted DiSTI Software.
19 ///
20 /// NO WARRANTY. THE SOFTWARE IS PROVIDED "AS-IS," WITHOUT WARRANTY OF ANY KIND,
21 /// AND ANY USE OF THIS SOFTWARE PRODUCT IS AT YOUR OWN RISK. TO THE MAXIMUM EXTENT
22 /// PERMITTED BY APPLICABLE LAW, DISTI AND ITS SUPPLIERS DISCLAIM ALL WARRANTIES
23 /// AND CONDITIONS, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
24 /// IMPLIED WARRANTIES AND CONDITIONS OF MERCHANTABILITY AND/OR FITNESS FOR A
25 /// PARTICULAR PURPOSE, TITLE, AND NON-INFRINGEMENT, WITH REGARD TO THE SOFTWARE.
26 ///
27 /// LIMITATION OF LIABILITY. TO THE MAXIMUM EXTENT PERMITTED BY APPLICABLE LAW,
28 /// IN NO EVENT SHALL DISTI OR ITS SUPPLIERS BE LIABLE FOR ANY SPECIAL, INCIDENTAL,
29 /// INDIRECT, OR CONSEQUENTIAL DAMAGES WHATSOEVER (INCLUDING, WITHOUT LIMITATION,
30 /// DAMAGES FOR LOSS OF BUSINESS PROFITS, BUSINESS INTERRUPTION, LOSS OF BUSINESS
31 /// INFORMATION, OR ANY OTHER PECUNIARY LOSS) ARISING OUT OF THE USE OF OR
32 /// INABILITY TO USE THE SOFTWARE, EVEN IF DISTI HAS BEEN ADVISED OF THE POSSIBILITY
33 /// OF SUCH DAMAGES. DISTI'S ENTIRE LIABILITY AND YOUR EXCLUSIVE REMEDY SHALL NOT
34 /// EXCEED FIVE DOLLARS (US$5.00).
35 ///
36 /// The aforementioned terms and restrictions are governed by the laws of the
37 /// State of Florida and the United States of America.
38 
39 #ifndef INCLUDED_DISTI_DYNAMIC_ARRAY_H
40 #define INCLUDED_DISTI_DYNAMIC_ARRAY_H
41 
42 #include "disti_assert.h"
43 #include "gls_cpp_lang_support.h"
44 #include "gls_include.h"
45 
46 #include <climits>
47 #include <cstddef>
48 #include <cstdlib>
49 #include <new>
50 
51 #if defined( DISTI_HAS_CPP11 )
52 # include <initializer_list>
53 #endif
54 
55 #if defined( DISTI_HAS_TYPE_TRAITS )
56 # include <type_traits>
57 #endif
58 #if defined( DISTI_HAS_RVAL_REFS )
59 # include <utility>
60 #endif
61 
62 namespace disti
63 {
64 // Forward declarations
65 // clang-format off
66 template<class T, bool Obsolete> class DynamicArray;
67 template<class T, bool Obsolete, class U> unsigned FindIndexOf( const DynamicArray<T, Obsolete>& array, const U& object );
68 template<class T, bool Obsolete> void DeleteEachAndClear( DynamicArray<T, Obsolete>& array );
69 // clang-format on
70 
71 /// Constant returned by FindIndexOf() if the item is not found.
72 const unsigned g_itemNotFound = UINT_MAX;
73 
74 /// A templated array of objects. The array dynamically resizes as needed.
75 /// \tparam T The type of the objects contained.
76 /// \tparam Obsolete Obsolete parameter retained for backwards compatibility. Please ignore.
77 template<class T, bool Obsolete = true>
78 class DynamicArray DISTI_FINAL
79 {
80 public:
81  typedef T ElementType;
82 
83  /// DynamicArray constructor
84  /// \param initialCapacity The initial number of elements to be allocated for the array
85  explicit DynamicArray( unsigned initialCapacity = 0 )
86  : _capacity( 0 )
87  , _count( 0 )
88  , _objects( NULL )
89  {
90  if( initialCapacity != 0 )
91  {
92  Capacity( initialCapacity );
93  }
94  }
95 
96 #if defined( DISTI_HAS_CPP11 )
97  /// Construct from a list of items, e.g.:
98  /// \code
99  /// const auto a = DynamicArray<int>{ 1, 2, 3, 4 };
100  /// \endcode
101  DynamicArray( std::initializer_list<T> list )
102  : _capacity( 0 )
103  , _count( 0 )
104  , _objects( NULL )
105  {
106  const auto capacity = static_cast<unsigned>( list.size() );
107  if( capacity != 0 )
108  {
109  Capacity( capacity );
110  for( auto&& item : list )
111  {
112  PushBack( std::move( item ) );
113  }
114  }
115  }
116 #endif
117 
118  /// Initialize this array by deep-copying \a other
120  : _capacity( 0 )
121  , _count( 0 )
122  , _objects( NULL )
123  {
124  DeepCopyFrom( other );
125  }
126 
127  /// Initialize this array by deep-copying \a other
129  : _capacity( 0 )
130  , _count( 0 )
131  , _objects( NULL )
132  {
133  DeepCopyFrom( other );
134  }
135 
136  /// Assign this array by deep-copying \a other
138  {
139  if( this != &other )
140  {
141  DeepCopyFrom( other );
142  }
143  return *this;
144  }
145 
146  /// Assign this array by deep-copying \a other
148  {
149  if( this != &other )
150  {
151  DeepCopyFrom( other );
152  }
153  return *this;
154  }
155 
156 #if defined( DISTI_HAS_RVAL_REFS )
157  /// Construct this array by taking ownership of \a other's contents
159  : _capacity( other._capacity )
160  , _count( other._count )
161  , _objects( other._objects )
162  {
163  // Relieve of ownership
164  other._capacity = 0;
165  other._count = 0;
166  other._objects = NULL;
167  }
168 
169  /// Construct this array by taking ownership of \a other's contents
171  : _capacity( other._capacity )
172  , _count( other._count )
173  , _objects( other._objects )
174  {
175  // Relieve of ownership
176  other._capacity = 0;
177  other._count = 0;
178  other._objects = NULL;
179  }
180 
181  /// Assign this array by clearing any current contents and then taking ownership of \a other's contents
183  {
184  StealFrom( std::move( other ) );
185  return *this;
186  }
187 
189  {
190  StealFrom( std::move( other ) );
191  return *this;
192  }
193 #endif
194 
195  /// DynamicArray destructor. Clears the array but does not delete the objects being pointed to by the array.
197  {
198  StripCapacity();
199  }
200 
201  /// Returns the number of elements used of this dynamic array
202  /// \return The number of elements used of the array (number of elements)
203  /// \note Similar to std::vector::size()
204  unsigned Count() const { return _count; }
205 
206  /// Set the "Count" value for this array, destroying items or creating default-constructed items as needed.
207  /// \note Similar to std::vector::resize()
208  void Count( const unsigned newCount )
209  {
210  if( newCount > _capacity )
211  {
212  Capacity( newCount );
213  }
214 
215  if( newCount > _count )
216  {
217  // If we're increasing our count, then we need to initialize the new values manually since
218  // setting the capacity doesn't deal with initializing objects.
219  for( unsigned i = _count; i < newCount; ++i )
220  {
221  new( _objects + i ) T(); // Use placement-new to construct at this memory location
222  }
223  }
224  else
225  {
226  // If we're lowering our count, we need to destroy some objects because we want them to
227  // clean up after themselves (e.g., if they have some resource they need to close). We
228  // can't call delete because this container manually manages the memory the object sits in.
229  Destroy( newCount, _count );
230  }
231 
232  _count = newCount;
233  }
234 
235  /// Clears the list so Count() is zero, destroying all items. Does not strip capacity. Shorthand for Count( 0 ).
236  /// \note Similar to std::vector::clear().
237  /// \sa StripCapacity()
238  void Clear()
239  {
240  Count( 0 );
241  }
242 
243  /// Returns the capacity of this dynamic array
244  /// \note Similar to std::vector::capacity()
245  unsigned Capacity() const { return _capacity; }
246 
247  /// Reserves space for \a newCapacity elements in the array, reallocating as needed.
248  /// \param newCapacity The new number of elements reserved in the array.
249  /// \note Similar to std::vector::reserve(), but does lower capacity when asked.
250  void Capacity( const unsigned newCapacity )
251  {
252  // Case 1: Don't reallocate if the capacity doesn't change
253  if( newCapacity == _capacity )
254  {
255  return;
256  }
257  // Case 2: Erasing all capacity
258  else if( 0 == newCapacity )
259  {
260  Destroy( 0, _count );
261  std::free( _objects );
262  _objects = NULL;
263  _capacity = 0;
264  _count = 0;
265  return;
266  }
267 
268  // Case 3: Change the capacity
269 
270  // Allocate the new memory using malloc since we will control construction
271  // and destruction separately from memory allocation.
272  // Note: Don't set any member vars until after the malloc so that we have
273  // perfect roll-back if malloc fails.
274  T* const newObjects = reinterpret_cast<T*>( std::malloc( sizeof( T ) * newCapacity ) );
275  if( !newObjects )
276  {
277  throw std::bad_alloc();
278  }
279 
280  // If we're shrinking the capacity, destroy the obsolete objects
281  if( newCapacity < _count )
282  {
283  Destroy( newCapacity, _count );
284  _count = newCapacity;
285  }
286 
287  // Move the old objects over to the new array, if needed
288  if( _objects )
289  {
290  // Move only the active objects, not the potentially uninitialized ones
291  for( unsigned i = 0; i < _count; i++ )
292  {
293  Assign( newObjects[ i ], DISTI_RVAL_MOVE( _objects[ i ] ) );
294  }
295 
296  // Release the old memory
297  std::free( _objects );
298  }
299 
300  // Own the new objects
301  _objects = newObjects;
302  _capacity = newCapacity;
303  }
304 
305  /// Remove all capacity, destroying any extant items (but deleting any pointees, if the item is a pointer; for that, see DeleteEachAndClear()).
306  /// \sa Clear(), DeleteEachAndClear()
307  void StripCapacity() { Capacity( 0 ); }
308 
309  /// Attempts to insert the object into the list at the specified location. If the
310  /// specified location is beyond the array bounds, the object is inserted at the next
311  /// position in the array.
312  /// \param object The object to insert
313  /// \param loc The index location to insert into
314  /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
315  /// \note Similar to std::vector::insert( object, begin(*this) + loc );
316  unsigned Insert( const T& object, unsigned loc )
317  {
318  return InsertImpl( object, loc );
319  }
320 
321  /// Adds the specified object into the list, at the end of the list
322  /// \param object A pointer to the object to add
323  /// \return Where the object was inserted
324  /// \note Similar to std::vector::push_back()
325  unsigned PushBack( const T& object )
326  {
327  InsertImpl( object, _count );
328  return _count - 1;
329  }
330 
331  /// Removes the last item in the array. If the array is empty, it has no effect.
332  void PopBack()
333  {
334  if( _count > 0 )
335  {
336  Count( _count - 1 );
337  }
338  }
339 
340  /// Returns the last element in the array.
341  /// \throws DistiException if array is empty.
342  T& Back()
343  {
344  GLS_VERIFY( !IsEmpty() );
345  return _objects[ _count - 1 ];
346  }
347 
348  /// Returns the last element in the array.
349  /// \throws DistiException if array is empty.
350  const T& Back() const
351  {
352  GLS_VERIFY( !IsEmpty() );
353  return _objects[ _count - 1 ];
354  }
355 
356  /// Adds the specified \a object at the head of the list.
357  /// \note Similar to std::vector::insert( object, begin(*this) );
358  /// \note Prefer PushBack() instead to avoid inefficiencies.
359  void PushFront( const T& object )
360  {
361  InsertImpl( object, 0 );
362  }
363 
364  // Extra rvalue overloads for efficiency, where available.
365 #if defined( DISTI_HAS_RVAL_REFS )
366  /// Attempts to insert the object into the list at the specified location. If the
367  /// specified location is beyond the array bounds, the object is inserted at the next
368  /// position in the array.
369  /// \param object The object to insert
370  /// \param loc The index location to insert into
371  /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
372  unsigned Insert( T&& object, unsigned loc )
373  {
374  return InsertImpl( std::move( object ), loc );
375  }
376 
377  /// Adds the specified \a object into the list, at the end of the list
378  /// \return Where the object was inserted
379  unsigned PushBack( T&& object )
380  {
381  return InsertImpl( std::move( object ), _count );
382  }
383 
384  /// Adds the specified \a object at the head of the list.
385  /// \note Similar to std::vector::insert( object, begin(*this) );
386  /// \note Prefer PushBack() instead to avoid inefficiencies.
387  void PushFront( T&& object )
388  {
389  InsertImpl( std::move( object ), 0 );
390  }
391 #endif
392 
393  /// Deletes the specified object from the list. Does not delete it, if a pointer.
394  /// \param object A pointer to the object to delete
395  /// \return true if object was found and deleted else false
396  bool Erase( const T& object )
397  {
398  const unsigned loc = FindIndexOf( *this, object );
399  if( loc != g_itemNotFound )
400  {
401  return EraseAt( loc );
402  }
403  return false;
404  }
405 
406  /// Removes the object at the specified index. (Does not delete it, if pointer.)
407  /// \param index Index of the object to delete
408  /// \return true if object was found and deleted else false
409  bool EraseAt( const unsigned index )
410  {
411  if( index >= _count )
412  {
413  return false;
414  }
415 
416  // Destroy the object in question
417  Destroy( _objects[ index ] );
418 
419  // Shift all items down on top of the deleted item
420  for( unsigned j = index; j < _count - 1u; j++ )
421  {
422  Assign( _objects[ j ], DISTI_RVAL_MOVE( _objects[ j + 1u ] ) );
423  }
424 
425  _count--;
426 
427  return true;
428  }
429 
430  /// Overload of array operator to get element at desired index
431  /// \note Resizes if \a index exceeds Capacity() or Count().
432  T& operator[]( const unsigned index )
433  {
434  // This gets an element, resizing the array if needed
435  if( index >= _capacity )
436  {
437  Count( index + 1 );
438  }
439  else if( index >= _count )
440  {
441  for( unsigned i = _count; i <= index; ++i )
442  {
443  Assign( _objects[ i ], T() );
444  }
445 
446  _count = index + 1;
447  }
448 
449  return _objects[ index ];
450  }
451 
452  /// Overload of array operator to get element at desired index
453  /// \note Does not resize if \a index exceeds Capacity() or Count().
454  const T& operator[]( const unsigned index ) const
455  {
456  GLS_ASSERT( index < _capacity && index < _count );
457  return _objects[ index ];
458  }
459 
460  /// Return the internal array pointer
461  /// \note If you call any non-const methods on this object it may invalidate the pointer.
463  {
464  return _objects;
465  }
466 
467  /// Return the internal array pointer
468  /// \note If you call any non-const methods on this object it may invalidate the pointer.
469  const T* InternalArray() const
470  {
471  return _objects;
472  }
473 
474  /// \return true if the list is empty
475  bool IsEmpty() const
476  {
477  return ( _count == 0 );
478  }
479 
480  ///////////////////////////////////////////////////////////////////////////////////////////////
481  // The following functions have been deprecated but are retained for now for backwards
482  // compatibility. All new code should use their noted replacements.
483  ///////////////////////////////////////////////////////////////////////////////////////////////
484 
485  /// Returns the capacity of this array
486  /// \deprecated Renamed to Capacity() for clarity.
487  /// \note similar to std::vector::capacity()
488  DISTI_DEPRECATED( "Renamed to Capacity() for clarity." )
489  unsigned Size() const { return Capacity(); }
490 
491  /// Reserves space for \a newCapacity elements in the array, reallocating as needed.
492  /// \param newCapacity The new number of elements reserved in the array
493  /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
494  /// \note similar to std::vector::reserve()
495  /// \deprecated Renamed to Capacity() for clarity.
496  DISTI_DEPRECATED( "Renamed to Capacity() for clarity." )
497  void Size( unsigned newCapacity )
498  {
499  Capacity( newCapacity );
500  }
501 
502  /// Attempts to insert the object into the list at the specified location. If the
503  /// specified location is beyond the array bounds, the object is inserted at the next
504  /// position in the array.
505  /// \param object The object to insert
506  /// \param loc The index location to insert into
507  /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
508  /// \note Similar to std::vector::insert()
509  /// \deprecated Use Insert( object, loc ) instead.
510  DISTI_DEPRECATED( "Use Insert( object, loc ) instead." )
511  unsigned InsertObject( const T& object, unsigned loc )
512  {
513  return Insert( object, loc );
514  }
515 
516  /// Adds the specified \a object into the list, at the end of the list
517  /// \return Where the object was inserted
518  /// \note similar to std::vector::push_back()
519  /// \deprecated Use PushBack( object ) instead.
520  DISTI_DEPRECATED( "Use PushBack( object ) instead." )
521  unsigned InsertObject( const T& object )
522  {
523  return PushBack( object );
524  }
525 
526  /// Insert the object into the list at the specified location
527  /// \param object The object to insert
528  /// \param loc The index location to insert into
529  /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
530  /// \note similar to std::vector::insert()
531  /// \deprecated Use Insert( object, loc + 1 ) instead.
532  DISTI_DEPRECATED( "Use Insert( object, loc + 1 ) instead." )
533  unsigned InsertObjectAfter( const T& object, unsigned loc )
534  {
535  return Insert( object, loc + 1 );
536  }
537 
538  /// Adds the specified \a object into the list, at the head of the list
539  /// Treats the list like a stack, hence the name Push
540  /// \note Similar to std::vector::insert( object, begin(*this) );
541  /// \deprecated Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies.
542  DISTI_DEPRECATED( "Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies." )
543  void PushObject( const T& object )
544  {
545  PushFront( object );
546  }
547 
548  // Extra rvalue overloads for efficiency, where available.
549 #if defined( DISTI_HAS_RVAL_REFS )
550  /// Attempts to insert the object into the list at the specified location. If the
551  /// specified location is beyond the array bounds, the object is inserted at the next
552  /// position in the array.
553  /// \param object The object to insert
554  /// \param loc The index location to insert into
555  /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
556  /// \note Similar to std::vector::insert()
557  /// \deprecated Use Insert( object, loc ) instead.
558  DISTI_DEPRECATED( "Use Insert( object, loc ) instead." )
559  void InsertObject( T&& object, unsigned loc )
560  {
561  Insert( std::move( object ), loc );
562  }
563 
564  /// Adds the specified \a object into the list, at the end of the list
565  /// \return Where the object was inserted
566  /// \note Similar to std::vector::push_back()
567  /// \deprecated Use PushBack( object ) instead.
568  DISTI_DEPRECATED( "Use PushBack( object ) instead." )
569  unsigned InsertObject( T&& object )
570  {
571  return PushBack( std::move( object ) );
572  }
573 
574  /// Insert the object into the list at the specified location
575  /// \param object The object to insert
576  /// \param loc The index location to insert into
577  /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
578  /// \note Similar to std::vector::insert()
579  /// \deprecated Use Insert( object, loc + 1 ) instead.
580  DISTI_DEPRECATED( "Use Insert( object, loc + 1 ) instead." )
581  void InsertObjectAfter( T&& object, unsigned loc )
582  {
583  Insert( std::move( object ), loc + 1 );
584  }
585 
586  /// Adds the specified \a object at the head of the list.
587  /// \note This must move or copy all existing items, so it may be expensive.
588  /// \note Similar to std::vector::insert( object, begin(*this) );
589  /// \deprecated Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies.
590  DISTI_DEPRECATED( "Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies." )
591  void PushObject( T&& object )
592  {
593  PushFront( std::move( object ) );
594  }
595 #endif
596 
597  /// Removes the object, shrinking the array count. (Does not delete it, if pointer.)
598  /// \param object A pointer to the object to delete
599  /// \return true if object was found and deleted else false
600  /// \note Similar to std::vector::erase()
601  /// \deprecated Renamed EraseAt() for clarity.
602  DISTI_DEPRECATED( "Renamed Erase() for clarity." )
603  bool DeleteObject( const T& object )
604  {
605  return Erase( object );
606  }
607 
608  /// Removes the object at the specified index. (Does not delete it, if pointer.)
609  /// \param index Index of the object to delete
610  /// \return true if object was found and removed else false
611  /// \note Similar to std::vector::erase()
612  /// \deprecated Renamed EraseAt() for clarity.
613  DISTI_DEPRECATED( "Renamed EraseAt() for clarity." )
614  bool DeleteObjectAtIndex( const unsigned index )
615  {
616  return EraseAt( index );
617  }
618 
619  /// Calls delete on each element and then clears the list.
620  /// \deprecated Use the non-member function DeleteEachAndClear( dynamicArray ) instead.
621  DISTI_DEPRECATED( "Use the non-member function DeleteEachAndClear( dynamicArray ) instead." )
622  void EmptyList()
623  {
624  DeleteEachAndClear( *this );
625  }
626 
627  /// Clears the list so Count() is zero. Does not strip capacity. Shorthand for Count( 0 ).
628  /// \deprecated Renamed to Clear() for consistency.
629  DISTI_DEPRECATED( "Renamed to Clear() for consistency." )
630  void ClearList()
631  {
632  Clear();
633  }
634 
635  /// Get the index position of the specified \a object in the list
636  /// \return The index of the object in the list, -1 if it isn't in the list
637  /// \deprecated Use helper function FindIndexOf() instead, but note that it returns unsigned.
638  DISTI_DEPRECATED( "Use helper function FindIndexOf() instead, but note that it returns unsigned." )
639  int Position( const T& object ) const
640  {
641  const unsigned index = FindIndexOf( *this, object );
642  return index == g_itemNotFound ? -1 : static_cast<int>( index );
643  }
644 
645 private:
646  unsigned _capacity; // Number of elements in the array
647  unsigned _count; // Number of elements used
648  T* _objects; // The array of objects
649 
650  // Give access to the dynamic array with the *other* value for the old TypeIsSimple parameter.
651  friend class DynamicArray<T, !Obsolete>;
652 
653  // Expands the object array, leaving a hole at loc.
654  void GrowAround( const unsigned loc )
655  {
656  const unsigned newCapacity = _capacity == 0 ? 2 : _capacity * 2;
657  T* const newObjects = reinterpret_cast<T*>( std::malloc( sizeof( T ) * newCapacity ) );
658  if( !newObjects )
659  {
660  throw std::bad_alloc();
661  }
662 
663  // Note: We set this after the malloc so that we have perfect roll-back if malloc fails.
664  _capacity = newCapacity;
665 
666  GLS_ASSERT( loc < _capacity );
667 
668  // Move any old objects over to the new array, touching only the active objects,
669  // not the potentially uninitialized ones, leaving a hole at loc.
670  for( unsigned i = 0; i < loc; i++ )
671  {
672  Assign( newObjects[ i ], DISTI_RVAL_MOVE( _objects[ i ] ) );
673  }
674 
675  for( unsigned i = loc; i < _count; i++ )
676  {
677  Assign( newObjects[ i + 1 ], DISTI_RVAL_MOVE( _objects[ i ] ) );
678  }
679 
680  // Release the old memory
681  std::free( _objects );
682 
683  // Take ownership of the new array
684  _objects = newObjects;
685  }
686 
687  // Insert an object by using universal references.
688  // This implementation allows us to avoid overloading on universal references, per Effective Modern C++ #26.
689  template<class U>
690  unsigned InsertImpl( DISTI_UREF( U ) object, unsigned loc )
691  {
692  // If the Location Index exceeds the array bounds, put the new object at the end of the array.
693  // Note: This is a bit surprising behavior from the user's perspective and may hide bugs.
694  // It is kept for historical reasons.
695  if( loc >= _count + 1 )
696  {
697  loc = _count;
698  }
699 
700  // Do we need to expand the array to accomodate the new value?
701  if( _count + 1 > _capacity )
702  {
703  GrowAround( loc );
704  }
705  else
706  {
707  // Shift the array elements *after* the insertion location up to make room
708  for( unsigned i = _count; i > loc; i-- )
709  {
710  Assign( _objects[ i ], DISTI_RVAL_MOVE( _objects[ i - 1 ] ) );
711  }
712  }
713 
714  // Assign the object at the specified location
715  Assign( _objects[ loc ], DISTI_UREF_FORWARD( U, object ) );
716  ++_count;
717  return loc;
718  }
719 
720  template<bool OtherObsolete>
721  void DeepCopyFrom( const DynamicArray<T, OtherObsolete>& other )
722  {
723  Capacity( other.Count() ); // Don't copy capacity, just active count
724  for( unsigned i = 0; i < other.Count(); i++ )
725  {
726  Assign( _objects[ i ], other._objects[ i ] );
727  }
728  _count = other.Count();
729  }
730 
731 #if defined( DISTI_HAS_RVAL_REFS )
732  template<bool OtherObsolete>
733  void StealFrom( DynamicArray<T, OtherObsolete>&& other )
734  {
735  if( this != &other )
736  {
737  // We're replacing our list, so get rid of any current contents
738  StripCapacity();
739 
740  // Take ownership
741  _capacity = other._capacity;
742  _count = other._count;
743  _objects = other._objects;
744 
745  // Relieve of ownership
746  other._capacity = 0;
747  other._count = 0;
748  other._objects = NULL;
749  }
750  }
751 #endif
752 
753  // Assign as if dest = src, but without assuming that dest is valid.
754  template<class U>
755  static void Assign( T& dest, DISTI_UREF( U ) src )
756  {
757  // Use placement-new to construct in situ by invoking the copy/move constructor,
758  // and not the assignment operator, which makes the (bad) assumption that both
759  // the left-hand and right-hand side of the equals are valid.
760  new( &dest ) T( DISTI_UREF_FORWARD( U, src ) );
761  }
762 
763  // Destroy an object by selecting which Destroy() implementation is appropriate for this type
764  static void Destroy( T& object )
765  {
766  DestroyImpl( object, DISTI_IS_TRIVIALLY_DESTRUCTIBLE( T ) );
767  }
768 
769  // For non-trivially destructible types, call their destructor explicitly.
770  static void DestroyImpl( T& object, /*trivially destructible*/ DISTI_TT_FALSE_TYPE )
771  {
772  object.~T();
773  }
774 
775  // Do nothing for trivially destructible types
776  static void DestroyImpl( T& /*object*/, /*trivially destructible*/ DISTI_TT_TRUE_TYPE ) {}
777 
778  // Destroy objects with indices in the range [i, end).
779  // Does not modify _count or _capacity.
780  void Destroy( unsigned i, const unsigned end )
781  {
782  GLS_ASSERT( i <= end );
783  while( i < end )
784  {
785  Destroy( _objects[ i++ ] );
786  }
787  }
788 };
789 
790 /// Overload begin() so that range-for loops and other constructs work with DynamicArray
791 template<class T, bool Obsolete>
793 {
794  return array.Count() == 0 ? NULL : array.InternalArray();
795 }
796 
797 /// Overload begin() so that range-for loops and other constructs work with DynamicArray
798 template<class T, bool Obsolete>
799 const T* begin( const DynamicArray<T, Obsolete>& array )
800 {
801  return array.Count() == 0 ? NULL : array.InternalArray();
802 }
803 
804 /// Overload end() so that range-for loops and other constructs work with DynamicArray
805 template<class T, bool Obsolete>
807 {
808  return array.Count() == 0 ? NULL : array.InternalArray() + array.Count();
809 }
810 
811 /// Overload end() so that range-for loops and other constructs work with DynamicArray
812 template<class T, bool Obsolete>
813 const T* end( const DynamicArray<T, Obsolete>& array )
814 {
815  return array.Count() == 0 ? NULL : array.InternalArray() + array.Count();
816 }
817 
818 /// Get the index position of the specified \a object in the given \a array
819 /// \return The index of the object in the list, or g_itemNotFound if it isn't in the list
820 template<class T, bool Obsolete, class U>
821 unsigned FindIndexOf( const DynamicArray<T, Obsolete>& array, const U& object )
822 {
823  for( unsigned i = 0, count = array.Count(); i < count; ++i )
824  {
825  if( object == array[ i ] )
826  {
827  return i;
828  }
829  }
830  return g_itemNotFound;
831 }
832 
833 /// Calls delete on each element and then clears the list.
834 /// \note Works only where T is a pointer.
835 template<class T, bool Obsolete>
837 {
838  for( unsigned i = 0; i < array.Count(); ++i )
839  {
840  delete array[ i ];
841  array[ i ] = NULL;
842  }
843  array.Clear();
844 }
845 
846 /// Calls delete[] on each element and then clears the list.
847 /// \note Works only where T is a pointer to an array.
848 template<class T, bool Obsolete>
850 {
851  for( unsigned i = 0; i < array.Count(); ++i )
852  {
853  delete[] array[ i ];
854  array[ i ] = NULL;
855  }
856  array.Clear();
857 }
858 } // namespace disti
859 
860 #endif
const T & operator[](const unsigned index) const
Definition: dynamic_array.h:454
unsigned Size() const
Definition: dynamic_array.h:489
unsigned Insert(const T &object, unsigned loc)
Definition: dynamic_array.h:316
unsigned PushBack(T &&object)
Definition: dynamic_array.h:379
void Capacity(const unsigned newCapacity)
Definition: dynamic_array.h:250
#define DISTI_DEPRECATED(msg)
Defines whether this compiler supports the C++14 deprecated attribute.
Definition: gls_cpp_lang_support.h:436
unsigned Insert(T &&object, unsigned loc)
Definition: dynamic_array.h:372
DynamicArray & operator=(const DynamicArray< T, true > &other)
Assign this array by deep-copying other.
Definition: dynamic_array.h:137
DynamicArray(DynamicArray< T, true > &&other)
Construct this array by taking ownership of other's contents.
Definition: dynamic_array.h:158
unsigned Count() const
Definition: dynamic_array.h:204
Definition: dynamic_array.h:66
DynamicArray & operator=(const DynamicArray< T, false > &other)
Assign this array by deep-copying other.
Definition: dynamic_array.h:147
void Count(const unsigned newCount)
Definition: dynamic_array.h:208
void PushFront(T &&object)
Definition: dynamic_array.h:387
DynamicArray(unsigned initialCapacity=0)
Definition: dynamic_array.h:85
const T * end(const DynamicArray< T, Obsolete > &array)
Overload end() so that range-for loops and other constructs work with DynamicArray.
Definition: dynamic_array.h:813
void DeleteEachAndClear(DynamicArray< T, Obsolete > &array)
Definition: dynamic_array.h:836
void EmptyList()
Definition: dynamic_array.h:622
int Position(const T &object) const
Definition: dynamic_array.h:639
~DynamicArray()
DynamicArray destructor. Clears the array but does not delete the objects being pointed to by the arr...
Definition: dynamic_array.h:196
void PushObject(const T &object)
Definition: dynamic_array.h:543
A file for all GL Studio files to include.
unsigned FindIndexOf(const DynamicArray< T, Obsolete > &array, const U &object)
Definition: dynamic_array.h:821
DynamicArray & operator=(DynamicArray< T, true > &&other)
Assign this array by clearing any current contents and then taking ownership of other's contents...
Definition: dynamic_array.h:182
unsigned Capacity() const
Definition: dynamic_array.h:245
#define GLS_ASSERT(exp)
Definition: disti_assert.h:135
bool Erase(const T &object)
Definition: dynamic_array.h:396
bool DeleteObjectAtIndex(const unsigned index)
Definition: dynamic_array.h:614
T & operator[](const unsigned index)
Definition: dynamic_array.h:432
#define GLS_VERIFY(exp)
Definition: disti_assert.h:155
const T & Back() const
Definition: dynamic_array.h:350
unsigned InsertObject(const T &object, unsigned loc)
Definition: dynamic_array.h:511
DynamicArray(DynamicArray< T, false > &&other)
Construct this array by taking ownership of other's contents.
Definition: dynamic_array.h:170
#define DISTI_IS_TRIVIALLY_DESTRUCTIBLE(T)
Determines if a class T is trivially destructible (i.e., has no side effects)
Definition: gls_cpp_lang_support.h:250
T * InternalArray()
Definition: dynamic_array.h:462
DistiAttribDict::const_iterator begin(const DistiAttribDict &dict)
Definition: disti_metadata.h:860
T & Back()
Definition: dynamic_array.h:342
const unsigned g_itemNotFound
Constant returned by FindIndexOf() if the item is not found.
Definition: dynamic_array.h:72
DynamicArray(std::initializer_list< T > list)
Definition: dynamic_array.h:101
DynamicArray(const DynamicArray< T, true > &other)
Initialize this array by deep-copying other.
Definition: dynamic_array.h:119
bool IsEmpty() const
Definition: dynamic_array.h:475
const T * InternalArray() const
Definition: dynamic_array.h:469
unsigned PushBack(const T &object)
Definition: dynamic_array.h:325
bool EraseAt(const unsigned index)
Definition: dynamic_array.h:409
Contains the DistiAssert macro.
void Clear()
Definition: dynamic_array.h:238
void PushFront(const T &object)
Definition: dynamic_array.h:359
Macros and helper code to determine what subset of C++11/14/17 is available.
void DeleteArraysAndClear(DynamicArray< T, Obsolete > &array)
Definition: dynamic_array.h:849
Definition: bmpimage.h:46
void PopBack()
Removes the last item in the array. If the array is empty, it has no effect.
Definition: dynamic_array.h:332
unsigned InsertObjectAfter(const T &object, unsigned loc)
Definition: dynamic_array.h:533
DynamicArray(const DynamicArray< T, false > &other)
Initialize this array by deep-copying other.
Definition: dynamic_array.h:128
void StripCapacity()
Definition: dynamic_array.h:307
void ClearList()
Definition: dynamic_array.h:630
bool DeleteObject(const T &object)
Definition: dynamic_array.h:603