// Author: Hannah C. Tang (hctang@cs)
//
// Implementation for a templated array class with bounds checking
// Data in this array is kept in sorted order


#include <iostream>           // For printing to the screen
#include <cassert>            // For assert()
using namespace std;

#include "SortedArray.hh"

//
// Overloaded constructor.  Note the use of the member initialization list
// to initialize m_capacity and m_comp before its use in the body of 
// the constructor
//
template< typename DataType, typename Comparator >
SortedArray< DataType, Comparator >::SortedArray( int initCapacity, 
                                                  const Comparator& c )
    : m_capacity( initCapacity ),
      m_size( 0 ),
      m_comp( c )  // Const data members *must* be initialized (and not 
                   // assigned to) in the member initialization list
{
    m_pData = new DataType[ m_capacity ];
}


//
// Copy constructor.  Uses the member function Copy().  Note that there
// is no need to delete m_pData.  Why do you think this is the case?
//
template< typename DataType, typename Comparator >
SortedArray< DataType, Comparator >::SortedArray( const SortedArray& other )
{
    Copy( other );
}


//
// Assignment operator.  Uses the member functions Copy() and Destroy().
// Remember that it is necessary to check against self-assignment. 
// Why does the assignment operator need to delete m_pData but the
// copy constructor does not?
//
template< typename DataType, typename Comparator >
const SortedArray< DataType, Comparator >&
SortedArray< DataType, Comparator >::operator=( const SortedArray& other )
{
    if( this != &other )
    {
        Destroy();       // Delete existing memory
        Copy( other );   // Copy 'other' into 'this'
    }
    return *this;
}


//
// Destructor.  Uses the member function Destroy()
//
template< typename DataType, typename Comparator >
SortedArray< DataType, Comparator >::~SortedArray( void )
{
    Destroy();
}


//
// Indexing operator, const version (insertions happen via the Insert() method)
//
template< typename DataType, typename Comparator >
const DataType&
SortedArray< DataType, Comparator >::operator[]( int index ) const
{
    // Invalid index.  Note that I'm using >=, not >
    // Asserting isn't the best way to handle error conditions,
    // but it allows for an informative error message
    assert( index >= 0 && index < m_capacity && "Index out of bounds on operator[]!" );

    return m_pData[ index ];
}


//
// GetCapacity.  Gets the current capacity of the array
//
template< typename DataType, typename Comparator >
int
SortedArray< DataType, Comparator >::GetCapacity( void ) const
{
    return m_capacity;
}


//
// GetSize.  Gets the current number of valid elements in the array
//
template< typename DataType, typename Comparator >
int
SortedArray< DataType, Comparator >::GetSize( void ) const
{
    return m_size;
}


//
// Insert.  Adds the element to the SortedArray, maintaining sorted order
//
template< typename DataType, typename Comparator >
bool
SortedArray< DataType, Comparator >::Insert( const DataType& data )
{
    //
    // Find the proper place in the array to insert the data
    //
    int i;

    for( i = 0; i < m_size; i++ )
    {
        if( m_comp( data, m_pData[ i ] ) )
        {
            // If the Comparator evaluates to "false", then inserting
            // data at the current index will break the element ordering
            // imposed by the Comparator, so we'll insert it prior to i.
            break;
        }
    }

    //
    // Insert the data into the array (assuming there's space)
    //

    // Full array -- do not insert.  Note that this is not the
    // best way to handle an error condition ....
    assert( m_size != m_capacity 
            && "Index out of bounds on insert; array is full!" );        

    // Not full -- shift all the data up on slot and then insert at 
    // the correct location
    for( int j = m_size; j > i; j-- )
    {
        m_pData[ j ] = m_pData[ j - 1 ];
    }

    m_pData[ i ] = data;
    m_size++;

    return true;
}


//
// Copy.  Copies its argument into the current instance
//
template< typename DataType, typename Comparator >
void
SortedArray< DataType, Comparator >::Copy( const SortedArray& other )
{
    m_capacity = other.m_capacity;
    m_size = other.m_size;

    // Create an array that is the same size as 'other', and
    // copy other's data over
    DataType* pNewData = new DataType[ m_capacity ];

    for( int i = 0; i < m_size; i++ )
    {
        pNewData[ i ] = other.m_pData[ i ];
    }

    // Delete our old data.  Note that I'm using delete[], not delete
    delete [] m_pData;
}


//
// Destroy.  Cleans up the current instance (deletes dynamic memory, etc)
//
template< typename DataType, typename Comparator >
void
SortedArray< DataType, Comparator >::Destroy( void )
{
    delete [] m_pData; // C++ trivia: deleting NULL is defined to be a no-op
                       // Note that I'm using delete[], not delete.  Remember:
                       // if you use new[], it *must* be matched with delete[]
    m_pData = NULL;
    m_capacity = 0;
}