ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166x/Deque.java

Comparing jsr166/src/jsr166x/Deque.java (file contents):
Revision 1.3 by dl, Sun Dec 5 21:15:31 2004 UTC vs.
Revision 1.11 by jsr166, Wed Jan 16 00:51:11 2013 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea and Josh Bloch with assistance from members of
3		* JCP JSR-166 Expert Group and released to the public domain, as explained
4	<	* at http://creativecommons.org/licenses/publicdomain
4	>	* at http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		package jsr166x;     // XXX This belongs in java.util!!! XXX
8		import java.util.*;    // XXX This import goes away        XXX
9
10		/**
11	<	* A linear collection that supports element insertion and removal
12	<	* at both ends.  The name <i>deque</i> is short for "double ended
13	<	* queue" and is usually pronounced "deck".  Most <tt>Deque</tt>
11	>	* A linear collection that supports element insertion and removal at
12	>	* both ends.  The name <i>deque</i> is short for "double ended queue"
13	>	* and is usually pronounced "deck".  Most {@code Deque}
14		* implementations place no fixed limits on the number of elements
15		* they may contain, but this interface supports capacity-restricted
16		* deques as well as those with no fixed size limit.
17		*
18	<	* <p>This interface defines methods to access the elements at both ends of
19	<	* the deque.  Methods are provided to insert, remove, and examine the
20	<	* element.  Each of these methods exists in two forms: one throws an
21	<	* exception if the operation fails, the other returns a special value (either
22	<	* <tt>null</tt> or <tt>false</tt>, depending on the operation).  The latter
23	<	* form of the insert operation is designed specifically for use with
24	<	* capacity-restricted <tt>Deque</tt> implementations; in most implementations,
25	<	* insert operations cannot fail.
26	<	*
27	<	* <p>The twelve methods described above are are summarized in the
28	<	* follwoing table:<p>
29	<	*
18	>	* <p>This interface defines methods to access the elements at both
19	>	* ends of the deque.  Methods are provided to insert, remove, and
20	>	* examine the element.  Each of these methods exists in two forms:
21	>	* one throws an exception if the operation fails, the other returns a
22	>	* special value (either {@code null} or {@code false}, depending on
23	>	* the operation).  The latter form of the insert operation is
24	>	* designed specifically for use with capacity-restricted
25	>	* {@code Deque} implementations; in most implementations, insert
26	>	* operations cannot fail.
27	>	*
28	>	* <p>The twelve methods described above are summarized in the
29	>	* following table:<p>
30	>	*
31		* <table BORDER CELLPADDING=3 CELLSPACING=1>
32		*  <tr>
33		*    <td></td>
#	Line 56 | Line 57 | import java.util.*;    // XXX This impor
57		*  </tr>
58		*  <tr>
59		*    <td><b>Examine</b></td>
60	<	*    <td>{@link #firstElement firstElement()}</td>
60	>	*    <td>{@link #getFirst getFirst()}</td>
61		*    <td>{@link #peekFirst peekFirst()}</td>
62	<	*    <td>{@link #lastElement lastElement()}</td>
62	>	*    <td>{@link #getLast getLast()}</td>
63		*    <td>{@link #peekLast peekLast()}</td>
64		*  </tr>
65		* </table>
#	Line 66 | Line 67 | import java.util.*;    // XXX This impor
67		* <p>This interface extends the {@link Queue} interface.  When a deque is
68		* used as a queue, FIFO (First-In-First-Out) behavior results.  Elements are
69		* added to the end of the deque and removed from the beginning.  The methods
70	<	* inherited from the <tt>Queue</tt> interface are precisely equivalent to
71	<	* <tt>Deque</tt> methods as indicated in the following table:<p>
70	>	* inherited from the {@code Queue} interface are precisely equivalent to
71	>	* {@code Deque} methods as indicated in the following table:<p>
72		*
73		* <table BORDER CELLPADDING=3 CELLSPACING=1>
74		*  <tr>
75	<	*    <td ALIGN=CENTER> <b><tt>Queue</tt> Method</b></td>
76	<	*    <td ALIGN=CENTER> <b>Equivalent <tt>Deque</tt> Method</b></td>
75	>	*    <td ALIGN=CENTER> <b>{@code Queue} Method</b></td>
76	>	*    <td ALIGN=CENTER> <b>Equivalent {@code Deque} Method</b></td>
77		*  </tr>
78		*  <tr>
79		*   <tr>
#	Line 97 | Line 98 | import java.util.*;    // XXX This impor
98		*   </tr>
99		*   <tr>
100		*    <td>{@link java.util.Queue#element element()}</td>
101	<	*    <td>{@link #firstElement firstElement()}</td>
101	>	*    <td>{@link #getFirst getFirst()}</td>
102		*   </tr>
103		* </table>
104		*
#	Line 105 | Line 106 | import java.util.*;    // XXX This impor
106		* interface should be used in preference to the legacy {@link Stack} class.
107		* When a dequeue is used as a stack, elements are pushed and popped from the
108		* beginning of the deque.  Stack methods are precisely equivalent to
109	<	* <tt>Deque</tt> methods as indicated in the table below:<p>
109	>	* {@code Deque} methods as indicated in the table below:<p>
110		*
111		* <table BORDER CELLPADDING=3 CELLSPACING=1>
112		*  <tr>
113		*    <td ALIGN=CENTER> <b>Stack Method</b></td>
114	<	*    <td ALIGN=CENTER> <b>Equivalent <tt>Deque</tt> Method</b></td>
114	>	*    <td ALIGN=CENTER> <b>Equivalent {@code Deque} Method</b></td>
115		*  </tr>
116		*  <tr>
117		*   <tr>
#	Line 126 | Line 127 | import java.util.*;    // XXX This impor
127		*    <td>{@link #peekFirst peekFirst()}</td>
128		*   </tr>
129		* </table>
130	<	* <p>Note that the {@link #peek peek} method works equally well when a deque
131	<	* is used as a queue or a stack; in either case, elements are drawn from the
132	<	* beginning of the deque.
133	<	*
134	<	* <p>This inteface provides two methods to to remove interior elements,
135	<	* {@link #removeFirstOccurrence removeFirstOccurrence} and {@link
136	<	* #removeLastOccurrence removeLastOccurrence}.  Unlike the {@link List}
137	<	* interface, this interface does not provide support for indexed access to
138	<	* elements.
139	<	*
140	<	* <p>While <tt>Deque</tt> implementations are not strictly required to
141	<	* prohibit the insertion of null elements, they are strongly encouraged to do
142	<	* so.  Users of any <tt>Deque</tt> implementations that do allow null
143	<	* elements are strongly encouraged <i>not</i> to take advantage of the
144	<	* ability to insert nulls.  This is so because <tt>null</tt> is used as a
145	<	* special return value by various methods to indicated that the deque is
146	<	* empty.
147	<	*
148	<	* <p><tt>Deque</tt> implementations generally do not define
149	<	* element-based versions of the <tt>equals</tt> and <tt>hashCode</tt>
130	>	*
131	>	* <p>Note that the {@link #peek peek} method works equally well when
132	>	* a deque is used as a queue or a stack; in either case, elements are
133	>	* drawn from the beginning of the deque.
134	>	*
135	>	* <p>This interface provides two methods to remove interior
136	>	* elements, {@link #removeFirstOccurrence removeFirstOccurrence} and
137	>	* {@link #removeLastOccurrence removeLastOccurrence}.  Unlike the
138	>	* {@link List} interface, this interface does not provide support for
139	>	* indexed access to elements.
140	>	*
141	>	* <p>While {@code Deque} implementations are not strictly required
142	>	* to prohibit the insertion of null elements, they are strongly
143	>	* encouraged to do so.  Users of any {@code Deque} implementations
144	>	* that do allow null elements are strongly encouraged <i>not</i> to
145	>	* take advantage of the ability to insert nulls.  This is so because
146	>	* {@code null} is used as a special return value by various methods
147	>	* to indicated that the deque is empty.
148	>	*
149	>	* <p>{@code Deque} implementations generally do not define
150	>	* element-based versions of the {@code equals} and {@code hashCode}
151		* methods, but instead inherit the identity-based versions from class
152	<	* <tt>Object</tt>.
152	>	* {@code Object}.
153		*
154		* <p>This interface is a member of the <a
155		* href="{@docRoot}/../guide/collections/index.html"> Java Collections
#	Line 162 | Line 164 | public interface Deque<E> extends Queue<
164		/**
165		* Inserts the specified element to the front this deque unless it would
166		* violate capacity restrictions.  When using a capacity-restricted deque,
167	<	* this method is generally preferable to method <tt>addFirst</tt>, which
167	>	* this method is generally preferable to method {@code addFirst}, which
168		* can fail to insert an element only by throwing an exception.
169		*
170		* @param e the element to insert
171	<	* @return <tt>true</tt> if it was possible to insert the element,
172	<	*     else <tt>false</tt>
173	<	* @throws NullPointerException if <tt>e</tt> is null and this
171	>	* @return {@code true} if it was possible to insert the element,
172	>	*     else {@code false}
173	>	* @throws NullPointerException if {@code e} is null and this
174		*     deque does not permit null elements
175		*/
176		boolean offerFirst(E e);
#	Line 176 | Line 178 | public interface Deque<E> extends Queue<
178		/**
179		* Inserts the specified element to the end of this deque unless it would
180		* violate capacity restrictions.  When using a capacity-restricted deque,
181	<	* this method is generally preferable to method <tt>addLast</tt> which
181	>	* this method is generally preferable to method {@code addLast} which
182		* can fail to insert an element only by throwing an exception.
183		*
184		* @param e the element to insert
185	<	* @return <tt>true</tt> if it was possible to insert the element,
186	<	*     else <tt>false</tt>
187	<	* @throws NullPointerException if <tt>e</tt> is null and this
185	>	* @return {@code true} if it was possible to insert the element,
186	>	*     else {@code false}
187	>	* @throws NullPointerException if {@code e} is null and this
188		*     deque does not permit null elements
189		*/
190		boolean offerLast(E e);
#	Line 194 | Line 196 | public interface Deque<E> extends Queue<
196		* @param e the element to insert
197		* @throws IllegalStateException if it was not possible to insert
198		*    the element due to capacity restrictions
199	<	* @throws NullPointerException if <tt>e</tt> is null and this
199	>	* @throws NullPointerException if {@code e} is null and this
200		*     deque does not permit null elements
201		*/
202		void addFirst(E e);
#	Line 206 | Line 208 | public interface Deque<E> extends Queue<
208		* @param e the element to insert
209		* @throws IllegalStateException if it was not possible to insert
210		*    the element due to capacity restrictions
211	<	* @throws NullPointerException if <tt>e</tt> is null and this
211	>	* @throws NullPointerException if {@code e} is null and this
212		*     deque does not permit null elements
213		*/
214		void addLast(E e);
215
216		/**
217		* Retrieves and removes the first element of this deque, or
218	<	* <tt>null</tt> if this deque is empty.
218	>	* {@code null} if this deque is empty.
219		*
220	<	* @return the first element of this deque, or <tt>null</tt> if
220	>	* @return the first element of this deque, or {@code null} if
221		*     this deque is empty
222		*/
223		E pollFirst();
224
225		/**
226		* Retrieves and removes the last element of this deque, or
227	<	* <tt>null</tt> if this deque is empty.
227	>	* {@code null} if this deque is empty.
228		*
229	<	* @return the last element of this deque, or <tt>null</tt> if
229	>	* @return the last element of this deque, or {@code null} if
230		*     this deque is empty
231		*/
232		E pollLast();
233
234		/**
235		* Removes and returns the first element of this deque.  This method
236	<	* differs from the <tt>pollFirst</tt> method only in that it throws an
236	>	* differs from the {@code pollFirst} method only in that it throws an
237		* exception if this deque is empty.
238		*
239		* @return the first element of this deque
#	Line 241 | Line 243 | public interface Deque<E> extends Queue<
243
244		/**
245		* Retrieves and removes the last element of this deque.  This method
246	<	* differs from the <tt>pollLast</tt> method only in that it throws an
246	>	* differs from the {@code pollLast} method only in that it throws an
247		* exception if this deque is empty.
248		*
249		* @return the last element of this deque
#	Line 251 | Line 253 | public interface Deque<E> extends Queue<
253
254		/**
255		* Retrieves, but does not remove, the first element of this deque,
256	<	* returning <tt>null</tt> if this deque is empty.
256	>	* returning {@code null} if this deque is empty.
257		*
258	<	* @return the first element of this deque, or <tt>null</tt> if
258	>	* @return the first element of this deque, or {@code null} if
259		*     this deque is empty
260		*/
261		E peekFirst();
262
263		/**
264		* Retrieves, but does not remove, the last element of this deque,
265	<	* returning <tt>null</tt> if this deque is empty.
265	>	* returning {@code null} if this deque is empty.
266		*
267	<	* @return the last element of this deque, or <tt>null</tt> if this deque
267	>	* @return the last element of this deque, or {@code null} if this deque
268		*     is empty
269		*/
270		E peekLast();
271
272		/**
273		* Retrieves, but does not remove, the first element of this
274	<	* deque.  This method differs from the <tt>peek</tt> method only
274	>	* deque.  This method differs from the {@code peek} method only
275		* in that it throws an exception if this deque is empty.
276		*
277		* @return the first element of this deque
278		* @throws NoSuchElementException if this deque is empty
279		*/
280	<	E firstElement();
280	>	E getFirst();
281
282		/**
283		* Retrieves, but does not remove, the last element of this
284	<	* deque.  This method differs from the <tt>peek</tt> method only
284	>	* deque.  This method differs from the {@code peek} method only
285		* in that it throws an exception if this deque is empty.
286		*
287		* @return the last element of this deque
288		* @throws NoSuchElementException if this deque is empty
289		*/
290	<	E lastElement();
290	>	E getLast();
291
292		/**
293		* Removes the first occurrence of the specified element in this
294		* deque.  If the deque does not contain the element, it is
295	<	* unchanged.  More formally, removes the first element <tt>e</tt>
296	<	* such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
295	>	* unchanged.  More formally, removes the first element {@code e}
296	>	* such that {@code (o==null ? e==null : o.equals(e))} (if
297		* such an element exists).
298		*
299		* @param e element to be removed from this deque, if present
300	<	* @return <tt>true</tt> if the deque contained the specified element
301	<	* @throws NullPointerException if the specified element is <tt>null</tt>
300	>	* @return {@code true} if the deque contained the specified element
301	>	* @throws NullPointerException if the specified element is {@code null}
302		*/
303		boolean removeFirstOccurrence(Object e);
304
305		/**
306		* Removes the last occurrence of the specified element in this
307		* deque.  If the deque does not contain the element, it is
308	<	* unchanged.  More formally, removes the last element <tt>e</tt>
309	<	* such that <tt>(o==null ? e==null : o.equals(e))</tt> (if
308	>	* unchanged.  More formally, removes the last element {@code e}
309	>	* such that {@code (o==null ? e==null : o.equals(e))} (if
310		* such an element exists).
311		*
312		* @param e element to be removed from this deque, if present
313	<	* @return <tt>true</tt> if the deque contained the specified element
314	<	* @throws NullPointerException if the specified element is <tt>null</tt>
313	>	* @return {@code true} if the deque contained the specified element
314	>	* @throws NullPointerException if the specified element is {@code null}
315		*/
316		boolean removeLastOccurrence(Object e);
317
#	Line 327 | Line 329 | public interface Deque<E> extends Queue<
329		* <p>This method is equivalent to {@link #offerLast}.
330		*
331		* @param e the element to insert
332	<	* @return <tt>true</tt> if it was possible to insert the element,
333	<	*     else <tt>false</tt>
334	<	* @throws NullPointerException if <tt>e</tt> is null and this
332	>	* @return {@code true} if it was possible to insert the element,
333	>	*     else {@code false}
334	>	* @throws NullPointerException if {@code e} is null and this
335		*     deque does not permit null elements
336		*/
337		boolean offer(E e);
#	Line 337 | Line 339 | public interface Deque<E> extends Queue<
339		/**
340		* Inserts the specified element into the queue represented by this
341		* deque unless it would violate capacity restrictions.  In other words,
342	<	* inserts the specified element as the last element of this deque.
342	>	* inserts the specified element as the last element of this deque.
343		*
344		* <p>This method is equivalent to {@link #addLast}.
345		*
346		* @param e the element to insert
347	<	* @return <tt>true</tt> (as per the spec for {@link Collection#add})
347	>	* @return {@code true} (as per the spec for {@link Collection#add})
348		* @throws IllegalStateException if it was not possible to insert
349		*    the element due to capacity restrictions
350	<	* @throws NullPointerException if <tt>e</tt> is null and this
350	>	* @throws NullPointerException if {@code e} is null and this
351		*     deque does not permit null elements
352		*/
353		boolean add(E e);
354
355		/**
356		* Retrieves and removes the head of the queue represented by
357	<	* this deque, or <tt>null</tt> if this deque is empty.  In other words,
358	<	* retrieves and removes the first element of this deque, or <tt>null</tt>
357	>	* this deque, or {@code null} if this deque is empty.  In other words,
358	>	* retrieves and removes the first element of this deque, or {@code null}
359		* if this deque is empty.
360		*
361		* <p>This method is equivalent to {@link #pollFirst()}.
362		*
363	<	* @return the first element of this deque, or <tt>null</tt> if
363	>	* @return the first element of this deque, or {@code null} if
364		*     this deque is empty
365		*/
366		E poll();
367
368		/**
369		* Retrieves and removes the head of the queue represented by this deque.
370	<	* This method differs from the <tt>poll</tt> method only in that it
370	>	* This method differs from the {@code poll} method only in that it
371		* throws an exception if this deque is empty.
372		*
373		* <p>This method is equivalent to {@link #removeFirst()}.
#	Line 377 | Line 379 | public interface Deque<E> extends Queue<
379
380		/**
381		* Retrieves, but does not remove, the head of the queue represented by
382	<	* this deque, returning <tt>null</tt> if this deque is empty.
382	>	* this deque, returning {@code null} if this deque is empty.
383		*
384		* <p>This method is equivalent to {@link #peekFirst()}
385		*
386		* @return the head of the queue represented by this deque, or
387	<	*     <tt>null</tt> if this deque is empty
387	>	*     {@code null} if this deque is empty
388		*/
389		E peek();
390
391		/**
392		* Retrieves, but does not remove, the head of the queue represented by
393	<	* this deque.  This method differs from the <tt>peek</tt> method only in
393	>	* this deque.  This method differs from the {@code peek} method only in
394		* that it throws an exception if this deque is empty.
395		*
396	<	* <p>This method is equivalent to {@link #firstElement()}
396	>	* <p>This method is equivalent to {@link #getFirst()}
397		*
398		* @return the head of the queue represented by this deque
399		* @throws NoSuchElementException if this deque is empty
#	Line 410 | Line 412 | public interface Deque<E> extends Queue<
412		*
413		* @throws IllegalStateException if it was not possible to insert
414		*    the element due to capacity restrictions
415	<	* @throws NullPointerException if <tt>e</tt> is null and this
415	>	* @throws NullPointerException if {@code e} is null and this
416		*     deque does not permit null elements
417		*/
418		void push(E e);
419
420		/**
421		* Pops an element from the stack represented by this deque.  In other
422	<	* words, removes and returns the the first element of this deque.
422	>	* words, removes and returns the first element of this deque.
423		*
424		* <p>This method is equivalent to {@link #removeFirst()}.
425		*
#	Line 433 | Line 435 | public interface Deque<E> extends Queue<
435		/**
436		* Returns an iterator over the elements in this deque.  The elements
437		* will be ordered from first (head) to last (tail).
438	<	*
439	<	* @return an <tt>Iterator</tt> over the elements in this deque
438	>	*
439	>	* @return an {@code Iterator} over the elements in this deque
440		*/
441		Iterator<E> iterator();
442		}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines