IntArrayQueue.java

/*
 * Copyright (C) 2019 The Android Open Source Project
 *
 * 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 androidx.media3.exoplayer.mediacodec;

import androidx.media3.common.util.UnstableApi;
import java.util.NoSuchElementException;

/**
 * Array-based unbounded queue for int primitives with amortized O(1) add and remove.
 *
 * <p>Use this class instead of a {@link java.util.Deque} to avoid boxing int primitives to {@link
 * Integer} instances.
 */
@UnstableApi
/* package */ final class IntArrayQueue {

  /** Default capacity needs to be a power of 2. */
  private static final int DEFAULT_INITIAL_CAPACITY = 16;

  private int headIndex;
  private int tailIndex;
  private int size;
  private int[] data;
  private int wrapAroundMask;

  public IntArrayQueue() {
    headIndex = 0;
    tailIndex = -1;
    size = 0;
    data = new int[DEFAULT_INITIAL_CAPACITY];
    wrapAroundMask = data.length - 1;
  }

  /** Add a new item to the queue. */
  public void add(int value) {
    if (size == data.length) {
      doubleArraySize();
    }

    tailIndex = (tailIndex + 1) & wrapAroundMask;
    data[tailIndex] = value;
    size++;
  }

  /**
   * Remove an item from the queue.
   *
   * @throws NoSuchElementException if the queue is empty.
   */
  public int remove() {
    if (size == 0) {
      throw new NoSuchElementException();
    }

    int value = data[headIndex];
    headIndex = (headIndex + 1) & wrapAroundMask;
    size--;

    return value;
  }

  /** Returns the number of items in the queue. */
  public int size() {
    return size;
  }

  /** Returns whether the queue is empty. */
  public boolean isEmpty() {
    return size == 0;
  }

  /** Clears the queue. */
  public void clear() {
    headIndex = 0;
    tailIndex = -1;
    size = 0;
  }

  /** Returns the length of the backing array. */
  public int capacity() {
    return data.length;
  }

  private void doubleArraySize() {
    int newCapacity = data.length << 1;
    if (newCapacity < 0) {
      throw new IllegalStateException();
    }

    int[] newData = new int[newCapacity];
    int itemsToRight = data.length - headIndex;
    int itemsToLeft = headIndex;
    System.arraycopy(data, headIndex, newData, 0, itemsToRight);
    System.arraycopy(data, 0, newData, itemsToRight, itemsToLeft);

    headIndex = 0;
    tailIndex = size - 1;
    data = newData;
    wrapAroundMask = data.length - 1;
  }
}