DAJ - Li, Hudak - path compression
algorithm 2000-06-19 (
import java.util.Random;
import java.awt.Dimension;
import daj.*;
public class MainApp extends daj.Application {
public static final Dimension SIZE =
new Dimension (450, 450);
public static final int nrOfProgs = 4;
public daj.Node[] nodes;
public AProg[] progs;
// Constructor
public MainApp () {
super ("Li and Hudak's path compression", SIZE.width,
SIZE.height);
nodes = new daj.Node[nrOfProgs];
progs = new AProg[nrOfProgs];
} // MainApp
public void construct() {
int i,j;
Random rand = new Random();
// create all nodes
for (i=0; i<nrOfProgs; i++) {
nodes[i] = node(progs[i]=new AProg(i, (i+1),
i==(nrOfProgs-1)),
String.valueOf(i), 160*(i%2)+80,
160*(i/2)+80);
}
// link all Nodes
for (i=0; i<nrOfProgs; i++) {
for (j=0; j<nrOfProgs; j++) {
link(nodes[i], nodes[j]);
}
}
} // construct
public String getText () {
return "Li and Hudak's path compression";
} // getText
public static void main (String[] args) {
new MainApp().run ();
} // main
}
import daj.*;
import java.util.Random;
public class AProg extends daj.Program {
private int progID, curDir;
private boolean haveToken, sentRequest;
private InChannelSet msgIn;
private OutChannelSet msgOut;
private FIFO map;
private Random rand;
// Constructor
public AProg (int progID, int curDir,
boolean startWithToken) {
this.progID = progID;
if (haveToken = startWithToken) {
this.curDir = progID;
}
else {
this.curDir = curDir;
}
msgIn = new InChannelSet();
msgOut = new OutChannelSet();
rand = new Random();
map = new FIFO();
sentRequest = false;
}
public String getText() {
return "curDir : " + curDir + " have token : " +
haveToken + " sent request : " + sentRequest;
} // getText
// Main loop of the Node
public void main() {
int fromChannel, outChannels, inChannels, i;
Msg msg;
FIFO tokenMap;
inChannels = in().getSize();
for (i=0; i<inChannels; i++) {
msgIn.addChannel(in(i));
}
outChannels = out().getSize();
for (i=0; i<outChannels; i++) {
msgOut.addChannel(out(i));
}
// Program main loop
while(true) {
if (haveToken) {
/*
Enter critical section ...
*/
// give token to the next "requester"
if ((i = map.getNextReceiver()) >= 0) {
haveToken = false;
msgOut.getChannel(i).send(new Token(progID, i,
map));
map = new FIFO();
curDir = i;
}
}
if (!haveToken && !sentRequest) {
// request Token
msgOut.getChannel(curDir).send(new
Request(progID, curDir));
curDir = progID;
sentRequest = true;
}
fromChannel=msgIn.select();
msg = (Msg)msgIn.getChannel(fromChannel).receive();
if (msg.getReceiver() == progID) {
if (msg instanceof Request) {
if (curDir == progID) {
// add the request to the local map
map.addToFIFO(msg.getSender());
}
else {
msgOut.getChannel(curDir).send(new
// fwd the request
Request(i=msg.getSender(), curDir));
curDir = i;
msg = null;
}
}
else { // Token
haveToken = true;
sentRequest = false;
// merge the local and the tokenMap;
tokenMap = ((Token)msg).getMap();
while ((i=map.getNextReceiver()) >= 0) {
tokenMap.addToFIFO(i);
}
map = tokenMap;
tokenMap = null;
msg = null;
}
} // if (msg.getReceiver() == progID)
else {
// should never be reached
System.out.println("Error ! Got Msg from : " +
msg.getSender() + " wanted receiver : " +
msg.getReceiver());
}
} // while (true) main loop
} // main
} // AProg
import daj.*;
public class Msg extends daj.Message
{
protected int sender, receiver;
public Msg (int sender, int receiver) {
this.sender = sender;
this.receiver = receiver;
}
public String getText () {
return "Message from : " + sender + " to : " +
receiver;
}
public int getSender() {
return sender;
}
public int getReceiver() {
return receiver;
}
} // Msg
public class Request extends Msg {
public Request (int sender, int receiver) {
super(sender, receiver);
}
public String getText () {
return "Request from : " + sender + " to : " +
receiver;
}
} // Request
public class Token extends Msg {
protected FIFO map;
public Token (int sender, int receiver, FIFO map) {
super(sender, receiver);
this.map = map;
}
public FIFO getMap() {
return map;
}
public String getText () {
return "Token from : " + sender + " to : " +
receiver;
}
} // Token
public class FIFO {
ListNode first, last;
private class ListNode {
int receiver;
ListNode next;
ListNode(int receiver) {
this.receiver = receiver;
next = null;
}
} // ListNode
public FIFO() {
first = null;
last = null;
}
public void addToFIFO(int receiver) {
ListNode newNode = new ListNode(receiver);
if (first == null) {
last = newNode;
first = last;
}
else {
last.next = newNode;
last = newNode;
}
} // addToFIFO
// returns id of the next receiver or -1 if there is no
public int getNextReceiver() {
int result;
if (first != null) {
result = first.receiver;
first = first.next;
}
else {
result = -1;
}
return result;
} // getNextReceiver
} // FIFO