//******************************************************************************
   //
   // File:    TimerThread.java
   // Package: edu.rit.util
   // Unit:    Class edu.rit.util.TimerThread
   //
   // This Java source file is copyright (C) 2002-2004 by Alan Kaminsky. All rights
   // reserved. For further information, contact the author, Alan Kaminsky, at
   // ark@cs.rit.edu.
  //
  // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
  // software; you can redistribute it and/or modify it under the terms of the GNU
  // General Public License as published by the Free Software Foundation; either
  // version 3 of the License, or (at your option) any later version.
  //
  // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
  // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
  //
  // Linking this library statically or dynamically with other modules is making a
  // combined work based on this library. Thus, the terms and conditions of the GNU
  // General Public License cover the whole combination.
  //
  // As a special exception, the copyright holders of this library give you
  // permission to link this library with independent modules to produce an
  // executable, regardless of the license terms of these independent modules, and
  // to copy and distribute the resulting executable under terms of your choice,
  // provided that you also meet, for each linked independent module, the terms
  // and conditions of the license of that module. An independent module is a module
  // which is not derived from or based on this library. If you modify this library,
  // you may extend this exception to your version of the library, but you are not
  // obligated to do so. If you do not wish to do so, delete this exception
  // statement from your version.
  //
  // A copy of the GNU General Public License is provided in the file gpl.txt. You
  // may also obtain a copy of the GNU General Public License on the World Wide
  // Web at http://www.gnu.org/licenses/gpl.html.
  //
  //******************************************************************************
  package edu.rit.util;
  
  import java.util.Iterator;
  import java.util.Vector;
  
  /**
   * Class TimerThread encapsulates a thread that does the timing for {@linkplain
   * Timer}s and performs {@linkplain TimerTask}s' actions when timeouts occur.
   * <P>
   * A timer is created by calling a timer thread's <code>createTimer()</code> method,
   * giving a timer task to associate with the timer. Multiple timers may be
   * created under the control of the same timer thread. The timer thread will
   * perform the actions of its timers' timer tasks one at a time at the proper
   * instants (by causing each timer to call its timer task's <code>action()</code>
   * method). Note that the timer tasks of a single timer thread are performed
   * sequentially, which may cause some timer tasks' actions to be delayed
   * depending on how long other timer tasks' actions take to execute. If
   * necessary, consider running separate timers in separate timer threads so the
   * timer tasks' actions run concurrently.
   * <P>
   * Class TimerThread does <I>not</I> offer real-time guarantees. It merely makes
   * a best-effort attempt to perform each timer task's actions as soon as
   * possible after the timeouts occur.
   * <P>
   * A TimerThread is just a {@linkplain java.lang.Thread Thread}. After
   * constructing a timer thread, you can mark it as a daemon thread if you want.
   * You must also call the timer thread's <code>start()</code> method, or no timeouts
   * will occur. To gracefully stop a timer thread, call the <code>shutdown()</code>
   * method.
   * <P>
   * To simplify writing programs with multiple objects that all use the same
   * timer thread, the static <code>TimerThread.getDefault()</code> method returns a
   * single shared instance of class TimerThread. The default timer thread is
   * marked as a daemon thread and is started automatically. The default timer
   * thread is not created until the first call to
   * <code>TimerThread.getDefault()</code>.
   * <P>
   * Classes {@linkplain Timer}, {@linkplain TimerTask}, and TimerThread provide
   * capabilities similar to classes java.util.Timer and java.util.TimerTask.
   * Unlike the latter, they also provide the ability to stop and restart a timer
   * and the ability to deal with race conditions in multithreaded programs.
   *
   * @author Alan Kaminsky
   * @version 18-Jun-2003
   */
  public class TimerThread
          extends Thread {
  
  // Hidden helper classes.
      /**
       * Class TimerThread.TimeoutInfo is a record used to keep track of a
       * timeout.
       *
       * @author Alan Kaminsky
       * @version 18-Sep-2002
       */
      private static class TimeoutInfo {
          // Instant at which the timeout will occur (milliseconds since midnight
          // 01-Jan-1970 UTC).
  
         public long myTimeout;
 
         // Timer to trigger.
         public Timer myTimer;
 
         public TimeoutInfo(long theTimeout,
                 Timer theTimer) {
             myTimeout = theTimeout;
             myTimer = theTimer;
         }
     }
 
 // Hidden data members.
     /**
      * Queue of timeout info records, organized as a heap in order of timeout.
      * Index 0 is unused. Indexes 1 .. mySize contain the heap. The queue's
      * length is increased by INCR when necessary to add a new record.
      */
     private static final int INCR = 4;
     private TimeoutInfo[] myQueue = new TimeoutInfo[INCR + 1];
 
     /**
      * Number of records in the queue.
      */
     private int mySize = 0;
 
     /**
      * True if this timer thread is running, false if it's shut down.
      */
     private boolean iamRunning = true;
 
 // Hidden static data members.
     /**
      * The default timer thread.
      */
     private static TimerThread theDefaultTimerThread = null;
 
 // Exported constructors.
     /**
      * Construct a new timer thread. After constructing it, you must call the
      * timer thread's <code>start()</code> method, or no timeouts will occur.
      */
     public TimerThread() {
         super();
     }
 
 // Exported operations.
     /**
      * Get the default timer thread, a single shared instance of class
      * TimerThread. The default timer thread is marked as a daemon thread and is
      * started automatically. The default timer thread is not created until the
      * first call to <code>TimerThread.getDefault()</code>.
      *
      * @return Default timer thread.
      */
     public static synchronized TimerThread getDefault() {
         if (theDefaultTimerThread == null) {
             theDefaultTimerThread = new TimerThread();
             theDefaultTimerThread.setDaemon(true);
             theDefaultTimerThread.start();
         }
         return theDefaultTimerThread;
     }
 
     /**
      * Create a new timer associated with the given timer task and under the
      * control of this timer thread. When the timer is triggered, this timer
      * thread will cause the timer to call the given timer task's
      * <code>action()</code> method.
      *
      * @param theTimerTask Timer task.
      * @exception NullPointerException (unchecked exception) Thrown if
      * <code>theTimerTask</code> is null.
      * @return a {@link edu.rit.util.Timer} object.
      */
     public Timer createTimer(TimerTask theTimerTask) {
         return new Timer(this, theTimerTask);
     }
 
     /**
      * Shut down this timer thread.
      */
     public void shutdown() {
         synchronized (this) {
             iamRunning = false;
             notifyAll();
         }
     }
 
     /**
      * Perform this timer thread's processing. (Never call the <code>run()</code>
      * method yourself!)
      *
      * @exception IllegalStateException (unchecked exception) Thrown if some
      * thread other than this timer thread called the <code>run()</code> method.
      */
     @SuppressWarnings("unchecked")
     public void run() {
         // Only this timer thread itself can call the run() method.
         if (Thread.currentThread() != this) {
             throw new IllegalStateException("Wrong thread called the run() method");
         }
 
         try {
             while (iamRunning) {
                 long now = System.currentTimeMillis();
                 Vector<TimeoutInfo> theTriggeredTimeouts;
 
                 synchronized (this) {
                     // If timeout queue is empty, wait until notified.
                     if (mySize == 0) {
                         wait();
                         now = System.currentTimeMillis();
                     } // If timeout queue is not empty and first timeout is in the
                     // future, wait until timeout or until notified.
                     else {
                         long waitTime = myQueue[1].myTimeout - now;
                         if (waitTime > 0L) {
                             wait(waitTime);
                             now = System.currentTimeMillis();
                         }
                     }
 
                     // Pull all timeouts that have occurred out of the timeout
                     // queue into a separate list.
                     theTriggeredTimeouts = new Vector<>();
                     while (mySize > 0 && myQueue[1].myTimeout <= now) {
                         theTriggeredTimeouts.add(myQueue[1]);
                         myQueue[1] = myQueue[mySize];
                         myQueue[mySize] = null;
                         --mySize;
                         siftDown(mySize);
                     }
                 }
 
                 // Perform the action of each triggered timeout. Do this outside
                 // the synchronized block, or a deadlock may happen if a timer
                 // is restarted.
                 Iterator<TimeoutInfo> iter = theTriggeredTimeouts.iterator();
                 while (iter.hasNext()) {
                     iter.next().myTimer.trigger(now);
                 }
             }
         } catch (InterruptedException exc) {
             System.err.println("TimerThread interrupted");
             exc.printStackTrace(System.err);
         }
     }
 
 // Hidden operations.
     /**
      * Schedule a timer.
      *
      * @param theTimeout Timeout instant.
      * @param theTimer Timer.
      */
     synchronized void schedule(long theTimeout,
             Timer theTimer) {
         // Increase queue allocation if necessary.
         if (mySize == myQueue.length - 1) {
             TimeoutInfo[] newQueue = new TimeoutInfo[myQueue.length + INCR];
             System.arraycopy(myQueue, 1, newQueue, 1, mySize);
             myQueue = newQueue;
         }
 
         // Add a new timeout info record to the queue.
         ++mySize;
         myQueue[mySize] = new TimeoutInfo(theTimeout, theTimer);
         siftUp(mySize);
 
         // Wake up the timer thread.
         notifyAll();
     }
 
     /**
      * Sift up the last element in the heap. Precondition: HEAP(1,n-1) and n
      * &gt; 0. Postcondition: HEAP(1,n).
      */
     private void siftUp(int n) {
         int i = n;
         int p;
         TimeoutInfo temp;
         for (;;) {
             // Invariant: HEAP(1,n) except perhaps between i and its parent.
             if (i == 1) {
                 break;
             }
             p = i / 2;
             if (myQueue[p].myTimeout <= myQueue[i].myTimeout) {
                 break;
             }
             temp = myQueue[p];
             myQueue[p] = myQueue[i];
             myQueue[i] = temp;
             i = p;
         }
     }
 
     /**
      * Sift down the first element in the heap. Precondition: HEAP(2,n) and n
      * &gt;= 0. Postcondition: HEAP(1,n).
      */
     private void siftDown(int n) {
         int i = 1;
         int c;
         TimeoutInfo temp;
         for (;;) {
             // Invariant: HEAP(1,n) except perhaps between i and its 0, 1, or 2
             // children.
             c = 2 * i;
             if (c > n) {
                 break;
             }
             // c is the left child of i.
             if (c + 1 <= n) {
                 // c+1 is the right child of i.
                 if (myQueue[c + 1].myTimeout < myQueue[c].myTimeout) {
                     c = c + 1;
                 }
             }
             // c is the least child of i.
             if (myQueue[i].myTimeout <= myQueue[c].myTimeout) {
                 break;
             }
             temp = myQueue[c];
             myQueue[c] = myQueue[i];
             myQueue[i] = temp;
             i = c;
         }
     }
 
 // Unit test main program.
 //	/**
 //	 * Helper class for unit test main program.
 //	 */
 //	private static class Message
 //		implements TimerTask
 //		{
 //		private String myMessage;
 //
 //		public Message
 //			(String theMessage)
 //			{
 //			myMessage = theMessage;
 //			}
 //
 //		public void action
 //			(Timer theTimer)
 //			{
 //			System.out.println (myMessage);
 //			}
 //		}
 //
 //	/**
 //	 * Unit test main program.
 //	 */
 //	public static void main
 //		(String[] args)
 //		{
 //		try
 //			{
 //			TimerThread theTimerThread = new TimerThread();
 //			theTimerThread.start();
 //
 //			Timer timer1 =
 //				theTimerThread.createTimer
 //					(new Message ("Timer 1 triggered"));
 //
 //			Timer timer2 =
 //				theTimerThread.createTimer
 //					(new Message ("Timer 2 triggered"));
 //
 //			Timer timer3 =
 //				theTimerThread.createTimer
 //					(new Message ("Timer 3 triggered"));
 //
 //			timer1.start (1000L, 1000L);
 //			timer2.start (5000L, 5000L);
 //			timer3.start (10000L);
 //			}
 //		catch (Throwable exc)
 //			{
 //			System.err.println ("edu.rit.util.TimerThread: Uncaught exception");
 //			exc.printStackTrace (System.err);
 //			}
 //		}
 }