I had previously posted about this on the jdk-collaboration list without getting any responses.
Attached is an implementation of BitSet.java which includes the previousClearBit and previousSetBit methods. It is in the form of a NetBeans project, including JUnit tests. The project is specified in a non-java package for testing. All up, there are 73 additional lines of code and docs in BitSet.java. No big deal. Also attached is a udiff against JDK build 15 of 5th July. I have been, on and off, roaming in the wilderness of JDK builds and jtreg testing since I first submitted the code on the 6th of May, without making much progress, and without getting any response. As far as I can tell, I have followed the recommended path for a submission. Obviously, there are flaws in either the documentation or the implementation. I have tried using the NetBeans build facilities to build and test a project consisting only of BitSet.java. While I can build it, I don't know how to run jtreg against it. I suspect I must have a full JDK build, which I have not been able to achieve on my SuSE 10.2 box. Note that I haven't actually written a jtreg test yet. I'll do that when I've been able to get one to run in the current environment. Anyway, what I'm after is some (hopefully simple) set of steps I can follow to get this trivial piece of code either accepted or rejected for, what, Java 8? Java 9? -- Peter B. West <http://cv.pbw.id.au/> Folio <http://defoe.sourceforge.net/folio/>
BitSet.tgz
Description: application/compressed-tar
--- openjdk/j2se/src/share/classes/java/util/BitSet.java 2007-07-05 17:49:27.000000000 +1000
+++ openjdk.mods/j2se/src/share/classes/java/util/BitSet.java 2007-07-18 16:16:59.000000000 +1000
@@ -593,6 +593,81 @@
}
/**
+ * Returns the index of the nearest bit that is set to <code>true</code>
+ * that occurs on or before the specified starting index. If no such
+ * bit exists then -1 is returned.
+ *
+ * To iterate over the <code>true</code> bits in a <code>BitSet</code>,
+ * use the following loop:
+ *
+ * <pre>
+ * int i = bs.previousSetBit(bs.length);
+ * while (i >= 0) {
+ * // operate on index i here
+ * if (--i < 0) {
+ * i = bs.previousSetBit(i);
+ * }
+ * }
+ *
+ * @param fromIndex the index to start checking from (inclusive).
+ * @return the index of the previous set bit.
+ * @throws IndexOutOfBoundsException if the specified index is negative.
+ */
+ public int previousSetBit(int fromIndex) {
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+
+ checkInvariants();
+
+ int u = wordIndex(fromIndex);
+ if (u >= wordsInUse) {
+ return length() - 1;
+ }
+
+ long mask = (WORD_MASK << fromIndex + 1) ^ WORD_MASK;
+ long word = words[u] & ( mask != 0 ? mask : WORD_MASK );
+
+ while (true) {
+ if (word != 0)
+ return (u * BITS_PER_WORD) + BIT_INDEX_MASK - Long.numberOfLeadingZeros(word);
+ if (u-- == 0)
+ return -1;
+ word = words[u];
+ }
+ }
+
+ /**
+ * Returns the index of the nearest bit that is set to <code>false</code>
+ * that occurs on or before the specified starting index.
+ *
+ * @param fromIndex the index to start checking from (inclusive).
+ * @return the index of the previous clear bit.
+ * @throws IndexOutOfBoundsException if the specified index is negative.
+ */
+ public int previousClearBit(int fromIndex) {
+ if (fromIndex < 0)
+ throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
+
+ checkInvariants();
+
+ int u = wordIndex(fromIndex);
+ if (u >= wordsInUse) {
+ return fromIndex;
+ }
+
+ long mask = (WORD_MASK << fromIndex + 1) ^ WORD_MASK;
+ long word = ~words[u] & ( mask != 0 ? mask : WORD_MASK );
+
+ while (true) {
+ if (word != 0)
+ return (u * BITS_PER_WORD) + BIT_INDEX_MASK - Long.numberOfLeadingZeros(word);
+ if (u-- == 0)
+ return -1;
+ word = ~words[u];
+ }
+ }
+
+ /**
* Returns the "logical size" of this <code>BitSet</code>: the index of
* the highest set bit in the <code>BitSet</code> plus one. Returns zero
* if the <code>BitSet</code> contains no set bits.
