/**
 * Chandy/Misra solution implementation.
 * 
 * 1. For every pair of philosophers give chopstick to the one with the lower ID.
 * 
 * 2. Each chopstick can either be dirty or clean. Initially, all chopsticks are
 * dirty.
 * 
 * 3. When a philosopher wants to eat, he must obtain the chopsticks he does not
 * have from his contending neighbors. For all such chopsticks he does not have, he 
 * sends a request message and waits. See Philosopher.obtainChopsticksIfNecessary() 
 * and Philosopher.waitForChopstick()
 * 
 * 4. Only dirty chopstick can be given up. When the chopstick sent over, it
 * gets cleaned. See Philosopher.giveUpChopstickIfNecessary()
 * 
 * 5. After a philosopher is done eating, all his chopsticks become dirty. See
 * Philosopher.eat() 
 * 
 * 6. Philosopher can eat only when both chopsticks present. Chopsticks can not
 * be sent away when philosopher is eating. Chopsticks change state ONLY inside the 
 * owner's thread so philosopher does not need to lock them when he's eating. 
 * 
 * 7. What he needs however is to check his neighbors periodically in order to 
 * send them chopsticks when they're ready to eat. See processChopsticks() and
 * giveUpChopstickIfNecessary()
 * 
 * The clean/dirty labels give preference to the most "starved" processes. It
 * solves the starvation problem.
 * 
 * Initializing the system so that philosophers with lower IDs have dirty
 * chopsticks AND continuous tracking neighbor's state gives a guarantee that 
 * deadlock cannot occur and system has overall progress.
 * 
 */

class Program {

    public static void main(String[] args) {

        final int philosophersCount = 6;
        final int eatCount = 5;

        Philosopher[] philosophers = new Philosopher[philosophersCount];
        Chopstick[] chopsticks = new Chopstick[philosophersCount];

        for (int i = 0; i < philosophersCount; i++)
            chopsticks[i] = new Chopstick(i + 1);

        for (int i = 0; i < philosophersCount; i++)
            philosophers[i] = new Philosopher(i + 1, chopsticks[i],
                    chopsticks[(i + 1) % philosophersCount], eatCount);

        //  set neighbors and assign owners: give the chopsticks to the philosopher with the lower ID
        philosophers[0].leftNeighbor = philosophers[philosophersCount - 1];
        philosophers[0].rightNeighbor = philosophers[1];
        chopsticks[0].owner = philosophers[0];
        for (int i = 1; i < philosophersCount; i++) {
            philosophers[i].leftNeighbor = philosophers[(i - 1) % philosophersCount];
            philosophers[i].rightNeighbor = philosophers[(i + 1) % philosophersCount];
            chopsticks[i].owner = philosophers[i - 1];
        }

        System.out.println("Dinner is starting!\n");
        for (int i = 0; i < philosophersCount; i++)
            philosophers[i].start();

        // wait all threads to complete
        for (int i = 0; i < philosophersCount; i++)
            philosophers[i].join();
        System.out.println("Dinner is over!");
    }
}

class Philosopher implements Runnable {

    final int id;
    final Chopstick leftChopstick, rightChopstick;
    final int eatCount;
    Philosopher leftNeighbor, rightNeighbor;

    final Thread thread;
    
    int eatNum = 0;     // total # times Philosopher has eaten
    int eatInRaw = 0;   // how many times Philosopher has eaten in a row
    
    boolean goingToEatRequest = false;  // signal "I want to eat"

    public Philosopher(int id, Chopstick leftChopstick,
            Chopstick rightChopstick, int eatCount) {
        super();
        this.id = id;
        this.leftChopstick = leftChopstick;
        this.rightChopstick = rightChopstick;
        this.eatCount = eatCount;
        thread = new Thread(this);
    }

    
    /**
     * Main loop
     */
    public void run() {
        while (eatNum < eatCount) {
            think();
            processChopsticks(true);
            obtainChopsticksIfNecessary();
            eat();
            processChopsticks(eatNum != eatCount);  // give up chopsticks unconditionally after the last iteration 
        }
    }

    
    void obtainChopsticksIfNecessary() {
        // indicate that we need chopsticks so the neighbors send them
        goingToEatRequest = true;
        waitForChopstick(leftChopstick);
        waitForChopstick(rightChopstick);
        goingToEatRequest = false;
    }

    
    /**
     * Monitor "Guarded Wait" implementation
     */
    void waitForChopstick(Chopstick chopstick) {
        if (chopstick.owner != this) {
            synchronized (chopstick) {

//                System.out.format("Philosopher %d WAITING for chopstick %d.\n",
//                        id, chopstick.id);

                try {
                    while (chopstick.owner != this) {
                        // while waiting, Philosopher must be able to release 
                        // dirty chopstick he owns to avoid deadlock
                        processChopsticks(true);
                        chopstick.wait();
                    }
                } catch (InterruptedException e) {
                    System.out.println("InterruptedException caught");
                }
            }
        }
        System.out.format("Philosopher %d picks up %s chopstick.\n", id, chopstick == leftChopstick ? "left" : "right");
    }

    
    /**
     * Philosopher is checking his neighbor's state periodically and releases 
     * chopsticks synchronously, in his thread. If isRequestRequired set to 
     * true philosopher can send chopstick he owns only if the neighbor requested
     * it. If isRequestRequired is false he can release chopstick regardless 
     * of neighbor's request (useful when he stops checking neighbor's state).
     */
    void processChopsticks(boolean isRequestRequired) {
        giveUpChopstickIfNecessary(leftChopstick, leftNeighbor, isRequestRequired);
        giveUpChopstickIfNecessary(rightChopstick, rightNeighbor, isRequestRequired);
    }
    
    
    /**
     * Philosopher gives up only dirty chopstick he owns, 
     * on request OR unconditionally (e.g. if he's finished dinner
     * and not going to track his neighbor's requests anymore)
     */
    void giveUpChopstickIfNecessary(Chopstick chopstick, Philosopher receiver, boolean isRequestRequired) {
        
         synchronized (chopstick) {
            if ( (receiver.goingToEatRequest || !isRequestRequired) &&  // give up chopstick only on request OR unconditionally
                    !chopstick.isClean &&                       // only dirty chopstick
                    chopstick.owner == this) {                  // only chopstick he owns
                chopstick.isClean = true;                       // wash chopstick before sending out
                chopstick.owner = receiver;
                eatInRaw = 0;                                   // reset # eats-in-raw because chopstick sent out

//                System.out.format("Chopstick %d sent to Philosopher %d by Philosopher %d\n", chopstick.id,
//                        chopstick.owner.id, id);

                chopstick.notify();                             // notify waiting threads
            }
        }
    }
    
    
    void eat() {
        eatInRaw++;
        eatNum++;
        rightChopstick.isClean = leftChopstick.isClean = false;
        String eatersList = eaters.addEater(this);
        System.out.format("Philosopher %d starts eating. Eats in raw: %d. Eating at present: %s.\n",
                        id, eatInRaw, eatersList);
//        System.out.format("Philosopher %d eats.\n", id);
        StaticMethods.sleep(StaticMethods.random(100, 200));
        eaters.removeEater(this);
//        System.out.format("Philosopher %d finished eating (%d times).\n", id, eatNum);
        System.out.format("Philosopher %d puts down right chopstick.\n", id);
        System.out.format("Philosopher %d puts down left chopstick.\n", id);
    }

    
    void think() {
//        System.out.format("Philosopher %d thinks.\n", id);
        StaticMethods.sleep(StaticMethods.random(100, 200));
    }

    
    public void start() {
        thread.start();
    }

    
    public void join() {
        try {
            thread.join();
        } catch (InterruptedException e) {
            System.out.println("InterruptedException caught");
        }
    }
    
}

class Chopstick {

    final int id;
    volatile Philosopher owner;
    volatile boolean isClean = false;

    public Chopstick(int id) {
        super();
        this.id = id;
    }
}

/**
 * Auxiliary static methods.
 * 
 */
class StaticMethods {

    /**
     * Generates random integer [Min, Max]
     */
    public static int random(int Min, int Max) {
        return Min + (int) (Math.random() * ((Max - Min) + 1));
    }
    
    /**
     * Sleeps delay ms 
     */
    public static void sleep(int delay)
    {
        try {
            Thread.sleep(delay);
        } catch (InterruptedException e) {
            System.out.println("InterruptedException caught");
        }
    }
}

/**
 * Auxiliary class. Tracks persons eating at present  
 * 
 */
class eaters {

    static java.util.List<Philosopher> eaters = new java.util.ArrayList<Philosopher>();

    public synchronized static String addEater(Philosopher philosopher) {
        eaters.add(philosopher);
        return eatersToString();
    }

    public synchronized static String removeEater(Philosopher philosopher) {
        eaters.remove(philosopher);
        return eatersToString();
    }

    private static String eatersToString() {
        String s = "";
        for (Philosopher philosopher : eaters)
            s += philosopher.id + " ";
        return s.trim();
    }
}