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