CircularArray.java revision ae6b4cc8fd0872c64c4e1295e54e109222938d86
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 * CircularArray is a generic circular array data structure that provides O(1) random read, O(1) 18 * prepend and O(1) append. The CircularArray automatically grows its capacity when number of added 19 * items is over its capacity. 20 */ 21public final class CircularArray<E> { 22 private E[] mElements; 23 private int mHead; 24 private int mTail; 25 private int mCapacityBitmask; 26 27 private void doubleCapacity() { 28 int n = mElements.length; 29 int r = n - mHead; 30 int newCapacity = n << 1; 31 if (newCapacity < 0) { 32 throw new RuntimeException("Max array capacity exceeded"); 33 } 34 Object[] a = new Object[newCapacity]; 35 System.arraycopy(mElements, mHead, a, 0, r); 36 System.arraycopy(mElements, 0, a, r, mHead); 37 mElements = (E[]) a; 38 mHead = 0; 39 mTail = n; 40 mCapacityBitmask = newCapacity - 1; 41 } 42 43 /** 44 * Create a CircularArray with default capacity. 45 */ 46 public CircularArray() { 47 this(8); 48 } 49 50 /** 51 * Create a CircularArray with capacity for at least minCapacity elements. 52 * 53 * @param minCapacity The minimum capacity required for the CircularArray. 54 */ 55 public CircularArray(int minCapacity) { 56 if (minCapacity <= 0) { 57 throw new IllegalArgumentException("capacity must be positive"); 58 } 59 int arrayCapacity = minCapacity; 60 // If minCapacity isn't a power of 2, round up to the next highest power 61 // of 2. 62 if (Integer.bitCount(minCapacity) != 1) { 63 arrayCapacity = 1 << (Integer.highestOneBit(minCapacity) + 1); 64 } 65 mCapacityBitmask = arrayCapacity - 1; 66 mElements = (E[]) new Object[arrayCapacity]; 67 } 68 69 /** 70 * Add an element in front of the CircularArray. 71 * @param e Element to add. 72 */ 73 public void addFirst(E e) { 74 mHead = (mHead - 1) & mCapacityBitmask; 75 mElements[mHead] = e; 76 if (mHead == mTail) { 77 doubleCapacity(); 78 } 79 } 80 81 /** 82 * Add an element at end of the CircularArray. 83 * @param e Element to add. 84 */ 85 public void addLast(E e) { 86 mElements[mTail] = e; 87 mTail = (mTail + 1) & mCapacityBitmask; 88 if (mTail == mHead) { 89 doubleCapacity(); 90 } 91 } 92 93 /** 94 * Remove first element from front of the CircularArray and return it. 95 * @return The element removed. 96 * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty. 97 */ 98 public E popFirst() { 99 if (mHead == mTail) { 100 throw new ArrayIndexOutOfBoundsException(); 101 } 102 E result = mElements[mHead]; 103 mElements[mHead] = null; 104 mHead = (mHead + 1) & mCapacityBitmask; 105 return result; 106 } 107 108 /** 109 * Remove last element from end of the CircularArray and return it. 110 * @return The element removed. 111 * @throws {@link ArrayIndexOutOfBoundsException} if CircularArray is empty. 112 */ 113 public E popLast() { 114 if (mHead == mTail) { 115 throw new ArrayIndexOutOfBoundsException(); 116 } 117 int t = (mTail - 1) & mCapacityBitmask; 118 E result = mElements[t]; 119 mElements[t] = null; 120 mTail = t; 121 return result; 122 } 123 124 /** 125 * Remove all elements from the CircularArray. 126 */ 127 public void clear() { 128 removeFromStart(size()); 129 } 130 131 /** 132 * Remove multiple elements from front of the CircularArray, ignore when numOfElements 133 * is less than or equals to 0. 134 * @param numOfElements Number of elements to remove. 135 * @throws {@link ArrayIndexOutOfBoundsException} if numOfElements is larger than 136 * {@link #size()} 137 */ 138 public void removeFromStart(int numOfElements) { 139 if (numOfElements <= 0) { 140 return; 141 } 142 if (numOfElements > size()) { 143 throw new ArrayIndexOutOfBoundsException(); 144 } 145 int end = mElements.length; 146 if (numOfElements < end - mHead) { 147 end = mHead + numOfElements; 148 } 149 for (int i = mHead; i < end; i++) { 150 mElements[i] = null; 151 } 152 int removed = (end - mHead); 153 numOfElements -= removed; 154 mHead = (mHead + removed) & mCapacityBitmask; 155 if (numOfElements > 0) { 156 // mHead wrapped to 0 157 for (int i = 0; i < numOfElements; i++) { 158 mElements[i] = null; 159 } 160 mHead = numOfElements; 161 } 162 } 163 164 /** 165 * Remove multiple elements from end of the CircularArray, ignore when numOfElements 166 * is less than or equals to 0. 167 * @param numOfElements Number of elements to remove. 168 * @throws {@link ArrayIndexOutOfBoundsException} if numOfElements is larger than 169 * {@link #size()} 170 */ 171 public void removeFromEnd(int numOfElements) { 172 if (numOfElements <= 0) { 173 return; 174 } 175 if (numOfElements > size()) { 176 throw new ArrayIndexOutOfBoundsException(); 177 } 178 int start = 0; 179 if (numOfElements < mTail) { 180 start = mTail - numOfElements; 181 } 182 for (int i = start; i < mTail; i++) { 183 mElements[i] = null; 184 } 185 int removed = (mTail - start); 186 numOfElements -= removed; 187 mTail = mTail - removed; 188 if (numOfElements > 0) { 189 // mTail wrapped to mElements.length 190 mTail = mElements.length; 191 int newTail = mTail - numOfElements; 192 for (int i = newTail; i < mTail; i++) { 193 mElements[i] = null; 194 } 195 mTail = newTail; 196 } 197 } 198 199 /** 200 * Get first element of the CircularArray. 201 * @return The first element. 202 * @throws{@link ArrayIndexOutOfBoundsException} if CircularArray is empty. 203 */ 204 public E getFirst() { 205 if (mHead == mTail) { 206 throw new ArrayIndexOutOfBoundsException(); 207 } 208 return mElements[mHead]; 209 } 210 211 /** 212 * Get last element of the CircularArray. 213 * @return The last element. 214 * @throws{@link ArrayIndexOutOfBoundsException} if CircularArray is empty. 215 */ 216 public E getLast() { 217 if (mHead == mTail) { 218 throw new ArrayIndexOutOfBoundsException(); 219 } 220 return mElements[(mTail - 1) & mCapacityBitmask]; 221 } 222 223 /** 224 * Get nth (0 <= n <= size()-1) element of the CircularArray. 225 * @param n The zero based element index in the CircularArray. 226 * @return The nth element. 227 * @throws{@link ArrayIndexOutOfBoundsException} if n < 0 or n >= size(). 228 */ 229 public E get(int n) { 230 if (n < 0 || n >= size()) { 231 throw new ArrayIndexOutOfBoundsException(); 232 } 233 return mElements[(mHead + n) & mCapacityBitmask]; 234 } 235 236 /** 237 * Get number of elements in the CircularArray. 238 * @return Number of elements in the CircularArray. 239 */ 240 public int size() { 241 return (mTail - mHead) & mCapacityBitmask; 242 } 243 244 /** 245 * Return true if size() is 0. 246 * @return true if size() is 0. 247 */ 248 public boolean isEmpty() { 249 return mHead == mTail; 250 } 251 252} 253