CircularFifoQueue.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.collections4.queue;

  18. import java.io.IOException;
  19. import java.io.ObjectInputStream;
  20. import java.io.ObjectOutputStream;
  21. import java.io.Serializable;
  22. import java.util.AbstractCollection;
  23. import java.util.Arrays;
  24. import java.util.Collection;
  25. import java.util.Iterator;
  26. import java.util.NoSuchElementException;
  27. import java.util.Objects;
  28. import java.util.Queue;

  29. import org.apache.commons.collections4.BoundedCollection;

  30. /**
  31.  * CircularFifoQueue is a first-in first-out queue with a fixed size that
  32.  * replaces its oldest element if full.
  33.  * <p>
  34.  * The removal order of a {@link CircularFifoQueue} is based on the
  35.  * insertion order; elements are removed in the same order in which they
  36.  * were added.  The iteration order is the same as the removal order.
  37.  * </p>
  38.  * <p>
  39.  * The {@link #add(Object)}, {@link #remove()}, {@link #peek()}, {@link #poll()},
  40.  * {@link #offer(Object)} operations all perform in constant time.
  41.  * All other operations perform in linear time or worse.
  42.  * </p>
  43.  * <p>
  44.  * This queue prevents null objects from being added.
  45.  * </p>
  46.  *
  47.  * @param <E> the type of elements in this collection
  48.  * @since 4.0
  49.  */
  50. public class CircularFifoQueue<E> extends AbstractCollection<E>
  51.     implements Queue<E>, BoundedCollection<E>, Serializable {

  52.     /** Serialization version. */
  53.     private static final long serialVersionUID = -8423413834657610406L;

  54.     /** Underlying storage array. */
  55.     private transient E[] elements;

  56.     /** Array index of first (oldest) queue element. */
  57.     private transient int start;

  58.     /**
  59.      * Index mod maxElements of the array position following the last queue
  60.      * element.  Queue elements start at elements[start] and "wrap around"
  61.      * elements[maxElements-1], ending at elements[decrement(end)].
  62.      * For example, elements = {c,a,b}, start=1, end=1 corresponds to
  63.      * the queue [a,b,c].
  64.      */
  65.     private transient int end;

  66.     /** Flag to indicate if the queue is currently full. */
  67.     private transient boolean full;

  68.     /** Capacity of the queue. */
  69.     private final int maxElements;

  70.     /**
  71.      * Constructor that creates a queue with the default size of 32.
  72.      */
  73.     public CircularFifoQueue() {
  74.         this(32);
  75.     }

  76.     /**
  77.      * Constructor that creates a queue from the specified collection.
  78.      * The collection size also sets the queue size.
  79.      *
  80.      * @param coll  the collection to copy into the queue, may not be null
  81.      * @throws NullPointerException if the collection is null
  82.      */
  83.     public CircularFifoQueue(final Collection<? extends E> coll) {
  84.         this(coll.size());
  85.         addAll(coll);
  86.     }

  87.     /**
  88.      * Constructor that creates a queue with the specified size.
  89.      *
  90.      * @param size  the size of the queue (cannot be changed)
  91.      * @throws IllegalArgumentException  if the size is &lt; 1
  92.      */
  93.     @SuppressWarnings("unchecked")
  94.     public CircularFifoQueue(final int size) {
  95.         if (size <= 0) {
  96.             throw new IllegalArgumentException("The size must be greater than 0");
  97.         }
  98.         elements = (E[]) new Object[size];
  99.         maxElements = elements.length;
  100.     }

  101.     /**
  102.      * Adds the given element to this queue. If the queue is full, the least recently added
  103.      * element is discarded so that a new element can be inserted.
  104.      *
  105.      * @param element  the element to add
  106.      * @return true, always
  107.      * @throws NullPointerException  if the given element is null
  108.      */
  109.     @Override
  110.     public boolean add(final E element) {
  111.         Objects.requireNonNull(element, "element");

  112.         if (isAtFullCapacity()) {
  113.             remove();
  114.         }

  115.         elements[end++] = element;

  116.         if (end >= maxElements) {
  117.             end = 0;
  118.         }

  119.         if (end == start) {
  120.             full = true;
  121.         }

  122.         return true;
  123.     }

  124.     /**
  125.      * Clears this queue.
  126.      */
  127.     @Override
  128.     public void clear() {
  129.         full = false;
  130.         start = 0;
  131.         end = 0;
  132.         Arrays.fill(elements, null);
  133.     }

  134.     /**
  135.      * Decrements the internal index.
  136.      *
  137.      * @param index  the index to decrement
  138.      * @return the updated index
  139.      */
  140.     private int decrement(int index) {
  141.         index--;
  142.         if (index < 0) {
  143.             index = maxElements - 1;
  144.         }
  145.         return index;
  146.     }

  147.     @Override
  148.     public E element() {
  149.         if (isEmpty()) {
  150.             throw new NoSuchElementException("queue is empty");
  151.         }
  152.         return peek();
  153.     }

  154.     /**
  155.      * Gets the element at the specified position in this queue.
  156.      *
  157.      * @param index the position of the element in the queue
  158.      * @return the element at position {@code index}
  159.      * @throws NoSuchElementException if the requested position is outside the range [0, size)
  160.      */
  161.     public E get(final int index) {
  162.         final int sz = size();
  163.         if (index < 0 || index >= sz) {
  164.             throw new NoSuchElementException(
  165.                     String.format("The specified index %1$d is outside the available range [0, %2$d)",
  166.                                   Integer.valueOf(index), Integer.valueOf(sz)));
  167.         }

  168.         final int idx = (start + index) % maxElements;
  169.         return elements[idx];
  170.     }

  171.     /**
  172.      * Increments the internal index.
  173.      *
  174.      * @param index  the index to increment
  175.      * @return the updated index
  176.      */
  177.     private int increment(int index) {
  178.         index++;
  179.         if (index >= maxElements) {
  180.             index = 0;
  181.         }
  182.         return index;
  183.     }

  184.     /**
  185.      * Returns {@code true} if the capacity limit of this queue has been reached,
  186.      * i.e. the number of elements stored in the queue equals its maximum size.
  187.      *
  188.      * @return {@code true} if the capacity limit has been reached, {@code false} otherwise
  189.      * @since 4.1
  190.      */
  191.     public boolean isAtFullCapacity() {
  192.         return size() == maxElements;
  193.     }

  194.     /**
  195.      * Returns true if this queue is empty; false otherwise.
  196.      *
  197.      * @return true if this queue is empty
  198.      */
  199.     @Override
  200.     public boolean isEmpty() {
  201.         return size() == 0;
  202.     }

  203.     /**
  204.      * {@inheritDoc}
  205.      * <p>
  206.      * A {@code CircularFifoQueue} can never be full, thus this returns always
  207.      * {@code false}.
  208.      *
  209.      * @return always returns {@code false}
  210.      */
  211.     @Override
  212.     public boolean isFull() {
  213.         return false;
  214.     }

  215.     /**
  216.      * Returns an iterator over this queue's elements.
  217.      *
  218.      * @return an iterator over this queue's elements
  219.      */
  220.     @Override
  221.     public Iterator<E> iterator() {
  222.         return new Iterator<E>() {

  223.             private int index = start;
  224.             private int lastReturnedIndex = -1;
  225.             private boolean isFirst = full;

  226.             @Override
  227.             public boolean hasNext() {
  228.                 return isFirst || index != end;
  229.             }

  230.             @Override
  231.             public E next() {
  232.                 if (!hasNext()) {
  233.                     throw new NoSuchElementException();
  234.                 }
  235.                 isFirst = false;
  236.                 lastReturnedIndex = index;
  237.                 index = increment(index);
  238.                 return elements[lastReturnedIndex];
  239.             }

  240.             @Override
  241.             public void remove() {
  242.                 if (lastReturnedIndex == -1) {
  243.                     throw new IllegalStateException();
  244.                 }

  245.                 // First element can be removed quickly
  246.                 if (lastReturnedIndex == start) {
  247.                     CircularFifoQueue.this.remove();
  248.                     lastReturnedIndex = -1;
  249.                     return;
  250.                 }

  251.                 int pos = lastReturnedIndex + 1;
  252.                 if (start < lastReturnedIndex && pos < end) {
  253.                     // shift in one part
  254.                     System.arraycopy(elements, pos, elements, lastReturnedIndex, end - pos);
  255.                 } else {
  256.                     // Other elements require us to shift the subsequent elements
  257.                     while (pos != end) {
  258.                         if (pos >= maxElements) {
  259.                             elements[pos - 1] = elements[0];
  260.                             pos = 0;
  261.                         } else {
  262.                             elements[decrement(pos)] = elements[pos];
  263.                             pos = increment(pos);
  264.                         }
  265.                     }
  266.                 }

  267.                 lastReturnedIndex = -1;
  268.                 end = decrement(end);
  269.                 elements[end] = null;
  270.                 full = false;
  271.                 index = decrement(index);
  272.             }

  273.         };
  274.     }

  275.     /**
  276.      * Gets the maximum size of the collection (the bound).
  277.      *
  278.      * @return the maximum number of elements the collection can hold
  279.      */
  280.     @Override
  281.     public int maxSize() {
  282.         return maxElements;
  283.     }

  284.     /**
  285.      * Adds the given element to this queue. If the queue is full, the least recently added
  286.      * element is discarded so that a new element can be inserted.
  287.      *
  288.      * @param element  the element to add
  289.      * @return true, always
  290.      * @throws NullPointerException  if the given element is null
  291.      */
  292.     @Override
  293.     public boolean offer(final E element) {
  294.         return add(element);
  295.     }

  296.     @Override
  297.     public E peek() {
  298.         if (isEmpty()) {
  299.             return null;
  300.         }
  301.         return elements[start];
  302.     }

  303.     @Override
  304.     public E poll() {
  305.         if (isEmpty()) {
  306.             return null;
  307.         }
  308.         return remove();
  309.     }

  310.     /**
  311.      * Deserializes the queue in using a custom routine.
  312.      *
  313.      * @param in  the input stream
  314.      * @throws IOException if an I/O error occurs while writing to the output stream
  315.      * @throws ClassNotFoundException if the class of a serialized object cannot be found
  316.      */
  317.     @SuppressWarnings("unchecked")
  318.     private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
  319.         in.defaultReadObject();
  320.         elements = (E[]) new Object[maxElements];
  321.         final int size = in.readInt();
  322.         for (int i = 0; i < size; i++) {
  323.             elements[i] = (E) in.readObject();
  324.         }
  325.         start = 0;
  326.         full = size == maxElements;
  327.         if (full) {
  328.             end = 0;
  329.         } else {
  330.             end = size;
  331.         }
  332.     }

  333.     @Override
  334.     public E remove() {
  335.         if (isEmpty()) {
  336.             throw new NoSuchElementException("queue is empty");
  337.         }

  338.         final E element = elements[start];
  339.         if (null != element) {
  340.             elements[start++] = null;

  341.             if (start >= maxElements) {
  342.                 start = 0;
  343.             }
  344.             full = false;
  345.         }
  346.         return element;
  347.     }

  348.     /**
  349.      * Returns the number of elements stored in the queue.
  350.      *
  351.      * @return this queue's size
  352.      */
  353.     @Override
  354.     public int size() {
  355.         int size = 0;

  356.         if (end < start) {
  357.             size = maxElements - start + end;
  358.         } else if (end == start) {
  359.             size = full ? maxElements : 0;
  360.         } else {
  361.             size = end - start;
  362.         }

  363.         return size;
  364.     }

  365.     /**
  366.      * Serializes this object to an ObjectOutputStream.
  367.      *
  368.      * @param out the target ObjectOutputStream.
  369.      * @throws IOException thrown when an I/O errors occur writing to the target stream.
  370.      */
  371.     private void writeObject(final ObjectOutputStream out) throws IOException {
  372.         out.defaultWriteObject();
  373.         out.writeInt(size());
  374.         for (final E e : this) {
  375.             out.writeObject(e);
  376.         }
  377.     }

  378. }