1 /* 2 * Copyright (C) 2019 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package android.util; 18 19 import com.android.internal.util.ArrayUtils; 20 import com.android.internal.util.GrowingArrayUtils; 21 22 import java.util.NoSuchElementException; 23 24 /** 25 * A lightweight implementation for a queue with long values. 26 * Additionally supports getting an element with a specified position from the head of the queue. 27 * The queue grows in size if needed to accommodate new elements. 28 * 29 * @hide 30 */ 31 @android.ravenwood.annotation.RavenwoodKeepWholeClass 32 public class LongArrayQueue { 33 34 private long[] mValues; 35 private int mSize; 36 private int mHead; 37 private int mTail; 38 39 /** 40 * Initializes a queue with the given starting capacity. 41 * 42 * @param initialCapacity the capacity. 43 */ LongArrayQueue(int initialCapacity)44 public LongArrayQueue(int initialCapacity) { 45 if (initialCapacity == 0) { 46 mValues = EmptyArray.LONG; 47 } else { 48 mValues = ArrayUtils.newUnpaddedLongArray(initialCapacity); 49 } 50 mSize = 0; 51 mHead = mTail = 0; 52 } 53 54 /** 55 * Initializes a queue with default starting capacity. 56 */ LongArrayQueue()57 public LongArrayQueue() { 58 this(16); 59 } 60 grow()61 private void grow() { 62 if (mSize < mValues.length) { 63 throw new IllegalStateException("Queue not full yet!"); 64 } 65 final int newSize = GrowingArrayUtils.growSize(mSize); 66 final long[] newArray = ArrayUtils.newUnpaddedLongArray(newSize); 67 final int r = mValues.length - mHead; // Number of elements on and to the right of head. 68 System.arraycopy(mValues, mHead, newArray, 0, r); 69 System.arraycopy(mValues, 0, newArray, r, mHead); 70 mValues = newArray; 71 mHead = 0; 72 mTail = mSize; 73 } 74 75 /** 76 * Returns the number of elements in the queue. 77 */ size()78 public int size() { 79 return mSize; 80 } 81 82 /** 83 * Removes all elements from this queue. 84 */ clear()85 public void clear() { 86 mSize = 0; 87 mHead = mTail = 0; 88 } 89 90 /** 91 * Adds a value to the tail of the queue. 92 * 93 * @param value the value to be added. 94 */ addLast(long value)95 public void addLast(long value) { 96 if (mSize == mValues.length) { 97 grow(); 98 } 99 mValues[mTail] = value; 100 mTail = (mTail + 1) % mValues.length; 101 mSize++; 102 } 103 104 /** 105 * Removes an element from the head of the queue. 106 * 107 * @return the element at the head of the queue. 108 * @throws NoSuchElementException if the queue is empty. 109 */ removeFirst()110 public long removeFirst() { 111 if (mSize == 0) { 112 throw new NoSuchElementException("Queue is empty!"); 113 } 114 final long ret = mValues[mHead]; 115 mHead = (mHead + 1) % mValues.length; 116 mSize--; 117 return ret; 118 } 119 120 /** 121 * Returns the element at the given position from the head of the queue, where 0 represents the 122 * head of the queue. 123 * 124 * @param position the position from the head of the queue. 125 * @return the element found at the given position. 126 * @throws IndexOutOfBoundsException if {@code position} < {@code 0} or 127 * {@code position} >= {@link #size()} 128 */ get(int position)129 public long get(int position) { 130 if (position < 0 || position >= mSize) { 131 throw new IndexOutOfBoundsException("Index " + position 132 + " not valid for a queue of size " + mSize); 133 } 134 final int index = (mHead + position) % mValues.length; 135 return mValues[index]; 136 } 137 138 /** 139 * Returns the element at the head of the queue, without removing it. 140 * 141 * @return the element at the head of the queue. 142 * @throws NoSuchElementException if the queue is empty 143 */ peekFirst()144 public long peekFirst() { 145 if (mSize == 0) { 146 throw new NoSuchElementException("Queue is empty!"); 147 } 148 return mValues[mHead]; 149 } 150 151 /** 152 * Returns the element at the tail of the queue. 153 * 154 * @return the element at the tail of the queue. 155 * @throws NoSuchElementException if the queue is empty. 156 */ peekLast()157 public long peekLast() { 158 if (mSize == 0) { 159 throw new NoSuchElementException("Queue is empty!"); 160 } 161 final int index = (mTail == 0) ? mValues.length - 1 : mTail - 1; 162 return mValues[index]; 163 } 164 165 /** 166 * {@inheritDoc} 167 */ 168 @Override toString()169 public String toString() { 170 if (mSize <= 0) { 171 return "{}"; 172 } 173 174 final StringBuilder buffer = new StringBuilder(mSize * 64); 175 buffer.append('{'); 176 buffer.append(get(0)); 177 for (int i = 1; i < mSize; i++) { 178 buffer.append(", "); 179 buffer.append(get(i)); 180 } 181 buffer.append('}'); 182 return buffer.toString(); 183 } 184 } 185