Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ImmutableBitSet #1059

Open
gissuebot opened this issue Oct 31, 2014 · 11 comments
Open

ImmutableBitSet #1059

gissuebot opened this issue Oct 31, 2014 · 11 comments

Comments

@gissuebot
Copy link

gissuebot commented Oct 31, 2014

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

gissuebot commented Nov 1, 2014

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
Copy link
Author

gissuebot commented Nov 1, 2014

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
Copy link
Author

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
Copy link
Author

gissuebot commented Nov 1, 2014

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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
Copy link
Author

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
Copy link

buraksarac commented Nov 25, 2019

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:)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

5 participants