12f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson/* 22f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Written by Doug Lea with assistance from members of JCP JSR-166 32f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Expert Group and released to the public domain, as explained at 4a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util; 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 92f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson// BEGIN android-note 102f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson// removed link to collections framework docs 112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson// END android-note 122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * This class provides skeletal implementations of some {@link Queue} 152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * operations. The implementations in this class are appropriate when 162f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * the base implementation does <em>not</em> allow <tt>null</tt> 172f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * elements. Methods {@link #add add}, {@link #remove remove}, and 182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * {@link #element element} are based on {@link #offer offer}, {@link 192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * #poll poll}, and {@link #peek peek}, respectively, but throw 202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * exceptions instead of indicating failure via <tt>false</tt> or 212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt> returns. 222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>A <tt>Queue</tt> implementation that extends this class must 242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * minimally define a method {@link Queue#offer} which does not permit 252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * insertion of <tt>null</tt> elements, along with methods {@link 262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Queue#peek}, {@link Queue#poll}, {@link Collection#size}, and 272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * {@link Collection#iterator}. Typically, additional methods will be 282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * overridden as well. If these requirements cannot be met, consider 292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * instead subclassing {@link AbstractCollection}. 30f5597e626ecf7949d249dea08c1a2964d890ec11Jesse Wilson * 312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @since 1.5 322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @author Doug Lea 332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param <E> the type of elements held in this collection 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilsonpublic abstract class AbstractQueue<E> 362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson extends AbstractCollection<E> 372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson implements Queue<E> { 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 39adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Constructor for use by subclasses. 41adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 42adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project protected AbstractQueue() { 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 45adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Inserts the specified element into this queue if it is possible to do so 472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * immediately without violating capacity restrictions, returning 482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>true</tt> upon success and throwing an <tt>IllegalStateException</tt> 492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * if no space is currently available. 50f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This implementation returns <tt>true</tt> if <tt>offer</tt> succeeds, 522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * else throws an <tt>IllegalStateException</tt>. 532f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param e the element to add 552f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> (as specified by {@link Collection#add}) 562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws IllegalStateException if the element cannot be added at this 572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * time due to capacity restrictions 582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws ClassCastException if the class of the specified element 592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * prevents it from being added to this queue 602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified element is null and 612f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this queue does not permit null elements 622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws IllegalArgumentException if some property of this element 632f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * prevents it from being added to this queue 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 652f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean add(E e) { 662f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (offer(e)) 67adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 682f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson else 692f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson throw new IllegalStateException("Queue full"); 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 732f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves and removes the head of this queue. This method differs 742f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * from {@link #poll poll} only in that it throws an exception if this 752f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * queue is empty. 76f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 772f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This implementation returns the result of <tt>poll</tt> 782f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * unless the queue is empty. 79f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 802f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of this queue 812f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException if this queue is empty 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E remove() { 842f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x = poll(); 852f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (x != null) 862f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return x; 872f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson else 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 922f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Retrieves, but does not remove, the head of this queue. This method 932f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * differs from {@link #peek peek} only in that it throws an exception if 942f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this queue is empty. 95f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 962f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This implementation returns the result of <tt>peek</tt> 972f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * unless the queue is empty. 982f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 992f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return the head of this queue 1002f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NoSuchElementException if this queue is empty 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public E element() { 1032f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson E x = peek(); 1042f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (x != null) 1052f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return x; 1062f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson else 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project throw new NoSuchElementException(); 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1112f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Removes all of the elements from this queue. 1122f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * The queue will be empty after this call returns. 1132f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 1142f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This implementation repeatedly invokes {@link #poll poll} until it 1152f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * returns <tt>null</tt>. 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void clear() { 1182f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson while (poll() != null) 1192f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson ; 1202f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson } 1212f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 1222f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson /** 1232f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * Adds all of the elements in the specified collection to this 1242f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * queue. Attempts to addAll of a queue to itself result in 1252f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>IllegalArgumentException</tt>. Further, the behavior of 1262f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this operation is undefined if the specified collection is 1272f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * modified while the operation is in progress. 1282f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 1292f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <p>This implementation iterates over the specified collection, 1302f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * and adds each element returned by the iterator to this 1312f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * queue, in turn. A runtime exception encountered while 1322f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * trying to add an element (including, in particular, a 1332f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * <tt>null</tt> element) may result in only some of the elements 1342f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * having been successfully added when the associated exception is 1352f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * thrown. 1362f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * 1372f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @param c collection containing elements to be added to this queue 1382f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @return <tt>true</tt> if this queue changed as a result of the call 1392f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws ClassCastException if the class of an element of the specified 1402f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * collection prevents it from being added to this queue 1412f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws NullPointerException if the specified collection contains a 1422f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * null element and this queue does not permit null elements, 1432f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * or if the specified collection is null 1442f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws IllegalArgumentException if some property of an element of the 1452f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * specified collection prevents it from being added to this 1462f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * queue, or if the specified collection is this queue 1472f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @throws IllegalStateException if not all the elements can be added at 1482f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * this time due to insertion restrictions 1492f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson * @see #add(Object) 1502f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson */ 1512f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson public boolean addAll(Collection<? extends E> c) { 1522f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (c == null) 15386acc043d3334651ee26c65467d78d6cefedd397Kenny Root throw new NullPointerException("c == null"); 1542f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (c == this) 15586acc043d3334651ee26c65467d78d6cefedd397Kenny Root throw new IllegalArgumentException("c == this"); 1562f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson boolean modified = false; 1572f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson for (E e : c) 1582f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson if (add(e)) 1592f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson modified = true; 1602f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson return modified; 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1622f03027aaa09158ac70ebf9c6b53f7bb8c495541Jesse Wilson 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 164