# -*- mode: org -*-
#+HTML_HEAD: <link rel="stylesheet" type="text/css" href="../css/emacs.css" />


#+HTML_HEAD: <style type='text/css'> table { width: 100%; text-align: center; } table, th, td { border: 1px solid #000; border-collapse: collapse; }  .uml { width: 50%; margin: 0 auto; border: solid 1px #000; background: #fff5b5; } .uml th, .uml td { border: none; } </style>

[[http://rachel.likespizza.com/courses/_images/bytopic/datastructure-array/arrays.png]]


* *Smart dynamic array structure*

With the dynamic array structure, most of it will be similar to the Fixed
Array Structure, except we now have to deal with memory management and pointers.

Instead of throwing exceptions if the array is full, with a dynamic array we
can resize it instead. However, we also now need to check for the array
pointer (=m_array= in this example) pointing to =nullptr=.

The class declaration could look like this:

#+BEGIN_SRC cpp :class cpp
class SmartDynamicArray
{
public:
  SmartDynamicArray();
  ~SmartDynamicArray();

  void PushBack( T newItem );
  void PushFront( T newItem );
  void PushAt( T newItem, int index );

  void PopBack();
  void PopFront();
  void PopAt( int index );

  T GetBack() const;
  T GetFront() const;
  T GetAt( int index ) const;

  int Search( T item ) const;

  void Display() const;
  int Size() const;
  bool IsEmpty() const;
  void Clear();

private:
  T* m_array;
  int m_arraySize;
  int m_itemCount;

  void ShiftLeft( int index );
  void ShiftRight( int index );

  void AllocateMemory( int size );
  void Resize( int newSize );

  bool IsFull() const;
};
#+END_SRC

~

*** *Constructor - Preparing the array to be used*

With the constructor here, it is important to assign =nullptr= to
the pointer so that we don't try to dereference a garbage address.
The array size and item count variables should also be assigned to 0.

#+BEGIN_SRC cpp :class cpp
template <typename T>
SmartDynamicArray<T>::SmartDynamicArray()
{
  m_array = nullptr;
  m_itemCount = 0;
  m_arraySize = 0;
}
#+END_SRC


*** *Destructor - Cleaning up the array*

Having a destructor is also very important since we're working with pointers.
Before our data structure is destroyed, we need to make sure that we free
any allocated memory.

#+BEGIN_SRC cpp :class cpp
template <typename T>
SmartDynamicArray<T>::~SmartDynamicArray()
{
  if ( m_array != nullptr )
  {
    delete [] m_array;
    m_array = nullptr;
  }
  m_arraySize = 0;
  m_itemCount = 0;
}
#+END_SRC

We can also put this functionality into the Clear() function, and call Clear()
from the destructor.

*** *void AllocateMemory( int size )*

When the array is not in use, the =m_array= pointer will be pointing to
=nullptr=. In this case, we need to allocate space for a new array before
we can begin putting items into it.

*Error checks:*
- If the =m_array= pointer is NOT pointing to nullptr, throw an exception.

*Functionality:*
1. Allocate space for the array via the =m_array= pointer.
2. Assign =m_arraySize= to the size passed in as a parameter.
3. Set =m_itemCount= to 0.


#+BEGIN_SRC cpp :class cpp
template <typename T>
void SmartDynamicArray<T>::AllocateMemory( int size )
{
  if ( m_array != nullptr )
  {
    throw logic_error( "Can't allocate memory, m_array is already pointing to a memory address!" );
  }

  m_array = new T[ size ];
  m_arraySize = size;
  m_itemCount = 0;
}
#+END_SRC


For this function, if the array is already pointing somewhere, we don't want
to just erase all that data and allocate space for a new array. We want to try
to prevent data loss, so it would be better to throw an exception instead
so that the caller can decide how they want to handle it.

*** *void Resize( int newSize )*

We can't technically resize an array that has been created. We can, however,
allocate more space for a bigger array and copy all the data over and then
update the pointer to point to the new array. And that's exactly how we "resize"
our dynamic array.

*Error checks:*
- If the new size is smaller than the old size, throw an exception.

*Functionality:*
1. If =m_array= is pointing to nullptr, then just call AllocateMemory instead.
2. Otherwise:
   1. Allocate space for a new array with the new size using a new pointer.
   2. Iterate over all the elements of the old array, copying each element to
      the new array.
   3. Free space from the old array.
   4. Update the =m_array= pointer to point to the new array address.
   5. Update the =m_arraySize= to the new size.


#+BEGIN_SRC cpp :class cpp
template <typename T>
void SmartDynamicArray<T>::Resize( int newSize )
{
  if ( newSize < m_arraySize )
  {
    throw logic_error( "Invalid size!" );
  }
  else if ( m_array == nullptr )
  {
    AllocateMemory( newSize );
  }
  else
  {
    T* newArray = new T[newSize]; // New array

    // Copy values over
    for ( int i = 0; i < m_itemCount; i++ )
    {
      newArray[i] = m_array[i];
    }

    delete [] m_array;      // Deallocate old space
    m_array = newArray;     // Update pointer
    m_arraySize = newSize;  // Update size
  }
}
#+END_SRC

*** *Updating other functions*

- *ShiftLeft:*   If =m_array= is pointing to =nullptr=, throw an exception.
- *ShiftRight:*
  - If =m_array= is pointing to =nullptr=, throw an exception.
  - If the array is full, call Resize.

- *PushBack, PushFront, PushAt:*
  - If =m_array= is pointing to =nullptr= call AllocateMemory.
  - If the array is full, call Resize.