CircularArray.kt

/*
 * Copyright 2022 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.collection

import androidx.collection.CollectionPlatformUtils.createIndexOutOfBoundsException
import kotlin.jvm.JvmOverloads

/**
 * CircularArray is a generic circular array data structure that provides O(1) random read, O(1)
 * prepend and O(1) append. The CircularArray automatically grows its capacity when number of added
 * items is over its capacity.
 *
 * @constructor Creates a circular array with capacity for at least [minCapacity] elements.
 *
 * @param minCapacity the minimum capacity, between 1 and 2^30 inclusive
 */
public class CircularArray<E> @JvmOverloads public constructor(minCapacity: Int = 8) {
    private var elements: Array<E?>
    private var head = 0
    private var tail = 0
    private var capacityBitmask: Int

    init {
        require(minCapacity >= 1) { "capacity must be >= 1" }
        require(minCapacity <= 2 shl 29) { "capacity must be <= 2^30" }

        // If minCapacity isn't a power of 2, round up to the next highest
        // power of 2.
        val arrayCapacity: Int = if (minCapacity.countOneBits() != 1) {
            (minCapacity - 1).takeHighestOneBit() shl 1
        } else {
            minCapacity
        }
        capacityBitmask = arrayCapacity - 1
        @Suppress("UNCHECKED_CAST")
        elements = arrayOfNulls<Any?>(arrayCapacity) as Array<E?>
    }

    private fun doubleCapacity() {
        val n = elements.size
        val r = n - head
        val newCapacity = n shl 1
        if (newCapacity < 0) {
            throw RuntimeException("Max array capacity exceeded")
        }
        @Suppress("UNCHECKED_CAST")
        val a = arrayOfNulls<Any?>(newCapacity) as Array<E?>
        elements.copyInto(destination = a, destinationOffset = 0, startIndex = head, endIndex = n)
        elements.copyInto(destination = a, destinationOffset = r, startIndex = 0, endIndex = head)
        elements = a
        head = 0
        tail = n
        capacityBitmask = newCapacity - 1
    }

    /**
     * Add an element in front of the [CircularArray].
     *
     * @param element Element to add.
     */
    public fun addFirst(element: E) {
        head = (head - 1) and capacityBitmask
        elements[head] = element
        if (head == tail) {
            doubleCapacity()
        }
    }

    /**
     * Add an element at end of the CircularArray.
     *
     * @param element Element to add.
     */
    public fun addLast(element: E) {
        elements[tail] = element
        tail = tail + 1 and capacityBitmask
        if (tail == head) {
            doubleCapacity()
        }
    }

    /**
     * Remove first element from front of the [CircularArray] and return it.
     *
     * @return The element removed.
     * @throws [ArrayIndexOutOfBoundsException] if [CircularArray] is empty (on jvm)
     */
    public fun popFirst(): E {
        if (head == tail) {
            throw createIndexOutOfBoundsException()
        }
        val result = elements[head]
        elements[head] = null
        head = (head + 1) and capacityBitmask

        @Suppress("UNCHECKED_CAST")
        return result as E
    }

    /**
     * Remove last element from end of the [CircularArray] and return it.
     *
     * @return The element removed.
     * @throws [ArrayIndexOutOfBoundsException] if [CircularArray] is empty
     */
    public fun popLast(): E {
        if (head == tail) {
            throw createIndexOutOfBoundsException()
        }
        val t = (tail - 1) and capacityBitmask
        val result = elements[t]
        elements[t] = null
        tail = t

        @Suppress("UNCHECKED_CAST")
        return result as E
    }

    /**
     * Remove all elements from the [CircularArray].
     */
    public fun clear() {
        removeFromStart(size())
    }

    /**
     * Remove multiple elements from front of the [CircularArray], ignore when [count]
     * is less than or equal to 0.
     *
     * @param count Number of elements to remove.
     * @throws [ArrayIndexOutOfBoundsException] if [count] is larger than [size]
     */
    public fun removeFromStart(count: Int) {
        if (count <= 0) {
            return
        }
        if (count > size()) {
            throw createIndexOutOfBoundsException()
        }

        var numOfElements = count
        var end = elements.size
        if (numOfElements < end - head) {
            end = head + numOfElements
        }
        for (i in head until end) {
            elements[i] = null
        }
        val removed = end - head
        numOfElements -= removed
        head = head + removed and capacityBitmask
        if (numOfElements > 0) {
            // head wrapped to 0
            for (i in 0 until numOfElements) {
                elements[i] = null
            }
            head = numOfElements
        }
    }

    /**
     * Remove multiple elements from end of the [CircularArray], ignore when [count]
     * is less than or equals to 0.
     *
     * @param count Number of elements to remove.
     * @throws [ArrayIndexOutOfBoundsException] if [count] is larger than [size]
     */
    public fun removeFromEnd(count: Int) {
        if (count <= 0) {
            return
        }
        if (count > size()) {
            throw createIndexOutOfBoundsException()
        }

        var numOfElements = count
        var start = 0
        if (numOfElements < tail) {
            start = tail - numOfElements
        }
        for (i in start until tail) {
            elements[i] = null
        }
        val removed = tail - start
        numOfElements -= removed
        tail -= removed
        if (numOfElements > 0) {
            // tail wrapped to elements.length
            tail = elements.size
            val newTail = tail - numOfElements
            for (i in newTail until tail) {
                elements[i] = null
            }
            tail = newTail
        }
    }

    /**
     * Get first element of the [CircularArray].
     *
     * @return The first element.
     * @throws [ArrayIndexOutOfBoundsException] if [CircularArray] is empty
     */
    public val first: E
        get() {
            if (head == tail) {
                throw createIndexOutOfBoundsException()
            }
            return elements[head]!!
        }

    /**
     * Get last element of the [CircularArray].
     *
     * @return The last element.
     * @throws [ArrayIndexOutOfBoundsException] if [CircularArray] is empty
     */
    public val last: E
        get() {
            if (head == tail) {
                throw createIndexOutOfBoundsException()
            }
            return elements[tail - 1 and capacityBitmask]!!
        }

    /**
     * Get nth (0 <= n <= size()-1) element of the [CircularArray].
     *
     * @param index The zero based element index in the [CircularArray].
     * @return The nth element.
     * @throws [ArrayIndexOutOfBoundsException] if n < 0 or n >= size()
     */
    public operator fun get(index: Int): E {
        if (index < 0 || index >= size()) {
            throw createIndexOutOfBoundsException()
        }
        return elements[(head + index) and capacityBitmask]!!
    }

    /**
     * Get number of elements in the [CircularArray].
     *
     * @return Number of elements in the [CircularArray].
     */
    public fun size(): Int {
        return (tail - head) and capacityBitmask
    }

    /**
     * Return `true` if [size] is 0.
     *
     * @return `true` if [size] is 0.
     */
    public fun isEmpty(): Boolean = head == tail
}