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