--- jsr166/src/main/java/util/Deque.java 2005/03/22 16:48:32 1.4 +++ jsr166/src/main/java/util/Deque.java 2005/05/17 16:14:34 1.12 @@ -25,8 +25,9 @@ package java.util; * operations cannot fail. * *

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

+ * following table: * + *

* * * @@ -36,9 +37,9 @@ package java.util; * * * - * + * * - * + * * * * @@ -67,64 +68,64 @@ package java.util; * used as a queue, FIFO (First-In-First-Out) behavior results. Elements are * 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 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 @@ -162,215 +164,239 @@ package java.util; public interface Deque extends Queue { /** + * 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}. + * + * @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 + * @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 + * 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 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 + * @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 + * 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 at 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} 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 the specified element 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 at 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} 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 the specified element 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 + * Retrieves, but does not remove, the first element of this deque. + * This method differs from {@link #peekFirst} only in that it throws an * exception if this deque is empty. * - * @return the first element of this deque + * @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 + * Retrieves, but does not remove, the last element of this deque. + * This method differs from {@link #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 peekFirst 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 - */ - E getFirst(); - - /** - * Retrieves, but does not remove, the last element of this - * deque. This method differs from the peekLast 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(); - - /** - * 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). + * 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 the deque contained the specified element + * @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 + * deque does not permit null elements (optional) */ boolean removeFirstOccurrence(Object o); /** - * 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). + * 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 the deque contained the specified element + * @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 + * deque does not permit null elements (optional) */ boolean removeLastOccurrence(Object o); - // *** Queue methods *** /** * Inserts the specified element into the queue represented by this deque - * unless it would violate capacity restrictions. In other words, inserts - * the specified element at 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 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 #offerLast}. + *

This method is equivalent to {@link #addLast(Object) addLast}. * - * @param e the element to insert - * @return true if it was possible to insert the element, - * else false - * @throws NullPointerException if the specified element is null and this - * deque does not permit null elements - */ - 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. - * - *

This method is equivalent to {@link #addLast}. - * - * @param e the element to insert + * @param e the element to add * @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 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 + * deque does not permit null elements + * @throws IllegalArgumentException if some property of the specified + * element prevents it from being added to this deque */ boolean add(E e); /** - * 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. + * 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 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 #pollFirst()}. + *

This method is equivalent to {@link #offerLast}. * - * @return the first element of this deque, or null if - * this deque is empty + * @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 */ - E poll(); + boolean offer(E e); /** - * 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 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} only in that it throws an + * exception if this deque is empty. * *

This method is equivalent to {@link #removeFirst()}. * @@ -380,20 +406,22 @@ public interface Deque extends Queue< E remove(); /** - * Retrieves, but does not remove, the head of the queue represented by - * this deque, returning 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 #peekFirst()}. + *

This method is equivalent to {@link #pollFirst()}. * - * @return the head of the queue represented by this deque, or - * null if this deque is empty + * @return the first element of this deque, or null if + * this deque is empty */ - E peek(); + E poll(); /** * 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 deque (in other words, the first element of this deque). + * This method differs from {@link #peek} only in that it throws an + * exception if this deque is empty. * *

This method is equivalent to {@link #getFirst()}. * @@ -402,21 +430,39 @@ public interface Deque extends Queue< */ E element(); + /** + * Retrieves, but does not remove, 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 #peekFirst()}. + * + * @return the head of the queue represented by this deque, or + * null if this deque is empty + */ + E peek(); + // *** Stack methods *** /** - * Pushes an element onto the stack represented by this deque. In other - * words, inserts the element at the front of 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}. * * @param e the element to push - * @throws IllegalStateException if it was not possible to insert - * the element due to capacity restrictions + * @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 + * 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); @@ -427,19 +473,61 @@ 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). + * 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 + * @return an iterator over the elements in this deque in proper sequence */ Iterator iterator(); }