1 /* 2 * Copyright (c) 2007, 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 6410729 6586631 27 * @summary Test previousClearBit, previousSetBit 28 * @key randomness 29 */ 30 31 import java.util.*; 32 33 public class PreviousBits { 34 35 void testHashCode(final BitSet s) { 36 long h = 1234; 37 long[] words = s.toLongArray(); 38 for (int i = words.length; --i >= 0; ) 39 h ^= words[i] * (i + 1); 40 equal((int)((h >> 32) ^ h), s.hashCode()); 41 } 42 43 void testOutOfBounds(final BitSet s) { 44 THROWS(IndexOutOfBoundsException.class, 45 new F(){void f(){ s.previousSetBit(-2);}}, 46 new F(){void f(){ s.previousClearBit(-2);}}, 47 new F(){void f(){ s.previousSetBit(Integer.MIN_VALUE);}}, 48 new F(){void f(){ s.previousClearBit(Integer.MIN_VALUE);}}, 49 new F(){void f(){ s.nextSetBit(-1);}}, 50 new F(){void f(){ s.nextClearBit(-1);}}, 51 new F(){void f(){ s.nextSetBit(Integer.MIN_VALUE);}}, 52 new F(){void f(){ s.nextClearBit(Integer.MIN_VALUE);}}); 53 } 54 55 void test(String[] args) throws Throwable { 56 final BitSet s = new BitSet(); 57 58 // Test empty bitset 59 testOutOfBounds(s); 60 testHashCode(s); 61 62 for (int i = -1; i < 93;) { 63 equal(-1, s.previousSetBit(i)); 64 equal( i, s.previousClearBit(i)); 65 i++; 66 equal(-1, s.nextSetBit(i)); 67 equal( i, s.nextClearBit(i)); 68 } 69 70 // Test "singleton" bitsets 71 for (int j = 0; j < 161; j++) { 72 s.clear(); 73 s.set(j); 74 testOutOfBounds(s); 75 testHashCode(s); 76 77 for (int i = -1; i < j; i++) { 78 equal(-1, s.previousSetBit(i)); 79 equal( i, s.previousClearBit(i)); 80 if (i >= 0) { 81 equal(j, s.nextSetBit(i)); 82 equal(i, s.nextClearBit(i)); 83 } 84 } 85 86 equal(j, s.previousSetBit(j)); 87 equal(j-1, s.previousClearBit(j)); 88 equal(j, s.nextSetBit(j)); 89 equal(j+1, s.nextClearBit(j)); 90 91 for (int i = j+1; i < j+100; i++) { 92 equal(j, s.previousSetBit(i)); 93 equal(i, s.previousClearBit(i)); 94 equal(-1, s.nextSetBit(i)); 95 equal(i, s.nextClearBit(i)); 96 } 97 } 98 99 // set even bits 100 s.clear(); 101 for (int i = 0; i <= 128; i+=2) 102 s.set(i); 103 testHashCode(s); 104 for (int i = 1; i <= 128; i++) { 105 equal(s.previousSetBit(i), 106 ((i & 1) == 0) ? i : i - 1); 107 equal(s.previousClearBit(i), 108 ((i & 1) == 0) ? i - 1 : i); 109 } 110 111 // set odd bits as well 112 for (int i = 1; i <= 128; i+=2) 113 s.set(i); 114 testHashCode(s); 115 for (int i = 1; i <= 128; i++) { 116 equal(s.previousSetBit(i), i); 117 equal(s.previousClearBit(i), -1); 118 } 119 120 // Test loops documented in javadoc 121 Random rnd = new Random(); 122 s.clear(); 123 for (int i = 0; i < 10; i++) 124 s.set(rnd.nextInt(1066)); 125 List<Integer> down = new ArrayList<Integer>(); 126 for (int i = s.length(); (i = s.previousSetBit(i-1)) >= 0; ) 127 down.add(i); 128 List<Integer> up = new ArrayList<Integer>(); 129 for (int i = s.nextSetBit(0); i >= 0; i = s.nextSetBit(i+1)) 130 up.add(i); 131 Collections.reverse(up); 132 equal(up, down); 133 } 134 135 //--------------------- Infrastructure --------------------------- 136 volatile int passed = 0, failed = 0; 137 void pass() {passed++;} 138 void fail() {failed++; Thread.dumpStack();} 139 void fail(String msg) {System.err.println(msg); fail();} 140 void unexpected(Throwable t) {failed++; t.printStackTrace();} 141 void check(boolean cond) {if (cond) pass(); else fail();} 142 void equal(Object x, Object y) { 143 if (x == null ? y == null : x.equals(y)) pass(); 144 else fail(x + " not equal to " + y);} 145 public static void main(String[] args) throws Throwable { 146 new PreviousBits().instanceMain(args);} 147 void instanceMain(String[] args) throws Throwable { 148 try {test(args);} catch (Throwable t) {unexpected(t);} 149 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 150 if (failed > 0) throw new AssertionError("Some tests failed");} 151 abstract class F {abstract void f() throws Throwable;} 152 void THROWS(Class<? extends Throwable> k, F... fs) { 153 for (F f : fs) 154 try {f.f(); fail("Expected " + k.getName() + " not thrown");} 155 catch (Throwable t) { 156 if (k.isAssignableFrom(t.getClass())) pass(); 157 else unexpected(t);}} 158 }