%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1997,1999-2000,2002-2003,2005-2006 The University of Melbourne.
% Copyright (C) 2014-2022 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: bt_array.m
% Main author: bromage.
% Stability: medium-low
%
% This file contains a set of predicates for generating and manipulating a
% bt_array data structure. This implementation allows O(log n) access and
% update time, and does not require the bt_array to be unique. If you need
% O(1) access/update time, use the array datatype instead. (`bt_array' is
% supposed to stand for either "binary tree array" or "backtrackable array".)
%
% Implementation obscurity: This implementation is biased towards larger
% indices. The access/update time for a bt_array of size N with index I is
% actually O(log(N-I)). The reason for this is so that the resize operations
% can be optimised for a (possibly very) common case, and to exploit
% accumulator recursion in some operations. See the documentation of resize
% and shrink for more details.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module bt_array.
:- interface.
:- import_module list.

:- type bt_array(T).

%--------------------------------------------------%
%
% Creating arrays.
%

    % init(Low, High, Init, Array) is true iff Array is a
    % bt_array with bounds from Low to High whose elements each equal Init.
    %
:- func init(int, int, T) = bt_array(T).
:- pred init(int::in, int::in, T::in, bt_array(T)::out) is det.

    % make_empty_array(Low, Array) is true iff Array is a
    % bt_array of size zero starting at index Low.
    %
:- func make_empty_array(int) = bt_array(T).
:- pred make_empty_array(int::in, bt_array(T)::out) is det.

%--------------------------------------------------%
%
% Reading array elements.
%

    % lookup returns the Nth element of a bt_array.
    % It is an error if the index is out of bounds.
    %
:- func lookup(bt_array(T), int) = T.
:- pred lookup(bt_array(T)::in, int::in, T::out) is det.

    % semidet_lookup is like lookup except that it fails if the index is out of
    % bounds.
    %
:- pred semidet_lookup(bt_array(T)::in, int::in, T::out) is semidet.

    % Field selection for arrays.
    % Array ^ elem(Index) = lookup(Array, Index).
    %
:- func elem(int, bt_array(T)) = T.

%--------------------------------------------------%
%
% Writing array elements.
%

    % set sets the nth element of a bt_array, and returns the resulting
    % bt_array. It is an error if the index is out of bounds.
    %
:- func set(bt_array(T), int, T) = bt_array(T).
:- pred set(bt_array(T)::in, int::in, T::in, bt_array(T)::out) is det.

    % set sets the nth element of a bt_array, and returns the
    % resulting bt_array (good opportunity for destructive update ;-).
    % It fails if the index is out of bounds.
    %
:- pred semidet_set(bt_array(T)::in, int::in, T::in, bt_array(T)::out)
    is semidet.

    % Field update for arrays.
    % (Array ^ elem(Index) := Value) = set(Array, Index, Value).
    %
:- func 'elem :='(int, bt_array(T), T) = bt_array(T).

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

    % Returns the lower bound of the array.
    %
:- func min(bt_array(_T)) = int.
:- pred min(bt_array(_T)::in, int::out) is det.

    % Returns the upper bound of the array.
    % Returns lower bound - 1 for an empty array.
    %
:- func max(bt_array(_T)) = int.
:- pred max(bt_array(_T)::in, int::out) is det.

    % Returns the length of the array,
    % i.e. upper bound - lower bound + 1.
    %
:- func size(bt_array(_T)) = int.
:- pred size(bt_array(_T)::in, int::out) is det.

    % bounds(Array, Min, Max) returns the lower and upper bounds of a bt_array.
    % The upper bound will be the lower bound - 1 for an empty array.
    %
:- pred bounds(bt_array(_T)::in, int::out, int::out) is det.

    % in_bounds checks whether an index is in the bounds
    % of a bt_array.
    %
:- pred in_bounds(bt_array(_T)::in, int::in) is semidet.

%--------------------------------------------------%
%
% Resizing arrays.
%

    % `resize(BtArray0, Lo, Hi, Item, BtArray)' is true if BtArray
    % is a bt_array created by expanding or shrinking BtArray0 to fit the
    % bounds (Lo, Hi). If the new bounds are not wholly contained within
    % the bounds of BtArray0, Item is used to fill out the other places.
    %
    % Note: This operation is optimised for the case where the lower bound
    % of the new bt_array is the same as that of the old bt_array. In that
    % case, the operation takes time proportional to the absolute difference
    % in size between the two bt_arrays. If this is not the case, it may take
    % time proportional to the larger of the two bt_arrays.
    %
:- func resize(bt_array(T), int, int, T) = bt_array(T).
:- pred resize(bt_array(T)::in, int::in, int::in, T::in,
    bt_array(T)::out) is det.

    % shrink(BtArray0, Lo, Hi, Item, BtArray) is true if BtArray
    % is a bt_array created by shrinking BtArray0 to fit the bounds (Lo, Hi).
    % It is an error if the new bounds are not wholly within the bounds of
    % BtArray0.
    %
    % Note: This operation is optimised for the case where the lower bound
    % of the new bt_array is the same as that of the old bt_array. In that
    % case, the operation takes time proportional to the absolute difference
    % in size between the two bt_arrays. If this is not the case, it may take
    % time proportional to the larger of the two bt_arrays.
    %
:- func shrink(bt_array(T), int, int) = bt_array(T).
:- pred shrink(bt_array(T)::in, int::in, int::in, bt_array(T)::out)
    is det.

%--------------------------------------------------%
%
% Conversions between bt_arrays and lists.
%

    % from_list(Low, List, BtArray) takes a list (of possibly zero
    % length), and returns a bt_array containing % those elements in the same
    % order that they occurred in the list. The lower bound of the new array
    % is Low.
    %
:- func from_list(int, list(T)) = bt_array(T).
:- pred from_list(int::in, list(T)::in, bt_array(T)::out) is det.

    % to_list takes a bt_array and returns a list containing
    % the elements of the bt_array in the same order that they occurred
    % in the bt_array.
    %
:- func to_list(bt_array(T)) = list(T).
:- pred to_list(bt_array(T)::in, list(T)::out) is det.

    % fetch_items takes a bt_array and a lower and upper index,
    % and places those items in the bt_array between these indices into a list.
    % It is an error if either index is out of bounds.
    %
:- func fetch_items(bt_array(T), int, int) = list(T).
:- pred fetch_items(bt_array(T)::in, int::in, int::in, list(T)::out)
    is det.

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

    % bsearch takes a bt_array, an element to be matched and a
    % comparison predicate and returns the position of the first occurrence
    % in the bt_array of an element which is equivalent to the given one
    % in the ordering provided. Assumes the bt_array is sorted according
    % to this ordering. Fails if the element is not present.
    %
:- pred bsearch(bt_array(T)::in, T::in,
    comparison_pred(T)::in(comparison_pred), int::out) is semidet.

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