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