import java.util.ArrayList;
import java.util.concurrent.Semaphore;
import java.util.logging.Level;
import java.util.logging.Logger;


public class LizardsSync {
    /*
     * Set this to the number of seconds you want the lizard world to
     * be simulated.
     * Try 30 for development and 120 for more thorough testing.
     */

    private static int WORLDEND = 120;

    /*
     * Number of lizard threads to create
     */
    private static int NUM_LIZARDS = 20;

    /*
     * Maximum lizards crossing at once before alerting cats
     */
    private static int MAX_LIZARD_CROSSING = 4;

    /*
     * Maximum seconds for a lizard to sleep
     */
    private static int MAX_LIZARD_SLEEP_TIME = 3;

    /*
     * Maximum seconds for a lizard to eat
     */
    private static int MAX_LIZARD_EAT_TIME = 5;

    /*
     * Number of seconds it takes to cross the driveway
     */
    private static int CROSS_TIME = 2;

    /*
     * Number of seconds for the cat to sleep.
     */
    private static int MAX_CAT_SLEEP=2;

    /*
     * A counter that counts the number of lizzards crossing sago to monkey grass
     */
    int numCrossingSago2MonkeyGrass = 0;

    /*
     * A counter that counts the number of lizzards crossing monkey grass to sago
     */
    int numCrossingMonkeyGrass2Sago = 0;

    /**
     * A semaphore to protect the crossway.
     */
    Semaphore semaphoreCrossway= new Semaphore(MAX_LIZARD_CROSSING);

    /**
     * A semaphore for mutual exclusion.
     */
    Semaphore mutex = new Semaphore(1);
    /*
     * Indicates if the world is still running.
     */
    private static boolean running = true;
    /*
     * Indicates if you want to see debug information or not.
     */
    private static boolean debug = true;

    /**
     * The program that runs the lizard simulation.
     **/
    public void startSimulation()
    {
        ArrayList<Thread> allThreads = new ArrayList<Thread>();

        // create all the lizzard threads
        for (int i=0; i <NUM_LIZARDS; i++)
        {       allThreads.add(new LizardThread(i) );
        }
        // create the cat thread
        allThreads.add(new CatThread());

        // let the world run for a while
        for (int i=0; i < allThreads.size(); i++)
        {

            allThreads.get(i).start();

        }
          sleep (WORLDEND);
        // terminate all threads
        running = false;

         // wait until all threads terminate by joining all of them
         for (int i=0; i < allThreads.size(); i++) {
            try {
               allThreads.get(i).join();
            } catch (InterruptedException ex) {
                System.err.println ("unable to join thread, " + ex.getMessage());
            }

         }
    }

     /**
     * Models a cat thread.
     */
    public class CatThread extends Thread {


        /**
         * @see java.lang.Runnable.
         */
        @Override
        public void run()
        {

            while (running) {
               // sleep for a while
               catSleep();

               // check on lizzards
               checkCrossway();
            }
        }

        /**
         * Puts cat thread to sleep for a random time.
         */
        public void catSleep()
        {
            int sleepSeconds  = 1 + (int)(Math.random()*MAX_CAT_SLEEP);

            if (debug) {
                System.out.println ("Cat is sleeping for " + sleepSeconds + " seconds.");
                System.out.flush();
            }
            try {
                sleep(sleepSeconds*1000);
            } catch (InterruptedException ex) {
                Logger.getLogger(LizardsSync.class.getName()).log(Level.SEVERE, null, ex);
            }
            if (debug) {
                System.out.println ("Cat awakes.");
                System.out.flush();
            }
        }

        /**
         * Simulates cat checking the crossway.
         */
        public void checkCrossway()
        {
            if (numCrossingMonkeyGrass2Sago + numCrossingSago2MonkeyGrass > MAX_LIZARD_CROSSING) {
                System.out.println ("The cat says yum!");
                System.out.flush();
					 System.exit(-1);
            }
       }
    }

    /**
     * Models a lizard thread.
     */
    public class LizardThread extends Thread {

        private int _id;

        /**
         * Creates a new lizard thread.
         *
         * @param id the id assigned to the lizard thread
         */
        public LizardThread(int id)
        {
            _id = id;
        }

        /**
         * @see java.lang.Runnable.
         */
        @Override
        public void run()
        {

            while (running) {


               // sleep for a while in sago
               lizardSleep();
               // wait until safe to cross from sago to monkey grass
               sagoToMonkeyIsSafe();
               // cross path to monkey grass
               crossSagoToMonkey();
              //finish crossing
               crossedOverToMonkey();
              //eat in the monkey grass
               lizardEat();
              //Wait until safe to cross from monkey grass to sago
               monkeyToSagoIsSafe();
              // cross path to sago
               crossMonkeyToSago();
                //finish crossing
               crossedOverToSago();
            }

        }

        /**
         * This tests if it is safe to travel from sago to monkey.
         */
        public void sagoToMonkeyIsSafe()
        {
            if (debug) {
                System.out.println ("Lizard [" + _id + "] checks sago -> monkey grass.");
                System.out.flush();
            }
            //try to acquire a permit
        try {
                semaphoreCrossway.acquire();
            } catch (InterruptedException ex) {
                Logger.getLogger(LizardsSync.class.getName()).log(Level.SEVERE, "unable to acquire lock", ex);
            }

           //print the number of available permits
           System.out.println("Lock acquired onLizard [" + _id + "]. There are " +semaphoreCrossway.availablePermits()+" permits available");

            if (debug) {
                System.out.println ("Lizard [" + _id + "] thinks sago -> monkey grass is safe.");
                System.out.flush();
            }
        }

        /**
         * Indicates that lizard crossed over to monkey grass.
         */
        public void crossedOverToMonkey()
        {
            if (debug) {
                System.out.println ("Lizard [" + _id + "] made it to monkey grass.");
                System.out.flush();
            }
            //release the semaphore
             semaphoreCrossway.release();
             //print the number of available permits
           System.out.println("Lock acquired onLizard [" + _id + "]. There are " +semaphoreCrossway.availablePermits()+" permits available");
        }


        /**
         * This tests if it is safe to travel from monkey to sago.
         */
        public void monkeyToSagoIsSafe()
        {
            if (debug) {
                System.out.println ("Lizard [" + _id + "] checks monkey grass -> sago.");
                System.out.flush();
            }

           //try to acquire a permit
        try {
                semaphoreCrossway.acquire();
            } catch (InterruptedException ex) {
                Logger.getLogger(LizardsSync.class.getName()).log(Level.SEVERE, "unable to acquire lock", ex);
            }

           //print the number of available permits
           System.out.println("Lock acquired on Lizard [" + _id + "]. There are " +semaphoreCrossway.availablePermits()+" permits available");

            if (debug) {
                System.out.println ("Lizard [" + _id + "] thinks monkey grass -> sago is safe.");
                System.out.flush();
            }
        }

        /**
         * Indicates that lizard crossed over to sago.
         */
        public void crossedOverToSago()
       {
            if (debug) {
                System.out.println ("Lizard [" + _id + "] made it to sago.");
                System.out.flush();
            }
            //release the semaphore
             semaphoreCrossway.release();
           //print the number of available permits
           System.out.println("Lock acquired on Lizard [" + _id + "]. There are " +semaphoreCrossway.availablePermits()+" permits available");
        }

        /**
         * Indicates that lizard is crossing over from monkey to sago.
         */
        void crossMonkeyToSago()
        {
            if (debug) {
                System.out.println ("Lizard [" + _id + "] is crossing monkey grass to sago.");
                System.out.flush();
            }


            numCrossingMonkeyGrass2Sago++;
            System.err.print(numCrossingMonkeyGrass2Sago);


            // simulate walk
            try {
                sleep(CROSS_TIME*1000);
            } catch (InterruptedException ex) {
                Logger.getLogger(LizardsSync.class.getName()).log(Level.SEVERE, null, ex);
            }

            numCrossingMonkeyGrass2Sago--;
            System.err.print(numCrossingMonkeyGrass2Sago);

        }

        /**
         * Indicates that lizard is crossing over from sago to monkey.
         */
        void crossSagoToMonkey()
        {

            if (debug) {
                System.out.println ("Lizard [" + _id + "] is crossing sago to monkey grass.");
                System.out.flush();
            }

            numCrossingSago2MonkeyGrass++;
            System.err.print(numCrossingSago2MonkeyGrass);



            // simulate walk
            try {
                sleep(CROSS_TIME*1000);
            } catch (InterruptedException ex) {
                Logger.getLogger(LizardsSync.class.getName()).log(Level.SEVERE, null, ex);
            }

            numCrossingSago2MonkeyGrass--;
            System.err.print(numCrossingSago2MonkeyGrass);

        }


        /**
         * Puts lizard thread to sleep for a random amount of time.
         */
        public void lizardSleep()
        {
            int sleepSeconds  = 1 + (int)(Math.random()*MAX_LIZARD_SLEEP_TIME);

            if (debug) {
                System.out.println ("Lizard [" + _id + "] is sleeping for " + sleepSeconds + " seconds.");
                System.out.flush();
            }
            try {
                sleep(sleepSeconds*1000);
            } catch (InterruptedException ex) {
                Logger.getLogger(LizardsSync.class.getName()).log(Level.SEVERE, null, ex);
            }
            if (debug) {
                System.out.println ("Lizard [" + _id + "] awakes.");
                System.out.flush();
            }
        }

        /**
         * Simulates lizard eating for a random amount of time.
         */
        public void lizardEat()
        {
            int eatSeconds  = 1 + (int)(Math.random()*MAX_LIZARD_EAT_TIME);

            if (debug) {
                System.out.println ("Lizard [" + _id + "] is eating for " + eatSeconds + " seconds.");
                System.out.flush();
            }
            try {
                sleep(eatSeconds*1000);
            } catch (InterruptedException ex) {
                Logger.getLogger(LizardsSync.class.getName()).log(Level.SEVERE, null, ex);
            }
            if (debug) {
                System.out.println ("Lizard [" + _id + "] finished eating.");
                System.out.flush();
            }
        }
    }

    /**
     * Puts current thread to sleep for a specified amount of time.
     *
     * @param seconds the number of seconds to put the thread to sleep
     */
    private static void sleep(int seconds)
    {
        try {
            Thread.sleep(seconds*1000);
        } catch (InterruptedException ex) {
            Logger.getLogger(LizardsSync.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

}
----
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        LizardsSync myLizardsSync = new LizardsSync();

        // run simulation of lizards and cats.
        myLizardsSync.startSimulation();

    }
}