/* Prog.java
This program poses the programs run on each processor in the network.

26-Jan-1999: created by Thomas Prokosch (tp)
27-Jan-1999: implementation of message processing (tp)
28-Jan-1999: changed implementation of waitingQ from Vector to Hashtable (tp)
30-Jan-1999: implementation of voting_entry && enter_cr (tp)
31-Jan-1999: changed code for simulating fully connected networks
             through broadcasting (tp)
12-Feb-1999: Igor Rents fixed a bug that I/O automaton has:
             after leaving the Critical Region yes_votes had to be set to 0.
*/

import daj.*;
import java.util.*;
import java.lang.Math;
import Msg;

public class Prog extends Program {
    int my_TS=0, yes_votes=0, candidate_TS=0, candidate=-1;
    boolean have_voted=false, have_inquired=false, cr_entry=false;
    public boolean in_CR=false;  /* true when proc is in the critical region */
    Hashtable waitingQ=new Hashtable();
    private int i=-1;                                    /* processor number */
    static int SQPROCS=0, NOPROCS=0;              /* overall number of procs */
    static int timer=0;          /* class variable counting the elapsed time */

    /* constructor, sets the processor number */
    public Prog(int proc, int procs) {
        i=proc;
        SQPROCS=procs;
        NOPROCS=SQPROCS*SQPROCS;
    }

    /* returns the status of this processor */
    public String getText() {
        String str=new String("");
        if (cr_entry) {
            str=new String("voting stamp: "+my_TS);
            str+="\nyes votes: "+yes_votes+"\n";
        } else{
	  if (have_inquired) str+="already inquired\n";}
	if (have_voted) str+="\nvoted for "+candidate;
	if (have_voted) str+="\ncandidate TS: "+candidate_TS+"\n";
	return(str);
    }

    /* finds the processor with the lowest request time stamp */
    int lowRTS() {
        int s=-1, rts=-1, s_, rts_;
        boolean init=false;
        /* iterates over all processors with requests */
        for (Enumeration enum=waitingQ.keys(); enum.hasMoreElements(); ) {
            /* get the request time stamp */
            s_=((Integer)enum.nextElement()).intValue();
            rts_=((Integer)waitingQ.get(new Integer(s_))).intValue();
            /* compare with the actual minimal time stamp */
            if ((!init)||(rts_<rts)) { rts=rts_; s=s_; init=true; }
        }
        // System.out.println("removing proc "+s+" with time "+rts);
        return(s);
    }

    /* inquire makes the proc relinquish */
    void inquire(int j, int inquire_TS) {
         System.out.println("proc "+i+ " inquire("+j +","+inquire_TS+")\n");
       if (my_TS==inquire_TS) {
            route(new Msg(i, j, Msg.RELINQUISH, 0));
            yes_votes--; //(tp)
        }
    }

    /* request a vote */
    void request(int j, int request_TS) {
         System.out.println("proc "+i+"request("+j+","+request_TS+")\n");
       if (have_voted) {
            waitingQ.put(new Integer(j), new Integer(request_TS));
            route(new Msg(i, j, Msg.ACK, 0));
            if ((request_TS<candidate_TS)&&(!have_inquired)) {
                route(new Msg(i, candidate, Msg.INQUIRE, candidate_TS)); //(tp)
                have_inquired=true;
            }
        } else {
            route(new Msg(i, j, Msg.ACK, 1));
            candidate_TS=request_TS;
            candidate=j;
            have_voted=true;
        }
    }

    /* release */
    void release() {
        System.out.println("proc "+i+" release()\n");
        have_inquired=false;
        if (waitingQ.isEmpty())
            have_voted=false;
        else {
            int s=lowRTS();
            int rts=((Integer)waitingQ.get(new Integer(s))).intValue();
            waitingQ.remove(new Integer(s));
            route(new Msg(i, s, Msg.ACK, 1));
            candidate_TS=rts;
            candidate=s;
        }
    }

    /* relinquish the vote */
    void relinquish() {
        System.out.println("proc "+i+" relinquish()\n");
        waitingQ.put(new Integer(candidate), new Integer(candidate_TS));
        int s=lowRTS();
        int rts=((Integer)waitingQ.get(new Integer(s))).intValue();
        waitingQ.remove(new Integer(s));
        route(new Msg(i, s, Msg.ACK, 1));
        candidate_TS=rts;
        candidate=s;
        have_inquired=false;
    }

    /* route finds the best way for a msg through the network                */
    /* unfortunately (because of simplicity reasons) routing is static and   */
    /* must be changed when the network uses another topology                */
    void route(Msg msg) {
        int way=-1;
        int d=msg.dst;
        if (i/SQPROCS<d/SQPROCS) { /* move packet downwards */
            way=2;
            if (i<SQPROCS) way--;
            if (i%SQPROCS==0) way--;
        }
        if (i%SQPROCS<d%SQPROCS) { /* move packet to the right */
            way=3;
            if (i<SQPROCS) way--;
            if (i%SQPROCS==0) way--;
            if (i>=NOPROCS-SQPROCS) way--;
        }
        if (i%SQPROCS>d%SQPROCS) { /* move packet to the left */
            if (i<SQPROCS) way=0; else way=1;
        }
        if (i/SQPROCS>d/SQPROCS) { /* move packet upwards */
            way=0;
        }
        /* send the msg in the appropriate direction */
        if (way>=0) out(way).send(msg);
    }

    /* prepares for a vote */
    void voting_entry() {
        System.out.println("proc "+i+" voting_entry()\n");
        cr_entry=true;
        my_TS=timer++;
        // System.out.println(my_TS+": proc "+i+" wants to enter");
        Msg msg=new Msg(i, 0, Msg.REQUEST, my_TS);
        for (int j=0; j<SQPROCS; j++) {
            route(new Msg(msg).setdest((i/SQPROCS)*SQPROCS+j));
            route(new Msg(msg).setdest((i%SQPROCS)+SQPROCS*j));
        }
    }

    /* does the critical action */
    void enter_cr() {
        GlobalAssertion assertion=new only_one();
        System.out.println((timer++)+": proc "+i+" entered");
        in_CR=true; /* point of no-return */
        assert(assertion);
        sleep((int)(4*Math.random()+1));
        in_CR=false;
        cr_entry=false;
        System.out.println((timer++)+": proc "+i+" left");
	yes_votes=0;
        Msg msg=new Msg(i, 0, Msg.RELEASE, 0);
        for (int j=0; j<SQPROCS; j++) {
            route(new Msg(msg).setdest((i/SQPROCS)*SQPROCS+j));
            route(new Msg(msg).setdest((i%SQPROCS)+SQPROCS*j));
        }
    }

    /* main execution loop, process the incoming messages */
    public void main() {
        Msg msg;
        int j; /* the sender of the message */
        int c; /* the channel of an incoming msg */
        while (true) {
            if ((!cr_entry)&&((int)(20*Math.random())==0)) voting_entry();
            if ((j=in().select(1))>=0) {
                msg=(Msg)in(j).receive();
                if (msg.dst==i) {
                    switch (msg.type) {
                    case Msg.INQUIRE: inquire(msg.src, msg.data); break;
                    case Msg.REQUEST: request(msg.src, msg.data); break;
                    case Msg.RELEASE: release();                  break;
                    case Msg.RELINQUISH: relinquish();            break;
                    case Msg.ACK: if (msg.data==1) yes_votes++;   break;
                    }
                    /* status of yes_votes can only change when a msg has */
                    /* been received                                      */
                    if ((cr_entry)&&(yes_votes==2*SQPROCS-2)) enter_cr();
                } else
                    route(msg);
            }
        }
    }
}

class only_one extends GlobalAssertion {
    public String getText() {
        return("More than 1 proc entered the critical region!");
    }

    public boolean assert(Program prog[]) {
        int count=0;
        for (int j=0; j<prog.length; j++) {
            if (((Prog)prog[j]).in_CR) count++;
        }
        return(count<=1);
    }
}