system.bit_sequences module¶

Concrete bit-sequence implementations: integer-backed, bit-list, and Word-Aligned Hybrid (WAH) compressed.

class system.bit_sequences.IntegerBitSequence(number: int = 0, represented_number_of_bits: int | None = None)[source]¶

Bases: UncompressedBitSequence

Represents a bit-sequence as an integer type.

update_represented_number_of_bits(updated_represented_number_of_bits: int) → None[source]¶

See BitSequence.update_represented_number_of_bits().

When shrinking, masks off all bits above the new length on the backing integer.

contains_bit_sequence(other: IntegerBitSequence) → bool[source]¶

See BitSequence.contains_bit_sequence().

Uses a bitwise AND: other is contained iff ANDing both backing integers yields other’s integer.

all_bits_set_to_false() → bool[source]¶

See BitSequence.all_bits_set_to_false().

Checks whether the backing integer is zero.

all_bits_set_to_true() → bool[source]¶

See BitSequence.all_bits_set_to_true().

Compares the popcount of the backing integer to the represented length.

static create_all_false_bit_sequence(max_len: int = 0) → IntegerBitSequence[source]¶

See BitSequence.create_all_false_bit_sequence().

Parameters:: max_len – The number of bits in the bit-sequence.

intersects(other: IntegerBitSequence) → bool[source]¶

See BitSequence.intersects().

Uses a bitwise AND: the sequences intersect iff ANDing their backing integers is non-zero.

bit_count() → int[source]¶

See BitSequence.bit_count().

Uses Python’s int.bit_count() on the backing integer.

get_least_significant_bit() → IntegerBitSequence[source]¶

See BitSequence.get_least_significant_bit().

Isolates the lowest set bit via the two’s-complement identity number & -number.

get_most_significant_bit() → IntegerBitSequence[source]¶

See BitSequence.get_most_significant_bit().

Uses int.bit_length() to locate the highest set bit.

increase_represented_integer(number: int) → None[source]¶

See BitSequence.increase_represented_integer().

Adds number to the backing integer directly.

get_represented_integer() → int[source]¶: See BitSequence.get_represented_integer().

class SetBitsIterator(bit_sequence: IntegerBitSequence)[source]¶

Bases: SetBitsIterator

See BitSequence.SetBitsIterator.

class SetBitsReverseIterator(bit_sequence: IntegerBitSequence)[source]¶

Bases: SetBitsReverseIterator

See BitSequence.SetBitsReverseIterator.

class system.bit_sequences.BitListBitSequence(bit_list: list[bool] | None = None, represented_number_of_bits: int | None = None)[source]¶

Bases: UncompressedBitSequence

Represents a bit-sequence as a list of booleans.

intersects(other: BitListBitSequence) → bool[source]¶

See BitSequence.intersects().

Scans the overlapping prefix of both lists for a shared set bit.

bit_count() → int[source]¶

See BitSequence.bit_count().

Counts the set bits by iterating over them.

get_least_significant_bit() → BitListBitSequence[source]¶

See BitSequence.get_least_significant_bit().

Returns the first set bit found iterating low to high.

get_most_significant_bit() → BitListBitSequence[source]¶

See BitSequence.get_most_significant_bit().

Returns the first set bit found iterating high to low.

update_represented_number_of_bits(updated_represented_number_of_bits: int) → None[source]¶

See BitSequence.update_represented_number_of_bits().

Truncates the boolean list when shrinking, or pads it with False entries when growing.

contains_bit_sequence(other: BitListBitSequence) → bool[source]¶

See BitSequence.contains_bit_sequence().

Checks that every set bit of other is also set in self.

static create_all_false_bit_sequence(represented_number_of_bits: int = 0) → BitListBitSequence[source]¶: See BitSequence.create_all_false_bit_sequence().

increase_represented_integer(number: int) → None[source]¶

See BitSequence.increase_represented_integer().

Performs bit-by-bit binary addition of number into the boolean list, propagating a carry.

get_represented_integer() → int[source]¶: See BitSequence.get_represented_integer().

class SetBitsIterator(bit_sequence: BitListBitSequence)[source]¶

Bases: SetBitsIterator

See BitSequence.SetBitsIterator.

class SetBitsReverseIterator(bit_sequence: BitListBitSequence)[source]¶

Bases: SetBitsReverseIterator

See BitSequence.SetBitsReverseIterator.

all_bits_set_to_false() → bool[source]¶

See BitSequence.all_bits_set_to_false().

Checks that no entry of the boolean list is set.

all_bits_set_to_true() → bool[source]¶

See BitSequence.all_bits_set_to_true().

Checks that every entry of the boolean list is set.

class system.bit_sequences.WAHBitSequence(represented_number_of_bits: int, words: list[~system.interfaces.bit_sequence.UncompressedBitSequence], bit_sequence_type: ~typing.Type[~system.interfaces.bit_sequence.UncompressedBitSequence] = <class 'system.bit_sequences.IntegerBitSequence'>)[source]¶

Bases: CompressedBitSequence

Compressed bit sequence implementing Word-Aligned-Hybrid Encoding.

WORD_LENGTH: int = 64¶

class WordListCreator(bit_sequence_type: ~typing.Type[~system.interfaces.bit_sequence.UncompressedBitSequence] = <class 'system.bit_sequences.IntegerBitSequence'>)[source]¶

Bases: object

Helper class to create a list of words. Used during compression and bit-wise operations. The idea that we keep an inner counter that tracks how many consecutive fills we already found. Whenever we find a new represented fill bit, a literal is found, or the fill word becomes fill, we add a single fill word containing all these fill words to the list of words.

add_fills(new_fill_bit: bool, number_of_added_fills: int = 1) → None[source]¶: Creates a new fill word if necessary, or increments current number of consecutive fills if possible. :param new_fill_bit: The bit represented by the new fill word. True if it represents a 1-fill, False otherwise. :param number_of_added_fills: The number of consecutive fills to add.

get_resulting_word_list() → list[UncompressedBitSequence][source]¶: Obtains the final word list. :return: The final compressed word list.

add_literal(literal_word: UncompressedBitSequence) → None[source]¶: Adds the given literal word to the word list. :param literal_word: The literal word to add.

add_uncompressed_bit_sequence_as_literal(uncompressed_bit_sequence: UncompressedBitSequence) → None[source]¶: Adds the given uncompressed bit sequence as literal to the word list. :param uncompressed_bit_sequence: The bit sequence to add.

add_from_uncompressed_bit_sequence(bit_sequence: UncompressedBitSequence) → None[source]¶: Obtains a bit sequence of length (WORD_LENGTH - 1) and either compresses it into a literal or fill word. :param bit_sequence: The uncompressed bit sequence to add.

static max_number_of_merged_fills_in_one_word() → int[source]¶: Returns the maximal number of fill words that can be merged into a single fill word. :return: The maximal number of fill words that can be merged into a single fill word.

static create_fill_word(represented_bit: bool, bit_sequence_type: Type[UncompressedBitSequence]) → UncompressedBitSequence[source]¶: Creates a fill word representing (WORD_LENGTH - 1) of the represented bit. :param represented_bit: The represented bit. :param bit_sequence_type: The bit sequence type to represent the underlying bit sequence. :return: The fill word.

static create_literal_word(bit_sequence_type: Type[UncompressedBitSequence]) → UncompressedBitSequence[source]¶: Creates a literal word representing (WORD_LENGTH - 1) bits :param bit_sequence_type: The bit sequence to represent the underlying bit sequence. :return: The literal word.

static get_represented_bit_of_fill_word(fill_word: UncompressedBitSequence) → bool[source]¶: Returns the represented bit of a fill word. Assumes that the passed word is a fill! :param fill_word: The fill word. :return: True, if 1 is represented, False if 0 is represented.

static get_number_of_fills_represented_by_fill_word(fill_word: UncompressedBitSequence) → int[source]¶: Returns the number of fills represented by a fill word. Assumes that the passed word is a fill! :param fill_word: The fill word. :return: The number of represented fills.

static compress_bit_sequence(bit_sequence: UncompressedBitSequence) → WAHBitSequence[source]¶

See CompressedBitSequence.compress_bit_sequence().

Traverses the uncompressed sequence in chunks of WORD_LENGTH - 1 bits, encoding each chunk as a fill or literal word via a WordListCreator.

static is_fill(word: UncompressedBitSequence) → bool[source]¶: Checks if the given word is a fill word. :param word: The index of the word. :return: True, if the word is a fill word.

static xor_literal_fill(literal: UncompressedBitSequence, fill: UncompressedBitSequence, word_list_creator: WordListCreator) → None[source]¶: Computes the logical xor between the literal and fill word. :param literal: The literal word. :param fill: The fill word. :param word_list_creator: Helper structure to create the underlying word list. :return: The resulting word, either as fill or as literal.

static and_literal_fill(literal: UncompressedBitSequence, fill: UncompressedBitSequence, word_list_creator: WordListCreator) → None[source]¶: Computes the logical and between the literal and fill word. :param literal: The literal word. :param fill: The fill word. :param word_list_creator: Helper structure to create the underlying word list. :return: The resulting word, either as fill or as literal.

static or_literal_fill(literal: UncompressedBitSequence, fill: UncompressedBitSequence, word_list_creator: WordListCreator) → None[source]¶: Computes the logical or between the literal and fill word. :param literal: The literal word. :param fill: The fill word. :param word_list_creator: Helper structure to create the underlying word list. :return: The resulting word, either as fill or as literal.

get_number_of_bits() → int[source]¶

See BitSequence.get_number_of_bits().

Returns the number of bits physically stored, i.e. WORD_LENGTH times the number of words, including any padding bits; this can be larger than the represented length returned by len(self).

class FillIterator(fill_word: UncompressedBitSequence, bit_index: int)[source]¶

Bases: SetBitsIterator

An iterator to traverse a fill word.

class LiteralIterator(literal_word: UncompressedBitSequence, bit_index: int)[source]¶

Bases: SetBitsIterator

An iterator to traverse a literal word.

class SetBitsIterator(compressed_bit_sequence: WAHBitSequence)[source]¶

Bases: SetBitsIterator

See BitSequence.SetBitsIterator.

get_current_word() → UncompressedBitSequence[source]¶: Returns the current word. :return: The current word.

get_next_iterator() → SetBitsIterator | None[source]¶

Returns the next iterator.

Skipped 0-fill words are traversed with a loop rather than recursion: a sparse bitmap can contain thousands of consecutive 0-fill words, and recursing once per skipped word would exceed Python’s recursion limit. The loop keeps the stack depth constant. :return: The iterator.

all_bits_set_to_false() → bool[source]¶

See BitSequence.all_bits_set_to_false().