`bits` class

[y-richie-y]

Right now the extractors inputs and outputs python list of booleans. This is 1) not the most compact 2) not the most readable. We can create a new class behaves like it has type List[bool], but stores the bits compactly as bytes, and exports to different formats.

Then we adapt the extractors to output bits in this format.

(edit: see https://numpy.org/doc/2.3/reference/generated/numpy.packbits.html)

[Mathwizard1]

Hi @y-richie-y, I got this repo link from @cforeman-cqc .

I am new to open source so please forgive me if i am not familiar with the conventions. I had tried to solve it with a class CompactBoolList. I have attached my code here since i am not changing any function signatures of trevisan yet. I will be happy to send the PR, if this is upto the mark.

from typing import Sequence, Literal
_bool_bits = Literal[1, 0]

class CompactBoolList:
    """
    A compact list of booleans using bit-level storage, 
    designed to interface with functions expecting list[bool].
    """

    ############ Python native methods ##############
    def __init__(self, iterable: Sequence[bool]|Sequence[_bool_bits]|None= None):
        self._data = bytearray()
        self._length = 0
        if iterable is not None:
            for item in iterable:
                self.append(item)

    def __len__(self):
        return self._length

    def _get_byte_and_bit_index(self, index) -> tuple[int, int]:
        """ Helper functions for getter, setter"""     

        # Handle negative indexing for convenience
        if index < 0:
            index += self._length

        if not (0 <= index < self._length):
            raise IndexError("Index out of range")

        byte_index = index // 8
        bit_index = index % 8
        return byte_index, bit_index

    def __getitem__(self, index: int) -> bool:
        byte_idx, bit_idx = self._get_byte_and_bit_index(index)
        mask = 1 << bit_idx
        return (self._data[byte_idx] & mask) != 0
    
    def __iter__(self):
        for i in range(self._length):
            yield self[i]

    def __setitem__(self, index: int, value: bool|_bool_bits):
        byte_idx, bit_idx = self._get_byte_and_bit_index(index)
        
        if value:
            self._data[byte_idx] |= (1 << bit_idx)
        else:
            self._data[byte_idx] &= ~(1 << bit_idx)

    def append(self, value: bool|_bool_bits):
        if self._length % 8 == 0:
            self._data.append(0)
        
        self._length += 1
        self.__setitem__(self._length - 1, value)

    def __repr__(self) -> str:
        """
        Returns the official string representation of the list.
        Example: CompactBoolList([True, False, True])
        """

        list_representation = list(self)    # use self.__iter__(self)
        return f"{self.__class__.__name__}({list_representation!r})"

    ############ Custom methods ##############
    def to_list(self) -> list[bool]:
        """Converts to a standard list[bool] for functions expecting it."""
        return list(self)


from random import randint
import sys

n = 25

input_bits = [randint(0, 1) for _ in range(n)]
print(input_bits)
print(f"\nSize:{sys.getsizeof(input_bits)}\n")

input_bool = [bool(bit) for bit in input_bits]
print(input_bool)
print(f"\nSize:{sys.getsizeof(input_bool)}\n")

compact_bool = CompactBoolList(input_bits)
print(compact_bool)
print(f"\nSize:{sys.getsizeof(compact_bool)}\n")

###### Output ######
'''
[1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1]

Size:312

[True, False, False, False, True, False, False, True, False, True, False, True, False, True, True, True, True, True, True, False, False, False, False, False, True]

Size:312

CompactBoolList([True, False, False, False, True, False, False, True, False, True, False, True, False, True, True, True, True, True, True, False, False, False, False, False, True])

Size:48
'''

for i in range(10):
    print(compact_bool[i])
    compact_bool[i] = 0

print(compact_bool.to_list())
print(f"\nSize:{sys.getsizeof(compact_bool)}\n")

###### Output ######
'''
False
True
False
False
True
True
True
True
True
False
[False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, True, True, True, False, False, True, True, False]

Size:48
'''