#ifndef RCITLIST_H
#define RCITLIST_H


#ifndef __IOSTREAM_H
#include <iostream.h>
#endif


#ifndef __FSTREAM_H
#include <fstream.h>
#endif

#include<assert.h>

// This file contains templates for a simple linked list, the link
// and a list iterator

// The list in this file has a counted pointer that holds a pointer
// to the first item in the list. As in all counted pointer implementations
// the assigment operator and memberwise copy constructor build aliases
// for the list. This saves memory and allows the user to easily see if
// there are memory leaks. The fact that all standard copying functions
// create aliases means that if you want a copy that will change without
// affecting the original you must use the function List::copy to create
// a copy that is not an alias.

template <class Type> class ListIterator;


template <class Type>
class Link
{
public:
	Link(const Type &LinkValue,Link *nextPtr);//creates a new node with specified value and next item
	Link() {ptrToNextLink = NULL;}
	virtual Link* insert(const Type &val);	//insert item following this Link
	Link*	duplicate();// recursively duplicates list starting at this node
	virtual Link* getNext(){return ptrToNextLink;}// returns pointer to next node
	virtual Link* removeNext();// removes next node and adjusts next to next->next
	Type&	value(){return _value;} // returns a reference to data in node
	virtual ostream& print(ostream &s){return s<<_value;}
	virtual istream& read(istream &s){return s>>_value;}
protected:
	Type _value; // data stored in node
	Link	*ptrToNextLink;// link to next item

};


template <class Type>
class List
{
public:
	List(){ptrToFirstItem = new RCPtr;_size = 0;}
	List(const List&);
	virtual ~List();
	virtual void 	add(const Type &value);				// add to head of List
	void  append(const Type &value);			// add this value to end of the list
	int 	insert(const Type &value);			// insert value if it is not in the list
												// in the simple list this is insert at end
	int  	insertAt(int where,const Type &value);// inserts at location where if possible (returns 1) otherwise returns 0
	void 	deleteAllValues();			// delete all items in List
	inline Type 	firstElement();	// returns first int
	virtual int locate(const Type &value)const;	// is value in the List
	virtual int locateNext(int after,const Type &value)const;// used to find next occurence of a value  
	void 	removeFirst();					// delete the first item in the list
	void 	removeValue(const Type&);  // remove the given item from the list
	inline int	isEmpty()const;		// is the list empty
	inline int size()const {return _size;}  // how large is the list
	List copy();							// creates a copy of the list not an alias
	int fwrite(const char* fName);   // prints file fName, returns 1 if ok 0 otherwise
	ostream& fwrite(ostream&); 		// print the list to the given ostream
	int fread(const char* fName);		// opens the file fName returns 1 if file read 0 otherwise
	virtual istream& fread(istream&);// reads from a file beginning with number of items in list
	void terminalPrint();				// print the list to the screen
	virtual ListIterator<Type>* genIterator();// generates an iterator for a type of list
protected:

	class RCPtr // This is the counted pointer type used to store the first link
	{
	public:
		RCPtr(){data = NULL;count = 1;}
		RCPtr(Link<Type> *p){data = p;count = 1;}
		~RCPtr(){}
		Link<Type> *data; 			// actual pointer to first node in list
		int count;                 // how many copies of list are active
	};
	RCPtr *ptrToFirstItem;			// pointer to node containing head of the List
	int _size;   						// size of the list
	friend  class ListIterator<Type>;
};

template <class Type>
class ShallowList :public List<Type>
{
public:
	ShallowList(Link<Type>*,int);// builds a part of a list starting at the link
	virtual ~ShallowList() // kills the connect to the list so original list left intact
		{
			ptrToFirstItem->data = NULL;//ptrToFirstItem is deleted in ~List->deleteAllItems
		}//list left intact
};


template <class Type>
class ListIterator
{
public:
	ListIterator(List<Type> &list);
	//~ListIterator(){cout<<"ListIterator destroyed\n";}//used to trace debugs
	virtual int 	init();
	Type&	operator()();	// return current value
	Type  operator()(int place){return moveTo(place);} //move to this location in the list return the value
	int 	operator ! ();	//end of list
	int 	operator ++(); //next item in list prefix operator
	int 	operator ++(int); //postfix get next item in list
	void	operator =	(const Type &value); //set the current to value
	virtual void 	removeCurrent();          // remove node at current location
	virtual void 	addBefore(const Type &newValue); // add before current location
	virtual void 	addAfter (const Type &newValue); // add after current location
	// the two locate functions return the location of the item if found 0 otherwise
	virtual int	locate(const Type&);       // locate the first occurrence of an item
	virtual int locateNextAfter(int,const Type&); // locate first occurrence of item after integer position
	Type& operator [](int place) {return moveTo(place);} // return a reference to data at current location
	ListIterator<Type> spawn();//test list cloning creates an iterator for part of the list
	int position(){return _pos;}
	operator int (); //used in while loop to determine the end of a list
protected:

	virtual Type& moveTo(int); // move to this location in the list return value
	virtual void moveToNext(); //advances one through list
	Link<Type>	*current;
	Link<Type>	*previous;
	List<Type>	&theList; //reference to list
	int			_pos;		//used to keep the current position in list
};

template <class Type>
class OrderedIterator :public ListIterator<Type>
{
public:
 	OrderedIterator(List<Type> &l):ListIterator<Type>(l){}
	virtual int locate(const Type&);
};

template <class Type>
class OrderedList : public List<Type>
{
public:
	OrderedList():List<Type>(){}
	OrderedList(const OrderedList &l):List<Type>(l){}
	virtual ListIterator<Type>* genIterator();
	int readAndOrder(const char* fName);// opens the file fName returns 1 if file read 0 otherwise
	istream& readAndOrder(istream&); // reads from an unordered file
	//and creates an ordered list

	friend class OrderedIterator<Type>;
};

//************ code for classes ****************************************


// ** code for Link ********

//****** non-member io operators for link<type>* ***********

template <class Type>
ostream& operator <<(ostream &s,Link<Type> *l)
{
	return l->print(s);//*** print is virtual so may be adjusted as needed
}

template <class Type>
istream& operator >>(istream &s, Link<Type>*l)
{
	return l->read(s);//*** read is virtual so may be adjusted as needed
}


template <class Type>
ostream& operator <<(ostream &s,Link<Type> l)
{
	return l.print(s);//*** print is virtual so may be adjusted as needed
}

template <class Type>
istream& operator >>(istream &s, Link<Type>l)
{
	return l.read(s);//*** read is virtual so may be adjusted as needed
}
//*** end of io non-member operators

template <class Type>
Link<Type>::Link(const Type &val, Link<Type> *nxt)
		:_value(val),ptrToNextLink(nxt){}

template <class Type>
Link<Type>*	Link<Type>::insert(const Type &val)
{
	ptrToNextLink = new Link<Type> (val, ptrToNextLink);
	assert(ptrToNextLink != NULL);
	return ptrToNextLink;
}

template <class Type>
Link<Type>* Link<Type>::removeNext()
{
	Link<Type>* temp = ptrToNextLink;
	if (temp)
	{
		ptrToNextLink = temp->ptrToNextLink;
		delete temp;
	}
	return this;
}

template <class Type>
Link<Type>* Link<Type>::duplicate()
{
	Link<Type> *newLink;
	if(ptrToNextLink != NULL)
		newLink = new Link<Type>(_value,
							ptrToNextLink->duplicate());//recursive step
	else
		newLink = new Link<Type>(_value,NULL);
	assert(newLink != NULL);
	return newLink;
}



//*****************  code for list ***************

template <class Type>
void List<Type>::add(const Type &val)
{
	Link<Type> *p = new Link<Type>(val,ptrToFirstItem->data);
	assert(p!=NULL);
	ptrToFirstItem->data = p;
	_size++;
}


template <class Type>
void List<Type>::append(const Type &value)
{
	ListIterator<Type>loc(*this);
	loc.init();
	for(int i = 1;i<=_size;i++)
		loc++;
	loc.addAfter(value);
}

template <class Type>
int 	List<Type>::insert(const Type &value)
{
	ListIterator<Type>* next = genIterator();
	if(!next->locate(value))
	{
		next->addBefore(value);
		delete next;
		return 1;
	}
	delete next;
	return 0;
}



template <class Type>
int List<Type>::insertAt(int where,const Type &value)
{
	if(where<1 || where>_size +1)
		return 0;
	ListIterator<Type>loc(*this);
	loc.init();
	for(int i = 1;i<where;i++)// start at 1 so only want to move where-1 places
		loc++;
	loc.addBefore(value);
	return 1;
}



template <class Type>
void List<Type>::removeFirst()
{
	Link<Type> *p = ptrToFirstItem->data;
	if (p != NULL)
		{
			ptrToFirstItem->data = p->getNext();
			delete p;
			_size--;
		}
}

template <class Type>
List<Type>::~List()
{
	  //	cout<<"List destructor\n";
		if(--(ptrToFirstItem->count)==0)
		{
			deleteAllValues();
			delete ptrToFirstItem;
		}
}

template <class Type>
void List<Type>::deleteAllValues()
{
	Link<Type> *next;
	for (Link<Type> *p = ptrToFirstItem->data; p !=NULL; p = next)
	{
		next = p->getNext();
		delete p;
	}
	_size = 0;
}


template <class Type>
List<Type>::List(const List<Type> &source)
{
	_size = source._size;
	ptrToFirstItem = source.ptrToFirstItem;
	ptrToFirstItem->count++;
}

template <class Type>
List<Type> List<Type>::copy()
{
	List<Type> L;
	L._size = _size;
	Link<Type> *firstLink = ptrToFirstItem->data;
	L.ptrToFirstItem->data = firstLink->duplicate();
	return L;
}


template <class Type>
int List<Type>::locate(const Type &v)const
{
	return locateNext(0,v);
}

template <class Type>
int List<Type>::locateNext(int after,const Type &v) const
{
	ListIterator<Type> next(*this);
	int loc = after + 1;
	for(next(loc);!next;next++)
		if(next()==v)
			return next.position();
	return 0;
}


template <class Type>
inline int List<Type>::isEmpty()const
{
	return _size == 0;
}

template <class Type>
inline Type List<Type>::firstElement()
{
	Type badReturn;
	if (ptrToFirstItem->data)
		return ptrToFirstItem->data->value();
	else
		return badReturn;
}

template <class Type>
void List<Type>::terminalPrint()
{
	ListIterator<Type> next(*this);
	while (!next)
	{
		cout<<next()<<endl;
		next++;
	}
}

template <class Type>
int List<Type>::fwrite(const char* fName)
{
	ofstream out(fName,ios::out);// ios::out is default-so not needed
	if (!out)//then failed to open the file
	{
		cerr <<"Unable to open this file "<<fName<<endl;
		return 0;
	}
	else
	{
		fwrite(out);
		out.close();
		return 1;
	}
}



template <class Type>
ostream& List<Type>::fwrite(ostream &s)
{
	ListIterator<Type> next(*this);
   s << _size<<endl;
	while (!next)
	{
		s<<next()<<endl;
		next++;
	}
	return s;
}


template <class Type>
int List<Type>::fread(const char* fName)
{
	ifstream in (fName,ios::in);

	if (!in)
	{
		cerr<<"Unable to open file "<<fName<<endl;
		return 0;
	}
	else
	{
		fread(in);
		in.close();
		return 1;
	}
}


template <class Type>
istream& List<Type>::fread(istream &in)
{
	char buff[20];
	int size; // can't use length because it is set by wipeOut and insert
	deleteAllValues();
	Type newData;
	in >> size;
	in.getline(buff,20);// clear out the return at end of line with size
	ListIterator<Type> next(*this);
	next.init();
	for(int i = 1;i<=size;i++)
	{
		Type val;
		in>>val;
		next.addAfter(val);
		next++;
	}
	return in;
}



template <class Type>
void List<Type>::removeValue(const Type &val)
{
	ListIterator<Type> *next = genIterator();
	if (next->locate(val))
		next->removeCurrent();
}

template <class Type>
ListIterator<Type>* List<Type>::genIterator()
{
	ListIterator<Type>* returnVal = new ListIterator<Type>(*this);
	return returnVal;
}

//************* code for ShallowList ***********

template <class Type>
ShallowList<Type>::ShallowList(Link<Type> *p,int sz)
{
	_size = sz;
	ptrToFirstItem = new RCPtr(p);
}


//************  code for ListIterator **********

template <class Type>
ListIterator<Type> ListIterator<Type>::spawn()
{
	static ShallowList<Type> L(current,theList._size-_pos);
	ListIterator result(L);
	return result;
}

template <class Type>
ListIterator<Type>::ListIterator (List<Type> &list)
	:theList(list)
{
	init();
}

template <class Type>
int ListIterator<Type>::init()
{
	previous = NULL;
	current = theList.ptrToFirstItem->data;
	_pos = 1;
	return current !=NULL;
}

template <class Type>
Type&	ListIterator<Type>::operator() (){
	static Type errorDump;
	if(current !=NULL)
		return current->value();
	else
		{
			cerr <<"current item is NULL\n";
			return errorDump;
		}
}


template <class Type>
Type& ListIterator<Type>::moveTo(int i)
{
	static Type errorDump;


	if(i<=0||i>theList._size+1)
	{
		cerr<<"Subscript "<<i<<" is out of range\n";
		return errorDump;
	}
	init();
	for ( _pos =1;_pos<i;_pos++)
	{
		if (current->getNext())
		{
			previous = current;
			current = current->getNext();
		}
	}

	if (current)
		return current->value();
	else
		return errorDump;

}


template <class Type>
void ListIterator<Type>::operator = (const Type &val){
	assert(current != NULL);
	current ->value() = val;
}

template <class Type>
void ListIterator<Type>::moveToNext()
{
	previous = current;
	current = current->getNext();
	_pos++;
}

template <class Type>
int ListIterator<Type>::operator ++()
{
	if(current == NULL)
	{
		if(previous ==NULL)
		{
			current = theList.ptrToFirstItem->data;
			_pos = 1;
		}
		else
			current = previous->getNext();
	}
	else
		moveToNext();
	return current !=NULL;
}


template <class Type>
int ListIterator<Type>::operator ++(int)
{
	if(current == NULL)
	{
		if(previous ==NULL)
		{
			current = theList.ptrToFirstItem->data;
			_pos = 1;
		}
		else
			current = previous->getNext();
	}
	else
		moveToNext();
	return current !=NULL;
}


template <class Type>
void ListIterator<Type>::addBefore(const Type &val)
{
	if (previous)
	{
		previous = previous->insert(val);
		theList._size++;
	}
	else
	{
		theList.List<Type>::add(val);// add at beginning of list
		previous = theList.ptrToFirstItem->data;
		current = previous->getNext();
	}
	_pos++;
}

template <class Type>
void ListIterator<Type>::addAfter(const Type &val)
{
	if (current != NULL)
	{
		current->insert(val);
		theList._size++;
	}
	else if(previous != NULL)
	{
		current = previous->insert(val);
		theList._size++;
	}
	else
		theList.List<Type>::add(val);
}

template <class Type>
int ListIterator<Type>::locate(const Type &val)
{
	return locateNextAfter(0,val);
}

template <class Type>
int ListIterator<Type>::locateNextAfter(int after,const Type &val)
{
	after++;
	if(after<=0||after>theList._size+1)
	{
		cerr<<"Subscript "<<after<<" is out of range\n";
		return 0;
	}
	moveTo(after);

	while (current)
	{
		if (current->value() == val)
			return _pos;
		moveToNext();
	}
	return 0;
}

template <class Type>
int ListIterator<Type>::operator !()
{
	if(current == NULL)
		if(previous != NULL)
			current = previous->getNext();
	return current != NULL;
}

template <class Type>
ListIterator<Type>::operator int ()
{
	if(current == NULL)
		if(previous != NULL)
			current = previous->getNext();
	return current != NULL;
}

template <class Type>
void ListIterator<Type>::removeCurrent()
{
  //	cout<<"In ListIterator::removeCurrent... removing "<<current->value()<<endl;
	if(previous == NULL && current) // removing the first item in the list
	{
		theList.ptrToFirstItem->data = current->getNext();
		delete current;
	}
	else  // not the first item in the list
		previous->removeNext();
	theList._size--;
	current =NULL;
}


//************ OrderedIterator code **************

template <class Type>
int OrderedIterator<Type>::locate(const Type &val)
{
	init();
	while (current && current->value() <= val)
	{
		if (current->value() == val)
			return _pos;
		moveToNext();
	}
	return 0;
}

//************ OrderedList code *******************


template <class Type>
ListIterator<Type>* OrderedList<Type>::genIterator()
{
	ListIterator<Type>* returnVal = new OrderedIterator<Type>(*this);
	return returnVal;
}


template <class Type>
int OrderedList<Type>::readAndOrder(const char* fName)
{
	ifstream in (fName,ios::in);

	if (!in)
	{
		cerr<<"Unable to open file "<<fName<<endl;
		return 0;
	}
	else
	{
		readAndOrder(in);
		in.close();
		return 1;
	}
}


template <class Type>
istream& OrderedList<Type>::readAndOrder(istream &in)
{
	char buff[20];
	int size; // can't use length because it is set by wipeOut and insert
	deleteAllValues();
	Type newData;
	in >> size;
	in.getline(buff,20);// clear out the return at end of line with size
	OrderedIterator<Type> next(*this);

	for(int i = 1;i<=size;i++)
	{
		Type val;
		in>>val;
		if(!next.locate(val))//could just call insert here but is less efficient
		  next.addBefore(val);// since insert must create the iterator for each
									// call to insert.
	}
	return in;
}

class IntList :public List<int>{};

#endif