fastutil
fastutil copied to clipboard
vigna
BooleanMap/Set implementations should delegate to a super simple data structure
Instead of having grand data structures for a keyspace of only 2 elements, all BooleanMap/Set implementations should delegate to a super simple implementation that only has whether true is present, whether false is present, and for maps, the true value and the false value. This should be super fast and super compact in memory.
The only complexity would be that for some implementations, a sorted order needs to be maintained (those that implement SortedBooleanMap/Set). In others, we need to maintain insertion order. (For implementations that do not assure a key order, we can just use the sorted order for free).
Oh, I didn't notice that there aren't even Boolean2WhateverMaps generated. So I guess make this feature request only about BooleanSet
"All BooleanMap/Set implementations" sounds a bit grand for a single implementation: BooleanOpenHashSet. LOL.
Yep, the whole point is that something like "BooleanOpenHashSet" is complete overkill for booleans. It should just be two boolean variables (whether true and false are present). All of the boolean sets should be. The only reason I didn't suggest getting rid of all the boolean set implementations and just have one or two of this sort of super simple implementation is for backwards compatibility.
Ok. In the interest of clarity, can you name another implementation beside BooleanOpenHashSet?
Hmm, looking over it, BooleanOpenHashSet and BooleanArraySet are the only concrete set type for booleans currently. There isn't even a SortedSet implementation.
So I guess then we can just make a new set implementation, BooleanSimpleSet or BooleanFastSet or BooleanDirectSet or something, that is just two boolean member variables.
Optionally, we can then make those two set implementations delegate to that implementation (though care would be needed for BooleanArraySet to preserve insertion order)
I'd just write ten-line specific implementations of those, with a two-element boolean array remembering whether true or false are in the set. Pull requests, anybody?
I might be willing to try this. I just had my hands full with the Spliterator stuff at the time. However, implementing NavigableMap may be a better first step.
Yes I would try to release 8.5.0 with #162 and the attack navigabile. There's even a proposal from 2017 with the interfaces 🙈.
Given that a boolean set can have only 4 possible states, {}, {false}, {true}, and {false, true}, it would make sense to have an immutable boolean set implementation alongside the mutable one.