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} based on a
 * {@link PriorityQueue},
 * obeying its ordering rules and implementation characteristics.
 * While this queue is logically unbounded,
 * attempted additions may fail due to resource exhaustion (causing
 * <tt>OutOfMemoryError</tt>).
 *
 * <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
*/
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 Condition 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 {@inheritDoc}
     * @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);
    }

    /**
     * Adds all of the elements in the specified collection to this queue.
     * The behavior of this operation is undefined if
     * the specified collection is modified while the operation is in
     * progress.  (This implies that the behavior of this call is undefined if
     * the specified collection is this queue, and this queue is nonempty.)
     * <p>
     * This implementation iterates over the specified collection, and adds
     * each object returned by the iterator to this collection, in turn.
     * @throws NullPointerException {@inheritDoc}
     * @throws ClassCastException if any element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     */
    public boolean addAll(Collection<? extends E> c) {
        return super.addAll(c);
    }

    /**
     * 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();
    }

    /**
     * Adds the specified element to this priority queue.
     *
     * @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 {@inheritDoc}
     */
    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.
     * @throws ClassCastException if the element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     * @throws NullPointerException {@inheritDoc}
     */
    public void put(E o) {
        offer(o); // never need to block
    }

    /**
     * Adds the specified element to this priority queue. As the queue is
     * unbounded this method will never block.
     * @param o {@inheritDoc}
     * @param timeout This parameter is ignored as the method never blocks
     * @param unit This parameter is ignored as the method never blocks
     * @throws ClassCastException if the element cannot be compared
     * with elements currently in the priority queue according
     * to the priority queue's ordering.
     * @throws NullPointerException {@inheritDoc}
     * @return <tt>true</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;
    }

    /**
     * Removes a single instance of the specified element from this
     * queue, if it is present.  More formally,
     * removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
     * o.equals(e))</tt>, if the queue contains one or more such
     * elements.  Returns <tt>true</tt> if the queue contained the
     * specified element (or equivalently, if the queue changed as a
     * result of the call).
     *
     * <p>This implementation iterates over the queue looking for the
     * specified element.  If it finds the element, it removes the element
     * from the queue using the iterator's remove method.<p>
     *
     */
    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();
        }
    }

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