Module opshin.std.bitmap

The BitMap library provides tools to interact with a highly efficient datastructure that stores boolean values with minimal overhead (1 bit per bool)

"""
The BitMap library provides tools to interact with a highly efficient datastructure
that stores boolean values with minimal overhead (1 bit per bool)
"""

from opshin.std.builtins import *

BitMap = bytes

BYTE_SIZE = 8
POWS = [2 ** (BYTE_SIZE - i - 1) for i in range(BYTE_SIZE)]


def init_bitmap(size: int) -> BitMap:
    """Creates an empty bitmap with size bits"""
    return replicate_byte(((size + BYTE_SIZE - 1) // BYTE_SIZE), 0)


def test_bitmap(bmp: BitMap, i: int) -> bool:
    """Tests if bit at position i has been set to 1"""
    return read_bit(bmp, i)


def set_bitmap(bmp: BitMap, i: List[int]) -> BitMap:
    """Sets bits of the bitmap at indices specified by i to 1"""
    return write_bits(bmp, i, True)


def reset_bitmap(bmp: BitMap, i: List[int]) -> BitMap:
    """Sets bits of the bitmap at indices specified by i to 0"""
    return write_bits(bmp, i, False)


def flip_bitmap(bmp: BitMap, i: int) -> BitMap:
    """Flips a bit in the bitmap"""
    prev_val = read_bit(bmp, i)
    return write_bits(bmp, [i], not prev_val)


def size_bitmap(bmp: BitMap) -> int:
    """Returns the size of the bitmap in bits"""
    return len(bmp) * BYTE_SIZE


def any_bitmap(b: BitMap) -> bool:
    """Returns whether any bit was set to 1"""
    return count_set_bits(b) > 0


def all_bitmap(b: BitMap) -> bool:
    """Returns whether all bits were set to 1"""
    return count_set_bits(b) == size_bitmap(b)


def none_bitmap(b: BitMap) -> bool:
    """Returns whether no bits were set to 1"""
    return count_set_bits(b) == 0

Functions

def all_bitmap(b: bytes) ‑> bool

Returns whether all bits were set to 1

Expand source code

def all_bitmap(b: BitMap) -> bool:
    """Returns whether all bits were set to 1"""
    return count_set_bits(b) == size_bitmap(b)

def any_bitmap(b: bytes) ‑> bool

Returns whether any bit was set to 1

Expand source code

def any_bitmap(b: BitMap) -> bool:
    """Returns whether any bit was set to 1"""
    return count_set_bits(b) > 0

def flip_bitmap(bmp: bytes, i: int) ‑> bytes

Flips a bit in the bitmap

Expand source code

def flip_bitmap(bmp: BitMap, i: int) -> BitMap:
    """Flips a bit in the bitmap"""
    prev_val = read_bit(bmp, i)
    return write_bits(bmp, [i], not prev_val)

def init_bitmap(size: int) ‑> bytes

Creates an empty bitmap with size bits

Expand source code

def init_bitmap(size: int) -> BitMap:
    """Creates an empty bitmap with size bits"""
    return replicate_byte(((size + BYTE_SIZE - 1) // BYTE_SIZE), 0)

def none_bitmap(b: bytes) ‑> bool

Returns whether no bits were set to 1

Expand source code

def none_bitmap(b: BitMap) -> bool:
    """Returns whether no bits were set to 1"""
    return count_set_bits(b) == 0

def reset_bitmap(bmp: bytes, i: List[int]) ‑> bytes

Sets bits of the bitmap at indices specified by i to 0

Expand source code

def reset_bitmap(bmp: BitMap, i: List[int]) -> BitMap:
    """Sets bits of the bitmap at indices specified by i to 0"""
    return write_bits(bmp, i, False)

def set_bitmap(bmp: bytes, i: List[int]) ‑> bytes

Sets bits of the bitmap at indices specified by i to 1

Expand source code

def set_bitmap(bmp: BitMap, i: List[int]) -> BitMap:
    """Sets bits of the bitmap at indices specified by i to 1"""
    return write_bits(bmp, i, True)

def size_bitmap(bmp: bytes) ‑> int

Returns the size of the bitmap in bits

Expand source code

def size_bitmap(bmp: BitMap) -> int:
    """Returns the size of the bitmap in bits"""
    return len(bmp) * BYTE_SIZE

def test_bitmap(bmp: bytes, i: int) ‑> bool

Tests if bit at position i has been set to 1

Expand source code

def test_bitmap(bmp: BitMap, i: int) -> bool:
    """Tests if bit at position i has been set to 1"""
    return read_bit(bmp, i)