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 #asFIFO} to support only Last-In-First-Out (LIFO)
 * stack behavior, as well as method {@link #asFIFO} 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 manipulate elements
 * embedded within a deque, proceding from either direction:
 * <tt>removeFirstOccurrence</tt>, <tt>replaceFirstOccurrence</tt>
 * <tt>removeLastOccurrence</tt>, and <tt>replaceLastOccurrence</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);

    /**
     * Replaces the first occurrence of the specified element in this
     * deque.  If the deque does not contain the element, it is
     * unchanged.  More formally, replaces the first element <tt>e</tt>
     * such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
     * such an element exists).
     *
     * @param oldElement element to be replaced in this deque, if present.
     * @param newElement replacement value
     * @return <tt>true</tt> if an element was replaced
     */
    public boolean replaceFirstOccurrence(E oldElement, E newElement);

    /**
     * Replaces the last occurrence of the specified element in this
     * deque.  If the deque does not contain the element, it is
     * unchanged.  More formally, replaces the last element <tt>e</tt>
     * such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
     * such an element exists).
     *
     * @param oldElement element to be replaced in this deque, if present.
     * @param newElement replacement value
     * @return <tt>true</tt> if an element was replaced
     */
    public boolean replaceLastOccurrence(E oldElement, E newElement);

    /**
     * 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> asFIFO();

    /**
     * Returns a view of this deque as a first-in-Last-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> asLIFO();

}
Revision:	1.1
Committed:	Sun Sep 5 21:28:19 2004 UTC (19 years, 8 months ago) by dl
Branch:	MAIN
Log Message:	Initial checkin of Deques
#	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 #asFIFO} to support only Last-In-First-Out (LIFO)
23	* stack behavior, as well as method {@link #asFIFO} 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 manipulate elements
29	* embedded within a deque, proceding from either direction:
30	* <tt>removeFirstOccurrence</tt>, <tt>replaceFirstOccurrence</tt>
31	* <tt>removeLastOccurrence</tt>, and <tt>replaceLastOccurrence</tt>.
32	* They also support {@link Collection} operations including
33	* <tt>contains</tt>, <tt>iterator</tt>, and so on.
34	*
35	* <p>The {@link #offerFirst} and {@link #offerLast} methods insert an
36	* element if possible, otherwise returning <tt>false</tt>. They
37	* differ from {@link java.util.Collection#add Collection.add}, as
38	* well as {@link #addFirst} and {@link #addLast} methods, which can
39	* fail to add an element only by throwing an unchecked exception.
40	* The <tt>offer</tt> methods are designed for use when failure is a
41	* normal, rather than exceptional occurrence, for example, in
42	* fixed-capacity (or "bounded") deques.
43	*
44	* <p><tt>Deque</tt> implementations generally do not allow insertion
45	* of <tt>null</tt> elements. Even in implementations that permit it,
46	* <tt>null</tt> should not be inserted into a <tt>Deque</tt>, as
47	* <tt>null</tt> is also used as a special return value by the poll
48	* methods to indicate that the deque contains no elements.
49	*
50	* <p><tt>Deque</tt> implementations generally do not define
51	* element-based versions of methods <tt>equals</tt> and
52	* <tt>hashCode</tt> but instead inherit the identity based versions
53	* from class <tt>Object</tt>.
54	*
55	* <p>This interface is a member of the <a
56	* href="{@docRoot}/../guide/collections/index.html"> Java Collections
57	* Framework</a>.
58	*
59	* @author Doug Lea
60	* @param <E> the type of elements held in this collection
61	*/
62	public interface Deque<E> extends Collection<E> {
63
64	/**
65	* Inserts the specified element to the front this deque, if
66	* possible. When using deques that may impose insertion
67	* restrictions (for example capacity bounds), method
68	* <tt>offerFirst</tt> is generally preferable to method
69	* <tt>addFirst</tt> which can fail to insert a non-duplicate
70	* element only by throwing an exception.
71	*
72	* @param o the element to insert.
73	* @return <tt>true</tt> if it was possible to add the element to
74	* this deque, else <tt>false</tt>
75	*/
76	boolean offerFirst(E o);
77
78	/**
79	* Inserts the specified element to the end this deque, if
80	* possible. When using deques that may impose insertion
81	* restrictions (for example capacity bounds), method
82	* <tt>offerFirst</tt> is generally preferable to method
83	* <tt>addLast</tt> which can fail to insert a non-duplicate
84	* element only by throwing an exception.
85	*
86	* @param o the element to insert.
87	* @return <tt>true</tt> if it was possible to add the element to
88	* this deque, else <tt>false</tt>
89	*/
90	boolean offerLast(E o);
91
92	/**
93	* Inserts the specified element to the front this deque, if
94	* this deque permits insertion of the given element. This
95	* method has the same semantics as {@link Collection#add}.
96	*
97	* @param o the element to insert.
98	* @return <tt>true</tt> if this deque changed as a result of this
99	* call, else <tt>false</tt>
100	*/
101	boolean addFirst(E o);
102
103	/**
104	* Inserts the specified element to the end this deque, if
105	* this deque permits insertion of the given element. This
106	* method has the same semantics as {@link Collection#add}.
107	*
108	* @param o the element to insert.
109	* @return <tt>true</tt> if this deque changed as a result of this
110	* call, else <tt>false</tt>
111	*/
112	boolean addLast(E o);
113
114	/**
115	* Retrieves and removes the first element of this deque, or
116	* <tt>null</tt> if this deque is empty.
117	*
118	* @return the first element of this deque, or <tt>null</tt> if
119	* this deque is empty.
120	*/
121	E pollFirst();
122
123	/**
124	* Retrieves and removes the last element of this deque, or
125	* <tt>null</tt> if this deque is empty.
126	*
127	* @return the last element of this deque, or <tt>null</tt> if
128	* this deque is empty.
129	*/
130	E pollLast();
131
132	/**
133	* Retrieves and removes the first element of this deque. This method
134	* differs from the <tt>pollFirst</tt> method in that it throws an
135	* exception if this deque is empty.
136	*
137	* @return the first element of this deque.
138	* @throws NoSuchElementException if this deque is empty.
139	*/
140	E removeFirst();
141
142	/**
143	* Retrieves and removes the last element of this deque. This method
144	* differs from the <tt>pollLast</tt> method in that it throws an
145	* exception if this deque is empty.
146	*
147	* @return the last element of this deque.
148	* @throws NoSuchElementException if this deque is empty.
149	*/
150	E removeLast();
151
152	/**
153	* Retrieves, but does not remove, the first element of this deque,
154	* returning <tt>null</tt> if this deque is empty.
155	*
156	* @return the first element of this deque, or <tt>null</tt> if
157	* this deque is empty.
158	*/
159	E peekFirst();
160
161	/**
162	* Retrieves, but does not remove, the last element of this deque,
163	* returning <tt>null</tt> if this deque is empty.
164	*
165	* @return the last element of this deque, or <tt>null</tt> if this deque
166	* is empty.
167	*/
168	E peekLast();
169
170	/**
171	* Retrieves, but does not remove, the first element of this
172	* deque. This method differs from the <tt>peek</tt> method only
173	* in that it throws an exception if this deque is empty.
174	*
175	* @return the first element of this deque.
176	* @throws NoSuchElementException if this deque is empty.
177	*/
178	E getFirst();
179
180	/**
181	* Retrieves, but does not remove, the last element of this
182	* deque. This method differs from the <tt>peek</tt> method only
183	* in that it throws an exception if this deque is empty.
184	*
185	* @return the last element of this deque.
186	* @throws NoSuchElementException if this deque is empty.
187	*/
188	E getLast();
189
190	/**
191	* Removes the first occurrence of the specified element in this
192	* deque. If the deque does not contain the element, it is
193	* unchanged. More formally, removes the first element <tt>e</tt>
194	* such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
195	* such an element exists).
196	*
197	* @param o element to be removed from this deque, if present.
198	* @return <tt>true</tt> if the deque contained the specified element.
199	* @throws NullPointerException if the specified element is <tt>null</tt>
200	*/
201	boolean removeFirstOccurrence(E o);
202
203	/**
204	* Removes the last occurrence of the specified element in this
205	* deque. If the deque does not contain the element, it is
206	* unchanged. More formally, removes the last element <tt>e</tt>
207	* such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
208	* such an element exists).
209	*
210	* @param o element to be removed from this deque, if present.
211	* @return <tt>true</tt> if the deque contained the specified element.
212	* @throws NullPointerException if the specified element is <tt>null</tt>
213	*/
214	boolean removeLastOccurrence(E o);
215
216	/**
217	* Replaces the first occurrence of the specified element in this
218	* deque. If the deque does not contain the element, it is
219	* unchanged. More formally, replaces the first element <tt>e</tt>
220	* such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
221	* such an element exists).
222	*
223	* @param oldElement element to be replaced in this deque, if present.
224	* @param newElement replacement value
225	* @return <tt>true</tt> if an element was replaced
226	*/
227	public boolean replaceFirstOccurrence(E oldElement, E newElement);
228
229	/**
230	* Replaces the last occurrence of the specified element in this
231	* deque. If the deque does not contain the element, it is
232	* unchanged. More formally, replaces the last element <tt>e</tt>
233	* such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
234	* such an element exists).
235	*
236	* @param oldElement element to be replaced in this deque, if present.
237	* @param newElement replacement value
238	* @return <tt>true</tt> if an element was replaced
239	*/
240	public boolean replaceLastOccurrence(E oldElement, E newElement);
241
242	/**
243	* Returns a view of this deque as a first-in-first-out queue,
244	* mapping {@link Queue#offer} to <tt>offerLast</tt>, {@link
245	* Queue#poll} to <tt>pollFirst</tt>, and other operations
246	* accordingly.
247	* @return a first-in-first-out view of this deque.
248	*/
249	public Queue<E> asFIFO();
250
251	/**
252	* Returns a view of this deque as a first-in-Last-out stack,
253	* mapping {@link Queue#offer} to <tt>offerFirst</tt>, {@link
254	* Queue#poll} to <tt>pollFirst</tt>, and other operations
255	* accordingly.
256	* @return a first-in-last-out view of this deque.
257	*/
258	public Queue<E> asLIFO();
259
260	}