%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 2001-2002, 2004-2007, 2009-2011 The University of Melbourne
% Copyright (C) 2013-2025 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: bitmap.m.
% Main author: rafe, stayl.
% Stability: medium.
%
% Efficient bitmap implementation.
%
% CAVEAT: the user is referred to the documentation in the header of array.m
% regarding programming with unique objects (the compiler does not
% currently recognise them, hence we are forced to use non-unique modes
% until the situation is rectified; this places a small burden on programmers
% to ensure the correctness of their code that would otherwise be assured
% by the compiler.)
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module bitmap.
:- interface.

:- import_module bool.
:- import_module io.
:- import_module list.
:- import_module stream.

%--------------------------------------------------%

    % Type `bitmap' is equivalent to `array(bool)', but is implemented
    % much more efficiently. Accessing bitmaps as if they were an array
    % of eight bit bytes is especially efficient.
    %
    % See runtime/mercury_types.h for the definition of MR_BitmapPtr for
    % use in foreign code.
    %
    % Comparison of bitmaps first compares the size. If the sizes are equal,
    % then it compares each bit in turn, starting from bit zero.
    %
:- type bitmap.

:- inst bitmap == ground.
:- inst uniq_bitmap == bitmap.          % XXX should be unique
:- mode bitmap_di == in(uniq_bitmap).   % XXX should be di
:- mode bitmap_uo == out(uniq_bitmap).
:- mode bitmap_ui == in(uniq_bitmap).

    % The exception thrown for any error.
    %
:- type bitmap_error
    --->    bitmap_error(string).

%--------------------------------------------------%

:- type bit_index == int.
:- type byte_index == int.
:- type num_bits == int.
:- type num_bytes == int.

    % 8 bits stored in the least significant bits of the integer.
    %
:- type byte == int.

    % An integer interpreted as a vector of int.bits_per_int bits.
    %
:- type word == int.

%--------------------------------------------------%

    % init(N, B) creates a bitmap of size N (indexed 0 .. N-1)
    % setting each bit if B = yes and clearing each bit if B = no.
    % An exception is thrown if N is negative.
    %
:- func init(num_bits::in, bool::in) = (bitmap::bitmap_uo) is det.

    % A synonym for init(N, no).
    %
:- func init(num_bits::in) = (bitmap::bitmap_uo) is det.

    % Is the given bit number in range?
    %
:- pred in_range(bitmap, bit_index).
% :- mode in_range(bitmap_ui, in) is semidet.
:- mode in_range(in, in) is semidet.

    % Is the given byte number in range?
    %
:- pred byte_in_range(bitmap, byte_index).
% :- mode byte_in_range(bitmap_ui, in) is semidet.
:- mode byte_in_range(in, in) is semidet.

    % Return the number of bits in a bitmap.
    %
:- func num_bits(bitmap) = num_bits.
% :- mode num_bits(bitmap_ui) = out is det.
:- mode num_bits(in) = out is det.

    % Return the number of bytes in a bitmap, failing if the bitmap
    % has a partial final byte.
    %
:- func num_bytes(bitmap) = num_bytes.
% :- mode num_bytes(bitmap_ui) = out is semidet.
:- mode num_bytes(in) = out is semidet.
:- pred num_bytes(bitmap, num_bytes).
% :- mode num_bytes(bitmap_ui, out) is semidet.
:- mode num_bytes(in, out) is semidet.

    % As above, but throw an exception if the bitmap has a partial final byte.
    %
:- func det_num_bytes(bitmap) = num_bytes.
% :- mode det_num_bytes(bitmap_ui) = out is det.
:- mode det_num_bytes(in) = out is det.

    % Return the number of bits in a byte (always 8).
    %
:- func bits_per_byte = int.

    % is_empty(Bitmap):
    % True if-and-only-if Bitmap is a bitmap containing zero bits.
    %
:- pred is_empty(bitmap).
%:- mode is_empty(bitmap_ui) is semidet.
:- mode is_empty(in) is semidet.

%--------------------------------------------------%

    % get_bit(Bitmap, Index) = Bit:
    % Bitmap ^ bit(Index) = Bit:
    %
    % Get the indicated bit of Bitmap.
    %
    % Throws an exception if Index is not in range.
    %
:- func get_bit(bitmap, bit_index) = bool.
% :- mode get_bit(bitmap_ui, in) = out is det.
:- mode get_bit(in, in) = out is det.
:- func bit(bit_index, bitmap) = bool.
% :- mode bit(in, bitmap_ui) = out is det.
:- mode bit(in, in) = out is det.

    % unsafe_get_bit(Bitmap, Index) = Bit:
    % Bitmap ^ unsafe_bit(Index) = Bit:
    %
    % Does the same job as get_bit, but the result is undefined
    % if Index is not in range.
    %
:- func unsafe_get_bit(bitmap, bit_index) = bool.
% :- mode unsafe_get_bit(bitmap_ui, in) = out is det.
:- mode unsafe_get_bit(in, in) = out is det.
:- func unsafe_bit(bit_index, bitmap) = bool.
% :- mode unsafe_bit(in, bitmap_ui) = out is det.
:- mode unsafe_bit(in, in) = out is det.

    % set_bit(Index, NewBit, !BitMap):
    % !.Bitmap ^ bit(Index) := NewBit:
    %
    % Set the indicated bit of !.Bitmap to NewBit.
    %
    % Throws an exception if Index is not in range.
    %
:- pred set_bit(bit_index, bool, bitmap, bitmap).
:- mode set_bit(in, in, bitmap_di, bitmap_uo) is det.
:- func 'bit :='(bit_index, bitmap, bool) = bitmap.
:- mode 'bit :='(in, bitmap_di, in) = bitmap_uo is det.

    % unsafe_set_bit(Index, NewBit, !BitMap):
    % !.Bitmap ^ unsafe_bit(Index) := NewBit:
    %
    % Does the same job as set_bit, but the result is undefined
    % if Index is not in range.
    %
:- pred unsafe_set_bit(bit_index, bool, bitmap, bitmap).
:- mode unsafe_set_bit(in, in, bitmap_di, bitmap_uo) is det.
:- func 'unsafe_bit :='(bit_index, bitmap, bool) = bitmap.
:- mode 'unsafe_bit :='(in, bitmap_di, in) = bitmap_uo is det.

%--------------------------------------------------%

    % get_bits(Bitmap, Index, NumBits) = Word:
    % Bitmap ^ bits(Index) = Word:
    %
    % Get some number of bits at the indicated Index out of Bitmap.
    % The low order bits of Word will contain the NumBits bits of Bitmap
    % starting at Index. NumBits must be in the range given by
    % 0 =< NumBits =< int.bits_per_int.
    %
    % Throws an exception if either Index or NumBits is not in range.
    %
:- func get_bits(bitmap, bit_index, num_bits) = word.
% :- mode get_bits(bitmap_ui, in, in) = out is det.
:- mode get_bits(in, in, in) = out is det.
:- func bits(bit_index, num_bits, bitmap) = word.
% :- mode bits(in, in, bitmap_ui) = out is det.
:- mode bits(in, in, in) = out is det.

    % unsafe_get_bits(Bitmap, Index, NumBits) = Word:
    % Bitmap ^ unsafe_bits(Index) = Word:
    %
    % Does the same job as get_bits, but the result is undefined
    % if either Index or NumBits is not in range.
    %
:- func unsafe_get_bits(bitmap, bit_index, num_bits) = word.
% :- mode unsafe_get_bits(bitmap_ui, in, in) = out is det.
:- mode unsafe_get_bits(in, in, in) = out is det.
:- func unsafe_bits(bit_index, num_bits, bitmap) = word.
% :- mode unsafe_bits(in, in, bitmap_ui) = out is det.
:- mode unsafe_bits(in, in, in) = out is det.

    % set_bits(Index, NumBits, Word, Bitmap0, BitMap):
    % Bitmap0 ^ bits(Index) := Word = BitMap:
    %
    % Set the NumBits bits of Bitmap0 starting at Index the low order
    % NumBits bits of Words, returning the updated bitmap as Bitmap.
    %
    % NumBits must be in the range given by 0 =< NumBits =< int.bits_per_int.
    %
    % Throws an exception if either Index or NumBits is not in range.
    %
:- pred set_bits(bit_index, num_bits, word, bitmap, bitmap).
:- mode set_bits(in, in, in, bitmap_di, bitmap_uo) is det.
:- func 'bits :='(bit_index, num_bits, bitmap, word) = bitmap.
:- mode 'bits :='(in, in, bitmap_di, in) = bitmap_uo is det.

    % unsafe_set_bits(Index, NumBits, Word, Bitmap0, BitMap):
    % Bitmap0 ^ unsafe_bits(Index) := Word = BitMap:
    %
    % Does the same job as set_bits, but the result is undefined
    % if either Index or NumBits is not in range.
    %
:- pred unsafe_set_bits(bit_index, num_bits, word, bitmap, bitmap).
:- mode unsafe_set_bits(in, in, in, bitmap_di, bitmap_uo) is det.
:- func 'unsafe_bits :='(bit_index, num_bits, bitmap, word) = bitmap.
:- mode 'unsafe_bits :='(in, in, bitmap_di, in) = bitmap_uo is det.

%--------------------------------------------------%
%
% Get or set the given numbered byte (multiply ByteNumber by bits_per_byte
% to get the bit index of the start of the byte).
%
% The bits are stored in or taken from the least significant bits of an int.
% The safe versions will throw an exception if the given ByteNumber is out of
% bounds. Final partial bytes are out of bounds. The unsafe versions do not
% check whether the byte is in range.
%

:- func get_byte(bitmap, byte_index) = byte.
% :- mode get_byte(bitmap_ui, in) = out is det.
:- mode get_byte(in, in) = out is det.
:- func byte(byte_index, bitmap) = word.
% :- mode byte(in, bitmap_ui) = out is det.
:- mode byte(in, in) = out is det.

:- func unsafe_get_byte(bitmap, byte_index) = byte.
% :- mode unsafe_get_byte(bitmap_ui, in) = out is det.
:- mode unsafe_get_byte(in, in) = out is det.
:- func unsafe_byte(byte_index, bitmap) = word.
% :- mode unsafe_byte(in, bitmap_ui) = out is det.
:- mode unsafe_byte(in, in) = out is det.

:- pred set_byte(byte_index, byte, bitmap, bitmap).
:- mode set_byte(in, in, bitmap_di, bitmap_uo) is det.
:- func 'byte :='(byte_index, bitmap, byte) = bitmap.
:- mode 'byte :='(in, bitmap_di, in) = bitmap_uo is det.

:- pred unsafe_set_byte(byte_index, byte, bitmap, bitmap).
:- mode unsafe_set_byte(in, in, bitmap_di, bitmap_uo) is det.
:- func 'unsafe_byte :='(byte_index, bitmap, byte) = bitmap.
:- mode 'unsafe_byte :='(in, bitmap_di, in) = bitmap_uo is det.

%
% Versions of the above that set or take uint8 values instead of a byte stored
% in the least significant bits of an int.
%

:- func get_uint8(bitmap, byte_index) = uint8.
%:- mode get_uint8(bitmap_ui, in) = out is det.
:- mode get_uint8(in, in) = out is det.

:- func unsafe_get_uint8(bitmap, byte_index) = uint8.
%:- mode unsafe_get_uint8(bitmap_ui, in) = out is det.
:- mode unsafe_get_uint8(in, in) = out is det.

:- pred set_uint8(byte_index::in, uint8::in,
    bitmap::bitmap_di, bitmap::bitmap_uo) is det.

:- pred unsafe_set_uint8(byte_index::in, uint8::in,
    bitmap::bitmap_di, bitmap::bitmap_uo) is det.

%--------------------------------------------------%

    % Flip the given bit.
    %
:- func flip(bitmap, bit_index) = bitmap.
:- mode flip(bitmap_di, in) = bitmap_uo is det.

:- pred flip(bit_index, bitmap, bitmap).
:- mode flip(in, bitmap_di, bitmap_uo) is det.

%--------------------------------------------------%
%
% Variations that might be slightly more efficient by not
% converting bits to bool.
%

:- func set(bitmap, bit_index) = bitmap.
:- mode set(bitmap_di, in) = bitmap_uo is det.

:- pred set(bit_index, bitmap, bitmap).
:- mode set(in, bitmap_di, bitmap_uo) is det.

:- func clear(bitmap, bit_index) = bitmap.
:- mode clear(bitmap_di, in) = bitmap_uo is det.

:- pred clear(bit_index, bitmap, bitmap).
:- mode clear(in, bitmap_di, bitmap_uo) is det.

    % is_set(BM, I) succeeds if-and-only-if bit I in BM is set.
    %
:- pred is_set(bitmap, bit_index).
% :- mode is_set(bitmap_ui, in) is semidet.
:- mode is_set(in, in) is semidet.

    % is_clear(BM, I) succeeds if-and-only-if bit I in BM is clear.
    %
:- pred is_clear(bitmap, bit_index).
% :- mode is_clear(bitmap_ui, in) is semidet.
:- mode is_clear(in, in) is semidet.

%--------------------------------------------------%
%
% Unsafe versions of the above. If the index is out of range,
% then behaviour is undefined, and bad things are likely to happen.
%

:- func unsafe_flip(bitmap, bit_index) = bitmap.
:- mode unsafe_flip(bitmap_di, in) = bitmap_uo is det.

:- pred unsafe_flip(bit_index, bitmap, bitmap).
:- mode unsafe_flip(in, bitmap_di, bitmap_uo) is det.

:- func unsafe_set(bitmap, bit_index) = bitmap.
:- mode unsafe_set(bitmap_di, in) = bitmap_uo is det.

:- pred unsafe_set(bit_index, bitmap, bitmap).
:- mode unsafe_set(in, bitmap_di, bitmap_uo) is det.

:- func unsafe_clear(bitmap, bit_index) = bitmap.
:- mode unsafe_clear(bitmap_di, in) = bitmap_uo is det.

:- pred unsafe_clear(bit_index, bitmap, bitmap).
:- mode unsafe_clear(in, bitmap_di, bitmap_uo) is det.

:- pred unsafe_is_set(bitmap, bit_index).
% :- mode unsafe_is_set(bitmap_ui, in) is semidet.
:- mode unsafe_is_set(in, in) is semidet.

:- pred unsafe_is_clear(bitmap, bit_index).
% :- mode unsafe_is_clear(bitmap_ui, in) is semidet.
:- mode unsafe_is_clear(in, in) is semidet.

%--------------------------------------------------%

    % Create a new copy of a bitmap.
    %
:- func copy(bitmap) = bitmap.
% :- mode copy(bitmap_ui) = bitmap_uo is det.
:- mode copy(in) = bitmap_uo is det.

    % resize(BM, N, B) resizes bitmap BM to have N bits; if N is smaller
    % than the current number of bits in BM then the excess are discarded.
    % If N is larger than the current number of bits in BM, then
    % the new bits are set if B = yes and cleared if B = no.
    %
:- func resize(bitmap, num_bits, bool) = bitmap.
:- mode resize(bitmap_di, in, in) = bitmap_uo is det.

    % Shrink a bitmap without copying it into a smaller memory allocation.
    %
:- func shrink_without_copying(bitmap, num_bits) = bitmap.
:- mode shrink_without_copying(bitmap_di, in) = bitmap_uo is det.

%--------------------------------------------------%

    % Slice = slice(BM, StartIndex, NumBits)
    %
    % A bitmap slice represents the sub-range of a bitmap of NumBits bits
    % starting at bit index StartIndex. Throws an exception if the slice
    % is not within the bounds of the bitmap.
    %
:- type slice.
:- func slice(bitmap, bit_index, num_bits) = slice.

    % As above, but use byte indices.
    %
:- func byte_slice(bitmap, byte_index, num_bytes) = slice.

    % Access functions for slices.
    %
:- func slice ^ slice_bitmap = bitmap.
:- func slice ^ slice_start_bit_index = bit_index.
:- func slice ^ slice_num_bits = num_bits.

    % As above, but return byte indices, throwing an exception
    % if the slice doesn't start and end on a byte boundary.
    %
:- func slice ^ slice_start_byte_index = byte_index.
:- func slice ^ slice_num_bytes = num_bytes.

%--------------------------------------------------%
%
% Set operations; for binary operations the second argument is altered
% in all cases. The input bitmaps must have the same size.
%

:- func complement(bitmap) = bitmap.
:- mode complement(bitmap_di) = bitmap_uo is det.

:- func union(bitmap, bitmap) = bitmap.
% :- mode union(bitmap_ui, bitmap_di) = bitmap_uo is det.
:- mode union(in, bitmap_di) = bitmap_uo is det.

:- func intersect(bitmap, bitmap) = bitmap.
% :- mode intersect(bitmap_ui, bitmap_di) = bitmap_uo is det.
:- mode intersect(in, bitmap_di) = bitmap_uo is det.

:- func difference(bitmap, bitmap) = bitmap.
% :- mode difference(bitmap_ui, bitmap_di) = bitmap_uo is det.
:- mode difference(in, bitmap_di) = bitmap_uo is det.

:- func xor(bitmap, bitmap) = bitmap.
% :- mode xor(bitmap_ui, bitmap_di) = bitmap_uo is det.
:- mode xor(in, bitmap_di) = bitmap_uo is det.

%--------------------------------------------------%

    % Condense a list of bitmaps into a single bitmap.
    %
:- func append_list(list(bitmap)) = bitmap.
:- mode append_list(in) = bitmap_uo is det.

%--------------------------------------------------%
%
% Operations to copy part of a bitmap.
%

    % copy_bits(SrcBM, SrcStartBit, DestBM, DestStartBit, NumBits)
    %
    % Overwrite NumBits bits in DestBM starting at DestStartBit with
    % the NumBits bits starting at SrcStartBit in SrcBM.
    %
:- func copy_bits(bitmap, bit_index, bitmap, bit_index, num_bits) = bitmap.
% :- mode copy_bits(bitmap_ui, in, bitmap_di, in, in) = bitmap_uo is det.
:- mode copy_bits(in, in, bitmap_di, in, in) = bitmap_uo is det.

    % copy_bits_in_bitmap(BM, SrcStartBit, DestStartBit, NumBits)
    %
    % Overwrite NumBits bits starting at DestStartBit with the NumBits
    % bits starting at SrcStartBit in the same bitmap.
    %
:- func copy_bits_in_bitmap(bitmap, bit_index, bit_index, num_bits) = bitmap.
:- mode copy_bits_in_bitmap(bitmap_di, in, in, in) = bitmap_uo is det.

    % copy_bytes(SrcBM, SrcStartByte, DestBM, DestStartByte, NumBytes)
    %
    % Overwrite NumBytes bytes in DestBM starting at DestStartByte with
    % the NumBytes bytes starting at SrcStartByte in SrcBM.
    %
:- func copy_bytes(bitmap, byte_index, bitmap, byte_index, num_bytes) = bitmap.
% :- mode copy_bytes(bitmap_ui, in, bitmap_di, in, in) = bitmap_uo is det.
:- mode copy_bytes(in, in, bitmap_di, in, in) = bitmap_uo is det.

    % copy_bytes_in_bitmap(BM, SrcStartByte, DestStartByte, NumBytes)
    %
    % Overwrite NumBytes bytes starting at DestStartByte with the NumBytes
    % bytes starting at SrcStartByte in the same bitmap.
    %
:- func copy_bytes_in_bitmap(bitmap, byte_index,
    byte_index, num_bytes) = bitmap.
:- mode copy_bytes_in_bitmap(bitmap_di, in, in, in) = bitmap_uo is det.

%--------------------------------------------------%

    % Compute a hash function for a bitmap.
    %
:- func hash(bitmap) = int.
% :- mode hash(bitmap_ui) = out is det.
:- mode hash(in) = out is det.

%--------------------------------------------------%

    % Convert a bitmap to a string of the form "<length:hex digits>",
    % e.g. "<24:10AFBD>".
    %
:- func to_string(bitmap) = string.
% :- mode to_string(bitmap_ui) = out is det.
:- mode to_string(in) = out is det.

    % Convert a string created by to_string back into a bitmap.
    % Fails if the string is not of the form created by to_string.
    %
:- func from_string(string) = bitmap.
:- mode from_string(in) = bitmap_uo is semidet.
:- pred from_string(string, bitmap).
:- mode from_string(in, bitmap_uo) is semidet.

    % As above, but throws an exception instead of failing.
    %
:- func det_from_string(string) = bitmap.
:- mode det_from_string(in) = bitmap_uo is det.

    % Convert a bitmap to a string of `1' and `0' characters, where
    % the bytes are separated by `.'.
    %
:- func to_byte_string(bitmap) = string.
% :- mode to_byte_string(bitmap_ui) = out is det.
:- mode to_byte_string(in) = out is det.

%--------------------------------------------------%
%
% Bitmap input and output predicates.
%

    % Fill a bitmap from the current binary input stream
    % or from the specified binary input stream.
    % Return the number of bytes read. On end-of-file, the number of
    % bytes read will be less than the size of the bitmap, and
    % the result will be `ok'.
    % Throws an exception if the bitmap has a partial final byte.
    %
:- pred read_bitmap(bitmap::bitmap_di, bitmap::bitmap_uo,
    int::out, io.res::out, io::di, io::uo) is det.
:- pred read_bitmap(io.binary_input_stream::in,
    bitmap::bitmap_di, bitmap::bitmap_uo,
    int::out, io.res::out, io::di, io::uo) is det.

    % read_bitmap(StartByte, NumBytes, !Bitmap, BytesRead, Result, !IO)
    %
    % Read NumBytes bytes into a bitmap starting at StartByte from the
    % current binary input stream, or from the specified binary input stream.
    % Return the number of bytes read. On end-of-file, the number of
    % bytes read will be less than NumBytes, and the result will be `ok'.
    %
:- pred read_bitmap_range(byte_index::in, num_bytes::in,
    bitmap::bitmap_di, bitmap::bitmap_uo, num_bytes::out, io.res::out,
    io::di, io::uo) is det.
:- pred read_bitmap_range(io.binary_input_stream::in,
    byte_index::in, num_bytes::in,
    bitmap::bitmap_di, bitmap::bitmap_uo, num_bytes::out, io.res::out,
    io::di, io::uo) is det.

%--------------------------------------------------%

    % Write a bitmap to the current binary output stream
    % or to the specified binary output stream. The bitmap must not contain
    % a partial final byte.
    %
:- pred write_bitmap(bitmap, io, io).
%:- mode write_bitmap(bitmap_ui, di, uo) is det.
:- mode write_bitmap(in, di, uo) is det.
:- pred write_bitmap(io.binary_output_stream, bitmap, io, io).
%:- mode write_bitmap(in, bitmap_ui, di, uo) is det.
:- mode write_bitmap(in, in, di, uo) is det.

    % write_bitmap_range(BM, StartByte, NumBytes, !IO):
    % write_bitmap_range(Stream, BM, StartByte, NumBytes, !IO):
    %
    % Write part of a bitmap to the current binary output stream
    % or to the specified binary output stream.
    %
:- pred write_bitmap_range(bitmap, int, int, io, io).
%:- mode write_bitmap_range(bitmap_ui, in, in, di, uo) is det.
:- mode write_bitmap_range(in, in, in, di, uo) is det.
:- pred write_bitmap_range(io.binary_output_stream, bitmap, int, int, io, io).
%:- mode write_bitmap_range(in, bitmap_ui, in, in, di, uo) is det.
:- mode write_bitmap_range(in, in, in, in, di, uo) is det.

%--------------------------------------------------%

:- instance stream.bulk_reader(binary_input_stream, int, bitmap, io, io.error).
:- instance stream.writer(binary_output_stream, bitmap, io).
:- instance stream.writer(binary_output_stream, bitmap.slice, io).

%--------------------------------------------------%
%--------------------------------------------------%