// File: LinkList.h
// Definitions for Linked List ADT
// The linked list contains a dummy header node that is initialized to
//	hold a value that will always come first


#ifndef LINK_LIST_H
#define LINK_LIST_H

#include <iostream>
#include <vector>

using namespace std;

template <class listEltType>
class List {

public:

 // Constructor...Initialize List to NULL
 // Pre:
 List();

// No destructor or copy constructor need be explicitly implemented
// There are no pointers in this implementation, so defaults are fine

 // Pre:  None
 // Post: List is empty
 void init();

 // Pre:  Argument contains element of the proper type 
 // Post: List contains at least one element (not necessarily ordered)
 void insertAtHead(const listEltType &);

 // Pre:  List is ordered
 // Post: List is ordered, containing one additional element
 void insertInOrder(const listEltType &);

 // Pre:  List contains at least one element
 // Post: List contains one less element
 void removeHead();

 // Pre:  List is ordered, item is found in list
 // Post: List is ordered, containing one additional element
 void deleteInOrder(const listEltType &);

 // Pre:  None
 // Post: Boolean value returned
 bool search(const listEltType&);

 // Retrieve a listEltType reference using an int key
 listEltType &retrieve(const int &);

 // Pre:  None
 // Post: Value returned is number of elements in list
 int countNodes();

 friend ostream &operator<<(ostream &,List);

 vector<listEltType> theList;

};

// Implementation of vector-implemented List Class

using namespace std;

template <class listEltType> List<listEltType>::List()
{} // No constructor necessary. Vector starts empty

// Start from scratch
template <class listEltType> void List<listEltType>::init()
{theList.clear();}

template <class listEltType> 
		void List<listEltType>::insertAtHead(const listEltType &elt)
{vector<listEltType>::iterator it=theList.begin();
 theList.insert(it,elt);
 // easier: theList.insert(theList.begin(),elt);
}

template <class listEltType> 
		void List<listEltType>::insertInOrder(const listEltType &elt)
{vector<listEltType>::iterator it;
 for (it=theList.begin();it!=theList.end() && *it<elt;it++);
 theList.insert(it,elt);
}

template <class listEltType> void List<listEltType>::removeHead()
{theList.erase(theList.begin());
}

template <class listEltType> 
		void List<listEltType>::deleteInOrder(const listEltType &elt)
{vector<listEltType>::iterator it;
 for (it=theList.begin();*it!=elt;it++);//assumes it will be found...crash if not
 theList.erase(it);
}

template <class listEltType> 
		bool List<listEltType>::search(const listEltType &elt)
{vector<listEltType>::iterator it;
 for (it=theList.begin();it!=theList.end() && *it!=elt;it++);
 return(it!=theList.end());
}

template <class listEltType> 
		listEltType &List<listEltType>::retrieve(const int &key)
{// This function can be easily adapted to search in objects or structs for
 // a member that is an int
}

template <class listEltType> int List<listEltType>::countNodes()
{return(theList.size());}


template <class listEltType> 
		ostream &operator<<(ostream &out,List<listEltType> aList)
{for (vector<listEltType>::iterator it=aList.theList.begin();
										it!=aList.theList.end();it++)
	out << *it;
 return(out);
}

ostream &operator<<(ostream &out,List<int> aList)
{for (vector<int>::iterator it=aList.theList.begin();it!=aList.theList.end();it++)
	out << *it;
 return(out);
}

#endif