New upstream release.
Kali Janitor
1 year, 5 months ago
0 | [![][Build Status img]][Build Status] | |
1 | [![][license img]][license] | |
2 | [![][Maven Central img]][Maven Central] | |
3 | [![][Javadocs img]][Javadocs] | |
4 | ||
0 | 5 | SparseBitSet |
1 | 6 | ============ |
2 | 7 | |
17 | 22 | <dependency> |
18 | 23 | <groupId>com.zaxxer</groupId> |
19 | 24 | <artifactId>SparseBitSet</artifactId> |
20 | <version>1.0</version> | |
25 | <version>1.1</version> | |
21 | 26 | <scope>compile</scope> |
22 | 27 | </dependency> |
23 | 28 | ``` |
38 | 43 | Using a virtual-memory like structure, the SparseBitSet overhead is ~0.03 32-bit words overhead per 64 bits. |
39 | 44 | |
40 | 45 | For a full analysis, read Dr. Haddon's [slide stack](https://github.com/brettwooldridge/SparseBitSet/blob/master/SparseBitSet.pdf). |
46 | ||
47 | [Build Status]:https://travis-ci.org/brettwooldridge/SparseBitSet | |
48 | [Build Status img]:https://travis-ci.org/brettwooldridge/SparseBitSet.svg?branch=master | |
49 | ||
50 | [license]:LICENSE | |
51 | [license img]:https://img.shields.io/badge/license-Apache%202-blue.svg | |
52 | ||
53 | [Maven Central]:https://maven-badges.herokuapp.com/maven-central/com.zaxxer/SparseBitSet | |
54 | [Maven Central img]:https://maven-badges.herokuapp.com/maven-central/com.zaxxer/SparseBitSet/badge.svg | |
55 | ||
56 | [Javadocs]:http://javadoc.io/doc/com.zaxxer/SparseBitSet | |
57 | [Javadocs img]:http://javadoc.io/badge/com.zaxxer/SparseBitSet.svg |
0 | sparsebitset (1.2+dfsg-0kali1) UNRELEASED; urgency=low | |
1 | ||
2 | * New upstream release. | |
3 | ||
4 | -- Kali Janitor <[email protected]> Fri, 02 Dec 2022 01:41:12 -0000 | |
5 | ||
0 | 6 | sparsebitset (1.1+dfsg-0kali3) kali-dev; urgency=medium |
1 | 7 | |
2 | 8 | * Update Maintainer field |
2 | 2 | |
3 | 3 | <groupId>com.zaxxer</groupId> |
4 | 4 | <artifactId>SparseBitSet</artifactId> |
5 | <version>1.1</version> | |
5 | <version>1.2</version> | |
6 | 6 | <packaging>jar</packaging> |
7 | 7 | |
8 | 8 | <name>SparseBitSet</name> |
49 | 49 | <dependency> |
50 | 50 | <groupId>junit</groupId> |
51 | 51 | <artifactId>junit</artifactId> |
52 | <version>3.8.1</version> | |
52 | <version>4.12</version> | |
53 | 53 | <scope>test</scope> |
54 | 54 | </dependency> |
55 | 55 | </dependencies> |
11 | 11 | /** |
12 | 12 | * This class implements a set of bits that grows as needed. Each bit of the |
13 | 13 | * bit set represents a <code>boolean</code> value. The values of a |
14 | * <code>SparseBitSet</code> are indexed by nonnegative integers. | |
14 | * <code>SparseBitSet</code> are indexed by non-negative integers. | |
15 | 15 | * Individual indexed values may be examined, set, cleared, or modified by |
16 | 16 | * logical operations. One <code>SparseBitSet</code> or logical value may be |
17 | 17 | * used to modify the contents of (another) <code>SparseBitSet</code> through |
30 | 30 | * <code>SparseBitSet</code> are labelled <code> |
31 | 31 | * 0</code> .. <code>Integer.MAX_VALUE − 1</code>. |
32 | 32 | * After the last set bit of a <code>SparseBitSet</code>, any attempt to find |
33 | * a subsequent bit (<i>getNextSetBit</i>()), will return an value of −1. | |
34 | * If an attempt is made to use <i>getNextClearBit</i>(), and all the bits are | |
35 | * set from the starting postion of the search to the bit labelled | |
33 | * a subsequent bit (<i>nextSetBit</i>()), will return an value of −1. | |
34 | * If an attempt is made to use <i>nextClearBit</i>(), and all the bits are | |
35 | * set from the starting position of the search to the bit labelled | |
36 | 36 | * <code>Integer.MAX_VALUE − 1</code>, then similarly −1 |
37 | 37 | * will be returned. |
38 | 38 | * <p> |
40 | 40 | * a <code>SparseBitSet</code> will result in a |
41 | 41 | * <code>NullPointerException</code>. |
42 | 42 | * <p> |
43 | * A <code>SparseBitSet</code> is not safe for multithreaded use without | |
43 | * A <code>SparseBitSet</code> is not safe for multi-threaded use without | |
44 | 44 | * external synchronization. |
45 | 45 | * |
46 | 46 | * @author Bruce K. Haddon |
591 | 591 | setScanner(i, j, null, clearStrategy); |
592 | 592 | } |
593 | 593 | |
594 | /** | |
594 | /** | |
595 | 595 | * Sets all of the bits in this <code>SparseBitSet</code> to |
596 | 596 | * <code>false</code>. |
597 | 597 | * |
650 | 650 | |
651 | 651 | /** |
652 | 652 | * Compares this object against the specified object. The result is |
653 | * <code>true</code> if and only if the argument is not <code>null</code> | |
654 | * and is a <code>SparseBitSet</code> object that has exactly the same bits | |
653 | * <code>true</code> if and only if the argument is not <code>null</code> | |
654 | * and is a <code>SparseBitSet</code> object that has exactly the same bits | |
655 | 655 | * set to <code>true</code> as this bit set. That is, for every nonnegative |
656 | 656 | * <code>i</code> indexing a bit in the set, |
657 | 657 | * <pre>((SparseBitSet)obj).get(i) == this.get(i)</pre> |
1008 | 1008 | return (w1 >= aLength ? -1 |
1009 | 1009 | : (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) |
1010 | 1010 | + Long.numberOfTrailingZeros(word)); |
1011 | } | |
1012 | ||
1013 | /** | |
1014 | * Returns the index of the nearest bit that is set to {@code false} | |
1015 | * that occurs on or before the specified starting index. | |
1016 | * If no such bit exists, or if {@code -1} is given as the | |
1017 | * starting index, then {@code -1} is returned. | |
1018 | * | |
1019 | * @param i the index to start checking from (inclusive) | |
1020 | * @return the index of the previous clear bit, or {@code -1} if there | |
1021 | * is no such bit | |
1022 | * @throws IndexOutOfBoundsException if the specified index is less | |
1023 | * than {@code -1} | |
1024 | * @since 1.2 | |
1025 | * @see java.util.BitSet#previousClearBit | |
1026 | */ | |
1027 | public int previousClearBit(int i) | |
1028 | { | |
1029 | if (i < 0) | |
1030 | { | |
1031 | if (i == -1) | |
1032 | return -1; | |
1033 | throw new IndexOutOfBoundsException("i=" + i); | |
1034 | } | |
1035 | ||
1036 | final long[][][] bits = this.bits; | |
1037 | final int aLength = bits.length; | |
1038 | ||
1039 | int w = i >> SHIFT3; | |
1040 | int w3 = w & MASK3; | |
1041 | int w2 = (w >> SHIFT2) & MASK2; | |
1042 | int w1 = w >> SHIFT1; | |
1043 | if (w1 > aLength - 1) | |
1044 | return i; | |
1045 | w1 = Math.min(w1, aLength - 1); | |
1046 | final int w4 = i % LENGTH4; | |
1047 | ||
1048 | long word; | |
1049 | long[][] a2; | |
1050 | long[] a3; | |
1051 | ||
1052 | final int f3 = w3; | |
1053 | final int f2 = w2; | |
1054 | final int f1 = w1; | |
1055 | ||
1056 | for (; w1 >= 0; --w1) | |
1057 | { | |
1058 | if ((a2 = bits[w1]) == null) | |
1059 | return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) | |
1060 | + (f1 == w1 ? w4 : LENGTH4 - 1); | |
1061 | for (; w2 >= 0; --w2) | |
1062 | { | |
1063 | if ((a3 = a2[w2]) == null) | |
1064 | return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) | |
1065 | + (f2 == w2 ? w4 : LENGTH4 - 1); | |
1066 | for (; w3 >= 0; --w3) | |
1067 | { | |
1068 | if ((word = a3[w3]) == 0) | |
1069 | return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) | |
1070 | + (f3 == w3 ? w4 : LENGTH4 - 1); | |
1071 | for (int bitIdx = w4; bitIdx >= 0; --bitIdx) | |
1072 | { | |
1073 | if ((word & (1L << bitIdx)) == 0) | |
1074 | return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + bitIdx; | |
1075 | } | |
1076 | } | |
1077 | w3 = LENGTH3 - 1; | |
1078 | } | |
1079 | w2 = LENGTH2 - 1; | |
1080 | w3 = LENGTH3 - 1; | |
1081 | } | |
1082 | return -1; | |
1083 | } | |
1084 | ||
1085 | /** | |
1086 | * Returns the index of the nearest bit that is set to {@code true} | |
1087 | * that occurs on or before the specified starting index. | |
1088 | * If no such bit exists, or if {@code -1} is given as the | |
1089 | * starting index, then {@code -1} is returned. | |
1090 | * | |
1091 | * @param i the index to start checking from (inclusive) | |
1092 | * @return the index of the previous set bit, or {@code -1} if there | |
1093 | * is no such bit | |
1094 | * @throws IndexOutOfBoundsException if the specified index is less | |
1095 | * than {@code -1} | |
1096 | * @since 1.2 | |
1097 | * @see java.util.BitSet#previousSetBit | |
1098 | */ | |
1099 | public int previousSetBit(int i) | |
1100 | { | |
1101 | if (i < 0) | |
1102 | { | |
1103 | if (i == -1) | |
1104 | return -1; | |
1105 | throw new IndexOutOfBoundsException("i=" + i); | |
1106 | } | |
1107 | ||
1108 | final long[][][] bits = this.bits; | |
1109 | final int aLength = bits.length; | |
1110 | ||
1111 | /* This is the word from which the search begins. */ | |
1112 | final int w = i >> SHIFT3; | |
1113 | int w1 = w >> SHIFT1; | |
1114 | int w2, w3, w4; | |
1115 | /* But if its off the end of the array, start from the very end. */ | |
1116 | if (w1 > aLength - 1) | |
1117 | { | |
1118 | w1 = aLength - 1; | |
1119 | w2 = LENGTH2 - 1; | |
1120 | w3 = LENGTH3 - 1; | |
1121 | w4 = LENGTH4 - 1; | |
1122 | } | |
1123 | else | |
1124 | { | |
1125 | w2 = (w >> SHIFT2) & MASK2; | |
1126 | w3 = w & MASK3; | |
1127 | w4 = i % LENGTH4; | |
1128 | } | |
1129 | boolean initialWord = true; | |
1130 | ||
1131 | long word; | |
1132 | long[][] a2; | |
1133 | long[] a3; | |
1134 | for (; w1 >= 0; --w1, initialWord = false) | |
1135 | { | |
1136 | if ((a2 = bits[w1]) != null) | |
1137 | for (; w2 >= 0; --w2, initialWord = false) | |
1138 | { | |
1139 | if ((a3 = a2[w2]) != null) | |
1140 | for (; w3 >= 0; --w3, initialWord = false) | |
1141 | { | |
1142 | if ((word = a3[w3]) != 0) | |
1143 | for (int bitIdx = (initialWord ? w4 : LENGTH4 - 1); bitIdx >= 0; --bitIdx) | |
1144 | { | |
1145 | if ((word & (1L << bitIdx)) != 0) | |
1146 | return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + bitIdx; | |
1147 | } | |
1148 | } | |
1149 | w3 = LENGTH3 - 1; | |
1150 | } | |
1151 | w2 = LENGTH2 - 1; | |
1152 | w3 = LENGTH3 - 1; | |
1153 | } | |
1154 | return -1; | |
1011 | 1155 | } |
1012 | 1156 | |
1013 | 1157 | /** |
1351 | 1495 | /** Sequences of set bits longer than this value are shown by |
1352 | 1496 | * {@link #toString()} as a "sub-sequence," in the form <code>a..b</code>. |
1353 | 1497 | * Setting this value to zero causes each set bit to be listed individually. |
1354 | * The default default value is 2 (which means sequences of three or more | |
1498 | * The default default value is 2 (which means sequences of three or more | |
1355 | 1499 | * bits set are shown as a subsequence, and all other set bits are listed |
1356 | 1500 | * individually). |
1357 | 1501 | * <p> |
1569 | 1713 | newSize = MAX_LENGTH1; |
1570 | 1714 | final int aLength1 = (bits != null ? bits.length : 0); |
1571 | 1715 | |
1572 | if (newSize != aLength1) | |
1716 | if (newSize != aLength1 || bits == null) | |
1573 | 1717 | { // only if the size needs to be changed |
1574 | 1718 | final long[][][] temp = new long[newSize][][]; // Get the new array |
1575 | 1719 | if (aLength1 != 0) |
1838 | 1982 | //============================================================================== |
1839 | 1983 | |
1840 | 1984 | /** |
1841 | * Save the state of the <code>SparseBitSet</code> instance to a stream | |
1985 | * Save the state of the <code>SparseBitSet</code> instance to a stream | |
1842 | 1986 | * (<i>i.e.</i>, serialize it). |
1843 | 1987 | * |
1844 | 1988 | * @param s the ObjectOutputStream to which to write the serialized object |
1847 | 1991 | * inconsistent |
1848 | 1992 | * |
1849 | 1993 | * @serialData The default data is emitted, followed by the current |
1850 | * <i>compactionCount</i> for the bit set, and then the | |
1994 | * <i>compactionCount</i> for the bit set, and then the | |
1851 | 1995 | * <i>length</i> of the set (the position of the last bit), |
1852 | 1996 | * followed by the <i>cache.count</i> value (an <code>int</code>, |
1853 | 1997 | * the number of <code>int->long</code> pairs needed to describe |
1901 | 2045 | private static final long serialVersionUID = -6663013367427929992L; |
1902 | 2046 | |
1903 | 2047 | /** |
1904 | * Reconstitute the <code>SparseBitSet</code> instance from a stream | |
2048 | * Reconstitute the <code>SparseBitSet</code> instance from a stream | |
1905 | 2049 | * (<i>i.e.</i>, deserialize it). |
1906 | 2050 | * |
1907 | 2051 | * @param s the ObjectInputStream to use |
0 | package com.zaxxer.sparsebits; | |
1 | ||
2 | import org.junit.Assert; | |
3 | import org.junit.Before; | |
4 | import org.junit.Test; | |
5 | ||
6 | public class InitWithZeroTest { | |
7 | private SparseBitSet bitset; | |
8 | ||
9 | @Before | |
10 | public void setup() { | |
11 | bitset = new SparseBitSet(0); | |
12 | } | |
13 | ||
14 | @Test | |
15 | public void testPreviousSetBit() { | |
16 | Assert.assertEquals(-1, bitset.previousSetBit(0)); | |
17 | } | |
18 | ||
19 | @Test | |
20 | public void testPreviousClearBit() { | |
21 | Assert.assertEquals(0, bitset.previousClearBit(0)); | |
22 | } | |
23 | ||
24 | @Test | |
25 | public void testNextSetBit() { | |
26 | Assert.assertEquals(-1, bitset.nextSetBit(0)); | |
27 | } | |
28 | ||
29 | @Test | |
30 | public void testNextClearBit() { | |
31 | Assert.assertEquals(0, bitset.nextClearBit(0)); | |
32 | } | |
33 | ||
34 | @Test | |
35 | public void testClone() { | |
36 | Assert.assertEquals(-1, bitset.clone().nextSetBit(0)); | |
37 | } | |
38 | ||
39 | @Test | |
40 | public void testAnd() { | |
41 | bitset.and(new SparseBitSet()); | |
42 | } | |
43 | } |
0 | package com.zaxxer.sparsebits; | |
1 | ||
2 | import org.junit.Assert; | |
3 | import org.junit.Before; | |
4 | import org.junit.Test; | |
5 | ||
6 | import java.util.HashSet; | |
7 | import java.util.Random; | |
8 | import java.util.Set; | |
9 | ||
10 | import static com.zaxxer.sparsebits.SparseBitSet.SHIFT1; | |
11 | import static com.zaxxer.sparsebits.SparseBitSet.SHIFT2; | |
12 | import static com.zaxxer.sparsebits.SparseBitSet.SHIFT3; | |
13 | ||
14 | /** | |
15 | * @author <a href="mailto:[email protected]">Brent Douglas</a> | |
16 | */ | |
17 | public class PreviousClearBitTest extends Assert { | |
18 | ||
19 | SparseBitSet set; | |
20 | ||
21 | @Before | |
22 | public void setUp() { | |
23 | set = new SparseBitSet(); | |
24 | } | |
25 | ||
26 | @Test | |
27 | public void minusOne() throws Exception { | |
28 | final int ret = set.previousClearBit(-1); | |
29 | ||
30 | assertEquals(-1, ret); | |
31 | } | |
32 | ||
33 | @Test | |
34 | public void emptySet() throws Exception { | |
35 | final int ret = set.previousClearBit(0); | |
36 | ||
37 | assertEquals(0, ret); | |
38 | } | |
39 | ||
40 | @Test | |
41 | public void bottomBit() throws Exception { | |
42 | final int ret = set.previousClearBit(1); | |
43 | ||
44 | assertEquals(1, ret); | |
45 | } | |
46 | ||
47 | @Test | |
48 | public void sameBit() throws Exception { | |
49 | set.set(12345); | |
50 | final int ret = set.previousClearBit(12345); | |
51 | ||
52 | assertEquals(12344, ret); | |
53 | } | |
54 | ||
55 | @Test | |
56 | public void level1Miss() throws Exception { | |
57 | final int i = (1 << (SHIFT1 + SHIFT3)); | |
58 | set.set(i); | |
59 | final int ret = set.previousClearBit(i); | |
60 | ||
61 | assertEquals(i - 1, ret); | |
62 | } | |
63 | ||
64 | @Test | |
65 | public void level1MissPlus1() throws Exception { | |
66 | final int i = (1 << (SHIFT1 + SHIFT3)) + 1; | |
67 | set.set(i); | |
68 | final int ret = set.previousClearBit(i); | |
69 | ||
70 | assertEquals(i - 1, ret); | |
71 | } | |
72 | ||
73 | @Test | |
74 | public void level1MissMinus1() throws Exception { | |
75 | final int i = (1 << (SHIFT1 + SHIFT3)) - 1; | |
76 | set.set(i); | |
77 | final int ret = set.previousClearBit(i); | |
78 | ||
79 | assertEquals(i - 1, ret); | |
80 | } | |
81 | ||
82 | @Test | |
83 | public void level2Miss() throws Exception { | |
84 | final int i = (1 << (SHIFT3 + SHIFT2)); | |
85 | set.set(i); | |
86 | final int ret = set.previousClearBit(i); | |
87 | ||
88 | assertEquals(i - 1, ret); | |
89 | } | |
90 | ||
91 | @Test | |
92 | public void level2MissPlus1() throws Exception { | |
93 | final int i = (1 << (SHIFT3 + SHIFT2)) + 1; | |
94 | set.set(i); | |
95 | final int ret = set.previousClearBit(i); | |
96 | ||
97 | assertEquals(i - 1, ret); | |
98 | } | |
99 | ||
100 | @Test | |
101 | public void level2MissMinus1() throws Exception { | |
102 | final int i = (1 << (SHIFT3 + SHIFT2)) - 1; | |
103 | set.set(i); | |
104 | final int ret = set.previousClearBit(i); | |
105 | ||
106 | assertEquals(i - 1, ret); | |
107 | } | |
108 | ||
109 | @Test | |
110 | public void level3Miss() throws Exception { | |
111 | final int i = (1 << SHIFT3); | |
112 | set.set(i); | |
113 | final int ret = set.previousClearBit(i); | |
114 | ||
115 | assertEquals(i - 1, ret); | |
116 | } | |
117 | ||
118 | @Test | |
119 | public void level3MissPlus1() throws Exception { | |
120 | final int i = (1 << SHIFT3) + 1; | |
121 | set.set(i); | |
122 | final int ret = set.previousClearBit(i); | |
123 | ||
124 | assertEquals(i - 1, ret); | |
125 | } | |
126 | ||
127 | @Test | |
128 | public void level3MissMinus1() throws Exception { | |
129 | final int i = (1 << SHIFT3) - 1; | |
130 | set.set(i); | |
131 | final int ret = set.previousClearBit(i); | |
132 | ||
133 | assertEquals(i - 1, ret); | |
134 | } | |
135 | ||
136 | @Test | |
137 | public void noneBelow() throws Exception { | |
138 | set.set(1); | |
139 | final int ret = set.previousClearBit(1); | |
140 | ||
141 | assertEquals(0, ret); | |
142 | } | |
143 | ||
144 | @Test | |
145 | public void oneBelow() throws Exception { | |
146 | set.set(1); | |
147 | final int ret = set.previousClearBit(2); | |
148 | ||
149 | assertEquals(2, ret); | |
150 | } | |
151 | ||
152 | @Test | |
153 | public void threeNoSet() throws Exception { | |
154 | set.set(1); | |
155 | final int ret = set.previousClearBit(3); | |
156 | ||
157 | assertEquals(3, ret); | |
158 | } | |
159 | ||
160 | @Test | |
161 | public void threeSet() throws Exception { | |
162 | set.set(3); | |
163 | final int ret = set.previousClearBit(3); | |
164 | ||
165 | assertEquals(2, ret); | |
166 | } | |
167 | ||
168 | @Test | |
169 | public void topBit() throws Exception { | |
170 | final int i = Integer.MAX_VALUE - 1; | |
171 | final int ret = set.previousClearBit(i); | |
172 | ||
173 | assertEquals(i, ret); | |
174 | } | |
175 | ||
176 | @Test | |
177 | public void randomSingleEntry() throws Exception { | |
178 | final Random random = new Random(0); | |
179 | for (int i = 0; i < 10000; ++i) { | |
180 | set = new SparseBitSet(); | |
181 | final int x = Math.abs(random.nextInt() + 1); | |
182 | final int ret = set.previousClearBit(x); | |
183 | assertEquals("Failed on i = " + i, x, ret); | |
184 | } | |
185 | } | |
186 | ||
187 | @Test | |
188 | public void randomMultiEntry() throws Exception { | |
189 | final Random random = new Random(0); | |
190 | final Set<Integer> values = new HashSet<Integer>(); | |
191 | for (int i = 0; i < 10000; ++i) { | |
192 | set = new SparseBitSet(); | |
193 | for (int j = 0; j < 1000; ++j) { | |
194 | final int x = Math.abs(random.nextInt() + 1); | |
195 | set.set(x); | |
196 | values.add(x); | |
197 | } | |
198 | final int x = Math.abs(random.nextInt() + 1); | |
199 | int expected = x; | |
200 | while (values.contains(expected)) { | |
201 | --expected; | |
202 | } | |
203 | final int ret = set.previousClearBit(x); | |
204 | assertEquals("Failed on i = " + i + " x = " + x, expected, ret); | |
205 | values.clear(); | |
206 | } | |
207 | } | |
208 | }⏎ |
0 | package com.zaxxer.sparsebits; | |
1 | ||
2 | import org.junit.Assert; | |
3 | import org.junit.Before; | |
4 | import org.junit.Test; | |
5 | ||
6 | import java.util.ArrayList; | |
7 | import java.util.Collections; | |
8 | import java.util.List; | |
9 | import java.util.Random; | |
10 | ||
11 | import static com.zaxxer.sparsebits.SparseBitSet.SHIFT1; | |
12 | import static com.zaxxer.sparsebits.SparseBitSet.SHIFT2; | |
13 | import static com.zaxxer.sparsebits.SparseBitSet.SHIFT3; | |
14 | ||
15 | /** | |
16 | * @author <a href="mailto:[email protected]">Brent Douglas</a> | |
17 | */ | |
18 | public class PreviousSetBitTest extends Assert { | |
19 | ||
20 | SparseBitSet set; | |
21 | ||
22 | @Before | |
23 | public void setUp() { | |
24 | set = new SparseBitSet(); | |
25 | } | |
26 | ||
27 | @Test | |
28 | public void emptySet() throws Exception { | |
29 | final int ret = set.previousSetBit(0); | |
30 | ||
31 | assertEquals(-1, ret); | |
32 | } | |
33 | ||
34 | @Test | |
35 | public void bottomBit() throws Exception { | |
36 | set.set(0); | |
37 | final int ret = set.previousSetBit(0); | |
38 | ||
39 | assertEquals(0, ret); | |
40 | } | |
41 | ||
42 | @Test | |
43 | public void betweenTwo() throws Exception { | |
44 | set.set(4); | |
45 | set.set(8); | |
46 | final int ret = set.previousSetBit(5); | |
47 | ||
48 | assertEquals(4, ret); | |
49 | } | |
50 | ||
51 | @Test | |
52 | public void inRun() throws Exception { | |
53 | set.set(4); | |
54 | set.set(8); | |
55 | set.set(13); | |
56 | set.set(25); | |
57 | set.set(268); | |
58 | final int ret = set.previousSetBit(22); | |
59 | ||
60 | assertEquals(13, ret); | |
61 | } | |
62 | ||
63 | @Test | |
64 | public void sameBit() throws Exception { | |
65 | set.set(12345); | |
66 | final int ret = set.previousSetBit(12345); | |
67 | ||
68 | assertEquals(12345, ret); | |
69 | } | |
70 | ||
71 | @Test | |
72 | public void noneBelow() throws Exception { | |
73 | set.set(1); | |
74 | final int ret = set.previousSetBit(0); | |
75 | ||
76 | assertEquals(-1, ret); | |
77 | } | |
78 | ||
79 | @Test | |
80 | public void oneBelow() throws Exception { | |
81 | set.set(1); | |
82 | final int ret = set.previousSetBit(2); | |
83 | ||
84 | assertEquals(1, ret); | |
85 | } | |
86 | ||
87 | @Test | |
88 | public void twoBelow() throws Exception { | |
89 | set.set(1); | |
90 | final int ret = set.previousSetBit(3); | |
91 | ||
92 | assertEquals(1, ret); | |
93 | } | |
94 | ||
95 | @Test | |
96 | public void topBit() throws Exception { | |
97 | final int i = Integer.MAX_VALUE - 1; | |
98 | set.set(i); | |
99 | final int ret = set.previousSetBit(i); | |
100 | ||
101 | assertEquals(i, ret); | |
102 | } | |
103 | ||
104 | @Test | |
105 | public void level1Miss() throws Exception { | |
106 | final int i = (1 << (SHIFT1 + SHIFT3)); | |
107 | set.set(i - 1); | |
108 | final int ret = set.previousSetBit(i); | |
109 | ||
110 | assertEquals(i - 1, ret); | |
111 | } | |
112 | ||
113 | @Test | |
114 | public void level1MissPlus1() throws Exception { | |
115 | final int i = (1 << (SHIFT1 + SHIFT3)) + 1; | |
116 | set.set(i - 1); | |
117 | final int ret = set.previousSetBit(i); | |
118 | ||
119 | assertEquals(i - 1, ret); | |
120 | } | |
121 | ||
122 | @Test | |
123 | public void level1MissMinus1() throws Exception { | |
124 | final int i = (1 << (SHIFT1 + SHIFT3)) - 1; | |
125 | set.set(i - 1); | |
126 | final int ret = set.previousSetBit(i); | |
127 | ||
128 | assertEquals(i - 1, ret); | |
129 | } | |
130 | ||
131 | @Test | |
132 | public void level2Miss() throws Exception { | |
133 | final int i = (1 << (SHIFT3 + SHIFT2)); | |
134 | set.set(i - 1); | |
135 | final int ret = set.previousSetBit(i); | |
136 | ||
137 | assertEquals(i - 1, ret); | |
138 | } | |
139 | ||
140 | @Test | |
141 | public void level2MissPlus1() throws Exception { | |
142 | final int i = (1 << (SHIFT3 + SHIFT2)) + 1; | |
143 | set.set(i - 1); | |
144 | final int ret = set.previousSetBit(i); | |
145 | ||
146 | assertEquals(i - 1, ret); | |
147 | } | |
148 | ||
149 | @Test | |
150 | public void level2MissMinus1() throws Exception { | |
151 | final int i = (1 << (SHIFT3 + SHIFT2)) - 1; | |
152 | set.set(i - 1); | |
153 | final int ret = set.previousSetBit(i); | |
154 | ||
155 | assertEquals(i - 1, ret); | |
156 | } | |
157 | ||
158 | @Test | |
159 | public void level3Miss() throws Exception { | |
160 | final int i = (1 << SHIFT3); | |
161 | set.set(i - 1); | |
162 | final int ret = set.previousSetBit(i); | |
163 | ||
164 | assertEquals(i - 1, ret); | |
165 | } | |
166 | ||
167 | @Test | |
168 | public void level3MissPlus1() throws Exception { | |
169 | final int i = (1 << SHIFT3) + 1; | |
170 | set.set(i - 1); | |
171 | final int ret = set.previousSetBit(i); | |
172 | ||
173 | assertEquals(i - 1, ret); | |
174 | } | |
175 | ||
176 | @Test | |
177 | public void level3MissMinus1() throws Exception { | |
178 | final int i = (1 << SHIFT3) - 1; | |
179 | set.set(i - 1); | |
180 | final int ret = set.previousSetBit(i); | |
181 | ||
182 | assertEquals(i - 1, ret); | |
183 | } | |
184 | ||
185 | @Test | |
186 | public void randomSingleEntry() throws Exception { | |
187 | final int max = Integer.MAX_VALUE - 1; | |
188 | final Random random = new Random(0); | |
189 | for (int i = 0; i < 10000; ++i) { | |
190 | set = new SparseBitSet(); | |
191 | final int x = Math.abs(random.nextInt() + 1); | |
192 | set.set(x); | |
193 | final int ret = set.previousSetBit(max); | |
194 | assertEquals("Failed on i = " + i, x, ret); | |
195 | } | |
196 | } | |
197 | ||
198 | @Test | |
199 | public void randomMultiEntry() throws Exception { | |
200 | randomMultiEntry(Integer.MAX_VALUE); | |
201 | } | |
202 | ||
203 | @Test | |
204 | public void randomMultiEntryTight() throws Exception { | |
205 | randomMultiEntry(2000); | |
206 | } | |
207 | ||
208 | public void randomMultiEntry(final int max) throws Exception { | |
209 | final Random random = new Random(0); | |
210 | final List<Integer> values = new ArrayList<Integer>(); | |
211 | for (int i = 0; i < 10000; ++i) { | |
212 | set = new SparseBitSet(); | |
213 | for (int j = 0; j < 1000; ++j) { | |
214 | final int x = Math.abs(random.nextInt() + 1) % max; | |
215 | set.set(x); | |
216 | values.add(x); | |
217 | } | |
218 | final int x = Math.abs(random.nextInt() + 1) % max; | |
219 | Collections.sort(values); | |
220 | int expected = -1; | |
221 | for (final Integer val : values) { | |
222 | if (val > x) { | |
223 | break; | |
224 | } | |
225 | expected = val; | |
226 | } | |
227 | final int ret = set.previousSetBit(x); | |
228 | assertEquals("Failed on i = " + i, expected, ret); | |
229 | values.clear(); | |
230 | } | |
231 | } | |
232 | }⏎ |