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 31 package test.java.util.Collections; 32 33 import java.util.AbstractList; 34 import java.util.Collections; 35 import java.util.Comparator; 36 import java.util.HashMap; 37 import java.util.List; 38 import java.util.Map; 39 import java.util.RandomAccess; 40 41 public class BigBinarySearch { 42 43 // Allows creation of very "big" collections without using too 44 // many real resources 45 static class SparseIntegerList 46 extends AbstractList<Integer> 47 implements RandomAccess 48 { 49 private Map<Integer,Integer> m = new HashMap<>(); 50 get(int i)51 public Integer get(int i) { 52 if (i < 0) throw new IndexOutOfBoundsException(""+i); 53 Integer v = m.get(i); 54 return (v == null) ? Integer.valueOf(0) : v; 55 } 56 size()57 public int size() { 58 return Collections.max(m.keySet()) + 1; 59 } 60 set(int i, Integer v)61 public Integer set(int i, Integer v) { 62 if (i < 0) throw new IndexOutOfBoundsException(""+i); 63 Integer ret = get(i); 64 if (v == 0) 65 m.remove(i); 66 else 67 m.put(i, v); 68 return ret; 69 } 70 } 71 72 /** Checks that binarySearch finds an element where we got it. */ checkBinarySearch(List<Integer> l, int i)73 private static void checkBinarySearch(List<Integer> l, int i) { 74 try { equal(i, Collections.binarySearch(l, l.get(i))); } 75 catch (Throwable t) { unexpected(t); } 76 } 77 78 /** Checks that binarySearch finds an element where we got it. */ checkBinarySearch(List<Integer> l, int i, Comparator<Integer> comparator)79 private static void checkBinarySearch(List<Integer> l, int i, 80 Comparator<Integer> comparator) { 81 try { equal(i, Collections.binarySearch(l, l.get(i), comparator)); } 82 catch (Throwable t) { unexpected(t); } 83 } 84 realMain(String[] args)85 private static void realMain(String[] args) throws Throwable { 86 final int n = (1<<30) + 47; 87 88 System.out.println("binarySearch(List<Integer>, Integer)"); 89 List<Integer> big = new SparseIntegerList(); 90 big.set( 0, -44); 91 big.set( 1, -43); 92 big.set(n-2, 43); 93 big.set(n-1, 44); 94 int[] ints = { 0, 1, n-2, n-1 }; 95 Comparator<Integer> reverse = Collections.reverseOrder(); 96 Comparator<Integer> natural = Collections.reverseOrder(reverse); 97 98 for (int i : ints) { 99 checkBinarySearch(big, i); 100 checkBinarySearch(big, i, null); 101 checkBinarySearch(big, i, natural); 102 } 103 for (int i : ints) 104 big.set(i, - big.get(i)); 105 for (int i : ints) 106 checkBinarySearch(big, i, reverse); 107 } 108 109 //--------------------- Infrastructure --------------------------- 110 static volatile int passed = 0, failed = 0; pass()111 static void pass() {passed++;} fail()112 static void fail() {failed++; Thread.dumpStack();} fail(String msg)113 static void fail(String msg) {System.out.println(msg); fail();} unexpected(Throwable t)114 static void unexpected(Throwable t) {failed++; t.printStackTrace();} check(boolean cond)115 static void check(boolean cond) {if (cond) pass(); else fail();} equal(Object x, Object y)116 static void equal(Object x, Object y) { 117 if (x == null ? y == null : x.equals(y)) pass(); 118 else fail(x + " not equal to " + y);} main(String[] args)119 public static void main(String[] args) throws Throwable { 120 try {realMain(args);} catch (Throwable t) {unexpected(t);} 121 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 122 if (failed > 0) throw new AssertionError("Some tests failed");} 123 } 124