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 static org.junit.Assert.assertEquals;
20 import static org.junit.Assert.assertNotEquals;
21 import static org.junit.Assert.fail;
22 
23 import androidx.test.filters.SmallTest;
24 import androidx.test.runner.AndroidJUnit4;
25 
26 import org.junit.Before;
27 import org.junit.Test;
28 import org.junit.runner.RunWith;
29 
30 import java.util.NoSuchElementException;
31 
32 /**
33  * Internal tests for {@link LongArrayQueue}.
34  */
35 @SmallTest
36 @RunWith(AndroidJUnit4.class)
37 public class LongArrayQueueTest {
38 
39     private LongArrayQueue mQueueUnderTest;
40 
41     @Before
setUp()42     public void setUp() {
43         mQueueUnderTest = new LongArrayQueue();
44     }
45 
46     @Test
removeFirstOnEmptyQueue()47     public void removeFirstOnEmptyQueue() {
48         try {
49             mQueueUnderTest.removeFirst();
50             fail("removeFirst() succeeded on an empty queue!");
51         } catch (NoSuchElementException e) {
52         }
53         mQueueUnderTest.addLast(5);
54         mQueueUnderTest.removeFirst();
55         try {
56             mQueueUnderTest.removeFirst();
57             fail("removeFirst() succeeded on an empty queue!");
58         } catch (NoSuchElementException e) {
59         }
60     }
61 
62     @Test
addLastRemoveFirstFifo()63     public void addLastRemoveFirstFifo() {
64         mQueueUnderTest.addLast(1);
65         assertEquals(1, mQueueUnderTest.removeFirst());
66         int n = 890;
67         int removes = 0;
68         for (int i = 0; i < n; i++) {
69             mQueueUnderTest.addLast(i);
70             if ((i % 3) == 0) {
71                 assertEquals(removes++, mQueueUnderTest.removeFirst());
72             }
73         }
74         while (removes < n) {
75             assertEquals(removes++, mQueueUnderTest.removeFirst());
76         }
77     }
78 
79     @Test
peekFirstOnEmptyQueue()80     public void peekFirstOnEmptyQueue() {
81         try {
82             mQueueUnderTest.peekFirst();
83             fail("peekFirst() succeeded on an empty queue!");
84         } catch (NoSuchElementException e) {
85         }
86         mQueueUnderTest.addLast(5);
87         mQueueUnderTest.removeFirst();
88         try {
89             mQueueUnderTest.peekFirst();
90             fail("peekFirst() succeeded on an empty queue!");
91         } catch (NoSuchElementException e) {
92         }
93     }
94 
95     @Test
peekFirstChanges()96     public void peekFirstChanges() {
97         mQueueUnderTest.addLast(1);
98         assertEquals(1, mQueueUnderTest.peekFirst());
99         mQueueUnderTest.addLast(2);
100         mQueueUnderTest.addLast(3);
101         mQueueUnderTest.addLast(4);
102         // addLast() has no effect on peekFirst().
103         assertEquals(1, mQueueUnderTest.peekFirst());
104         mQueueUnderTest.removeFirst();
105         mQueueUnderTest.removeFirst();
106         assertEquals(3, mQueueUnderTest.peekFirst());
107     }
108 
109     @Test
peekLastOnEmptyQueue()110     public void peekLastOnEmptyQueue() {
111         try {
112             mQueueUnderTest.peekLast();
113             fail("peekLast() succeeded on an empty queue!");
114         } catch (NoSuchElementException e) {
115         }
116         mQueueUnderTest.addLast(5);
117         mQueueUnderTest.removeFirst();
118         try {
119             mQueueUnderTest.peekLast();
120             fail("peekLast() succeeded on an empty queue!");
121         } catch (NoSuchElementException e) {
122         }
123     }
124 
125     @Test
peekLastChanges()126     public void peekLastChanges() {
127         mQueueUnderTest.addLast(1);
128         assertEquals(1, mQueueUnderTest.peekLast());
129         mQueueUnderTest.addLast(2);
130         mQueueUnderTest.addLast(3);
131         mQueueUnderTest.addLast(4);
132         assertEquals(4, mQueueUnderTest.peekLast());
133         mQueueUnderTest.removeFirst();
134         mQueueUnderTest.removeFirst();
135         // removeFirst() has no effect on peekLast().
136         assertEquals(4, mQueueUnderTest.peekLast());
137     }
138 
139     @Test
peekFirstVsPeekLast()140     public void peekFirstVsPeekLast() {
141         mQueueUnderTest.addLast(2);
142         assertEquals(mQueueUnderTest.peekFirst(), mQueueUnderTest.peekLast());
143         mQueueUnderTest.addLast(3);
144         assertNotEquals(mQueueUnderTest.peekFirst(), mQueueUnderTest.peekLast());
145         mQueueUnderTest.removeFirst();
146         assertEquals(mQueueUnderTest.peekFirst(), mQueueUnderTest.peekLast());
147     }
148 
149     @Test
peekFirstVsRemoveFirst()150     public void peekFirstVsRemoveFirst() {
151         int n = 25;
152         for (int i = 0; i < n; i++) {
153             mQueueUnderTest.addLast(i + 1);
154         }
155         for (int i = 0; i < n; i++) {
156             long peekVal = mQueueUnderTest.peekFirst();
157             assertEquals(peekVal, mQueueUnderTest.removeFirst());
158         }
159     }
160 
161     @Test
sizeOfEmptyQueue()162     public void sizeOfEmptyQueue() {
163         assertEquals(0, mQueueUnderTest.size());
164         mQueueUnderTest = new LongArrayQueue(1000);
165         // capacity doesn't affect size.
166         assertEquals(0, mQueueUnderTest.size());
167     }
168 
169     @Test
sizeAfterOperations()170     public void sizeAfterOperations() {
171         final int added = 1200;
172         for (int i = 0; i < added; i++) {
173             mQueueUnderTest.addLast(i);
174         }
175         // each add increments the size by 1.
176         assertEquals(added, mQueueUnderTest.size());
177         mQueueUnderTest.peekLast();
178         mQueueUnderTest.peekFirst();
179         // peeks don't change the size.
180         assertEquals(added, mQueueUnderTest.size());
181         final int removed = 345;
182         for (int i = 0; i < removed; i++) {
183             mQueueUnderTest.removeFirst();
184         }
185         // each remove decrements the size by 1.
186         assertEquals(added - removed, mQueueUnderTest.size());
187         mQueueUnderTest.clear();
188         // clear reduces the size to 0.
189         assertEquals(0, mQueueUnderTest.size());
190     }
191 
192     @Test
getInvalidPositions()193     public void getInvalidPositions() {
194         try {
195             mQueueUnderTest.get(0);
196             fail("get(0) succeeded on an empty queue!");
197         } catch (IndexOutOfBoundsException e) {
198         }
199         int n = 520;
200         for (int i = 0; i < 2 * n; i++) {
201             mQueueUnderTest.addLast(i + 1);
202         }
203         for (int i = 0; i < n; i++) {
204             mQueueUnderTest.removeFirst();
205         }
206         try {
207             mQueueUnderTest.get(-3);
208             fail("get(-3) succeeded");
209         } catch (IndexOutOfBoundsException e) {
210         }
211         assertEquals(n, mQueueUnderTest.size());
212         try {
213             mQueueUnderTest.get(n);
214             fail("get(" + n + ") succeeded on a queue with " + n + " elements");
215         } catch (IndexOutOfBoundsException e) {
216         }
217         try {
218             mQueueUnderTest.get(n + 3);
219             fail("get(" + (n + 3) + ") succeeded on a queue with " + n + " elements");
220         } catch (IndexOutOfBoundsException e) {
221         }
222     }
223 
224     @Test
getValidPositions()225     public void getValidPositions() {
226         int added = 423;
227         int removed = 212;
228         for (int i = 0; i < added; i++) {
229             mQueueUnderTest.addLast(i);
230         }
231         for (int i = 0; i < removed; i++) {
232             mQueueUnderTest.removeFirst();
233         }
234         for (int i = 0; i < (added - removed); i++) {
235             assertEquals(removed + i, mQueueUnderTest.get(i));
236         }
237     }
238 }
239