#include<iostream>
#include<iterator>
#include<math.h>

using namespace std;

template<typename key, typename info>
class Ring{
	private:
		struct Node{
    		key nkey;
    		info ninfo;
    		Node* next;
    		Node* prev;
		};

		Node* head;
    	Node headNode;
    	void copyAll(const Ring<key,info>& x);
    	void clearAll();
    	unsigned int size=0;

    public:
    	class iterator{
			Node* itr;
			public:
				iterator(Node* temp):itr(temp){}
				iterator(const iterator& myitr):itr(myitr.itr){}

				const iterator& operator++(){
					itr = itr->next;
					return *this;
				}

				const iterator& operator--(){
					itr=itr->prev;
					return *this;
				}

				bool operator==(const iterator& right){
					return itr == right.itr;
				}

				bool operator!=(const iterator& right){
					return itr!=right.itr;
				}

				const Node& operator*()const{
					return *itr;
				}

				const iterator& operator+=(int x){
					for(int i=0; i<abs(x) ;i++){
						if(x>0){
							itr = itr->next;
						}
						if(x<0){
							itr = itr->prev;
						}
					}
					return *this;
				}

				const iterator& operator-=(int x){
//					for(int i=0; i<abs(x) ;i++){
//						if(x<0){
//							itr = itr->next;
//						}
//						if(x>0){
//							itr = itr->prev;
//						}
//					}
					return *this += -x;
				}
		};

	public:
		Ring();
        Ring(const Ring<key,info>& right);
		Ring(Ring<key,info>&& right);
		~Ring();
        Ring& operator=(const Ring<key,info>& right);
    	Ring& operator=(Ring<key,info>&& right);
		void push_front(const key& nkey, const info& ninfo); //AFTER SENTINEL NODE
		void push_back(const key& nkey, const info& ninfo); //BEFORE SENTINEL NODE
        void remove(const key& nkey); //deletes the first occurance of the key in the ring
   		iterator begin()const{return head->next;}
		iterator end()const{return head;}
    	void display();
    	int getsize()const{return this->size;}
};


template<typename key, typename info>
Ring<key,info>::Ring(){
    headNode.nkey=0;//Key();
    headNode.ninfo=0;//Info();
	head=&headNode;
	headNode.next=&headNode;
    headNode.prev=&headNode;
}

template<typename key, typename info>
Ring<key,info>::Ring(const Ring<key,info>& right){
	head=&headNode;
    headNode.next=&headNode;
    headNode.prev=&headNode;
	copyAll(right);
	size=right.size;
}

template<typename key, typename info>
Ring<key,info>::Ring(Ring<key,info>&& right){
	head=right.head;
	size=right.size;
	right.size=0;
	right.head=nullptr;
}

template<typename key, typename info>
Ring<key,info>::~Ring(){
	clearAll();
}

template<typename key, typename info>
void Ring<key,info>::push_back(const key& nkey,const info& ninfo){
    if(nkey==0 || ninfo==0){
    	cerr << "Key or Info can not be 0" << endl;				//zero values belong to sentinel only
    	return;
	}
	Node* nptr = new Node;
	nptr->nkey=nkey;
	nptr->ninfo=ninfo;
    if(head->next==head){
        head->next=nptr;
        nptr->next=head;
        nptr->prev=head;
        head->prev=nptr;
        size++;
        return;
    }
    else{
       	head->prev->next=nptr;
        nptr->prev=head->prev;
		nptr->next=head;
        head->prev=nptr;
        size++;
        return;
    }
}

template<typename key, typename info>
void Ring<key,info>::push_front(const key& nkey,const info& ninfo){
    if(nkey==0 || ninfo==0){
    	cerr << "Key or Info can not be 0" << endl;				//zero values belong to sentinel only
    	return;
	}
	Node* nptr = new Node;
	nptr->nkey=nkey;
	nptr->ninfo=ninfo;
    if(head->next==head){ // head->next==head
        head->next=nptr;
        nptr->next=head;
        nptr->prev=head;
        head->prev=nptr;
        size++;
        return;
    }
    else{
        head->next->prev=nptr;
        nptr->prev=head;
        nptr->next=head->next;
        head->next=nptr;
        size++;
        return;
    }
}

template<typename key, typename info>
void Ring<key,info>::remove(const key& nkey){
	if(head->next->nkey==nkey && head->next==head){
			delete head->next;
			head->next=head;
			head->prev=head;
			size--;
			return;
	}
	else{
		Node* ptr=head->next;
		while(ptr!=head){
			if(ptr->nkey==nkey){
				ptr->prev->next=ptr->next;
				ptr->next->prev=ptr->prev;
				delete ptr;
				size--;
				return;
			}
		ptr=ptr->next;
		}
	}
	cerr << "Key not found" << endl;
}

template<typename key, typename info>
void Ring<key,info>::clearAll(){
	Node* ptr=head->next;
	while(ptr!=head){
		ptr=ptr->next;
		delete (head->next);
		head->next=ptr;
	}
	head->next=head; //just to make sure head is not lost
	head->prev=head;
	size=0;			 //really a need for these 3 lines??
}

template<typename key, typename info>
void Ring<key,info>::copyAll(const Ring<key,info>& x){

	Node* xtr = x.head->next;
	Node* etr = this->head->next;
	if(etr->next!=etr){
		this->clearAll();
	}

	while(xtr!=x.head){
		Node* ntr = new Node;
		ntr->nkey=xtr->nkey;
		ntr->ninfo=xtr->ninfo;
		ntr->next=nullptr;							//can also use head in place of this->head
		if(head->next==head){
			head->next=ntr;
			ntr->prev=head;
		}											// original in xtr
		else{
			etr->next=ntr;
			ntr->prev=etr;
		}															//copy in ntr
		etr=ntr;								//etr points to this copy so ntr points to new element in the next loop
		xtr=xtr->next;
	}
	head->prev=etr;
	etr->next=head;
}

template<typename key, typename info>
Ring<key,info>& Ring<key,info>::operator=(const Ring<key,info>& right){
	if(right.getsize()==0){return *this;}
	if(this==&right){return *this;}
	this->copyAll(right);
	size=right.size;
	return *this;
}

template<typename key, typename info>
Ring<key,info>& Ring<key,info>::operator=(Ring<key,info>&& right){
	this->clearAll();
	head=right.head;
	size=right.size;
	right.head=nullptr;
	return *this;
}

template<typename key, typename info>
void Ring<key,info>::display(){
	for(auto it=this->begin();it!=this->end();++it){
    		cout << (*it).nkey << "-" << (*it).ninfo<< " ";
	}
	cout << endl;
}

template<typename key, typename info>
Ring<key,info> produce(const Ring<key,info>& r1, const Ring<key,info>& r2, int s1, int len1, int s2, int len2, int repeat, bool dir){
	Ring<key,info> nRing;
	if(len1==0 || len2==0 || repeat==0 || r1.getsize()==0 || r2.getsize()==0){
		cerr << "Invalid parameters" << endl;
		return nRing;
	}
	auto itr1=r1.begin(); auto itr2=r2.begin();
	itr1+=s1; itr2+=s2;
	if(s1<0){itr1-=((abs(s1)/r1.getsize())+1);}  // to deal with the difference of 1 after each cycle due to sentinel node
	if(s2<0){itr2-=((abs(s2)/r2.getsize())+1);}

	for(int x=0;x<repeat;x++){
		for(int i=0;i<abs(len1);i++){
			if(itr1==r1.end()){--i;} 			//bypassing the sentinel node
			else{
				if(!dir){nRing.push_front((*itr1).nkey,(*itr1).ninfo);}
				else{nRing.push_back((*itr1).nkey,(*itr1).ninfo);}
			}
			len1>0?++itr1:--itr1;
		}
		for(int j=0;j<abs(len2);j++){
			if(itr2==r2.end()){--j;}
			else{
				if(!dir){nRing.push_front((*itr2).nkey,(*itr2).ninfo);}
				else{nRing.push_back((*itr2).nkey,(*itr2).ninfo);}
			}
			len2>0?++itr2:--itr2;
		}
	}
	return nRing;
}

int main(){
/*Ring<int,int> a;
a.push_front(2,4);
a.push_front(4,6);
a.push_front(3,7);
a.display();
Ring<int,int> b;
b.push_front(9,7);
b.push_front(5,2);
b.push_front(6,8);
b.push_front(1,1);
b.display();*/

Ring<int,int> a;
a.push_back(1,1);
a.push_back(2,1);
a.push_back(3,1);
a.push_back(4,1);
//a.push_back(3,2);
a.display();
Ring<int,int> b;
b.push_back(10,2);
b.push_back(20,2);
b.push_back(30,2);
b.push_back(40,2);
b.push_back(50,2);
b.display();
Ring<int,int> r;
Ring<int,int> d=produce(a,b,-2,3,3,-2,2,1);
d.display();
//cout << d.getsize()<<endl;
//r=b;
//r.display();
//Ring<int,int> c;
//c.reverse(b);
//c.display();
return 0;
}