#include<iostream>
#include<string>
#include<list>
using namespace std;

template <typename T>
struct Node{
	T data;
	Node<T> *next;
	Node():data(0),next(0){}
	Node(T d, Node<T>* n=0):data(d),next(n){}
};

template<class X>
class slink{
private:
	Node<X>* head;
public:
	slink():head(0){}
	~slink(){
		Node<X> *c = head;
		while(c != 0){
			Node<X> *t = c;
			c = c->next;
			delete t;
		}
	}
	void wipeOut(X d){
		if(head==0){
			cout << "attempt to wipeOut on empty list" << endl;
			return;
		}
		// search for deletion point
		Node<X> *c = head;
		Node<X> *p = 0;
		while(c != 0  && c->data != d){
			p = c;
			c = c->next;
		}
		if(c == 0){
			cout << d << " not in list "<<endl;
			return;
		}
		// delete head
		if(p==0){
			head = head->next;
			delete c;
		}
		// middle delete
		else if(p!=0&&c!=0){
			p->next = c->next;
			delete c;
		}
		else if(c==0){
			p->next = 0;
			delete c;
		}

	}
	void add(X d){
		if(head==0){
			head = new Node<X>(d);
			return;
		}

		// search for insertion point
		Node<X> *c = head;
		Node<X> *p = 0;
		while(c != 0  && c->data < d){
			p = c;
			c = c->next;
		}
		// beginning insert
		if(p == 0){
			head = new Node<X>(d,head);
			return;
		}
		// end insert
		else if(c==0){
			p->next = new Node<X>(d);
		}
		// middle insert
		else{
			p->next = new Node<X>(d,c);
		}

	}
	template<class T>
		friend ostream& operator <<(ostream & o, slink<T> & s);
};
template<class M>
ostream& operator <<(ostream & o, slink<M> & s){
	Node<M> *c = s.head;
	while(c!=0){
		o << c->data << endl;
		c = c->next;
	}
	return o;
}


void main(){
	slink<int> s;
	s.add(3);
	s.add(1);
	s.add(17);
	s.add(5);
	cout << s << endl;
	cout << endl << "starting to wipeOut "<<endl<<endl;
	s.wipeOut(1);
	s.wipeOut(5);
	s.wipeOut(17);
	s.wipeOut(17);
	s.wipeOut(3);
	s.wipeOut(3);
	cout << s << endl;
	slink<string> ss;
	ss.add("tau");
	ss.add("gamma");
	ss.add("mu");
	ss.add("chi");
	cout << ss << endl;
	list<double> ld;
	ld.push_back(3.14159);
	ld.push_back(2.7182);
	ld.sort();
	ostream_iterator<double> out(cout, "\n");
	copy(ld.begin(), ld.end(), out);

}