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
#	Content
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	* method {@link #asFifoQueue} to support only Last-In-First-Out (LIFO)
23	* stack behavior, as well as method {@link #asFifoQueue} to support only
24	* 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	* <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	* 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	public Queue<E> asFifoQueue();
223
224	/**
225	* Returns a view of this deque as a last-in-first-out stack,
226	* 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	public Queue<E> asLifoQueue();
232
233	}