12 bt_array
%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%--------------------------------------------------%
% Copyright (C) 1997, 1999-2000, 2002-2003, 2005-2006 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
% Public License - see the file COPYING.LIB in the Mercury distribution.
%--------------------------------------------------%
%
% File: bt_array.m
% Main author: bromage.
% Stability: medium-low
%
% This file contains a set of predicates for generating an 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 bt_array.resize and bt_array.shrink for more details.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module bt_array.
:- interface.
:- import_module list.
:- type bt_array(T).
%--------------------------------------------------%
% bt_array.make_empty_array(Low, Array) is true iff Array is a
% bt_array of size zero starting at index Low.
%
:- pred bt_array.make_empty_array(int::in, bt_array(T)::out) is det.
:- func bt_array.make_empty_array(int) = bt_array(T).
% bt_array.init(Low, High, Init, Array) is true iff Array is a
% bt_array with bounds from Low to High whose elements each equal Init.
%
:- pred bt_array.init(int::in, int::in, T::in, bt_array(T)::out) is det.
:- func bt_array.init(int, int, T) = bt_array(T).
%--------------------------------------------------%
% array.min returns the lower bound of the array.
%
:- pred bt_array.min(bt_array(_T)::in, int::out) is det.
:- func bt_array.min(bt_array(_T)) = int.
% array.max returns the upper bound of the array.
%
:- pred bt_array.max(bt_array(_T)::in, int::out) is det.
:- func bt_array.max(bt_array(_T)) = int.
% array.size returns the length of the array,
% i.e. upper bound - lower bound + 1.
%
:- pred bt_array.size(bt_array(_T)::in, int::out) is det.
:- func bt_array.size(bt_array(_T)) = int.
% bt_array.bounds returns the upper and lower bounds of a bt_array.
%
:- pred bt_array.bounds(bt_array(_T)::in, int::out, int::out) is det.
% bt_array.in_bounds checks whether an index is in the bounds
% of a bt_array.
%
:- pred bt_array.in_bounds(bt_array(_T)::in, int::in) is semidet.
%--------------------------------------------------%
% bt_array.lookup returns the Nth element of a bt_array.
% It is an error if the index is out of bounds.
%
:- pred bt_array.lookup(bt_array(T)::in, int::in, T::out) is det.
:- func bt_array.lookup(bt_array(T), int) = T.
% bt_array.semidet_lookup is like bt_array.lookup except that it fails
% if the index is out of bounds.
%
:- pred bt_array.semidet_lookup(bt_array(T)::in, int::in, T::out) is semidet.
% bt_array.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.
%
:- pred bt_array.set(bt_array(T)::in, int::in, T::in, bt_array(T)::out)
is det.
:- func bt_array.set(bt_array(T), int, T) = bt_array(T).
% bt_array.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 bt_array.semidet_set(bt_array(T)::in, int::in, T::in,
bt_array(T)::out) is semidet.
% `bt_array.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.
%
:- pred bt_array.resize(bt_array(T)::in, int::in, int::in, T::in,
bt_array(T)::out) is det.
:- func bt_array.resize(bt_array(T), int, int, T) = bt_array(T).
% bt_array.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.
%
:- pred bt_array.shrink(bt_array(T)::in, int::in, int::in, bt_array(T)::out)
is det.
:- func bt_array.shrink(bt_array(T), int, int) = bt_array(T).
% bt_array.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'.
:- pred bt_array.from_list(int::in, list(T)::in, bt_array(T)::out) is det.
:- func bt_array.from_list(int, list(T)) = bt_array(T).
% bt_array.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.
%
:- pred bt_array.to_list(bt_array(T)::in, list(T)::out) is det.
:- func bt_array.to_list(bt_array(T)) = list(T).
% bt_array.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.
%
:- pred bt_array.fetch_items(bt_array(T)::in, int::in, int::in, list(T)::out)
is det.
:- func bt_array.fetch_items(bt_array(T), int, int) = list(T).
% bt_array.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 bt_array.bsearch(bt_array(T)::in, T::in,
comparison_pred(T)::in(comparison_pred), int::out) is semidet.
% Field selection for arrays.
% Array ^ elem(Index) = bt_array.lookup(Array, Index).
%
:- func bt_array.elem(int, bt_array(T)) = T.
% Field update for arrays.
% (Array ^ elem(Index) := Value) = bt_array.set(Array, Index, Value).
%
:- func 'elem :='(int, bt_array(T), T) = bt_array(T).
%--------------------------------------------------%