1/*
2 * Copyright 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16package androidx.collection;
17
18/**
19 * CircularIntArray is a circular integer array data structure that provides O(1) random read, O(1)
20 * prepend and O(1) append. The CircularIntArray automatically grows its capacity when number of
21 * added integers is over its capacity.
22 */
23public final class CircularIntArray
24{
25    private int[] mElements;
26    private int mHead;
27    private int mTail;
28    private int mCapacityBitmask;
29
30    private void doubleCapacity() {
31        int n = mElements.length;
32        int r = n - mHead;
33        int newCapacity = n << 1;
34        if (newCapacity < 0) {
35            throw new RuntimeException("Max array capacity exceeded");
36        }
37        int[] a = new int[newCapacity];
38        System.arraycopy(mElements, mHead, a, 0, r);
39        System.arraycopy(mElements, 0, a, r, mHead);
40        mElements = a;
41        mHead = 0;
42        mTail = n;
43        mCapacityBitmask = newCapacity - 1;
44    }
45
46    /**
47     * Creates a circular array with default capacity.
48     */
49    public CircularIntArray() {
50        this(8);
51    }
52
53    /**
54     * Creates a circular array with capacity for at least {@code minCapacity}
55     * elements.
56     *
57     * @param minCapacity the minimum capacity, between 1 and 2^30 inclusive
58     */
59    public CircularIntArray(int minCapacity) {
60        if (minCapacity < 1) {
61            throw new IllegalArgumentException("capacity must be >= 1");
62        }
63        if (minCapacity > (2 << 29)) {
64            throw new IllegalArgumentException("capacity must be <= 2^30");
65        }
66
67        // If minCapacity isn't a power of 2, round up to the next highest
68        // power of 2.
69        final int arrayCapacity;
70        if (Integer.bitCount(minCapacity) != 1) {
71            arrayCapacity = Integer.highestOneBit(minCapacity - 1) << 1;
72        } else {
73            arrayCapacity = minCapacity;
74        }
75
76        mCapacityBitmask = arrayCapacity - 1;
77        mElements = new int[arrayCapacity];
78    }
79
80    /**
81     * Add an integer in front of the CircularIntArray.
82     * @param e  Integer to add.
83     */
84    public void addFirst(int e) {
85        mHead = (mHead - 1) & mCapacityBitmask;
86        mElements[mHead] = e;
87        if (mHead == mTail) {
88            doubleCapacity();
89        }
90    }
91
92    /**
93     * Add an integer at end of the CircularIntArray.
94     * @param e  Integer to add.
95     */
96    public void addLast(int e) {
97        mElements[mTail] = e;
98        mTail = (mTail + 1) & mCapacityBitmask;
99        if (mTail == mHead) {
100            doubleCapacity();
101        }
102    }
103
104    /**
105     * Remove first integer from front of the CircularIntArray and return it.
106     * @return  The integer removed.
107     * @throws ArrayIndexOutOfBoundsException if CircularIntArray is empty.
108     */
109    public int popFirst() {
110        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
111        int result = mElements[mHead];
112        mHead = (mHead + 1) & mCapacityBitmask;
113        return result;
114    }
115
116    /**
117     * Remove last integer from end of the CircularIntArray and return it.
118     * @return  The integer removed.
119     * @throws ArrayIndexOutOfBoundsException if CircularIntArray is empty.
120     */
121    public int popLast() {
122        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
123        int t = (mTail - 1) & mCapacityBitmask;
124        int result = mElements[t];
125        mTail = t;
126        return result;
127    }
128
129    /**
130     * Remove all integers from the CircularIntArray.
131     */
132    public void clear() {
133        mTail = mHead;
134    }
135
136    /**
137     * Remove multiple integers from front of the CircularIntArray, ignore when numOfElements
138     * is less than or equals to 0.
139     * @param numOfElements  Number of integers to remove.
140     * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than
141     *         {@link #size()}
142     */
143    public void removeFromStart(int numOfElements) {
144        if (numOfElements <= 0) {
145            return;
146        }
147        if (numOfElements > size()) {
148            throw new ArrayIndexOutOfBoundsException();
149        }
150        mHead = (mHead + numOfElements) & mCapacityBitmask;
151    }
152
153    /**
154     * Remove multiple elements from end of the CircularIntArray, ignore when numOfElements
155     * is less than or equals to 0.
156     * @param numOfElements  Number of integers to remove.
157     * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than
158     *         {@link #size()}
159     */
160    public void removeFromEnd(int numOfElements) {
161        if (numOfElements <= 0) {
162            return;
163        }
164        if (numOfElements > size()) {
165            throw new ArrayIndexOutOfBoundsException();
166        }
167        mTail = (mTail - numOfElements) & mCapacityBitmask;
168    }
169
170    /**
171     * Get first integer of the CircularIntArray.
172     * @return The first integer.
173     * @throws {@link ArrayIndexOutOfBoundsException} if CircularIntArray is empty.
174     */
175    public int getFirst() {
176        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
177        return mElements[mHead];
178    }
179
180    /**
181     * Get last integer of the CircularIntArray.
182     * @return The last integer.
183     * @throws {@link ArrayIndexOutOfBoundsException} if CircularIntArray is empty.
184     */
185    public int getLast() {
186        if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
187        return mElements[(mTail - 1) & mCapacityBitmask];
188    }
189
190    /**
191     * Get nth (0 <= n <= size()-1) integer of the CircularIntArray.
192     * @param n  The zero based element index in the CircularIntArray.
193     * @return The nth integer.
194     * @throws {@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size().
195     */
196    public int get(int n) {
197        if (n < 0 || n >= size()) throw new ArrayIndexOutOfBoundsException();
198        return mElements[(mHead + n) & mCapacityBitmask];
199    }
200
201    /**
202     * Get number of integers in the CircularIntArray.
203     * @return Number of integers in the CircularIntArray.
204     */
205    public int size() {
206        return (mTail - mHead) & mCapacityBitmask;
207    }
208
209    /**
210     * Return true if size() is 0.
211     * @return true if size() is 0.
212     */
213    public boolean isEmpty() {
214        return mHead == mTail;
215    }
216
217}
218