//-----------------------------------------------------------------
// CSE 461 Project 1:                        Timer implementation
//
// timer.java: implementation of the simulated time clock
//             and other time-related functions.
//-----------------------------------------------------------------
import java.io.*;
import java.util.*;

//-----------------------------------------------------------------
// TimerClient: clients who wish to receive timeouts need to 
//              implement this interface
//-----------------------------------------------------------------
interface TimerClient
{
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Timeout: the callback for timeouts.  When a timeout fires,
   //          this method on the client will be called.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public void Timeout (Object info);
}

//-----------------------------------------------------------------
// NotActiveThreadException is thrown if a thread attempts to
// use the waiting interface without being registered.
//-----------------------------------------------------------------
class NotActiveThreadException extends Exception
{
}

//-----------------------------------------------------------------
// Timer: the simulated-time clock.  This is a large class, and
//        the interface is divided into several sections:
//
//    Clock interface:    read the time
//    Timeout interface:  establish timeouts that will fire some
//                        time in the future
//    Wait interface:     block the current thread until some
//                        time in the future.
//
// Clients using the timeout interface need to make sure that
// the processing done on a timeout logically takes zero
// simulated time, because simulated time cannot advance while
// a timeout is being processed.
//
// Clients using the wait interface need to use the registration
// to control the advance of time.  Simulated time cannot advance
// when a thread is registered but not currently blocked in 
// one of the Timer Wait* functions.  Correct use of this
// interface is subtle.
//-----------------------------------------------------------------
class Timer implements Runnable
{
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Constructor: set stuff up and start the event processing
   //              thread
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public Timer ()
   {
      simTime = 0;
      activeThreads = new Hashtable ();
      pendingTimeouts = new Vector ();

      timeoutThread = new Thread (this);
      timeoutThread.start ();

      (new TimerMonitor (this)).start ();
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Shutdown: stop the timer, not really necessary.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public void Shutdown ()
   {
      timeoutThread.stop ();
      timeoutThread = null;
      activeThreads = null;
      pendingTimeouts = null;
   }

   //--------------------------------------------------------------
   // General clock interface:
   //
   // The Timer can be used as a simple clock that measure simulated
   // time to a ridiculously accurate degree.
   //--------------------------------------------------------------

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Current simulator time in us
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public long CurrentSimTime ()
   {
      return simTime;
   }

   //--------------------------------------------------------------
   // Timeout interface:
   //
   // Use this interface to set up timeouts.  Any class which 
   // implements the TimerClient interface above can receive 
   // timeouts.  SetTimeout sets up a timeout for client.  Some
   // time (as soon as possible) after the simulated time exceeds
   // alarmTime a call to the clients Timeout method will occur,
   // with the object info as an argument.
   //
   // The TimeoutID that SetTimeout returns can be passed to 
   // CancelTimeout to cancel that timeout before it fires.
   //--------------------------------------------------------------

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // SetTimeout:  set a timeout for the future
   //
   //    client         the client to wake up when the time expires
   //    time           the number of time units from now that the
   //                     timeout will expire
   //    units          the units of time, one of:
   //                      Timer.SEC     seconds
   //                      Timer.MS      milliseconds
   //                      Timer.US      microseconds
   //    info           the information about the timeout to pass
   //                     back to the client when the timeout expires
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public synchronized TimeoutID SetTimeout (TimerClient client, 
                                             long time, 
                                             TimeUnit units,
                                             Object info)
   {
      long alarmTime = CurrentSimTime () + units.ConvertToUS (time);

      TimeoutID id = new TimeoutID ();
      id.time = alarmTime;
      id.info = info;
      id.client = client;
      id.internalWakeup = false;
      id.thread = null;

      AddTimeout (id);

      notifyAll ();     // wake up the timeoutThread

      return id;
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Internal function to manipulate the event queue
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   private void AddTimeout (TimeoutID id)
   {
      int i = 0;
      while (i < pendingTimeouts.size () &&
             ((TimeoutID) pendingTimeouts.elementAt (i)).time < id.time)
         ++i;

      pendingTimeouts.insertElementAt (id, i);
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // CancelTimeout: given an ID from a previous SetTimeout,
   //                remove it from the queue.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public synchronized void CancelTimeout (TimeoutID id)
   {
      pendingTimeouts.removeElement (id);
   }

   //--------------------------------------------------------------
   // Waiting interface:    (intended for internal use only)
   //
   // This interface allows threads to block until a simulated
   // time is reached.  WaitUntil blocks the caller until some
   // time after simulated time exceeds time.
   //
   // The important thing about this interface is that threads
   // which are using WaitUntil need to register with the timer,
   // using RegisterThread and UnregisterThread, and that the
   // waiting behavior of these threads determines when simulated
   // time advances: only when all registered threads are blocked
   // will simulated time advance.
   //--------------------------------------------------------------


   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // WaitFor: block the current thread for a specified number
   //          of simulated time units
   //
   //   time   time units to sleep
   //   units  units for time
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public void WaitFor (long time, TimeUnit units) throws NotActiveThreadException
   {
      long wakeupTime = CurrentSimTime () + units.ConvertToUS (time);
      WaitUntil (wakeupTime, US);
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // WaitUntil: block the current thread until a specified 
   //            simulated time
   //
   //   time     time to wake up
   //   units    units for time
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public synchronized void WaitUntil (long time, TimeUnit units)
                                             throws NotActiveThreadException 
   {
      long wakeupTime = units.ConvertToUS (time);

      // make sure we sleep for a little while
      if (wakeupTime <= CurrentSimTime ())
         wakeupTime = CurrentSimTime () + 1; 

      Thread current = Thread.currentThread ();
      if (!activeThreads.containsKey (current))
         throw new NotActiveThreadException ();

      activeThreads.put (current, Boolean.TRUE);

      TimeoutID id = new TimeoutID ();
      id.time = wakeupTime;
      id.info = null;
      id.client = null;
      id.internalWakeup = true;
      id.thread = current;

      AddTimeout (id);

      notifyAll ();            // wake up the timer thread

      while (CurrentSimTime () < wakeupTime)
         try
            {
            wait ();
            }
         catch (InterruptedException e)
            {
            }

      // Don't need to set ourselves as not waiting, because
      // run thread did that before it woke us
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // RegisterThread: tell the simulator that this thread cares
   //                 about simulated time.  Time may only advance
   //                 when all registered threads are waiting.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public synchronized void RegisterThread (Thread t)
   {
      if (!activeThreads.containsKey (t))
         activeThreads.put (t, Boolean.FALSE);   // not waiting
      notifyAll ();
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // UnregisterThread: tell the simulator that this thread no
   //                   longer cares about simulated time.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public synchronized void UnregisterThread (Thread t)
   {
      activeThreads.remove (t);

      boolean canGo = true;
      Enumeration e = activeThreads.elements ();
      while (e.hasMoreElements ())
         if (e.nextElement () == Boolean.FALSE)
            canGo = false;

      notifyAll ();
      Debug.println ('t', "Just unregistered thread '" + t + "'");
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // main event processing loop: if we can advance time, then 
   // advance to the next event and process it.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public synchronized void run ()
   {
      Thread.currentThread ().setName ("Timeout processor");
      for (;;)
         {
         boolean timeAdvanced = false;

         boolean canGo = true;
         Enumeration e = activeThreads.elements ();
         while (e.hasMoreElements ())
            if (e.nextElement () == Boolean.FALSE)
               canGo = false;

         Debug.println ('t', "Top of process loop: canGo is " + canGo);
         Debug.print ('t', "Queue: ");
         Enumeration pendingEvents = pendingTimeouts.elements ();
         while (pendingEvents.hasMoreElements ())
            {
            TimeoutID data = (TimeoutID) pendingEvents.nextElement ();
            Debug.print ('t', "[" + data.time + " (");
            if (data.internalWakeup)
               Debug.print ('t', "w '" + data.thread + ")] ");
            else
               Debug.print ('t', "t '" + data.client + ")] ");
            }
         Debug.println ('t', "");

         while (pendingTimeouts.size () > 0 && (canGo || 
                ((TimeoutID)pendingTimeouts.elementAt (0)).time <= simTime))
            {
            // All threads blocked, trigger next event
            TimeoutID id = (TimeoutID) pendingTimeouts.elementAt (0);
            pendingTimeouts.removeElementAt (0);
            if (simTime < id.time)
               {
               simTime = id.time;
               timeAdvanced = true;
               }

            if (id.internalWakeup)
               {
               if (activeThreads.containsKey (id.thread))
                  activeThreads.put (id.thread, Boolean.FALSE);
               else
                  Debug.println ('t', "BAD!!! thread " + id.thread + " was woken unregistered!");
               }
            else
               {
               inTimeout = true;
               Thread t = new TimeoutCallbackThread (this, id.client, id.info);
               RegisterThread (t);
               t.start ();
               inTimeout = false;
               }

            canGo = true;
            e = activeThreads.elements ();
            while (e.hasMoreElements ())
               if (e.nextElement () == Boolean.FALSE)
                  canGo = false;

            Debug.print ('t', "canGo is " + canGo + "; Queue: ");
            pendingEvents = pendingTimeouts.elements ();
            while (pendingEvents.hasMoreElements ())
               {
               TimeoutID data = (TimeoutID) pendingEvents.nextElement ();
               Debug.print ('t', "[" + data.time + " (");
               if (data.internalWakeup)
                  Debug.print ('t', "w '" + data.thread + ")] ");
               else
                  Debug.print ('t', "t '" + data.client + ")] ");
               }
            Debug.println ('t', "");
            }

         if (timeAdvanced)
            notifyAll ();

         try
            {
            waiting = true;
            Debug.println ('t', "Timeout proceesor waiting.");
            wait ();
            waiting = false;
            }
         catch (InterruptedException ex)
            {
            }
         }
   }

   private long simTime;
   private Vector pendingTimeouts;
   private Hashtable activeThreads;
   private Thread timeoutThread;

   public static TimeUnit SEC = new TimeUnit (1000000);
   public static TimeUnit MS  = new TimeUnit (1000);
   public static TimeUnit US  = new TimeUnit (1);

   private boolean waiting;
   private boolean inTimeout;

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Print out the status of the timer, including event queue
   // and registered threads.  Should be synchronized, but this
   // is useful as a debugging tool when things deadlock, so
   // it is left unsychronized.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public /*synchronized*/ void PrintStatus ()
   {
      System.out.print ("\nTimer stalled at time " + CurrentSimTime ()
			 + ": Current Timer Status:");
      if (waiting)
         System.out.println (" waiting");
      if (inTimeout)
         System.out.println (" in timeout");

      System.out.print ("Queue: ");
      Enumeration pendingEvents = pendingTimeouts.elements ();
      while (pendingEvents.hasMoreElements ())
         {
         TimeoutID data = (TimeoutID) pendingEvents.nextElement ();
         System.out.print ("[" + data.time + " (");
         if (data.internalWakeup)
            System.out.print ("w '" + data.thread + ")] ");
         else
            System.out.print ("t '" + data.client + ")] ");
         }
      System.out.println ("");
      System.out.println ("Active Threads: ");

      Enumeration e = activeThreads.keys ();
      while (e.hasMoreElements ())
         {
         Thread t = (Thread) e.nextElement ();
         System.out.print ("  " + t + ": ");
         if (activeThreads.get (t) == Boolean.TRUE)
            System.out.println ("waiting");
         else
            System.out.println ("processing");
         }

      Thread[] threads = new Thread[50];
      int count = Thread.currentThread ().enumerate (threads);
      System.out.println ("All threads:");
      for (int i=0; i<count; ++i)
         {
         System.out.println ("   '" + threads[i] + "'");
         }
   }
}

//-----------------------------------------------------------------
// TimeoutID: implementation of the IDs passed for timeouts.
//            For convenience, this carries the data about the
//            timeout.  Clients should not access this data.
//-----------------------------------------------------------------
class TimeoutID
{
   boolean internalWakeup;

   long time;
   Object info;
   TimerClient client;

   Thread thread;
}

//-----------------------------------------------------------------
// TimeUnit: implementation of the time units in the Timer.
//           TimeUnits know how to convert themselves
//-----------------------------------------------------------------
class TimeUnit
{
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Create a new unit with a given conversion to mircoseconds
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   TimeUnit (long factor)
   {
      convFactor = factor;
   }

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Convert a time in these units to microseconds
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public long ConvertToUS (long time)
   {
      return time * convFactor;
   }

   private long convFactor;
}


//-----------------------------------------------------------------
// TimeoutCallbackThread: a thread to run timeout processing 
//                        in the background.  This allows
//                        timeouts to run without holding the
//                        Timer monitor, which is desireable for
//                        deadlock avoidance.
//-----------------------------------------------------------------
class TimeoutCallbackThread extends Thread
{
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Set up the thread
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public TimeoutCallbackThread (Timer timer, TimerClient client, Object info)
   {
      this.timer = timer;
      this.client = client;
      this.info = info;
   }

   private Timer timer;
   private TimerClient client;
   private Object info;

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Run the timeout.  Note that we run registered to prevent 
   // time from advancing.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public void run ()
   {
      Thread.currentThread ().setName ("Timeout run thread for client " + client);
      /* Already registered when created
         timer.RegisterThread (Thread.currentThread ());
      */
      client.Timeout (info);
      timer.UnregisterThread (Thread.currentThread ());
   }
}

//-----------------------------------------------------------------
// TimerMonitor: another thread which watches to see if the timer
//               appears stalled (i.e. deadlocked), and prints
//               out some status if it happens
//-----------------------------------------------------------------
class TimerMonitor extends Thread
{
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Set up the timer to monitor
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public TimerMonitor (Timer timer)
   {
      this.timer = timer;
   }

   private Timer timer;

   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   // Wait for 2 real seconds, and if simulated time doesn't advance
   // assume deadlock.
   // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   public void run ()
   {
      Thread.currentThread ().setName ("Timer monitor");

      long lastPrint = -1;

      for (;;)
         {
         long t1 = timer.CurrentSimTime ();

         try
            {
            sleep (2000);
            }
         catch (InterruptedException e)
            {
            }

         long t2 = timer.CurrentSimTime ();
         if (t1 == t2 && t2 != lastPrint)
            {
            lastPrint = t2;
            timer.PrintStatus ();
            }
         }
   }
}