1/* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements.  See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License.  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
17package libcore.java.util;
18
19import java.util.Arrays;
20import java.util.Comparator;
21import java.util.List;
22import java.util.PriorityQueue;
23import junit.framework.TestCase;
24import libcore.libcore.util.SerializationTester;
25
26public class OldPriorityQueueTest extends TestCase {
27    public void test_ConstructorI() {
28        PriorityQueue<Object> queue = new PriorityQueue<Object>(100);
29        assertNotNull(queue);
30        assertEquals(0, queue.size());
31        assertNull(queue.comparator());
32
33        try {
34            new PriorityQueue(0);
35            fail("IllegalArgumentException expected");
36        } catch (IllegalArgumentException e) {
37            //expected
38        }
39    }
40
41    public void test_remove_Ljava_lang_Object_using_comparator() {
42        PriorityQueue<String> queue = new PriorityQueue<String>(10,
43                new MockComparatorStringByLength());
44        String[] array = { "AAAAA", "AA", "AAAA", "AAAAAAAA" };
45        for (int i = 0; i < array.length; i++) {
46            queue.offer(array[i]);
47        }
48        assertFalse(queue.contains("BB"));
49        // Even though "BB" is equivalent to "AA" using the string length comparator, remove()
50        // uses equals(), so only "AA" succeeds in removing element "AA".
51        assertFalse(queue.remove("BB"));
52        assertTrue(queue.remove("AA"));
53    }
54
55    @SuppressWarnings("CollectionIncompatibleType")
56    public void test_remove_Ljava_lang_Object_not_exists() {
57        Integer[] array = { 2, 45, 7, -12, 9, 23, 17, 1118, 10, 16, 39 };
58        List<Integer> list = Arrays.asList(array);
59        PriorityQueue<Integer> integerQueue = new PriorityQueue<Integer>(list);
60        assertFalse(integerQueue.remove(111));
61        assertFalse(integerQueue.remove(null));
62        assertFalse(integerQueue.remove(""));
63    }
64
65    public void test_Serialization() throws Exception {
66        String s = "aced0005737200176a6176612e7574696c2e5072696f72697479517565756594"
67                + "da30b4fb3f82b103000249000473697a654c000a636f6d70617261746f7274001"
68                + "64c6a6176612f7574696c2f436f6d70617261746f723b78700000000b70770400"
69                + "00000c737200116a6176612e6c616e672e496e746567657212e2a0a4f78187380"
70                + "2000149000576616c7565787200106a6176612e6c616e672e4e756d62657286ac"
71                + "951d0b94e08b0200007870fffffff47371007e0003000000027371007e0003000"
72                + "000077371007e00030000000a7371007e0003000000097371007e000300000017"
73                + "7371007e0003000000117371007e00030000045e7371007e00030000002d73710"
74                + "07e0003000000107371007e00030000002778";
75        PriorityQueue<Integer> srcIntegerQueue = new PriorityQueue<Integer>(
76                Arrays.asList(2, 45, 7, -12, 9, 23, 17, 1118, 10, 16, 39));
77        new SerializationTester<PriorityQueue<Integer>>(srcIntegerQueue, s) {
78            @Override protected boolean equals(PriorityQueue<Integer> a, PriorityQueue<Integer> b) {
79                return Arrays.equals(a.toArray(), b.toArray());
80            }
81        }.test();
82    }
83
84    private static class MockComparatorStringByLength implements
85            Comparator<String> {
86
87        public int compare(String object1, String object2) {
88            int length1 = object1.length();
89            int length2 = object2.length();
90            if (length1 > length2) {
91                return 1;
92            } else if (length1 == length2) {
93                return 0;
94            } else {
95                return -1;
96            }
97        }
98
99    }
100
101    private static class MockComparatorCast<E> implements Comparator<E> {
102
103        public int compare(E object1, E object2) {
104            return 0;
105        }
106    }
107
108    /**
109     * removeAt(.) must sometimes perform siftUp(.).
110     */
111    public void test_removeAt_siftUp() {
112        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
113        // Adding a valid heap will keep elements in the same order
114        for (int i : new int[] { 0, 3, 1, 4, 5, 6, 2 }) {
115            q.add(i);
116        }
117        q.remove(4);  // 2 replaces 4 but parent is 3, siftUp(.) is needed
118        for (int i : new int[] { 0, 1, 2, 3, 5, 6 }) {
119            assertEquals(i, (int) q.poll());
120        }
121        assertNull(q.poll());
122    }
123
124}
125