/*
 * COMP225 Assignment #1
 *
 * Student name: Sina Sadeghi
 * Student num#: 40523284
 * Tut time/day: Wednesday 4PM
 * Prac time/da: Wednesday 12PM
 *
 * Assignment written in:
 * 	- VIM - Vi IMproved 7.0 (2006 May 7, compiled Jul 11 2006 04:00:23)
 * 	- Linux measel 2.6.17-2-486 #1 Fri Aug 11 20:00:44 UTC 2006 i686 GNU/Linux
 * 	- gcc version 4.1.2 20060729 (prerelease) (Debian 4.1.1-10)
 * 	- Debian GNU/Linux unstable
 *
 */

#include "ring.h"

/**********************************************************
       Chordalring Class
A Chordal ring has no beginning or end but only a current position
which is initially at node labelled 1


The chordal ring C(n,k), where n >= 5 and 2  <= k <= n/2, 
consists of n items, each assigned a
unique number between 1 and n. Each item, labelled i, has a connection
with two other items, namely, the item labelled i+1 (modulo n) and the
item labelled i+k (modulo n). We will refer to connections like i to i+1
(modulo n) as short-links and connections like i to i+k (modulo n) as long-links.

Note that long-links can be calculated in c++ as
    from i to (i+k-1)%n +1
************************************************************/


//Pre  : none
//Post : an empty ring is created;
ring::ring()
{
	current = NULL;
	length = 0;
}

//Pre  : non empty array passed as parameter
//Post : identical array created
ring::ring(ring &otherRing)
{
	current = new node;
	node *start = current;
	
	for(int i = 1; i <= otherRing.size(); i++)
	{
		current->num = otherRing.getCurrent();
		current->shortlink = new node;

		cout << current->num << " " << otherRing.getCurrent()<< endl;

		current = current->shortlink;
		otherRing.move(1);
	}

	current->num = otherRing.getCurrent();
	

	current->shortlink = start;
	current = start;
	length = otherRing.size();

	node *nextlong = start;

	//Outer loop:
	//Move current through the newly created shortlinks
	//Inner loop:
	//Link each node to the node k spaces ahead.
	cout << endl;
	for(int i=1; i<=length; i++)
	{
		nextlong = current;
		while(nextlong->num != otherRing.current->longlink->num)
		{
			 nextlong = nextlong->shortlink;
		}

		current->longlink = nextlong;

		current = current->shortlink;
		otherRing.move(1);
		cout <<getCurrent() << " " << otherRing.getCurrent() << endl;
	}
	
	//Reset current to start bookmark again.
	current = start;
	
}


//Pre  : none
//Post : creates a Chordal ring of n and k
void ring::create(int n, int k)
{
	//createShort(n,k);
	createLong(n,k);
}


//called by create to create the short linked ring
void ring::createShort(int n)
{
	//Create first node as current
	//Set a start "bookmark" pointer so we can
	//reset counter to beginning once done.
	
	current = new node;
	node *start = current;

	
	//Create nodes numbered 1..n-1
	//Set shortlinks to next new node 
	
	for(int i=1; i<n; i++)
	{
		current->num = i;
		current->shortlink = new node;
		current = current->shortlink;
	}

	//Setup final last node
	//Including set shortlink to beginning number
	current->num = n;
	current->shortlink = start;

	//Reset current to node 1 from "bookmark" from "bookmark".
	current = start;

	//Then set length attribute to n. size() returns this.
	length = n;
}


//called by create to create the long linked ring
void ring::createLong(int n, int k)
{

	//SHORTLINKS:
	//Create first node as current
	//Set a start "bookmark" pointer so we can
	//reset counter to beginning once done.
	
	current = new node;
	node *start = current;

	
	//Create nodes numbered 1..n-1
	//Set shortlinks to next new node 
	
	for(int i=1; i<n; i++)
	{
		current->num = i;
		current->shortlink = new node;
		current = current->shortlink;
	}

	//Setup final last node
	//Including set shortlink to beginning number
	current->num = n;
	current->shortlink = start;

	//Reset current to node 1 from "bookmark" from "bookmark".
	current = start;

	//Then set length attribute to n. size() returns this.
	length = n;

	//LONGLINKS:
	//We need a secondary counter to skip k spaces ahead of current
	//This will be the next longlink 

	node *nextlong = current;

	//Outer loop:
	//Move current through the newly created shortlinks
	//Inner loop:
	//Link each node to the node k spaces ahead.
	for(int i=1; i<=n; i++)
	{
		nextlong = current;
		for(int j = 0; j < k; j++)
		{
			 nextlong = nextlong->shortlink;
		}
		//The nextlong counter now points to kth shortlink from node i
		//Point i->longlink at it.
		current->longlink = nextlong;

		//Move shortling one along
		current = current->shortlink;
	}
	
	//Reset current to start bookmark again.
	current = start;
}


//Pre  : ring is not empty
//Post : have moved the current position pointer y places around the ring
void ring::move(int y)
{

	//Moves current across y shortlinks.
	for(int i=0; i<y; i++)
	{
		//Move current along one shortlink.
		current = current->shortlink;
	}
}


//Pre  : the ring is not empty
//Post : returns the value at the current position
int ring::getCurrent()const 
{
	//Return num attribute of object.
	return current->num;
}


//Pre  : none
//Post : returns the number of nodes in the ring
int ring::size()const 
{
	//Return length attribute of object.
	return length;
}


//Pre  : ring is not empty
//Post : Starting with current node and using short links, 
//	the current->num of each node is displayed.
void ring::dumpShort()const 
{
	if(!empty())
	{
		//Don't want to use current for this loop
		//so point "counter" at current.
		
		node *counter = current;

		//Output title
		cout << "Node" << endl;

		//Now iterate through ring on shortlinks
		//and display num attribute of node
		//then move counter to next shortlink node
		for(int i=0; i < size(); i++)
		{
			cout << counter->num << endl;
			counter = counter->shortlink;
		} 

		//End output
		cout << endl;
	}
}


//Pre  : ring is not empty
//Post : Starting with current node and using long links, the current->num of each 
//       node is displayed.
void ring::dumpLong()const
{
	if(!empty())
	{
		//Point counter at current
		node *counter = current;

		//Output title
		cout << "Node" << endl;

		//Now iterate through ring on longlinks
		//and display num attribute of each node
		//then move counter to next longlink node
		node *start = current;

		for(int i=0; i < size(); i++)
		{
			cout << counter->num << endl;
			counter = counter->longlink;
			if(counter->num == start->num)
				break;
		} 

		//End output
		cout << endl;
	}


}


//Pre  : ring is not empty
//Post : starting from current node and using short links
//	 each node in chordal ring is displayed in full
//	 i.e. node, shortlink->num, longlink->num
void ring::display()const{
	if(!empty())
	{
		node *counter = current;
		cout << "\t Node\tShort\tLong" << endl;
		for(int i=0; i < size(); i++)
		{
			cout << "\t" << counter->num << "\t";
			cout << counter->shortlink->num << "\t";
			cout << counter->longlink->num << endl;
			counter = counter->shortlink;
		} 
		cout << endl;
	}

}


//Pre  : none
//Post : returns true if ring is empty otherwise false
bool ring::empty() const 
{
	if(current == NULL || length == 0)
		return true;
	else
		return false;
}


//Pre  : ring is not empty
//Post : removes the node with value from x from the ring
//	nodes previously linked (short and long) to x 
//	will now link to short and long of x i
//	respectively. if current position is at x then current 
//	moved to x's short link.
void ring::remove(int x)
{
	if(!empty())
	{
		if(hasMember(x))
		{
			node *counter = current;

			//Move counter to the beginning of the ring
			while(counter->num > counter->shortlink->num)
			{
				counter=counter->shortlink;
			}

			//Create a bookmark for the node to be deleted
			//to be placed into.
			node *deletenode = NULL;

			
			//Iterate through ring
			for(int i = 1 ; (i <= size()) ;i++)
			{
				//If number one ahead == x then we want to 
				//rearrange the links according to the rules
				//to prepare for deletion.
				if(counter->shortlink->num == x)	
				{
					node *newcounter = counter;

					//Secondary counter jumps ahead, discovers the
					//node with longlink pointing to the node x
					for(int j = 1; j <= size() ; j++)
					{
						if(newcounter->longlink->num == x)
						{
							//Once found, change the nodes
							//longlink to reflect the deletion. 
							newcounter->longlink = counter->shortlink->longlink;
							
						}
						newcounter = newcounter->shortlink;
					}
					
					//Node ahead (counter->shortlink) is x (to be deleted)
					//so point our deletenode bookmark at it (we need it soon).
					deletenode = counter->shortlink;

					//Then move to the next item of the loop.
					counter->shortlink = counter->shortlink->shortlink;
				}

				//If deletenode != NULL then obviously we have something
				//to delete! Yay!
				if(deletenode != NULL)
				{
					//Check to see if current is the node to be deleted
					//If so, move current one ahead (don't want current 
					//pointing at a deleted node!)
					if(current->num == x)
						current = current->shortlink;
		
					//Finally kill the node.
					delete deletenode;
					
					//Don't forget to subtract from length!
					length--;

					//We deleted a node, there should only be one of each 
					//node number in the ring, so exit!
					break;
				}

				//If node != x, just move one across.
				counter = counter->shortlink;
			}	
		}
		else
		{
			cout << x << " does not exist" << endl;
		}
	}
}

//Pre  : none
//Post : returns true if a node with value x is a member of ring
bool ring::hasMember(int x) const 
{
	if(!empty())
	{
		node *counter = current;

		for(int i=0; i < size(); i++)
		{
			if(counter->num == x)
				return true;
			counter = counter->shortlink;
		} 
		return false;
	}
	
}