001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.collections4.queue;
018
019import java.io.IOException;
020import java.io.ObjectInputStream;
021import java.io.ObjectOutputStream;
022import java.io.Serializable;
023import java.util.AbstractCollection;
024import java.util.Arrays;
025import java.util.Collection;
026import java.util.Iterator;
027import java.util.NoSuchElementException;
028import java.util.Queue;
029
030import org.apache.commons.collections4.BoundedCollection;
031
032/**
033 * CircularFifoQueue is a first-in first-out queue with a fixed size that
034 * replaces its oldest element if full.
035 * <p>
036 * The removal order of a {@link CircularFifoQueue} is based on the
037 * insertion order; elements are removed in the same order in which they
038 * were added.  The iteration order is the same as the removal order.
039 * <p>
040 * The {@link #add(Object)}, {@link #remove()}, {@link #peek()}, {@link #poll},
041 * {@link #offer(Object)} operations all perform in constant time.
042 * All other operations perform in linear time or worse.
043 * <p>
044 * This queue prevents null objects from being added.
045 *
046 * @since 4.0
047 * @version $Id: CircularFifoQueue.html 972397 2015-11-14 15:01:49Z tn $
048 */
049public class CircularFifoQueue<E> extends AbstractCollection<E>
050    implements Queue<E>, BoundedCollection<E>, Serializable {
051
052    /** Serialization version. */
053    private static final long serialVersionUID = -8423413834657610406L;
054
055    /** Underlying storage array. */
056    private transient E[] elements;
057
058    /** Array index of first (oldest) queue element. */
059    private transient int start = 0;
060
061    /**
062     * Index mod maxElements of the array position following the last queue
063     * element.  Queue elements start at elements[start] and "wrap around"
064     * elements[maxElements-1], ending at elements[decrement(end)].
065     * For example, elements = {c,a,b}, start=1, end=1 corresponds to
066     * the queue [a,b,c].
067     */
068    private transient int end = 0;
069
070    /** Flag to indicate if the queue is currently full. */
071    private transient boolean full = false;
072
073    /** Capacity of the queue. */
074    private final int maxElements;
075
076    /**
077     * Constructor that creates a queue with the default size of 32.
078     */
079    public CircularFifoQueue() {
080        this(32);
081    }
082
083    /**
084     * Constructor that creates a queue with the specified size.
085     *
086     * @param size  the size of the queue (cannot be changed)
087     * @throws IllegalArgumentException  if the size is &lt; 1
088     */
089    @SuppressWarnings("unchecked")
090    public CircularFifoQueue(final int size) {
091        if (size <= 0) {
092            throw new IllegalArgumentException("The size must be greater than 0");
093        }
094        elements = (E[]) new Object[size];
095        maxElements = elements.length;
096    }
097
098    /**
099     * Constructor that creates a queue from the specified collection.
100     * The collection size also sets the queue size.
101     *
102     * @param coll  the collection to copy into the queue, may not be null
103     * @throws NullPointerException if the collection is null
104     */
105    public CircularFifoQueue(final Collection<? extends E> coll) {
106        this(coll.size());
107        addAll(coll);
108    }
109
110    //-----------------------------------------------------------------------
111    /**
112     * Write the queue out using a custom routine.
113     *
114     * @param out  the output stream
115     * @throws IOException if an I/O error occurs while writing to the output stream
116     */
117    private void writeObject(final ObjectOutputStream out) throws IOException {
118        out.defaultWriteObject();
119        out.writeInt(size());
120        for (final E e : this) {
121            out.writeObject(e);
122        }
123    }
124
125    /**
126     * Read the queue in using a custom routine.
127     *
128     * @param in  the input stream
129     * @throws IOException if an I/O error occurs while writing to the output stream
130     * @throws ClassNotFoundException if the class of a serialized object can not be found
131     */
132    @SuppressWarnings("unchecked")
133    private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
134        in.defaultReadObject();
135        elements = (E[]) new Object[maxElements];
136        final int size = in.readInt();
137        for (int i = 0; i < size; i++) {
138            elements[i] = (E) in.readObject();
139        }
140        start = 0;
141        full = size == maxElements;
142        if (full) {
143            end = 0;
144        } else {
145            end = size;
146        }
147    }
148
149    //-----------------------------------------------------------------------
150    /**
151     * Returns the number of elements stored in the queue.
152     *
153     * @return this queue's size
154     */
155    @Override
156    public int size() {
157        int size = 0;
158
159        if (end < start) {
160            size = maxElements - start + end;
161        } else if (end == start) {
162            size = full ? maxElements : 0;
163        } else {
164            size = end - start;
165        }
166
167        return size;
168    }
169
170    /**
171     * Returns true if this queue is empty; false otherwise.
172     *
173     * @return true if this queue is empty
174     */
175    @Override
176    public boolean isEmpty() {
177        return size() == 0;
178    }
179
180    /**
181     * {@inheritDoc}
182     * <p>
183     * A {@code CircularFifoQueue} can never be full, thus this returns always
184     * {@code false}.
185     *
186     * @return always returns {@code false}
187     */
188    public boolean isFull() {
189        return false;
190    }
191
192    /**
193     * Returns {@code true} if the capacity limit of this queue has been reached,
194     * i.e. the number of elements stored in the queue equals its maximum size.
195     *
196     * @return {@code true} if the capacity limit has been reached, {@code false} otherwise
197     * @since 4.1
198     */
199    public boolean isAtFullCapacity() {
200        return size() == maxElements;
201    }
202
203    /**
204     * Gets the maximum size of the collection (the bound).
205     *
206     * @return the maximum number of elements the collection can hold
207     */
208    public int maxSize() {
209        return maxElements;
210    }
211
212    /**
213     * Clears this queue.
214     */
215    @Override
216    public void clear() {
217        full = false;
218        start = 0;
219        end = 0;
220        Arrays.fill(elements, null);
221    }
222
223    /**
224     * Adds the given element to this queue. If the queue is full, the least recently added
225     * element is discarded so that a new element can be inserted.
226     *
227     * @param element  the element to add
228     * @return true, always
229     * @throws NullPointerException  if the given element is null
230     */
231    @Override
232    public boolean add(final E element) {
233        if (null == element) {
234            throw new NullPointerException("Attempted to add null object to queue");
235        }
236
237        if (isAtFullCapacity()) {
238            remove();
239        }
240
241        elements[end++] = element;
242
243        if (end >= maxElements) {
244            end = 0;
245        }
246
247        if (end == start) {
248            full = true;
249        }
250
251        return true;
252    }
253
254    /**
255     * Returns the element at the specified position in this queue.
256     *
257     * @param index the position of the element in the queue
258     * @return the element at position {@code index}
259     * @throws NoSuchElementException if the requested position is outside the range [0, size)
260     */
261    public E get(final int index) {
262        final int sz = size();
263        if (index < 0 || index >= sz) {
264            throw new NoSuchElementException(
265                    String.format("The specified index (%1$d) is outside the available range [0, %2$d)",
266                                  Integer.valueOf(index), Integer.valueOf(sz)));
267        }
268
269        final int idx = (start + index) % maxElements;
270        return elements[idx];
271    }
272
273    //-----------------------------------------------------------------------
274
275    /**
276     * Adds the given element to this queue. If the queue is full, the least recently added
277     * element is discarded so that a new element can be inserted.
278     *
279     * @param element  the element to add
280     * @return true, always
281     * @throws NullPointerException  if the given element is null
282     */
283    public boolean offer(E element) {
284        return add(element);
285    }
286
287    public E poll() {
288        if (isEmpty()) {
289            return null;
290        }
291        return remove();
292    }
293
294    public E element() {
295        if (isEmpty()) {
296            throw new NoSuchElementException("queue is empty");
297        }
298        return peek();
299    }
300
301    public E peek() {
302        if (isEmpty()) {
303            return null;
304        }
305        return elements[start];
306    }
307
308    public E remove() {
309        if (isEmpty()) {
310            throw new NoSuchElementException("queue is empty");
311        }
312
313        final E element = elements[start];
314        if (null != element) {
315            elements[start++] = null;
316
317            if (start >= maxElements) {
318                start = 0;
319            }
320            full = false;
321        }
322        return element;
323    }
324
325    //-----------------------------------------------------------------------
326    /**
327     * Increments the internal index.
328     *
329     * @param index  the index to increment
330     * @return the updated index
331     */
332    private int increment(int index) {
333        index++;
334        if (index >= maxElements) {
335            index = 0;
336        }
337        return index;
338    }
339
340    /**
341     * Decrements the internal index.
342     *
343     * @param index  the index to decrement
344     * @return the updated index
345     */
346    private int decrement(int index) {
347        index--;
348        if (index < 0) {
349            index = maxElements - 1;
350        }
351        return index;
352    }
353
354    /**
355     * Returns an iterator over this queue's elements.
356     *
357     * @return an iterator over this queue's elements
358     */
359    @Override
360    public Iterator<E> iterator() {
361        return new Iterator<E>() {
362
363            private int index = start;
364            private int lastReturnedIndex = -1;
365            private boolean isFirst = full;
366
367            public boolean hasNext() {
368                return isFirst || index != end;
369            }
370
371            public E next() {
372                if (!hasNext()) {
373                    throw new NoSuchElementException();
374                }
375                isFirst = false;
376                lastReturnedIndex = index;
377                index = increment(index);
378                return elements[lastReturnedIndex];
379            }
380
381            public void remove() {
382                if (lastReturnedIndex == -1) {
383                    throw new IllegalStateException();
384                }
385
386                // First element can be removed quickly
387                if (lastReturnedIndex == start) {
388                    CircularFifoQueue.this.remove();
389                    lastReturnedIndex = -1;
390                    return;
391                }
392
393                int pos = lastReturnedIndex + 1;
394                if (start < lastReturnedIndex && pos < end) {
395                    // shift in one part
396                    System.arraycopy(elements, pos, elements, lastReturnedIndex, end - pos);
397                } else {
398                    // Other elements require us to shift the subsequent elements
399                    while (pos != end) {
400                        if (pos >= maxElements) {
401                            elements[pos - 1] = elements[0];
402                            pos = 0;
403                        } else {
404                            elements[decrement(pos)] = elements[pos];
405                            pos = increment(pos);
406                        }
407                    }
408                }
409
410                lastReturnedIndex = -1;
411                end = decrement(end);
412                elements[end] = null;
413                full = false;
414                index = decrement(index);
415            }
416
417        };
418    }
419
420}