// *********************************************************
// Header file List.h for the ADT list.
// Array-based implementation. Using templates.
// *********************************************************
#include "ListIndexOutOfRangeException.h"
#include "ListException.h"

// declaration of the class
template <typename T>
class List
{
public:
   List();                    
   // default constructor

   bool isEmpty() const;
  // Determines whether a list is empty.
  // Precondition: None.
  // Postcondition: Returns true if the list is empty,
  // otherwise returns false.
  // Throws: None.

   int size() const;
  // Determines the length of a list.
  // Precondition: None.
  // Postcondition: Returns the number of items that are
  // currently in the list.
  // Throws: None.

   const T& get(int index) const
     throw(ListIndexOutOfRangeException);
  // Retrieves a list item by position.
  // Precondition: index is the number of the item to be
  // retrieved.
  // Postcondition: If 1 <= index <= size(), the item at
  // position index in the list is returned.
  // Throws: ListIndexOutOfBoundsException if index < 1 or 
  // index > size().

   void add(int index, const T& newItem)
     throw(ListIndexOutOfRangeException,ListException);
  // Adds an item to the list at position index.
  // Precondition: index indicates the position at which  
  // the item should be inserted in the list.
  // Postcondition: If insertion is successful, item is 
  // at position index in the list, and other items are
  // renumbered accordingly.
  // Throws: ListIndexOutOfBoundsException if index < 1 or 
  // index > size()+1.
  // Throws: ListException if item cannot be placed on 
  // the list.

   void remove(int index)
     throw(ListIndexOutOfRangeException);
  // Deletes an item from the list at a given position.
  // Precondition: index indicates where the deletion 
  // should occur. 
  // Postcondition: If 1 <= index <= size(), the item at 
  // position index in the list is deleted, and other items
  // are renumbered accordingly.
  // Throws: ListIndexOutOfBoundsException if index < 1 or 
  // index > size().

   void removeAll();
  // Deletes all the items from the list.
  // Precondition: None.
  // Postcondition: The list is empty.
  // Throws: None.

private:

	static const int MAX_LIST = 100;
	T items[MAX_LIST];  // an array of list items - stored by value,
	                    // not by references as in Java
	int numItems;  // number of items in list
  int List::translate(int position) const;

}; // end class

// definitions of the method:
template <typename T>
List<T>::List() 
{
	numItems = 0;
}  // end default constructor
	
template <typename T>
bool List<T>::isEmpty() const 
{
	return (numItems == 0);
} // end isEmpty
	
template <typename T>
int List<T>::size() const 
{
	return numItems;
}  // end size
	
template <typename T>
void List<T>::removeAll() 
{
	numItems = 0;
} // end removeAll
	
template <typename T>
void List<T>::add(int index, const T& item) 
	throw(ListIndexOutOfRangeException,ListException)  
{
	if (numItems > MAX_LIST) {
		throw ListException("ListException on add");
	}  // end if
	if (index >= 1 && index <= numItems+1) {
		// make room for new element by shifting all items at 
		// positions >= index toward the end of the 
		// list (no shift if index == numItems+1)
		for (int pos = numItems; pos >= index; pos--) {
			items[translate(pos+1)] = items[translate(pos)];
		} // end for
			// insert new item
		items[translate(index)] = item;
		numItems++;
	} 
	else {  // index out of range
		throw ListIndexOutOfRangeException("ListIndexOutOfBoundsException on add");
	}  // end if
} //end add
	
template <typename T>
const T& List<T>::get(int index) const
	throw(ListIndexOutOfRangeException) 
{
	if (index >= 1 && index <= numItems) {
		return items[translate(index)];
	}
	else  {  // index out of range
		throw ListIndexOutOfRangeException("ListIndexOutOfBoundsException on get");
	}  // end if
} // end get
	
template <typename T>
void List<T>::remove(int index) 
	throw(ListIndexOutOfRangeException) 
{
//  cout <<"List::remove"<<endl;
	if (index >= 1 && index <= numItems) {
		// delete item by shifting all items at 
		// positions > index toward the beginning of the list
		// (no shift if index == size)
		for (int pos = index+1; pos <= size(); pos++) {
			items[translate(pos-1)] = items[translate(pos)];
		}  // end for
		numItems--;
	}
	else {  // index out of range
		throw ListIndexOutOfRangeException("ListIndexOutOfBoundsException on remove");
	}  // end if
} // end remove
	
template <typename T>
int List<T>::translate(int position) const
{
	return position - 1;
}  // end translate

// End of header file.