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
#	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			* 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			}