lib/classpath/external/jsr166/java/util/Deque.java

   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
   5  */
   6
   7 package java.util;
   8
   9 /**
  10  * A linear collection that supports element insertion and removal at
  11  * both ends.  The name <i>deque</i> is short for "double ended queue"
  12  * and is usually pronounced "deck".  Most <tt>Deque</tt>
  13  * implementations place no fixed limits on the number of elements
  14  * they may contain, but this interface supports capacity-restricted
  15  * deques as well as those with no fixed size limit.
  16  *
  17  * <p>This interface defines methods to access the elements at both
  18  * ends of the deque.  Methods are provided to insert, remove, and
  19  * examine the element.  Each of these methods exists in two forms:
  20  * one throws an exception if the operation fails, the other returns a
  21  * special value (either <tt>null</tt> or <tt>false</tt>, depending on
  22  * the operation).  The latter form of the insert operation is
  23  * designed specifically for use with capacity-restricted
  24  * <tt>Deque</tt> implementations; in most implementations, insert
  25  * operations cannot fail.
  26  *
  27  * <p>The twelve methods described above are summarized in the
  28  * following table:
  29  *
  30  * <p>
  31  * <table BORDER CELLPADDING=3 CELLSPACING=1>
  32  *  <tr>
  33  *    <td></td>
  34  *    <td ALIGN=CENTER COLSPAN = 2> <b>First Element (Head)</b></td>
  35  *    <td ALIGN=CENTER COLSPAN = 2> <b>Last Element (Tail)</b></td>
  36  *  </tr>
  37  *  <tr>
  38  *    <td></td>
  39  *    <td ALIGN=CENTER><em>Throws exception</em></td>
  40  *    <td ALIGN=CENTER><em>Special value</em></td>
  41  *    <td ALIGN=CENTER><em>Throws exception</em></td>
  42  *    <td ALIGN=CENTER><em>Special value</em></td>
  43  *  </tr>
  44  *  <tr>
  45  *    <td><b>Insert</b></td>
  46  *    <td>{@link #addFirst addFirst(e)}</td>
  47  *    <td>{@link #offerFirst offerFirst(e)}</td>
  48  *    <td>{@link #addLast addLast(e)}</td>
  49  *    <td>{@link #offerLast offerLast(e)}</td>
  50  *  </tr>
  51  *  <tr>
  52  *    <td><b>Remove</b></td>
  53  *    <td>{@link #removeFirst removeFirst()}</td>
  54  *    <td>{@link #pollFirst pollFirst()}</td>
  55  *    <td>{@link #removeLast removeLast()}</td>
  56  *    <td>{@link #pollLast pollLast()}</td>
  57  *  </tr>
  58  *  <tr>
  59  *    <td><b>Examine</b></td>
  60  *    <td>{@link #getFirst getFirst()}</td>
  61  *    <td>{@link #peekFirst peekFirst()}</td>
  62  *    <td>{@link #getLast getLast()}</td>
  63  *    <td>{@link #peekLast peekLast()}</td>
  64  *  </tr>
  65  * </table>
  66  *
  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 at 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:
  72  *
  73  * <p>
  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>
  78  *  </tr>
  79  *  <tr>
  80  *    <td>{@link java.util.Queue#add add(e)}</td>
  81  *    <td>{@link #addLast addLast(e)}</td>
  82  *  </tr>
  83  *  <tr>
  84  *    <td>{@link java.util.Queue#offer offer(e)}</td>
  85  *    <td>{@link #offerLast offerLast(e)}</td>
  86  *  </tr>
  87  *  <tr>
  88  *    <td>{@link java.util.Queue#remove remove()}</td>
  89  *    <td>{@link #removeFirst removeFirst()}</td>
  90  *  </tr>
  91  *  <tr>
  92  *    <td>{@link java.util.Queue#poll poll()}</td>
  93  *    <td>{@link #pollFirst pollFirst()}</td>
  94  *  </tr>
  95  *  <tr>
  96  *    <td>{@link java.util.Queue#element element()}</td>
  97  *    <td>{@link #getFirst getFirst()}</td>
  98  *  </tr>
  99  *  <tr>
 100  *    <td>{@link java.util.Queue#peek peek()}</td>
 101  *    <td>{@link #peek peekFirst()}</td>
 102  *  </tr>
 103  * </table>
 104  *
 105  * <p>Deques can also be used as LIFO (Last-In-First-Out) stacks.  This
 106  * interface should be used in preference to the legacy {@link Stack} class.
 107  * When a deque 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:
 110  *
 111  * <p>
 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>
 116  *  </tr>
 117  *  <tr>
 118  *    <td>{@link #push push(e)}</td>
 119  *    <td>{@link #addFirst addFirst(e)}</td>
 120  *  </tr>
 121  *  <tr>
 122  *    <td>{@link #pop pop()}</td>
 123  *    <td>{@link #removeFirst removeFirst()}</td>
 124  *  </tr>
 125  *  <tr>
 126  *    <td>{@link #peek peek()}</td>
 127  *    <td>{@link #peekFirst peekFirst()}</td>
 128  *  </tr>
 129  * </table>
 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}.
 138  *
 139  * <p>Unlike the {@link List} interface, this interface does not
 140  * provide support for indexed access to elements.
 141  *
 142  * <p>While <tt>Deque</tt> implementations are not strictly required
 143  * to prohibit the insertion of null elements, they are strongly
 144  * encouraged to do so.  Users of any <tt>Deque</tt> 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  * <tt>null</tt> is used as a special return value by various methods
 148  * to indicated that the deque is empty.
 149  *
 150  * <p><tt>Deque</tt> implementations generally do not define
 151  * element-based versions of the <tt>equals</tt> and <tt>hashCode</tt>
 152  * methods, but instead inherit the identity-based versions from class
 153  * <tt>Object</tt>.
 154  *
 155  * <p>This interface is a member of the <a
 156  * href="{@docRoot}/../technotes/guides/collections/index.html"> Java Collections
 157  * Framework</a>.
 158  *
 159  * @author Doug Lea
 160  * @author Josh Bloch
 161  * @since  1.6
 162  * @param <E> the type of elements held in this collection
 163  */
 164
 165 public interface Deque<E> extends Queue<E> {
 166     /**
 167      * Inserts the specified element at the front of this deque if it is
 168      * possible to do so immediately without violating capacity restrictions.
 169      * When using a capacity-restricted deque, it is generally preferable to
 170      * use method {@link #offerFirst}.
 171      *
 172      * @param e the element to add
 173      * @throws IllegalStateException if the element cannot be added at this
 174      *         time due to capacity restrictions
 175      * @throws ClassCastException if the class of the specified element
 176      *         prevents it from being added to this deque
 177      * @throws NullPointerException if the specified element is null and this
 178      *         deque does not permit null elements
 179      * @throws IllegalArgumentException if some property of the specified
 180      *         element prevents it from being added to this deque
 181      */
 182     void addFirst(E e);
 183
 184     /**
 185      * Inserts the specified element at the end of this deque if it is
 186      * possible to do so immediately without violating capacity restrictions.
 187      * When using a capacity-restricted deque, it is generally preferable to
 188      * use method {@link #offerLast}.
 189      *
 190      * <p>This method is equivalent to {@link #add}.
 191      *
 192      * @param e the element to add
 193      * @throws IllegalStateException if the element cannot be added at this
 194      *         time due to capacity restrictions
 195      * @throws ClassCastException if the class of the specified element
 196      *         prevents it from being added to this deque
 197      * @throws NullPointerException if the specified element is null and this
 198      *         deque does not permit null elements
 199      * @throws IllegalArgumentException if some property of the specified
 200      *         element prevents it from being added to this deque
 201      */
 202     void addLast(E e);
 203
 204     /**
 205      * Inserts the specified element at the front of this deque unless it would
 206      * violate capacity restrictions.  When using a capacity-restricted deque,
 207      * this method is generally preferable to the {@link #addFirst} method,
 208      * which can fail to insert an element only by throwing an exception.
 209      *
 210      * @param e the element to add
 211      * @return <tt>true</tt> if the element was added to this deque, else
 212      *         <tt>false</tt>
 213      * @throws ClassCastException if the class of the specified element
 214      *         prevents it from being added to this deque
 215      * @throws NullPointerException if the specified element is null and this
 216      *         deque does not permit null elements
 217      * @throws IllegalArgumentException if some property of the specified
 218      *         element prevents it from being added to this deque
 219      */
 220     boolean offerFirst(E e);
 221
 222     /**
 223      * Inserts the specified element at the end of this deque unless it would
 224      * violate capacity restrictions.  When using a capacity-restricted deque,
 225      * this method is generally preferable to the {@link #addLast} method,
 226      * which can fail to insert an element only by throwing an exception.
 227      *
 228      * @param e the element to add
 229      * @return <tt>true</tt> if the element was added to this deque, else
 230      *         <tt>false</tt>
 231      * @throws ClassCastException if the class of the specified element
 232      *         prevents it from being added to this deque
 233      * @throws NullPointerException if the specified element is null and this
 234      *         deque does not permit null elements
 235      * @throws IllegalArgumentException if some property of the specified
 236      *         element prevents it from being added to this deque
 237      */
 238     boolean offerLast(E e);
 239
 240     /**
 241      * Retrieves and removes the first element of this deque.  This method
 242      * differs from {@link #pollFirst pollFirst} only in that it throws an
 243      * exception if this deque is empty.
 244      *
 245      * @return the head of this deque
 246      * @throws NoSuchElementException if this deque is empty
 247      */
 248     E removeFirst();
 249
 250     /**
 251      * Retrieves and removes the last element of this deque.  This method
 252      * differs from {@link #pollLast pollLast} only in that it throws an
 253      * exception if this deque is empty.
 254      *
 255      * @return the tail of this deque
 256      * @throws NoSuchElementException if this deque is empty
 257      */
 258     E removeLast();
 259
 260     /**
 261      * Retrieves and removes the first element of this deque,
 262      * or returns <tt>null</tt> if this deque is empty.
 263      *
 264      * @return the head of this deque, or <tt>null</tt> if this deque is empty
 265      */
 266     E pollFirst();
 267
 268     /**
 269      * Retrieves and removes the last element of this deque,
 270      * or returns <tt>null</tt> if this deque is empty.
 271      *
 272      * @return the tail of this deque, or <tt>null</tt> if this deque is empty
 273      */
 274     E pollLast();
 275
 276     /**
 277      * Retrieves, but does not remove, the first element of this deque.
 278      *
 279      * This method differs from {@link #peekFirst peekFirst} only in that it
 280      * throws an exception if this deque is empty.
 281      *
 282      * @return the head of this deque
 283      * @throws NoSuchElementException if this deque is empty
 284      */
 285     E getFirst();
 286
 287     /**
 288      * Retrieves, but does not remove, the last element of this deque.
 289      * This method differs from {@link #peekLast peekLast} only in that it
 290      * throws an exception if this deque is empty.
 291      *
 292      * @return the tail of this deque
 293      * @throws NoSuchElementException if this deque is empty
 294      */
 295     E getLast();
 296
 297     /**
 298      * Retrieves, but does not remove, the first element of this deque,
 299      * or returns <tt>null</tt> if this deque is empty.
 300      *
 301      * @return the head of this deque, or <tt>null</tt> if this deque is empty
 302      */
 303     E peekFirst();
 304
 305     /**
 306      * Retrieves, but does not remove, the last element of this deque,
 307      * or returns <tt>null</tt> if this deque is empty.
 308      *
 309      * @return the tail of this deque, or <tt>null</tt> if this deque is empty
 310      */
 311     E peekLast();
 312
 313     /**
 314      * Removes the first occurrence of the specified element from this deque.
 315      * If the deque does not contain the element, it is unchanged.
 316      * More formally, removes the first element <tt>e</tt> such that
 317      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
 318      * (if such an element exists).
 319      * Returns <tt>true</tt> if this deque contained the specified element
 320      * (or equivalently, if this deque changed as a result of the call).
 321      *
 322      * @param o element to be removed from this deque, if present
 323      * @return <tt>true</tt> if an element was removed as a result of this call
 324      * @throws ClassCastException if the class of the specified element
 325      *         is incompatible with this deque (optional)
 326      * @throws NullPointerException if the specified element is null and this
 327      *         deque does not permit null elements (optional)
 328      */
 329     boolean removeFirstOccurrence(Object o);
 330
 331     /**
 332      * Removes the last occurrence of the specified element from this deque.
 333      * If the deque does not contain the element, it is unchanged.
 334      * More formally, removes the last element <tt>e</tt> such that
 335      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
 336      * (if such an element exists).
 337      * Returns <tt>true</tt> if this deque contained the specified element
 338      * (or equivalently, if this deque changed as a result of the call).
 339      *
 340      * @param o element to be removed from this deque, if present
 341      * @return <tt>true</tt> if an element was removed as a result of this call
 342      * @throws ClassCastException if the class of the specified element
 343      *         is incompatible with this deque (optional)
 344      * @throws NullPointerException if the specified element is null and this
 345      *         deque does not permit null elements (optional)
 346      */
 347     boolean removeLastOccurrence(Object o);
 348
 349     // *** Queue methods ***
 350
 351     /**
 352      * Inserts the specified element into the queue represented by this deque
 353      * (in other words, at the tail of this deque) if it is possible to do so
 354      * immediately without violating capacity restrictions, returning
 355      * <tt>true</tt> upon success and throwing an
 356      * <tt>IllegalStateException</tt> if no space is currently available.
 357      * When using a capacity-restricted deque, it is generally preferable to
 358      * use {@link #offer(Object) offer}.
 359      *
 360      * <p>This method is equivalent to {@link #addLast}.
 361      *
 362      * @param e the element to add
 363      * @return <tt>true</tt> (as specified by {@link Collection#add})
 364      * @throws IllegalStateException if the element cannot be added at this
 365      *         time due to capacity restrictions
 366      * @throws ClassCastException if the class of the specified element
 367      *         prevents it from being added to this deque
 368      * @throws NullPointerException if the specified element is null and this
 369      *         deque does not permit null elements
 370      * @throws IllegalArgumentException if some property of the specified
 371      *         element prevents it from being added to this deque
 372      */
 373     boolean add(E e);
 374
 375     /**
 376      * Inserts the specified element into the queue represented by this deque
 377      * (in other words, at the tail of this deque) if it is possible to do so
 378      * immediately without violating capacity restrictions, returning
 379      * <tt>true</tt> upon success and <tt>false</tt> if no space is currently
 380      * available.  When using a capacity-restricted deque, this method is
 381      * generally preferable to the {@link #add} method, which can fail to
 382      * insert an element only by throwing an exception.
 383      *
 384      * <p>This method is equivalent to {@link #offerLast}.
 385      *
 386      * @param e the element to add
 387      * @return <tt>true</tt> if the element was added to this deque, else
 388      *         <tt>false</tt>
 389      * @throws ClassCastException if the class of the specified element
 390      *         prevents it from being added to this deque
 391      * @throws NullPointerException if the specified element is null and this
 392      *         deque does not permit null elements
 393      * @throws IllegalArgumentException if some property of the specified
 394      *         element prevents it from being added to this deque
 395      */
 396     boolean offer(E e);
 397
 398     /**
 399      * Retrieves and removes the head of the queue represented by this deque
 400      * (in other words, the first element of this deque).
 401      * This method differs from {@link #poll poll} only in that it throws an
 402      * exception if this deque is empty.
 403      *
 404      * <p>This method is equivalent to {@link #removeFirst()}.
 405      *
 406      * @return the head of the queue represented by this deque
 407      * @throws NoSuchElementException if this deque is empty
 408      */
 409     E remove();
 410
 411     /**
 412      * Retrieves and removes the head of the queue represented by this deque
 413      * (in other words, the first element of this deque), or returns
 414      * <tt>null</tt> if this deque is empty.
 415      *
 416      * <p>This method is equivalent to {@link #pollFirst()}.
 417      *
 418      * @return the first element of this deque, or <tt>null</tt> if
 419      *         this deque is empty
 420      */
 421     E poll();
 422
 423     /**
 424      * Retrieves, but does not remove, the head of the queue represented by
 425      * this deque (in other words, the first element of this deque).
 426      * This method differs from {@link #peek peek} only in that it throws an
 427      * exception if this deque is empty.
 428      *
 429      * <p>This method is equivalent to {@link #getFirst()}.
 430      *
 431      * @return the head of the queue represented by this deque
 432      * @throws NoSuchElementException if this deque is empty
 433      */
 434     E element();
 435
 436     /**
 437      * Retrieves, but does not remove, the head of the queue represented by
 438      * this deque (in other words, the first element of this deque), or
 439      * returns <tt>null</tt> if this deque is empty.
 440      *
 441      * <p>This method is equivalent to {@link #peekFirst()}.
 442      *
 443      * @return the head of the queue represented by this deque, or
 444      *         <tt>null</tt> if this deque is empty
 445      */
 446     E peek();
 447
 448
 449     // *** Stack methods ***
 450
 451     /**
 452      * Pushes an element onto the stack represented by this deque (in other
 453      * words, at the head of this deque) if it is possible to do so
 454      * immediately without violating capacity restrictions, returning
 455      * <tt>true</tt> upon success and throwing an
 456      * <tt>IllegalStateException</tt> if no space is currently available.
 457      *
 458      * <p>This method is equivalent to {@link #addFirst}.
 459      *
 460      * @param e the element to push
 461      * @throws IllegalStateException if the element cannot be added at this
 462      *         time due to capacity restrictions
 463      * @throws ClassCastException if the class of the specified element
 464      *         prevents it from being added to this deque
 465      * @throws NullPointerException if the specified element is null and this
 466      *         deque does not permit null elements
 467      * @throws IllegalArgumentException if some property of the specified
 468      *         element prevents it from being added to this deque
 469      */
 470     void push(E e);
 471
 472     /**
 473      * Pops an element from the stack represented by this deque.  In other
 474      * words, removes and returns the first element of this deque.
 475      *
 476      * <p>This method is equivalent to {@link #removeFirst()}.
 477      *
 478      * @return the element at the front of this deque (which is the top
 479      *         of the stack represented by this deque)
 480      * @throws NoSuchElementException if this deque is empty
 481      */
 482     E pop();
 483
 484
 485     // *** Collection methods ***
 486
 487     /**
 488      * Removes the first occurrence of the specified element from this deque.
 489      * If the deque does not contain the element, it is unchanged.
 490      * More formally, removes the first element <tt>e</tt> such that
 491      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>
 492      * (if such an element exists).
 493      * Returns <tt>true</tt> if this deque contained the specified element
 494      * (or equivalently, if this deque changed as a result of the call).
 495      *
 496      * <p>This method is equivalent to {@link #removeFirstOccurrence}.
 497      *
 498      * @param o element to be removed from this deque, if present
 499      * @return <tt>true</tt> if an element was removed as a result of this call
 500      * @throws ClassCastException if the class of the specified element
 501      *         is incompatible with this deque (optional)
 502      * @throws NullPointerException if the specified element is null and this
 503      *         deque does not permit null elements (optional)
 504      */
 505     boolean remove(Object o);
 506
 507     /**
 508      * Returns <tt>true</tt> if this deque contains the specified element.
 509      * More formally, returns <tt>true</tt> if and only if this deque contains
 510      * at least one element <tt>e</tt> such that
 511      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 512      *
 513      * @param o element whose presence in this deque is to be tested
 514      * @return <tt>true</tt> if this deque contains the specified element
 515      * @throws ClassCastException if the type of the specified element
 516      *         is incompatible with this deque (optional)
 517      * @throws NullPointerException if the specified element is null and this
 518      *         deque does not permit null elements (optional)
 519      */
 520     boolean contains(Object o);
 521
 522     /**
 523      * Returns the number of elements in this deque.
 524      *
 525      * @return the number of elements in this deque
 526      */
 527     public int size();
 528
 529     /**
 530      * Returns an iterator over the elements in this deque in proper sequence.
 531      * The elements will be returned in order from first (head) to last (tail).
 532      *
 533      * @return an iterator over the elements in this deque in proper sequence
 534      */
 535     Iterator<E> iterator();
 536
 537     /**
 538      * Returns an iterator over the elements in this deque in reverse
 539      * sequential order.  The elements will be returned in order from
 540      * last (tail) to first (head).
 541      *
 542      * @return an iterator over the elements in this deque in reverse
 543      * sequence
 544      */
 545     Iterator<E> descendingIterator();
 546
 547 }