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