[cvs] / jsr166 / src / main / java / util / PriorityQueue.java Repository:
ViewVC logotype

Diff of /jsr166/src/main/java/util/PriorityQueue.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.6, Mon Jun 23 02:26:15 2003 UTC revision 1.7, Tue Jun 24 14:34:30 2003 UTC
# Line 11  Line 11 
11   * elements are tied for least value, no guarantees are made as to   * elements are tied for least value, no guarantees are made as to
12   * which of these elements is returned.   * which of these elements is returned.
13   *   *
14   * <p>A priority queue has a <i>capacity</i>.  The capacity is the size of   * <p>A priority queue has a <i>capacity</i>.  The capacity is the
15   * the array used internally to store the elements on the queue.  It is always at least   * size of the array used internally to store the elements on the
16   * as large as the queue size.  As elements are added to a priority queue,   * queue.  It is always at least as large as the queue size.  As
17   * its capacity grows automatically.  The details of the growth policy are not   * elements are added to a priority queue, its capacity grows
18   * specified.   * automatically.  The details of the growth policy are not specified.
19   *   *
20   *<p>Implementation note: this implementation provides O(log(n)) time for   *<p>Implementation note: this implementation provides O(log(n)) time
21   * the insertion methods (<tt>offer</tt>, <tt>poll</tt>, <tt>remove()</tt> and <tt>add</tt>)   *for the insertion methods (<tt>offer</tt>, <tt>poll</tt>,
22   * methods; linear time for the <tt>remove(Object)</tt> and   *<tt>remove()</tt> and <tt>add</tt>) methods; linear time for the
23   * <tt>contains(Object)</tt> methods; and constant time for the retrieval methods (<tt>peek</tt>,   *<tt>remove(Object)</tt> and <tt>contains(Object)</tt> methods; and
24     *constant time for the retrieval methods (<tt>peek</tt>,
25   * <tt>element</tt>, and <tt>size</tt>).   * <tt>element</tt>, and <tt>size</tt>).
26   *   *
27   * <p>This class is a member of the   * <p>This class is a member of the
28   * <a href="{@docRoot}/../guide/collections/index.html">   * <a href="{@docRoot}/../guide/collections/index.html">
29   * Java Collections Framework</a>.   * Java Collections Framework</a>.
30     * @since 1.5
31     * @author Josh Bloch
32   */   */
33  public class PriorityQueue<E> extends AbstractQueue<E>  public class PriorityQueue<E> extends AbstractQueue<E>
34                                implements Queue<E>                                implements Queue<E> {
 {  
35      private static final int DEFAULT_INITIAL_CAPACITY = 11;      private static final int DEFAULT_INITIAL_CAPACITY = 11;
36    
37      /**      /**
# Line 65  Line 67 
67      private transient int modCount = 0;      private transient int modCount = 0;
68    
69      /**      /**
70       * Create a new priority queue with the default initial capacity (11)       * Create a new priority queue with the default initial capacity
71       * that orders its elements according to their natural ordering (using <tt>Comparable</tt>.)       * (11) that orders its elements according to their natural
72         * ordering (using <tt>Comparable</tt>.)
73       */       */
74      public PriorityQueue() {      public PriorityQueue() {
75          this(DEFAULT_INITIAL_CAPACITY);          this(DEFAULT_INITIAL_CAPACITY);
# Line 74  Line 77 
77    
78      /**      /**
79       * Create a new priority queue with the specified initial capacity       * Create a new priority queue with the specified initial capacity
80       * that orders its elements according to their natural ordering (using <tt>Comparable</tt>.)       * that orders its elements according to their natural ordering
81         * (using <tt>Comparable</tt>.)
82       *       *
83       * @param initialCapacity the initial capacity for this priority queue.       * @param initialCapacity the initial capacity for this priority queue.
84       */       */
# Line 141  Line 145 
145      // Queue Methods      // Queue Methods
146    
147      /**      /**
148       * Remove and return the minimal element from this priority queue if       * Remove and return the minimal element from this priority queue
149       * it contains one or more elements, otherwise return <tt>null</tt>.  The term       * if it contains one or more elements, otherwise return
150       * <i>minimal</i> is defined according to this priority queue's order.       * <tt>null</tt>.  The term <i>minimal</i> is defined according to
151         * this priority queue's order.
152       *       *
153       * @return the minimal element from this priority queue if it contains       * @return the minimal element from this priority queue if it contains
154       *         one or more elements, otherwise <tt>null</tt>.       *         one or more elements, otherwise <tt>null</tt>.
# Line 155  Line 160 
160      }      }
161    
162      /**      /**
163       * Return, but do not remove, the minimal element from the priority queue,       * Return, but do not remove, the minimal element from the
164       * or return <tt>null</tt> if the queue is empty.  The term <i>minimal</i> is       * priority queue, or return <tt>null</tt> if the queue is empty.
165       * defined according to this priority queue's order.  This method returns       * The term <i>minimal</i> is defined according to this priority
166       * the same object reference that would be returned by by the       * queue's order.  This method returns the same object reference
167       * <tt>poll</tt> method.  The two methods differ in that this method       * that would be returned by by the <tt>poll</tt> method.  The two
168       * does not remove the element from the priority queue.       * methods differ in that this method does not remove the element
169         * from the priority queue.
170       *       *
171       * @return the minimal element from this priority queue if it contains       * @return the minimal element from this priority queue if it contains
172       *         one or more elements, otherwise <tt>null</tt>.       *         one or more elements, otherwise <tt>null</tt>.
# Line 177  Line 183 
183       * specified element (or equivalently, if this collection changed as a       * specified element (or equivalently, if this collection changed as a
184       * result of the call).       * result of the call).
185       *       *
186       * @param element the element to be removed from this collection, if present.       * @param element the element to be removed from this collection,
187         * if present.
188       * @return <tt>true</tt> if this collection changed as a result of the       * @return <tt>true</tt> if this collection changed as a result of the
189       *         call       *         call
190       * @throws ClassCastException if the specified element cannot be compared       * @throws ClassCastException if the specified element cannot be compared
# Line 224  Line 231 
231           * Index (into queue array) of element to be returned by           * Index (into queue array) of element to be returned by
232           * subsequent call to next.           * subsequent call to next.
233           */           */
234          int cursor = 1;          private int cursor = 1;
235    
236          /**          /**
237           * Index of element returned by most recent call to next or           * Index of element returned by most recent call to next or
238           * previous.  Reset to 0 if this element is deleted by a call           * previous.  Reset to 0 if this element is deleted by a call
239           * to remove.           * to remove.
240           */           */
241          int lastRet = 0;          private int lastRet = 0;
242    
243          /**          /**
244           * The modCount value that the iterator believes that the backing           * The modCount value that the iterator believes that the backing
245           * List should have.  If this expectation is violated, the iterator           * List should have.  If this expectation is violated, the iterator
246           * has detected concurrent modification.           * has detected concurrent modification.
247           */           */
248          int expectedModCount = modCount;          private int expectedModCount = modCount;
249    
250          public boolean hasNext() {          public boolean hasNext() {
251              return cursor <= size;              return cursor <= size;
# Line 418  Line 425 
425       * @serialData The length of the array backing the instance is       * @serialData The length of the array backing the instance is
426       * emitted (int), followed by all of its elements (each an       * emitted (int), followed by all of its elements (each an
427       * <tt>Object</tt>) in the proper order.       * <tt>Object</tt>) in the proper order.
428         * @param s the stream
429       */       */
430      private synchronized void writeObject(java.io.ObjectOutputStream s)      private synchronized void writeObject(java.io.ObjectOutputStream s)
431          throws java.io.IOException{          throws java.io.IOException{
# Line 435  Line 443 
443      /**      /**
444       * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,       * Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
445       * deserialize it).       * deserialize it).
446         * @param s the stream
447       */       */
448      private synchronized void readObject(java.io.ObjectInputStream s)      private synchronized void readObject(java.io.ObjectInputStream s)
449          throws java.io.IOException, ClassNotFoundException {          throws java.io.IOException, ClassNotFoundException {

Legend:
Removed from v.1.6  
changed lines
  Added in v.1.7

Doug Lea
ViewVC Help
Powered by ViewVC 1.0.8