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

Diff Legend

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