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  */
14 package 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  */
21 public final class CircularIntArray
22 {
23     private int[] mElements;
24     private int mHead;
25     private int mTail;
26     private int mCapacityBitmask;
27 
doubleCapacity()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      * Create a CircularIntArray with default capacity.
46      */
CircularIntArray()47     public CircularIntArray() {
48         this(8);
49     }
50 
51     /**
52      * Create a CircularIntArray with capacity for at least minCapacity elements.
53      *
54      * @param minCapacity The minimum capacity required for the CircularIntArray.
55      */
CircularIntArray(int minCapacity)56     public CircularIntArray(int minCapacity) {
57         if (minCapacity <= 0) {
58             throw new IllegalArgumentException("capacity must be positive");
59         }
60         int arrayCapacity = minCapacity;
61         // If minCapacity isn't a power of 2, round up to the next highest power
62         // of 2.
63         if (Integer.bitCount(minCapacity) != 1) {
64             arrayCapacity = 1 << (Integer.highestOneBit(minCapacity) + 1);
65         }
66         mCapacityBitmask = arrayCapacity - 1;
67         mElements = new int[arrayCapacity];
68     }
69 
70     /**
71      * Add an integer in front of the CircularIntArray.
72      * @param e  Integer to add.
73      */
addFirst(int e)74     public void addFirst(int e) {
75         mHead = (mHead - 1) & mCapacityBitmask;
76         mElements[mHead] = e;
77         if (mHead == mTail) {
78             doubleCapacity();
79         }
80     }
81 
82     /**
83      * Add an integer at end of the CircularIntArray.
84      * @param e  Integer to add.
85      */
addLast(int e)86     public void addLast(int e) {
87         mElements[mTail] = e;
88         mTail = (mTail + 1) & mCapacityBitmask;
89         if (mTail == mHead) {
90             doubleCapacity();
91         }
92     }
93 
94     /**
95      * Remove first integer from front of the CircularIntArray and return it.
96      * @return  The integer removed.
97      * @throws ArrayIndexOutOfBoundsException if CircularIntArray is empty.
98      */
popFirst()99     public int popFirst() {
100         if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
101         int result = mElements[mHead];
102         mHead = (mHead + 1) & mCapacityBitmask;
103         return result;
104     }
105 
106     /**
107      * Remove last integer from end of the CircularIntArray and return it.
108      * @return  The integer removed.
109      * @throws ArrayIndexOutOfBoundsException if CircularIntArray is empty.
110      */
popLast()111     public int popLast() {
112         if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
113         int t = (mTail - 1) & mCapacityBitmask;
114         int result = mElements[t];
115         mTail = t;
116         return result;
117     }
118 
119     /**
120      * Remove all integers from the CircularIntArray.
121      */
clear()122     public void clear() {
123         mTail = mHead;
124     }
125 
126     /**
127      * Remove multiple integers from front of the CircularIntArray, ignore when numOfElements
128      * is less than or equals to 0.
129      * @param numOfElements  Number of integers to remove.
130      * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than
131      *         {@link #size()}
132      */
removeFromStart(int numOfElements)133     public void removeFromStart(int numOfElements) {
134         if (numOfElements <= 0) {
135             return;
136         }
137         if (numOfElements > size()) {
138             throw new ArrayIndexOutOfBoundsException();
139         }
140         mHead = (mHead + numOfElements) & mCapacityBitmask;
141     }
142 
143     /**
144      * Remove multiple elements from end of the CircularIntArray, ignore when numOfElements
145      * is less than or equals to 0.
146      * @param numOfElements  Number of integers to remove.
147      * @throws ArrayIndexOutOfBoundsException if numOfElements is larger than
148      *         {@link #size()}
149      */
removeFromEnd(int numOfElements)150     public void removeFromEnd(int numOfElements) {
151         if (numOfElements <= 0) {
152             return;
153         }
154         if (numOfElements > size()) {
155             throw new ArrayIndexOutOfBoundsException();
156         }
157         mTail = (mTail - numOfElements) & mCapacityBitmask;
158     }
159 
160     /**
161      * Get first integer of the CircularIntArray.
162      * @return The first integer.
163      * @throws {@link ArrayIndexOutOfBoundsException} if CircularIntArray is empty.
164      */
getFirst()165     public int getFirst() {
166         if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
167         return mElements[mHead];
168     }
169 
170     /**
171      * Get last integer of the CircularIntArray.
172      * @return The last integer.
173      * @throws {@link ArrayIndexOutOfBoundsException} if CircularIntArray is empty.
174      */
getLast()175     public int getLast() {
176         if (mHead == mTail) throw new ArrayIndexOutOfBoundsException();
177         return mElements[(mTail - 1) & mCapacityBitmask];
178     }
179 
180     /**
181      * Get nth (0 <= n <= size()-1) integer of the CircularIntArray.
182      * @param n  The zero based element index in the CircularIntArray.
183      * @return The nth integer.
184      * @throws {@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size().
185      */
get(int n)186     public int get(int n) {
187         if (n < 0 || n >= size()) throw new ArrayIndexOutOfBoundsException();
188         return mElements[(mHead + n) & mCapacityBitmask];
189     }
190 
191     /**
192      * Get number of integers in the CircularIntArray.
193      * @return Number of integers in the CircularIntArray.
194      */
size()195     public int size() {
196         return (mTail - mHead) & mCapacityBitmask;
197     }
198 
199     /**
200      * Return true if size() is 0.
201      * @return true if size() is 0.
202      */
isEmpty()203     public boolean isEmpty() {
204         return mHead == mTail;
205     }
206 
207 }
208