Imported JSR 166 reference implementation:

	* .classpath: Added external/jsr166.
	* java/util/concurrent/CopyOnWriteArrayList.java: New file.
	* java/util/AbstractQueue.java: Removed.
	* java/util/Queue.java: Removed.
	* external/jsr166/java/util/concurrent/ScheduledThreadPoolExecutor.java
	(runPeriodic): Added explicit cast.
	* external/jsr166/java/util/ArrayDeque.java (clone): Use
	elements.clone.

7 files changed, 1917 insertions, 146 deletions

diff --git a/.classpath b/.classpath
index 611ba22c6..f4ba74e8d 100644
--- a/.classpath
+++ b/.classpath
@@ -1,7 +1,8 @@
 <?xml version="1.0" encoding="UTF-8"?>
 <classpath>
-	<classpathentry excluding=".externalToolBuilders/|.settings/|ChangeLog*|Makefile*|autom4te.cache/|compat/|config*|doc/|examples/|external/|external/relaxngDatatype/|include/|install/|lib/|m4/|native/|resource/|scripts/|test/|testsuite/|tools/|vm/reference/" kind="src" path=""/>
+	<classpathentry excluding=".externalToolBuilders/|.settings/|ChangeLog*|Makefile*|autom4te.cache/|compat/|config*|doc/|examples/|external/|external/relaxngDatatype/|include/|install/|jessie-tests/|lib/|m4/|native/|resource/|scripts/|test/|testsuite/|tools/|vm/reference/" kind="src" path=""/>
 	<classpathentry excluding=".cvsignore|Makefile|Makefile.am|Makefile.in|README.txt" kind="src" path="external/relaxngDatatype"/>
+	<classpathentry kind="src" path="external/jsr166"/>
 	<classpathentry excluding=".cvsignore|Makefile|Makefile.am|Makefile.in|README" kind="src" path="tools"/>
 	<classpathentry excluding=".cvsignore|Makefile|Makefile.am|Makefile.in" kind="src" path="resource"/>
 	<classpathentry excluding=".cvsignore|Makefile.am" kind="src" path="vm/reference"/>
diff --git a/ChangeLog b/ChangeLog
index b5703cc4d..a45cc1174 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,17 @@
 2006-06-16  Tom Tromey  <tromey@redhat.com>
 
+	Imported JSR 166 reference implementation:
+	* .classpath: Added external/jsr166.
+	* java/util/concurrent/CopyOnWriteArrayList.java: New file.
+	* java/util/AbstractQueue.java: Removed.
+	* java/util/Queue.java: Removed.
+	* external/jsr166/java/util/concurrent/ScheduledThreadPoolExecutor.java
+	(runPeriodic): Added explicit cast.
+	* external/jsr166/java/util/ArrayDeque.java (clone): Use
+	elements.clone.
+
+2006-06-16  Tom Tromey  <tromey@redhat.com>
+
 	* vm/reference/sun/reflect/Reflection.java (verifyMemberAccess):
 	Removed.
 	(getCallerClass): Now static.
diff --git a/external/jsr166/java/util/ArrayDeque.java b/external/jsr166/java/util/ArrayDeque.java
new file mode 100644
index 000000000..418fa410c
--- /dev/null
+++ b/external/jsr166/java/util/ArrayDeque.java
@@ -0,0 +1,839 @@
+/*
+ * Written by Josh Bloch of Google Inc. and released to the public domain,
+ * as explained at http://creativecommons.org/licenses/publicdomain.
+ */
+
+package java.util;
+import java.io.*;
+
+/**
+ * Resizable-array implementation of the {@link Deque} interface.  Array
+ * deques have no capacity restrictions; they grow as necessary to support
+ * usage.  They are not thread-safe; in the absence of external
+ * synchronization, they do not support concurrent access by multiple threads.
+ * Null elements are prohibited.  This class is likely to be faster than
+ * {@link Stack} when used as a stack, and faster than {@link LinkedList}
+ * when used as a queue.
+ *
+ * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
+ * Exceptions include {@link #remove(Object) remove}, {@link
+ * #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
+ * removeLastOccurrence}, {@link #contains contains}, {@link #iterator
+ * iterator.remove()}, and the bulk operations, all of which run in linear
+ * time.
+ *
+ * <p>The iterators returned by this class's <tt>iterator</tt> method are
+ * <i>fail-fast</i>: If the deque is modified at any time after the iterator
+ * is created, in any way except through the iterator's own <tt>remove</tt>
+ * method, the iterator will generally throw a {@link
+ * ConcurrentModificationException}.  Thus, in the face of concurrent
+ * modification, the iterator fails quickly and cleanly, rather than risking
+ * arbitrary, non-deterministic behavior at an undetermined time in the
+ * future.
+ *
+ * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
+ * as it is, generally speaking, impossible to make any hard guarantees in the
+ * presence of unsynchronized concurrent modification.  Fail-fast iterators
+ * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
+ * Therefore, it would be wrong to write a program that depended on this
+ * exception for its correctness: <i>the fail-fast behavior of iterators
+ * should be used only to detect bugs.</i>
+ *
+ * <p>This class and its iterator implement all of the
+ * <em>optional</em> methods of the {@link Collection} and {@link
+ * Iterator} interfaces.
+ *
+ * <p>This class is a member of the
+ * <a href="{@docRoot}/../technotes/guides/collections/index.html">
+ * Java Collections Framework</a>.
+ *
+ * @author  Josh Bloch and Doug Lea
+ * @since   1.6
+ * @param <E> the type of elements held in this collection
+ */
+public class ArrayDeque<E> extends AbstractCollection<E>
+                           implements Deque<E>, Cloneable, Serializable
+{
+    /**
+     * The array in which the elements of the deque are stored.
+     * The capacity of the deque is the length of this array, which is
+     * always a power of two. The array is never allowed to become
+     * full, except transiently within an addX method where it is
+     * resized (see doubleCapacity) immediately upon becoming full,
+     * thus avoiding head and tail wrapping around to equal each
+     * other.  We also guarantee that all array cells not holding
+     * deque elements are always null.
+     */
+    private transient E[] elements;
+
+    /**
+     * The index of the element at the head of the deque (which is the
+     * element that would be removed by remove() or pop()); or an
+     * arbitrary number equal to tail if the deque is empty.
+     */
+    private transient int head;
+
+    /**
+     * The index at which the next element would be added to the tail
+     * of the deque (via addLast(E), add(E), or push(E)).
+     */
+    private transient int tail;
+
+    /**
+     * The minimum capacity that we'll use for a newly created deque.
+     * Must be a power of 2.
+     */
+    private static final int MIN_INITIAL_CAPACITY = 8;
+
+    // ******  Array allocation and resizing utilities ******
+
+    /**
+     * Allocate empty array to hold the given number of elements.
+     *
+     * @param numElements  the number of elements to hold
+     */
+    private void allocateElements(int numElements) {
+        int initialCapacity = MIN_INITIAL_CAPACITY;
+        // Find the best power of two to hold elements.
+        // Tests "<=" because arrays aren't kept full.
+        if (numElements >= initialCapacity) {
+            initialCapacity = numElements;
+            initialCapacity |= (initialCapacity >>>  1);
+            initialCapacity |= (initialCapacity >>>  2);
+            initialCapacity |= (initialCapacity >>>  4);
+            initialCapacity |= (initialCapacity >>>  8);
+            initialCapacity |= (initialCapacity >>> 16);
+            initialCapacity++;
+
+            if (initialCapacity < 0)   // Too many elements, must back off
+                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
+        }
+        elements = (E[]) new Object[initialCapacity];
+    }
+
+    /**
+     * Double the capacity of this deque.  Call only when full, i.e.,
+     * when head and tail have wrapped around to become equal.
+     */
+    private void doubleCapacity() {
+        assert head == tail;
+        int p = head;
+        int n = elements.length;
+        int r = n - p; // number of elements to the right of p
+        int newCapacity = n << 1;
+        if (newCapacity < 0)
+            throw new IllegalStateException("Sorry, deque too big");
+        Object[] a = new Object[newCapacity];
+        System.arraycopy(elements, p, a, 0, r);
+        System.arraycopy(elements, 0, a, r, p);
+        elements = (E[])a;
+        head = 0;
+        tail = n;
+    }
+
+    /**
+     * Copies the elements from our element array into the specified array,
+     * in order (from first to last element in the deque).  It is assumed
+     * that the array is large enough to hold all elements in the deque.
+     *
+     * @return its argument
+     */
+    private <T> T[] copyElements(T[] a) {
+        if (head < tail) {
+            System.arraycopy(elements, head, a, 0, size());
+        } else if (head > tail) {
+            int headPortionLen = elements.length - head;
+            System.arraycopy(elements, head, a, 0, headPortionLen);
+            System.arraycopy(elements, 0, a, headPortionLen, tail);
+        }
+        return a;
+    }
+
+    /**
+     * Constructs an empty array deque with an initial capacity
+     * sufficient to hold 16 elements.
+     */
+    public ArrayDeque() {
+        elements = (E[]) new Object[16];
+    }
+
+    /**
+     * Constructs an empty array deque with an initial capacity
+     * sufficient to hold the specified number of elements.
+     *
+     * @param numElements  lower bound on initial capacity of the deque
+     */
+    public ArrayDeque(int numElements) {
+        allocateElements(numElements);
+    }
+
+    /**
+     * Constructs a deque containing the elements of the specified
+     * collection, in the order they are returned by the collection's
+     * iterator.  (The first element returned by the collection's
+     * iterator becomes the first element, or <i>front</i> of the
+     * deque.)
+     *
+     * @param c the collection whose elements are to be placed into the deque
+     * @throws NullPointerException if the specified collection is null
+     */
+    public ArrayDeque(Collection<? extends E> c) {
+        allocateElements(c.size());
+        addAll(c);
+    }
+
+    // The main insertion and extraction methods are addFirst,
+    // addLast, pollFirst, pollLast. The other methods are defined in
+    // terms of these.
+
+    /**
+     * Inserts the specified element at the front of this deque.
+     *
+     * @param e the element to add
+     * @throws NullPointerException if the specified element is null
+     */
+    public void addFirst(E e) {
+        if (e == null)
+            throw new NullPointerException();
+        elements[head = (head - 1) & (elements.length - 1)] = e;
+        if (head == tail)
+            doubleCapacity();
+    }
+
+    /**
+     * Inserts the specified element at the end of this deque.
+     *
+     * <p>This method is equivalent to {@link #add}.
+     *
+     * @param e the element to add
+     * @throws NullPointerException if the specified element is null
+     */
+    public void addLast(E e) {
+        if (e == null)
+            throw new NullPointerException();
+        elements[tail] = e;
+        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
+            doubleCapacity();
+    }
+
+    /**
+     * Inserts the specified element at the front of this deque.
+     *
+     * @param e the element to add
+     * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
+     * @throws NullPointerException if the specified element is null
+     */
+    public boolean offerFirst(E e) {
+        addFirst(e);
+        return true;
+    }
+
+    /**
+     * Inserts the specified element at the end of this deque.
+     *
+     * @param e the element to add
+     * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
+     * @throws NullPointerException if the specified element is null
+     */
+    public boolean offerLast(E e) {
+        addLast(e);
+        return true;
+    }
+
+    /**
+     * @throws NoSuchElementException {@inheritDoc}
+     */
+    public E removeFirst() {
+        E x = pollFirst();
+        if (x == null)
+            throw new NoSuchElementException();
+        return x;
+    }
+
+    /**
+     * @throws NoSuchElementException {@inheritDoc}
+     */
+    public E removeLast() {
+        E x = pollLast();
+        if (x == null)
+            throw new NoSuchElementException();
+        return x;
+    }
+
+    public E pollFirst() {
+        int h = head;
+        E result = elements[h]; // Element is null if deque empty
+        if (result == null)
+            return null;
+        elements[h] = null;     // Must null out slot
+        head = (h + 1) & (elements.length - 1);
+        return result;
+    }
+
+    public E pollLast() {
+        int t = (tail - 1) & (elements.length - 1);
+        E result = elements[t];
+        if (result == null)
+            return null;
+        elements[t] = null;
+        tail = t;
+        return result;
+    }
+
+    /**
+     * @throws NoSuchElementException {@inheritDoc}
+     */
+    public E getFirst() {
+        E x = elements[head];
+        if (x == null)
+            throw new NoSuchElementException();
+        return x;
+    }
+
+    /**
+     * @throws NoSuchElementException {@inheritDoc}
+     */
+    public E getLast() {
+        E x = elements[(tail - 1) & (elements.length - 1)];
+        if (x == null)
+            throw new NoSuchElementException();
+        return x;
+    }
+
+    public E peekFirst() {
+        return elements[head]; // elements[head] is null if deque empty
+    }
+
+    public E peekLast() {
+        return elements[(tail - 1) & (elements.length - 1)];
+    }
+
+    /**
+     * Removes the first occurrence of the specified element in this
+     * deque (when traversing the deque from head to tail).
+     * If the deque does not contain the element, it is unchanged.
+     * More formally, removes the first element <tt>e</tt> such that
+     * <tt>o.equals(e)</tt> (if such an element exists).
+     * Returns <tt>true</tt> if this deque contained the specified element
+     * (or equivalently, if this deque changed as a result of the call).
+     *
+     * @param o element to be removed from this deque, if present
+     * @return <tt>true</tt> if the deque contained the specified element
+     */
+    public boolean removeFirstOccurrence(Object o) {
+        if (o == null)
+            return false;
+        int mask = elements.length - 1;
+        int i = head;
+        E x;
+        while ( (x = elements[i]) != null) {
+            if (o.equals(x)) {
+                delete(i);
+                return true;
+            }
+            i = (i + 1) & mask;
+        }
+        return false;
+    }
+
+    /**
+     * Removes the last occurrence of the specified element in this
+     * deque (when traversing the deque from head to tail).
+     * If the deque does not contain the element, it is unchanged.
+     * More formally, removes the last element <tt>e</tt> such that
+     * <tt>o.equals(e)</tt> (if such an element exists).
+     * Returns <tt>true</tt> if this deque contained the specified element
+     * (or equivalently, if this deque changed as a result of the call).
+     *
+     * @param o element to be removed from this deque, if present
+     * @return <tt>true</tt> if the deque contained the specified element
+     */
+    public boolean removeLastOccurrence(Object o) {
+        if (o == null)
+            return false;
+        int mask = elements.length - 1;
+        int i = (tail - 1) & mask;
+        E x;
+        while ( (x = elements[i]) != null) {
+            if (o.equals(x)) {
+                delete(i);
+                return true;
+            }
+            i = (i - 1) & mask;
+        }
+        return false;
+    }
+
+    // *** Queue methods ***
+
+    /**
+     * Inserts the specified element at the end of this deque.
+     *
+     * <p>This method is equivalent to {@link #addLast}.
+     *
+     * @param e the element to add
+     * @return <tt>true</tt> (as specified by {@link Collection#add})
+     * @throws NullPointerException if the specified element is null
+     */
+    public boolean add(E e) {
+        addLast(e);
+        return true;
+    }
+
+    /**
+     * Inserts the specified element at the end of this deque.
+     *
+     * <p>This method is equivalent to {@link #offerLast}.
+     *
+     * @param e the element to add
+     * @return <tt>true</tt> (as specified by {@link Queue#offer})
+     * @throws NullPointerException if the specified element is null
+     */
+    public boolean offer(E e) {
+        return offerLast(e);
+    }
+
+    /**
+     * Retrieves and removes the head of the queue represented by this deque.
+     *
+     * This method differs from {@link #poll poll} only in that it throws an
+     * exception if this deque is empty.
+     *
+     * <p>This method is equivalent to {@link #removeFirst}.
+     *
+     * @return the head of the queue represented by this deque
+     * @throws NoSuchElementException {@inheritDoc}
+     */
+    public E remove() {
+        return removeFirst();
+    }
+
+    /**
+     * Retrieves and removes the head of the queue represented by this deque
+     * (in other words, the first element of this deque), or returns
+     * <tt>null</tt> if this deque is empty.
+     *
+     * <p>This method is equivalent to {@link #pollFirst}.
+     *
+     * @return the head of the queue represented by this deque, or
+     *         <tt>null</tt> if this deque is empty
+     */
+    public E poll() {
+        return pollFirst();
+    }
+
+    /**
+     * Retrieves, but does not remove, the head of the queue represented by
+     * this deque.  This method differs from {@link #peek peek} only in
+     * that it throws an exception if this deque is empty.
+     *
+     * <p>This method is equivalent to {@link #getFirst}.
+     *
+     * @return the head of the queue represented by this deque
+     * @throws NoSuchElementException {@inheritDoc}
+     */
+    public E element() {
+        return getFirst();
+    }
+
+    /**
+     * Retrieves, but does not remove, the head of the queue represented by
+     * this deque, or returns <tt>null</tt> if this deque is empty.
+     *
+     * <p>This method is equivalent to {@link #peekFirst}.
+     *
+     * @return the head of the queue represented by this deque, or
+     *         <tt>null</tt> if this deque is empty
+     */
+    public E peek() {
+        return peekFirst();
+    }
+
+    // *** Stack methods ***
+
+    /**
+     * Pushes an element onto the stack represented by this deque.  In other
+     * words, inserts the element at the front of this deque.
+     *
+     * <p>This method is equivalent to {@link #addFirst}.
+     *
+     * @param e the element to push
+     * @throws NullPointerException if the specified element is null
+     */
+    public void push(E e) {
+        addFirst(e);
+    }
+
+    /**
+     * Pops an element from the stack represented by this deque.  In other
+     * words, removes and returns the first element of this deque.
+     *
+     * <p>This method is equivalent to {@link #removeFirst()}.
+     *
+     * @return the element at the front of this deque (which is the top
+     *         of the stack represented by this deque)
+     * @throws NoSuchElementException {@inheritDoc}
+     */
+    public E pop() {
+        return removeFirst();
+    }
+
+    private void checkInvariants() {
+	assert elements[tail] == null;
+	assert head == tail ? elements[head] == null :
+	    (elements[head] != null &&
+	     elements[(tail - 1) & (elements.length - 1)] != null);
+	assert elements[(head - 1) & (elements.length - 1)] == null;
+    }
+
+    /**
+     * Removes the element at the specified position in the elements array,
+     * adjusting head and tail as necessary.  This can result in motion of
+     * elements backwards or forwards in the array.
+     *
+     * <p>This method is called delete rather than remove to emphasize
+     * that its semantics differ from those of {@link List#remove(int)}.
+     *
+     * @return true if elements moved backwards
+     */
+    private boolean delete(int i) {
+ 	checkInvariants();
+	final E[] elements = this.elements;
+	final int mask = elements.length - 1;
+	final int h = head;
+	final int t = tail;
+	final int front = (i - h) & mask;
+	final int back  = (t - i) & mask;
+
+	// Invariant: head <= i < tail mod circularity
+	if (front >= ((t - h) & mask))
+	    throw new ConcurrentModificationException();
+
+	// Optimize for least element motion
+	if (front < back) {
+	    if (h <= i) {
+		System.arraycopy(elements, h, elements, h + 1, front);
+	    } else { // Wrap around
+		System.arraycopy(elements, 0, elements, 1, i);
+		elements[0] = elements[mask];
+		System.arraycopy(elements, h, elements, h + 1, mask - h);
+	    }
+	    elements[h] = null;
+	    head = (h + 1) & mask;
+	    return false;
+	} else {
+	    if (i < t) { // Copy the null tail as well
+		System.arraycopy(elements, i + 1, elements, i, back);
+		tail = t - 1;
+	    } else { // Wrap around
+		System.arraycopy(elements, i + 1, elements, i, mask - i);
+		elements[mask] = elements[0];
+		System.arraycopy(elements, 1, elements, 0, t);
+		tail = (t - 1) & mask;
+	    }
+	    return true;
+	}
+    }
+
+    // *** Collection Methods ***
+
+    /**
+     * Returns the number of elements in this deque.
+     *
+     * @return the number of elements in this deque
+     */
+    public int size() {
+        return (tail - head) & (elements.length - 1);
+    }
+
+    /**
+     * Returns <tt>true</tt> if this deque contains no elements.
+     *
+     * @return <tt>true</tt> if this deque contains no elements
+     */
+    public boolean isEmpty() {
+        return head == tail;
+    }
+
+    /**
+     * Returns an iterator over the elements in this deque.  The elements
+     * will be ordered from first (head) to last (tail).  This is the same
+     * order that elements would be dequeued (via successive calls to
+     * {@link #remove} or popped (via successive calls to {@link #pop}).
+     *
+     * @return an iterator over the elements in this deque
+     */
+    public Iterator<E> iterator() {
+        return new DeqIterator();
+    }
+
+    public Iterator<E> descendingIterator() {
+        return new DescendingIterator();
+    }
+
+    private class DeqIterator implements Iterator<E> {
+        /**
+         * Index of element to be returned by subsequent call to next.
+         */
+        private int cursor = head;
+
+        /**
+         * Tail recorded at construction (also in remove), to stop
+         * iterator and also to check for comodification.
+         */
+        private int fence = tail;
+
+        /**
+         * Index of element returned by most recent call to next.
+         * Reset to -1 if element is deleted by a call to remove.
+         */
+        private int lastRet = -1;
+
+        public boolean hasNext() {
+            return cursor != fence;
+        }
+
+        public E next() {
+            if (cursor == fence)
+                throw new NoSuchElementException();
+            E result = elements[cursor];
+            // This check doesn't catch all possible comodifications,
+            // but does catch the ones that corrupt traversal
+            if (tail != fence || result == null)
+                throw new ConcurrentModificationException();
+            lastRet = cursor;
+            cursor = (cursor + 1) & (elements.length - 1);
+            return result;
+        }
+
+        public void remove() {
+            if (lastRet < 0)
+                throw new IllegalStateException();
+            if (delete(lastRet)) { // if left-shifted, undo increment in next()
+                cursor = (cursor - 1) & (elements.length - 1);
+		fence = tail;
+	    }
+            lastRet = -1;
+        }
+    }
+
+    private class DescendingIterator implements Iterator<E> {
+        /*
+         * This class is nearly a mirror-image of DeqIterator, using
+         * tail instead of head for initial cursor, and head instead of
+         * tail for fence.
+         */
+        private int cursor = tail;
+        private int fence = head;
+        private int lastRet = -1;
+
+        public boolean hasNext() {
+            return cursor != fence;
+        }
+
+        public E next() {
+            if (cursor == fence)
+                throw new NoSuchElementException();
+            cursor = (cursor - 1) & (elements.length - 1);
+	    E result = elements[cursor];
+            if (head != fence || result == null)
+                throw new ConcurrentModificationException();
+            lastRet = cursor;
+            return result;
+        }
+
+        public void remove() {
+            if (lastRet < 0)
+                throw new IllegalStateException();
+            if (!delete(lastRet)) {
+                cursor = (cursor + 1) & (elements.length - 1);
+		fence = head;
+	    }
+            lastRet = -1;
+        }
+    }
+
+    /**
+     * Returns <tt>true</tt> if this deque contains the specified element.
+     * More formally, returns <tt>true</tt> if and only if this deque contains
+     * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
+     *
+     * @param o object to be checked for containment in this deque
+     * @return <tt>true</tt> if this deque contains the specified element
+     */
+    public boolean contains(Object o) {
+        if (o == null)
+            return false;
+        int mask = elements.length - 1;
+        int i = head;
+        E x;
+        while ( (x = elements[i]) != null) {
+            if (o.equals(x))
+                return true;
+            i = (i + 1) & mask;
+        }
+        return false;
+    }
+
+    /**
+     * Removes a single instance of the specified element from this deque.
+     * If the deque does not contain the element, it is unchanged.
+     * More formally, removes the first element <tt>e</tt> such that
+     * <tt>o.equals(e)</tt> (if such an element exists).
+     * Returns <tt>true</tt> if this deque contained the specified element
+     * (or equivalently, if this deque changed as a result of the call).
+     *
+     * <p>This method is equivalent to {@link #removeFirstOccurrence}.
+     *
+     * @param o element to be removed from this deque, if present
+     * @return <tt>true</tt> if this deque contained the specified element
+     */
+    public boolean remove(Object o) {
+        return removeFirstOccurrence(o);
+    }
+
+    /**
+     * Removes all of the elements from this deque.
+     * The deque will be empty after this call returns.
+     */
+    public void clear() {
+        int h = head;
+        int t = tail;
+        if (h != t) { // clear all cells
+            head = tail = 0;
+            int i = h;
+            int mask = elements.length - 1;
+            do {
+                elements[i] = null;
+                i = (i + 1) & mask;
+            } while (i != t);
+        }
+    }
+
+    /**
+     * Returns an array containing all of the elements in this deque
+     * in proper sequence (from first to last element).
+     *
+     * <p>The returned array will be "safe" in that no references to it are
+     * maintained by this deque.  (In other words, this method must allocate
+     * a new array).  The caller is thus free to modify the returned array.
+     *
+     * <p>This method acts as bridge between array-based and collection-based
+     * APIs.
+     *
+     * @return an array containing all of the elements in this deque
+     */
+    public Object[] toArray() {
+	return copyElements(new Object[size()]);
+    }
+
+    /**
+     * Returns an array containing all of the elements in this deque in
+     * proper sequence (from first to last element); the runtime type of the
+     * returned array is that of the specified array.  If the deque fits in
+     * the specified array, it is returned therein.  Otherwise, a new array
+     * is allocated with the runtime type of the specified array and the
+     * size of this deque.
+     *
+     * <p>If this deque fits in the specified array with room to spare
+     * (i.e., the array has more elements than this deque), the element in
+     * the array immediately following the end of the deque is set to
+     * <tt>null</tt>.
+     *
+     * <p>Like the {@link #toArray()} method, this method acts as bridge between
+     * array-based and collection-based APIs.  Further, this method allows
+     * precise control over the runtime type of the output array, and may,
+     * under certain circumstances, be used to save allocation costs.
+     *
+     * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
+     * The following code can be used to dump the deque into a newly
+     * allocated array of <tt>String</tt>:
+     *
+     * <pre>
+     *     String[] y = x.toArray(new String[0]);</pre>
+     *
+     * Note that <tt>toArray(new Object[0])</tt> is identical in function to
+     * <tt>toArray()</tt>.
+     *
+     * @param a the array into which the elements of the deque are to
+     *          be stored, if it is big enough; otherwise, a new array of the
+     *          same runtime type is allocated for this purpose
+     * @return an array containing all of the elements in this deque
+     * @throws ArrayStoreException if the runtime type of the specified array
+     *         is not a supertype of the runtime type of every element in
+     *         this deque
+     * @throws NullPointerException if the specified array is null
+     */
+    public <T> T[] toArray(T[] a) {
+        int size = size();
+        if (a.length < size)
+            a = (T[])java.lang.reflect.Array.newInstance(
+                    a.getClass().getComponentType(), size);
+	copyElements(a);
+        if (a.length > size)
+            a[size] = null;
+        return a;
+    }
+
+    // *** Object methods ***
+
+    /**
+     * Returns a copy of this deque.
+     *
+     * @return a copy of this deque
+     */
+    public ArrayDeque<E> clone() {
+        try {
+            ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
+            // Classpath local: we don't have Arrays.copyOf yet.
+            // result.elements = Arrays.copyOf(elements, elements.length);
+            result.elements = elements.clone();
+            return result;
+
+        } catch (CloneNotSupportedException e) {
+            throw new AssertionError();
+        }
+    }
+
+    /**
+     * Appease the serialization gods.
+     */
+    private static final long serialVersionUID = 2340985798034038923L;
+
+    /**
+     * Serialize this deque.
+     *
+     * @serialData The current size (<tt>int</tt>) of the deque,
+     * followed by all of its elements (each an object reference) in
+     * first-to-last order.
+     */
+    private void writeObject(ObjectOutputStream s) throws IOException {
+        s.defaultWriteObject();
+
+        // Write out size
+        s.writeInt(size());
+
+        // Write out elements in order.
+        int mask = elements.length - 1;
+        for (int i = head; i != tail; i = (i + 1) & mask)
+            s.writeObject(elements[i]);
+    }
+
+    /**
+     * Deserialize this deque.
+     */
+    private void readObject(ObjectInputStream s)
+            throws IOException, ClassNotFoundException {
+        s.defaultReadObject();
+
+        // Read in size and allocate array
+        int size = s.readInt();
+        allocateElements(size);
+        head = 0;
+        tail = size;
+
+        // Read in all elements in the proper order.
+        for (int i = 0; i < size; i++)
+            elements[i] = (E)s.readObject();
+    }
+}
diff --git a/external/jsr166/java/util/concurrent/ScheduledThreadPoolExecutor.java b/external/jsr166/java/util/concurrent/ScheduledThreadPoolExecutor.java
new file mode 100644
index 000000000..d4da334c6
--- /dev/null
+++ b/external/jsr166/java/util/concurrent/ScheduledThreadPoolExecutor.java
@@ -0,0 +1,626 @@
+/*
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+package java.util.concurrent;
+import java.util.concurrent.atomic.*;
+import java.util.*;
+
+/**
+ * A {@link ThreadPoolExecutor} that can additionally schedule
+ * commands to run after a given delay, or to execute
+ * periodically. This class is preferable to {@link java.util.Timer}
+ * when multiple worker threads are needed, or when the additional
+ * flexibility or capabilities of {@link ThreadPoolExecutor} (which
+ * this class extends) are required.
+ *
+ * <p> Delayed tasks execute no sooner than they are enabled, but
+ * without any real-time guarantees about when, after they are
+ * enabled, they will commence. Tasks scheduled for exactly the same
+ * execution time are enabled in first-in-first-out (FIFO) order of
+ * submission.
+ *
+ * <p>While this class inherits from {@link ThreadPoolExecutor}, a few
+ * of the inherited tuning methods are not useful for it. In
+ * particular, because it acts as a fixed-sized pool using
+ * <tt>corePoolSize</tt> threads and an unbounded queue, adjustments
+ * to <tt>maximumPoolSize</tt> have no useful effect.
+ *
+ * <p><b>Extension notes:</b> This class overrides {@link
+ * AbstractExecutorService} <tt>submit</tt> methods to generate
+ * internal objects to control per-task delays and scheduling. To
+ * preserve functionality, any further overrides of these methods in
+ * subclasses must invoke superclass versions, which effectively
+ * disables additional task customization. However, this class
+ * provides alternative protected extension method
+ * <tt>decorateTask</tt> (one version each for <tt>Runnable</tt> and
+ * <tt>Callable</tt>) that can be used to customize the concrete task
+ * types used to execute commands entered via <tt>execute</tt>,
+ * <tt>submit</tt>, <tt>schedule</tt>, <tt>scheduleAtFixedRate</tt>,
+ * and <tt>scheduleWithFixedDelay</tt>.  By default, a
+ * <tt>ScheduledThreadPoolExecutor</tt> uses a task type extending
+ * {@link FutureTask}. However, this may be modified or replaced using
+ * subclasses of the form:
+ *
+ * <pre>
+ * public class CustomScheduledExecutor extends ScheduledThreadPoolExecutor {
+ *
+ *   static class CustomTask&lt;V&gt; implements RunnableScheduledFuture&lt;V&gt; { ... }
+ *
+ *   protected &lt;V&gt; RunnableScheduledFuture&lt;V&gt; decorateTask(
+ *                Runnable r, RunnableScheduledFuture&lt;V&gt; task) {
+ *       return new CustomTask&lt;V&gt;(r, task);
+ *   }
+ *
+ *   protected &lt;V&gt; RunnableScheduledFuture&lt;V&gt; decorateTask(
+ *                Callable&lt;V&gt; c, RunnableScheduledFuture&lt;V&gt; task) {
+ *       return new CustomTask&lt;V&gt;(c, task);
+ *   }
+ *   // ... add constructors, etc.
+ * }
+ * </pre>
+ * @since 1.5
+ * @author Doug Lea
+ */
+public class ScheduledThreadPoolExecutor
+        extends ThreadPoolExecutor
+        implements ScheduledExecutorService {
+
+    /**
+     * False if should cancel/suppress periodic tasks on shutdown.
+     */
+    private volatile boolean continueExistingPeriodicTasksAfterShutdown;
+
+    /**
+     * False if should cancel non-periodic tasks on shutdown.
+     */
+    private volatile boolean executeExistingDelayedTasksAfterShutdown = true;
+
+    /**
+     * Sequence number to break scheduling ties, and in turn to
+     * guarantee FIFO order among tied entries.
+     */
+    private static final AtomicLong sequencer = new AtomicLong(0);
+
+    /** Base of nanosecond timings, to avoid wrapping */
+    private static final long NANO_ORIGIN = System.nanoTime();
+
+    /**
+     * Returns nanosecond time offset by origin
+     */
+    final long now() {
+        return System.nanoTime() - NANO_ORIGIN;
+    }
+
+    private class ScheduledFutureTask<V>
+            extends FutureTask<V> implements RunnableScheduledFuture<V> {
+
+        /** Sequence number to break ties FIFO */
+        private final long sequenceNumber;
+        /** The time the task is enabled to execute in nanoTime units */
+        private long time;
+        /**
+         * Period in nanoseconds for repeating tasks.  A positive
+         * value indicates fixed-rate execution.  A negative value
+         * indicates fixed-delay execution.  A value of 0 indicates a
+         * non-repeating task.
+         */
+        private final long period;
+
+        /**
+         * Creates a one-shot action with given nanoTime-based trigger time.
+         */
+        ScheduledFutureTask(Runnable r, V result, long ns) {
+            super(r, result);
+            this.time = ns;
+            this.period = 0;
+            this.sequenceNumber = sequencer.getAndIncrement();
+        }
+
+        /**
+         * Creates a periodic action with given nano time and period.
+         */
+        ScheduledFutureTask(Runnable r, V result, long ns, long period) {
+            super(r, result);
+            this.time = ns;
+            this.period = period;
+            this.sequenceNumber = sequencer.getAndIncrement();
+        }
+
+        /**
+         * Creates a one-shot action with given nanoTime-based trigger.
+         */
+        ScheduledFutureTask(Callable<V> callable, long ns) {
+            super(callable);
+            this.time = ns;
+            this.period = 0;
+            this.sequenceNumber = sequencer.getAndIncrement();
+        }
+
+        public long getDelay(TimeUnit unit) {
+            long d = unit.convert(time - now(), TimeUnit.NANOSECONDS);
+            return d;
+        }
+
+        public int compareTo(Delayed other) {
+            if (other == this) // compare zero ONLY if same object
+                return 0;
+            if (other instanceof ScheduledFutureTask) {
+                ScheduledFutureTask<?> x = (ScheduledFutureTask<?>)other;
+                long diff = time - x.time;
+                if (diff < 0)
+                    return -1;
+                else if (diff > 0)
+                    return 1;
+                else if (sequenceNumber < x.sequenceNumber)
+                    return -1;
+                else
+                    return 1;
+            }
+            long d = (getDelay(TimeUnit.NANOSECONDS) -
+                      other.getDelay(TimeUnit.NANOSECONDS));
+            return (d == 0)? 0 : ((d < 0)? -1 : 1);
+        }
+
+        /**
+         * Returns true if this is a periodic (not a one-shot) action.
+         *
+         * @return true if periodic
+         */
+        public boolean isPeriodic() {
+            return period != 0;
+        }
+
+        /**
+         * Runs a periodic task.
+         */
+        private void runPeriodic() {
+            boolean ok = ScheduledFutureTask.super.runAndReset();
+            boolean down = isShutdown();
+            // Reschedule if not cancelled and not shutdown or policy allows
+            if (ok && (!down ||
+                       (getContinueExistingPeriodicTasksAfterShutdownPolicy() &&
+                        !isTerminating()))) {
+                long p = period;
+                if (p > 0)
+                    time += p;
+                else
+                    time = now() - p;
+                // Classpath local: ecj from eclipse 3.1 does not
+                // compile this.
+                // ScheduledThreadPoolExecutor.super.getQueue().add(this);
+                ScheduledThreadPoolExecutor.super.getQueue().add((Runnable) this);
+            }
+            // This might have been the final executed delayed
+            // task.  Wake up threads to check.
+            else if (down)
+                interruptIdleWorkers();
+        }
+
+        /**
+         * Overrides FutureTask version so as to reset/requeue if periodic.
+         */
+        public void run() {
+            if (isPeriodic())
+                runPeriodic();
+            else
+                ScheduledFutureTask.super.run();
+        }
+    }
+
+    /**
+     * Specialized variant of ThreadPoolExecutor.execute for delayed tasks.
+     */
+    private void delayedExecute(Runnable command) {
+        if (isShutdown()) {
+            reject(command);
+            return;
+        }
+        // Prestart a thread if necessary. We cannot prestart it
+        // running the task because the task (probably) shouldn't be
+        // run yet, so thread will just idle until delay elapses.
+        if (getPoolSize() < getCorePoolSize())
+            prestartCoreThread();
+
+        super.getQueue().add(command);
+    }
+
+    /**
+     * Cancels and clears the queue of all tasks that should not be run
+     * due to shutdown policy.
+     */
+    private void cancelUnwantedTasks() {
+        boolean keepDelayed = getExecuteExistingDelayedTasksAfterShutdownPolicy();
+        boolean keepPeriodic = getContinueExistingPeriodicTasksAfterShutdownPolicy();
+        if (!keepDelayed && !keepPeriodic)
+            super.getQueue().clear();
+        else if (keepDelayed || keepPeriodic) {
+            Object[] entries = super.getQueue().toArray();
+            for (int i = 0; i < entries.length; ++i) {
+                Object e = entries[i];
+                if (e instanceof RunnableScheduledFuture) {
+                    RunnableScheduledFuture<?> t = (RunnableScheduledFuture<?>)e;
+                    if (t.isPeriodic()? !keepPeriodic : !keepDelayed)
+                        t.cancel(false);
+                }
+            }
+            entries = null;
+            purge();
+        }
+    }
+
+    public boolean remove(Runnable task) {
+        if (!(task instanceof RunnableScheduledFuture))
+            return false;
+        return getQueue().remove(task);
+    }
+
+    /**
+     * Modifies or replaces the task used to execute a runnable.
+     * This method can be used to override the concrete
+     * class used for managing internal tasks.
+     * The default implementation simply returns the given task.
+     *
+     * @param runnable the submitted Runnable
+     * @param task the task created to execute the runnable
+     * @return a task that can execute the runnable
+     * @since 1.6
+     */
+    protected <V> RunnableScheduledFuture<V> decorateTask(
+        Runnable runnable, RunnableScheduledFuture<V> task) {
+        return task;
+    }
+
+    /**
+     * Modifies or replaces the task used to execute a callable.
+     * This method can be used to override the concrete
+     * class used for managing internal tasks.
+     * The default implementation simply returns the given task.
+     *
+     * @param callable the submitted Callable
+     * @param task the task created to execute the callable
+     * @return a task that can execute the callable
+     * @since 1.6
+     */
+    protected <V> RunnableScheduledFuture<V> decorateTask(
+        Callable<V> callable, RunnableScheduledFuture<V> task) {
+        return task;
+    }
+
+    /**
+     * Creates a new ScheduledThreadPoolExecutor with the given core
+     * pool size.
+     *
+     * @param corePoolSize the number of threads to keep in the pool,
+     * even if they are idle
+     * @throws IllegalArgumentException if <tt>corePoolSize &lt; 0</tt>
+     */
+    public ScheduledThreadPoolExecutor(int corePoolSize) {
+        super(corePoolSize, Integer.MAX_VALUE, 0, TimeUnit.NANOSECONDS,
+              new DelayedWorkQueue());
+    }
+
+    /**
+     * Creates a new ScheduledThreadPoolExecutor with the given
+     * initial parameters.
+     *
+     * @param corePoolSize the number of threads to keep in the pool,
+     * even if they are idle
+     * @param threadFactory the factory to use when the executor
+     * creates a new thread
+     * @throws IllegalArgumentException if <tt>corePoolSize &lt; 0</tt>
+     * @throws NullPointerException if threadFactory is null
+     */
+    public ScheduledThreadPoolExecutor(int corePoolSize,
+                             ThreadFactory threadFactory) {
+        super(corePoolSize, Integer.MAX_VALUE, 0, TimeUnit.NANOSECONDS,
+              new DelayedWorkQueue(), threadFactory);
+    }
+
+    /**
+     * Creates a new ScheduledThreadPoolExecutor with the given
+     * initial parameters.
+     *
+     * @param corePoolSize the number of threads to keep in the pool,
+     * even if they are idle
+     * @param handler the handler to use when execution is blocked
+     * because the thread bounds and queue capacities are reached
+     * @throws IllegalArgumentException if <tt>corePoolSize &lt; 0</tt>
+     * @throws NullPointerException if handler is null
+     */
+    public ScheduledThreadPoolExecutor(int corePoolSize,
+                              RejectedExecutionHandler handler) {
+        super(corePoolSize, Integer.MAX_VALUE, 0, TimeUnit.NANOSECONDS,
+              new DelayedWorkQueue(), handler);
+    }
+
+    /**
+     * Creates a new ScheduledThreadPoolExecutor with the given
+     * initial parameters.
+     *
+     * @param corePoolSize the number of threads to keep in the pool,
+     * even if they are idle
+     * @param threadFactory the factory to use when the executor
+     * creates a new thread
+     * @param handler the handler to use when execution is blocked
+     * because the thread bounds and queue capacities are reached.
+     * @throws IllegalArgumentException if <tt>corePoolSize &lt; 0</tt>
+     * @throws NullPointerException if threadFactory or handler is null
+     */
+    public ScheduledThreadPoolExecutor(int corePoolSize,
+                              ThreadFactory threadFactory,
+                              RejectedExecutionHandler handler) {
+        super(corePoolSize, Integer.MAX_VALUE, 0, TimeUnit.NANOSECONDS,
+              new DelayedWorkQueue(), threadFactory, handler);
+    }
+
+    public ScheduledFuture<?> schedule(Runnable command,
+                                       long delay,
+                                       TimeUnit unit) {
+        if (command == null || unit == null)
+            throw new NullPointerException();
+        long triggerTime = now() + unit.toNanos(delay);
+        RunnableScheduledFuture<?> t = decorateTask(command,
+            new ScheduledFutureTask<Boolean>(command, null, triggerTime));
+        delayedExecute(t);
+        return t;
+    }
+
+    public <V> ScheduledFuture<V> schedule(Callable<V> callable,
+                                           long delay,
+                                           TimeUnit unit) {
+        if (callable == null || unit == null)
+            throw new NullPointerException();
+        if (delay < 0) delay = 0;
+        long triggerTime = now() + unit.toNanos(delay);
+        RunnableScheduledFuture<V> t = decorateTask(callable,
+            new ScheduledFutureTask<V>(callable, triggerTime));
+        delayedExecute(t);
+        return t;
+    }
+
+    public ScheduledFuture<?> scheduleAtFixedRate(Runnable command,
+                                                  long initialDelay,
+                                                  long period,
+                                                  TimeUnit unit) {
+        if (command == null || unit == null)
+            throw new NullPointerException();
+        if (period <= 0)
+            throw new IllegalArgumentException();
+        if (initialDelay < 0) initialDelay = 0;
+        long triggerTime = now() + unit.toNanos(initialDelay);
+        RunnableScheduledFuture<?> t = decorateTask(command,
+            new ScheduledFutureTask<Object>(command,
+                                            null,
+                                            triggerTime,
+                                            unit.toNanos(period)));
+        delayedExecute(t);
+        return t;
+    }
+
+    public ScheduledFuture<?> scheduleWithFixedDelay(Runnable command,
+                                                     long initialDelay,
+                                                     long delay,
+                                                     TimeUnit unit) {
+        if (command == null || unit == null)
+            throw new NullPointerException();
+        if (delay <= 0)
+            throw new IllegalArgumentException();
+        if (initialDelay < 0) initialDelay = 0;
+        long triggerTime = now() + unit.toNanos(initialDelay);
+        RunnableScheduledFuture<?> t = decorateTask(command,
+            new ScheduledFutureTask<Boolean>(command,
+                                             null,
+                                             triggerTime,
+                                             unit.toNanos(-delay)));
+        delayedExecute(t);
+        return t;
+    }
+
+
+    /**
+     * Executes command with zero required delay. This has effect
+     * equivalent to <tt>schedule(command, 0, anyUnit)</tt>.  Note
+     * that inspections of the queue and of the list returned by
+     * <tt>shutdownNow</tt> will access the zero-delayed
+     * {@link ScheduledFuture}, not the <tt>command</tt> itself.
+     *
+     * @param command the task to execute
+     * @throws RejectedExecutionException at discretion of
+     * <tt>RejectedExecutionHandler</tt>, if task cannot be accepted
+     * for execution because the executor has been shut down.
+     * @throws NullPointerException if command is null
+     */
+    public void execute(Runnable command) {
+        if (command == null)
+            throw new NullPointerException();
+        schedule(command, 0, TimeUnit.NANOSECONDS);
+    }
+
+    // Override AbstractExecutorService methods
+
+    public Future<?> submit(Runnable task) {
+        return schedule(task, 0, TimeUnit.NANOSECONDS);
+    }
+
+    public <T> Future<T> submit(Runnable task, T result) {
+        return schedule(Executors.callable(task, result),
+                        0, TimeUnit.NANOSECONDS);
+    }
+
+    public <T> Future<T> submit(Callable<T> task) {
+        return schedule(task, 0, TimeUnit.NANOSECONDS);
+    }
+
+    /**
+     * Sets the policy on whether to continue executing existing periodic
+     * tasks even when this executor has been <tt>shutdown</tt>. In
+     * this case, these tasks will only terminate upon
+     * <tt>shutdownNow</tt>, or after setting the policy to
+     * <tt>false</tt> when already shutdown. This value is by default
+     * false.
+     *
+     * @param value if true, continue after shutdown, else don't.
+     * @see #getContinueExistingPeriodicTasksAfterShutdownPolicy
+     */
+    public void setContinueExistingPeriodicTasksAfterShutdownPolicy(boolean value) {
+        continueExistingPeriodicTasksAfterShutdown = value;
+        if (!value && isShutdown())
+            cancelUnwantedTasks();
+    }
+
+    /**
+     * Gets the policy on whether to continue executing existing
+     * periodic tasks even when this executor has been
+     * <tt>shutdown</tt>. In this case, these tasks will only
+     * terminate upon <tt>shutdownNow</tt> or after setting the policy
+     * to <tt>false</tt> when already shutdown. This value is by
+     * default false.
+     *
+     * @return true if will continue after shutdown
+     * @see #setContinueExistingPeriodicTasksAfterShutdownPolicy
+     */
+    public boolean getContinueExistingPeriodicTasksAfterShutdownPolicy() {
+        return continueExistingPeriodicTasksAfterShutdown;
+    }
+
+    /**
+     * Sets the policy on whether to execute existing delayed
+     * tasks even when this executor has been <tt>shutdown</tt>. In
+     * this case, these tasks will only terminate upon
+     * <tt>shutdownNow</tt>, or after setting the policy to
+     * <tt>false</tt> when already shutdown. This value is by default
+     * true.
+     *
+     * @param value if true, execute after shutdown, else don't.
+     * @see #getExecuteExistingDelayedTasksAfterShutdownPolicy
+     */
+    public void setExecuteExistingDelayedTasksAfterShutdownPolicy(boolean value) {
+        executeExistingDelayedTasksAfterShutdown = value;
+        if (!value && isShutdown())
+            cancelUnwantedTasks();
+    }
+
+    /**
+     * Gets the policy on whether to execute existing delayed
+     * tasks even when this executor has been <tt>shutdown</tt>. In
+     * this case, these tasks will only terminate upon
+     * <tt>shutdownNow</tt>, or after setting the policy to
+     * <tt>false</tt> when already shutdown. This value is by default
+     * true.
+     *
+     * @return true if will execute after shutdown
+     * @see #setExecuteExistingDelayedTasksAfterShutdownPolicy
+     */
+    public boolean getExecuteExistingDelayedTasksAfterShutdownPolicy() {
+        return executeExistingDelayedTasksAfterShutdown;
+    }
+
+
+    /**
+     * Initiates an orderly shutdown in which previously submitted
+     * tasks are executed, but no new tasks will be accepted. If the
+     * <tt>ExecuteExistingDelayedTasksAfterShutdownPolicy</tt> has
+     * been set <tt>false</tt>, existing delayed tasks whose delays
+     * have not yet elapsed are cancelled. And unless the
+     * <tt>ContinueExistingPeriodicTasksAfterShutdownPolicy</tt> has
+     * been set <tt>true</tt>, future executions of existing periodic
+     * tasks will be cancelled.
+     */
+    public void shutdown() {
+        cancelUnwantedTasks();
+        super.shutdown();
+    }
+
+    /**
+     * Attempts to stop all actively executing tasks, halts the
+     * processing of waiting tasks, and returns a list of the tasks
+     * that were awaiting execution.
+     *
+     * <p>There are no guarantees beyond best-effort attempts to stop
+     * processing actively executing tasks.  This implementation
+     * cancels tasks via {@link Thread#interrupt}, so any task that
+     * fails to respond to interrupts may never terminate.
+     *
+     * @return list of tasks that never commenced execution.  Each
+     * element of this list is a {@link ScheduledFuture},
+     * including those tasks submitted using <tt>execute</tt>, which
+     * are for scheduling purposes used as the basis of a zero-delay
+     * <tt>ScheduledFuture</tt>.
+     * @throws SecurityException {@inheritDoc}
+     */
+    public List<Runnable> shutdownNow() {
+        return super.shutdownNow();
+    }
+
+    /**
+     * Returns the task queue used by this executor.  Each element of
+     * this queue is a {@link ScheduledFuture}, including those
+     * tasks submitted using <tt>execute</tt> which are for scheduling
+     * purposes used as the basis of a zero-delay
+     * <tt>ScheduledFuture</tt>. Iteration over this queue is
+     * <em>not</em> guaranteed to traverse tasks in the order in
+     * which they will execute.
+     *
+     * @return the task queue
+     */
+    public BlockingQueue<Runnable> getQueue() {
+        return super.getQueue();
+    }
+
+    /**
+     * An annoying wrapper class to convince javac to use a
+     * DelayQueue<RunnableScheduledFuture> as a BlockingQueue<Runnable>
+     */
+    private static class DelayedWorkQueue
+        extends AbstractCollection<Runnable>
+        implements BlockingQueue<Runnable> {
+
+        private final DelayQueue<RunnableScheduledFuture> dq = new DelayQueue<RunnableScheduledFuture>();
+        public Runnable poll() { return dq.poll(); }
+        public Runnable peek() { return dq.peek(); }
+        public Runnable take() throws InterruptedException { return dq.take(); }
+        public Runnable poll(long timeout, TimeUnit unit) throws InterruptedException {
+            return dq.poll(timeout, unit);
+        }
+
+        public boolean add(Runnable x) {
+	    return dq.add((RunnableScheduledFuture)x);
+	}
+        public boolean offer(Runnable x) {
+	    return dq.offer((RunnableScheduledFuture)x);
+	}
+        public void put(Runnable x) {
+            dq.put((RunnableScheduledFuture)x);
+        }
+        public boolean offer(Runnable x, long timeout, TimeUnit unit) {
+            return dq.offer((RunnableScheduledFuture)x, timeout, unit);
+        }
+
+        public Runnable remove() { return dq.remove(); }
+        public Runnable element() { return dq.element(); }
+        public void clear() { dq.clear(); }
+        public int drainTo(Collection<? super Runnable> c) { return dq.drainTo(c); }
+        public int drainTo(Collection<? super Runnable> c, int maxElements) {
+            return dq.drainTo(c, maxElements);
+        }
+
+        public int remainingCapacity() { return dq.remainingCapacity(); }
+        public boolean remove(Object x) { return dq.remove(x); }
+        public boolean contains(Object x) { return dq.contains(x); }
+        public int size() { return dq.size(); }
+        public boolean isEmpty() { return dq.isEmpty(); }
+        public Object[] toArray() { return dq.toArray(); }
+        public <T> T[] toArray(T[] array) { return dq.toArray(array); }
+        public Iterator<Runnable> iterator() {
+            return new Iterator<Runnable>() {
+                private Iterator<RunnableScheduledFuture> it = dq.iterator();
+                public boolean hasNext() { return it.hasNext(); }
+                public Runnable next() { return it.next(); }
+                public void remove() { it.remove(); }
+            };
+        }
+    }
+}
diff --git a/java/util/AbstractQueue.java b/java/util/AbstractQueue.java
deleted file mode 100644
index 3bc8cdb04..000000000
--- a/java/util/AbstractQueue.java
+++ /dev/null
@@ -1,94 +0,0 @@
-/* AbstractQueue.java -- Implementation of some Queue methods
-   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
-
-This file is part of GNU Classpath.
-
-GNU Classpath is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
-
-GNU Classpath is distributed in the hope that it will be useful, but
-WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GNU Classpath; see the file COPYING.  If not, write to the
-Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301 USA.
-
-Linking this library statically or dynamically with other modules is
-making a combined work based on this library.  Thus, the terms and
-conditions of the GNU General Public License cover the whole
-combination.
-
-As a special exception, the copyright holders of this library give you
-permission to link this library with independent modules to produce an
-executable, regardless of the license terms of these independent
-modules, and to copy and distribute the resulting executable under
-terms of your choice, provided that you also meet, for each linked
-independent module, the terms and conditions of the license of that
-module.  An independent module is a module which is not derived from
-or based on this library.  If you modify this library, you may extend
-this exception to your version of the library, but you are not
-obligated to do so.  If you do not wish to do so, delete this
-exception statement from your version. */
-
-
-package java.util;
-
-/**
- * @author Tom Tromey (tromey@redhat.com)
- * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
- * @since 1.5
- */
-public abstract class AbstractQueue<E> extends AbstractCollection<E> 
-  implements Queue<E>
-{
-  protected AbstractQueue()
-  {
-  }
-
-  public boolean add(E value)
-  {
-    if (offer(value))
-      return true;
-    throw new IllegalStateException();
-  }
-
-  public boolean addAll(Collection<? extends E> c)
-  {
-    if (c == this)
-      throw new IllegalArgumentException();
-    boolean result = false;
-    for (E val : c)
-      {
-	if (add(val))
-	  result = true;
-      }
-    return result;
-  }
-
-  public void clear()
-  {
-    while (poll() != null)
-      ;
-  }
-
-  public E element()
-  {
-    E result = peek();
-    if (result == null)
-      throw new NoSuchElementException();
-    return result;
-  }
-
-  public E remove()
-  {
-    E result = poll();
-    if (result == null)
-      throw new NoSuchElementException();
-    return result;
-  }
-}
diff --git a/java/util/Queue.java b/java/util/Queue.java
deleted file mode 100644
index c9c224afd..000000000
--- a/java/util/Queue.java
+++ /dev/null
@@ -1,51 +0,0 @@
-/* Queue.java -- Interface that represents a queue
-   Copyright (C) 2004 Free Software Foundation, Inc.
-
-This file is part of GNU Classpath.
-
-GNU Classpath is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
-any later version.
-
-GNU Classpath is distributed in the hope that it will be useful, but
-WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GNU Classpath; see the file COPYING.  If not, write to the
-Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301 USA.
-
-Linking this library statically or dynamically with other modules is
-making a combined work based on this library.  Thus, the terms and
-conditions of the GNU General Public License cover the whole
-combination.
-
-As a special exception, the copyright holders of this library give you
-permission to link this library with independent modules to produce an
-executable, regardless of the license terms of these independent
-modules, and to copy and distribute the resulting executable under
-terms of your choice, provided that you also meet, for each linked
-independent module, the terms and conditions of the license of that
-module.  An independent module is a module which is not derived from
-or based on this library.  If you modify this library, you may extend
-this exception to your version of the library, but you are not
-obligated to do so.  If you do not wish to do so, delete this
-exception statement from your version. */
-
-
-package java.util;
-
-/**
- * @since 1.5
- */
-public interface Queue<T> extends Collection<T>
-{
-  T element();
-  boolean offer(T value);
-  T peek();
-  T poll();
-  T remove();
-}
diff --git a/java/util/concurrent/CopyOnWriteArrayList.java b/java/util/concurrent/CopyOnWriteArrayList.java
new file mode 100644
index 000000000..ee9f7ac3a
--- /dev/null
+++ b/java/util/concurrent/CopyOnWriteArrayList.java
@@ -0,0 +1,438 @@
+/* CopyOnWriteArrayList.java
+   Copyright (C) 2006 Free Software Foundation
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING.  If not, write to the
+Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library.  Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module.  An independent module is a module which is not derived from
+or based on this library.  If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so.  If you do not wish to do so, delete this
+exception statement from your version. */
+
+package java.util.concurrent;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
+import java.lang.reflect.Array;
+import java.util.AbstractList;
+import java.util.Collection;
+import java.util.Iterator;
+import java.util.List;
+import java.util.RandomAccess;
+
+/** @since 1.5 */
+public class CopyOnWriteArrayList<E> extends AbstractList<E> implements
+    List<E>, RandomAccess, Cloneable, Serializable
+{
+  /**
+   * Where the data is stored.
+   */
+  private transient E[] data;
+
+  /**
+   * Construct a new ArrayList with the default capacity (16).
+   */
+  public CopyOnWriteArrayList()
+  {
+    data = (E[]) new Object[0];
+  }
+
+  /**
+   * Construct a new ArrayList, and initialize it with the elements in the
+   * supplied Collection. The initial capacity is 110% of the Collection's size.
+   * 
+   * @param c
+   *          the collection whose elements will initialize this list
+   * @throws NullPointerException
+   *           if c is null
+   */
+  public CopyOnWriteArrayList(Collection< ? extends E> c)
+  {
+    // FIXME ... correct?  use c.toArray()
+    data = (E[]) new Object[c.size()];
+    int index = 0;
+    for (E value : c)
+      data[index++] = value;
+  }
+
+  /**
+   * Returns the number of elements in this list.
+   * 
+   * @return the list size
+   */
+  public int size()
+  {
+    return data.length;
+  }
+
+  /**
+   * Checks if the list is empty.
+   * 
+   * @return true if there are no elements
+   */
+  public boolean isEmpty()
+  {
+    return data.length == 0;
+  }
+
+  /**
+   * Returns true iff element is in this ArrayList.
+   * 
+   * @param e
+   *          the element whose inclusion in the List is being tested
+   * @return true if the list contains e
+   */
+  public boolean contains(Object e)
+  {
+    return indexOf(e) != -1;
+  }
+
+  /**
+   * Returns the lowest index at which element appears in this List, or -1 if it
+   * does not appear.
+   * 
+   * @param e
+   *          the element whose inclusion in the List is being tested
+   * @return the index where e was found
+   */
+  public int indexOf(Object e)
+  {
+    E[] data = this.data;
+    for (int i = 0; i < data.length; i++)
+      if (equals(e, data[i]))
+        return i;
+    return -1;
+  }
+
+  /**
+   * Returns the highest index at which element appears in this List, or -1 if
+   * it does not appear.
+   * 
+   * @param e
+   *          the element whose inclusion in the List is being tested
+   * @return the index where e was found
+   */
+  public int lastIndexOf(Object e)
+  {
+    E[] data = this.data;
+    for (int i = data.length - 1; i >= 0; i--)
+      if (equals(e, data[i]))
+        return i;
+    return -1;
+  }
+
+  /**
+   * Creates a shallow copy of this ArrayList (elements are not cloned).
+   * 
+   * @return the cloned object
+   */
+  public Object clone()
+  {
+    CopyOnWriteArrayList<E> clone = null;
+    try
+      {
+        clone = (CopyOnWriteArrayList<E>) super.clone();
+        clone.data = (E[]) data.clone();
+      }
+    catch (CloneNotSupportedException e)
+      {
+        // Impossible to get here.
+      }
+    return clone;
+  }
+
+  /**
+   * Returns an Object array containing all of the elements in this ArrayList.
+   * The array is independent of this list.
+   * 
+   * @return an array representation of this list
+   */
+  public Object[] toArray()
+  {
+    E[] data = this.data;
+    E[] array = (E[]) new Object[data.length];
+    System.arraycopy(data, 0, array, 0, data.length);
+    return array;
+  }
+
+  /**
+   * Returns an Array whose component type is the runtime component type of the
+   * passed-in Array. The returned Array is populated with all of the elements
+   * in this ArrayList. If the passed-in Array is not large enough to store all
+   * of the elements in this List, a new Array will be created and returned; if
+   * the passed-in Array is <i>larger</i> than the size of this List, then
+   * size() index will be set to null.
+   * 
+   * @param a
+   *          the passed-in Array
+   * @return an array representation of this list
+   * @throws ArrayStoreException
+   *           if the runtime type of a does not allow an element in this list
+   * @throws NullPointerException
+   *           if a is null
+   */
+  public <T> T[] toArray(T[] a)
+  {
+    E[] data = this.data;
+    if (a.length < data.length)
+      a = (T[]) Array.newInstance(a.getClass().getComponentType(), data.length);
+    else if (a.length > data.length)
+      a[data.length] = null;
+    System.arraycopy(data, 0, a, 0, data.length);
+    return a;
+  }
+
+  /**
+   * Retrieves the element at the user-supplied index.
+   * 
+   * @param index
+   *          the index of the element we are fetching
+   * @throws IndexOutOfBoundsException
+   *           if index &lt; 0 || index &gt;= size()
+   */
+  public E get(int index)
+  {
+    return data[index];
+  }
+
+  /**
+   * Sets the element at the specified index. The new element, e, can be an
+   * object of any type or null.
+   * 
+   * @param index
+   *          the index at which the element is being set
+   * @param e
+   *          the element to be set
+   * @return the element previously at the specified index
+   * @throws IndexOutOfBoundsException
+   *           if index &lt; 0 || index &gt;= 0
+   */
+  public synchronized E set(int index, E e)
+  {
+    E result = data[index];
+    E[] newData = data.clone();
+    newData[index] = e;
+    data = newData;
+    return result;
+  }
+
+  /**
+   * Appends the supplied element to the end of this list. The element, e, can
+   * be an object of any type or null.
+   * 
+   * @param e
+   *          the element to be appended to this list
+   * @return true, the add will always succeed
+   */
+  public synchronized boolean add(E e)
+  {
+    E[] data = this.data;
+    E[] newData = (E[]) new Object[data.length];
+    System.arraycopy(data, 0, newData, 0, data.length);
+    newData[data.length] = e;
+    this.data = newData;
+    return true;
+  }
+
+  /**
+   * Adds the supplied element at the specified index, shifting all elements
+   * currently at that index or higher one to the right. The element, e, can be
+   * an object of any type or null.
+   * 
+   * @param index
+   *          the index at which the element is being added
+   * @param e
+   *          the item being added
+   * @throws IndexOutOfBoundsException
+   *           if index &lt; 0 || index &gt; size()
+   */
+  public synchronized void add(int index, E e)
+  {
+    E[] data = this.data;
+    E[] newData = (E[]) new Object[data.length];
+    System.arraycopy(data, 0, newData, 0, index);
+    newData[index] = e;
+    System.arraycopy(data, index, newData, index + 1, data.length - index);
+    this.data = newData;
+  }
+
+  /**
+   * Removes the element at the user-supplied index.
+   * 
+   * @param index
+   *          the index of the element to be removed
+   * @return the removed Object
+   * @throws IndexOutOfBoundsException
+   *           if index &lt; 0 || index &gt;= size()
+   */
+  public synchronized E remove(int index)
+  {
+    E[] data = this.data;
+    E[] newData = (E[]) new Object[data.length - 1];
+    System.arraycopy(data, 0, newData, 0, index - 1);
+    System.arraycopy(data, index + 1, newData, index,
+                     data.length - index - 1);
+    E r = data[index];
+    this.data = newData;
+    return r;
+  }
+
+  /**
+   * Removes all elements from this List
+   */
+  public synchronized void clear()
+  {
+    data = (E[]) new Object[0];
+  }
+
+  /**
+   * Add each element in the supplied Collection to this List. It is undefined
+   * what happens if you modify the list while this is taking place; for
+   * example, if the collection contains this list. c can contain objects of any
+   * type, as well as null values.
+   * 
+   * @param c
+   *          a Collection containing elements to be added to this List
+   * @return true if the list was modified, in other words c is not empty
+   * @throws NullPointerException
+   *           if c is null
+   */
+  public synchronized boolean addAll(Collection< ? extends E> c)
+  {
+    return addAll(data.length, c);
+  }
+
+  /**
+   * Add all elements in the supplied collection, inserting them beginning at
+   * the specified index. c can contain objects of any type, as well as null
+   * values.
+   * 
+   * @param index
+   *          the index at which the elements will be inserted
+   * @param c
+   *          the Collection containing the elements to be inserted
+   * @throws IndexOutOfBoundsException
+   *           if index &lt; 0 || index &gt; 0
+   * @throws NullPointerException
+   *           if c is null
+   */
+  public synchronized boolean addAll(int index, Collection< ? extends E> c)
+  {
+    E[] data = this.data;
+    Iterator<? extends E> itr = c.iterator();
+    int csize = c.size();
+    if (csize == 0)
+      return false;
+
+    E[] newData = (E[]) new Object[data.length + csize];
+    System.arraycopy(data, 0, newData, 0, data.length);
+    int end = data.length;
+    for (E value : c)
+      newData[end++] = value;
+    this.data = newData;
+    return true;
+  }
+  
+  public synchronized boolean addIfAbsent(E val)
+  {
+    if (contains(val))
+      return false;
+    add(val);
+    return true;
+  }
+
+  public synchronized int addAllAbsent(Collection<? extends E> c)
+  {
+    int result = 0;
+    for (E val : c)
+      {
+        if (addIfAbsent(val))
+          ++result;
+      }
+    return result;
+  }
+
+  /**
+   * Serializes this object to the given stream.
+   * 
+   * @param s
+   *          the stream to write to
+   * @throws IOException
+   *           if the underlying stream fails
+   * @serialData the size field (int), the length of the backing array (int),
+   *             followed by its elements (Objects) in proper order.
+   */
+  private void writeObject(ObjectOutputStream s) throws IOException
+  {
+    // The 'size' field.
+    s.defaultWriteObject();
+    // We serialize unused list entries to preserve capacity.
+    int len = data.length;
+    s.writeInt(len);
+    // it would be more efficient to just write "size" items,
+    // this need readObject read "size" items too.
+    for (int i = 0; i < data.length; i++)
+      s.writeObject(data[i]);
+  }
+
+  /**
+   * Deserializes this object from the given stream.
+   * 
+   * @param s
+   *          the stream to read from
+   * @throws ClassNotFoundException
+   *           if the underlying stream fails
+   * @throws IOException
+   *           if the underlying stream fails
+   * @serialData the size field (int), the length of the backing array (int),
+   *             followed by its elements (Objects) in proper order.
+   */
+  private void readObject(ObjectInputStream s) throws IOException,
+      ClassNotFoundException
+  {
+    // the `size' field.
+    s.defaultReadObject();
+    int capacity = s.readInt();
+    data = (E[]) new Object[capacity];
+    for (int i = 0; i < capacity; i++)
+      data[i] = (E) s.readObject();
+  }
+
+  static final boolean equals(Object o1, Object o2)
+  {
+    return o1 == null ? o2 == null : o1.equals(o2);
+  }
+  
+  Object[] getArray()
+  {
+    return data;
+  }
+}