apache / apache/lucene

Fix FixedBitSet.nextSetBit/prevSetBit to support the common usage pattern in every programming book [LUCENE-3449]

Open
#4,523 16 comments 0 reactions 0 assignees View on GitHub
affects-version:3.4 affects-version:4.0-ALPHA legacy-jira-priority:Minor module:core/other type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

The usage pattern for nextSetBit/prevSetBit is the following:

```java
for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) {
// operate on index i here
}
```

The problem is that the i+1 at the end can be bs.length(), but the code in nextSetBit does not allow this (same applies to prevSetBit(0)). The above usage pattern is in every programming book, so it should really be supported. The check has to be done in all cases (with the current impl in the calling code).

If the check is done inside xxxSetBit() it can also be optimized to be only called seldom and not all the time, like in the ugly looking replacement, thats currently needed:

```java
for(int i=bs.nextSetBit(0); i>=0; i=(i

Contributor guide

Open the contributing guide

Research direction

Start with FixedBitSet.nextSetBit and prevSetBit, then inspect the existing FixedBitSet test code referenced in the issue. Verify the boundary calls nextSetBit(bs.length()) and prevSetBit(0), and ensure the common iteration patterns return the expected results without requiring caller-side guards.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Bug
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.