Home » openjdk-7 » java » util » [javadoc | source]

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

Home » openjdk-7 » java » util » [javadoc | source]