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