user/super/com/google/gwt/emul/java/util/ArrayDeque.java

/*
 * Copyright 2016 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package java.util;

import static javaemul.internal.InternalPreconditions.checkCriticalElement;
import static javaemul.internal.InternalPreconditions.checkCriticalNotNull;
import static javaemul.internal.InternalPreconditions.checkElement;
import static javaemul.internal.InternalPreconditions.checkState;

import javaemul.internal.ArrayHelper;

/**
 * A {@link Deque} based on circular buffer that is implemented with an array and head/tail
 * pointers. Array deques have no capacity restrictions; they grow as necessary to support usage.
 * Null elements are prohibited. This class is likely to be faster than {@link Stack}
 * when used as a stack, and faster than {@link LinkedList} when used as a queue.
 * <a href="https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html">ArrayDeque</a>
 *
 * @param <E> the element type.
 */
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable {

  private final class IteratorImpl implements Iterator<E> {
    /**
     * Index of element to be returned by subsequent call to next.
     */
    private int currentIndex = head;

    /**
     * Tail recorded at construction (also in remove), to stop
     * iterator and also to check for comodification.
     */
    private int fence = tail;

    /**
     * Index of element returned by most recent call to next.
     * Reset to -1 if element is deleted by a call to remove.
     */
    private int lastIndex = -1;

    @Override
    public boolean hasNext() {
      return currentIndex != fence;
    }

    @Override
    public E next() {
      checkCriticalElement(hasNext());

      E e = array[currentIndex];
      // OpenJDK ArrayDeque doesn't catch all possible comodifications,
      // but does catch the ones that corrupt traversal
      checkConcurrentModification(fence == tail && e != null);
      lastIndex = currentIndex;
      currentIndex = (currentIndex + 1) & (array.length - 1);
      return e;
    }

    @Override
    public void remove() {
      checkState(lastIndex >= 0);

      if (removeAtIndex(lastIndex) < 0) {
        // if left-shifted, undo increment in next()
        currentIndex = (currentIndex - 1) & (array.length - 1);
        fence = tail;
      }
      lastIndex = -1;
    }
  }

  private final class DescendingIteratorImpl implements Iterator<E> {
    private int currentIndex = tail;
    private int fence = head;
    private int lastIndex = -1;

    @Override
    public boolean hasNext() {
      return currentIndex != fence;
    }

    @Override
    public E next() {
      checkCriticalElement(hasNext());

      currentIndex = (currentIndex - 1) & (array.length - 1);
      E e = array[currentIndex];
      checkConcurrentModification(fence == head && e != null);
      lastIndex = currentIndex;
      return e;
    }

    @Override
    public void remove() {
      checkState(lastIndex >= 0);

      if (removeAtIndex(lastIndex) > 0) {
        // if right-shifted, undo decrement in next()
        currentIndex = (currentIndex + 1) & (array.length - 1);
        fence = head;
      }
      lastIndex = -1;
    }
  }

  /**
   * The minimum capacity that we'll use for a newly created deque.
   * Must be a power of 2.
   */
  private static final int MIN_INITIAL_CAPACITY = 8;

  private static void checkConcurrentModification(boolean expression) {
    if (!expression) {
      throw new ConcurrentModificationException();
    }
  }

  /**
   * Returns best power-of-two array length to hold the given number of elements.
   *
   * @param numElements the number of elements to hold
   */
  @SuppressWarnings("unchecked")
  private static int nextArrayLength(int numElements) {
    return nextPowerOfTwo(Math.max(MIN_INITIAL_CAPACITY, numElements));
  }

  /**
   * Returns a number that is greater than {@code num} and is a power of two.
   * If passed {@code num} is not positive integer or next power of two overflows then
   * returned value is non-positive.
   * E.g., if num == 32, returns 64. if num == 31, returns 32.
   *
   * @param num positive integer.
   */
  private static int nextPowerOfTwo(int num) {
    return Integer.highestOneBit(num) << 1;
  }

  private E[] array;

  /**
   * The index of the element at the head of the deque (which is the
   * element that would be removed by remove() or pop()); or an
   * arbitrary number equal to tail if the deque is empty.
   */
  private int head;

  /**
   * The index at which the next element would be added to the tail
   * of the deque (via addLast(E), add(E), or push(E)).
   */
  private int tail;

  public ArrayDeque() {
    this.array = (E[]) new Object[MIN_INITIAL_CAPACITY];
  }

  public ArrayDeque(int numElements) {
    this.array = (E[]) new Object[nextArrayLength(numElements)];
  }

  public ArrayDeque(Collection<? extends E> c) {
    this(c.size());
    addAll(c);
  }

  @Override
  public boolean add(E e) {
    addLast(e);
    return true;
  }

  @Override
  public void addFirst(E e) {
    checkCriticalNotNull(e);

    head = (head - 1) & (array.length - 1);
    array[head] = e;
    ensureCapacity();
  }

  @Override
  public void addLast(E e) {
    checkCriticalNotNull(e);

    array[tail] = e;
    tail = (tail + 1) & (array.length - 1);
    ensureCapacity();
  }

  @SuppressWarnings("unchecked")
  @Override
  public void clear() {
    if (head == tail) {
      return;
    }

    array = (E[]) new Object[MIN_INITIAL_CAPACITY];
    head = 0;
    tail = 0;
  }

  public Object clone() {
    return new ArrayDeque<>(this);
  }

  @Override
  public boolean contains(Object o) {
    return contains(iterator(), o);
  }

  @Override
  public Iterator<E> descendingIterator() {
    return new DescendingIteratorImpl();
  }

  @Override
  public E element() {
    return getFirst();
  }

  @Override
  public E getFirst() {
    E e = peekFirstElement();
    checkElement(e != null);
    return e;
  }

  @Override
  public E getLast() {
    E e = peekLastElement();
    checkElement(e != null);
    return e;
  }

  @Override
  public boolean isEmpty() {
    return head == tail;
  }

  @Override
  public Iterator<E> iterator() {
    return new IteratorImpl();
  }

  @Override
  public boolean offer(E e) {
    return offerLast(e);
  }

  @Override
  public boolean offerFirst(E e) {
    addFirst(e);
    return true;
  }

  @Override
  public boolean offerLast(E e) {
    addLast(e);
    return true;
  }

  @Override
  public E peek() {
    return peekFirst();
  }

  @Override
  public E peekFirst() {
    return peekFirstElement();
  }

  @Override
  public E peekLast() {
    return peekLastElement();
  }

  @Override
  public E poll() {
    return pollFirst();
  }

  @Override
  public E pollFirst() {
    E e = peekFirstElement();
    if (e == null) {
      return null;
    }
    array[head] = null;
    head = (head + 1) & (array.length - 1);
    return e;
  }

  @Override
  public E pollLast() {
    E e = peekLastElement();
    if (e == null) {
      return null;
    }
    tail = (tail - 1) & (array.length - 1);
    array[tail] = null;
    return e;
  }

  @Override
  public E pop() {
    return removeFirst();
  }

  @Override
  public void push(E e) {
    addFirst(e);
  }

  @Override
  public E remove() {
    return removeFirst();
  }

  @Override
  public boolean remove(Object o) {
    return removeFirstOccurrence(o);
  }

  @Override
  public E removeFirst() {
    E e = pollFirst();
    checkElement(e != null);
    return e;
  }

  @Override
  public boolean removeFirstOccurrence(Object o) {
    return remove(iterator(), o);
  }

  @Override
  public E removeLast() {
    E e = pollLast();
    checkElement(e != null);
    return e;
  }

  @Override
  public boolean removeLastOccurrence(Object o) {
    return remove(descendingIterator(), o);
  }

  @Override
  public int size() {
    return (tail - head) & (array.length - 1);
  }

  @Override
  public Spliterator<E> spliterator() {
    return Spliterators.spliterator(this, Spliterator.NONNULL | Spliterator.ORDERED);
  }

  @SuppressWarnings("unchecked")
  @Override
  public <T> T[] toArray(T[] out) {
    int size = size();
    if (out.length < size) {
      out = ArrayHelper.createFrom(out, size);
    }
    copyElements(out, size);
    if (out.length > size) {
      out[size] = null;
    }
    return out;
  }

  private boolean contains(Iterator<E> it, Object o) {
    if (o == null) {
      return false;
    }

    while (it.hasNext()) {
      if (o.equals(it.next())) {
        return true;
      }
    }
    return false;
  }

  private boolean remove(Iterator<E> it, Object o) {
    if (contains(it, o)) {
      it.remove();
      return true;
    }
    return false;
  }

  private E peekFirstElement() {
    return array[head];
  }

  private E peekLastElement() {
    return array[(tail - 1) & (array.length - 1)];
  }

  /**
   * Copies {@code count} ArrayDeque's elements to {@code dest} array.
   * The method is safe to use when ArrayDeque's array has been rolled over,
   * i.e. {@code head == tail}.
   * It is assumed that {@code count < size()}.
   */
  private void copyElements(Object[] dest, int count) {
    final int mask = array.length - 1;
    for (int i = head, dstIdx = 0; dstIdx < count; i = (i + 1) & mask, ++dstIdx) {
      dest[dstIdx] = array[i];
    }
  }

  /**
   * Increase the capacity of this deque when full, i.e.,
   * when head and tail have wrapped around to become equal.
   */
  private void ensureCapacity() {
    if (head != tail) {
      return;
    }

    int numElements = array.length;
    int newLength = nextArrayLength(numElements);
    if (head != 0) {
      E[] newArray = ArrayHelper.createFrom(array, newLength);
      copyElements(newArray, numElements);
      array = newArray;
      head = 0;
    } else {
      ArrayHelper.setLength(array, newLength);
    }
    tail = numElements;
  }

  /**
   * Removes the element at the specified position in the elements array,
   * adjusting head and tail as necessary. This results in motion of
   * elements backwards or forwards in the array.
   *
   * @return -1 if elements moved backwards (left-shifted); 1 if forwards (right-shifted).
   */
  private int removeAtIndex(int i) {
    final int mask = array.length - 1;
    int headDistance = (i - head) & mask;
    int tailDistance = (tail - i) & mask;
    int size = (tail - head) & mask;

    checkConcurrentModification(headDistance < size);
    if (headDistance >= tailDistance) {
      shiftLeftAtIndex(i);
      return -1;
    } else {
      shiftRightAtIndex(i);
      return 1;
    }
  }

  private void shiftLeftAtIndex(int i) {
    final int mask = array.length - 1;
    tail = (tail - 1) & mask;
    while (i != tail) {
      int nextOffset = (i + 1) & mask;
      array[i] = array[nextOffset];
      i = nextOffset;
    }
    array[tail] = null;
  }

  private void shiftRightAtIndex(int i) {
    final int mask = array.length - 1;
    while (i != head) {
      int prevOffset = (i - 1) & mask;
      array[i] = array[prevOffset];
      i = prevOffset;
    }
    array[head] = null;
    head = (head + 1) & mask;
  }
}