ImmutableBitSet

[gissuebot]

Original issue created by adam.g...@evocatus.com on 2012-07-06 at 12:55 PM

---

Java does not have an immutable BitSet. It would be nice if there was an ImmutableBitSetBuilder.

I and many others often use BitSets for URI encoding purposes or for complicated flag configuration. Thus the BitSets are often saved configuration (as a static final) that you don't want people to mutate.

http://stackoverflow.com/questions/7023936/is-there-an-immutablebitset-n-java

I hate requesting stuff with out writing the code so I will look into doing that today if people are interested.

[gissuebot]

Original comment posted by wasserman.louis on 2012-07-06 at 02:13 PM

---

How would this differ from e.g. BigInteger?

---

Labels: -Type-Enhancement, Type-Addition

[gissuebot]

Original comment posted by wasserman.louis on 2012-07-06 at 02:17 PM

---

(Also, I'm not certain I understand your use cases -- where would you use a BitSet for flag configuration that e.g. an EnumSet is less appropriate?)

[gissuebot]

Original comment posted by adam.g...@evocatus.com on 2012-07-06 at 02:57 PM

---

EnumSet could be used but is pain if you have lets say 256 flags as is the case with URI encoding: http://grepcode.com/file/repo1.maven.org/maven2/commons-httpclient/commons-httpclient/3.1/org/apache/commons/httpclient/util/URIUtil.java#URIUtil.encode%28java.lang.String%2Cjava.util.BitSet%29

The flags indicate which character should be encoded or not.

As for BigInteger besides the semantics (BigInteger doesn't make me think of bit arrays) I was unclear of the performance of getting a specific bit or how to effectively to get a specific bit easily.

[gissuebot]

Original comment posted by adam.g...@evocatus.com on 2012-07-06 at 03:03 PM

---

Notice that even Guava's JavaDoc recommends using bitset:

https://google.github.io/guava/apidocs/com/google/common/primitives/Booleans.html#contains(boolean[], boolean)

"Note: consider representing the array as a BitSet instead, replacing Booleans.contains(array, true) with !bitSet.isEmpty() and Booleans.contains(array, false) with bitSet.nextClearBit(0) == sizeOfBitSet."

[gissuebot]

Original comment posted by wasserman.louis on 2012-07-06 at 08:17 PM

---

Eh? BigInteger.testBit is O(1).

Also, are you suggesting that ImmutableBitSet would extend BitSet, if you want it to be used in that URIUtil implementation? I'm a bit uncomfortable with extending JDK classes that seem like they ought to be final.

(Effective Java mentions: "Arguably, BitSet plays the role of mutable companion to BigInteger under certain circumstances." in item 15.)

[gissuebot]

Original comment posted by adam.g...@evocatus.com on 2012-07-07 at 12:40 AM

---

Eh? BigInteger.testBit is O(1).

Wasserman.louis I did not know about BigInteger.testBit() and you obviously are more versed (and probably smarter) than me on BigInteger. I'll have to look at the JDK core more closely.

Also, are you suggesting that ImmutableBitSet would extend BitSet,

You got me on that I forgot that BitSet is not an interface.

(Effective Java mentions: "Arguably, BitSet plays the role of mutable companion to BigInteger under certain circumstances." in item 15.)

I know Joshua Bloch is the Jesus of Java and he's probably right.

I just don't like using BigInteger for BitSets when clearly even according to the Guava doc (which while not Joshua Bloch but still good stuff) says use BitSets for Boolean array. BigInteger seems to be a lucky fit. Compare this to Scala where there is an Immutable Bit Set: http://www.scala-lang.org/api/current/scala/collection/BitSet.html

I wish I could go change all the old code to accept BigInteger instead of BitSet but I'm stuck with BitSet.

[gissuebot]

Original comment posted by wasserman.louis on 2012-07-07 at 10:03 AM

---

Let me be clear: if I could rewrite the JDK, I would absolutely ensure that BitSet had an obvious immutable implementation and everything.

Scala, of course, can get away with rewriting the core libraries. But I'm not sure there's any good solution here for Guava to provide. =/

[gissuebot]

Original comment posted by kurt.kluever on 2012-07-24 at 05:54 PM

---

BigInteger is the right implementation but the wrong abstraction.

Might be worth exploring.

---

Status: Research

[gissuebot]

Original comment posted by kevinb@google.com on 2013-04-08 at 06:58 PM

---

(No comment entered for this change.)

---

Labels: Package-Base

[gissuebot]

Original comment posted by heuermh on 2013-04-18 at 05:06 PM

---

I have implemented such based on org.apache.lucene.util.OpenBitSet from the Apache Lucene project here

http://www.dishevelled.org/bitset http://www.dishevelled.org/bitset/apidocs/index.html

I can relicense as Apache version 2 if there is any interest.

[buraksarac]

I am also playing around with this implementation but it has limited size, https://github.com/buraksarac/bitset/blob/master/src/main/java/org/qunix/bitset/BitSet.java in case of you are interested I will be happy to do changes you want! Or I could use some feedback:)

[lukeu]

I stumble back to this page from time to time. This time I found something new - the JDK added this last year:

https://bugs.openjdk.org/browse/JDK-8315454

Unfortunately it's a private-impl in JDK-22. But maybe a useful reference? e.g. the ticket lists where an ImmutableBitSet could find uses within the JDK itself. (In 16 static finals across 6 classes)