1/* 2 * Copyright (c) 2006, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24/* 25 * @test 26 * @bug 5045582 27 * @summary binarySearch of Collections larger than 1<<30 28 * @author Martin Buchholz 29 */ 30 31import java.util.*; 32 33public class BigBinarySearch { 34 35 // Allows creation of very "big" collections without using too 36 // many real resources 37 static class SparseIntegerList 38 extends AbstractList<Integer> 39 implements RandomAccess 40 { 41 private Map<Integer,Integer> m = new HashMap<>(); 42 43 public Integer get(int i) { 44 if (i < 0) throw new IndexOutOfBoundsException(""+i); 45 Integer v = m.get(i); 46 return (v == null) ? Integer.valueOf(0) : v; 47 } 48 49 public int size() { 50 return Collections.max(m.keySet()) + 1; 51 } 52 53 public Integer set(int i, Integer v) { 54 if (i < 0) throw new IndexOutOfBoundsException(""+i); 55 Integer ret = get(i); 56 if (v == 0) 57 m.remove(i); 58 else 59 m.put(i, v); 60 return ret; 61 } 62 } 63 64 /** Checks that binarySearch finds an element where we got it. */ 65 private static void checkBinarySearch(List<Integer> l, int i) { 66 try { equal(i, Collections.binarySearch(l, l.get(i))); } 67 catch (Throwable t) { unexpected(t); } 68 } 69 70 /** Checks that binarySearch finds an element where we got it. */ 71 private static void checkBinarySearch(List<Integer> l, int i, 72 Comparator<Integer> comparator) { 73 try { equal(i, Collections.binarySearch(l, l.get(i), comparator)); } 74 catch (Throwable t) { unexpected(t); } 75 } 76 77 private static void realMain(String[] args) throws Throwable { 78 final int n = (1<<30) + 47; 79 80 System.out.println("binarySearch(List<Integer>, Integer)"); 81 List<Integer> big = new SparseIntegerList(); 82 big.set( 0, -44); 83 big.set( 1, -43); 84 big.set(n-2, 43); 85 big.set(n-1, 44); 86 int[] ints = { 0, 1, n-2, n-1 }; 87 Comparator<Integer> reverse = Collections.reverseOrder(); 88 Comparator<Integer> natural = Collections.reverseOrder(reverse); 89 90 for (int i : ints) { 91 checkBinarySearch(big, i); 92 checkBinarySearch(big, i, null); 93 checkBinarySearch(big, i, natural); 94 } 95 for (int i : ints) 96 big.set(i, - big.get(i)); 97 for (int i : ints) 98 checkBinarySearch(big, i, reverse); 99 } 100 101 //--------------------- Infrastructure --------------------------- 102 static volatile int passed = 0, failed = 0; 103 static void pass() {passed++;} 104 static void fail() {failed++; Thread.dumpStack();} 105 static void fail(String msg) {System.out.println(msg); fail();} 106 static void unexpected(Throwable t) {failed++; t.printStackTrace();} 107 static void check(boolean cond) {if (cond) pass(); else fail();} 108 static void equal(Object x, Object y) { 109 if (x == null ? y == null : x.equals(y)) pass(); 110 else fail(x + " not equal to " + y);} 111 public static void main(String[] args) throws Throwable { 112 try {realMain(args);} catch (Throwable t) {unexpected(t);} 113 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 114 if (failed > 0) throw new AssertionError("Some tests failed");} 115} 116