--- jsr166/src/main/java/util/Deque.java 2005/03/08 12:27:06 1.2 +++ jsr166/src/main/java/util/Deque.java 2012/10/21 06:40:20 1.21 @@ -1,7 +1,7 @@ /* * Written by Doug Lea and Josh Bloch with assistance from members of * JCP JSR-166 Expert Group and released to the public domain, as explained - * at http://creativecommons.org/licenses/publicdomain + * at http://creativecommons.org/publicdomain/zero/1.0/ */ package java.util; @@ -24,9 +24,10 @@ package java.util; * Deque implementations; in most implementations, insert * operations cannot fail. * - *

The twelve methods described above are summarized in the - * following table:

- * + *

The twelve methods described above are summarized in the + * following table: + * + *

* * * @@ -36,9 +37,9 @@ package java.util; * * * - * + * * - * + * * * * @@ -65,66 +66,66 @@ package java.util; * *

This interface extends the {@link Queue} interface. When a deque is * used as a queue, FIFO (First-In-First-Out) behavior results. Elements are - * added to the end of the deque and removed from the beginning. The methods + * added at the end of the deque and removed from the beginning. The methods * inherited from the Queue interface are precisely equivalent to - * Deque methods as indicated in the following table:

+ * Deque methods as indicated in the following table: * + *

*

Throws exceptionReturns special valueSpecial valueThrows exceptionReturns special valueSpecial value
Insert
* * * * * - * - * - * - * - * * * - * - * - * - * - * - * + * + * + * + * + * + * * * - * - * - * - * - * - * + * + * + * + * + * + * * * - * + * + * + * + * + * *
Queue Method Equivalent Deque Method
{@link java.util.Queue#offer offer(e)}{@link #offerLast offerLast(e)}
{@link java.util.Queue#add add(e)}{@link #addLast addLast(e)}
{@link java.util.Queue#poll poll()}{@link #pollFirst pollFirst()}
{@link java.util.Queue#offer offer(e)}{@link #offerLast offerLast(e)}
{@link java.util.Queue#remove remove()}{@link #removeFirst removeFirst()}
{@link java.util.Queue#peek peek()}{@link #peek peekFirst()}
{@link java.util.Queue#poll poll()}{@link #pollFirst pollFirst()}
{@link java.util.Queue#element element()}{@link #getFirst getFirst()}
{@link java.util.Queue#peek peek()}{@link #peek peekFirst()}
* *

Deques can also be used as LIFO (Last-In-First-Out) stacks. This * interface should be used in preference to the legacy {@link Stack} class. - * When a dequeue is used as a stack, elements are pushed and popped from the + * When a deque is used as a stack, elements are pushed and popped from the * beginning of the deque. Stack methods are precisely equivalent to - * Deque methods as indicated in the table below:

+ * Deque methods as indicated in the table below: * + *

* * * * * * - * * * - * - * + * + * * * - * - * + * + * * * - * + * *
Stack Method Equivalent Deque Method
{@link #push push(e)}{@link #addFirst addFirst(e)}
{@link #pop pop()}{@link #removeFirst removeFirst()}
{@link #peek peek()}{@link #peekFirst peekFirst()}
* *

Note that the {@link #peek peek} method works equally well when @@ -133,9 +134,10 @@ package java.util; * *

This interface provides two methods to remove interior * elements, {@link #removeFirstOccurrence removeFirstOccurrence} and - * {@link #removeLastOccurrence removeLastOccurrence}. Unlike the - * {@link List} interface, this interface does not provide support for - * indexed access to elements. + * {@link #removeLastOccurrence removeLastOccurrence}. + * + *

Unlike the {@link List} interface, this interface does not + * provide support for indexed access to elements. * *

While Deque implementations are not strictly required * to prohibit the insertion of null elements, they are strongly @@ -144,14 +146,14 @@ package java.util; * take advantage of the ability to insert nulls. This is so because * null is used as a special return value by various methods * to indicated that the deque is empty. - * + * *

Deque implementations generally do not define * element-based versions of the equals and hashCode * methods, but instead inherit the identity-based versions from class * Object. * *

This interface is a member of the Java Collections + * href="{@docRoot}/../technotes/guides/collections/index.html"> Java Collections * Framework. * * @author Doug Lea @@ -159,261 +161,310 @@ package java.util; * @since 1.6 * @param the type of elements held in this collection */ - public interface Deque extends Queue { /** - * Inserts the specified element to the front this deque unless it would + * Inserts the specified element at the front of this deque if it is + * possible to do so immediately without violating capacity restrictions. + * When using a capacity-restricted deque, it is generally preferable to + * use method {@link #offerFirst}. + * + * @param e the element to add + * @throws IllegalStateException if the element cannot be added at this + * time due to capacity restrictions + * @throws ClassCastException if the class of the specified element + * prevents it from being added to this deque + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements + * @throws IllegalArgumentException if some property of the specified + * element prevents it from being added to this deque + */ + void addFirst(E e); + + /** + * Inserts the specified element at the end of this deque if it is + * possible to do so immediately without violating capacity restrictions. + * When using a capacity-restricted deque, it is generally preferable to + * use method {@link #offerLast}. + * + *

This method is equivalent to {@link #add}. + * + * @param e the element to add + * @throws IllegalStateException if the element cannot be added at this + * time due to capacity restrictions + * @throws ClassCastException if the class of the specified element + * prevents it from being added to this deque + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements + * @throws IllegalArgumentException if some property of the specified + * element prevents it from being added to this deque + */ + void addLast(E e); + + /** + * Inserts the specified element at the front of this deque unless it would * violate capacity restrictions. When using a capacity-restricted deque, - * this method is generally preferable to method addFirst, which - * can fail to insert an element only by throwing an exception. + * this method is generally preferable to the {@link #addFirst} method, + * which can fail to insert an element only by throwing an exception. * - * @param e the element to insert - * @return true if it was possible to insert the element, - * else false - * @throws NullPointerException if e is null and this - * deque does not permit null elements + * @param e the element to add + * @return true if the element was added to this deque, else + * false + * @throws ClassCastException if the class of the specified element + * prevents it from being added to this deque + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements + * @throws IllegalArgumentException if some property of the specified + * element prevents it from being added to this deque */ boolean offerFirst(E e); /** - * Inserts the specified element to the end of this deque unless it would + * Inserts the specified element at the end of this deque unless it would * violate capacity restrictions. When using a capacity-restricted deque, - * this method is generally preferable to method addLast which - * can fail to insert an element only by throwing an exception. + * this method is generally preferable to the {@link #addLast} method, + * which can fail to insert an element only by throwing an exception. * - * @param e the element to insert - * @return true if it was possible to insert the element, - * else false - * @throws NullPointerException if e is null and this - * deque does not permit null elements + * @param e the element to add + * @return true if the element was added to this deque, else + * false + * @throws ClassCastException if the class of the specified element + * prevents it from being added to this deque + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements + * @throws IllegalArgumentException if some property of the specified + * element prevents it from being added to this deque */ boolean offerLast(E e); /** - * Inserts the specified element to the front of this deque unless it - * would violate capacity restrictions. + * Retrieves and removes the first element of this deque. This method + * differs from {@link #pollFirst pollFirst} only in that it throws an + * exception if this deque is empty. * - * @param e the element to insert - * @throws IllegalStateException if it was not possible to insert - * the element due to capacity restrictions - * @throws NullPointerException if e is null and this - * deque does not permit null elements + * @return the head of this deque + * @throws NoSuchElementException if this deque is empty */ - void addFirst(E e); + E removeFirst(); /** - * Inserts the specified element to the end of this deque unless it would - * violate capacity restrictions. + * Retrieves and removes the last element of this deque. This method + * differs from {@link #pollLast pollLast} only in that it throws an + * exception if this deque is empty. * - * @param e the element to insert - * @throws IllegalStateException if it was not possible to insert - * the element due to capacity restrictions - * @throws NullPointerException if e is null and this - * deque does not permit null elements + * @return the tail of this deque + * @throws NoSuchElementException if this deque is empty */ - void addLast(E e); + E removeLast(); /** - * Retrieves and removes the first element of this deque, or - * null if this deque is empty. + * Retrieves and removes the first element of this deque, + * or returns null if this deque is empty. * - * @return the first element of this deque, or null if - * this deque is empty + * @return the head of this deque, or null if this deque is empty */ E pollFirst(); /** - * Retrieves and removes the last element of this deque, or - * null if this deque is empty. + * Retrieves and removes the last element of this deque, + * or returns null if this deque is empty. * - * @return the last element of this deque, or null if - * this deque is empty + * @return the tail of this deque, or null if this deque is empty */ E pollLast(); /** - * Removes and returns the first element of this deque. This method - * differs from the pollFirst method only in that it throws an - * exception if this deque is empty. + * Retrieves, but does not remove, the first element of this deque. * - * @return the first element of this deque + * This method differs from {@link #peekFirst peekFirst} only in that it + * throws an exception if this deque is empty. + * + * @return the head of this deque * @throws NoSuchElementException if this deque is empty */ - E removeFirst(); + E getFirst(); /** - * Retrieves and removes the last element of this deque. This method - * differs from the pollLast method only in that it throws an - * exception if this deque is empty. + * Retrieves, but does not remove, the last element of this deque. + * This method differs from {@link #peekLast peekLast} only in that it + * throws an exception if this deque is empty. * - * @return the last element of this deque + * @return the tail of this deque * @throws NoSuchElementException if this deque is empty */ - E removeLast(); + E getLast(); /** * Retrieves, but does not remove, the first element of this deque, - * returning null if this deque is empty. + * or returns null if this deque is empty. * - * @return the first element of this deque, or null if - * this deque is empty + * @return the head of this deque, or null if this deque is empty */ E peekFirst(); /** * Retrieves, but does not remove, the last element of this deque, - * returning null if this deque is empty. + * or returns null if this deque is empty. * - * @return the last element of this deque, or null if this deque - * is empty + * @return the tail of this deque, or null if this deque is empty */ E peekLast(); /** - * Retrieves, but does not remove, the first element of this - * deque. This method differs from the peek method only - * in that it throws an exception if this deque is empty. - * - * @return the first element of this deque - * @throws NoSuchElementException if this deque is empty + * Removes the first occurrence of the specified element from this deque. + * If the deque does not contain the element, it is unchanged. + * More formally, removes the first element e such that + * (o==null ? e==null : o.equals(e)) + * (if such an element exists). + * Returns true if this deque contained the specified element + * (or equivalently, if this deque changed as a result of the call). + * + * @param o element to be removed from this deque, if present + * @return true if an element was removed as a result of this call + * @throws ClassCastException if the class of the specified element + * is incompatible with this deque (optional) + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements (optional) + */ + boolean removeFirstOccurrence(Object o); + + /** + * Removes the last occurrence of the specified element from this deque. + * If the deque does not contain the element, it is unchanged. + * More formally, removes the last element e such that + * (o==null ? e==null : o.equals(e)) + * (if such an element exists). + * Returns true if this deque contained the specified element + * (or equivalently, if this deque changed as a result of the call). + * + * @param o element to be removed from this deque, if present + * @return true if an element was removed as a result of this call + * @throws ClassCastException if the class of the specified element + * is incompatible with this deque (optional) + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements (optional) */ - E getFirst(); + boolean removeLastOccurrence(Object o); - /** - * Retrieves, but does not remove, the last element of this - * deque. This method differs from the peek method only - * in that it throws an exception if this deque is empty. - * - * @return the last element of this deque - * @throws NoSuchElementException if this deque is empty - */ - E getLast(); + // *** Queue methods *** /** - * Removes the first occurrence of the specified element in this - * deque. If the deque does not contain the element, it is - * unchanged. More formally, removes the first element e - * such that (o==null ? e==null : o.equals(e)) (if - * such an element exists). - * - * @param e element to be removed from this deque, if present - * @return true if the deque contained the specified element - * @throws NullPointerException if the specified element is null - */ - boolean removeFirstOccurrence(Object e); - - /** - * Removes the last occurrence of the specified element in this - * deque. If the deque does not contain the element, it is - * unchanged. More formally, removes the last element e - * such that (o==null ? e==null : o.equals(e)) (if - * such an element exists). - * - * @param e element to be removed from this deque, if present - * @return true if the deque contained the specified element - * @throws NullPointerException if the specified element is null + * Inserts the specified element into the queue represented by this deque + * (in other words, at the tail of this deque) if it is possible to do so + * immediately without violating capacity restrictions, returning + * true upon success and throwing an + * IllegalStateException if no space is currently available. + * When using a capacity-restricted deque, it is generally preferable to + * use {@link #offer(Object) offer}. + * + *

This method is equivalent to {@link #addLast}. + * + * @param e the element to add + * @return true (as specified by {@link Collection#add}) + * @throws IllegalStateException if the element cannot be added at this + * time due to capacity restrictions + * @throws ClassCastException if the class of the specified element + * prevents it from being added to this deque + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements + * @throws IllegalArgumentException if some property of the specified + * element prevents it from being added to this deque */ - boolean removeLastOccurrence(Object e); - - - // *** Queue methods *** + boolean add(E e); /** * Inserts the specified element into the queue represented by this deque - * unless it would violate capacity restrictions. In other words, inserts - * the specified element to the end of this deque. When using a - * capacity-restricted deque, this method is generally preferable to the - * {@link #add} method, which can fail to insert an element only by - * throwing an exception. + * (in other words, at the tail of this deque) if it is possible to do so + * immediately without violating capacity restrictions, returning + * true upon success and false if no space is currently + * available. When using a capacity-restricted deque, this method is + * generally preferable to the {@link #add} method, which can fail to + * insert an element only by throwing an exception. * *

This method is equivalent to {@link #offerLast}. * - * @param e the element to insert - * @return true if it was possible to insert the element, - * else false - * @throws NullPointerException if e is null and this - * deque does not permit null elements + * @param e the element to add + * @return true if the element was added to this deque, else + * false + * @throws ClassCastException if the class of the specified element + * prevents it from being added to this deque + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements + * @throws IllegalArgumentException if some property of the specified + * element prevents it from being added to this deque */ boolean offer(E e); /** - * Inserts the specified element into the queue represented by this - * deque unless it would violate capacity restrictions. In other words, - * inserts the specified element as the last element of this deque. + * Retrieves and removes the head of the queue represented by this deque + * (in other words, the first element of this deque). + * This method differs from {@link #poll poll} only in that it throws an + * exception if this deque is empty. * - *

This method is equivalent to {@link #addLast}. + *

This method is equivalent to {@link #removeFirst()}. * - * @param e the element to insert - * @return true (as per the spec for {@link Collection#add}) - * @throws IllegalStateException if it was not possible to insert - * the element due to capacity restrictions - * @throws NullPointerException if e is null and this - * deque does not permit null elements + * @return the head of the queue represented by this deque + * @throws NoSuchElementException if this deque is empty */ - boolean add(E e); + E remove(); /** - * Retrieves and removes the head of the queue represented by - * this deque, or null if this deque is empty. In other words, - * retrieves and removes the first element of this deque, or null - * if this deque is empty. + * Retrieves and removes the head of the queue represented by this deque + * (in other words, the first element of this deque), or returns + * null if this deque is empty. * *

This method is equivalent to {@link #pollFirst()}. * * @return the first element of this deque, or null if - * this deque is empty + * this deque is empty */ E poll(); /** - * Retrieves and removes the head of the queue represented by this deque. - * This method differs from the poll method only in that it - * throws an exception if this deque is empty. + * Retrieves, but does not remove, the head of the queue represented by + * this deque (in other words, the first element of this deque). + * This method differs from {@link #peek peek} only in that it throws an + * exception if this deque is empty. * - *

This method is equivalent to {@link #removeFirst()}. + *

This method is equivalent to {@link #getFirst()}. * * @return the head of the queue represented by this deque * @throws NoSuchElementException if this deque is empty */ - E remove(); + E element(); /** * Retrieves, but does not remove, the head of the queue represented by - * this deque, returning null if this deque is empty. + * this deque (in other words, the first element of this deque), or + * returns null if this deque is empty. * - *

This method is equivalent to {@link #peekFirst()} + *

This method is equivalent to {@link #peekFirst()}. * * @return the head of the queue represented by this deque, or - * null if this deque is empty + * null if this deque is empty */ E peek(); - /** - * Retrieves, but does not remove, the head of the queue represented by - * this deque. This method differs from the peek method only in - * that it throws an exception if this deque is empty. - * - *

This method is equivalent to {@link #getFirst()} - * - * @return the head of the queue represented by this deque - * @throws NoSuchElementException if this deque is empty - */ - E element(); - // *** Stack methods *** /** - * Pushes an element onto the stack represented by this deque. In other - * words, inserts the element to the front this deque unless it would - * violate capacity restrictions. + * Pushes an element onto the stack represented by this deque (in other + * words, at the head of this deque) if it is possible to do so + * immediately without violating capacity restrictions, returning + * true upon success and throwing an + * IllegalStateException if no space is currently available. * *

This method is equivalent to {@link #addFirst}. * - * @throws IllegalStateException if it was not possible to insert - * the element due to capacity restrictions - * @throws NullPointerException if e is null and this - * deque does not permit null elements + * @param e the element to push + * @throws IllegalStateException if the element cannot be added at this + * time due to capacity restrictions + * @throws ClassCastException if the class of the specified element + * prevents it from being added to this deque + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements + * @throws IllegalArgumentException if some property of the specified + * element prevents it from being added to this deque */ void push(E e); @@ -424,19 +475,72 @@ public interface Deque extends Queue< *

This method is equivalent to {@link #removeFirst()}. * * @return the element at the front of this deque (which is the top - * of the stack represented by this deque) + * of the stack represented by this deque) * @throws NoSuchElementException if this deque is empty */ E pop(); - // *** Collection Method *** + // *** Collection methods *** + + /** + * Removes the first occurrence of the specified element from this deque. + * If the deque does not contain the element, it is unchanged. + * More formally, removes the first element e such that + * (o==null ? e==null : o.equals(e)) + * (if such an element exists). + * Returns true if this deque contained the specified element + * (or equivalently, if this deque changed as a result of the call). + * + *

This method is equivalent to {@link #removeFirstOccurrence}. + * + * @param o element to be removed from this deque, if present + * @return true if an element was removed as a result of this call + * @throws ClassCastException if the class of the specified element + * is incompatible with this deque (optional) + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements (optional) + */ + boolean remove(Object o); + + /** + * Returns true if this deque contains the specified element. + * More formally, returns true if and only if this deque contains + * at least one element e such that + * (o==null ? e==null : o.equals(e)). + * + * @param o element whose presence in this deque is to be tested + * @return true if this deque contains the specified element + * @throws ClassCastException if the type of the specified element + * is incompatible with this deque (optional) + * @throws NullPointerException if the specified element is null and this + * deque does not permit null elements (optional) + */ + boolean contains(Object o); + + /** + * Returns the number of elements in this deque. + * + * @return the number of elements in this deque + */ + public int size(); /** - * Returns an iterator over the elements in this deque. The elements - * will be ordered from first (head) to last (tail). - * - * @return an Iterator over the elements in this deque + * Returns an iterator over the elements in this deque in proper sequence. + * The elements will be returned in order from first (head) to last (tail). + * + * @return an iterator over the elements in this deque in proper sequence */ Iterator iterator(); + + /** + * Returns an iterator over the elements in this deque in reverse + * sequential order. The elements will be returned in order from + * last (tail) to first (head). + * + * @return an iterator over the elements in this deque in reverse + * sequence + */ + Iterator descendingIterator(); + }