// File: LinkList.h
// Definitions for Linked MyVectorList 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 <typename listEltType> class MyVectorList {

public:

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

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

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

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

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

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

 // Pre:  MyVectorList is ordered, item is found in list
 // Post: MyVectorList 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();

 vector<listEltType> theList; // the data
};

// Implementation of vector-implemented Linked List Class

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

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

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

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

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

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

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

template <typename listEltType> 
		listEltType &MyVectorList<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 <typename listEltType> int MyVectorList<listEltType>::countNodes()
{return(theList.size());}

/* This has been commented out because it does not pass the vector as a const reference
template <typename listEltType> 
		ostream &operator<<(ostream &out,MyVectorList<listEltType> aList)
{for (typename vector<listEltType>::iterator it=aList.theList.begin();
						it!=aList.theList.end();it++)
	out << *it << " ";
 return(out);
}*/

template <typename listEltType> 
		ostream &operator<<(ostream &out,const MyVectorList<listEltType> &aList)
{for (typename vector<listEltType>::const_iterator it=aList.theList.begin();
						it!=aList.theList.end();it++)
	out << *it << " ";
 return(out);
}

#endif