LongArrayQueue.java
/*
* Copyright 2023 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.common.util;
import static androidx.media3.common.util.Assertions.checkArgument;
import androidx.annotation.VisibleForTesting;
import java.util.NoSuchElementException;
/**
* Array-based unbounded queue for long primitives with amortized O(1) add and remove.
*
* <p>Use this class instead of a {@link java.util.Deque} to avoid boxing long primitives to {@link
* Long} instances.
*/
@UnstableApi
public final class LongArrayQueue {
/** Default initial capacity. */
public static final int DEFAULT_INITIAL_CAPACITY = 16;
private int headIndex;
private int tailIndex;
private int size;
private long[] data;
private int wrapAroundMask;
/** Creates a queue with an initial capacity of {@link #DEFAULT_INITIAL_CAPACITY}. */
public LongArrayQueue() {
this(DEFAULT_INITIAL_CAPACITY);
}
/**
* Creates a queue with capacity for at least {@code minCapacity}
*
* @param minCapacity minCapacity the minimum capacity, between 1 and 2^30 inclusive
*/
public LongArrayQueue(int minCapacity) {
checkArgument(minCapacity >= 0 && minCapacity <= (1 << 30));
minCapacity = minCapacity == 0 ? 1 : minCapacity;
// If capacity isn't a power of 2, round up to the next highest power of 2.
if (Integer.bitCount(minCapacity) != 1) {
minCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
}
headIndex = 0;
tailIndex = -1;
size = 0;
data = new long[minCapacity];
wrapAroundMask = data.length - 1;
}
/** Add a new item to the queue. */
public void add(long 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 long remove() {
if (size == 0) {
throw new NoSuchElementException();
}
long value = data[headIndex];
headIndex = (headIndex + 1) & wrapAroundMask;
size--;
return value;
}
/**
* Retrieves, but does not remove, the head of the queue.
*
* @throws NoSuchElementException if the queue is empty.
*/
public long element() {
if (size == 0) {
throw new NoSuchElementException();
}
return data[headIndex];
}
/** 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. */
@VisibleForTesting
/* package */ int capacity() {
return data.length;
}
private void doubleArraySize() {
int newCapacity = data.length << 1;
if (newCapacity < 0) {
throw new IllegalStateException();
}
long[] newData = new long[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;
}
}