%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 2002-2011 The University of Melbourne.
% Copyright (C) 2013-2018, 2021-2022, 2024-2025 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: cord.m.
% Author: Ralph Becket <rafe@cs.mu.oz.au>
% Stability: high.
%
% Like lists, cords contain a sequence of elements. The difference is that
% many operations that construct cords (such as appending two cords together,
% or adding a new element to the end of a cord) are O(1) operations, not O(N).
% In general, if you want to construct a list in any order other than
% strictly back-to-front, then you should consider constructing a cord instead,
% and then converting the final cord to a list.
%
% The reason why such lower asymptotic complexities are possible for many
% operations is that cords are essentially binary trees that store elements
% in their leaf nodes.
%
% The price of lower complexity for cord-construction operations is
% (a) higher complexity for some inspection operations, such as head_tail/3,
% and (b) higher constant factors for most operations.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module cord.
:- interface.
:- import_module list.
%--------------------------------------------------%
% Conceptually, a cord contains a list of elements of type T.
%
% Cords that contain the same elements in the same order will not
% necessarily have the same representation. Therefore it is possible
% that they may not unify, and that comparing them may return a result
% other than "equal".
%
% The exception to this rule is that the empty cord does have a
% unique representation.
%
% You can test two cords for equality using the cord.equal predicate below.
%
:- type cord(T).
%--------------------------------------------------%
%
% Constructing a cord from scratch.
%
% The init and empty functions do the same job: return the empty cord.
%
% list(cord(init)) = [].
% list(cord(empty)) = [].
%
:- func init = cord(T).
:- func empty = cord(T).
% Return a cord containing just the given element.
%
% list(cord(singleton(X))) = [X].
%
:- func singleton(T) = cord(T).
%--------------------------------------------------%
%
% Constructing a new cord from one existing cord.
%
% cons(Element, Cord0) = Cord:
% cons(Element, Cord0, Cord):
%
% Return Cord, which is the cord you get when you add Element
% to the front of Cord0.
%
% list(cons(Element, Cord0)) = [Element | list(Cord0)]
%
% This is an O(1) operation.
%
:- func cons(T, cord(T)) = cord(T).
:- pred cons(T::in, cord(T)::in, cord(T)::out) is det.
% cons_list(List, Cord0) = Cord:
% cons_list(List, Cord0, Cord):
%
% Return Cord, which is the cord you get when you add List
% to the front of Cord0.
%
% list(cons_list(List, Cord0)) = List ++ list(Cord0)
%
% This is an O(1) operation.
%
:- func cons_list(list(T), cord(T)) = cord(T).
:- pred cons_list(list(T)::in, cord(T)::in, cord(T)::out) is det.
% snoc(Cord0, Element) = Cord:
% snoc(Element, Cord0, Cord):
%
% Return Cord, which is the cord you get when you add Element
% to the end of Cord0. (The argument order of the predicate version
% simplifies its use when the cord is represented by a state variable.)
%
% list(snoc(Cord0, Element)) = list(Cord0) ++ [Element]
%
% This is an O(1) operation.
%
:- func snoc(cord(T), T) = cord(T).
:- pred snoc(T::in, cord(T)::in, cord(T)::out) is det.
% snoc_list(Cord0, List) = Cord:
% snoc_list(List, Cord0, Cord):
%
% Return Cord, which is the cord you get when you add List
% to the end of Cord0. (The argument order of the predicate version
% simplifies its use when the cord is represented by a state variable.)
%
% list(snoc_list(Cord0, List)) = list(Cord0) ++ List
%
% This is an O(1) operation.
%
:- func snoc_list(cord(T), list(T)) = cord(T).
:- pred snoc_list(list(T)::in, cord(T)::in, cord(T)::out) is det.
%--------------------------------------------------%
%
% Constructing a new cord from two or more existing cords.
%
% CA ++ CB = C:
%
% Return C, which is the cord you get when you append CB to the end of CA.
%
% list(CA ++ CB) = list(CA) ++ list(CB)
%
% This is an O(1) operation.
% (With lists, the complexity would be O(len(CA)).)
%
:- func cord(T) ++ cord(T) = cord(T).
% Append together a list of cords.
%
:- func cord_list_to_cord(list(cord(T))) = cord(T).
% Reverse the given list (of cords), and then
% append together the resulting list of cords.
%
:- func rev_cord_list_to_cord(list(cord(T))) = cord(T).
% Cord = condense(CordOfCords):
%
% Cord is the result of concatenating all the elements of CordOfCords.
%
:- func condense(cord(cord(T))) = cord(T).
%--------------------------------------------------%
%
% Simple tests on cords.
%
% Succeed if-and-only-if the given cord is empty.
%
:- pred is_empty(cord(T)::in) is semidet.
% Succeed if-and-only-if the given cord is not empty.
%
:- pred is_non_empty(cord(T)::in) is semidet.
% If the given cord contains exactly one element, then return that element.
% Otherwise, fail.
%
:- pred is_singleton(cord(T)::in, T::out) is semidet.
%--------------------------------------------------%
%
% Getting single elements out of cords.
%
% head(Cord, Head):
% get_first(Cord, Head):
%
% Return just the first element in Cord, if Cord contains any elements.
% Otherwise, fail.
%
% head(Cord, Head) => some [Tail]: list(Cord) = [Head] ++ Tail.
% not head(Cord, _) => Cord = empty
%
% This is an O(n) operation.
%
:- pred head(cord(T)::in, T::out) is semidet.
:- pred get_first(cord(T)::in, T::out) is semidet.
% head_tail(Cord, Head, Tail):
%
% If the cord Cord is not empty, then return its first element as Head,
% and the cord containing all the remaining elements as T.
% If the cord is empty, then fail.
%
% head_tail(Cord, Head, Tail) => list(Cord) = [Head | list(Tail)]
% not head_tail(Cord, _, _) => Cord = empty
%
% This is an O(n) operation, although traversing an entire cord with
% head_tail/3 gives O(1) amortized cost for each call.
%
:- pred head_tail(cord(T)::in, T::out, cord(T)::out) is semidet.
% get_last(Cord, Last):
%
% Return just the last element in Cord, if Cord contains any elements.
% Otherwise, fail.
%
% get_last(Cord, Lasr) => some [List]: list(Cord) = List ++ [Last].
% not get_last(Cord, _) => Cord = empty
%
% This is an O(n) operation.
%
:- pred get_last(cord(T)::in, T::out) is semidet.
% split_last(Cord, Prev, Last):
%
% If the cord Cord is not empty, then return its last element as Last,
% and the cord containing all the previous elements as Prev.
% If the cord is empty, then fail.
%
% split_last(Cord, Prev, Last) => list(Cord) = list(Prev) ++ [Last].
% not split_last(Cord, _, _) => Cord = empty
%
% This is an O(n) operation, although traversing an entire cord with
% split_last/3 gives O(1) amortized cost for each call.
%
:- pred split_last(cord(T)::in, cord(T)::out, T::out) is semidet.
%--------------------------------------------------%
%
% Operations on whole cords.
%
% length(C) = list.length(list(C))
%
% This is an O(n) operation.
%
:- func length(cord(T)) = int.
% member(X, C) <=> list.member(X, list(C)).
%
:- pred member(T::out, cord(T)::in) is nondet.
% equal(CA, CB):
%
% Succeed if-and-only-if CA and CB contain the same elements
% in the same % order.
%
% equal(CA, CB) <=> list(CA) = list(CB).
% (Note: the current implementation works exactly this way.)
%
% This is an O(n) operation where n = length(CA) + length(CB).
%
:- pred equal(cord(T)::in, cord(T)::in) is semidet.
%--------------------------------------------------%
%
% Converting lists to cords.
%
% from_list(List) = Cord:
%
% Return a cord containing the same elements in the same order as List.
%
% list(from_list(Xs)) = Xs
%
% This is an O(1) operation.
%
:- func from_list(list(T)) = cord(T).
%--------------------------------------------------%
%
% Converting cords to lists.
%
% list(Cord) = List:
% to_list(Cord) = List:
%
% Return a list containing the same elements in the same order as Cord.
%
% The list of data in a cord:
%
% list(empty ) = []
% list(from_list(Xs)) = Xs
% list(cons(X, C) ) = [X | list(C)]
% list(TA ++ TB ) = list(TA) ++ list(TB)
%
:- func list(cord(T)) = list(T).
:- func to_list(cord(T)) = list(T).
% rev_list(Cord) = RevList:
% to_rev_list(Cord) = RevList:
%
% Return a list containing the same elements as Cord,
% but in the reverse order.
%
% rev_list(Cord) = list.reverse(list(Cord).
%
:- func rev_list(cord(T)) = list(T).
:- func to_rev_list(cord(T)) = list(T).
% Append together a list of cords, and return the result as a list.
%
:- func cord_list_to_list(list(cord(T))) = list(T).
% Reverse the given list (of cords), append together
% the resulting list of cords, and return it as a list.
%
:- func rev_cord_list_to_list(list(cord(T))) = list(T).
%--------------------------------------------------%
%
% Some standard higher order operations.
%
% find_first_match(Pred, Cord, FirstMatch):
%
% Return as FirstMatch the first element E in Cord
% for which Pred(E) is true. If there is no such element, fail.
%
:- pred find_first_match(pred(T)::in(pred(in) is semidet),
cord(T)::in, T::out) is semidet.
% map(Func, Cord) = MappedCord:
%
% Apply Func to every element of Cord, and return the result.
%
% list(map(Func, Cord)) = list.map(Func, list(Cord))
%
:- func map(func(T) = U, cord(T)) = cord(U).
% map_pred(Pred, Cord, MappedCord):
%
% Apply Pred to every element of Cord, and return the result.
%
% cord.map_pred(Pred, Cord, MappedCord), MappedList = cord.list(MappedCord)
% is equivalent to
% list.map(Pred, cord.list(Cord), MappedList)
%
:- pred map_pred(pred(T, U)::in(pred(in, out) is det),
cord(T)::in, cord(U)::out) is det.
% filter(Pred, Cord, TrueCord):
%
% For each member E of Cord,
% - if Pred(E) is true, then include E in TrueCord.
%
% The order of the included elements is preserved.
%
:- pred filter(pred(T)::in(pred(in) is semidet),
cord(T)::in, cord(T)::out) is det.
% filter(Pred, Cord, TrueCord, FalseCord):
%
% For each member E of Cord,
% - if Pred(E) is true, then include E in TrueCord.
% - if Pred(E) is false, then include E in FalseCord.
%
% The order of the included elements is preserved.
%
:- pred filter(pred(T)::in(pred(in) is semidet),
cord(T)::in, cord(T)::out, cord(T)::out) is det.
%--------------------------------------------------%
%
% Foldl operations.
%
% foldl(F, C, A) = list.foldl(F, list(C), A).
%
:- func foldl(func(T, A) = A, cord(T), A) = A.
% foldl_pred(P, C, !AccA)
%
% Equivalent to list.foldl(P, list(C), !AccA), but faster.
%
:- pred foldl_pred(pred(T, A, A), cord(T), A, A).
:- mode foldl_pred(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl_pred(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldl_pred(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldl_pred(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
% foldl2(P, C, !AccA, !AccB)
%
% Equivalent to list.foldl2(P, list(C), !AccA, !AccB), but faster.
%
:- pred foldl2(pred(T, A, A, B, B), cord(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.
% foldl3(P, C, !AccA, !AccB, !AccC)
%
% Equivalent to list.foldl3(P, list(C), !AccA, !AccB, !AccC), but faster.
%
:- pred foldl3(pred(T, A, A, B, B, C, C), cord(T), A, A, B, B, C, C).
:- mode foldl3(in(pred(in, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out) is det.
:- mode foldl3(in(pred(in, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, mdi, muo) is det.
:- mode foldl3(in(pred(in, in, out, in, out, di, uo) is det),
in, in, out, in, out, di, uo) is det.
:- mode foldl3(in(pred(in, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out) is semidet.
:- mode foldl3(in(pred(in, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3(in(pred(in, in, out, in, out, di, uo) is semidet),
in, in, out, in, out, di, uo) is semidet.
%--------------------------------------------------%
%
% Foldr operations.
%
% foldr(F, C, A) = list.foldr(F, list(C), A).
%
:- func foldr(func(T, A) = A, cord(T), A) = A.
% foldr(F, C, !AccA)
%
% Equivalent to list.foldr(F, list(C), !AccA), but faster.
%
:- pred foldr_pred(pred(T, A, A), cord(T), A, A).
:- mode foldr_pred(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldr_pred(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldr_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldr_pred(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldr_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldr_pred(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.
% foldr2(P, C, !AccA, !AccB):
%
% Equivalent to list.foldr2(P, list(C), !AccA, !AccB), but faster.
%
:- pred foldr2(pred(T, A, A, B, B), cord(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.
% foldr3(P, C, !AccA, !AccB,! AccC):
%
% Equivalent to list.foldr3(P, list(C), !AccA, !AccB, !AccC), but faster.
%
:- pred foldr3(pred(T, A, A, B, B, C, C), cord(T), A, A, B, B, C, C).
:- mode foldr3(in(pred(in, in, out, in, out, in, out) is det), in,
in, out, in, out, in, out) is det.
:- mode foldr3(in(pred(in, in, out, in, out, mdi, muo) is det), in,
in, out, in, out, mdi, muo) is det.
:- mode foldr3(in(pred(in, in, out, in, out, di, uo) is det), in,
in, out, in, out, di, uo) is det.
:- mode foldr3(in(pred(in, in, out, in, out, in, out) is semidet), in,
in, out, in, out, in, out) is semidet.
:- mode foldr3(in(pred(in, in, out, in, out, mdi, muo) is semidet), in,
in, out, in, out, mdi, muo) is semidet.
:- mode foldr3(in(pred(in, in, out, in, out, di, uo) is semidet), in,
in, out, in, out, di, uo) is semidet.
%--------------------------------------------------%
%
% Map_foldl operations.
%
% map_foldl(P, CA, CB, !Acc):
%
% This predicate calls P on each element of the input cord, working
% left to right. Each call to P transforms an element of the input cord
% to the corresponding element of the output cord, and updates the
% accumulator.
%
:- pred map_foldl(pred(T1, T2, A, A), cord(T1), cord(T2), A, A).
:- mode map_foldl(in(pred(in, out, in, out) is det), in, out, in, out)
is det.
:- mode map_foldl(in(pred(in, out, mdi, muo) is det), in, out, mdi, muo)
is det.
:- mode map_foldl(in(pred(in, out, di, uo) is det), in, out, di, uo)
is det.
:- mode map_foldl(in(pred(in, out, in, out) is semidet), in, out, in, out)
is semidet.
:- mode map_foldl(in(pred(in, out, mdi, muo) is semidet), in, out, mdi, muo)
is semidet.
:- mode map_foldl(in(pred(in, out, di, uo) is semidet), in, out, di, uo)
is semidet.
% As above, but with two accumulators.
%
:- pred map_foldl2(pred(T1, T2, A, A, B, B)::
in(pred(in, out, in, out, in, out) is det),
cord(T1)::in, cord(T2)::out, A::in, A::out, B::in, B::out) is det.
% As above, but with three accumulators.
%
:- pred map_foldl3(pred(T1, T2, A, A, B, B, C, C)::
in(pred(in, out, in, out, in, out, in, out) is det),
cord(T1)::in, cord(T2)::out, A::in, A::out, B::in, B::out, C::in, C::out)
is det.
%--------------------------------------------------%
%--------------------------------------------------%