/*
  WVector.h - Vector library for Wiring & Arduino
  Copyright (c) 2009 Hernando Barragan.  All right reserved.

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
*/

#ifndef Vector_h
#define Vector_h

#include <ctype.h>
#include <stdlib.h>

template <class Element>
class Vector {
  public:
    // constructors
    Vector( unsigned int initialCapacity = 10, unsigned int capacityIncrement = 10 );
    Vector( const Vector& rhv );
    virtual ~Vector();

    // methods
    unsigned int capacity() const;
    boolean contains( const Element& elem ) const;
    const Element& firstElement() const;
    int indexOf( const Element& elem ) const;
    boolean isEmpty() const;
    const Element& lastElement() const;
    int lastIndexOf( const Element& elem ) const;
    unsigned int size() const;
    void copyInto( Element* array ) const;
    inline boolean add( const Element& obj ) { addElement(obj);  return true; }
    void addElement( const Element& obj );
    inline void clear() { removeAllElements(); }
    void ensureCapacity( unsigned int minCapacity );
    void removeAllElements();
    boolean removeElement( const Element& obj );
    void setSize( unsigned int newSize );
    void trimToSize();
    const Element& elementAt( unsigned int index ) const;
    void insertElementAt( const Element& obj, unsigned int index );
    const Element& remove( unsigned int index );
    void removeElementAt( unsigned int index );
    void setElementAt( const Element& obj, unsigned int index );
    inline const Element& get( unsigned int index ) const
      { return elementAt(index); }

    const Element& operator[]( unsigned int index ) const;
    Element& operator[]( unsigned int index );

  protected:
    unsigned int _size;
    unsigned int _capacity;
    unsigned int _increment;
    Element** _data;
  };

template <class Element>
Vector<Element>::Vector( unsigned int initialCapacity, unsigned int capacityIncrement )
{
  _size = 0;
  _capacity = initialCapacity;
  _data = new Element*[ _capacity ];
  _increment = capacityIncrement;
};

template <class Element>
Vector<Element>::Vector( const Vector<Element>& rhv )
{
  _size = rhv._size;
  _capacity = rhv._capacity;
  _data = new Element*[ _capacity ];
  _increment = rhv._increment;
  
  for( unsigned int i = 0; i < _size; i++ )
  {
    _data[i] = new Element( *(rhv._data[i]) );
  }
};

template <class Element>
Vector<Element>::~Vector()
{
  removeAllElements();
  delete [] _data;
};

template <class Element>
unsigned int Vector<Element>::capacity() const
{
  return _capacity;
};

template <class Element>
boolean Vector<Element>::contains( const Element &elem ) const
{
  for ( unsigned int i = 0; i < _size; i++ )
  {
    if ( *_data[i] == elem )
      return true;
  }
  
  return false;
};

template <class Element>
void Vector<Element>::copyInto( Element* array ) const
{
  for( unsigned int i = 0; i < _size; i++ )
    array[i] = *_data[i];
};


template <class Element>
const Element & Vector<Element>::elementAt( unsigned int index ) const
{
  // add check for valid index
  return *_data[index];
};

template <class Element>
const Element & Vector<Element>::firstElement() const
{
  if ( _size == 0 )
  {
    // do something :) 
  }
  
  return *_data[ 0 ];
};

template <class Element>
int Vector<Element>::indexOf( const Element &elem ) const
{
  for ( unsigned int i = 0; i < _size; i++ )
  {
    if ( *_data[ i ] == elem )
      return i;
  }
  
  return -1;
};

template <class Element>
boolean Vector<Element>::isEmpty() const
{
  return _size == 0;
};

template <class Element>
const Element & Vector<Element>::lastElement() const
{
    if ( _size == 0 )
    {
    // do something  
    }
  
    return *_data[ _size - 1 ];
};

template <class Element>
int Vector<Element>::lastIndexOf( const Element &elem ) const
{
  //  check for empty vector
  if ( _size == 0 )
    return -1;
  
  unsigned int i = _size;
  
  do
  {
    i -= 1;
    if ( *_data[i] == elem )
      return i;
    
  }
  while ( i != 0 );
  
  return -1;
};

template <class Element>
unsigned int Vector<Element>::size() const
{
  return _size;
};

template <class Element>
void Vector<Element>::addElement( const Element &obj )
{
  if ( _size == _capacity )
    ensureCapacity( _capacity + _increment );
  
  _data[ _size++ ] = new Element( obj );
};

template <class Element>
void Vector<Element>::ensureCapacity( unsigned int minCapacity )
{
  if ( minCapacity > _capacity )
  {
    unsigned int i;
    _capacity = minCapacity;
    Element** temp = new Element*[ _capacity ];
    // copy all elements
    memcpy( temp, _data, sizeof(Element*) * _size );
    
    delete [] _data;
    _data = temp;
  }
};

template <class Element>
void Vector<Element>::insertElementAt( const Element &obj, unsigned int index )
{
  if ( index == _size )
    addElement( obj );
  else
  {
    //  need to verify index, right now you must know what you're doing
    if ( _size == _capacity )
      ensureCapacity( _capacity + _increment);
    
    Element* newItem = new Element(obj);  //  pointer to new item
    Element* tmp;  // temp to hold item to be moved over
    
    for( unsigned int i = index; i <= _size; i++ )
    {
      tmp = _data[i];
      _data[i] = newItem;
      
      if ( i != _size )
        newItem = tmp;
      else
        break;
    }
  }
  _size++;
};

template <class Element>
const Element& Vector<Element>::remove( unsigned int index )
{
  Element retval = get(index);
  removeElementAt(index);
  return retval;
};

template <class Element>
void Vector<Element>::removeAllElements()
{
  // avoid memory leak
  for ( unsigned int i = 0; i < _size; i++ )
    delete _data[i];
  
  _size = 0;
};

template <class Element>
boolean Vector<Element>::removeElement( const Element &obj )
{
  for ( unsigned int i = 0; i < _size; i++ )
  {
    if ( *_data[i] == obj )
    {
      removeElementAt( i );
      return true;
    }
  }
  return false;
};

template <class Element>
void Vector<Element>::removeElementAt( unsigned int index )
{
  // check for valid index
  
  delete _data[ index ];
  
  unsigned int i;
  for ( i = index+1; i < _size; i++ )
    _data[ i - 1 ] = _data[ i ];
  
  _data[i];
  _size--;
};

template <class Element>
void Vector<Element>::setElementAt( const Element &obj, unsigned int index )
{
  // check for valid index
    
  *_data[ index ] = obj;
};

template <class Element>
void Vector<Element>::setSize( unsigned int newSize )
{
  if ( newSize > _capacity )
    ensureCapacity( newSize );
  else if ( newSize < _size )
  {
    for( unsigned int i = newSize; i < _size; i++ )
      delete _data[i];
    
    _size = newSize;
  }
};

template <class Element>
void Vector<Element>::trimToSize()
{
  if ( _size != _capacity )
  {
    Element** temp = new Element*[ _size ];
    unsigned int i;
    
    for ( i = 0; i < _size; i++ )
      temp[i] = _data[i];
    
    delete [] _data;
    
    _data = temp;
    _capacity = _size;
  }
};

template <class Element>
const Element & Vector<Element>::operator[]( unsigned int index ) const
{
  return elementAt( index );
};

template <class Element>
Element & Vector<Element>::operator[]( unsigned int index )
{
  // check for valid index 
  return *_data[ index ];
};

#endif
