%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 2004-2012 The University of Melbourne.
% Copyright (C) 2014-2026 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: medium.
%
% 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(Size, DefaultValue):
    % uinit(Size, DefaultValue):
    %
    % Return an array of size Size, with each item initialised to DefaultValue.
    %
:- func init(int, T) = version_array(T).
:- func uinit(uint, 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/uint, except the resulting version_array is not thread safe.
    %
    % The downside of this difference is that your program can crash,
    % or behave strangely, if you ever attempt to concurrently access
    % or update a non-thread-safe version_array from different threads.
    % This is also true for any two version_arrays that were generated
    % from operations on the same original non-thread-safe version_array.
    %
    % The upside is that if you can guarantee that your program will do
    % none of the above, then non-thread-safe version arrays are much quicker
    % to access and to update in multi-threaded programs.
    %
:- func unsafe_init(int, T) = version_array(T).
:- func unsafe_uinit(uint, T) = version_array(T).

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

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

    % from_reverse_list(Items):
    %
    % Returns an array constructed from the reverse of Items.
    %
:- func from_reverse_list(list(T)) = version_array(T).

    % lookup(VersionArray, Index) = Item:
    % ulookup(VersionArray, Index) = Item:
    %
    % Return, as Item, the Index'th member of VersionArray.
    % (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.
:- func ulookup(version_array(T), uint) = T.
:- pred ulookup(version_array(T)::in, uint::in, T::out) is det.

    % VersionArray ^ elem(Index) = lookup(VersionArray, Index)
    % VersionArray ^ uelem(Index) = ulookup(VersionArray, Index)
    %
:- func elem(int, version_array(T)) = T.
:- func uelem(uint, version_array(T)) = T.

    % set(Index, Item, VersionArray0, VersionArray):
    % uset(Index, Item, VersionArray0, VersionArray):
    %
    % VersionArray is a copy of array VersionArray0,
    % with the item at Index replaced with Item.
    % Throws an exception if Index is out of bounds.
    %
:- pred set(int::in, T::in,
    version_array(T)::in, version_array(T)::out) is det.
:- pred uset(uint::in, T::in,
    version_array(T)::in, version_array(T)::out) is det.

    % (VersionArray0 ^ elem(Index) := Item) = VersionArray:
    % (VersionArray0 ^ uelem(Index) := Item) = VersionArray:
    %
    % is equivalent to set(Index, Item, VersionArray0, VersionArray).
    %
:- func 'elem :='(int, version_array(T), T) = version_array(T).
:- func 'uelem :='(uint, version_array(T), T) = version_array(T).

    % size(VersionArray) = Size:
    % usize(VersionArray) = Size:
    %
    % Return in Size the number of items in VersionArray (meaning that
    % the valid indices for VersionArray range from 0 to Size - 1).
    %
:- func size(version_array(T)) = int.
:- func usize(version_array(T)) = uint.

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

    % is_empty(VersionArray):
    %
    % Succeeds if-and-only-if VersionArray is the empty array.
    %
:- pred is_empty(version_array(T)::in) is semidet.

    % resize(VersionArray0, NewSize, DefaultValue) = VersionArray:
    % resize(NewSize, DefaultValue, VersionArray0, VersionArray):
    % uresize(VersionArray0, NewSize, DefaultValue) = VersionArray:
    % uresize(NewSize, DefaultValue, VersionArray0, VersionArray):
    %
    % Return in VersionArray a new array whose size is NewSize.
    %
    % Each slot in VersionArray will be filled with the value from
    % the corresponding slot in VersionArray0 (if there is such a slot),
    % or with DefaultValue (if there is no such slot, due to NewSize
    % being greater than size(VersionArray0)).
    %
:- 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.
:- func uresize(version_array(T), uint, T) = version_array(T).
:- pred uresize(uint::in, T::in,
    version_array(T)::in, version_array(T)::out) is det.

    % copy(VersionArray0) = VersionArray:
    %
    % Return in VersionArray a copy of VersionArray0.
    %
    % Access to the copy is O(1).
    %
:- func copy(version_array(T)) = version_array(T).

    % list(VersionArray) = Items:
    %
    % Return in Items the list of all items in VersionArray.
    % (Meaning that VersionArray = version_array(Items)).
    %
:- func list(version_array(T)) = list(T).

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

    % foldl(Func, VersionArray, Acc0) = Acc:
    %
    % Equivalent to list.foldl(Func, list(VersionArray), Acc0) = Acc,
    % but more efficient.
    %
:- func foldl(func(T, A) = A, version_array(T), A) = A.

    % foldl(Pred, VersionArray, !Acc):
    %
    % Equivalent to list.foldl(Pred, list(VersionArray), !Acc),
    % but more efficient.
    %
:- pred foldl(pred(T, A, A), version_array(T), A, A).
:- 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(Pred, VersionArray, !AccA, !AccB):
    %
    % Equivalent to list.foldl2(Pred, list(VersionArray), !AccA, !AccB),
    % but more efficient.
    %
:- pred foldl2(pred(T, A, A, B, B), version_array(T), A, A, B, B).
:- 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(Func, VersionArray, Acc0) = Acc:
    %
    % Equivalent to list.foldr(Func, list(VersionArray), Acc0) = Acc,
    % but more efficient.
    %
:- func foldr(func(T, A) = A, version_array(T), A) = A.

:- pred foldr(pred(T, A, A), version_array(T), A, A).
:- 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(T, A, A, B, B), version_array(T), A, A, B, B).
:- 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, VersionArray):
    %
    % True if-and-only-if Pred is true for every element of VersionArray.
    %
:- pred all_true(pred(T)::in(pred(in) is semidet), version_array(T)::in)
    is semidet.

    % all_false(Pred, VersionArray):
    %
    % True if-and-only-if Pred is false for every element of VersionArray.
    %
:- pred all_false(pred(T)::in(pred(in) is semidet), version_array(T)::in)
    is semidet.

    % unsafe_rewind(VersionArray0) = VersionArray:
    % unsafe_rewind(VersionArray0, VersionArray):

    % Return as VersionArray a version of VersionArray0 for which
    % all accesses are O(1).
    %
    % Invoking this predicate renders undefined both VersionArray0 and
    % all later versions derived from it by performing individual updates.
    % Use this *only* when you are absolutely certain that there are
    % no live references to either.
    %
:- 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]).

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