001/**
002 * Copyright (c) 2011, The University of Southampton and the individual contributors.
003 * All rights reserved.
004 *
005 * Redistribution and use in source and binary forms, with or without modification,
006 * are permitted provided that the following conditions are met:
007 *
008 *   *  Redistributions of source code must retain the above copyright notice,
009 *      this list of conditions and the following disclaimer.
010 *
011 *   *  Redistributions in binary form must reproduce the above copyright notice,
012 *      this list of conditions and the following disclaimer in the documentation
013 *      and/or other materials provided with the distribution.
014 *
015 *   *  Neither the name of the University of Southampton nor the names of its
016 *      contributors may be used to endorse or promote products derived from this
017 *      software without specific prior written permission.
018 *
019 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
020 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
021 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
022 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
023 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
024 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
025 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
026 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
027 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
028 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
029 */
030package org.openimaj.util.concurrent;
031
032import java.util.Collection;
033import java.util.Queue;
034import java.util.concurrent.TimeUnit;
035
036/**
037 * A {@link Queue} that additionally supports operations that wait for the queue
038 * to become non-empty when retrieving an element, and drop the oldest element
039 * from the queue when storing a new element if space is not available for the
040 * new element.
041 * 
042 * <p>
043 * <tt>BlockingDroppingQueue</tt> methods come in four forms, with different
044 * ways of handling operations that cannot be satisfied immediately, but may be
045 * satisfied at some point in the future: one throws an exception, the second
046 * returns a special value (either <tt>null</tt>, <tt>false</tt> or the dropped
047 * object, depending on the operation), the third blocks the current thread
048 * indefinitely until the operation can succeed, and the fourth blocks for only
049 * a given maximum time limit before giving up. These methods are summarized in
050 * the following table:
051 * 
052 * <p>
053 * <table BORDER CELLPADDING=3 CELLSPACING=1>
054 * <tr>
055 * <td></td>
056 * <td ALIGN=CENTER><em>Throws exception</em></td>
057 * <td ALIGN=CENTER><em>Special value</em></td>
058 * <td ALIGN=CENTER><em>Blocks</em></td>
059 * <td ALIGN=CENTER><em>Times out</em></td>
060 * </tr>
061 * <tr>
062 * <td><b>Insert</b></td>
063 * <td>{@link #add add(e)}</td>
064 * <td>{@link #offer offer(e)}, {@link #put put(e)}</td>
065 * <td><em>not applicable</em></td>
066 * <td><em>not applicable</em></td>
067 * </tr>
068 * <tr>
069 * <td><b>Remove</b></td>
070 * <td>{@link #remove remove()}</td>
071 * <td>{@link #poll poll()}</td>
072 * <td>{@link #take take()}</td>
073 * <td>{@link #poll(long, TimeUnit) poll(time, unit)}</td>
074 * </tr>
075 * <tr>
076 * <td><b>Examine</b></td>
077 * <td>{@link #element element()}</td>
078 * <td>{@link #peek peek()}</td>
079 * <td><em>not applicable</em></td>
080 * <td><em>not applicable</em></td>
081 * </tr>
082 * </table>
083 * 
084 * <p>
085 * <tt>BlockingDroppingQueue</tt>s keep track of statistics on the number of
086 * items that have been added to the queue and the number of items that have
087 * been dropped from the queue.
088 * 
089 * <p>
090 * A <tt>BlockingDroppingQueue</tt> does not accept <tt>null</tt> elements.
091 * Implementations throw <tt>NullPointerException</tt> on attempts to
092 * <tt>add</tt>, <tt>put</tt> or <tt>offer</tt> a <tt>null</tt>. A <tt>null</tt>
093 * is used as a sentinel value to indicate failure of <tt>poll</tt> operations.
094 * 
095 * <p>
096 * A <tt>BlockingDroppingQueue</tt> may be capacity bounded. At any given time
097 * it may have a <tt>remainingCapacity</tt> beyond which no additional elements
098 * can be <tt>put</tt> without blocking. A <tt>BlockingDroppingQueue</tt>
099 * without any intrinsic capacity constraints always reports a remaining
100 * capacity of <tt>Integer.MAX_VALUE</tt>.
101 * 
102 * <p>
103 * <tt>BlockingDroppingQueue</tt> implementations are designed to be used
104 * primarily for producer-consumer queues, but additionally support the
105 * {@link java.util.Collection} interface. So, for example, it is possible to
106 * remove an arbitrary element from a queue using <tt>remove(x)</tt>. However,
107 * such operations are in general <em>not</em> performed very efficiently, and
108 * are intended for only occasional use, such as when a queued message is
109 * cancelled.
110 * 
111 * <p>
112 * <tt>BlockingDroppingQueue</tt> implementations are thread-safe. All queuing
113 * methods achieve their effects atomically using internal locks or other forms
114 * of concurrency control. However, the <em>bulk</em> Collection operations
115 * <tt>addAll</tt>, <tt>containsAll</tt>, <tt>retainAll</tt> and
116 * <tt>removeAll</tt> are <em>not</em> necessarily performed atomically unless
117 * specified otherwise in an implementation. So it is possible, for example, for
118 * <tt>addAll(c)</tt> to fail (throwing an exception) after adding only some of
119 * the elements in <tt>c</tt>.
120 * 
121 * <p>
122 * A <tt>BlockingDroppingQueue</tt> does <em>not</em> intrinsically support any
123 * kind of &quot;close&quot; or &quot;shutdown&quot; operation to indicate that
124 * no more items will be added. The needs and usage of such features tend to be
125 * implementation-dependent. For example, a common tactic is for producers to
126 * insert special <em>end-of-stream</em> or <em>poison</em> objects, that are
127 * interpreted accordingly when taken by consumers.
128 * 
129 * <p>
130 * Memory consistency effects: As with other concurrent collections, actions in
131 * a thread prior to placing an object into a {@code BlockingDroppingQueue} <a
132 * href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> actions
133 * subsequent to the access or removal of that element from the
134 * {@code BlockingDroppingQueue} in another thread.
135 * 
136 * @author Jonathon Hare (jsh2@ecs.soton.ac.uk)
137 * 
138 * @param <E>
139 *            the type of elements held in this collection
140 */
141public interface BlockingDroppingQueue<E> extends Queue<E> {
142        /**
143         * Inserts the specified element into this queue if it is possible to do so
144         * immediately without violating capacity restrictions, returning
145         * <tt>true</tt> upon success and throwing an <tt>IllegalStateException</tt>
146         * if no space is currently available. When using a capacity-restricted
147         * queue, it is generally preferable to use {@link #offer(Object) offer}.
148         * 
149         * @param e
150         *            the element to add
151         * @return <tt>true</tt> (as specified by {@link Collection#add})
152         * @throws IllegalStateException
153         *             if the element cannot be added at this time due to capacity
154         *             restrictions
155         * @throws ClassCastException
156         *             if the class of the specified element prevents it from being
157         *             added to this queue
158         * @throws NullPointerException
159         *             if the specified element is null
160         * @throws IllegalArgumentException
161         *             if some property of the specified element prevents it from
162         *             being added to this queue
163         */
164        @Override
165        boolean add(E e);
166
167        /**
168         * Inserts the specified element into this queue if it is possible to do so
169         * immediately without violating capacity restrictions, returning
170         * <tt>true</tt> upon success and <tt>false</tt> if no space is currently
171         * available. When using a capacity-restricted queue, this method is
172         * generally preferable to {@link #add}, which can fail to insert an element
173         * only by throwing an exception.
174         * 
175         * @param e
176         *            the element to add
177         * @return <tt>true</tt> if the element was added to this queue, else
178         *         <tt>false</tt>
179         * @throws ClassCastException
180         *             if the class of the specified element prevents it from being
181         *             added to this queue
182         * @throws NullPointerException
183         *             if the specified element is null
184         * @throws IllegalArgumentException
185         *             if some property of the specified element prevents it from
186         *             being added to this queue
187         */
188        @Override
189        boolean offer(E e);
190
191        /**
192         * Inserts the specified element into this queue, dropping the oldest
193         * element to make space if necessary.
194         * 
195         * @param e
196         *            the element to add
197         * @return the element that was dropped to make space, or null if no element
198         *         was dropped
199         * @throws InterruptedException
200         *             if interrupted while waiting
201         * @throws ClassCastException
202         *             if the class of the specified element prevents it from being
203         *             added to this queue
204         * @throws NullPointerException
205         *             if the specified element is null
206         * @throws IllegalArgumentException
207         *             if some property of the specified element prevents it from
208         *             being added to this queue
209         */
210        E put(E e) throws InterruptedException;
211
212        /**
213         * Retrieves and removes the head of this queue, waiting if necessary until
214         * an element becomes available.
215         * 
216         * @return the head of this queue
217         * @throws InterruptedException
218         *             if interrupted while waiting
219         */
220        E take() throws InterruptedException;
221
222        /**
223         * Retrieves and removes the head of this queue, waiting up to the specified
224         * wait time if necessary for an element to become available.
225         * 
226         * @param timeout
227         *            how long to wait before giving up, in units of <tt>unit</tt>
228         * @param unit
229         *            a <tt>TimeUnit</tt> determining how to interpret the
230         *            <tt>timeout</tt> parameter
231         * @return the head of this queue, or <tt>null</tt> if the specified waiting
232         *         time elapses before an element is available
233         * @throws InterruptedException
234         *             if interrupted while waiting
235         */
236        E poll(long timeout, TimeUnit unit)
237                        throws InterruptedException;
238
239        /**
240         * Returns the number of additional elements that this queue can ideally (in
241         * the absence of memory or resource constraints) accept without blocking,
242         * or <tt>Integer.MAX_VALUE</tt> if there is no intrinsic limit.
243         * 
244         * <p>
245         * Note that you <em>cannot</em> always tell if an attempt to insert an
246         * element will succeed by inspecting <tt>remainingCapacity</tt> because it
247         * may be the case that another thread is about to insert or remove an
248         * element.
249         * 
250         * @return the remaining capacity
251         */
252        int remainingCapacity();
253
254        /**
255         * Removes a single instance of the specified element from this queue, if it
256         * is present. More formally, removes an element <tt>e</tt> such that
257         * <tt>o.equals(e)</tt>, if this queue contains one or more such elements.
258         * Returns <tt>true</tt> if this queue contained the specified element (or
259         * equivalently, if this queue changed as a result of the call).
260         * 
261         * @param o
262         *            element to be removed from this queue, if present
263         * @return <tt>true</tt> if this queue changed as a result of the call
264         * @throws ClassCastException
265         *             if the class of the specified element is incompatible with
266         *             this queue (optional)
267         * @throws NullPointerException
268         *             if the specified element is null (optional)
269         */
270        @Override
271        boolean remove(Object o);
272
273        /**
274         * Returns <tt>true</tt> if this queue contains the specified element. More
275         * formally, returns <tt>true</tt> if and only if this queue contains at
276         * least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
277         * 
278         * @param o
279         *            object to be checked for containment in this queue
280         * @return <tt>true</tt> if this queue contains the specified element
281         * @throws ClassCastException
282         *             if the class of the specified element is incompatible with
283         *             this queue (optional)
284         * @throws NullPointerException
285         *             if the specified element is null (optional)
286         */
287        @Override
288        public boolean contains(Object o);
289
290        /**
291         * Removes all available elements from this queue and adds them to the given
292         * collection. This operation may be more efficient than repeatedly polling
293         * this queue. A failure encountered while attempting to add elements to
294         * collection <tt>c</tt> may result in elements being in neither, either or
295         * both collections when the associated exception is thrown. Attempts to
296         * drain a queue to itself result in <tt>IllegalArgumentException</tt>.
297         * Further, the behavior of this operation is undefined if the specified
298         * collection is modified while the operation is in progress.
299         * 
300         * @param c
301         *            the collection to transfer elements into
302         * @return the number of elements transferred
303         * @throws UnsupportedOperationException
304         *             if addition of elements is not supported by the specified
305         *             collection
306         * @throws ClassCastException
307         *             if the class of an element of this queue prevents it from
308         *             being added to the specified collection
309         * @throws NullPointerException
310         *             if the specified collection is null
311         * @throws IllegalArgumentException
312         *             if the specified collection is this queue, or some property
313         *             of an element of this queue prevents it from being added to
314         *             the specified collection
315         */
316        int drainTo(Collection<? super E> c);
317
318        /**
319         * Removes at most the given number of available elements from this queue
320         * and adds them to the given collection. A failure encountered while
321         * attempting to add elements to collection <tt>c</tt> may result in
322         * elements being in neither, either or both collections when the associated
323         * exception is thrown. Attempts to drain a queue to itself result in
324         * <tt>IllegalArgumentException</tt>. Further, the behavior of this
325         * operation is undefined if the specified collection is modified while the
326         * operation is in progress.
327         * 
328         * @param c
329         *            the collection to transfer elements into
330         * @param maxElements
331         *            the maximum number of elements to transfer
332         * @return the number of elements transferred
333         * @throws UnsupportedOperationException
334         *             if addition of elements is not supported by the specified
335         *             collection
336         * @throws ClassCastException
337         *             if the class of an element of this queue prevents it from
338         *             being added to the specified collection
339         * @throws NullPointerException
340         *             if the specified collection is null
341         * @throws IllegalArgumentException
342         *             if the specified collection is this queue, or some property
343         *             of an element of this queue prevents it from being added to
344         *             the specified collection
345         */
346        int drainTo(Collection<? super E> c, int maxElements);
347
348        /**
349         * Returns the total number of items that have been inserted into this
350         * {@link BlockingDroppingQueue} within its lifetime.
351         * 
352         * @return the total number of items that have been inserted to the queue
353         */
354        long insertCount();
355
356        /**
357         * Returns the total number of items that have been dropped by this
358         * {@link BlockingDroppingQueue} to make space for new elements within its
359         * lifetime.
360         * 
361         * @return the total number of items that have been dropped from the queue
362         */
363        long dropCount();
364}