%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 2004-2012 The University of Melbourne.
% Copyright (C) 2014-2023 The Mercury Team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: version_array.m.
% Author: Ralph Becket <rafe@cs.mu.oz.au>.
% Stability: low.
%
% Version types are efficient pure implementations of typically imperative
% structures, subject to the following caveat: efficient access is only
% guaranteed for the "latest" version of a given structure. An older version
% incurs an access cost proportional to the number of its descendants.
%
% For example, if A0 is a version array, and A1 is created by updating A0,
% and A2 is created by updating A1, ..., and An is created by updating An-1,
% then accesses to An cost O(1) (assuming no further versions of the array
% have been created from An), but accesses to A0 cost O(n).
%
% Updates to older versions of the structure (for example A(n-1)) may have
% additional costs, for arrays this cost is O(m) where m is the size of the
% array, as the whole array is copied to make a new version array.
%
% Most version data structures come with impure, unsafe means to "rewind"
% to an earlier version, restoring that version's O(1) access times, but
% leaving later versions undefined (i.e. only do this if you are discarding
% all later versions of the structure.)
%
% The motivation for using version types is that they are ordinary ground
% structures and do not depend upon uniqueness, while in many circumstances
% offering similar levels of performance.
%
% This module implements version arrays. A version array provides O(1)
% access and update for the "latest" version of the array. "Older"
% versions of the array incur an O(k) penalty on accesses where k is
% the number of updates that have been made since.
%
% The advantage of version arrays is that in the common, singly threaded,
% case, they are almost as fast as unique arrays, but can be treated as
% ordinary ground values rather than unique values.
%
% Version arrays are zero based.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module version_array.
:- interface.

:- import_module list.
:- import_module pretty_printer.

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

:- type version_array(T).

    % An `index_out_of_bounds' is the exception thrown on out-of-bounds
    % array accesses. The string describes the predicate or function
    % reporting the error.
    %
:- type index_out_of_bounds
    --->    index_out_of_bounds(string).

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

    % empty returns the empty array.
    %
:- func empty = version_array(T).

    % init(N, X) returns an array of size N with each item initialised to X.
    %
:- func init(int, T) = version_array(T).

    % Same as empty/0 except the resulting version_array is not thread safe.
    %
    % That is your program can crash or behave strangely if you attempt to
    % concurrently access or update the array from different threads, or any
    % two arrays produced from operations on the same original array.
    % However this version is much quicker if you guarantee that you never
    % concurrently access the version array.
    %
:- func unsafe_empty = version_array(T).

    % Same as init(N, X) except the resulting version_array is not thread safe.
    %
    % That is your program can crash or behave strangely if you attempt to
    % concurrently access or update the array from different threads, or any
    % two arrays produced from operations on the same original array.
    % However this version is much quicker if you guarantee that you never
    % concurrently access the version array.
    %
:- func unsafe_init(int, T) = version_array(T).

    % version_array(Xs) returns an array constructed from the items in the list
    % Xs.
    %
:- func version_array(list(T)) = version_array(T).

    % A synonym for the above.
    %
:- func from_list(list(T)) = version_array(T).

    % from_reverse_list(Xs) returns an array constructed from the items in the
    % list Xs in reverse order.
    %
:- func from_reverse_list(list(T)) = version_array(T).

    % lookup(A, I) = X iff the I'th member of A is X.
    % (The first item has index 0).
    %
:- func lookup(version_array(T), int) = T.
:- pred lookup(version_array(T)::in, int::in, T::out) is det.

    % A ^ elem(I) = lookup(A, I)
    %
:- func version_array(T) ^ elem(int) = T.

    % set(I, X, A0, A): A is a copy of array A0 with item I updated to be X.
    % An exception is thrown if I is out of bounds.
    %
:- pred set(int::in, T::in, version_array(T)::in, version_array(T)::out)
    is det.

    % (A0 ^ elem(I) := X) = A is equivalent to set(I, X, A0, A).
    %
:- func (version_array(T) ^ elem(int) := T) = version_array(T).

    % size(A) = N if A contains N items (i.e. the valid indices for A
    % range from 0 to N - 1).
    %
:- func size(version_array(T)) = int.

    % max(A) = size(A) - 1.
    % Returns -1 for an empty array.
    %
:- func max(version_array(T)) = int.

    % is_empty(Array) is true iff Array is the empty array.
    %
:- pred is_empty(version_array(T)::in) is semidet.

    % resize(Array0, NewSize, NewValue) = Array:
    % resize(NewSize, NewValue, Array0, Array):
    %
    % Return in Array a new array whose size is NewSize.
    %
    % Each slot in Array will be filled with the value from the corresponding
    % slot in Array0, if there is one.
    %
    % When NewSize is greater than size(Array0), Array will have more slots
    % than Array0. All those extra slots will be initialised to NewValue.
    %
:- func resize(version_array(T), int, T) = version_array(T).
:- pred resize(int::in, T::in, version_array(T)::in, version_array(T)::out)
    is det.

    % copy(A) is a copy of array A. Access to the copy is O(1).
    %
:- func copy(version_array(T)) = version_array(T).

    % list(A) = Xs where Xs is the list of items in A
    % (i.e. A = version_array(Xs)).
    %
:- func list(version_array(T)) = list(T).

    % A synonym for the above.
    %
:- func to_list(version_array(T)) = list(T).

    % foldl(F, A, X) is equivalent to list.foldl(F, list(A), X).
    %
:- func foldl(func(T1, T2) = T2, version_array(T1), T2) = T2.

    % foldl(P, A, !X) is equivalent to list.foldl(P, list(A), !X).
    %
:- pred foldl(pred(T1, T2, T2), version_array(T1), T2, T2).
:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldl(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldl(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.

    % foldl2(P, A, !Acc1, !Acc2) is equivalent to
    % list.foldl2(P, list(A), !Acc1, !Acc2) but more efficient.
    %
:- pred foldl2(pred(T1, T2, T2, T3, T3), version_array(T1), T2, T2, T3, T3).
:- mode foldl2(in(pred(in, in, out, in, out) is det), in, in, out, in, out)
    is det.
:- mode foldl2(in(pred(in, in, out, mdi, muo) is det), in, in, out, mdi, muo)
    is det.
:- mode foldl2(in(pred(in, in, out, di, uo) is det), in, in, out, di, uo)
    is det.
:- mode foldl2(in(pred(in, in, out, in, out) is semidet), in,
    in, out, in, out) is semidet.
:- mode foldl2(in(pred(in, in, out, mdi, muo) is semidet), in,
    in, out, mdi, muo) is semidet.
:- mode foldl2(in(pred(in, in, out, di, uo) is semidet), in,
    in, out, di, uo) is semidet.

    % foldr(F, A, X) is equivalent to list.foldr(F, list(A), Xs).
    %
:- func foldr(func(T1, T2) = T2, version_array(T1), T2) = T2.

:- pred foldr(pred(T1, T2, T2), version_array(T1), T2, T2).
:- mode foldr(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldr(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldr(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldr(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldr(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldr(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.

:- pred foldr2(pred(T1, T2, T2, T3, T3), version_array(T1), T2, T2, T3, T3).
:- mode foldr2(in(pred(in, in, out, in, out) is det), in, in, out, in, out)
    is det.
:- mode foldr2(in(pred(in, in, out, mdi, muo) is det), in, in, out, mdi, muo)
    is det.
:- mode foldr2(in(pred(in, in, out, di, uo) is det), in, in, out, di, uo)
    is det.
:- mode foldr2(in(pred(in, in, out, in, out) is semidet), in,
    in, out, in, out) is semidet.
:- mode foldr2(in(pred(in, in, out, mdi, muo) is semidet), in,
    in, out, mdi, muo) is semidet.
:- mode foldr2(in(pred(in, in, out, di, uo) is semidet), in,
    in, out, di, uo) is semidet.

    % all_true(Pred, Array):
    %
    % True iff Pred is true for every element of Array.
    %
:- pred all_true(pred(T)::in(pred(in) is semidet), version_array(T)::in)
    is semidet.

    % all_false(Pred, Array):
    %
    % True iff Pred is false for every element of Array.
    %
:- pred all_false(pred(T)::in(pred(in) is semidet), version_array(T)::in)
    is semidet.

    % unsafe_rewind(A) produces a version of A for which all accesses are O(1).
    % Invoking this predicate renders A and all later versions undefined that
    % were derived by performing individual updates. Only use this when you are
    % absolutely certain there are no live references to A or later versions
    % of A. (A predicate version is also provided.)
    %
:- func unsafe_rewind(version_array(T)) = version_array(T).
:- pred unsafe_rewind(version_array(T)::in, version_array(T)::out) is det.

    % Convert a version_array to a pretty_printer.doc for formatting.
    %
:- func version_array_to_doc(version_array(T)) = pretty_printer.doc.
:- pragma obsolete(func(version_array_to_doc/1),
    [pretty_printer.version_array_to_doc/1]).

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