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 libcore.util.EmptyArray;
23 
24 import java.util.NoSuchElementException;
25 
26 /**
27  * A lightweight implementation for a queue with long values.
28  * Additionally supports getting an element with a specified position from the head of the queue.
29  * The queue grows in size if needed to accommodate new elements.
30  *
31  * @hide
32  */
33 public class LongArrayQueue {
34 
35     private long[] mValues;
36     private int mSize;
37     private int mHead;
38     private int mTail;
39 
40     /**
41      * Initializes a queue with the given starting capacity.
42      *
43      * @param initialCapacity the capacity.
44      */
LongArrayQueue(int initialCapacity)45     public LongArrayQueue(int initialCapacity) {
46         if (initialCapacity == 0) {
47             mValues = EmptyArray.LONG;
48         } else {
49             mValues = ArrayUtils.newUnpaddedLongArray(initialCapacity);
50         }
51         mSize = 0;
52         mHead = mTail = 0;
53     }
54 
55     /**
56      * Initializes a queue with default starting capacity.
57      */
LongArrayQueue()58     public LongArrayQueue() {
59         this(16);
60     }
61 
grow()62     private void grow() {
63         if (mSize < mValues.length) {
64             throw new IllegalStateException("Queue not full yet!");
65         }
66         final int newSize = GrowingArrayUtils.growSize(mSize);
67         final long[] newArray = ArrayUtils.newUnpaddedLongArray(newSize);
68         final int r = mValues.length - mHead; // Number of elements on and to the right of head.
69         System.arraycopy(mValues, mHead, newArray, 0, r);
70         System.arraycopy(mValues, 0, newArray, r, mHead);
71         mValues = newArray;
72         mHead = 0;
73         mTail = mSize;
74     }
75 
76     /**
77      * Returns the number of elements in the queue.
78      */
size()79     public int size() {
80         return mSize;
81     }
82 
83     /**
84      * Removes all elements from this queue.
85      */
clear()86     public void clear() {
87         mSize = 0;
88         mHead = mTail = 0;
89     }
90 
91     /**
92      * Adds a value to the tail of the queue.
93      *
94      * @param value the value to be added.
95      */
addLast(long value)96     public void addLast(long value) {
97         if (mSize == mValues.length) {
98             grow();
99         }
100         mValues[mTail] = value;
101         mTail = (mTail + 1) % mValues.length;
102         mSize++;
103     }
104 
105     /**
106      * Removes an element from the head of the queue.
107      *
108      * @return the element at the head of the queue.
109      * @throws NoSuchElementException if the queue is empty.
110      */
removeFirst()111     public long removeFirst() {
112         if (mSize == 0) {
113             throw new NoSuchElementException("Queue is empty!");
114         }
115         final long ret = mValues[mHead];
116         mHead = (mHead + 1) % mValues.length;
117         mSize--;
118         return ret;
119     }
120 
121     /**
122      * Returns the element at the given position from the head of the queue, where 0 represents the
123      * head of the queue.
124      *
125      * @param position the position from the head of the queue.
126      * @return the element found at the given position.
127      * @throws IndexOutOfBoundsException if {@code position} < {@code 0} or
128      *                                   {@code position} >= {@link #size()}
129      */
get(int position)130     public long get(int position) {
131         if (position < 0 || position >= mSize) {
132             throw new IndexOutOfBoundsException("Index " + position
133                     + " not valid for a queue of size " + mSize);
134         }
135         final int index = (mHead + position) % mValues.length;
136         return mValues[index];
137     }
138 
139     /**
140      * Returns the element at the head of the queue, without removing it.
141      *
142      * @return the element at the head of the queue.
143      * @throws NoSuchElementException if the queue is empty
144      */
peekFirst()145     public long peekFirst() {
146         if (mSize == 0) {
147             throw new NoSuchElementException("Queue is empty!");
148         }
149         return mValues[mHead];
150     }
151 
152     /**
153      * Returns the element at the tail of the queue.
154      *
155      * @return the element at the tail of the queue.
156      * @throws NoSuchElementException if the queue is empty.
157      */
peekLast()158     public long peekLast() {
159         if (mSize == 0) {
160             throw new NoSuchElementException("Queue is empty!");
161         }
162         final int index = (mTail == 0) ? mValues.length - 1 : mTail - 1;
163         return mValues[index];
164     }
165 }
166