| 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; ///< Typedef for the type of object contained in this array.
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 /// \param list The list of items to construct from.
102 DynamicArray( std::initializer_list<T> list )
103 : _capacity( 0 )
104 , _count( 0 )
105 , _objects( NULL )
106 {
107 const auto capacity = static_cast<unsigned>( list.size() );
108 if( capacity != 0 )
109 {
110 Capacity( capacity );
111 for( auto&& item : list )
112 {
113 PushBack( std::move( item ) );
114 }
115 }
116 }
117#endif
118
119 /// Initialize this array by deep-copying \a other
120 /// \param other The array to copy from.
121 DynamicArray( const DynamicArray<T, true>& other )
122 : _capacity( 0 )
123 , _count( 0 )
124 , _objects( NULL )
125 {
126 DeepCopyFrom( other );
127 }
128
129 /// Initialize this array by deep-copying \a other
130 /// \param other The array to copy from.
131 DynamicArray( const DynamicArray<T, false>& other )
132 : _capacity( 0 )
133 , _count( 0 )
134 , _objects( NULL )
135 {
136 DeepCopyFrom( other );
137 }
138
139 /// Assign this array by deep-copying \a other
140 /// \param other The array to copy from.
141 /// \return The resulting array (this).
142 DynamicArray& operator=( const DynamicArray<T, true>& other )
143 {
144 if( this != &other )
145 {
146 DeepCopyFrom( other );
147 }
148 return *this;
149 }
150
151 /// Assign this array by deep-copying \a other
152 /// \param other The array to copy from.
153 /// \return The resulting array (this).
154 DynamicArray& operator=( const DynamicArray<T, false>& other )
155 {
156 if( this != &other )
157 {
158 DeepCopyFrom( other );
159 }
160 return *this;
161 }
162
163#if defined( DISTI_HAS_RVAL_REFS )
164 /// Construct this array by taking ownership of \a other's contents.
165 /// \param other The array to move from.
166 DynamicArray( DynamicArray<T, true>&& other )
167 : _capacity( other._capacity )
168 , _count( other._count )
169 , _objects( other._objects )
170 {
171 // Relieve of ownership
172 other._capacity = 0;
173 other._count = 0;
174 other._objects = NULL;
175 }
176
177 /// Construct this array by taking ownership of \a other's contents.
178 /// \param other The array to move from.
179 DynamicArray( DynamicArray<T, false>&& other )
180 : _capacity( other._capacity )
181 , _count( other._count )
182 , _objects( other._objects )
183 {
184 // Relieve of ownership
185 other._capacity = 0;
186 other._count = 0;
187 other._objects = NULL;
188 }
189
190 /// Assign this array by clearing any current contents and then taking ownership of \a other's contents.
191 /// \param other The array to move from.
192 /// \return The resulting array (this).
193 DynamicArray& operator=( DynamicArray<T, true>&& other )
194 {
195 StealFrom( std::move( other ) );
196 return *this;
197 }
198
199 /// Assign this array by clearing any current contents and then taking ownership of \a other's contents.
200 /// \param other The array to move from.
201 /// \return The resulting array (this).
202 DynamicArray& operator=( DynamicArray<T, false>&& other )
203 {
204 StealFrom( std::move( other ) );
205 return *this;
206 }
207#endif
208
209 /// DynamicArray destructor. Clears the array but does not delete the objects being pointed to by the array.
210 ~DynamicArray()
211 {
212 StripCapacity();
213 }
214
215 /// Returns the number of elements used of this dynamic array
216 /// \return The number of elements used of the array (number of elements)
217 /// \note Similar to std::vector::size()
218 unsigned Count() const { return _count; }
219
220 /// Set the "Count" value for this array, destroying items or creating default-constructed items as needed.
221 /// \note Similar to std::vector::resize()
222 /// \param newCount The new count to allocate.
223 void Count( const unsigned newCount )
224 {
225 if( newCount > _capacity )
226 {
227 Capacity( newCount );
228 }
229
230 if( newCount > _count )
231 {
232 // If we're increasing our count, then we need to initialize the new values manually since
233 // setting the capacity doesn't deal with initializing objects.
234 for( unsigned i = _count; i < newCount; ++i )
235 {
236 new( _objects + i ) T(); // Use placement-new to construct at this memory location
237 }
238 }
239 else
240 {
241 // If we're lowering our count, we need to destroy some objects because we want them to
242 // clean up after themselves (e.g., if they have some resource they need to close). We
243 // can't call delete because this container manually manages the memory the object sits in.
244 Destroy( newCount, _count );
245 }
246
247 _count = newCount;
248 }
249
250 /// Clears the list so Count() is zero, destroying all items. Does not strip capacity. Shorthand for Count( 0 ).
251 /// \note Similar to std::vector::clear().
252 /// \sa StripCapacity()
253 void Clear()
254 {
255 Count( 0 );
256 }
257
258 /// \return The capacity of this dynamic array.
259 /// \note Similar to std::vector::capacity()
260 unsigned Capacity() const { return _capacity; }
261
262 /// Reserves space for \a newCapacity elements in the array, reallocating as needed.
263 /// \param newCapacity The new number of elements reserved in the array.
264 /// \note Similar to std::vector::reserve(), but does lower capacity when asked.
265 void Capacity( const unsigned newCapacity )
266 {
267 // Case 1: Don't reallocate if the capacity doesn't change
268 if( newCapacity == _capacity )
269 {
270 return;
271 }
272 // Case 2: Erasing all capacity
273 else if( 0 == newCapacity )
274 {
275 Destroy( 0, _count );
276 std::free( _objects );
277 _objects = NULL;
278 _capacity = 0;
279 _count = 0;
280 return;
281 }
282
283 // Case 3: Change the capacity
284
285 // Allocate the new memory using malloc since we will control construction
286 // and destruction separately from memory allocation.
287 // Note: Don't set any member vars until after the malloc so that we have
288 // perfect roll-back if malloc fails.
289 T* const newObjects = reinterpret_cast<T*>( std::malloc( sizeof( T ) * newCapacity ) );
290 if( !newObjects )
291 {
292 throw std::bad_alloc();
293 }
294
295 // If we're shrinking the capacity, destroy the obsolete objects
296 if( newCapacity < _count )
297 {
298 Destroy( newCapacity, _count );
299 _count = newCapacity;
300 }
301
302 // Move the old objects over to the new array, if needed
303 if( _objects )
304 {
305 // Move only the active objects, not the potentially uninitialized ones
306 for( unsigned i = 0; i < _count; i++ )
307 {
308 Assign( newObjects[ i ], DISTI_RVAL_MOVE( _objects[ i ] ) );
309 }
310
311 // Release the old memory
312 std::free( _objects );
313 }
314
315 // Own the new objects
316 _objects = newObjects;
317 _capacity = newCapacity;
318 }
319
320 /// Remove all capacity, destroying any extant items (but deleting any pointees, if the item is a pointer; for that, see DeleteEachAndClear()).
321 /// \sa Clear(), DeleteEachAndClear()
322 void StripCapacity() { Capacity( 0 ); }
323
324 /// Attempts to insert the object into the list at the specified location. If the
325 /// specified location is beyond the array bounds, the object is inserted at the next
326 /// position in the array.
327 /// \param object The object to insert
328 /// \param loc The index location to insert into
329 /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
330 /// \note Similar to std::vector::insert( object, begin(*this) + loc );
331 unsigned Insert( const T& object, unsigned loc )
332 {
333 return InsertImpl( object, loc );
334 }
335
336 /// Adds the specified object into the list, at the end of the list
337 /// \param object A pointer to the object to add
338 /// \return Where the object was inserted
339 /// \note Similar to std::vector::push_back()
340 unsigned PushBack( const T& object )
341 {
342 InsertImpl( object, _count );
343 return _count - 1;
344 }
345
346 /// Removes the last item in the array. If the array is empty, it has no effect.
347 void PopBack()
348 {
349 if( _count > 0 )
350 {
351 Count( _count - 1 );
352 }
353 }
354
355 /// \return The last element in the array.
356 /// \throws DistiException if array is empty.
357 T& Back()
358 {
359 GLS_VERIFY( !IsEmpty() );
360 return _objects[ _count - 1 ];
361 }
362
363 /// \return The last element in the array.
364 /// \throws DistiException if array is empty.
365 const T& Back() const
366 {
367 GLS_VERIFY( !IsEmpty() );
368 return _objects[ _count - 1 ];
369 }
370
371 /// Adds the specified \a object at the head of the list.
372 /// \note Similar to std::vector::insert( object, begin(*this) );
373 /// \note Prefer PushBack() instead to avoid inefficiencies.
374 /// \param object The object to add.
375 void PushFront( const T& object )
376 {
377 InsertImpl( object, 0 );
378 }
379
380 // Extra rvalue overloads for efficiency, where available.
381#if defined( DISTI_HAS_RVAL_REFS )
382 /// Attempts to insert the object into the list at the specified location. If the
383 /// specified location is beyond the array bounds, the object is inserted at the next
384 /// position in the array.
385 /// \param object The object to insert
386 /// \param loc The index location to insert into
387 /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
388 unsigned Insert( T&& object, unsigned loc )
389 {
390 return InsertImpl( std::move( object ), loc );
391 }
392
393 /// Adds the specified \a object into the list, at the end of the list
394 /// \param object The object to add.
395 /// \return Where the object was inserted
396 unsigned PushBack( T&& object )
397 {
398 return InsertImpl( std::move( object ), _count );
399 }
400
401 /// Adds the specified \a object at the head of the list.
402 /// \note Similar to std::vector::insert( object, begin(*this) );
403 /// \note Prefer PushBack() instead to avoid inefficiencies.
404 /// \param object The object to add.
405 void PushFront( T&& object )
406 {
407 InsertImpl( std::move( object ), 0 );
408 }
409#endif
410
411 /// Deletes the specified object from the list. Does not delete it, if a pointer.
412 /// \param object A pointer to the object to delete
413 /// \return true if object was found and deleted else false
414 bool Erase( const T& object )
415 {
416 const unsigned loc = FindIndexOf( *this, object );
417 if( loc != g_itemNotFound )
418 {
419 return EraseAt( loc );
420 }
421 return false;
422 }
423
424 /// Removes the object at the specified index. (Does not delete it, if pointer.)
425 /// \param index Index of the object to delete
426 /// \return true if object was found and deleted else false
427 bool EraseAt( const unsigned index )
428 {
429 if( index >= _count )
430 {
431 return false;
432 }
433
434 // Destroy the object in question
435 Destroy( _objects[ index ] );
436
437 // Shift all items down on top of the deleted item
438 for( unsigned j = index; j < _count - 1u; j++ )
439 {
440 Assign( _objects[ j ], DISTI_RVAL_MOVE( _objects[ j + 1u ] ) );
441 }
442
443 _count--;
444
445 return true;
446 }
447
448 /// Overload of array operator to get element at desired index
449 /// \note Resizes if \a index exceeds Capacity() or Count().
450 /// \param index The index of the item to return.
451 /// \return The item found, which will be a new item if index is greater than the count.
452 T& operator[]( const unsigned index )
453 {
454 // This gets an element, resizing the array if needed
455 if( index >= _capacity )
456 {
457 Count( index + 1 );
458 }
459 else if( index >= _count )
460 {
461 for( unsigned i = _count; i <= index; ++i )
462 {
463 Assign( _objects[ i ], T() );
464 }
465
466 _count = index + 1;
467 }
468
469 return _objects[ index ];
470 }
471
472 /// Overload of array operator to get element at desired index
473 /// \note Does not resize if \a index exceeds Capacity() or Count().
474 /// \param index The index of the item to return.
475 /// \return The item found.
476 const T& operator[]( const unsigned index ) const
477 {
478 GLS_ASSERT( index < _capacity && index < _count );
479 return _objects[ index ];
480 }
481
482 /// \return The internal array pointer.
483 /// \note If you call any non-const methods on this object it may invalidate the pointer.
484 T* InternalArray()
485 {
486 return _objects;
487 }
488
489 /// \return The internal array pointer.
490 /// \note If you call any non-const methods on this object it may invalidate the pointer.
491 const T* InternalArray() const
492 {
493 return _objects;
494 }
495
496 /// \return true if the list is empty
497 bool IsEmpty() const
498 {
499 return ( _count == 0 );
500 }
501
502 ///////////////////////////////////////////////////////////////////////////////////////////////
503 // The following functions have been deprecated but are retained for now for backwards
504 // compatibility. All new code should use their noted replacements.
505 ///////////////////////////////////////////////////////////////////////////////////////////////
506
507 /// \return The capacity of this array.
508 /// \deprecated Renamed to Capacity() for clarity.
509 /// \note similar to std::vector::capacity()
510 DISTI_DEPRECATED( "Renamed to Capacity() for clarity." )
511 unsigned Size() const { return Capacity(); }
512
513 /// Reserves space for \a newCapacity elements in the array, reallocating as needed.
514 /// \param newCapacity The new number of elements reserved in the array
515 /// \note similar to std::vector::reserve()
516 /// \deprecated Renamed to Capacity() for clarity.
517 DISTI_DEPRECATED( "Renamed to Capacity() for clarity." )
518 void Size( unsigned newCapacity )
519 {
520 Capacity( newCapacity );
521 }
522
523 /// Attempts to insert the object into the list at the specified location. If the
524 /// specified location is beyond the array bounds, the object is inserted at the next
525 /// position in the array.
526 /// \param object The object to insert
527 /// \param loc The index location to insert into
528 /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
529 /// \note Similar to std::vector::insert()
530 /// \deprecated Use Insert( object, loc ) instead.
531 DISTI_DEPRECATED( "Use Insert( object, loc ) instead." )
532 unsigned InsertObject( const T& object, unsigned loc )
533 {
534 return Insert( object, loc );
535 }
536
537 /// Adds the specified \a object into the list, at the end of the list
538 /// \param object The object to insert.
539 /// \return Where the object was inserted.
540 /// \note similar to std::vector::push_back()
541 /// \deprecated Use PushBack( object ) instead.
542 DISTI_DEPRECATED( "Use PushBack( object ) instead." )
543 unsigned InsertObject( const T& object )
544 {
545 return PushBack( object );
546 }
547
548 /// Insert the object into the list at the specified location
549 /// \param object The object to insert
550 /// \param loc The index location to insert into
551 /// \return The actual location inserted, which may be different than \a loc if it exceeded the count but not the capacity.
552 /// \note similar to std::vector::insert()
553 /// \deprecated Use Insert( object, loc + 1 ) instead.
554 DISTI_DEPRECATED( "Use Insert( object, loc + 1 ) instead." )
555 unsigned InsertObjectAfter( const T& object, unsigned loc )
556 {
557 return Insert( object, loc + 1 );
558 }
559
560 /// Adds the specified \a object into the list, at the head of the list
561 /// Treats the list like a stack, hence the name Push
562 /// \note Similar to std::vector::insert( object, begin(*this) );
563 /// \param object The object to add.
564 /// \deprecated Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies.
565 DISTI_DEPRECATED( "Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies." )
566 void PushObject( const T& object )
567 {
568 PushFront( object );
569 }
570
571 // Extra rvalue overloads for efficiency, where available.
572#if defined( DISTI_HAS_RVAL_REFS )
573 /// Attempts to insert the object into the list at the specified location. If the
574 /// specified location is beyond the array bounds, the object is inserted at the next
575 /// position in the array.
576 /// \param object The object to insert
577 /// \param loc The index location to insert into
578 /// \note Similar to std::vector::insert()
579 /// \deprecated Use Insert( object, loc ) instead.
580 DISTI_DEPRECATED( "Use Insert( object, loc ) instead." )
581 void InsertObject( T&& object, unsigned loc )
582 {
583 Insert( std::move( object ), loc );
584 }
585
586 /// Adds the specified \a object into the list, at the end of the list
587 /// \param object The object to insert.
588 /// \return Where the object was inserted.
589 /// \note Similar to std::vector::push_back()
590 /// \deprecated Use PushBack( object ) instead.
591 DISTI_DEPRECATED( "Use PushBack( object ) instead." )
592 unsigned InsertObject( T&& object )
593 {
594 return PushBack( std::move( object ) );
595 }
596
597 /// Insert the object into the list at the specified location
598 /// \param object The object to insert
599 /// \param loc The index location to insert into
600 /// \note Similar to std::vector::insert()
601 /// \deprecated Use Insert( object, loc + 1 ) instead.
602 DISTI_DEPRECATED( "Use Insert( object, loc + 1 ) instead." )
603 void InsertObjectAfter( T&& object, unsigned loc )
604 {
605 Insert( std::move( object ), loc + 1 );
606 }
607
608 /// Adds the specified \a object at the head of the list.
609 /// \note This must move or copy all existing items, so it may be expensive.
610 /// \note Similar to std::vector::insert( object, begin(*this) );
611 /// \param object The object to add.
612 /// \deprecated Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies.
613 DISTI_DEPRECATED( "Renamed to PushFront(), but prefer PushBack() instead to avoid inefficiencies." )
614 void PushObject( T&& object )
615 {
616 PushFront( std::move( object ) );
617 }
618#endif
619
620 /// Removes the object, shrinking the array count. (Does not delete it, if pointer.)
621 /// \param object A pointer to the object to delete
622 /// \return true if object was found and deleted else false
623 /// \note Similar to std::vector::erase()
624 /// \deprecated Renamed EraseAt() for clarity.
625 DISTI_DEPRECATED( "Renamed Erase() for clarity." )
626 bool DeleteObject( const T& object )
627 {
628 return Erase( object );
629 }
630
631 /// Removes the object at the specified index. (Does not delete it, if pointer.)
632 /// \param index Index of the object to delete
633 /// \return true if object was found and removed else false
634 /// \note Similar to std::vector::erase()
635 /// \deprecated Renamed EraseAt() for clarity.
636 DISTI_DEPRECATED( "Renamed EraseAt() for clarity." )
637 bool DeleteObjectAtIndex( const unsigned index )
638 {
639 return EraseAt( index );
640 }
641
642 /// Calls delete on each element and then clears the list.
643 /// \deprecated Use the non-member function DeleteEachAndClear( dynamicArray ) instead.
644 DISTI_DEPRECATED( "Use the non-member function DeleteEachAndClear( dynamicArray ) instead." )
645 void EmptyList()
646 {
647 DeleteEachAndClear( *this );
648 }
649
650 /// Clears the list so Count() is zero. Does not strip capacity. Shorthand for Count( 0 ).
651 /// \deprecated Renamed to Clear() for consistency.
652 DISTI_DEPRECATED( "Renamed to Clear() for consistency." )
653 void ClearList()
654 {
655 Clear();
656 }
657
658 /// Get the index position of the specified \a object in the list
659 /// \param object The object whose index is to be found.
660 /// \return The index of the object in the list, -1 if it isn't in the list
661 /// \deprecated Use helper function FindIndexOf() instead, but note that it returns unsigned.
662 DISTI_DEPRECATED( "Use helper function FindIndexOf() instead, but note that it returns unsigned." )
663 int Position( const T& object ) const
664 {
665 const unsigned index = FindIndexOf( *this, object );
666 return index == g_itemNotFound ? -1 : static_cast<int>( index );
667 }
668
669 private:
670 unsigned _capacity; // Number of elements in the array
671 unsigned _count; // Number of elements used
672 T* _objects; // The array of objects
673
674 // Give access to the dynamic array with the *other* value for the old TypeIsSimple parameter.
675 friend class DynamicArray<T, !Obsolete>;
676
677 // Expands the object array, leaving a hole at loc.
678 void GrowAround( const unsigned loc )
679 {
680 const unsigned newCapacity = _capacity == 0 ? 2 : _capacity * 2;
681 T* const newObjects = reinterpret_cast<T*>( std::malloc( sizeof( T ) * newCapacity ) );
682 if( !newObjects )
683 {
684 throw std::bad_alloc();
685 }
686
687 // Note: We set this after the malloc so that we have perfect roll-back if malloc fails.
688 _capacity = newCapacity;
689
690 GLS_ASSERT( loc < _capacity );
691
692 // Move any old objects over to the new array, touching only the active objects,
693 // not the potentially uninitialized ones, leaving a hole at loc.
694 for( unsigned i = 0; i < loc; i++ )
695 {
696 Assign( newObjects[ i ], DISTI_RVAL_MOVE( _objects[ i ] ) );
697 }
698
699 for( unsigned i = loc; i < _count; i++ )
700 {
701 Assign( newObjects[ i + 1 ], DISTI_RVAL_MOVE( _objects[ i ] ) );
702 }
703
704 // Release the old memory
705 std::free( _objects );
706
707 // Take ownership of the new array
708 _objects = newObjects;
709 }
710
711 // Insert an object by using universal references.
712 // This implementation allows us to avoid overloading on universal references, per Effective Modern C++ #26.
713 template<class U>
714 unsigned InsertImpl( DISTI_UREF( U ) object, unsigned loc )
715 {
716 // If the Location Index exceeds the array bounds, put the new object at the end of the array.
717 // Note: This is a bit surprising behavior from the user's perspective and may hide bugs.
718 // It is kept for historical reasons.
719 if( loc >= _count + 1 )
720 {
721 loc = _count;
722 }
723
724 // Do we need to expand the array to accomodate the new value?
725 if( _count + 1 > _capacity )
726 {
727 GrowAround( loc );
728 }
729 else
730 {
731 // Shift the array elements *after* the insertion location up to make room
732 for( unsigned i = _count; i > loc; i-- )
733 {
734 Assign( _objects[ i ], DISTI_RVAL_MOVE( _objects[ i - 1 ] ) );
735 }
736 }
737
738 // Assign the object at the specified location
739 Assign( _objects[ loc ], DISTI_UREF_FORWARD( U, object ) );
740 ++_count;
741 return loc;
742 }
743
744 template<bool OtherObsolete>
745 void DeepCopyFrom( const DynamicArray<T, OtherObsolete>& other )
746 {
747 Capacity( other.Count() ); // Don't copy capacity, just active count
748 for( unsigned i = 0; i < other.Count(); i++ )
749 {
750 Assign( _objects[ i ], other._objects[ i ] );
751 }
752 _count = other.Count();
753 }
754
755#if defined( DISTI_HAS_RVAL_REFS )
756 template<bool OtherObsolete>
757 void StealFrom( DynamicArray<T, OtherObsolete>&& other )
758 {
759 if( this != &other )
760 {
761 // We're replacing our list, so get rid of any current contents
762 StripCapacity();
763
764 // Take ownership
765 _capacity = other._capacity;
766 _count = other._count;
767 _objects = other._objects;
768
769 // Relieve of ownership
770 other._capacity = 0;
771 other._count = 0;
772 other._objects = NULL;
773 }
774 }
775#endif
776
777 // Assign as if dest = src, but without assuming that dest is valid.
778 template<class U>
779 static void Assign( T& dest, DISTI_UREF( U ) src )
780 {
781 // Use placement-new to construct in situ by invoking the copy/move constructor,
782 // and not the assignment operator, which makes the (bad) assumption that both
783 // the left-hand and right-hand side of the equals are valid.
784 new( &dest ) T( DISTI_UREF_FORWARD( U, src ) );
785 }
786
787 // Destroy an object by selecting which Destroy() implementation is appropriate for this type
788 static void Destroy( T& object )
789 {
790 DestroyImpl( object, DISTI_IS_TRIVIALLY_DESTRUCTIBLE( T ) );
791 }
792
793 // For non-trivially destructible types, call their destructor explicitly.
794 static void DestroyImpl( T& object, /*trivially destructible*/ DISTI_TT_FALSE_TYPE )
795 {
796 object.~T();
797 }
798
799 // Do nothing for trivially destructible types
800 static void DestroyImpl( T& /*object*/, /*trivially destructible*/ DISTI_TT_TRUE_TYPE ) {}
801
802 // Destroy objects with indices in the range [i, end).
803 // Does not modify _count or _capacity.
804 void Destroy( unsigned i, const unsigned end )
805 {
806 GLS_ASSERT( i <= end );
807 while( i < end )
808 {
809 Destroy( _objects[ i++ ] );
810 }
811 }
812};
813
814/// Overload begin() so that range-for loops and other constructs work with DynamicArray.
815/// \param array The array whose first element is to be returned.
816/// \return The first element of the array, otherwise NULL.
817 template<class T, bool Obsolete>
818T* begin( DynamicArray<T, Obsolete>& array )
819{
820 return array.Count() == 0 ? NULL : array.InternalArray();
821}
822
823/// Overload begin() so that range-for loops and other constructs work with DynamicArray.
824/// \param array The array whose first element is to be returned.
825/// \return The first element of the array, otherwise NULL.
826 template<class T, bool Obsolete>
827 const T* begin( const DynamicArray<T, Obsolete>& array )
828{
829 return array.Count() == 0 ? NULL : array.InternalArray();
830}
831
832/// Overload end() so that range-for loops and other constructs work with DynamicArray.
833/// \param array The array whose last element is to be returned.
834/// \return The last element of the array, otherwise NULL.
835 template<class T, bool Obsolete>
836T* end( DynamicArray<T, Obsolete>& array )
837{
838 return array.Count() == 0 ? NULL : array.InternalArray() + array.Count();
839}
840
841/// Overload end() so that range-for loops and other constructs work with DynamicArray.
842/// \param array The array whose last element is to be returned.
843/// \return The last element of the array, otherwise NULL.
844 template<class T, bool Obsolete>
845 const T* end( const DynamicArray<T, Obsolete>& array )
846{
847 return array.Count() == 0 ? NULL : array.InternalArray() + array.Count();
848}
849
850/// Get the index position of the specified \a object in the given \a array
851/// \param array The list to search.
852/// \param object The object to search for.
853/// \return The index of the object in the list, or g_itemNotFound if it isn't in the list
854 template<class T, bool Obsolete, class U>
855 unsigned FindIndexOf( const DynamicArray<T, Obsolete>& array, const U& object )
856{
857 for( unsigned i = 0, count = array.Count(); i < count; ++i )
858 {
859 if( object == array[ i ] )
860 {
861 return i;
862 }
863 }
864 return g_itemNotFound;
865}
866
867/// Calls delete on each element and then clears the list.
868/// \param array The list to operate on.
869/// \note Works only where T is a pointer.
870 template<class T, bool Obsolete>
871 void DeleteEachAndClear( DynamicArray<T, Obsolete>& array )
872{
873 for( unsigned i = 0; i < array.Count(); ++i )
874 {
875 delete array[ i ];
876 array[ i ] = NULL;
877 }
878 array.Clear();
879}
880
881/// Calls delete[] on each element and then clears the list.
882/// \param array The list to operate on.
883/// \note Works only where T is a pointer to an array.
884 template<class T, bool Obsolete>
885 void DeleteArraysAndClear( DynamicArray<T, Obsolete>& array )
886{
887 for( unsigned i = 0; i < array.Count(); ++i )
888 {
889 delete[] array[ i ];
890 array[ i ] = NULL;
891 }
892 array.Clear();
893}
894} // namespace disti
895
896#endif
disti::DynamicArray
Definition: dynamic_array.h:79
disti::DynamicArray::DynamicArray
DynamicArray(std::initializer_list< T > list)
Definition: dynamic_array.h:102
disti::DynamicArray::Erase
bool Erase(const T &object)
Definition: dynamic_array.h:414
disti::DynamicArray::Count
void Count(const unsigned newCount)
Definition: dynamic_array.h:223
disti::DynamicArray::PushFront
void PushFront(const T &object)
Definition: dynamic_array.h:375
disti::DynamicArray::Position
int Position(const T &object) const
Definition: dynamic_array.h:663
disti::DynamicArray::Capacity
unsigned Capacity() const
Definition: dynamic_array.h:260
disti::DynamicArray::InternalArray
T * InternalArray()
Definition: dynamic_array.h:484
disti::DynamicArray::Insert
unsigned Insert(const T &object, unsigned loc)
Definition: dynamic_array.h:331
disti::DynamicArray::PushBack
unsigned PushBack(T &&object)
Definition: dynamic_array.h:396
disti::DynamicArray::ClearList
void ClearList()
Definition: dynamic_array.h:653
disti::DynamicArray::DynamicArray
DynamicArray(const DynamicArray< T, true > &other)
Definition: dynamic_array.h:121
disti::DynamicArray::ElementType
T ElementType
Typedef for the type of object contained in this array.
Definition: dynamic_array.h:81
disti::DynamicArray::Back
const T & Back() const
Definition: dynamic_array.h:365
disti::DynamicArray::Count
unsigned Count() const
Definition: dynamic_array.h:218
disti::DynamicArray::operator=
DynamicArray & operator=(const DynamicArray< T, false > &other)
Definition: dynamic_array.h:154
disti::DynamicArray::operator[]
T & operator[](const unsigned index)
Definition: dynamic_array.h:452
disti::DynamicArray::~DynamicArray
~DynamicArray()
DynamicArray destructor. Clears the array but does not delete the objects being pointed to by the arr...
Definition: dynamic_array.h:210
disti::DynamicArray::Back
T & Back()
Definition: dynamic_array.h:357
disti::DynamicArray::Insert
unsigned Insert(T &&object, unsigned loc)
Definition: dynamic_array.h:388
disti::DynamicArray::InternalArray
const T * InternalArray() const
Definition: dynamic_array.h:491
disti::DynamicArray::EraseAt
bool EraseAt(const unsigned index)
Definition: dynamic_array.h:427
disti::DynamicArray::DeleteObjectAtIndex
bool DeleteObjectAtIndex(const unsigned index)
Definition: dynamic_array.h:637
disti::DynamicArray::DynamicArray
DynamicArray(DynamicArray< T, true > &&other)
Definition: dynamic_array.h:166
disti::DynamicArray::PushObject
void PushObject(const T &object)
Definition: dynamic_array.h:566
disti::DynamicArray::InsertObjectAfter
unsigned InsertObjectAfter(const T &object, unsigned loc)
Definition: dynamic_array.h:555
disti::DynamicArray::DynamicArray
DynamicArray(DynamicArray< T, false > &&other)
Definition: dynamic_array.h:179
disti::DynamicArray::IsEmpty
bool IsEmpty() const
Definition: dynamic_array.h:497
disti::DynamicArray::Clear
void Clear()
Definition: dynamic_array.h:253
disti::DynamicArray::PopBack
void PopBack()
Removes the last item in the array. If the array is empty, it has no effect.
Definition: dynamic_array.h:347
disti::DynamicArray::EmptyList
void EmptyList()
Definition: dynamic_array.h:645
disti::DynamicArray::operator[]
const T & operator[](const unsigned index) const
Definition: dynamic_array.h:476
disti::DynamicArray::DynamicArray
DynamicArray(const DynamicArray< T, false > &other)
Definition: dynamic_array.h:131
disti::DynamicArray::InsertObject
unsigned InsertObject(const T &object, unsigned loc)
Definition: dynamic_array.h:532
disti::DynamicArray::PushFront
void PushFront(T &&object)
Definition: dynamic_array.h:405
disti::DynamicArray::PushBack
unsigned PushBack(const T &object)
Definition: dynamic_array.h:340
disti::DynamicArray::Size
unsigned Size() const
Definition: dynamic_array.h:511
disti::DynamicArray::Capacity
void Capacity(const unsigned newCapacity)
Definition: dynamic_array.h:265
disti::DynamicArray::StripCapacity
void StripCapacity()
Definition: dynamic_array.h:322
disti::DynamicArray::operator=
DynamicArray & operator=(DynamicArray< T, true > &&other)
Definition: dynamic_array.h:193
disti::DynamicArray::DynamicArray
DynamicArray(unsigned initialCapacity=0)
Definition: dynamic_array.h:85
disti::DynamicArray::operator=
DynamicArray & operator=(const DynamicArray< T, true > &other)
Definition: dynamic_array.h:142
disti::DynamicArray::operator=
DynamicArray & operator=(DynamicArray< T, false > &&other)
Definition: dynamic_array.h:202
disti::DynamicArray::DeleteObject
bool DeleteObject(const T &object)
Definition: dynamic_array.h:626
disti_assert.h
Contains the DistiAssert macro.
GLS_ASSERT
#define GLS_ASSERT(exp)
Definition: disti_assert.h:150
GLS_VERIFY
#define GLS_VERIFY(exp)
Definition: disti_assert.h:170
gls_cpp_lang_support.h
Macros and helper code to determine what subset of C++11/14/17 is available.
DISTI_UREF_FORWARD
#define DISTI_UREF_FORWARD(T, x)
Macro to wrap std::forward, removed on compilers that don't support it.
Definition: gls_cpp_lang_support.h:198
DISTI_IS_TRIVIALLY_DESTRUCTIBLE
#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:280
DISTI_RVAL_MOVE
#define DISTI_RVAL_MOVE(x)
Macro to wrap std::move, removed on compilers that don't support it.
Definition: gls_cpp_lang_support.h:196
DISTI_TT_FALSE_TYPE
#define DISTI_TT_FALSE_TYPE
Macro wrapping std::false_type, removed on compilers that don't support it.
Definition: gls_cpp_lang_support.h:284
DISTI_DEPRECATED
#define DISTI_DEPRECATED(msg)
Defines whether this compiler supports the C++14 deprecated attribute.
Definition: gls_cpp_lang_support.h:488
DISTI_UREF
#define DISTI_UREF(T)
Macro to wrap r-value reference, removed on platforms that don't support it.
Definition: gls_cpp_lang_support.h:200
DISTI_TT_TRUE_TYPE
#define DISTI_TT_TRUE_TYPE
Macro wrapping std::true_type, removed on compilers that don't support it.
Definition: gls_cpp_lang_support.h:282
DISTI_FINAL
#define DISTI_FINAL
Macro to wrap the final keyword, removed on compilers that don't support it.
Definition: gls_cpp_lang_support.h:224
gls_include.h
A file for all GL Studio files to include.
disti
Definition: bmpimage.h:47
disti::begin
DistiAttribDict::const_iterator begin(const DistiAttribDict &dict)
Definition: disti_metadata.h:970
disti::DeleteArraysAndClear
void DeleteArraysAndClear(DynamicArray< T, Obsolete > &array)
Definition: dynamic_array.h:885
disti::end
DistiAttribDict::const_iterator end(const DistiAttribDict &dict)
Definition: disti_metadata.h:975
disti::FindIndexOf
unsigned FindIndexOf(const DynamicArray< T, Obsolete > &array, const U &object)
Definition: dynamic_array.h:855
disti::g_itemNotFound
const unsigned g_itemNotFound
Constant returned by FindIndexOf() if the item is not found.
Definition: dynamic_array.h:72
disti::DeleteEachAndClear
void DeleteEachAndClear(DynamicArray< T, Obsolete > &array)
Definition: dynamic_array.h:871