#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

struct empty_quenue_operation {
	string operation;
	empty_quenue_operation (string mes) : operation (mes) {}
	operator string  (){
		return operation;
	}
};


template <class T>
class RoundedQuenue {
 struct TNode {
	T inf;
	TNode * next;
	operator T (){
		return inf;
	}
 };

 public:
 
 unsigned unique_time;//  ? ??????? ?? ???????
 struct iterator {
	 TNode * curNode;
	 RoundedQuenue * parent ; 

	 unsigned local_unique_time;//  ? ??????? ?? ???????
	 void test_correct_time (){
		 if (local_unique_time != parent->unique_time)
			 throw empty_quenue_operation ( "times are  different: invalid iterator" );
	 }

	 iterator & operator ++ (){
		 test_correct_time ();
		 if (curNode)
			curNode = curNode->next;
		 else
			throw empty_quenue_operation ( "iterator & operator ++ ()" );
		 return *this;
	 }
	 iterator & operator  -- (){
 
		 test_correct_time ();
		 if (curNode)
			 curNode = parent->goEnd (curNode);
		 else
			throw empty_quenue_operation ( "iterator & operator ++ ()" );
		 return *this;
	 }


	 iterator & operator ++ (int){
		  return ++(*this);
	 }

 	 iterator & operator  -- (int){
 
		  return  --(*this);
 
	 }

	 T & operator * (){
		 test_correct_time ();
		 if (curNode)
			return curNode->inf;
		 else
			throw empty_quenue_operation ( "T & operator * ()" );
	 }



	 bool operator == (const iterator & an){
		 test_correct_time ();
		 return curNode == an.curNode;
	 }

	 bool operator != (const iterator & an){
		 return curNode != an.curNode;
	 }
	
	 iterator (TNode * _curNode , RoundedQuenue * _parent,  unsigned time_image):
		curNode(_curNode),
		local_unique_time(time_image),
		parent (_parent)
	{}

	 iterator ():
		curNode(NULL),
		local_unique_time(- 1 ),
		parent (NULL)
	{}
 };

 

 TNode * entry_point;
 TNode * goEnd (TNode * end) {
	 if (end == NULL) return NULL;

	 TNode * cur = end;
	 while (cur->next != end)
		 cur = cur->next;
	 return cur;
 }
 public:
	 RoundedQuenue () : entry_point (NULL), unique_time ( 0 ) {};
	 void push_back (const T & info){

		 unique_time++;

		 TNode * end  =  goEnd (entry_point);
		 TNode * now = new TNode ();
  	     now->inf = info;
		 
		 if (end != NULL){
			 end->next = now;
			 now->next = entry_point;
			 return;
		 }
		 entry_point = now;
		 now->next = entry_point;
		 
	 }

	 bool pop_back (void){
		return pop_selected (entry_point);
	 }

	 bool pop_selected (TNode * who){
		TNode * end  =  goEnd (who);
		if (end == NULL) return false;
		TNode * prev_end = goEnd (end);
		if (prev_end == end){
			// ???? ??????? ? ???????
			delete entry_point;
			entry_point  = NULL;
			return true;
		}
		prev_end->next = end->next;
		delete end;
		return true;
	 }

	 TNode * get_at_position (int offset_from_entry_point, bool cyclic = true){
		 if (cyclic){
			 TNode * pointer  = entry_point;
			 for (;offset_from_entry_point --;)
 
				 pointer = goEnd(pointer);
			 return pointer;
		 }
		 TNode * pointer  = entry_point;
		 for (;offset_from_entry_point -- ;){
 
			pointer = goEnd(pointer);
			if (pointer == entry_point) return NULL;
		 }
		 return pointer;
	 }

	 void printClock (void){
		 cout <<  "---- Rounded Quenue --- \n";
 
		 if (entry_point == NULL) {
			 cout << "() " << endl;
			 cout << "  ---- End Of Rounded Quenue --- \n";
 
			 return;
		 }
		 TNode * end = entry_point; 
		 do{
			 end  =  goEnd (end);	
			 cout << end->inf <<  ", " ;
		 }
		 while (end != entry_point);
		 cout <<  "\n---- End Of Rounded Quenue --- \n";
 

	 }
	 ~RoundedQuenue () {
		while (pop_back());
	 };

	 iterator iterate_entry_point (void){
		 return iterator (entry_point , this, unique_time);
	 }

	 iterator iterate_back_point (void){
		 return iterator (goEnd(entry_point) , this, unique_time);
	 }

	 T & operator [] (int cyclic_index) {
		 return get_at_position(cyclic_index)->inf;
	 }
	 operator int (){
		 if (entry_point == NULL) {
			  return  0  ;
		 }
		 int cnt =  0 ;
		 TNode * end = entry_point; 
		 do{
			 end  =  goEnd (end);	
			 cnt++;
		 }
		 while (end != entry_point);
		 return cnt;
	 }
};

void main (void){
	RoundedQuenue <char> rc;
	rc.printClock ();
	rc.push_back ('a');
	rc.printClock ();
	rc.push_back ('b');
	rc.printClock ();
	rc.push_back ('c');
	rc.printClock ();
	rc.pop_back ();
	rc.printClock ();
	rc.push_back ('d');
	rc.push_back ('b');
	rc.push_back ('z');
	rc.push_back ('b');
	rc.push_back ('a');
	rc.printClock ();

	RoundedQuenue <char>::iterator I = rc.iterate_entry_point ();
	RoundedQuenue <char>::iterator IStartedFrom = rc.iterate_entry_point ();
	
	do {
		cout << *I << endl;
		I++;
	}
	while (I !=IStartedFrom);
	I --;
 
	rc.push_back ('d');
	try{
		I --;
 
		cout << *I << endl;
	}
	catch (empty_quenue_operation e){
		cout << "Error:  "<< e.operator string () << endl;
	}

	RoundedQuenue <char>::iterator Ipoz = find (rc.iterate_entry_point () , rc.iterate_back_point () , 'b');
	int diff = count (rc.iterate_entry_point () , rc.iterate_back_point () , 'b');
	if (Ipoz == rc.iterate_back_point())
		cout << " Not Found ";
	else
		cout << " Found:  " << diff;

	cout << " \nGet at  5  PoZition:  "<< rc.get_at_position (5 )->operator char () << endl;
	cout << "\nGet at  6  PoZition:  "<< rc.get_at_position (6 )->operator char () << endl;
	cout << "Size Of RoundedQuenue = " << rc << endl;
	for (int i =  0 ; i < int(rc) ; i++)
		cout << char(rc [i]) << endl;

	rc.printClock ();

//	sort (rc.iterate_entry_point () , rc.iterate_back_point () );
// !!!! HOW !!!!!

}