/*
* 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 = NULL;
current = new node;
node *start = current;
if(!otherRing.empty())
{
for(int i = 1; i <= otherRing.size(); i++)
{
int f = otherRing.getCurrent();
current->num = f;
current->shortlink = new node;
current = current->shortlink;
otherRing.move(1);
cout << "Current num: " << current->num << " " << f << endl;//current->shortlink->num << endl;
cout << " other num: " << otherRing.getCurrent() << endl;
}
current->num = otherRing.getCurrent();
cout << "Final:"<<endl;
cout << "Current num: " << current->num << " " << endl;//current->shortlink->num << endl;
cout << " other num: " << otherRing.getCurrent() << endl;
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;
}
}