1/*
2 *  Licensed to the Apache Software Foundation (ASF) under one or more
3 *  contributor license agreements.  See the NOTICE file distributed with
4 *  this work for additional information regarding copyright ownership.
5 *  The ASF licenses this file to You under the Apache License, Version 2.0
6 *  (the "License"); you may not use this file except in compliance with
7 *  the License.  You may obtain a copy of the License at
8 *
9 *     http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *  Unless required by applicable law or agreed to in writing, software
12 *  distributed under the License is distributed on an "AS IS" BASIS,
13 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *  See the License for the specific language governing permissions and
15 *  limitations under the License.
16 */
17
18package org.apache.harmony.tests.java.util;
19
20import libcore.java.util.SpliteratorTester;
21
22import java.util.ArrayList;
23import java.util.Arrays;
24import java.util.Comparator;
25import java.util.HashSet;
26import java.util.Iterator;
27import java.util.LinkedHashSet;
28import java.util.List;
29import java.util.Set;
30import java.util.SortedSet;
31import java.util.Spliterator;
32import java.util.TreeSet;
33
34public class TreeSetTest extends junit.framework.TestCase {
35
36    public static class ReversedIntegerComparator implements Comparator {
37        public int compare(Object o1, Object o2) {
38            return -(((Integer) o1).compareTo((Integer) o2));
39        }
40
41        public boolean equals(Object o1, Object o2) {
42            return ((Integer) o1).compareTo((Integer) o2) == 0;
43        }
44    }
45
46    TreeSet ts;
47
48    Object objArray[] = new Object[1000];
49
50    /**
51     * java.util.TreeSet#TreeSet()
52     */
53    public void test_Constructor() {
54        // Test for method java.util.TreeSet()
55        assertTrue("Did not construct correct TreeSet", new TreeSet().isEmpty());
56    }
57
58    /**
59     * java.util.TreeSet#TreeSet(java.util.Collection)
60     */
61    public void test_ConstructorLjava_util_Collection() {
62        // Test for method java.util.TreeSet(java.util.Collection)
63        TreeSet myTreeSet = new TreeSet(Arrays.asList(objArray));
64        assertTrue("TreeSet incorrect size",
65                myTreeSet.size() == objArray.length);
66        for (int counter = 0; counter < objArray.length; counter++)
67            assertTrue("TreeSet does not contain correct elements", myTreeSet
68                    .contains(objArray[counter]));
69    }
70
71    /**
72     * java.util.TreeSet#TreeSet(java.util.Comparator)
73     */
74    public void test_ConstructorLjava_util_Comparator() {
75        // Test for method java.util.TreeSet(java.util.Comparator)
76        TreeSet myTreeSet = new TreeSet(new ReversedIntegerComparator());
77        assertTrue("Did not construct correct TreeSet", myTreeSet.isEmpty());
78        myTreeSet.add(new Integer(1));
79        myTreeSet.add(new Integer(2));
80        assertTrue(
81                "Answered incorrect first element--did not use custom comparator ",
82                myTreeSet.first().equals(new Integer(2)));
83        assertTrue(
84                "Answered incorrect last element--did not use custom comparator ",
85                myTreeSet.last().equals(new Integer(1)));
86    }
87
88    /**
89     * java.util.TreeSet#TreeSet(java.util.SortedSet)
90     */
91    public void test_ConstructorLjava_util_SortedSet() {
92        // Test for method java.util.TreeSet(java.util.SortedSet)
93        ReversedIntegerComparator comp = new ReversedIntegerComparator();
94        TreeSet myTreeSet = new TreeSet(comp);
95        for (int i = 0; i < objArray.length; i++)
96            myTreeSet.add(objArray[i]);
97        TreeSet anotherTreeSet = new TreeSet(myTreeSet);
98        assertTrue("TreeSet is not correct size",
99                anotherTreeSet.size() == objArray.length);
100        for (int counter = 0; counter < objArray.length; counter++)
101            assertTrue("TreeSet does not contain correct elements",
102                    anotherTreeSet.contains(objArray[counter]));
103        assertTrue("TreeSet does not answer correct comparator", anotherTreeSet
104                .comparator() == comp);
105        assertTrue("TreeSet does not use comparator",
106                anotherTreeSet.first() == objArray[objArray.length - 1]);
107    }
108
109    /**
110     * java.util.TreeSet#add(java.lang.Object)
111     */
112    public void test_addLjava_lang_Object() {
113        // Test for method boolean java.util.TreeSet.add(java.lang.Object)
114        ts.add(new Integer(-8));
115        assertTrue("Failed to add Object", ts.contains(new Integer(-8)));
116        ts.add(objArray[0]);
117        assertTrue("Added existing element", ts.size() == objArray.length + 1);
118
119    }
120
121    /**
122     * java.util.TreeSet#addAll(java.util.Collection)
123     */
124    public void test_addAllLjava_util_Collection() {
125        // Test for method boolean
126        // java.util.TreeSet.addAll(java.util.Collection)
127        TreeSet s = new TreeSet();
128        s.addAll(ts);
129        assertTrue("Incorrect size after add", s.size() == ts.size());
130        Iterator i = ts.iterator();
131        while (i.hasNext())
132            assertTrue("Returned incorrect set", s.contains(i.next()));
133
134    }
135
136    /**
137     * java.util.TreeSet#clear()
138     */
139    public void test_clear() {
140        // Test for method void java.util.TreeSet.clear()
141        ts.clear();
142        assertEquals("Returned non-zero size after clear", 0, ts.size());
143        assertTrue("Found element in cleared set", !ts.contains(objArray[0]));
144    }
145
146    /**
147     * java.util.TreeSet#clone()
148     */
149    public void test_clone() {
150        // Test for method java.lang.Object java.util.TreeSet.clone()
151        TreeSet s = (TreeSet) ts.clone();
152        Iterator i = ts.iterator();
153        while (i.hasNext())
154            assertTrue("Clone failed to copy all elements", s
155                    .contains(i.next()));
156    }
157
158    /**
159     * java.util.TreeSet#comparator()
160     */
161    public void test_comparator() {
162        // Test for method java.util.Comparator java.util.TreeSet.comparator()
163        ReversedIntegerComparator comp = new ReversedIntegerComparator();
164        TreeSet myTreeSet = new TreeSet(comp);
165        assertTrue("Answered incorrect comparator",
166                myTreeSet.comparator() == comp);
167    }
168
169    /**
170     * java.util.TreeSet#contains(java.lang.Object)
171     */
172    public void test_containsLjava_lang_Object() {
173        // Test for method boolean java.util.TreeSet.contains(java.lang.Object)
174        assertTrue("Returned false for valid Object", ts
175                .contains(objArray[objArray.length / 2]));
176        assertTrue("Returned true for invalid Object", !ts
177                .contains(new Integer(-9)));
178        try {
179            ts.contains(new Object());
180        } catch (ClassCastException e) {
181            // Correct
182            return;
183        }
184        fail("Failed to throw exception when passed invalid element");
185
186    }
187
188    /**
189     * java.util.TreeSet#first()
190     */
191    public void test_first() {
192        // Test for method java.lang.Object java.util.TreeSet.first()
193        assertTrue("Returned incorrect first element",
194                ts.first() == objArray[0]);
195    }
196
197    /**
198     * java.util.TreeSet#headSet(java.lang.Object)
199     */
200    public void test_headSetLjava_lang_Object() {
201        // Test for method java.util.SortedSet
202        // java.util.TreeSet.headSet(java.lang.Object)
203        Set s = ts.headSet(new Integer(100));
204        assertEquals("Returned set of incorrect size", 100, s.size());
205        for (int i = 0; i < 100; i++)
206            assertTrue("Returned incorrect set", s.contains(objArray[i]));
207    }
208
209    /**
210     * java.util.TreeSet#isEmpty()
211     */
212    public void test_isEmpty() {
213        // Test for method boolean java.util.TreeSet.isEmpty()
214        assertTrue("Empty set returned false", new TreeSet().isEmpty());
215        assertTrue("Non-Empty returned true", !ts.isEmpty());
216    }
217
218    /**
219     * java.util.TreeSet#iterator()
220     */
221    public void test_iterator() {
222        // Test for method java.util.Iterator java.util.TreeSet.iterator()
223        TreeSet s = new TreeSet();
224        s.addAll(ts);
225        Iterator i = ts.iterator();
226        Set as = new HashSet(Arrays.asList(objArray));
227        while (i.hasNext())
228            as.remove(i.next());
229        assertEquals("Returned incorrect iterator", 0, as.size());
230
231    }
232
233    /**
234     * java.util.TreeSet#last()
235     */
236    public void test_last() {
237        // Test for method java.lang.Object java.util.TreeSet.last()
238        assertTrue("Returned incorrect last element",
239                ts.last() == objArray[objArray.length - 1]);
240    }
241
242    /**
243     * java.util.TreeSet#remove(java.lang.Object)
244     */
245    public void test_removeLjava_lang_Object() {
246        // Test for method boolean java.util.TreeSet.remove(java.lang.Object)
247        ts.remove(objArray[0]);
248        assertTrue("Failed to remove object", !ts.contains(objArray[0]));
249        assertTrue("Failed to change size after remove",
250                ts.size() == objArray.length - 1);
251        try {
252            ts.remove(new Object());
253        } catch (ClassCastException e) {
254            // Correct
255            return;
256        }
257        fail("Failed to throw exception when past uncomparable value");
258    }
259
260    /**
261     * java.util.TreeSet#size()
262     */
263    public void test_size() {
264        // Test for method int java.util.TreeSet.size()
265        assertTrue("Returned incorrect size", ts.size() == objArray.length);
266    }
267
268    /**
269     * java.util.TreeSet#subSet(java.lang.Object, java.lang.Object)
270     */
271    public void test_subSetLjava_lang_ObjectLjava_lang_Object() {
272        // Test for method java.util.SortedSet
273        // java.util.TreeSet.subSet(java.lang.Object, java.lang.Object)
274        final int startPos = objArray.length / 4;
275        final int endPos = 3 * objArray.length / 4;
276        SortedSet aSubSet = ts.subSet(objArray[startPos], objArray[endPos]);
277        assertTrue("Subset has wrong number of elements",
278                aSubSet.size() == (endPos - startPos));
279        for (int counter = startPos; counter < endPos; counter++)
280            assertTrue("Subset does not contain all the elements it should",
281                    aSubSet.contains(objArray[counter]));
282
283        int result;
284        try {
285            ts.subSet(objArray[3], objArray[0]);
286            result = 0;
287        } catch (IllegalArgumentException e) {
288            result = 1;
289        }
290        assertEquals("end less than start should throw", 1, result);
291    }
292
293    /**
294     * java.util.TreeSet#tailSet(java.lang.Object)
295     */
296    public void test_tailSetLjava_lang_Object() {
297        // Test for method java.util.SortedSet
298        // java.util.TreeSet.tailSet(java.lang.Object)
299        Set s = ts.tailSet(new Integer(900));
300        assertEquals("Returned set of incorrect size", 100, s.size());
301        for (int i = 900; i < objArray.length; i++)
302            assertTrue("Returned incorrect set", s.contains(objArray[i]));
303    }
304
305    /**
306     * Tests equals() method.
307     * Tests that no ClassCastException will be thrown in all cases.
308     * Regression test for HARMONY-1639.
309     */
310    public void test_equals() throws Exception {
311        // comparing TreeSets with different object types
312        Set s1 = new TreeSet();
313        Set s2 = new TreeSet();
314        s1.add("key1");
315        s1.add("key2");
316        s2.add(new Integer(1));
317        s2.add(new Integer(2));
318        assertFalse("Sets should not be equal 1", s1.equals(s2));
319        assertFalse("Sets should not be equal 2", s2.equals(s1));
320
321        // comparing TreeSet with HashSet
322        s1 = new TreeSet();
323        s2 = new HashSet();
324        s1.add("key");
325        s2.add(new Object());
326        assertFalse("Sets should not be equal 3", s1.equals(s2));
327        assertFalse("Sets should not be equal 4", s2.equals(s1));
328    }
329
330    public void test_spliterator() throws Exception {
331        TreeSet<String> treeSet = new TreeSet<>();
332        List<String> keys = Arrays.asList(
333                "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p");
334        treeSet.addAll(keys);
335
336        ArrayList<String> expectedKeys = new ArrayList<>(keys);
337        SpliteratorTester.runBasicIterationTests_unordered(treeSet.spliterator(), expectedKeys,
338                String::compareTo);
339        SpliteratorTester.runBasicSplitTests(treeSet, expectedKeys);
340        SpliteratorTester.testSpliteratorNPE(treeSet.spliterator());
341
342        assertTrue(treeSet.spliterator().hasCharacteristics(Spliterator.ORDERED));
343        SpliteratorTester.runOrderedTests(keys);
344
345        assertTrue(treeSet.spliterator().hasCharacteristics(Spliterator.DISTINCT));
346        SpliteratorTester.runDistinctTests(keys);
347    }
348
349    /**
350     * Sets up the fixture, for example, open a network connection. This method
351     * is called before a test is executed.
352     */
353    protected void setUp() {
354        ts = new TreeSet();
355        for (int i = 0; i < objArray.length; i++) {
356            Object x = objArray[i] = new Integer(i);
357            ts.add(x);
358        }
359    }
360
361    /**
362     * Tears down the fixture, for example, close a network connection. This
363     * method is called after a test is executed.
364     */
365    protected void tearDown() {
366    }
367}
368