util/concurrent/PriorityBlockingQueue.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain. Use, modify, and
 * redistribute this code in any way without acknowledgement.
 */

package java.util.concurrent;

import java.util.concurrent.locks.*;
import java.util.*;

/**
 * An unbounded {@linkplain BlockingQueue blocking queue} that uses
 * the same ordering rules as class {@link PriorityQueue} and supplies
 * blocking retrieval operations.  While this queue is logically
 * unbounded, attempted additions may fail due to resource exhaustion
 * (causing <tt>OutOfMemoryError</tt>). This class does not permit
 * <tt>null</tt> elements.  A priority queue relying on natural
 * ordering also does not permit insertion of non-comparable objects
 * (doing so results in <tt>ClassCastException</tt>).
 *
 * <p>This class implements all of the <em>optional</em> methods
 * of the {@link Collection} and {@link Iterator} interfaces.
 * <p>The Iterator provided in method {@link #iterator()} is
 * <em>not</em> guaranteed to traverse the elements of the
 * PriorityBlockingQueue in any particular order. If you need ordered
 * traversal, consider using <tt>Arrays.sort(pq.toArray())</tt>.
 *
 * @since 1.5
 * @author Doug Lea
 * @param <E> the type of elements held in this collection
 */
public class PriorityBlockingQueue<E> extends AbstractQueue<E>
    implements BlockingQueue<E>, java.io.Serializable {
    private static final long serialVersionUID = 5595510919245408276L;

    private final PriorityQueue<E> q;
    private final ReentrantLock lock = new ReentrantLock(true);
    private final ReentrantLock.ConditionObject notEmpty = lock.newCondition();

    /**
     * Creates a <tt>PriorityBlockingQueue</tt> with the default initial 
     * capacity
     * (11) that orders its elements according to their natural
     * ordering (using <tt>Comparable</tt>).
     */
    public PriorityBlockingQueue() {
        q = new PriorityQueue<E>();
    }

    /**
     * Creates a <tt>PriorityBlockingQueue</tt> with the specified initial
     * capacity
     * that orders its elements according to their natural ordering
     * (using <tt>Comparable</tt>).
     *
     * @param initialCapacity the initial capacity for this priority queue.
     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
     * than 1
     */
    public PriorityBlockingQueue(int initialCapacity) {
        q = new PriorityQueue<E>(initialCapacity, null);
    }

    /**
     * Creates a <tt>PriorityBlockingQueue</tt> with the specified initial
     * capacity
     * that orders its elements according to the specified comparator.
     *
     * @param initialCapacity the initial capacity for this priority queue.
     * @param comparator the comparator used to order this priority queue.
     * If <tt>null</tt> then the order depends on the elements' natural
     * ordering.
     * @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
     * than 1
     */
    public PriorityBlockingQueue(int initialCapacity,
                                 Comparator<? super E> comparator) {
        q = new PriorityQueue<E>(initialCapacity, comparator);
    }

    /**
     * Creates a <tt>PriorityBlockingQueue</tt> containing the elements
     * in the specified collection.  The priority queue has an initial
     * capacity of 110% of the size of the specified collection. If
     * the specified collection is a {@link SortedSet} or a {@link
     * PriorityQueue}, this priority queue will be sorted according to
     * the same comparator, or according to its elements' natural
     * order if the collection is sorted according to its elements'
     * natural order.  Otherwise, this priority queue is ordered
     * according to its elements' natural order.
     *
     * @param c the collection whose elements are to be placed
     *        into this priority queue.
     * @throws ClassCastException if elements of the specified collection
     *         cannot be compared to one another according to the priority
     *         queue's ordering.
     * @throws NullPointerException if <tt>c</tt> or any element within it
     * is <tt>null</tt>
     */
    public PriorityBlockingQueue(Collection<? extends E> c) {
        q = new PriorityQueue<E>(c);
    }


    // these first few override just to update doc comments

    /**
     * Adds the specified element to this queue.
     * @return <tt>true</tt> (as per the general contract of
     * <tt>Collection.add</tt>).
     *
     * @throws NullPointerException if the specified element is <tt>null</tt>.
     * @throws ClassCastException if the specified element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     */
    public boolean add(E o) {
        return super.add(o);
    }

    /**
     * Returns the comparator used to order this collection, or <tt>null</tt>
     * if this collection is sorted according to its elements natural ordering
     * (using <tt>Comparable</tt>).
     *
     * @return the comparator used to order this collection, or <tt>null</tt>
     * if this collection is sorted according to its elements natural ordering.
     */
    public Comparator comparator() {
        return q.comparator();
    }

    /**
     * Inserts the specified element into this priority queue.
     *
     * @param o the element to add
     * @return <tt>true</tt>
     * @throws ClassCastException if the specified element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     * @throws NullPointerException if the specified element is <tt>null</tt>.
     */
    public boolean offer(E o) {
        if (o == null) throw new NullPointerException();
        lock.lock();
        try {
            boolean ok = q.offer(o);
            assert ok;
            notEmpty.signal();
            return true;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Adds the specified element to this priority queue. As the queue is
     * unbounded this method will never block.
     * @param o the element to add
     * @throws ClassCastException if the element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     * @throws NullPointerException if the specified element is <tt>null</tt>.
     */
    public void put(E o) {
        offer(o); // never need to block
    }

    /**
     * Inserts the specified element into this priority queue. As the queue is
     * unbounded this method will never block.
     * @param o 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 ClassCastException if the element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     * @throws NullPointerException if the specified element is <tt>null</tt>.
     */
    public boolean offer(E o, long timeout, TimeUnit unit) {
        return offer(o); // never need to block
    }

    public E take() throws InterruptedException {
        lock.lockInterruptibly();
        try {
            try {
                while (q.size() == 0)
                    notEmpty.await();
            } catch (InterruptedException ie) {
                notEmpty.signal(); // propagate to non-interrupted thread
                throw ie;
            }
            E x = q.poll();
            assert x != null;
            return x;
        } finally {
            lock.unlock();
        }
    }


    public E poll() {
        lock.lock();
        try {
            return q.poll();
        } finally {
            lock.unlock();
        }
    }

    public E poll(long timeout, TimeUnit unit) throws InterruptedException {
        long nanos = unit.toNanos(timeout);
        lock.lockInterruptibly();
        try {
            for (;;) {
                E x = q.poll();
                if (x != null)
                    return x;
                if (nanos <= 0)
                    return null;
                try {
                    nanos = notEmpty.awaitNanos(nanos);
                } catch (InterruptedException ie) {
                    notEmpty.signal(); // propagate to non-interrupted thread
                    throw ie;
                }
            }
        } finally {
            lock.unlock();
        }
    }

    public E peek() {
        lock.lock();
        try {
            return q.peek();
        } finally {
            lock.unlock();
        }
    }

    public int size() {
        lock.lock();
        try {
            return q.size();
        } finally {
            lock.unlock();
        }
    }

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

    public boolean remove(Object o) {
        lock.lock();
        try {
            return q.remove(o);
        } finally {
            lock.unlock();
        }
    }

    public boolean contains(Object o) {
        lock.lock();
        try {
            return q.contains(o);
        } finally {
            lock.unlock();
        }
    }

    public Object[] toArray() {
        lock.lock();
        try {
            return q.toArray();
        } finally {
            lock.unlock();
        }
    }


    public String toString() {
        lock.lock();
        try {
            return q.toString();
        } finally {
            lock.unlock();
        }
    }

    public int drainTo(Collection<? super E> c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        lock.lock();
        try {
            int n = 0;
            E e;
            while ( (e = q.poll()) != null) {
                c.add(e);
                ++n;
            }
            return n;
        } finally {
            lock.unlock();
        }
    }

    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;
        lock.lock();
        try {
            int n = 0;
            E e;
            while (n < maxElements && (e = q.poll()) != null) {
                c.add(e);
                ++n;
            }
            return n;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Atomically removes all of the elements from this delay queue.
     * The queue will be empty after this call returns.
     */
    public void clear() {
        lock.lock();
        try {
            q.clear();
        } finally {
            lock.unlock();
        }
    }

    public <T> T[] toArray(T[] a) {
        lock.lock();
        try {
            return q.toArray(a);
        } finally {
            lock.unlock();
        }
    }

    /**
     * Returns an iterator over the elements in this queue. The
     * iterator does not return the elements in any particular order.
     * The returned iterator is a thread-safe "fast-fail" iterator
     * that will throw {@link
     * java.util.ConcurrentModificationException} upon detected
     * interference.
     *
     * @return an iterator over the elements in this queue.
     */
    public Iterator<E> iterator() {
        lock.lock();
        try {
            return new Itr(q.iterator());
        } finally {
            lock.unlock();
        }
    }

    private class Itr<E> implements Iterator<E> {
        private final Iterator<E> iter;
        Itr(Iterator<E> i) {
            iter = i;
        }

        public boolean hasNext() {
            /*
             * No sync -- we rely on underlying hasNext to be
             * stateless, in which case we can return true by mistake
             * only when next() will subsequently throw
             * ConcurrentModificationException.
             */
            return iter.hasNext();
        }

        public E next() {
            lock.lock();
            try {
                return iter.next();
            } finally {
                lock.unlock();
            }
        }

        public void remove() {
            lock.lock();
            try {
                iter.remove();
            } finally {
                lock.unlock();
            }
        }
    }

    /**
     * Save the state to a stream (that is, serialize it).  This
     * merely wraps default serialization within lock.  The
     * serialization strategy for items is left to underlying
     * Queue. Note that locking is not needed on deserialization, so
     * readObject is not defined, just relying on default.
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        lock.lock();
        try {
            s.defaultWriteObject();
        } finally {
            lock.unlock();
        }
    }

}
Revision:	1.30
Committed:	Wed Nov 12 01:04:24 2003 UTC (20 years, 6 months ago) by dl
Branch:	MAIN
CVS Tags:	JSR166_DEC9_PRE_ES_SUBMIT, JSR166_DEC9_POST_ES_SUBMIT
Changes since 1.29:	+1 -1 lines
Log Message:	fixed typos; avoided some casts
#	User	Rev	Content
1	dl	1.2	/*
2			* Written by Doug Lea with assistance from members of JCP JSR-166
3			* Expert Group and released to the public domain. Use, modify, and
4			* redistribute this code in any way without acknowledgement.
5			*/
6
7	tim	1.1	package java.util.concurrent;
8	tim	1.13
9	dl	1.8	import java.util.concurrent.locks.*;
10	tim	1.1	import java.util.*;
11
12			/**
13	dl	1.25	* An unbounded {@linkplain BlockingQueue blocking queue} that uses
14			* the same ordering rules as class {@link PriorityQueue} and supplies
15			* blocking retrieval operations. While this queue is logically
16	dl	1.24	* unbounded, attempted additions may fail due to resource exhaustion
17	dl	1.25	* (causing <tt>OutOfMemoryError</tt>). This class does not permit
18			* <tt>null</tt> elements. A priority queue relying on natural
19	dl	1.24	* ordering also does not permit insertion of non-comparable objects
20			* (doing so results in <tt>ClassCastException</tt>).
21	dl	1.20	*
22	dl	1.23	* <p>This class implements all of the <em>optional</em> methods
23			* of the {@link Collection} and {@link Iterator} interfaces.
24	dl	1.20	* <p>The Iterator provided in method {@link #iterator()} is
25			* <em>not</em> guaranteed to traverse the elements of the
26			* PriorityBlockingQueue in any particular order. If you need ordered
27			* traversal, consider using <tt>Arrays.sort(pq.toArray())</tt>.
28			*
29	dl	1.6	* @since 1.5
30			* @author Doug Lea
31	dl	1.29	* @param <E> the type of elements held in this collection
32	dl	1.28	*/
33	dl	1.5	public class PriorityBlockingQueue<E> extends AbstractQueue<E>
34	dl	1.15	implements BlockingQueue<E>, java.io.Serializable {
35	dl	1.21	private static final long serialVersionUID = 5595510919245408276L;
36	tim	1.1
37	dl	1.5	private final PriorityQueue<E> q;
38	dl	1.9	private final ReentrantLock lock = new ReentrantLock(true);
39	dl	1.27	private final ReentrantLock.ConditionObject notEmpty = lock.newCondition();
40	dl	1.5
41	dl	1.2	/**
42	dholmes	1.16	* Creates a <tt>PriorityBlockingQueue</tt> with the default initial
43	dholmes	1.14	* capacity
44	dholmes	1.10	* (11) that orders its elements according to their natural
45	tim	1.18	* ordering (using <tt>Comparable</tt>).
46	dl	1.2	*/
47			public PriorityBlockingQueue() {
48	dl	1.5	q = new PriorityQueue<E>();
49	dl	1.2	}
50
51			/**
52	dholmes	1.16	* Creates a <tt>PriorityBlockingQueue</tt> with the specified initial
53	dholmes	1.10	* capacity
54			* that orders its elements according to their natural ordering
55	tim	1.18	* (using <tt>Comparable</tt>).
56	dl	1.2	*
57			* @param initialCapacity the initial capacity for this priority queue.
58	dholmes	1.16	* @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
59			* than 1
60	dl	1.2	*/
61			public PriorityBlockingQueue(int initialCapacity) {
62	dl	1.5	q = new PriorityQueue<E>(initialCapacity, null);
63	dl	1.2	}
64
65			/**
66	dholmes	1.16	* Creates a <tt>PriorityBlockingQueue</tt> with the specified initial
67	dholmes	1.10	* capacity
68	dl	1.2	* that orders its elements according to the specified comparator.
69			*
70			* @param initialCapacity the initial capacity for this priority queue.
71			* @param comparator the comparator used to order this priority queue.
72	dholmes	1.10	* If <tt>null</tt> then the order depends on the elements' natural
73			* ordering.
74	dholmes	1.16	* @throws IllegalArgumentException if <tt>initialCapacity</tt> is less
75			* than 1
76	dl	1.2	*/
77	tim	1.13	public PriorityBlockingQueue(int initialCapacity,
78	dholmes	1.14	Comparator<? super E> comparator) {
79	dl	1.5	q = new PriorityQueue<E>(initialCapacity, comparator);
80	dl	1.2	}
81
82			/**
83	dholmes	1.16	* Creates a <tt>PriorityBlockingQueue</tt> containing the elements
84	dl	1.15	* in the specified collection. The priority queue has an initial
85			* capacity of 110% of the size of the specified collection. If
86			* the specified collection is a {@link SortedSet} or a {@link
87			* PriorityQueue}, this priority queue will be sorted according to
88			* the same comparator, or according to its elements' natural
89			* order if the collection is sorted according to its elements'
90			* natural order. Otherwise, this priority queue is ordered
91			* according to its elements' natural order.
92	dl	1.2	*
93	dholmes	1.14	* @param c the collection whose elements are to be placed
94	dl	1.2	* into this priority queue.
95			* @throws ClassCastException if elements of the specified collection
96			* cannot be compared to one another according to the priority
97			* queue's ordering.
98	dholmes	1.14	* @throws NullPointerException if <tt>c</tt> or any element within it
99			* is <tt>null</tt>
100	dl	1.2	*/
101	dholmes	1.14	public PriorityBlockingQueue(Collection<? extends E> c) {
102			q = new PriorityQueue<E>(c);
103	dl	1.7	}
104
105	dholmes	1.10
106	dholmes	1.16	// these first few override just to update doc comments
107	dholmes	1.10
108			/**
109	dholmes	1.16	* Adds the specified element to this queue.
110			* @return <tt>true</tt> (as per the general contract of
111			* <tt>Collection.add</tt>).
112			*
113	dl	1.22	* @throws NullPointerException if the specified element is <tt>null</tt>.
114	dholmes	1.16	* @throws ClassCastException if the specified element cannot be compared
115			* with elements currently in the priority queue according
116			* to the priority queue's ordering.
117	dholmes	1.10	*/
118	dholmes	1.16	public boolean add(E o) {
119			return super.add(o);
120	dholmes	1.10	}
121
122	tim	1.13	/**
123	dholmes	1.16	* Returns the comparator used to order this collection, or <tt>null</tt>
124			* if this collection is sorted according to its elements natural ordering
125	tim	1.18	* (using <tt>Comparable</tt>).
126	dholmes	1.16	*
127			* @return the comparator used to order this collection, or <tt>null</tt>
128			* if this collection is sorted according to its elements natural ordering.
129			*/
130	dl	1.7	public Comparator comparator() {
131			return q.comparator();
132	dl	1.5	}
133
134	dholmes	1.16	/**
135	dl	1.24	* Inserts the specified element into this priority queue.
136	dholmes	1.16	*
137	dl	1.22	* @param o the element to add
138	dholmes	1.16	* @return <tt>true</tt>
139			* @throws ClassCastException if the specified element cannot be compared
140			* with elements currently in the priority queue according
141			* to the priority queue's ordering.
142	dl	1.22	* @throws NullPointerException if the specified element is <tt>null</tt>.
143	dholmes	1.16	*/
144	dholmes	1.14	public boolean offer(E o) {
145			if (o == null) throw new NullPointerException();
146	dl	1.5	lock.lock();
147			try {
148	dholmes	1.14	boolean ok = q.offer(o);
149	dl	1.5	assert ok;
150			notEmpty.signal();
151			return true;
152	tim	1.19	} finally {
153	tim	1.13	lock.unlock();
154	dl	1.5	}
155			}
156
157	dholmes	1.16	/**
158			* Adds the specified element to this priority queue. As the queue is
159			* unbounded this method will never block.
160	dl	1.22	* @param o the element to add
161	dholmes	1.16	* @throws ClassCastException if the element cannot be compared
162			* with elements currently in the priority queue according
163			* to the priority queue's ordering.
164	dl	1.22	* @throws NullPointerException if the specified element is <tt>null</tt>.
165	dholmes	1.16	*/
166			public void put(E o) {
167	dholmes	1.14	offer(o); // never need to block
168	dl	1.5	}
169
170	dholmes	1.16	/**
171	dl	1.24	* Inserts the specified element into this priority queue. As the queue is
172	dholmes	1.16	* unbounded this method will never block.
173	dl	1.22	* @param o the element to add
174	dholmes	1.16	* @param timeout This parameter is ignored as the method never blocks
175			* @param unit This parameter is ignored as the method never blocks
176	dl	1.22	* @return <tt>true</tt>
177	dholmes	1.16	* @throws ClassCastException if the element cannot be compared
178			* with elements currently in the priority queue according
179			* to the priority queue's ordering.
180	dl	1.22	* @throws NullPointerException if the specified element is <tt>null</tt>.
181	dholmes	1.16	*/
182			public boolean offer(E o, long timeout, TimeUnit unit) {
183	dholmes	1.14	return offer(o); // never need to block
184	dl	1.5	}
185
186			public E take() throws InterruptedException {
187			lock.lockInterruptibly();
188			try {
189			try {
190			while (q.size() == 0)
191			notEmpty.await();
192	tim	1.19	} catch (InterruptedException ie) {
193	dl	1.5	notEmpty.signal(); // propagate to non-interrupted thread
194			throw ie;
195			}
196			E x = q.poll();
197			assert x != null;
198			return x;
199	tim	1.19	} finally {
200	dl	1.5	lock.unlock();
201			}
202			}
203
204
205			public E poll() {
206			lock.lock();
207			try {
208			return q.poll();
209	tim	1.19	} finally {
210	tim	1.13	lock.unlock();
211	dl	1.5	}
212			}
213
214			public E poll(long timeout, TimeUnit unit) throws InterruptedException {
215	dholmes	1.10	long nanos = unit.toNanos(timeout);
216	dl	1.5	lock.lockInterruptibly();
217			try {
218			for (;;) {
219			E x = q.poll();
220	tim	1.13	if (x != null)
221	dl	1.5	return x;
222			if (nanos <= 0)
223			return null;
224			try {
225			nanos = notEmpty.awaitNanos(nanos);
226	tim	1.19	} catch (InterruptedException ie) {
227	dl	1.5	notEmpty.signal(); // propagate to non-interrupted thread
228			throw ie;
229			}
230			}
231	tim	1.19	} finally {
232	dl	1.5	lock.unlock();
233			}
234			}
235
236			public E peek() {
237			lock.lock();
238			try {
239			return q.peek();
240	tim	1.19	} finally {
241	tim	1.13	lock.unlock();
242	dl	1.5	}
243			}
244
245			public int size() {
246			lock.lock();
247			try {
248			return q.size();
249	tim	1.19	} finally {
250	dl	1.5	lock.unlock();
251			}
252			}
253
254			/**
255			* Always returns <tt>Integer.MAX_VALUE</tt> because
256	dholmes	1.16	* a <tt>PriorityBlockingQueue</tt> is not capacity constrained.
257	dl	1.5	* @return <tt>Integer.MAX_VALUE</tt>
258			*/
259			public int remainingCapacity() {
260			return Integer.MAX_VALUE;
261			}
262
263	dholmes	1.14	public boolean remove(Object o) {
264	dl	1.5	lock.lock();
265			try {
266	dholmes	1.14	return q.remove(o);
267	tim	1.19	} finally {
268	dl	1.5	lock.unlock();
269			}
270			}
271
272	dholmes	1.14	public boolean contains(Object o) {
273	dl	1.5	lock.lock();
274			try {
275	dholmes	1.14	return q.contains(o);
276	tim	1.19	} finally {
277	dl	1.5	lock.unlock();
278			}
279			}
280
281			public Object[] toArray() {
282			lock.lock();
283			try {
284			return q.toArray();
285	tim	1.19	} finally {
286	dl	1.5	lock.unlock();
287			}
288			}
289
290
291			public String toString() {
292			lock.lock();
293			try {
294			return q.toString();
295	tim	1.19	} finally {
296	dl	1.5	lock.unlock();
297			}
298			}
299
300	dl	1.26	public int drainTo(Collection<? super E> c) {
301			if (c == null)
302			throw new NullPointerException();
303			if (c == this)
304			throw new IllegalArgumentException();
305			lock.lock();
306			try {
307			int n = 0;
308			E e;
309			while ( (e = q.poll()) != null) {
310			c.add(e);
311			++n;
312			}
313			return n;
314			} finally {
315			lock.unlock();
316			}
317			}
318
319			public int drainTo(Collection<? super E> c, int maxElements) {
320			if (c == null)
321			throw new NullPointerException();
322			if (c == this)
323			throw new IllegalArgumentException();
324			if (maxElements <= 0)
325			return 0;
326			lock.lock();
327			try {
328			int n = 0;
329			E e;
330			while (n < maxElements && (e = q.poll()) != null) {
331			c.add(e);
332			++n;
333			}
334			return n;
335			} finally {
336			lock.unlock();
337			}
338			}
339
340	dl	1.17	/**
341			* Atomically removes all of the elements from this delay queue.
342			* The queue will be empty after this call returns.
343			*/
344			public void clear() {
345			lock.lock();
346			try {
347			q.clear();
348	tim	1.19	} finally {
349	dl	1.17	lock.unlock();
350			}
351			}
352
353	dl	1.5	public <T> T[] toArray(T[] a) {
354			lock.lock();
355			try {
356			return q.toArray(a);
357	tim	1.19	} finally {
358	dl	1.5	lock.unlock();
359			}
360			}
361
362	dholmes	1.16	/**
363	dl	1.23	* Returns an iterator over the elements in this queue. The
364			* iterator does not return the elements in any particular order.
365			* The returned iterator is a thread-safe "fast-fail" iterator
366			* that will throw {@link
367			* java.util.ConcurrentModificationException} upon detected
368			* interference.
369	dholmes	1.16	*
370			* @return an iterator over the elements in this queue.
371			*/
372	dl	1.5	public Iterator<E> iterator() {
373			lock.lock();
374			try {
375			return new Itr(q.iterator());
376	tim	1.19	} finally {
377	dl	1.5	lock.unlock();
378			}
379			}
380
381			private class Itr<E> implements Iterator<E> {
382			private final Iterator<E> iter;
383	tim	1.13	Itr(Iterator<E> i) {
384			iter = i;
385	dl	1.5	}
386
387	tim	1.13	public boolean hasNext() {
388	dl	1.5	/*
389			* No sync -- we rely on underlying hasNext to be
390			* stateless, in which case we can return true by mistake
391	dl	1.30	* only when next() will subsequently throw
392	dl	1.5	* ConcurrentModificationException.
393			*/
394			return iter.hasNext();
395	tim	1.13	}
396
397			public E next() {
398	dl	1.5	lock.lock();
399			try {
400			return iter.next();
401	tim	1.19	} finally {
402	dl	1.5	lock.unlock();
403			}
404	tim	1.13	}
405
406			public void remove() {
407	dl	1.5	lock.lock();
408			try {
409			iter.remove();
410	tim	1.19	} finally {
411	dl	1.5	lock.unlock();
412			}
413	tim	1.13	}
414	dl	1.5	}
415
416			/**
417			* Save the state to a stream (that is, serialize it). This
418			* merely wraps default serialization within lock. The
419			* serialization strategy for items is left to underlying
420			* Queue. Note that locking is not needed on deserialization, so
421			* readObject is not defined, just relying on default.
422			*/
423			private void writeObject(java.io.ObjectOutputStream s)
424			throws java.io.IOException {
425			lock.lock();
426			try {
427			s.defaultWriteObject();
428	tim	1.19	} finally {
429	dl	1.5	lock.unlock();
430			}
431	tim	1.1	}
432
433			}