Timer


1   /*
2    * @(#)Timer.java   1.17 04/04/12
3    *
4    * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5    * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6    */
7   
8   package java.util;
9   import java.util.Date  ;
10  
11  /**
12   * A facility for threads to schedule tasks for future execution in a
13   * background thread.  Tasks may be scheduled for one-time execution, or for
14   * repeated execution at regular intervals.
15   *
16   * <p>Corresponding to each <tt>Timer</tt> object is a single background
17   * thread that is used to execute all of the timer's tasks, sequentially.
18   * Timer tasks should complete quickly.  If a timer task takes excessive time
19   * to complete, it "hogs" the timer's task execution thread.  This can, in
20   * turn, delay the execution of subsequent tasks, which may "bunch up" and
21   * execute in rapid succession when (and if) the offending task finally
22   * completes.
23   *
24   * <p>After the last live reference to a <tt>Timer</tt> object goes away
25   * <i>and</i> all outstanding tasks have completed execution, the timer's task
26   * execution thread terminates gracefully (and becomes subject to garbage
27   * collection).  However, this can take arbitrarily long to occur.  By
28   * default, the task execution thread does not run as a <i>daemon thread</i>,
29   * so it is capable of keeping an application from terminating.  If a caller
30   * wants to terminate a timer's task execution thread rapidly, the caller
31   * should invoke the timer's <tt>cancel</tt> method.
32   *
33   * <p>If the timer's task execution thread terminates unexpectedly, for
34   * example, because its <tt>stop</tt> method is invoked, any further
35   * attempt to schedule a task on the timer will result in an
36   * <tt>IllegalStateException</tt>, as if the timer's <tt>cancel</tt>
37   * method had been invoked.
38   *
39   * <p>This class is thread-safe: multiple threads can share a single
40   * <tt>Timer</tt> object without the need for external synchronization.
41   *
42   * <p>This class does <i>not</i> offer real-time guarantees: it schedules
43   * tasks using the <tt>Object.wait(long)</tt> method.
44   *
45   * <p>Implementation note: This class scales to large numbers of concurrently
46   * scheduled tasks (thousands should present no problem).  Internally,
47   * it uses a binary heap to represent its task queue, so the cost to schedule
48   * a task is O(log n), where n is the number of concurrently scheduled tasks.
49   *
50   * <p>Implementation note: All constructors start a timer thread.
51   *
52   * @author  Josh Bloch
53   * @version 1.17, 04/12/04
54   * @see     TimerTask
55   * @see     Object#wait(long)
56   * @since   1.3
57   */
58  
59  public class Timer {
60      /**
61       * The timer task queue.  This data structure is shared with the timer
62       * thread.  The timer produces tasks, via its various schedule calls,
63       * and the timer thread consumes, executing timer tasks as appropriate,
64       * and removing them from the queue when they're obsolete.
65       */
66      private TaskQueue queue = new TaskQueue();
67  
68      /**
69       * The timer thread.
70       */
71      private TimerThread thread = new TimerThread(queue);
72  
73      /**
74       * This object causes the timer's task execution thread to exit
75       * gracefully when there are no live references to the Timer object and no
76       * tasks in the timer queue.  It is used in preference to a finalizer on
77       * Timer as such a finalizer would be susceptible to a subclass's
78       * finalizer forgetting to call it.
79       */
80      private Object   threadReaper = new Object  () {
81          protected void finalize() throws Throwable   {
82              synchronized(queue) {
83                  thread.newTasksMayBeScheduled = false;
84                  queue.notify(); // In case queue is empty.
85              }
86          }
87      };
88  
89      /**
90       * This ID is used to generate thread names.  (It could be replaced
91       * by an AtomicInteger as soon as they become available.)
92       */
93      private static int nextSerialNumber = 0;
94      private static synchronized int serialNumber() {
95          return nextSerialNumber++;
96      }
97  
98      /**
99       * Creates a new timer.  The associated thread does <i>not</i> run as
100      * a daemon.
101      *
102      * @see Thread
103      * @see #cancel()
104      */
105     public Timer() {
106         this("Timer-" + serialNumber());
107     }
108 
109     /**
110      * Creates a new timer whose associated thread may be specified to 
111      * run as a daemon.  A daemon thread is called for if the timer will
112      * be used to schedule repeating "maintenance activities", which must
113      * be performed as long as the application is running, but should not
114      * prolong the lifetime of the application.
115      *
116      * @param isDaemon true if the associated thread should run as a daemon.
117      *
118      * @see Thread
119      * @see #cancel()
120      */
121     public Timer(boolean isDaemon) {
122         this("Timer-" + serialNumber(), isDaemon);
123     }
124 
125     /**
126      * Creates a new timer whose associated thread has the specified name.
127      * The associated thread does <i>not</i> run as a daemon.
128      *
129      * @param name the name of the associated thread
130      * @throws NullPointerException if name is null
131      * @see Thread#getName()
132      * @see Thread#isDaemon()
133      * @since 1.5
134      */
135     public Timer(String   name) {
136         thread.setName(name);
137         thread.start();
138     }
139  
140     /**
141      * Creates a new timer whose associated thread has the specified name,
142      * and may be specified to run as a daemon.
143      *
144      * @param name the name of the associated thread
145      * @param isDaemon true if the associated thread should run as a daemon
146      * @throws NullPointerException if name is null
147      * @see Thread#getName()
148      * @see Thread#isDaemon()
149      * @since 1.5
150      */
151     public Timer(String   name, boolean isDaemon) {
152         thread.setName(name);
153         thread.setDaemon(isDaemon);
154         thread.start();
155     }
156 
157     /**
158      * Schedules the specified task for execution after the specified delay.
159      *
160      * @param task  task to be scheduled.
161      * @param delay delay in milliseconds before task is to be executed.
162      * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
163      *         <tt>delay + System.currentTimeMillis()</tt> is negative.
164      * @throws IllegalStateException if task was already scheduled or
165      *         cancelled, or timer was cancelled.
166      */
167     public void schedule(TimerTask   task, long delay) {
168         if (delay < 0)
169             throw new IllegalArgumentException  ("Negative delay.");
170         sched(task, System.currentTimeMillis()+delay, 0);
171     }
172 
173     /**
174      * Schedules the specified task for execution at the specified time.  If
175      * the time is in the past, the task is scheduled for immediate execution.
176      *
177      * @param task task to be scheduled.
178      * @param time time at which task is to be executed.
179      * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
180      * @throws IllegalStateException if task was already scheduled or
181      *         cancelled, timer was cancelled, or timer thread terminated.
182      */
183     public void schedule(TimerTask   task, Date   time) {
184         sched(task, time.getTime(), 0);
185     }
186 
187     /**
188      * Schedules the specified task for repeated <i>fixed-delay execution</i>,
189      * beginning after the specified delay.  Subsequent executions take place
190      * at approximately regular intervals separated by the specified period.
191      *
192      * <p>In fixed-delay execution, each execution is scheduled relative to
193      * the actual execution time of the previous execution.  If an execution
194      * is delayed for any reason (such as garbage collection or other
195      * background activity), subsequent executions will be delayed as well.
196      * In the long run, the frequency of execution will generally be slightly
197      * lower than the reciprocal of the specified period (assuming the system
198      * clock underlying <tt>Object.wait(long)</tt> is accurate).
199      *
200      * <p>Fixed-delay execution is appropriate for recurring activities
201      * that require "smoothness."  In other words, it is appropriate for
202      * activities where it is more important to keep the frequency accurate
203      * in the short run than in the long run.  This includes most animation
204      * tasks, such as blinking a cursor at regular intervals.  It also includes
205      * tasks wherein regular activity is performed in response to human
206      * input, such as automatically repeating a character as long as a key
207      * is held down.
208      *
209      * @param task   task to be scheduled.
210      * @param delay  delay in milliseconds before task is to be executed.
211      * @param period time in milliseconds between successive task executions.
212      * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
213      *         <tt>delay + System.currentTimeMillis()</tt> is negative.
214      * @throws IllegalStateException if task was already scheduled or
215      *         cancelled, timer was cancelled, or timer thread terminated.
216      */
217     public void schedule(TimerTask   task, long delay, long period) {
218         if (delay < 0)
219             throw new IllegalArgumentException  ("Negative delay.");
220         if (period <= 0)
221             throw new IllegalArgumentException  ("Non-positive period.");
222         sched(task, System.currentTimeMillis()+delay, -period);
223     }
224 
225     /**
226      * Schedules the specified task for repeated <i>fixed-delay execution</i>,
227      * beginning at the specified time. Subsequent executions take place at
228      * approximately regular intervals, separated by the specified period.
229      *
230      * <p>In fixed-delay execution, each execution is scheduled relative to
231      * the actual execution time of the previous execution.  If an execution
232      * is delayed for any reason (such as garbage collection or other
233      * background activity), subsequent executions will be delayed as well.
234      * In the long run, the frequency of execution will generally be slightly
235      * lower than the reciprocal of the specified period (assuming the system
236      * clock underlying <tt>Object.wait(long)</tt> is accurate).
237      *
238      * <p>Fixed-delay execution is appropriate for recurring activities
239      * that require "smoothness."  In other words, it is appropriate for
240      * activities where it is more important to keep the frequency accurate
241      * in the short run than in the long run.  This includes most animation
242      * tasks, such as blinking a cursor at regular intervals.  It also includes
243      * tasks wherein regular activity is performed in response to human
244      * input, such as automatically repeating a character as long as a key
245      * is held down.
246      *
247      * @param task   task to be scheduled.
248      * @param firstTime First time at which task is to be executed.
249      * @param period time in milliseconds between successive task executions.
250      * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
251      * @throws IllegalStateException if task was already scheduled or
252      *         cancelled, timer was cancelled, or timer thread terminated.
253      */
254     public void schedule(TimerTask   task, Date   firstTime, long period) {
255         if (period <= 0)
256             throw new IllegalArgumentException  ("Non-positive period.");
257         sched(task, firstTime.getTime(), -period);
258     }
259 
260     /**
261      * Schedules the specified task for repeated <i>fixed-rate execution</i>,
262      * beginning after the specified delay.  Subsequent executions take place
263      * at approximately regular intervals, separated by the specified period.
264      *
265      * <p>In fixed-rate execution, each execution is scheduled relative to the
266      * scheduled execution time of the initial execution.  If an execution is
267      * delayed for any reason (such as garbage collection or other background
268      * activity), two or more executions will occur in rapid succession to
269      * "catch up."  In the long run, the frequency of execution will be
270      * exactly the reciprocal of the specified period (assuming the system
271      * clock underlying <tt>Object.wait(long)</tt> is accurate).
272      *
273      * <p>Fixed-rate execution is appropriate for recurring activities that
274      * are sensitive to <i>absolute</i> time, such as ringing a chime every
275      * hour on the hour, or running scheduled maintenance every day at a
276      * particular time.  It is also appropriate for recurring activities
277      * where the total time to perform a fixed number of executions is
278      * important, such as a countdown timer that ticks once every second for
279      * ten seconds.  Finally, fixed-rate execution is appropriate for
280      * scheduling multiple repeating timer tasks that must remain synchronized
281      * with respect to one another.
282      *
283      * @param task   task to be scheduled.
284      * @param delay  delay in milliseconds before task is to be executed.
285      * @param period time in milliseconds between successive task executions.
286      * @throws IllegalArgumentException if <tt>delay</tt> is negative, or
287      *         <tt>delay + System.currentTimeMillis()</tt> is negative.
288      * @throws IllegalStateException if task was already scheduled or
289      *         cancelled, timer was cancelled, or timer thread terminated.
290      */
291     public void scheduleAtFixedRate(TimerTask   task, long delay, long period) {
292         if (delay < 0)
293             throw new IllegalArgumentException  ("Negative delay.");
294         if (period <= 0)
295             throw new IllegalArgumentException  ("Non-positive period.");
296         sched(task, System.currentTimeMillis()+delay, period);
297     }
298 
299     /**
300      * Schedules the specified task for repeated <i>fixed-rate execution</i>,
301      * beginning at the specified time. Subsequent executions take place at
302      * approximately regular intervals, separated by the specified period.
303      *
304      * <p>In fixed-rate execution, each execution is scheduled relative to the
305      * scheduled execution time of the initial execution.  If an execution is
306      * delayed for any reason (such as garbage collection or other background
307      * activity), two or more executions will occur in rapid succession to
308      * "catch up."  In the long run, the frequency of execution will be
309      * exactly the reciprocal of the specified period (assuming the system
310      * clock underlying <tt>Object.wait(long)</tt> is accurate).
311      *
312      * <p>Fixed-rate execution is appropriate for recurring activities that
313      * are sensitive to <i>absolute</i> time, such as ringing a chime every
314      * hour on the hour, or running scheduled maintenance every day at a
315      * particular time.  It is also appropriate for recurring activities
316      * where the total time to perform a fixed number of executions is
317      * important, such as a countdown timer that ticks once every second for
318      * ten seconds.  Finally, fixed-rate execution is appropriate for
319      * scheduling multiple repeating timer tasks that must remain synchronized
320      * with respect to one another.
321      *
322      * @param task   task to be scheduled.
323      * @param firstTime First time at which task is to be executed.
324      * @param period time in milliseconds between successive task executions.
325      * @throws IllegalArgumentException if <tt>time.getTime()</tt> is negative.
326      * @throws IllegalStateException if task was already scheduled or
327      *         cancelled, timer was cancelled, or timer thread terminated.
328      */
329     public void scheduleAtFixedRate(TimerTask   task, Date   firstTime,
330                                     long period) {
331         if (period <= 0)
332             throw new IllegalArgumentException  ("Non-positive period.");
333         sched(task, firstTime.getTime(), period);
334     }
335 
336     /**
337      * Schedule the specified timer task for execution at the specified
338      * time with the specified period, in milliseconds.  If period is
339      * positive, the task is scheduled for repeated execution; if period is
340      * zero, the task is scheduled for one-time execution. Time is specified
341      * in Date.getTime() format.  This method checks timer state, task state,
342      * and initial execution time, but not period.
343      *
344      * @throws IllegalArgumentException if <tt>time()</tt> is negative.
345      * @throws IllegalStateException if task was already scheduled or
346      *         cancelled, timer was cancelled, or timer thread terminated.
347      */
348     private void sched(TimerTask   task, long time, long period) {
349         if (time < 0)
350             throw new IllegalArgumentException  ("Illegal execution time.");
351         
352         synchronized(queue) {
353             if (!thread.newTasksMayBeScheduled)
354                 throw new IllegalStateException  ("Timer already cancelled.");
355 
356             synchronized(task.lock) {
357                 if (task.state != TimerTask.VIRGIN)
358                     throw new IllegalStateException  (
359                         "Task already scheduled or cancelled");
360                 task.nextExecutionTime = time;
361                 task.period = period;
362                 task.state = TimerTask.SCHEDULED;
363             }
364 
365             queue.add(task);
366             if (queue.getMin() == task)
367                 queue.notify();
368         }
369     }
370 
371     /**
372      * Terminates this timer, discarding any currently scheduled tasks.
373      * Does not interfere with a currently executing task (if it exists).
374      * Once a timer has been terminated, its execution thread terminates
375      * gracefully, and no more tasks may be scheduled on it.
376      *
377      * <p>Note that calling this method from within the run method of a
378      * timer task that was invoked by this timer absolutely guarantees that
379      * the ongoing task execution is the last task execution that will ever
380      * be performed by this timer.
381      *
382      * <p>This method may be called repeatedly; the second and subsequent 
383      * calls have no effect.
384      */
385     public void cancel() {
386         synchronized(queue) {
387             thread.newTasksMayBeScheduled = false;
388             queue.clear();
389             queue.notify();  // In case queue was already empty.
390         }
391     }
392 
393     /**
394      * Removes all cancelled tasks from this timer's task queue.  <i>Calling
395      * this method has no effect on the behavior of the timer</i>, but
396      * eliminates the references to the cancelled tasks from the queue.
397      * If there are no external references to these tasks, they become
398      * eligible for garbage collection.
399      *
400      * <p>Most programs will have no need to call this method.
401      * It is designed for use by the rare application that cancels a large
402      * number of tasks.  Calling this method trades time for space: the
403      * runtime of the method may be proportional to n + c log n, where n
404      * is the number of tasks in the queue and c is the number of cancelled
405      * tasks.
406      *
407      * <p>Note that it is permissible to call this method from within a
408      * a task scheduled on this timer.
409      *
410      * @return the number of tasks removed from the queue.
411      * @since 1.5
412      */
413      public int purge() {
414          int result = 0;
415 
416          synchronized(queue) {
417              for (int i = queue.size(); i > 0; i--) {
418                  if (queue.get(i).state == TimerTask.CANCELLED) {
419                      queue.quickRemove(i);
420                      result++;
421                  }
422              }
423 
424              if (result != 0)
425                  queue.heapify();
426          }
427 
428          return result;
429      }
430 }
431 
432 /**
433  * This "helper class" implements the timer's task execution thread, which
434  * waits for tasks on the timer queue, executions them when they fire,
435  * reschedules repeating tasks, and removes cancelled tasks and spent
436  * non-repeating tasks from the queue.
437  */
438 class TimerThread extends Thread   {
439     /**
440      * This flag is set to false by the reaper to inform us that there
441      * are no more live references to our Timer object.  Once this flag
442      * is true and there are no more tasks in our queue, there is no
443      * work left for us to do, so we terminate gracefully.  Note that
444      * this field is protected by queue's monitor!
445      */
446     boolean newTasksMayBeScheduled = true;
447 
448     /**
449      * Our Timer's queue.  We store this reference in preference to
450      * a reference to the Timer so the reference graph remains acyclic.
451      * Otherwise, the Timer would never be garbage-collected and this
452      * thread would never go away.
453      */
454     private TaskQueue queue;
455 
456     TimerThread(TaskQueue queue) {
457         this.queue = queue;
458     }
459 
460     public void run() {
461         try {
462             mainLoop();
463         } finally {
464             // Someone killed this Thread, behave as if Timer cancelled
465             synchronized(queue) {
466                 newTasksMayBeScheduled = false;
467                 queue.clear();  // Eliminate obsolete references
468             }
469         }
470     }
471 
472     /**
473      * The main timer loop.  (See class comment.)
474      */
475     private void mainLoop() {
476         while (true) {
477             try {
478                 TimerTask   task;
479                 boolean taskFired;
480                 synchronized(queue) {
481                     // Wait for queue to become non-empty
482                     while (queue.isEmpty() && newTasksMayBeScheduled)
483                         queue.wait();
484                     if (queue.isEmpty())
485                         break; // Queue is empty and will forever remain; die
486 
487                     // Queue nonempty; look at first evt and do the right thing
488                     long currentTime, executionTime;
489                     task = queue.getMin();
490                     synchronized(task.lock) {
491                         if (task.state == TimerTask.CANCELLED) {
492                             queue.removeMin();
493                             continue;  // No action required, poll queue again
494                         }
495                         currentTime = System.currentTimeMillis();
496                         executionTime = task.nextExecutionTime;
497                         if (taskFired = (executionTime<=currentTime)) {
498                             if (task.period == 0) { // Non-repeating, remove
499                                 queue.removeMin();
500                                 task.state = TimerTask.EXECUTED;
501                             } else { // Repeating task, reschedule
502                                 queue.rescheduleMin(
503                                   task.period<0 ? currentTime   - task.period
504                                                 : executionTime + task.period);
505                             }
506                         }
507                     }
508                     if (!taskFired) // Task hasn't yet fired; wait
509                         queue.wait(executionTime - currentTime);
510                 }
511                 if (taskFired)  // Task fired; run it, holding no locks
512                     task.run();
513             } catch(InterruptedException   e) {
514             }
515         }
516     }
517 }
518 
519 /**
520  * This class represents a timer task queue: a priority queue of TimerTasks,
521  * ordered on nextExecutionTime.  Each Timer object has one of these, which it
522  * shares with its TimerThread.  Internally this class uses a heap, which
523  * offers log(n) performance for the add, removeMin and rescheduleMin
524  * operations, and constant time performance for the getMin operation.
525  */
526 class TaskQueue {
527     /**
528      * Priority queue represented as a balanced binary heap: the two children
529      * of queue[n] are queue[2*n] and queue[2*n+1].  The priority queue is
530      * ordered on the nextExecutionTime field: The TimerTask with the lowest
531      * nextExecutionTime is in queue[1] (assuming the queue is nonempty).  For
532      * each node n in the heap, and each descendant of n, d,
533      * n.nextExecutionTime <= d.nextExecutionTime. 
534      */
535     private TimerTask  [] queue = new TimerTask  [128];
536 
537     /**
538      * The number of tasks in the priority queue.  (The tasks are stored in
539      * queue[1] up to queue[size]).
540      */
541     private int size = 0;
542 
543     /**
544      * Returns the number of tasks currently on the queue.
545      */
546     int size() {
547         return size;
548     }
549 
550     /**
551      * Adds a new task to the priority queue.
552      */
553     void add(TimerTask   task) {
554         // Grow backing store if necessary
555         if (++size == queue.length) {
556             TimerTask  [] newQueue = new TimerTask  [2*queue.length];
557             System.arraycopy(queue, 0, newQueue, 0, size);
558             queue = newQueue;
559         }
560 
561         queue[size] = task;
562         fixUp(size);
563     }
564 
565     /**
566      * Return the "head task" of the priority queue.  (The head task is an
567      * task with the lowest nextExecutionTime.)
568      */
569     TimerTask   getMin() {
570         return queue[1];
571     }
572 
573     /**
574      * Return the ith task in the priority queue, where i ranges from 1 (the
575      * head task, which is returned by getMin) to the number of tasks on the
576      * queue, inclusive.
577      */
578     TimerTask   get(int i) {
579         return queue[i];
580     }
581 
582     /**
583      * Remove the head task from the priority queue.
584      */
585     void removeMin() {
586         queue[1] = queue[size];
587         queue[size--] = null;  // Drop extra reference to prevent memory leak
588         fixDown(1);
589     }
590 
591     /**
592      * Removes the ith element from queue without regard for maintaining
593      * the heap invariant.  Recall that queue is one-based, so
594      * 1 <= i <= size.
595      */
596     void quickRemove(int i) {
597         assert i <= size;
598 
599         queue[i] = queue[size];
600         queue[size--] = null;  // Drop extra ref to prevent memory leak
601     }
602 
603     /**
604      * Sets the nextExecutionTime associated with the head task to the 
605      * specified value, and adjusts priority queue accordingly.
606      */
607     void rescheduleMin(long newTime) {
608         queue[1].nextExecutionTime = newTime;
609         fixDown(1);
610     }
611 
612     /**
613      * Returns true if the priority queue contains no elements.
614      */
615     boolean isEmpty() {
616         return size==0;
617     }
618 
619     /**
620      * Removes all elements from the priority queue.
621      */
622     void clear() {
623         // Null out task references to prevent memory leak
624         for (int i=1; i<=size; i++)
625             queue[i] = null;
626 
627         size = 0;
628     }
629 
630     /**
631      * Establishes the heap invariant (described above) assuming the heap
632      * satisfies the invariant except possibly for the leaf-node indexed by k
633      * (which may have a nextExecutionTime less than its parent's).
634      *
635      * This method functions by "promoting" queue[k] up the hierarchy
636      * (by swapping it with its parent) repeatedly until queue[k]'s
637      * nextExecutionTime is greater than or equal to that of its parent.
638      */
639     private void fixUp(int k) {
640         while (k > 1) {
641             int j = k >> 1;
642             if (queue[j].nextExecutionTime <= queue[k].nextExecutionTime)
643                 break;
644             TimerTask   tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
645             k = j;
646         }
647     }
648 
649     /**
650      * Establishes the heap invariant (described above) in the subtree
651      * rooted at k, which is assumed to satisfy the heap invariant except
652      * possibly for node k itself (which may have a nextExecutionTime greater
653      * than its children's).
654      *
655      * This method functions by "demoting" queue[k] down the hierarchy
656      * (by swapping it with its smaller child) repeatedly until queue[k]'s
657      * nextExecutionTime is less than or equal to those of its children.
658      */
659     private void fixDown(int k) {
660         int j;
661         while ((j = k << 1) <= size && j > 0) {
662             if (j < size &&
663                 queue[j].nextExecutionTime > queue[j+1].nextExecutionTime)
664                 j++; // j indexes smallest kid
665             if (queue[k].nextExecutionTime <= queue[j].nextExecutionTime)
666                 break;
667             TimerTask   tmp = queue[j];  queue[j] = queue[k]; queue[k] = tmp;
668             k = j;
669         }
670     }
671 
672     /**
673      * Establishes the heap invariant (described above) in the entire tree,
674      * assuming nothing about the order of the elements prior to the call.
675      */
676     void heapify() {
677         for (int i = size/2; i >= 1; i--)
678             fixDown(i);
679     }
680 }
681
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags