#include <string>
    #include <iostream>
    #ifndef ARRAYLIST_H
    #define ARRAYLIST_H
 
    using namespace std;
 
    class ArrayListException
    {
      public:
        ArrayListException(const string& aMessage)
        {
          message=aMessage;
        }
        string what() const
        {
          return message;
        }
      private:
        string message;
    };
 
    template <typename T>
    class ArrayList
    {
      public:
        cout<<"liststart";
        ArrayList<T>();
        cout<<"listfinish";
        virtual ~ArrayList<T>();
        ArrayList<T>(const ArrayList<T>& rhs);
        void add(T element);
        void add(int index, T element) throw(ArrayListException);
        T& operator[](int index)const throw(ArrayListException);
        T remove(int index) throw(ArrayListException);
        long size() const;
      private:
        template <typename U> class Node;
        Node<T>* rear;
        Node<T>* head;
        long length;
    };
 
 
    template <class U>
    template <typename T>
    class ArrayList<U>::Node
    {
      public:
        Node(T s);
 
      private:
        T data;
        Node<T>* next;
        friend class ArrayList<U>;
    };

    #include <iostream>
    #include <cassert>
    #include <string>
    #include "arraylist.h"
 
    using namespace std;
 
    template <typename T>
    ArrayList<T>::ArrayList()
    {
      head=NULL;
      rear=NULL;
      length=0;
    }
    template<typename T>
    ArrayList<T>::ArrayList(const ArrayList<T>& rhs)
    {
      int i;
      for(i=0; i<rhs.size(); i++)
      {
	T element = rhs[i];
        add(element);
      }
    }
 
 
    template <typename T>
    ArrayList<T>::~ArrayList()
    {
      Node<T>* tmp;
      while(head)
      {
        tmp=head;
        head=head->next;
        delete tmp;
      }
    }
 
 
    template<typename T>
    void ArrayList<T>::add(T element)
    {
      Node<T>* tmp;
      Node<T>* newNode=new Node<T>(element);
      if(length==0)
      {
        head = newNode;
      }
      else
      {
        rear->next=newNode;
        rear=rear->next;
      }
      length++;
    }
 
 
    template<typename T>
    void ArrayList<T>::add(int index, T element) throw(ArrayListException)
    {
      if(index<0||index>length)
        throw ArrayListException("Stack Exception: top() called on empty stack.");
        Node<T>* newnode=new Node<T>(element);
        this[index-1]->next=newnode;
        newnode->next=this[index]; 
    }
 
 
    template<typename T>
    T& ArrayList<T>::operator[](int index)const throw(ArrayListException)
    {
      if(index<0||index>length-1 )
        throw ArrayListException("Stack Exception: top() called on empty stack.");
        int i;
        Node<T>*tmp;
        tmp=head;
        for(i=0; i<index; i++)
          tmp=tmp->next;
        return tmp->data;
    }
 
 
    template<typename T>
    T ArrayList<T>::remove(int index) throw(ArrayListException)
    {
      Node<T>* nodePtr;
      T item;
      if(index<0||index>length-1)
        throw ArrayListException("Stack Exception: top() called on empty stack.");
        return head->data;
    }
 
 
    template<typename T>
    long ArrayList<T>::size() const
    {
      return length;
    } 
 
 
    template <class U>
    template <typename T>
    ArrayList<U>::Node<T>::Node(T s)
    {
      data=s;
      next=NULL;
    }