persistent-bitset 0.1.1

No project description provided

Persistent Bitsets

This package provides immutable, sparse, persistent bitsets. That is to say, adding an extra item to a bitset, or unioning two bitsets, will make a new bitset, but the new bitset will re-use as much of the old bitset as possible. It's implemented in Rust.

For a bitset with n elements whose largest element is m, memory usage should be O(n log m), single insertions should be O(log m), and unions should be O(k log m) where k is the size of the smallest bitset being unioned.

Usage example:

from persistent_bitset import PersistentBitSet

set1 = PersistentBitSet(1, 2, 3, 4, 5)
assert list(set1) == [1, 2, 3, 4, 5]
set2 = set1.add(9)
assert list(set1) == [1, 2, 3, 4, 5]
assert list(set2) == [1, 2, 3, 4, 5, 9]

set3 = PersistentBitSet(1, 2, 3).union(PersistentBitSet(4, 5, 6))
assert list(set3) == [1, 2, 3, 4, 5, 6]
assert 1 in set3
assert 6 in set3