/* Homework #2. Abstract class: linked array and derivates.  */
/*    Roman V. ShapovAlov. CM&C-210. overrider@cmcspec.ru    */

#include <iostream>

using namespace std;

enum origin_t {OR_HEAD,OR_BEFORE_CUR,OR_AFTER_CUR,OR_TAIL};

struct LAError {
	string errmsg;
	LAError (string em){errmsg = em;}};

template<class T> class LinkedArray{
	
	struct Link{
		Link *pre, *suc;
		T data;
		Link (Link *p, Link *s, const T& d): pre(p), suc(s), data(d) {}
	};
	
	Link *head, *tail; 
	mutable Link *cur;

public:	
	LinkedArray (): head(NULL), tail(NULL), cur(NULL) {}
	LinkedArray (const T& d): head (new Link(NULL,NULL,d)), cur(NULL) { tail = head;}
	LinkedArray (const LinkedArray &list);
	virtual ~LinkedArray () { toHead();
		while (!isEmpty()) removeLink(OR_HEAD); 
	}
	
	LinkedArray& operator= (const LinkedArray& list);
	T& operator[] (unsigned index) const{  unsigned i = 0;
		for (toHead();index>i;toNext(),i++) 
			if (!isCur()) throw (LAError("Out of bounds error")); // exception!!!
		if (!isCur()) throw (LAError("Out of bounds error"));
		return cur->data;}
	unsigned length () const {int i = 0;
		for (toHead();isCur();toNext()) i++;
		return i;}
	LinkedArray operator+ (const LinkedArray& list) const;
	
	void addLink (T d, origin_t origin);
	T removeLink (origin_t origin);
	
	bool isEmpty() const { return (head == NULL);}
	void toHead () const { cur = head; }
	void toTail () const { cur = tail; }
	void toNext () const { cur = cur->suc; }
	void toPrev () const { cur = cur->pre; }
	bool isCur  () const { return cur!=NULL; } 
	T getCurVal () const 
		{ if (!cur) throw (LAError("No cursor")); return cur->data; }
	bool search (T elem) const{
		for (toHead();isCur();toNext()) if (getCurVal() == elem) return true;
		return false;}
};

template<class T> LinkedArray<T>::LinkedArray (const LinkedArray &list){
	head = tail = cur = NULL;
	if (list.isEmpty()) return;
	for (list.toHead(); list.isCur(); list.toNext()) 
		addLink(list.getCurVal(),OR_TAIL);
}

template<class T> LinkedArray<T>& LinkedArray<T>::operator= (const LinkedArray& list){
	if (this == &list) return *this;
	head = tail = cur = NULL;
	if (list.isEmpty())  return *this;
	for (list.toHead(); list.isCur(); list.toNext()) 
		addLink(list.getCurVal(),OR_TAIL);
	return *this;
}

template<class T> LinkedArray<T> LinkedArray<T>::operator+ (const LinkedArray& list) const{
	LinkedArray resList = *this; 
	for (list.toHead(); list.isCur(); list.toNext()) 
		resList.addLink(list.getCurVal(),OR_TAIL);
	return resList; 
}

template<class T> void LinkedArray<T>::addLink (T d, origin_t origin){
	if (!head) { tail = head = new Link(NULL,NULL,d); return;} 
	if (origin == OR_BEFORE_CUR){// cur != NULL
		if (!isCur()) throw (LAError("Out of bounds error"));
		if (cur == head) origin = OR_HEAD; else {
			Link *tmp = new Link(cur->pre,cur,d);
			cur->pre->suc = tmp; cur->pre = tmp; return;
		}
	}
	if (origin == OR_AFTER_CUR){// cur != NULL
		if (!isCur()) throw (LAError("Out of bounds error"));
		if (cur == tail) origin = OR_TAIL; else {
			Link *tmp = new Link(cur,cur->pre,d);
			cur->suc->pre = tmp; cur->suc = tmp; return;
		}
	}
	if (origin == OR_HEAD){
		Link *tmp = new Link(NULL,head,d);
		head->pre = tmp;  head = tmp;  return;
	}
	if (origin == OR_TAIL){
		Link *tmp = new Link(tail,NULL,d);
		tail->suc = tmp;  tail = tmp;  return;
	}
}

template<class T> T LinkedArray<T>::removeLink (origin_t origin){
	if (origin == OR_BEFORE_CUR || origin == OR_AFTER_CUR){ // cur != NULL
		if (!isCur()) throw (LAError("Out of bounds error"));
		if (cur == head) origin = OR_HEAD; else 
		if (cur == tail) origin = OR_TAIL; else{
			T t = cur->data;
			cur->pre->suc = cur->suc; cur->suc->pre = cur->pre; 
			delete cur; cur = NULL; return t;
		}
	}
	if (origin == OR_HEAD){ 
		T t = head->data;   Link *tmp = head->suc;  
		if (tmp) tmp->pre = NULL; else tail = NULL;  
		delete head;   head = tmp;  cur = NULL;
		return t;}
	if (origin == OR_TAIL){ 
		T t = tail->data;   Link *tmp = tail->pre;  
		if (tmp) tmp->suc = NULL; else head = NULL;  
		delete tail;   tail = tmp;  cur = NULL;
		return t;}	
	T t; return t;  // no any idea here!! =)
}

template<class T> ostream& operator<< (ostream& out, const LinkedArray<T>& list){
	for (list.toHead(); list.isCur(); list.toNext()) out<<list.getCurVal()<<" "; 
	return out;}

template<class T> class Stack: protected LinkedArray<T>{
public:
	Stack (): LinkedArray<T>() {}
	Stack (const T& d): LinkedArray<T> (d) {}
	~Stack () {}
	
	bool isEmpty () const {return LinkedArray<T>::isEmpty();}
	void push (T d) {LinkedArray<T>::addLink(d,OR_TAIL);}
	T pop () {return LinkedArray<T>::removeLink(OR_TAIL);}
};

template<class T> class Queue: protected LinkedArray<T>{
public:
	Queue (): LinkedArray<T>() {}
	Queue (const T& d): LinkedArray<T> (d) {}
	~Queue () {}
	
	bool isEmpty () const {return LinkedArray<T>::isEmpty();}
	void push (T d) {LinkedArray<T>::addLink(d,OR_HEAD);}
	T pop () {return LinkedArray<T>::removeLink(OR_TAIL);}
};

template<class T> class Deck: protected LinkedArray<T>{
public:
	Deck (): LinkedArray<T>() {}
	Deck (const T& d): LinkedArray<T> (d) {}
	~Deck () {}
	
	bool isEmpty () const {return LinkedArray<T>::isEmpty();}
	void pushToHead (T d) {LinkedArray<T>::addLink(d,OR_HEAD);}
	void pushToTail (T d) {LinkedArray<T>::addLink(d,OR_TAIL);}
	T popFromHead () {return LinkedArray<T>::removeLink(OR_HEAD);}
	T popFromTail () {return LinkedArray<T>::removeLink(OR_TAIL);}
};

int main (){
	LinkedArray<int> l1(3);
	LinkedArray<int> l2 = 1;
	LinkedArray<int> l3;
	l1.addLink (4,OR_TAIL);  l1.addLink (5,OR_TAIL);  l1.addLink (6,OR_TAIL);
	cout<<"l1 ("<<l1.length()<<"): "<<l1<<endl;  
	cout<<"l2 ("<<l2.length()<<"): "<<l2<<endl;
	cout<<"l3 ("<<l3.length()<<"): "<<l3<<endl;
	l3 = l2 = l1;
	l1.removeLink (OR_TAIL);
	l2.removeLink (OR_HEAD);
	l3.toHead();  l3.toNext();  l3.removeLink (OR_BEFORE_CUR);
	cout<<"New lists:"<<endl;
	cout<<"l1 ("<<l1.length()<<"): "<<l1<<endl;  
	cout<<"l2 ("<<l2.length()<<"): "<<l2<<endl;
	cout<<"l3 ("<<l3.length()<<"): "<<l3<<endl;
	cout<<"3rd list by elements:"<<endl;
	for (unsigned i = 0; i<l3.length() + 1; i++) 
		try {cout<<l3[i]<<" ";} catch (LAError e) {cerr<<e.errmsg;}
	cout<<endl<<"Everything concatenation: "<<endl;
	l1 = l1 + l2 + l3;  cout<<l1<<endl;
	if (l1.search(3)) cout<<"Found: "<<l1.getCurVal()<<endl;
	
	Stack<int> s1(10);
	Stack<int> s2 = s1;
	s1 = s2;   
	s1.push(11);   s1.push(12);   s1.push(13);
	cout<<"s1: ";  while (!s1.isEmpty()) cout<<s1.pop()<<" ";   cout<<endl;
	return 0;
}