1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.commons.collections4.list;
18
19 import static org.junit.jupiter.api.Assertions.assertEquals;
20 import static org.junit.jupiter.api.Assertions.assertFalse;
21 import static org.junit.jupiter.api.Assertions.assertNull;
22
23 import java.util.ArrayList;
24 import java.util.List;
25 import java.util.ListIterator;
26
27 import org.junit.jupiter.api.Test;
28
29
30
31
32 public class TreeListTest<E> extends AbstractListTest<E> {
33
34 public static void benchmark(final List<? super Integer> l) {
35 long startMillis = System.currentTimeMillis();
36 for (int i = 0; i < 100000; i++) {
37 l.add(Integer.valueOf(i));
38 }
39 System.out.print(System.currentTimeMillis() - startMillis + ";");
40
41 startMillis = System.currentTimeMillis();
42 for (int i = 0; i < 200; i++) {
43 l.toArray();
44 }
45 System.out.print(System.currentTimeMillis() - startMillis + ";");
46
47 startMillis = System.currentTimeMillis();
48 for (int i = 0; i < 100; i++) {
49 final java.util.Iterator<? super Integer> it = l.iterator();
50 while (it.hasNext()) {
51 it.next();
52 }
53 }
54 System.out.print(System.currentTimeMillis() - startMillis + ";");
55
56 startMillis = System.currentTimeMillis();
57 for (int i = 0; i < 10000; i++) {
58 final int j = (int) (Math.random() * 100000);
59 l.add(j, Integer.valueOf(-j));
60 }
61 System.out.print(System.currentTimeMillis() - startMillis + ";");
62
63 startMillis = System.currentTimeMillis();
64 for (int i = 0; i < 50000; i++) {
65 final int j = (int) (Math.random() * 110000);
66 l.get(j);
67 }
68 System.out.print(System.currentTimeMillis() - startMillis + ";");
69
70 startMillis = System.currentTimeMillis();
71 for (int i = 0; i < 200; i++) {
72 final int j = (int) (Math.random() * 100000);
73 l.indexOf(Integer.valueOf(j));
74 }
75 System.out.print(System.currentTimeMillis() - startMillis + ";");
76
77 startMillis = System.currentTimeMillis();
78 for (int i = 0; i < 10000; i++) {
79 final int j = (int) (Math.random() * 100000);
80 l.remove(j);
81 }
82 System.out.print(System.currentTimeMillis() - startMillis + ";");
83 }
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98 public TreeListTest() {
99 super(TreeListTest.class.getSimpleName());
100 }
101
102 @Override
103 public TreeList<E> makeObject() {
104 return new TreeList<>();
105 }
106
107 @Test
108 @SuppressWarnings("unchecked")
109 public void testAddMultiple() {
110 final List<E> l = makeObject();
111 l.add((E) "hugo");
112 l.add((E) "erna");
113 l.add((E) "daniel");
114 l.add((E) "andres");
115 l.add((E) "harald");
116 l.add(0, null);
117 assertNull(l.get(0));
118 assertEquals("hugo", l.get(1));
119 assertEquals("erna", l.get(2));
120 assertEquals("daniel", l.get(3));
121 assertEquals("andres", l.get(4));
122 assertEquals("harald", l.get(5));
123 }
124
125 @Test
126 public void testBug35258() {
127 final Object objectToRemove = Integer.valueOf(3);
128
129 final List<Integer> treelist = new TreeList<>();
130 treelist.add(Integer.valueOf(0));
131 treelist.add(Integer.valueOf(1));
132 treelist.add(Integer.valueOf(2));
133 treelist.add(Integer.valueOf(3));
134 treelist.add(Integer.valueOf(4));
135
136
137 treelist.remove(objectToRemove);
138
139 final ListIterator<Integer> li = treelist.listIterator();
140 assertEquals(Integer.valueOf(0), li.next());
141 assertEquals(Integer.valueOf(0), li.previous());
142 assertEquals(Integer.valueOf(0), li.next());
143 assertEquals(Integer.valueOf(1), li.next());
144
145 assertEquals(Integer.valueOf(1), li.previous());
146 assertEquals(Integer.valueOf(1), li.next());
147 assertEquals(Integer.valueOf(2), li.next());
148 assertEquals(Integer.valueOf(2), li.previous());
149 assertEquals(Integer.valueOf(2), li.next());
150 assertEquals(Integer.valueOf(4), li.next());
151 assertEquals(Integer.valueOf(4), li.previous());
152 assertEquals(Integer.valueOf(4), li.next());
153 assertFalse(li.hasNext());
154 }
155
156 @Test
157 public void testBugCollections447() {
158 final List<String> treeList = new TreeList<>();
159 treeList.add("A");
160 treeList.add("B");
161 treeList.add("C");
162 treeList.add("D");
163
164 final ListIterator<String> li = treeList.listIterator();
165 assertEquals("A", li.next());
166 assertEquals("B", li.next());
167
168 assertEquals("B", li.previous());
169
170 li.remove();
171
172
173
174 assertEquals("A", li.previous());
175 }
176
177 @Test
178 @SuppressWarnings("unchecked")
179 public void testIndexOf() {
180 final List<E> l = makeObject();
181 l.add((E) "0");
182 l.add((E) "1");
183 l.add((E) "2");
184 l.add((E) "3");
185 l.add((E) "4");
186 l.add((E) "5");
187 l.add((E) "6");
188 assertEquals(0, l.indexOf("0"));
189 assertEquals(1, l.indexOf("1"));
190 assertEquals(2, l.indexOf("2"));
191 assertEquals(3, l.indexOf("3"));
192 assertEquals(4, l.indexOf("4"));
193 assertEquals(5, l.indexOf("5"));
194 assertEquals(6, l.indexOf("6"));
195
196 l.set(1, (E) "0");
197 assertEquals(0, l.indexOf("0"));
198
199 l.set(3, (E) "3");
200 assertEquals(3, l.indexOf("3"));
201 l.set(2, (E) "3");
202 assertEquals(2, l.indexOf("3"));
203 l.set(1, (E) "3");
204 assertEquals(1, l.indexOf("3"));
205 l.set(0, (E) "3");
206 assertEquals(0, l.indexOf("3"));
207 }
208
209
210
211
212
213
214
215
216
217
218
219 @Test
220 @SuppressWarnings("unchecked")
221 public void testInsertBefore() {
222 final List<E> l = makeObject();
223 l.add((E) "erna");
224 l.add(0, (E) "hugo");
225 assertEquals("hugo", l.get(0));
226 assertEquals("erna", l.get(1));
227 }
228
229 @Test
230 @SuppressWarnings("boxing")
231 public void testIterationOrder() {
232
233
234
235
236 for (int size = 1; size < 1000; size++) {
237 final List<Integer> other = new ArrayList<>(size);
238 for (int i = 0; i < size; i++) {
239 other.add(i);
240 }
241 final TreeList<Integer> l = new TreeList<>(other);
242 final ListIterator<Integer> it = l.listIterator();
243 int i = 0;
244 while (it.hasNext()) {
245 final Integer val = it.next();
246 assertEquals(i++, val.intValue());
247 }
248
249 while (it.hasPrevious()) {
250 final Integer val = it.previous();
251 assertEquals(--i, val.intValue());
252 }
253 }
254 }
255
256 @Test
257 @SuppressWarnings("boxing")
258 public void testIterationOrderAfterAddAll() {
259
260
261
262
263
264
265
266 final int size = 1000;
267 for (int i = 0; i < 100; i++) {
268 final List<Integer> other = new ArrayList<>(size);
269 for (int j = i; j < size; j++) {
270 other.add(j);
271 }
272 final TreeList<Integer> l = new TreeList<>();
273 for (int j = 0; j < i; j++) {
274 l.add(j);
275 }
276
277 l.addAll(other);
278
279 final ListIterator<Integer> it = l.listIterator();
280 int cnt = 0;
281 while (it.hasNext()) {
282 final Integer val = it.next();
283 assertEquals(cnt++, val.intValue());
284 }
285
286 while (it.hasPrevious()) {
287 final Integer val = it.previous();
288 assertEquals(--cnt, val.intValue());
289 }
290 }
291 }
292
293 @Test
294 @SuppressWarnings("unchecked")
295 public void testRemove() {
296 final List<E> l = makeObject();
297 l.add((E) "hugo");
298 l.add((E) "erna");
299 l.add((E) "daniel");
300 l.add((E) "andres");
301 l.add((E) "harald");
302 l.add(0, null);
303 int i = 0;
304 assertNull(l.get(i++));
305 assertEquals("hugo", l.get(i++));
306 assertEquals("erna", l.get(i++));
307 assertEquals("daniel", l.get(i++));
308 assertEquals("andres", l.get(i++));
309 assertEquals("harald", l.get(i++));
310
311 l.remove(0);
312 i = 0;
313 assertEquals("hugo", l.get(i++));
314 assertEquals("erna", l.get(i++));
315 assertEquals("daniel", l.get(i++));
316 assertEquals("andres", l.get(i++));
317 assertEquals("harald", l.get(i++));
318
319 i = 0;
320 l.remove(1);
321 assertEquals("hugo", l.get(i++));
322 assertEquals("daniel", l.get(i++));
323 assertEquals("andres", l.get(i++));
324 assertEquals("harald", l.get(i++));
325
326 i = 0;
327 l.remove(2);
328 assertEquals("hugo", l.get(i++));
329 assertEquals("daniel", l.get(i++));
330 assertEquals("harald", l.get(i++));
331 }
332
333 }