src/jsr166x/Deque.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/licenses/publicdomain
 */

package jsr166x;
import java.util.*;

/**
 * A linear collection in which elements may be inserted and removed
 * from both the beginning and end. A <tt>Deque</tt> (short for
 * "double ended queue") provides uniformly named methods to
 * <tt>get</tt>, <tt>peek</tt>, <tt>poll</tt>, <tt>remove</tt>,
 * <tt>offer</tt>, and <tt>add</tt> the <tt>first</tt> and
 * <tt>last</tt> element of the collection (for example, methods
 * <tt>addFirst</tt>, <tt>pollLast</tt>). Unlike interface {@link
 * List} the Deque interface does not define support for indexed
 * operations or sublists.
 *
 * <p>A view of a subset of Deque operations can be obtained using
 * method {@link #asFifoQueue} to support only Last-In-First-Out (LIFO)
 * stack behavior, as well as method {@link #asFifoQueue} to support only
 * First-in-First-Out (FIFO) queue behavior.  More commonly, a Deque
 * is used when various mixtures of LIFO and FIFO operations are
 * required.
 *
 * <p>Deques additionally provide a few methods to remove elements
 * embedded within a deque, proceding from either direction using
 * <tt>removeFirstOccurrence</tt> and <tt>removeLastOccurrence</tt>.
 * They also support {@link Collection} operations including
 * <tt>contains</tt>, <tt>iterator</tt>, and so on.
 *
 * <p>The {@link #offerFirst} and {@link #offerLast} methods insert an
 * element if possible, otherwise returning <tt>false</tt>.  They
 * differ from {@link java.util.Collection#add Collection.add}, as
 * well as {@link #addFirst} and {@link #addLast} methods, which can
 * fail to add an element only by throwing an unchecked exception.
 * The <tt>offer</tt> methods are designed for use when failure is a
 * normal, rather than exceptional occurrence, for example, in
 * fixed-capacity (or &quot;bounded&quot;) deques.
 *
 * <p><tt>Deque</tt> implementations generally do not allow insertion
 * of <tt>null</tt> elements.  Even in implementations that permit it,
 * <tt>null</tt> should not be inserted into a <tt>Deque</tt>, as
 * <tt>null</tt> is also used as a special return value by the poll
 * methods to indicate that the deque contains no elements.
 * 
 * <p><tt>Deque</tt> implementations generally do not define
 * element-based versions of methods <tt>equals</tt> and
 * <tt>hashCode</tt> but instead inherit the identity based versions
 * from class <tt>Object</tt>.
 *
 * <p>This interface is a member of the <a
 * href="{@docRoot}/../guide/collections/index.html"> Java Collections
 * Framework</a>.
 *
 * @author Doug Lea
 * @param <E> the type of elements held in this collection
 */
public interface Deque<E> extends Collection<E> {

    /**
     * Inserts the specified element to the front this deque, if
     * possible.  When using deques that may impose insertion
     * restrictions (for example capacity bounds), method
     * <tt>offerFirst</tt> is generally preferable to method
     * <tt>addFirst</tt> which can fail to insert a non-duplicate
     * element only by throwing an exception.
     *
     * @param o the element to insert.
     * @return <tt>true</tt> if it was possible to add the element to
     * this deque, else <tt>false</tt>
     */
    boolean offerFirst(E o);

    /**
     * Inserts the specified element to the end this deque, if
     * possible.  When using deques that may impose insertion
     * restrictions (for example capacity bounds), method
     * <tt>offerFirst</tt> is generally preferable to method
     * <tt>addLast</tt> which can fail to insert a non-duplicate
     * element only by throwing an exception.
     *
     * @param o the element to insert.
     * @return <tt>true</tt> if it was possible to add the element to
     * this deque, else <tt>false</tt>
     */
    boolean offerLast(E o);

    /**
     * Inserts the specified element to the front this deque, if
     * this deque permits insertion of the given element.  This
     * method has the same semantics as {@link Collection#add}.
     *
     * @param o the element to insert.
     * @return <tt>true</tt> if this deque changed as a result of this
     * call, else <tt>false</tt>
     */
    boolean addFirst(E o);

    /**
     * Inserts the specified element to the end this deque, if
     * this deque permits insertion of the given element.  This
     * method has the same semantics as {@link Collection#add}.
     *
     * @param o the element to insert.
     * @return <tt>true</tt> if this deque changed as a result of this
     * call, else <tt>false</tt>
     */
    boolean addLast(E o);

    /**
     * Retrieves and removes the first element of this deque, or
     * <tt>null</tt> if this deque is empty.
     *
     * @return the first element of this deque, or <tt>null</tt> if
     * this deque is empty.
     */
    E pollFirst();

    /**
     * Retrieves and removes the last element of this deque, or
     * <tt>null</tt> if this deque is empty.
     *
     * @return the last element of this deque, or <tt>null</tt> if
     * this deque is empty.
     */
    E pollLast();

    /**
     * Retrieves and removes the first element of this deque.  This method
     * differs from the <tt>pollFirst</tt> method 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 removeFirst();

    /**
     * Retrieves and removes the last element of this deque.  This method
     * differs from the <tt>pollLast</tt> method 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 removeLast();

    /**
     * Retrieves, but does not remove, the first element of this deque,
     * returning <tt>null</tt> if this deque is empty.
     *
     * @return the first element of this deque, or <tt>null</tt> if
     * this deque is empty.
     */
    E peekFirst();

    /**
     * Retrieves, but does not remove, the last element of this deque,
     * returning <tt>null</tt> if this deque is empty.
     *
     * @return the last element of this deque, or <tt>null</tt> if this deque
     * is empty.
     */
    E peekLast();

    /**
     * Retrieves, but does not remove, the first element of this
     * deque.  This method differs from the <tt>peek</tt> 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 <tt>peek</tt> 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 <tt>e</tt>
     * such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
     * such an element exists).
     *
     * @param o element to be removed from this deque, if present.
     * @return <tt>true</tt> if the deque contained the specified element.
     * @throws NullPointerException if the specified element is <tt>null</tt>
     */
    boolean removeFirstOccurrence(E 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 <tt>e</tt>
     * such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
     * such an element exists).
     *
     * @param o element to be removed from this deque, if present.
     * @return <tt>true</tt> if the deque contained the specified element.
     * @throws NullPointerException if the specified element is <tt>null</tt>
     */
    boolean removeLastOccurrence(E o);

    /**
     * Returns a view of this deque as a first-in-first-out queue,
     * mapping {@link Queue#offer} to <tt>offerLast</tt>, {@link
     * Queue#poll} to <tt>pollFirst</tt>, and other operations
     * accordingly.
     * @return a first-in-first-out view of this deque.
     */
    public Queue<E> asFifoQueue();

    /**
     * Returns a view of this deque as a last-in-first-out stack,
     * mapping {@link Queue#offer} to <tt>offerFirst</tt>, {@link
     * Queue#poll} to <tt>pollFirst</tt>, and other operations
     * accordingly.
     * @return a first-in-last-out view of this deque.
     */
    public Queue<E> asLifoQueue();

}
Revision:	1.2
Committed:	Tue Sep 7 10:37:29 2004 UTC (19 years, 8 months ago) by dl
Branch:	MAIN
Changes since 1.1:	+8 -35 lines
Log Message:	Improve method names, fix typos
#	User	Rev	Content
1	dl	1.1	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain, as explained at
4			* http://creativecommons.org/licenses/publicdomain
5			*/
6
7			package jsr166x;
8			import java.util.*;
9
10			/**
11			* A linear collection in which elements may be inserted and removed
12			* from both the beginning and end. A <tt>Deque</tt> (short for
13			* "double ended queue") provides uniformly named methods to
14			* <tt>get</tt>, <tt>peek</tt>, <tt>poll</tt>, <tt>remove</tt>,
15			* <tt>offer</tt>, and <tt>add</tt> the <tt>first</tt> and
16			* <tt>last</tt> element of the collection (for example, methods
17			* <tt>addFirst</tt>, <tt>pollLast</tt>). Unlike interface {@link
18			* List} the Deque interface does not define support for indexed
19			* operations or sublists.
20			*
21			* <p>A view of a subset of Deque operations can be obtained using
22	dl	1.2	* method {@link #asFifoQueue} to support only Last-In-First-Out (LIFO)
23			* stack behavior, as well as method {@link #asFifoQueue} to support only
24	dl	1.1	* First-in-First-Out (FIFO) queue behavior. More commonly, a Deque
25			* is used when various mixtures of LIFO and FIFO operations are
26			* required.
27			*
28	dl	1.2	* <p>Deques additionally provide a few methods to remove elements
29			* embedded within a deque, proceding from either direction using
30			* <tt>removeFirstOccurrence</tt> and <tt>removeLastOccurrence</tt>.
31	dl	1.1	* They also support {@link Collection} operations including
32			* <tt>contains</tt>, <tt>iterator</tt>, and so on.
33			*
34			* <p>The {@link #offerFirst} and {@link #offerLast} methods insert an
35			* element if possible, otherwise returning <tt>false</tt>. They
36			* differ from {@link java.util.Collection#add Collection.add}, as
37			* well as {@link #addFirst} and {@link #addLast} methods, which can
38			* fail to add an element only by throwing an unchecked exception.
39			* The <tt>offer</tt> methods are designed for use when failure is a
40			* normal, rather than exceptional occurrence, for example, in
41			* fixed-capacity (or "bounded") deques.
42			*
43			* <p><tt>Deque</tt> implementations generally do not allow insertion
44			* of <tt>null</tt> elements. Even in implementations that permit it,
45			* <tt>null</tt> should not be inserted into a <tt>Deque</tt>, as
46			* <tt>null</tt> is also used as a special return value by the poll
47			* methods to indicate that the deque contains no elements.
48			*
49			* <p><tt>Deque</tt> implementations generally do not define
50			* element-based versions of methods <tt>equals</tt> and
51			* <tt>hashCode</tt> but instead inherit the identity based versions
52			* from class <tt>Object</tt>.
53			*
54			* <p>This interface is a member of the <a
55			* href="{@docRoot}/../guide/collections/index.html"> Java Collections
56			* Framework</a>.
57			*
58			* @author Doug Lea
59			* @param <E> the type of elements held in this collection
60			*/
61			public interface Deque<E> extends Collection<E> {
62
63			/**
64			* Inserts the specified element to the front this deque, if
65			* possible. When using deques that may impose insertion
66			* restrictions (for example capacity bounds), method
67			* <tt>offerFirst</tt> is generally preferable to method
68			* <tt>addFirst</tt> which can fail to insert a non-duplicate
69			* element only by throwing an exception.
70			*
71			* @param o the element to insert.
72			* @return <tt>true</tt> if it was possible to add the element to
73			* this deque, else <tt>false</tt>
74			*/
75			boolean offerFirst(E o);
76
77			/**
78			* Inserts the specified element to the end this deque, if
79			* possible. When using deques that may impose insertion
80			* restrictions (for example capacity bounds), method
81			* <tt>offerFirst</tt> is generally preferable to method
82			* <tt>addLast</tt> which can fail to insert a non-duplicate
83			* element only by throwing an exception.
84			*
85			* @param o the element to insert.
86			* @return <tt>true</tt> if it was possible to add the element to
87			* this deque, else <tt>false</tt>
88			*/
89			boolean offerLast(E o);
90
91			/**
92			* Inserts the specified element to the front this deque, if
93			* this deque permits insertion of the given element. This
94			* method has the same semantics as {@link Collection#add}.
95			*
96			* @param o the element to insert.
97			* @return <tt>true</tt> if this deque changed as a result of this
98			* call, else <tt>false</tt>
99			*/
100			boolean addFirst(E o);
101
102			/**
103			* Inserts the specified element to the end this deque, if
104			* this deque permits insertion of the given element. This
105			* method has the same semantics as {@link Collection#add}.
106			*
107			* @param o the element to insert.
108			* @return <tt>true</tt> if this deque changed as a result of this
109			* call, else <tt>false</tt>
110			*/
111			boolean addLast(E o);
112
113			/**
114			* Retrieves and removes the first element of this deque, or
115			* <tt>null</tt> if this deque is empty.
116			*
117			* @return the first element of this deque, or <tt>null</tt> if
118			* this deque is empty.
119			*/
120			E pollFirst();
121
122			/**
123			* Retrieves and removes the last element of this deque, or
124			* <tt>null</tt> if this deque is empty.
125			*
126			* @return the last element of this deque, or <tt>null</tt> if
127			* this deque is empty.
128			*/
129			E pollLast();
130
131			/**
132			* Retrieves and removes the first element of this deque. This method
133			* differs from the <tt>pollFirst</tt> method in that it throws an
134			* exception if this deque is empty.
135			*
136			* @return the first element of this deque.
137			* @throws NoSuchElementException if this deque is empty.
138			*/
139			E removeFirst();
140
141			/**
142			* Retrieves and removes the last element of this deque. This method
143			* differs from the <tt>pollLast</tt> method in that it throws an
144			* exception if this deque is empty.
145			*
146			* @return the last element of this deque.
147			* @throws NoSuchElementException if this deque is empty.
148			*/
149			E removeLast();
150
151			/**
152			* Retrieves, but does not remove, the first element of this deque,
153			* returning <tt>null</tt> if this deque is empty.
154			*
155			* @return the first element of this deque, or <tt>null</tt> if
156			* this deque is empty.
157			*/
158			E peekFirst();
159
160			/**
161			* Retrieves, but does not remove, the last element of this deque,
162			* returning <tt>null</tt> if this deque is empty.
163			*
164			* @return the last element of this deque, or <tt>null</tt> if this deque
165			* is empty.
166			*/
167			E peekLast();
168
169			/**
170			* Retrieves, but does not remove, the first element of this
171			* deque. This method differs from the <tt>peek</tt> method only
172			* in that it throws an exception if this deque is empty.
173			*
174			* @return the first element of this deque.
175			* @throws NoSuchElementException if this deque is empty.
176			*/
177			E getFirst();
178
179			/**
180			* Retrieves, but does not remove, the last element of this
181			* deque. This method differs from the <tt>peek</tt> method only
182			* in that it throws an exception if this deque is empty.
183			*
184			* @return the last element of this deque.
185			* @throws NoSuchElementException if this deque is empty.
186			*/
187			E getLast();
188
189			/**
190			* Removes the first occurrence of the specified element in this
191			* deque. If the deque does not contain the element, it is
192			* unchanged. More formally, removes the first element <tt>e</tt>
193			* such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
194			* such an element exists).
195			*
196			* @param o element to be removed from this deque, if present.
197			* @return <tt>true</tt> if the deque contained the specified element.
198			* @throws NullPointerException if the specified element is <tt>null</tt>
199			*/
200			boolean removeFirstOccurrence(E o);
201
202			/**
203			* Removes the last occurrence of the specified element in this
204			* deque. If the deque does not contain the element, it is
205			* unchanged. More formally, removes the last element <tt>e</tt>
206			* such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
207			* such an element exists).
208			*
209			* @param o element to be removed from this deque, if present.
210			* @return <tt>true</tt> if the deque contained the specified element.
211			* @throws NullPointerException if the specified element is <tt>null</tt>
212			*/
213			boolean removeLastOccurrence(E o);
214
215			/**
216			* Returns a view of this deque as a first-in-first-out queue,
217			* mapping {@link Queue#offer} to <tt>offerLast</tt>, {@link
218			* Queue#poll} to <tt>pollFirst</tt>, and other operations
219			* accordingly.
220			* @return a first-in-first-out view of this deque.
221			*/
222	dl	1.2	public Queue<E> asFifoQueue();
223	dl	1.1
224			/**
225	dl	1.2	* Returns a view of this deque as a last-in-first-out stack,
226	dl	1.1	* mapping {@link Queue#offer} to <tt>offerFirst</tt>, {@link
227			* Queue#poll} to <tt>pollFirst</tt>, and other operations
228			* accordingly.
229			* @return a first-in-last-out view of this deque.
230			*/
231	dl	1.2	public Queue<E> asLifoQueue();
232	dl	1.1
233			}