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