util/concurrent/DelayQueue.java

/*
 * 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.locks.*;
import java.util.*;

/**
 * An unbounded {@linkplain BlockingQueue blocking queue} of
 * <tt>Delayed</tt> elements, in which an element can only be taken
 * when its delay has expired.  The <em>head</em> of the queue is that
 * <tt>Delayed</tt> element whose delay expired furthest in the
 * past.  If no delay has expired there is no head and <tt>poll</tt>
 * will return <tt>null</tt>. Expiration occurs when an element's
 * <tt>getDelay(TimeUnit.NANOSECONDS)</tt> method returns a value less
 * than or equal to zero.  Even though unexpired elements cannot be
 * removed using <tt>take</tt> or <tt>poll</tt>, they are otherwise
 * treated as normal elements. For example, the <tt>size</tt> method
 * returns the count of both expired and unexpired elements.
 * This queue does not permit null elements.
 *
 * <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>.
 *
 * @since 1.5
 * @author Doug Lea
 * @param <E> the type of elements held in this collection
 */

public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
    implements BlockingQueue<E> {

    private transient final ReentrantLock lock = new ReentrantLock();
    private transient final Condition available = lock.newCondition();
    private final PriorityQueue<E> q = new PriorityQueue<E>();

    /**
     * Creates a new <tt>DelayQueue</tt> that is initially empty.
     */
    public DelayQueue() {}

    /**
     * Creates a <tt>DelayQueue</tt> initially containing the elements of the
     * given collection of {@link Delayed} instances.
     *
     * @param c the collection of elements to initially contain
     * @throws NullPointerException if the specified collection or any
     *         of its elements are null
     */
    public DelayQueue(Collection<? extends E> c) {
        this.addAll(c);
    }

    /**
     * Inserts the specified element into this delay queue.
     *
     * @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) {
        return offer(e);
    }

    /**
     * Inserts the specified element into this delay queue.
     *
     * @param e the element to add
     * @return <tt>true</tt>
     * @throws NullPointerException if the specified element is null
     */
    public boolean offer(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            E first = q.peek();
            q.offer(e);
            if (first == null || e.compareTo(first) < 0)
                available.signalAll();
            return true;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Inserts the specified element into this delay queue. As the queue is
     * unbounded this method will never block.
     *
     * @param e the element to add
     * @throws NullPointerException {@inheritDoc}
     */
    public void put(E e) {
        offer(e);
    }

    /**
     * Inserts the specified element into this delay queue. As the queue is
     * unbounded this method will never block.
     *
     * @param e the element to add
     * @param timeout This parameter is ignored as the method never blocks
     * @param unit This parameter is ignored as the method never blocks
     * @return <tt>true</tt>
     * @throws NullPointerException {@inheritDoc}
     */
    public boolean offer(E e, long timeout, TimeUnit unit) {
        return offer(e);
    }

    /**
     * Retrieves and removes the head of this queue, or returns <tt>null</tt>
     * if this queue has no elements with an expired delay.
     *
     * @return the head of this queue, or <tt>null</tt> if this
     *         queue has no elements with an expired delay
     */
    public E poll() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            E first = q.peek();
            if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0)
                return null;
            else {
                E x = q.poll();
                assert x != null;
                if (q.size() != 0)
                    available.signalAll();
                return x;
            }
        } finally {
            lock.unlock();
        }
    }

    /**
     * Retrieves and removes the head of this queue, waiting if necessary
     * until an element with an expired delay is available on this queue.
     *
     * @return the head of this queue
     * @throws InterruptedException {@inheritDoc}
     */
    public E take() throws InterruptedException {
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            for (;;) {
                E first = q.peek();
                if (first == null) {
                    available.await();
                } else {
                    long delay =  first.getDelay(TimeUnit.NANOSECONDS);
                    if (delay > 0) {
                        long tl = available.awaitNanos(delay);
                    } else {
                        E x = q.poll();
                        assert x != null;
                        if (q.size() != 0)
                            available.signalAll(); // wake up other takers
                        return x;

                    }
                }
            }
        } finally {
            lock.unlock();
        }
    }

    /**
     * Retrieves and removes the head of this queue, waiting if necessary
     * until an element with an expired delay is available on this queue,
     * or the specified wait time expires.
     *
     * @return the head of this queue, or <tt>null</tt> if the
     *         specified waiting time elapses before an element with
     *         an expired delay becomes available
     * @throws InterruptedException {@inheritDoc}
     */
    public E poll(long timeout, TimeUnit unit) throws InterruptedException {
        long nanos = unit.toNanos(timeout);
        final ReentrantLock lock = this.lock;
        lock.lockInterruptibly();
        try {
            for (;;) {
                E first = q.peek();
                if (first == null) {
                    if (nanos <= 0)
                        return null;
                    else
                        nanos = available.awaitNanos(nanos);
                } else {
                    long delay = first.getDelay(TimeUnit.NANOSECONDS);
                    if (delay > 0) {
                        if (nanos <= 0)
                            return null;
                        if (delay > nanos)
                            delay = nanos;
                        long timeLeft = available.awaitNanos(delay);
                        nanos -= delay - timeLeft;
                    } else {
                        E x = q.poll();
                        assert x != null;
                        if (q.size() != 0)
                            available.signalAll();
                        return x;
                    }
                }
            }
        } finally {
            lock.unlock();
        }
    }

    /**
     * Retrieves, but does not remove, the head of this queue, or
     * returns <tt>null</tt> if this queue is empty.  Unlike
     * <tt>poll</tt>, if no expired elements are available in the queue,
     * this method returns the element that will expire next,
     * if one exists.
     *
     * @return the head of this queue, or <tt>null</tt> if this
     *         queue is empty.
     */
    public E peek() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return q.peek();
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return q.size();
        } finally {
            lock.unlock();
        }
    }

    /**
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     */
    public int drainTo(Collection<? super E> c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int n = 0;
            for (;;) {
                E first = q.peek();
                if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0)
                    break;
                c.add(q.poll());
                ++n;
            }
            if (n > 0)
                available.signalAll();
            return n;
        } finally {
            lock.unlock();
        }
    }

    /**
     * @throws UnsupportedOperationException {@inheritDoc}
     * @throws ClassCastException            {@inheritDoc}
     * @throws NullPointerException          {@inheritDoc}
     * @throws IllegalArgumentException      {@inheritDoc}
     */
    public int drainTo(Collection<? super E> c, int maxElements) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        if (maxElements <= 0)
            return 0;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            int n = 0;
            while (n < maxElements) {
                E first = q.peek();
                if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0)
                    break;
                c.add(q.poll());
                ++n;
            }
            if (n > 0)
                available.signalAll();
            return n;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Atomically removes all of the elements from this delay queue.
     * The queue will be empty after this call returns.
     * Elements with an unexpired delay are not waited for; they are
     * simply discarded from the queue.
     */
    public void clear() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            q.clear();
        } finally {
            lock.unlock();
        }
    }

    /**
     * Always returns <tt>Integer.MAX_VALUE</tt> because
     * a <tt>DelayQueue</tt> is not capacity constrained.
     *
     * @return <tt>Integer.MAX_VALUE</tt>
     */
    public int remainingCapacity() {
        return Integer.MAX_VALUE;
    }

    /**
     * Returns an array containing all of the elements in this queue.
     * The returned array elements are in no particular order.
     *
     * <p>The returned array will be "safe" in that no references to it are
     * maintained by this queue.  (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 queue
     */
    public Object[] toArray() {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return q.toArray();
        } finally {
            lock.unlock();
        }
    }

    /**
     * Returns an array containing all of the elements in this queue; the
     * runtime type of the returned array is that of the specified array.
     * The returned array elements are in no particular order.
     * If the queue 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 queue.
     *
     * <p>If this queue fits in the specified array with room to spare
     * (i.e., the array has more elements than this queue), the element in
     * the array immediately following the end of the queue 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>The following code can be used to dump a delay queue into a newly
     * allocated array of <tt>Delayed</tt>:
     *
     * <pre>
     *     Delayed[] a = q.toArray(new Delayed[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 queue 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 queue
     * @throws ArrayStoreException if the runtime type of the specified array
     *         is not a supertype of the runtime type of every element in
     *         this queue
     * @throws NullPointerException if the specified array is null
     */
    public <T> T[] toArray(T[] a) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return q.toArray(a);
        } finally {
            lock.unlock();
        }
    }

    /**
     * Removes a single instance of the specified element from this
     * queue, if it is present, whether or not it has expired.
     */
    public boolean remove(Object o) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            return q.remove(o);
        } finally {
            lock.unlock();
        }
    }

    /**
     * Returns an iterator over all the elements (both expired and
     * unexpired) in this queue. The iterator does not return the
     * elements in any particular order.  The returned
     * <tt>Iterator</tt> is a "weakly consistent" iterator that will
     * never throw {@link ConcurrentModificationException}, and
     * guarantees to traverse elements as they existed upon
     * construction of the iterator, and may (but is not guaranteed
     * to) reflect any modifications subsequent to construction.
     *
     * @return an iterator over the elements in this queue
     */
    public Iterator<E> iterator() {
        return new Itr(toArray());
    }

    /**
     * Snapshot iterator that works off copy of underlying q array.
     */
    private class Itr implements Iterator<E> {
        final Object[] array; // Array of all elements
        int cursor;           // index of next element to return;
        int lastRet;          // index of last element, or -1 if no such

        Itr(Object[] array) {
            lastRet = -1;
            this.array = array;
        }

        public boolean hasNext() {
            return cursor < array.length;
        }

        public E next() {
            if (cursor >= array.length)
                throw new NoSuchElementException();
            lastRet = cursor;
            return (E)array[cursor++];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            Object x = array[lastRet];
            lastRet = -1;
            // Traverse underlying queue to find == element,
            // not just a .equals element.
            lock.lock();
            try {
                for (Iterator it = q.iterator(); it.hasNext(); ) {
                    if (it.next() == x) {
                        it.remove();
                        return;
                    }
                }
            } finally {
                lock.unlock();
            }
        }
    }

}
Revision:	1.47
Committed:	Wed Aug 8 16:08:40 2007 UTC (16 years, 9 months ago) by jsr166
Branch:	MAIN
Changes since 1.46:	+0 -1 lines
Log Message:	whitespace
#	Content
1	/*
2	* Written by Doug Lea with assistance from members of JCP JSR-166
3	* Expert Group and released to the public domain, as explained at
4	* http://creativecommons.org/licenses/publicdomain
5	*/
6
7	package java.util.concurrent;
8	import java.util.concurrent.locks.*;
9	import java.util.*;
10
11	/**
12	* An unbounded {@linkplain BlockingQueue blocking queue} of
13	* <tt>Delayed</tt> elements, in which an element can only be taken
14	* when its delay has expired. The <em>head</em> of the queue is that
15	* <tt>Delayed</tt> element whose delay expired furthest in the
16	* past. If no delay has expired there is no head and <tt>poll</tt>
17	* will return <tt>null</tt>. Expiration occurs when an element's
18	* <tt>getDelay(TimeUnit.NANOSECONDS)</tt> method returns a value less
19	* than or equal to zero. Even though unexpired elements cannot be
20	* removed using <tt>take</tt> or <tt>poll</tt>, they are otherwise
21	* treated as normal elements. For example, the <tt>size</tt> method
22	* returns the count of both expired and unexpired elements.
23	* This queue does not permit null elements.
24	*
25	* <p>This class and its iterator implement all of the
26	* <em>optional</em> methods of the {@link Collection} and {@link
27	* Iterator} interfaces.
28	*
29	* <p>This class is a member of the
30	* <a href="{@docRoot}/../technotes/guides/collections/index.html">
31	* Java Collections Framework</a>.
32	*
33	* @since 1.5
34	* @author Doug Lea
35	* @param <E> the type of elements held in this collection
36	*/
37
38	public class DelayQueue<E extends Delayed> extends AbstractQueue<E>
39	implements BlockingQueue<E> {
40
41	private transient final ReentrantLock lock = new ReentrantLock();
42	private transient final Condition available = lock.newCondition();
43	private final PriorityQueue<E> q = new PriorityQueue<E>();
44
45	/**
46	* Creates a new <tt>DelayQueue</tt> that is initially empty.
47	*/
48	public DelayQueue() {}
49
50	/**
51	* Creates a <tt>DelayQueue</tt> initially containing the elements of the
52	* given collection of {@link Delayed} instances.
53	*
54	* @param c the collection of elements to initially contain
55	* @throws NullPointerException if the specified collection or any
56	* of its elements are null
57	*/
58	public DelayQueue(Collection<? extends E> c) {
59	this.addAll(c);
60	}
61
62	/**
63	* Inserts the specified element into this delay queue.
64	*
65	* @param e the element to add
66	* @return <tt>true</tt> (as specified by {@link Collection#add})
67	* @throws NullPointerException if the specified element is null
68	*/
69	public boolean add(E e) {
70	return offer(e);
71	}
72
73	/**
74	* Inserts the specified element into this delay queue.
75	*
76	* @param e the element to add
77	* @return <tt>true</tt>
78	* @throws NullPointerException if the specified element is null
79	*/
80	public boolean offer(E e) {
81	final ReentrantLock lock = this.lock;
82	lock.lock();
83	try {
84	E first = q.peek();
85	q.offer(e);
86	if (first == null \|\| e.compareTo(first) < 0)
87	available.signalAll();
88	return true;
89	} finally {
90	lock.unlock();
91	}
92	}
93
94	/**
95	* Inserts the specified element into this delay queue. As the queue is
96	* unbounded this method will never block.
97	*
98	* @param e the element to add
99	* @throws NullPointerException {@inheritDoc}
100	*/
101	public void put(E e) {
102	offer(e);
103	}
104
105	/**
106	* Inserts the specified element into this delay queue. As the queue is
107	* unbounded this method will never block.
108	*
109	* @param e the element to add
110	* @param timeout This parameter is ignored as the method never blocks
111	* @param unit This parameter is ignored as the method never blocks
112	* @return <tt>true</tt>
113	* @throws NullPointerException {@inheritDoc}
114	*/
115	public boolean offer(E e, long timeout, TimeUnit unit) {
116	return offer(e);
117	}
118
119	/**
120	* Retrieves and removes the head of this queue, or returns <tt>null</tt>
121	* if this queue has no elements with an expired delay.
122	*
123	* @return the head of this queue, or <tt>null</tt> if this
124	* queue has no elements with an expired delay
125	*/
126	public E poll() {
127	final ReentrantLock lock = this.lock;
128	lock.lock();
129	try {
130	E first = q.peek();
131	if (first == null \|\| first.getDelay(TimeUnit.NANOSECONDS) > 0)
132	return null;
133	else {
134	E x = q.poll();
135	assert x != null;
136	if (q.size() != 0)
137	available.signalAll();
138	return x;
139	}
140	} finally {
141	lock.unlock();
142	}
143	}
144
145	/**
146	* Retrieves and removes the head of this queue, waiting if necessary
147	* until an element with an expired delay is available on this queue.
148	*
149	* @return the head of this queue
150	* @throws InterruptedException {@inheritDoc}
151	*/
152	public E take() throws InterruptedException {
153	final ReentrantLock lock = this.lock;
154	lock.lockInterruptibly();
155	try {
156	for (;;) {
157	E first = q.peek();
158	if (first == null) {
159	available.await();
160	} else {
161	long delay = first.getDelay(TimeUnit.NANOSECONDS);
162	if (delay > 0) {
163	long tl = available.awaitNanos(delay);
164	} else {
165	E x = q.poll();
166	assert x != null;
167	if (q.size() != 0)
168	available.signalAll(); // wake up other takers
169	return x;
170
171	}
172	}
173	}
174	} finally {
175	lock.unlock();
176	}
177	}
178
179	/**
180	* Retrieves and removes the head of this queue, waiting if necessary
181	* until an element with an expired delay is available on this queue,
182	* or the specified wait time expires.
183	*
184	* @return the head of this queue, or <tt>null</tt> if the
185	* specified waiting time elapses before an element with
186	* an expired delay becomes available
187	* @throws InterruptedException {@inheritDoc}
188	*/
189	public E poll(long timeout, TimeUnit unit) throws InterruptedException {
190	long nanos = unit.toNanos(timeout);
191	final ReentrantLock lock = this.lock;
192	lock.lockInterruptibly();
193	try {
194	for (;;) {
195	E first = q.peek();
196	if (first == null) {
197	if (nanos <= 0)
198	return null;
199	else
200	nanos = available.awaitNanos(nanos);
201	} else {
202	long delay = first.getDelay(TimeUnit.NANOSECONDS);
203	if (delay > 0) {
204	if (nanos <= 0)
205	return null;
206	if (delay > nanos)
207	delay = nanos;
208	long timeLeft = available.awaitNanos(delay);
209	nanos -= delay - timeLeft;
210	} else {
211	E x = q.poll();
212	assert x != null;
213	if (q.size() != 0)
214	available.signalAll();
215	return x;
216	}
217	}
218	}
219	} finally {
220	lock.unlock();
221	}
222	}
223
224	/**
225	* Retrieves, but does not remove, the head of this queue, or
226	* returns <tt>null</tt> if this queue is empty. Unlike
227	* <tt>poll</tt>, if no expired elements are available in the queue,
228	* this method returns the element that will expire next,
229	* if one exists.
230	*
231	* @return the head of this queue, or <tt>null</tt> if this
232	* queue is empty.
233	*/
234	public E peek() {
235	final ReentrantLock lock = this.lock;
236	lock.lock();
237	try {
238	return q.peek();
239	} finally {
240	lock.unlock();
241	}
242	}
243
244	public int size() {
245	final ReentrantLock lock = this.lock;
246	lock.lock();
247	try {
248	return q.size();
249	} finally {
250	lock.unlock();
251	}
252	}
253
254	/**
255	* @throws UnsupportedOperationException {@inheritDoc}
256	* @throws ClassCastException {@inheritDoc}
257	* @throws NullPointerException {@inheritDoc}
258	* @throws IllegalArgumentException {@inheritDoc}
259	*/
260	public int drainTo(Collection<? super E> c) {
261	if (c == null)
262	throw new NullPointerException();
263	if (c == this)
264	throw new IllegalArgumentException();
265	final ReentrantLock lock = this.lock;
266	lock.lock();
267	try {
268	int n = 0;
269	for (;;) {
270	E first = q.peek();
271	if (first == null \|\| first.getDelay(TimeUnit.NANOSECONDS) > 0)
272	break;
273	c.add(q.poll());
274	++n;
275	}
276	if (n > 0)
277	available.signalAll();
278	return n;
279	} finally {
280	lock.unlock();
281	}
282	}
283
284	/**
285	* @throws UnsupportedOperationException {@inheritDoc}
286	* @throws ClassCastException {@inheritDoc}
287	* @throws NullPointerException {@inheritDoc}
288	* @throws IllegalArgumentException {@inheritDoc}
289	*/
290	public int drainTo(Collection<? super E> c, int maxElements) {
291	if (c == null)
292	throw new NullPointerException();
293	if (c == this)
294	throw new IllegalArgumentException();
295	if (maxElements <= 0)
296	return 0;
297	final ReentrantLock lock = this.lock;
298	lock.lock();
299	try {
300	int n = 0;
301	while (n < maxElements) {
302	E first = q.peek();
303	if (first == null \|\| first.getDelay(TimeUnit.NANOSECONDS) > 0)
304	break;
305	c.add(q.poll());
306	++n;
307	}
308	if (n > 0)
309	available.signalAll();
310	return n;
311	} finally {
312	lock.unlock();
313	}
314	}
315
316	/**
317	* Atomically removes all of the elements from this delay queue.
318	* The queue will be empty after this call returns.
319	* Elements with an unexpired delay are not waited for; they are
320	* simply discarded from the queue.
321	*/
322	public void clear() {
323	final ReentrantLock lock = this.lock;
324	lock.lock();
325	try {
326	q.clear();
327	} finally {
328	lock.unlock();
329	}
330	}
331
332	/**
333	* Always returns <tt>Integer.MAX_VALUE</tt> because
334	* a <tt>DelayQueue</tt> is not capacity constrained.
335	*
336	* @return <tt>Integer.MAX_VALUE</tt>
337	*/
338	public int remainingCapacity() {
339	return Integer.MAX_VALUE;
340	}
341
342	/**
343	* Returns an array containing all of the elements in this queue.
344	* The returned array elements are in no particular order.
345	*
346	* <p>The returned array will be "safe" in that no references to it are
347	* maintained by this queue. (In other words, this method must allocate
348	* a new array). The caller is thus free to modify the returned array.
349	*
350	* <p>This method acts as bridge between array-based and collection-based
351	* APIs.
352	*
353	* @return an array containing all of the elements in this queue
354	*/
355	public Object[] toArray() {
356	final ReentrantLock lock = this.lock;
357	lock.lock();
358	try {
359	return q.toArray();
360	} finally {
361	lock.unlock();
362	}
363	}
364
365	/**
366	* Returns an array containing all of the elements in this queue; the
367	* runtime type of the returned array is that of the specified array.
368	* The returned array elements are in no particular order.
369	* If the queue fits in the specified array, it is returned therein.
370	* Otherwise, a new array is allocated with the runtime type of the
371	* specified array and the size of this queue.
372	*
373	* <p>If this queue fits in the specified array with room to spare
374	* (i.e., the array has more elements than this queue), the element in
375	* the array immediately following the end of the queue is set to
376	* <tt>null</tt>.
377	*
378	* <p>Like the {@link #toArray()} method, this method acts as bridge between
379	* array-based and collection-based APIs. Further, this method allows
380	* precise control over the runtime type of the output array, and may,
381	* under certain circumstances, be used to save allocation costs.
382	*
383	* <p>The following code can be used to dump a delay queue into a newly
384	* allocated array of <tt>Delayed</tt>:
385	*
386	* <pre>
387	* Delayed[] a = q.toArray(new Delayed[0]);</pre>
388	*
389	* Note that <tt>toArray(new Object[0])</tt> is identical in function to
390	* <tt>toArray()</tt>.
391	*
392	* @param a the array into which the elements of the queue are to
393	* be stored, if it is big enough; otherwise, a new array of the
394	* same runtime type is allocated for this purpose
395	* @return an array containing all of the elements in this queue
396	* @throws ArrayStoreException if the runtime type of the specified array
397	* is not a supertype of the runtime type of every element in
398	* this queue
399	* @throws NullPointerException if the specified array is null
400	*/
401	public <T> T[] toArray(T[] a) {
402	final ReentrantLock lock = this.lock;
403	lock.lock();
404	try {
405	return q.toArray(a);
406	} finally {
407	lock.unlock();
408	}
409	}
410
411	/**
412	* Removes a single instance of the specified element from this
413	* queue, if it is present, whether or not it has expired.
414	*/
415	public boolean remove(Object o) {
416	final ReentrantLock lock = this.lock;
417	lock.lock();
418	try {
419	return q.remove(o);
420	} finally {
421	lock.unlock();
422	}
423	}
424
425	/**
426	* Returns an iterator over all the elements (both expired and
427	* unexpired) in this queue. The iterator does not return the
428	* elements in any particular order. The returned
429	* <tt>Iterator</tt> is a "weakly consistent" iterator that will
430	* never throw {@link ConcurrentModificationException}, and
431	* guarantees to traverse elements as they existed upon
432	* construction of the iterator, and may (but is not guaranteed
433	* to) reflect any modifications subsequent to construction.
434	*
435	* @return an iterator over the elements in this queue
436	*/
437	public Iterator<E> iterator() {
438	return new Itr(toArray());
439	}
440
441	/**
442	* Snapshot iterator that works off copy of underlying q array.
443	*/
444	private class Itr implements Iterator<E> {
445	final Object[] array; // Array of all elements
446	int cursor; // index of next element to return;
447	int lastRet; // index of last element, or -1 if no such
448
449	Itr(Object[] array) {
450	lastRet = -1;
451	this.array = array;
452	}
453
454	public boolean hasNext() {
455	return cursor < array.length;
456	}
457
458	public E next() {
459	if (cursor >= array.length)
460	throw new NoSuchElementException();
461	lastRet = cursor;
462	return (E)array[cursor++];
463	}
464
465	public void remove() {
466	if (lastRet < 0)
467	throw new IllegalStateException();
468	Object x = array[lastRet];
469	lastRet = -1;
470	// Traverse underlying queue to find == element,
471	// not just a .equals element.
472	lock.lock();
473	try {
474	for (Iterator it = q.iterator(); it.hasNext(); ) {
475	if (it.next() == x) {
476	it.remove();
477	return;
478	}
479	}
480	} finally {
481	lock.unlock();
482	}
483	}
484	}
485
486	}