6410729 Add BitSet.previousClearBit, previousSetBit

[Martin Buchholz]

Peter,

Thanks.

I agree that previousClearBit, previousSetBit are worth
adding to BitSet and intend to work on integrating your
contribution soon.

BitSet has not seen a lot of maintenance the past few
years, but I have been involved with most of it.

Martin

Peter B. West wrote:
> 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?
> 
> 
> ------------------------------------------------------------------------
> 
> --- 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.