Commit 9924bf41-89a2-4c0b-8853-50a4675eaacc/upstream/1.1+git20210623.1.67a5642+dfsg - sparsebitset

Import upstream version 1.1+git20210623.1.67a5642+dfsg Kali Janitor 1 year, 4 months ago

8 changed file(s) with 689 addition(s) and 22 deletion(s). Raw diff Collapse all Expand all

-6

~~.gitignore~~ less more

0		target
1		.settings/org.eclipse.core.resources.prefs
2		.settings/org.eclipse.jdt.core.prefs
3		.settings/org.eclipse.m2e.core.prefs
4		.idea/
5		*.iml

-0

.travis.yml less more

	0	language: java
	1	sudo: false
	2	cache:
	3	directories:
	4	- $HOME/.m2/repository
	5	jdk:
	6	- openjdk7

+18

-1

README.md less more

	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.2</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

-2

pom.xml less more

2	2
3	3	<groupId>com.zaxxer</groupId>
4	4	<artifactId>SparseBitSet</artifactId>
5		<version>1.1</version>
	5	<version>1.3-SNAPSHOT</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>

+166

-13

src/main/java/com/zaxxer/sparsebits/SparseBitSet.java less more

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

230	230	protected static final int SHIFT1 = LEVEL2 + LEVEL3;
231	231
232	232	/**
	233	* LENGTH2_SIZE is maximum index of a LEVEL2 page.
	234	*/
	235	protected static final int LENGTH2_SIZE = LENGTH2 - 1;
	236
	237	/**
	238	* LENGTH3_SIZE is maximum index of a LEVEL3 page.
	239	*/
	240	protected static final int LENGTH3_SIZE = LENGTH3 - 1;
	241
	242	/**
	243	* LENGTH4_SIZE is maximum index of a bit in a LEVEL4 word.
	244	*/
	245	protected static final int LENGTH4_SIZE = LENGTH4 - 1;
	246
	247	/**
233	248	* Holds reference to the cache of statistics values computed by the
234	249	* UpdateStrategy
235	250	* @see SparseBitSet.Cache

591	606	setScanner(i, j, null, clearStrategy);
592	607	}
593	608
594		/**
	609	/**
595	610	* Sets all of the bits in this <code>SparseBitSet</code> to
596	611	* <code>false</code>.
597	612	*

650	665
651	666	/**
652	667	* 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
	668	* <code>true</code> if and only if the argument is not <code>null</code>
	669	* and is a <code>SparseBitSet</code> object that has exactly the same bits
655	670	* set to <code>true</code> as this bit set. That is, for every nonnegative
656	671	* <code>i</code> indexing a bit in the set,
657	672	* <pre>((SparseBitSet)obj).get(i) == this.get(i)</pre>

1008	1023	return (w1 >= aLength ? -1
1009	1024	: (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3)
1010	1025	+ Long.numberOfTrailingZeros(word));
	1026	}
	1027
	1028	/**
	1029	* Returns the index of the nearest bit that is set to {@code false}
	1030	* that occurs on or before the specified starting index.
	1031	* If no such bit exists, or if {@code -1} is given as the
	1032	* starting index, then {@code -1} is returned.
	1033	*
	1034	* @param i the index to start checking from (inclusive)
	1035	* @return the index of the previous clear bit, or {@code -1} if there
	1036	* is no such bit
	1037	* @throws IndexOutOfBoundsException if the specified index is less
	1038	* than {@code -1}
	1039	* @since 1.2
	1040	* @see java.util.BitSet#previousClearBit
	1041	*/
	1042	public int previousClearBit(int i)
	1043	{
	1044	if (i < 0)
	1045	{
	1046	if (i == -1)
	1047	return -1;
	1048	throw new IndexOutOfBoundsException("i=" + i);
	1049	}
	1050
	1051	final long[][][] bits = this.bits;
	1052	final int aSize = bits.length - 1;
	1053
	1054	int w = i >> SHIFT3;
	1055	int w3 = w & MASK3;
	1056	int w2 = (w >> SHIFT2) & MASK2;
	1057	int w1 = w >> SHIFT1;
	1058	if (w1 > aSize)
	1059	return i;
	1060	w1 = Math.min(w1, aSize);
	1061	int w4 = i % LENGTH4;
	1062
	1063	long word;
	1064	long[][] a2;
	1065	long[] a3;
	1066
	1067	for (; w1 >= 0; --w1)
	1068	{
	1069	if ((a2 = bits[w1]) == null)
	1070	return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + w4;
	1071	for (; w2 >= 0; --w2)
	1072	{
	1073	if ((a3 = a2[w2]) == null)
	1074	return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + w4;
	1075	for (; w3 >= 0; --w3)
	1076	{
	1077	if ((word = a3[w3]) == 0)
	1078	return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + w4;
	1079	for (int bitIdx = w4; bitIdx >= 0; --bitIdx)
	1080	{
	1081	if ((word & (1L << bitIdx)) == 0)
	1082	return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + bitIdx;
	1083	}
	1084	w4 = LENGTH4_SIZE;
	1085	}
	1086	w3 = LENGTH3_SIZE;
	1087	}
	1088	w2 = LENGTH2_SIZE;
	1089	}
	1090	return -1;
	1091	}
	1092
	1093	/**
	1094	* Returns the index of the nearest bit that is set to {@code true}
	1095	* that occurs on or before the specified starting index.
	1096	* If no such bit exists, or if {@code -1} is given as the
	1097	* starting index, then {@code -1} is returned.
	1098	*
	1099	* @param i the index to start checking from (inclusive)
	1100	* @return the index of the previous set bit, or {@code -1} if there
	1101	* is no such bit
	1102	* @throws IndexOutOfBoundsException if the specified index is less
	1103	* than {@code -1}
	1104	* @since 1.2
	1105	* @see java.util.BitSet#previousSetBit
	1106	*/
	1107	public int previousSetBit(int i)
	1108	{
	1109	if (i < 0)
	1110	{
	1111	if (i == -1)
	1112	return -1;
	1113	throw new IndexOutOfBoundsException("i=" + i);
	1114	}
	1115
	1116	final long[][][] bits = this.bits;
	1117	final int aSize = bits.length - 1;
	1118
	1119	/* This is the word from which the search begins. */
	1120	final int w = i >> SHIFT3;
	1121	int w1 = w >> SHIFT1;
	1122	int w2, w3, w4;
	1123	/* But if its off the end of the array, start from the very end. */
	1124	if (w1 > aSize)
	1125	{
	1126	w1 = aSize;
	1127	w2 = LENGTH2_SIZE;
	1128	w3 = LENGTH3_SIZE;
	1129	w4 = LENGTH4_SIZE;
	1130	}
	1131	else
	1132	{
	1133	w2 = (w >> SHIFT2) & MASK2;
	1134	w3 = w & MASK3;
	1135	w4 = i % LENGTH4;
	1136	}
	1137	long word;
	1138	long[][] a2;
	1139	long[] a3;
	1140	for (; w1 >= 0; --w1)
	1141	{
	1142	if ((a2 = bits[w1]) != null)
	1143	for (; w2 >= 0; --w2)
	1144	{
	1145	if ((a3 = a2[w2]) != null)
	1146	for (; w3 >= 0; --w3)
	1147	{
	1148	if ((word = a3[w3]) != 0)
	1149	for (int bitIdx = w4; bitIdx >= 0; --bitIdx)
	1150	{
	1151	if ((word & (1L << bitIdx)) != 0)
	1152	return (((w1 << SHIFT1) + (w2 << SHIFT2) + w3) << SHIFT3) + bitIdx;
	1153	}
	1154	w4 = LENGTH4_SIZE;
	1155	}
	1156	w3 = LENGTH3_SIZE;
	1157	w4 = LENGTH4_SIZE;
	1158	}
	1159	w2 = LENGTH2_SIZE;
	1160	w3 = LENGTH3_SIZE;
	1161	w4 = LENGTH4_SIZE;
	1162	}
	1163	return -1;
1011	1164	}
1012	1165
1013	1166	/**

1351	1504	/** Sequences of set bits longer than this value are shown by
1352	1505	* {@link #toString()} as a "sub-sequence," in the form <code>a..b</code>.
1353	1506	* 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
	1507	* The default default value is 2 (which means sequences of three or more
1355	1508	* bits set are shown as a subsequence, and all other set bits are listed
1356	1509	* individually).
1357	1510	* <p>

1569	1722	newSize = MAX_LENGTH1;
1570	1723	final int aLength1 = (bits != null ? bits.length : 0);
1571	1724
1572		if (newSize != aLength1)
	1725	if (newSize != aLength1 \|\| bits == null)
1573	1726	{ // only if the size needs to be changed
1574	1727	final long[][][] temp = new long[newSize][][]; // Get the new array
1575	1728	if (aLength1 != 0)

1838	1991	//==============================================================================
1839	1992
1840	1993	/**
1841		* Save the state of the <code>SparseBitSet</code> instance to a stream
	1994	* Save the state of the <code>SparseBitSet</code> instance to a stream
1842	1995	* (<i>i.e.</i>, serialize it).
1843	1996	*
1844	1997	* @param s the ObjectOutputStream to which to write the serialized object

1847	2000	* inconsistent
1848	2001	*
1849	2002	* @serialData The default data is emitted, followed by the current
1850		* <i>compactionCount</i> for the bit set, and then the
	2003	* <i>compactionCount</i> for the bit set, and then the
1851	2004	* <i>length</i> of the set (the position of the last bit),
1852	2005	* followed by the <i>cache.count</i> value (an <code>int</code>,
1853	2006	* the number of <code>int->long</code> pairs needed to describe

1901	2054	private static final long serialVersionUID = -6663013367427929992L;
1902	2055
1903	2056	/**
1904		* Reconstitute the <code>SparseBitSet</code> instance from a stream
	2057	* Reconstitute the <code>SparseBitSet</code> instance from a stream
1905	2058	* (<i>i.e.</i>, deserialize it).
1906	2059	*
1907	2060	* @param s the ObjectInputStream to use

+44

-0

src/test/java/com/zaxxer/sparsebits/InitWithZeroTest.java less more

	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	}

+219

-0

src/test/java/com/zaxxer/sparsebits/PreviousClearBitTest.java less more

	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
	209	@Test
	210	public void bug15() throws Exception {
	211	set.set(1);
	212	set.set(64);
	213	assertEquals(63, set.previousClearBit(64));
	214	set.clear(0);
	215	set.set(1);
	216	assertEquals(63, set.previousClearBit(64));
	217	}
	218	}⏎

+233

-0

src/test/java/com/zaxxer/sparsebits/PreviousSetBitTest.java less more

	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	}⏎