public final class

CircularIntArray

extends java.lang.Object

 java.lang.Object

↳androidx.collection.CircularIntArray

Gradle dependencies

compile group: 'androidx.collection', name: 'collection', version: '1.2.0'

  • groupId: androidx.collection
  • artifactId: collection
  • version: 1.2.0

Artifact androidx.collection:collection:1.2.0 it located at Google repository (https://maven.google.com/)

Androidx artifact mapping:

androidx.collection:collection com.android.support:collections

Androidx class mapping:

androidx.collection.CircularIntArray android.support.v4.util.CircularIntArray

Overview

CircularIntArray is a circular integer array data structure that provides O(1) random read, O(1) prepend and O(1) append. The CircularIntArray automatically grows its capacity when number of added integers is over its capacity.

Summary

Constructors
publicCircularIntArray()

Creates a circular array with default capacity.

publicCircularIntArray(int minCapacity)

Creates a circular array with capacity for at least minCapacity elements.

Methods
public voidaddFirst(int e)

Add an integer in front of the CircularIntArray.

public voidaddLast(int e)

Add an integer at end of the CircularIntArray.

public voidclear()

Remove all integers from the CircularIntArray.

public intget(int n)

Get nth (0 <= n <= size()-1) integer of the CircularIntArray.

public intgetFirst()

Get first integer of the CircularIntArray.

public intgetLast()

Get last integer of the CircularIntArray.

public booleanisEmpty()

Return true if size() is 0.

public intpopFirst()

Remove first integer from front of the CircularIntArray and return it.

public intpopLast()

Remove last integer from end of the CircularIntArray and return it.

public voidremoveFromEnd(int numOfElements)

Remove multiple elements from end of the CircularIntArray, ignore when numOfElements is less than or equals to 0.

public voidremoveFromStart(int numOfElements)

Remove multiple integers from front of the CircularIntArray, ignore when numOfElements is less than or equals to 0.

public intsize()

Get number of integers in the CircularIntArray.

from java.lang.Objectclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructors

public CircularIntArray()

Creates a circular array with default capacity.

public CircularIntArray(int minCapacity)

Creates a circular array with capacity for at least minCapacity elements.

Parameters:

minCapacity: the minimum capacity, between 1 and 2^30 inclusive

Methods

public void addFirst(int e)

Add an integer in front of the CircularIntArray.

Parameters:

e: Integer to add.

public void addLast(int e)

Add an integer at end of the CircularIntArray.

Parameters:

e: Integer to add.

public int popFirst()

Remove first integer from front of the CircularIntArray and return it.

Returns:

The integer removed.

public int popLast()

Remove last integer from end of the CircularIntArray and return it.

Returns:

The integer removed.

public void clear()

Remove all integers from the CircularIntArray.

public void removeFromStart(int numOfElements)

Remove multiple integers from front of the CircularIntArray, ignore when numOfElements is less than or equals to 0.

Parameters:

numOfElements: Number of integers to remove.

public void removeFromEnd(int numOfElements)

Remove multiple elements from end of the CircularIntArray, ignore when numOfElements is less than or equals to 0.

Parameters:

numOfElements: Number of integers to remove.

public int getFirst()

Get first integer of the CircularIntArray.

Returns:

The first integer.

public int getLast()

Get last integer of the CircularIntArray.

Returns:

The last integer.

public int get(int n)

Get nth (0 <= n <= size()-1) integer of the CircularIntArray.

Parameters:

n: The zero based element index in the CircularIntArray.

Returns:

The nth integer.

public int size()

Get number of integers in the CircularIntArray.

Returns:

Number of integers in the CircularIntArray.

public boolean isEmpty()

Return true if size() is 0.

Returns:

true if size() is 0.

Source

/*
 * Copyright 2018 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;

/**
 * CircularIntArray is a circular integer array data structure that provides O(1) random read, O(1)
 * prepend and O(1) append. The CircularIntArray automatically grows its capacity when number of
 * added integers is over its capacity.
 */
public final class CircularIntArray
{
    private int[] mElements;
    private int mHead;
    private int mTail;
    private int mCapacityBitmask;

    private void doubleCapacity() {
        int n = mElements.length;
        int r = n - mHead;
        int newCapacity = n << 1;
        if (newCapacity < 0) {
            throw new RuntimeException("Max array capacity exceeded");
        }
        int[] a = new int[newCapacity];
        System.arraycopy(mElements, mHead, a, 0, r);
        System.arraycopy(mElements, 0, a, r, mHead);
        mElements = a;
        mHead = 0;
        mTail = n;
        mCapacityBitmask = newCapacity - 1;
    }

    /**
     * Creates a circular array with default capacity.
     */
    public CircularIntArray() {
        this(8);
    }

    /**
     * Creates a circular array with capacity for at least {@code minCapacity}
     * elements.
     *
     * @param minCapacity the minimum capacity, between 1 and 2^30 inclusive
     */
    public CircularIntArray(int minCapacity) {
        if (minCapacity < 1) {
            throw new IllegalArgumentException("capacity must be >= 1");
        }
        if (minCapacity > (2 << 29)) {
            throw new IllegalArgumentException("capacity must be <= 2^30");
        }

        // If minCapacity isn't a power of 2, round up to the next highest
        // power of 2.
        final int arrayCapacity;
        if (Integer.bitCount(minCapacity) != 1) {
            arrayCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
        } else {
            arrayCapacity = minCapacity;
        }

        mCapacityBitmask = arrayCapacity - 1;
        mElements = new int[arrayCapacity];
    }

    /**
     * Add an integer in front of the CircularIntArray.
     * @param e  Integer to add.
     */
    public void addFirst(int e) {
        mHead = (mHead - 1) & mCapacityBitmask;
        mElements[mHead] = e;
        if (mHead == mTail) {
            doubleCapacity();
        }
    }

    /**
     * Add an integer at end of the CircularIntArray.
     * @param e  Integer to add.
     */
    public void addLast(int e) {
        mElements[mTail] = e;
        mTail = (mTail + 1) & mCapacityBitmask;
        if (mTail == mHead) {
            doubleCapacity();
        }
    }

    /**
     * Remove first integer from front of the CircularIntArray and return it.
     * @return  The integer removed.
     * @throws ArrayIndexOutOfBoundsException if CircularIntArray is empty.
     */
    public int popFirst() {
        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
        int result = mElements[mHead];
        mHead = (mHead + 1) & mCapacityBitmask;
        return result;
    }

    /**
     * Remove last integer from end of the CircularIntArray and return it.
     * @return  The integer removed.
     * @throws ArrayIndexOutOfBoundsException if CircularIntArray is empty.
     */
    public int popLast() {
        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
        int t = (mTail - 1) & mCapacityBitmask;
        int result = mElements[t];
        mTail = t;
        return result;
    }

    /**
     * Remove all integers from the CircularIntArray.
     */
    public void clear() {
        mTail = mHead;
    }

    /**
     * Remove multiple integers from front of the CircularIntArray, ignore when numOfElements
     * is less than or equals to 0.
     * @param numOfElements  Number of integers to remove.
     * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than
     *         {@link #size()}
     */
    public void removeFromStart(int numOfElements) {
        if (numOfElements <= 0) {
            return;
        }
        if (numOfElements > size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        mHead = (mHead + numOfElements) & mCapacityBitmask;
    }

    /**
     * Remove multiple elements from end of the CircularIntArray, ignore when numOfElements
     * is less than or equals to 0.
     * @param numOfElements  Number of integers to remove.
     * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than
     *         {@link #size()}
     */
    public void removeFromEnd(int numOfElements) {
        if (numOfElements <= 0) {
            return;
        }
        if (numOfElements > size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        mTail = (mTail - numOfElements) & mCapacityBitmask;
    }

    /**
     * Get first integer of the CircularIntArray.
     * @return The first integer.
     * @throws {@link ArrayIndexOutOfBoundsException} if CircularIntArray is empty.
     */
    public int getFirst() {
        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
        return mElements[mHead];
    }

    /**
     * Get last integer of the CircularIntArray.
     * @return The last integer.
     * @throws {@link ArrayIndexOutOfBoundsException} if CircularIntArray is empty.
     */
    public int getLast() {
        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
        return mElements[(mTail - 1) & mCapacityBitmask];
    }

    /**
     * Get nth (0 <= n <= size()-1) integer of the CircularIntArray.
     * @param n  The zero based element index in the CircularIntArray.
     * @return The nth integer.
     * @throws {@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size().
     */
    public int get(int n) {
        if (n < 0 || n >= size()) throw new ArrayIndexOutOfBoundsException();
        return mElements[(mHead + n) & mCapacityBitmask];
    }

    /**
     * Get number of integers in the CircularIntArray.
     * @return Number of integers in the CircularIntArray.
     */
    public int size() {
        return (mTail - mHead) & mCapacityBitmask;
    }

    /**
     * Return true if size() is 0.
     * @return true if size() is 0.
     */
    public boolean isEmpty() {
        return mHead == mTail;
    }

}