/*
    * Copyright (c) 2003-2008 by Cosylab d. d.
    *
    * This file is part of Java-Common.
    *
    * Java-Common 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.
   *
   * Java-Common 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.
   *
   * You should have received a copy of the GNU General Public License
   * along with Java-Common.  If not, see <http://www.gnu.org/licenses/>.
   */
  
  package com.cosylab.util;
  
  import java.util.List;
  import java.util.Stack;
  
  
  /**
   * Scheduler implementation that prevents single tasks from locking up entire
   * scheduler. This implementation tries to use minimal number of threads to
   * execute given tasks.
   * 
   * <p>
   * Tasks are scheduled using a priority queue, sorted by next execution time.
   * Time is measured using wait method, so it is bound to be incorrect. This
   * implementation is not suitable for scheduling times below 10ms, but it
   * depends on platform (limits are about 50ms for Windows9x, 10ms for Windows
   * 2000/XP/NT and 1ms for Linux/Unix).<br>
   * Each task will run only once at any given time (if task is scheduled to be
   * executed every 10ms, but it takes 100ms to run, same task will not be
   * executed 10 times in between).<br>
   * If a task exceeds its next scheduled execution time while running, next
   * execution time will be assigned by adding
   * <code>SchedulerTask.getInterval()</code> after current task has completed.
   * </p>
   *
   * @author <a href="mailto:ales.pucelj@cosylab.com">Ales Pucelj</a>
   * @version $id$
   */
  public class Scheduler extends Thread
  {
  	private TaskEntry first;
  	private TaskEntry last;
  
  	/** List of threads executing tasks. */
  	private Stack runners = new Stack();
  
  	/** Flag indicating that Scheduler should stop. */
  	private volatile boolean done = false;
  
  	/** Minimum number of runner threads. */
  	private int minRunners = 1;
  	private int maxRunners = 0;
  
  	// closes tisk exparation
  	private long minNextTime;
  	private Object lock = new Object();
  	private final boolean debug = false;
  
  	/**
  	 * Thread that runs single task. These threads are automatically allocated
  	 * and stopped based on number of tasks that run simultaneously.
  	 */
  	private class SchedulerRunner extends Thread
  	{
  		/** Lock on which the thread waits until new task is assigned to it. */
  		private final Object lock = new Object();
  
  		/** Task to execute. */
  		private TaskEntry task;
  
  		/** Flag indicating this thread should stop. */
  		private volatile boolean done;
  
  		/**
  		 * Default constructor for ScheduleRunner.
  		 */
  		public SchedulerRunner()
  		{
  			done = false;
  			task = null;
  		}
  
  		/**
  		 * Assign a task to be executed. This is the task this thread will
  		 * execute. New tasks will not be accepted until current completes.
  		 *
  		 * @param task Task to execute.
  		 */
  		public void executeTask(TaskEntry task)
  		{
 			//setName("SchedulerRunner: running '" + task.getName() + "'");
 			this.task = task;
 
 			synchronized (lock) {
 				lock.notifyAll();
 			}
 		}
 
 		/**
 		 * Stop this thread. Will wait until current task completes.
 		 */
 		public void cancel()
 		{
 			done = true;
 
 			synchronized (lock) {
 				lock.notifyAll();
 			}
 		}
 
 		/**
 		 * Blocks until new task is assigned to this thread. Returns task that
 		 * was assigned.
 		 *
 		 * @return Task to execute
 		 *
 		 * @throws InterruptedException
 		 */
 		private TaskEntry getTask() throws InterruptedException
 		{
 			synchronized (lock) {
 				while (task == null) {
 					lock.wait();
 
 					if (done) {
 						return null;
 					}
 				}
 			}
 
 			return task;
 		}
 
 		/**
 		 * Loop that executes and runs tasks. This method will block on
 		 * getTask() until interrupted or task is assigned.
 		 *
 		 * @see java.lang.Runnable#run()
 		 */
 		public void run()
 		{
 			try {
 				while (!done) {
 					// Make a copy of task to prevent undefined behaviour
 					// in case new task is assigned while running current
 					TaskEntry t = getTask();
 
 					if (done) {
 						return;
 					}
 
 					long delta = 0;
 
 					if (debug) {
 						delta = System.currentTimeMillis() - t.nextTime;
 					}
 
 					t.run();
 					task = null;
 
 					if (!t.isCanceled()) {
 						if (debug) {
 							System.out.println("DELTA= " + delta + " DUTY= "
 							    + t.duty + " TASK= " + t.task);
 						}
 
 						returnTask(t);
 
 						// wake scheduler
 						synchronized (Scheduler.this.lock) {
 							Scheduler.this.lock.notifyAll();
 						}
 					} else {
 						if (debug) {
 							System.out.println("IN= "
 							    + (System.currentTimeMillis() - t.created)
 							    + " DUTY= " + t.duty + " TASK= " + t.task);
 						}
 					}
 
 					returnRunner(this);
 				}
 			} catch (InterruptedException e) {
 				// Do nothing since we exit the loop anyway.
 			}
 		}
 	}
 
 	/**
 	 * This is a wrapper arround the Task interface. It allows the Task
 	 * interface to be much simpler, since all scheduling related parameters
 	 * are stored here. For most methods it maps to the Task interface itself.
 	 */
 	private class TaskEntry implements Comparable
 	{
 		/** Next entry in linked list */
 		public TaskEntry next;
 
 		/** Next previous in linked list */
 		public TaskEntry previous;
 
 		// time of creation
 		private long created;
 
 		// time of creation
 		private long duty;
 
 		/**
 		 * Next time when this task is to be executed. Can be in the past,
 		 * indicating immediate execution.
 		 */
 		private long nextTime;
 
 		/** Actual task to execute. */
 		private SchedulerTask task;
 
 		/** Should this task be executed only once or repeated indefinitely. */
 		private boolean repeated;
 
 		/** Is this task to be canceled on next execution. */
 		private boolean canceled = false;
 
 		/**
 		 * Creates new TaskEntry, specifying task that will be executed
 		 * immediately and only once.
 		 *
 		 * @param t Task to schedule.
 		 */
 		public TaskEntry(SchedulerTask t)
 		{
 			this(t, 0, false);
 		}
 
 		/**
 		 * Creates new TaskEntry, specifying the task to be executed after a
 		 * given delay and whether this task should be repeated.
 		 *
 		 * @param t Task to schedule.
 		 * @param delay Delay before first execution.
 		 * @param isRepeated Should it be repeated.
 		 */
 		public TaskEntry(SchedulerTask t, long delay, boolean isRepeated)
 		{
 			task = t;
 			nextTime = System.currentTimeMillis() + delay;
 			repeated = isRepeated;
 			created = System.currentTimeMillis();
 		}
 
 		/**
 		 * Returns next time when this task should execute.
 		 *
 		 * @return Time in milliseconds.
 		 */
 		public long getNextTime()
 		{
 			return nextTime;
 		}
 
 		/**
 		 * Retunrs name of this task. Name is obtained from
 		 * <code>SchedulerTask</code> or set to 'anonymous' if null.
 		 *
 		 * @return Name of this task.
 		 */
 		public String getName()
 		{
 			String name = task.getTaskName();
 
 			if (name == null) {
 				name = "<anonymous>";
 			}
 
 			return name;
 		}
 
 		/**
 		 * Will this task be canceled before next execution. Non repeated tasks
 		 * return true after they have run once.
 		 *
 		 * @return True if the task should be canceled.
 		 */
 		public boolean isCanceled()
 		{
 			if (repeated) {
 				return task.isCanceled();
 			} else {
 				return canceled;
 			}
 		}
 
 		/**
 		 * Comparator implementation for use with priority queue. Compares
 		 * scheduled execution times.
 		 *
 		 * @see java.lang.Comparable#compareTo(java.lang.Object)
 		 */
 		public int compareTo(Object o)
 		{
 			long other = ((TaskEntry)o).getNextTime();
 
 			if (nextTime < other) {
 				return -1;
 			}
 
 			if (nextTime > other) {
 				return 1;
 			}
 
 			return 0;
 		}
 
 		/**
 		 * Executes the task and sets the new execution times. Also marks
 		 * non-repeated tasks for cancelation.
 		 */
 		public void run()
 		{
 			duty = System.currentTimeMillis();
 			task.run();
 			duty = System.currentTimeMillis() - duty;
 			canceled = true;
 			nextTime = System.currentTimeMillis() + task.getInterval();
 		}
 
 		/**
 		 * Name of the associated task.
 		 *
 		 * @see java.lang.Object#toString()
 		 */
 		public String toString()
 		{
 			return task.toString() + " " + nextTime;
 		}
 	}
 
 	/**
 	 * Creates new scheduler and starts it.
 	 */
 	public Scheduler()
 	{
 		this(3);
 	}
 
 	/**
 	 * Creates a new scheduler and specifies the minimum number of runner
 	 * threads alive, regardless the number of tasks.
 	 *
 	 * @param minimumRunners Number of threads.
 	 */
 	public Scheduler(int minimumRunners)
 	{
 		super();
 		minRunners = Math.max(1, minimumRunners);
 		setPriority(7);
 		start();
 
 		//timer= new Timer();
 	}
 	
 	public Scheduler(int min, int max) {
 		this(min);
 		maxRunners=max;
 	}
 
 	/**
 	 * Returns runner to the pool. If there are too many runners in the pool,
 	 * runner will be stopped.
 	 *
 	 * @param runner Runner thread to return to pool.
 	 */
 	protected void returnRunner(SchedulerRunner runner)
 	{
 		if (maxRunners>0) {
 			synchronized(runners) {
 				if ((runners == null) || (runners.size() >= maxRunners)) {
 					runner.cancel();
 				} else {
 					runners.push(runner);
 				}
 				runners.notify();
 			}
 		}else {
 		// runners can be null during shutdown, in which case, do no return to
 		// pool. 
 		if ((runners == null) || (runners.size() > minRunners)) {
 			runner.cancel();
 		} else {
 			runners.push(runner);
 		}
 		}
 	}
 
 	/**
 	 * Puts task back to the queue. If task was marked to be canceled, it will
 	 * be destroyed.
 	 *
 	 * @param task Task to return.
 	 */
 	protected synchronized void returnTask(TaskEntry task)
 	{
 		if (task.isCanceled()) {
 			return;
 		}
 
 
 //if (debug) System.out.println("RETURNED "+task);
 out: 
 		if (first == null) {
 			first = task;
 			first.previous = null;
 			first.next = null;
 			last = task;
 		} else {
 			if (task.nextTime >= last.nextTime) {
 				last.next = task;
 				task.previous = last;
 				last = task;
 			} else {
 				TaskEntry t = last;
 
 				while (t.previous != null) {
 					if (task.nextTime >= t.previous.nextTime) {
 						t.previous.next = task;
 						task.previous = t.previous;
 
 						t.previous = task;
 						task.next = t;
 
 						break out;
 					} else {
 						t = t.previous;
 					}
 				}
 
 				first = task;
 				first.previous = null;
 				first.next = t;
 				t.previous = first;
 			}
 		}
 
 		/*TaskEntry t = first;
 
 		while(t!=null) {
 		    System.out.println("> "+t);
 		    t= t.next;
 		}*/
 		minNextTime = first.nextTime;
 	}
 
 	/**
 	 * Schedule new task for immediate single time execution.
 	 *
 	 * @param task Task to schedule.
 	 */
 	public void schedule(SchedulerTask task)
 	{
 		schedule(task, 0, false);
 	}
 
 	/**
 	 * Schedule task for delayed execution.
 	 *
 	 * @param task Task to schedule
 	 * @param delay Delay before initial execution.
 	 * @param repeated Should this task be repeated or executed only once.
 	 */
 	public void schedule(SchedulerTask task, long delay, boolean repeated)
 	{
 		if (task == null) {
 			return;
 		}
 
 
 		/*        class Task extends TimerTask {
 		            private boolean repeated=false;
 		            private SchedulerTask task;
 		            private long created;
 		            private long duty;
 
 		            public Task(SchedulerTask task, boolean repeated) {
 		                created= System.currentTimeMillis();
 		                this.task=task;
 		                this.repeated=repeated;
 		            }
 		            public void run() {
 		                if (!repeated) {
 		                    cancel();
 		                }
 		                duty= System.currentTimeMillis();
 		                task.run();
 		                duty= System.currentTimeMillis()-duty;
 
 		                if (repeated) {
 		                    System.out.println("DELTA= "
 		                        + (System.currentTimeMillis() - scheduledExecutionTime())
 		                        + " DUTY= " + duty + " TASK= " + task);
 		                } else {
 		                    System.out.println("IN= "
 		                        + (System.currentTimeMillis() - created)
 		                        + " DUTY= " + duty + " TASK= " + task);
 		                }
 
 		            }
 
 		        }
 
 		        Task t= new Task(task,repeated);
 
 		        if (repeated){
 		            timer.scheduleAtFixedRate(t,delay,task.getInterval());
 		        } else {
 		            timer.schedule(t,delay);
 		        }
 		*/
 		TaskEntry entry = new TaskEntry(task, delay, repeated);
 
 		returnTask(entry);
 
 		// wake scheduler
 		synchronized (lock) {
 			lock.notifyAll();
 		}
 	}
 
 	/**
 	 * Gets new thread that executes tasks. If a task is available from the
 	 * pool, this instance will be used, otherwise new instance will be
 	 * created.
 	 *
 	 * @return Instance of task runner.
 	 */
 	private SchedulerRunner getRunner()
 	{
 		if (maxRunners > 0) {
 			synchronized (runners) {
 				while (runners.size() >= maxRunners) {
 					try {
 						runners.wait(60000);
 					} catch (Exception e) {
 						// IGNORE
 					}
 				}
 
 				if (runners.isEmpty()) {
 					SchedulerRunner sr = new SchedulerRunner();
 					sr.start();
 
 					return sr;
 				} else {
 					return (SchedulerRunner)runners.pop();
 				}
 			}
 		}
 
 		if (runners.isEmpty()) {
 			SchedulerRunner sr = new SchedulerRunner();
 			sr.start();
 
 			return sr;
 		} else {
 			return (SchedulerRunner)runners.pop();
 		}
 	}
 
 	/**
 	 * Main loop that executes tasks.
 	 *
 	 * @see java.lang.Runnable#run()
 	 */
 	public void run()
 	{
 		long delta;
 
 		try {
 			while (!done) {
 				while (first == null && !done) {
 					try {
 						synchronized (lock) {
 							lock.wait();
 						}
 					} catch (InterruptedException e) {
 					}
 				}
 
 				if (done) {
 					return;
 				}
 
 				delta = minNextTime - System.currentTimeMillis();
 
 				//System.out.println("delta "+delta);
 				// Wait until next task is due or we are interrupted
 				// by new task being added to the queue.
 				if (delta > 0) {
 					synchronized (lock) {
 						//System.out.println("delta "+delta);
 						lock.wait(delta);
 					}
 				} else {
 					// Do not execute canceled tasks.
 					TaskEntry task = removeTask();
 
 					if (!done && task != null && !task.isCanceled()) {
 						getRunner().executeTask(task);
 					}
 				}
 			}
 		} catch (InterruptedException e) {
 			// Ignore, since we quit anyway.
 		}
 	}
 
 	/**
 	 * Cancels all tasks, runners and stops the scheduler.
 	 */
 	public void cancel()
 	{
 		done = true;
 
 		// Stop this thread.
 		synchronized (lock) {
 			lock.notifyAll();
 		}
 
 		// Clear runners list, so that any runners still active will not 
 		// get returned to the list.
 		List r = runners;
 		runners = null;
 
 		while (!r.isEmpty()) {
 			((SchedulerRunner)r.get(0)).cancel();
 			r.remove(0);
 		}
 
 		/**
 		 * Clear all defined tasks.
 		 */
 		synchronized (this) {
 			first = null;
 		}
 	}
 
 	private synchronized TaskEntry removeTask()
 	{
 		if (first == null) {
 			return null;
 		}
 
 		TaskEntry t = first;
 		first = t.next;
 
 		if (first == null) {
 			last = null;
 			minNextTime = 0;
 		} else {
 			first.previous = null;
 			minNextTime = first.nextTime;
 		}
 
 		t.next = null;
 		t.previous = null;
 
 		/*TaskEntry t1 = first;
 
 		System.out.println("REM "+t);
 		while(t1!=null) {
 		    System.out.println("> "+t1);
 		    t1= t1.next;
 		}*/
 		return t;
 	}
 }
 
 /* __oOo__ */