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