1 package org.djutils.immutablecollections;
2
3 import static org.junit.Assert.assertEquals;
4 import static org.junit.Assert.assertFalse;
5 import static org.junit.Assert.assertNull;
6 import static org.junit.Assert.assertTrue;
7 import static org.junit.Assert.fail;
8
9 import java.util.Arrays;
10 import java.util.Comparator;
11 import java.util.List;
12 import java.util.NavigableSet;
13 import java.util.NoSuchElementException;
14 import java.util.Set;
15 import java.util.TreeSet;
16
17 import org.junit.Assert;
18 import org.junit.Test;
19
20
21
22
23
24
25
26
27
28
29
30 public class TestImmutableTreeSet
31 {
32
33
34
35
36 @Test
37 public final void testTreeSet()
38 {
39 Set<Integer> intSet = new TreeSet<>(Arrays.asList(new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}));
40 NavigableSet<Integer> sortedSet = new TreeSet<Integer>(intSet);
41 testIntSet(sortedSet, new ImmutableTreeSet<Integer>(sortedSet, Immutable.WRAP), Immutable.WRAP);
42 sortedSet = new TreeSet<Integer>(intSet);
43 testIntSet(sortedSet, new ImmutableTreeSet<Integer>(sortedSet, Immutable.COPY), Immutable.COPY);
44 sortedSet = new TreeSet<Integer>(intSet);
45 testIntSet(sortedSet, new ImmutableTreeSet<Integer>(sortedSet), Immutable.COPY);
46 sortedSet = new TreeSet<Integer>(intSet);
47 ImmutableTreeSet<Integer> ihs = new ImmutableTreeSet<Integer>(sortedSet);
48 testIntSet(sortedSet, new ImmutableTreeSet<Integer>(ihs), Immutable.COPY);
49
50 sortedSet = new TreeSet<Integer>(intSet);
51 List<Integer> il = Arrays.asList(new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
52 testIntSet(sortedSet, new ImmutableTreeSet<Integer>(il), Immutable.COPY);
53 ImmutableTreeSet<Integer> its = new ImmutableTreeSet<Integer>(sortedSet);
54 Assert.assertTrue("toString returns something descriptive", its.toString().startsWith("ImmutableTreeSet ["));
55
56 ImmutableTreeSet<Integer> wrapped = new ImmutableTreeSet<Integer>(its, Immutable.WRAP);
57 Assert.assertEquals("wrapped is equal wrapped-wrapped", its, wrapped);
58 ImmutableTreeSet<Integer> copied = new ImmutableTreeSet<Integer>(its, Immutable.COPY);
59 Assert.assertEquals("wrapped is equal to copy-wrapped", its, copied);
60 Assert.assertEquals("copy-wrapped is equal to wrapped", copied, its);
61 }
62
63
64
65
66
67
68
69 private void testIntSet(final NavigableSet<Integer> set, final ImmutableTreeSet<Integer> imSet, final Immutable copyOrWrap)
70 {
71 Assert.assertTrue(set.size() == 10);
72 Assert.assertTrue(imSet.size() == 10);
73 for (int i = 0; i < 10; i++)
74 {
75 Assert.assertTrue(imSet.contains(i + 1));
76 }
77 Assert.assertFalse(imSet.isEmpty());
78 Assert.assertFalse(imSet.contains(15));
79
80 Assert.assertTrue(imSet.first() == 1);
81 Assert.assertTrue(imSet.last() == 10);
82
83 if (copyOrWrap == Immutable.COPY)
84 {
85 Assert.assertTrue(imSet.isCopy());
86 Assert.assertTrue(imSet.toSet().equals(set));
87 Assert.assertFalse(imSet.toSet() == set);
88 }
89 else
90 {
91 Assert.assertTrue(imSet.isWrap());
92 Assert.assertTrue(imSet.toSet().equals(set));
93 Assert.assertFalse(imSet.toSet() == set);
94 }
95
96 Set<Integer> to = imSet.toSet();
97 Assert.assertTrue(set.equals(to));
98
99 Integer[] arr = imSet.toArray(new Integer[] {});
100 Integer[] sar = set.toArray(new Integer[] {});
101 Assert.assertArrayEquals(arr, sar);
102
103
104 set.add(11);
105 if (copyOrWrap == Immutable.COPY)
106 {
107 Assert.assertTrue(imSet.size() == 10);
108 }
109 else
110 {
111 Assert.assertTrue(imSet.size() == 11);
112 }
113 }
114
115
116
117
118 @Test
119 public void testComparator()
120 {
121 Integer[] values = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
122 Set<Integer> intSet = new TreeSet<>(Arrays.asList(values));
123 NavigableSet<Integer> sortedSet = new TreeSet<Integer>(intSet);
124 assertNull("Sorted set uses default compare; not an explicit comparator", sortedSet.comparator());
125 Comparator<Integer> reverseIntegerComparator = new Comparator<Integer>()
126 {
127 @Override
128 public int compare(final Integer o1, final Integer o2)
129 {
130 return -Integer.compare(o1, o2);
131 }
132
133 @Override
134 public String toString()
135 {
136 return "Reversing comparator";
137 }
138 };
139 sortedSet = new TreeSet<Integer>(reverseIntegerComparator);
140 sortedSet.addAll(intSet);
141 ImmutableTreeSet<Integer> its = new ImmutableTreeSet<>(sortedSet, Immutable.WRAP);
142 assertEquals("custom comparator is returned", reverseIntegerComparator, its.comparator());
143
144 assertEquals("size must match", values.length, its.size());
145 Integer prev = null;
146 for (Integer value : its)
147 {
148
149 if (prev != null)
150 {
151 assertTrue("Values must be in non-increasing order", value <= prev);
152 }
153 prev = value;
154 }
155 ImmutableSortedSet<Integer> subSet = its.subSet(7, 3);
156 prev = null;
157 boolean seen3 = false;
158 boolean seen7 = false;
159 for (Integer value : subSet)
160 {
161
162 assertTrue("value must be in range", value <= 7 && value >= 3);
163 if (3 == value)
164 {
165 seen3 = true;
166 }
167 if (7 == value)
168 {
169 seen7 = true;
170 }
171 if (prev != null)
172 {
173 assertTrue("Values are in decreasing order", value <= prev);
174 }
175 prev = value;
176 }
177 assertFalse("3 must not have been returned", seen3);
178 assertTrue("7 must have been returned", seen7);
179
180 subSet = its.subSet(7, false, 3, false);
181 prev = null;
182 seen3 = false;
183 seen7 = false;
184 for (Integer value : subSet)
185 {
186
187 assertTrue("value must be in range", value <= 7 && value >= 3);
188 if (3 == value)
189 {
190 seen3 = true;
191 }
192 if (7 == value)
193 {
194 seen7 = true;
195 }
196 if (prev != null)
197 {
198 assertTrue("Values are in decreasing order", value <= prev);
199 }
200 prev = value;
201 }
202 assertFalse("3 must not have been returned", seen3);
203 assertFalse("7 must not have been returned", seen7);
204
205 subSet = its.subSet(7, true, 3, false);
206 prev = null;
207 seen3 = false;
208 seen7 = false;
209 for (Integer value : subSet)
210 {
211
212 assertTrue("value must be in range", value <= 7 && value >= 3);
213 if (3 == value)
214 {
215 seen3 = true;
216 }
217 if (7 == value)
218 {
219 seen7 = true;
220 }
221 if (prev != null)
222 {
223 assertTrue("Values are in decreasing order", value <= prev);
224 }
225 prev = value;
226 }
227 assertFalse("3 must not have been returned", seen3);
228 assertTrue("7 must have been returned", seen7);
229
230 subSet = its.subSet(7, false, 3, true);
231 prev = null;
232 seen3 = false;
233 seen7 = false;
234 for (Integer value : subSet)
235 {
236
237 assertTrue("value must be in range", value <= 7 && value >= 3);
238 if (3 == value)
239 {
240 seen3 = true;
241 }
242 if (7 == value)
243 {
244 seen7 = true;
245 }
246 if (prev != null)
247 {
248 assertTrue("Values are in decreasing order", value <= prev);
249 }
250 prev = value;
251 }
252 assertTrue("3 must have been returned", seen3);
253 assertFalse("7 must not have been returned", seen7);
254
255 subSet = its.subSet(7, true, 3, true);
256 prev = null;
257 seen3 = false;
258 seen7 = false;
259 for (Integer value : subSet)
260 {
261
262 assertTrue("value must be in range", value <= 7 && value >= 3);
263 if (3 == value)
264 {
265 seen3 = true;
266 }
267 if (7 == value)
268 {
269 seen7 = true;
270 }
271 if (prev != null)
272 {
273 assertTrue("Values are in decreasing order", value <= prev);
274 }
275 prev = value;
276 }
277 assertTrue("3 must have been returned", seen3);
278 assertTrue("7 must have been returned", seen7);
279
280 ImmutableSortedSet<Integer> headSet = its.headSet(7);
281 prev = null;
282 seen7 = false;
283 for (Integer value : headSet)
284 {
285 assertTrue("value must be in range", value >= 7);
286 if (7 == value)
287 {
288 seen7 = true;
289 }
290 if (prev != null)
291 {
292 assertTrue("Values are in decreasing order", value <= prev);
293 }
294 prev = value;
295 }
296 assertFalse("7 must not have been returned", seen7);
297
298 headSet = its.headSet(7, true);
299 prev = null;
300 seen7 = false;
301 for (Integer value : headSet)
302 {
303 assertTrue("value must be in range", value >= 7);
304 if (7 == value)
305 {
306 seen7 = true;
307 }
308 if (prev != null)
309 {
310 assertTrue("Values are in decreasing order", value <= prev);
311 }
312 prev = value;
313 }
314 assertTrue("7 must have been returned", seen7);
315
316 headSet = its.headSet(7, false);
317 prev = null;
318 seen7 = false;
319 for (Integer value : headSet)
320 {
321 assertTrue("value must be in range", value >= 7);
322 if (7 == value)
323 {
324 seen7 = true;
325 }
326 if (prev != null)
327 {
328 assertTrue("Values are in decreasing order", value <= prev);
329 }
330 prev = value;
331 }
332 assertFalse("7 must not have been returned", seen7);
333
334 ImmutableSortedSet<Integer> tailSet = its.tailSet(3);
335 prev = null;
336 seen3 = false;
337 for (Integer value : tailSet)
338 {
339 assertTrue("value must be in range", value <= 3);
340 if (3 == value)
341 {
342 seen3 = true;
343 }
344 if (prev != null)
345 {
346 assertTrue("Values are in decreasing order", value <= prev);
347 }
348 prev = value;
349 }
350 assertTrue("3 must have been returned", seen3);
351
352 tailSet = its.tailSet(3, true);
353 prev = null;
354 seen3 = false;
355 for (Integer value : tailSet)
356 {
357 assertTrue("value must be in range", value <= 3);
358 if (3 == value)
359 {
360 seen3 = true;
361 }
362 if (prev != null)
363 {
364 assertTrue("Values are in decreasing order", value <= prev);
365 }
366 prev = value;
367 }
368 assertTrue("3 must have been returned", seen3);
369
370 tailSet = its.tailSet(3, false);
371 prev = null;
372 seen3 = false;
373 for (Integer value : tailSet)
374 {
375 assertTrue("value must be in range", value <= 3);
376 if (3 == value)
377 {
378 seen3 = true;
379 }
380 if (prev != null)
381 {
382 assertTrue("Values are in decreasing order", value <= prev);
383 }
384 prev = value;
385 }
386 assertFalse("3 must not have been returned", seen3);
387
388 for (int index = 0; index < values.length; index++)
389 {
390 Integer lower = its.lower(values[index]);
391 if (index == values.length - 1)
392 {
393 assertNull("lower of last element should have returned null", lower);
394 }
395 else
396 {
397 assertEquals("lower should have returned next higher value", values[index + 1], lower);
398 }
399 Integer higher = its.higher(values[index]);
400 if (index == 0)
401 {
402 assertNull("higher should have returned null", higher);
403 }
404 else
405 {
406 assertEquals("higher should have returned next lower value", values[index - 1], higher);
407 }
408 Integer floor = its.floor(values[index]);
409 assertEquals("floor of element in set returns that element", values[index], floor);
410 Integer ceil = its.floor(values[index]);
411 assertEquals("ceil of element in set returns that element", values[index], ceil);
412 }
413 assertNull("floor of value higher than any in set returns null", its.floor(11));
414 assertNull("ceil of value lower than any in set returns null", its.ceiling(0));
415 assertEquals("floor of value lower than any in set is lowest in set", 1, its.floor(0), 0);
416 assertEquals("ceiling of value higher than any in set is highest in set", 10, its.ceiling(11), 0);
417 ImmutableSet<Integer> descendingSet = its.descendingSet();
418 assertEquals("descendingSet has correct size", values.length, descendingSet.size());
419 prev = null;
420 for (Integer value : descendingSet)
421 {
422 if (null != prev)
423 {
424 assertTrue("descendingSet has value in ascending order", value >= prev);
425 }
426 prev = value;
427 }
428 ImmutableIterator<Integer> ii = its.descendingIterator();
429 prev = null;
430 while (ii.hasNext())
431 {
432 Integer next = ii.next();
433 if (null != prev)
434 {
435 assertTrue("descendingSet has value in ascending order", next >= prev);
436 }
437 prev = next;
438 }
439 try
440 {
441 ii.next();
442 fail("next should have thrown an Exception");
443 }
444 catch (NoSuchElementException nsee)
445 {
446
447 }
448 }
449
450 }