Next: , Previous: time, Up: Top   [Contents]


100 tree234

%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1994-1997,1999-2000,2002-2012 The University of Melbourne.
% Copyright (C) 2013-2018 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: tree234.m.
% Main author: conway.
% Stability: medium.
%
% This module implements a map (dictionary) using 2-3-4 trees - see
% map.m for further documentation.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module tree234.
:- interface.

:- import_module assoc_list.
:- import_module list.
:- import_module pretty_printer.
:- import_module term.

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

:- type tree234(K, V).

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

:- func init = tree234(K, V).
:- pred init(tree234(K, V)::uo) is det.

:- func singleton(K, V) = tree234(K, V).

:- pred is_empty(tree234(K, V)::in) is semidet.

    % True if both trees have the same set of key-value pairs, regardless of
    % how the trees were constructed.
    %
    % Unifying trees does not work as one might expect because the internal
    % structures of two trees that contain the same set of key-value pairs
    % may be different.
    %
:- pred equal(tree234(K, V)::in, tree234(K, V)::in) is semidet.

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

:- pred member(tree234(K, V)::in, K::out, V::out) is nondet.

:- pred search(tree234(K, V)::in, K::in, V::out) is semidet.

:- func lookup(tree234(K, V), K) = V.
:- pred lookup(tree234(K, V)::in, K::in, V::out) is det.

    % Search for a key-value pair using the key. If there is no entry
    % for the given key, returns the pair for the next lower key instead.
    % Fails if there is no key with the given or lower value.
    %
:- pred lower_bound_search(tree234(K, V)::in, K::in, K::out, V::out)
    is semidet.

    % Search for a key-value pair using the key. If there is no entry
    % for the given key, returns the pair for the next lower key instead.
    % Throws an exception if there is no key with the given or lower value.
    %
:- pred lower_bound_lookup(tree234(K, V)::in, K::in, K::out, V::out)
    is det.

    % Search for a key-value pair using the key. If there is no entry
    % for the given key, returns the pair for the next higher key instead.
    % Fails if there is no key with the given or higher value.
    %
:- pred upper_bound_search(tree234(K, V)::in, K::in, K::out, V::out)
    is semidet.

    % Search for a key-value pair using the key. If there is no entry
    % for the given key, returns the pair for the next higher key instead.
    % Throws an exception if there is no key with the given or higher value.
    %
:- pred upper_bound_lookup(tree234(K, V)::in, K::in, K::out, V::out)
    is det.

:- func max_key(tree234(K, V)) = K is semidet.

:- func min_key(tree234(K, V)) = K is semidet.

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

    % Insert the given key/value pair into the tree. If the key is already
    % in the tree, fail.
    %
:- pred insert(K::in, V::in, tree234(K, V)::in, tree234(K, V)::out)
    is semidet.

    % search_insert(K, V, MaybeOldV, !Tree):
    %
    % Search for the key K in the tree. If the key is already in the tree,
    % with corresponding value OldV, set MaybeOldV to yes(OldV). If it is
    % not in the tree, then insert it into the tree with value V, and set
    % MaybeOldV to no.
    %
:- pred search_insert(K::in, V::in, maybe(V)::out,
    tree234(K, V)::in, tree234(K, V)::out) is det.

    % Update the value corresponding to the given key in the tree.
    % If the key is not already in the tree, fail.
    %
:- pred update(K::in, V::in, tree234(K, V)::in, tree234(K, V)::out)
    is semidet.

    % set(K, V, !Tree):
    %
    % Set the value corresponding to K to V, regardless of whether K is
    % already in the tree or not.
    %
:- func set(tree234(K, V), K, V) = tree234(K, V).
:- pred set(K::in, V::in, tree234(K, V)::in, tree234(K, V)::out) is det.

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

    % Update the value at the given key by applying the supplied
    % transformation to it. This is faster than first searching for
    % the value and then updating it.
    %
:- pred transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
    tree234(K, V)::in, tree234(K, V)::out) is semidet.

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

    % Delete the given key from the tree if it is there.
    %
:- func delete(tree234(K, V), K) = tree234(K, V).
:- pred delete(K::in, tree234(K, V)::in, tree234(K, V)::out) is det.

    % If the given key exists in the tree, return it and then delete the pair.
    % Otherwise, fail.
    %
:- pred remove(K, V, tree234(K, V), tree234(K, V)).
:- mode remove(in, out, in, out) is semidet.

    % Remove the smallest key from the tree, and return both it and the value
    % corresponding to it. If the tree is empty, fail.
    %
:- pred remove_smallest(K, V, tree234(K, V), tree234(K, V)).
:- mode remove_smallest(out, out, in, out) is semidet.

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

    % Given a tree234, return a list of all the keys in the tree.
    % The list that is returned is in sorted order (ascending on keys).
    %
:- func keys(tree234(K, V)) = list(K).
:- pred keys(tree234(K, V)::in, list(K)::out) is det.

    % Given a tree234, return a list of all the values in the tree.
    % The list that is returned is in sorted order (ascending on the original
    % keys, but not sorted on the values).
    %
:- func values(tree234(K, V)) = list(V).
:- pred values(tree234(K, V)::in, list(V)::out) is det.

    % Given a tree234, return lists of all the keys and values in the tree.
    % The key list is in sorted order (ascending on keys).
    % The values list is in sorted order (ascending on their keys,
    % but not on the values themselves).
    %
:- pred keys_and_values(tree234(K, V)::in, list(K)::out, list(V)::out) is det.

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

    % Count the number of elements in a tree.
    %
:- func count(tree234(K, V)) = int.
:- pred count(tree234(K, V)::in, int::out) is det.

    % Given a tree234, return an association list of all the keys and values
    % in the tree. The association list that is returned is sorted on the keys.
    %
:- func tree234_to_assoc_list(tree234(K, V)) = assoc_list(K, V).
:- pred tree234_to_assoc_list(tree234(K, V)::in,
    assoc_list(K, V)::out) is det.

:- func assoc_list_to_tree234(assoc_list(K, V)) = tree234(K, V).
:- pred assoc_list_to_tree234(assoc_list(K, V)::in,
    tree234(K, V)::out) is det.

    % Given an assoc list of keys and values that are sorted on the keys
    % in ascending order (with no duplicate keys), convert it directly
    % to a tree.
    %
:- pred from_sorted_assoc_list(assoc_list(K, V)::in,
    tree234(K, V)::out) is det.

    % Given an assoc list of keys and values that are sorted on the keys
    % in descending order (with no duplicate keys), convert it directly
    % to a tree.
    %
:- pred from_rev_sorted_assoc_list(assoc_list(K, V)::in,
    tree234(K, V)::out) is det.

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

:- func foldl(func(K, V, A) = A, tree234(K, V), A) = A.

:- pred foldl(pred(K, V, A, A), tree234(K, V), A, A).
:- mode foldl(pred(in, in, in, out) is det, in, in, out) is det.
:- mode foldl(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode foldl(pred(in, in, in, out) is semidet, in, in, out) is semidet.
:- mode foldl(pred(in, in, mdi, muo) is semidet, in, mdi, muo) is semidet.
:- mode foldl(pred(in, in, di, uo) is semidet, in, di, uo) is semidet.
:- mode foldl(pred(in, in, in, out) is cc_multi, in, in, out) is cc_multi.
:- mode foldl(pred(in, in, di, uo) is cc_multi, in, di, uo) is cc_multi.
:- mode foldl(pred(in, in, mdi, muo) is cc_multi, in, mdi, muo) is cc_multi.

:- pred foldl2(pred(K, V, A, A, B, B), tree234(K, V), A, A, B, B).
:- mode foldl2(pred(in, in, in, out, in, out) is det,
    in, in, out, in, out) is det.
:- mode foldl2(pred(in, in, in, out, mdi, muo) is det,
    in, in, out, mdi, muo) is det.
:- mode foldl2(pred(in, in, in, out, di, uo) is det,
    in, in, out, di, uo) is det.
:- mode foldl2(pred(in, in, di, uo, di, uo) is det,
    in, di, uo, di, uo) is det.
:- mode foldl2(pred(in, in, in, out, in, out) is semidet,
    in, in, out, in, out) is semidet.
:- mode foldl2(pred(in, in, in, out, mdi, muo) is semidet,
    in, in, out, mdi, muo) is semidet.
:- mode foldl2(pred(in, in, in, out, di, uo) is semidet,
    in, in, out, di, uo) is semidet.
:- mode foldl2(pred(in, in, in, out, in, out) is cc_multi,
    in, in, out, in, out) is cc_multi.
:- mode foldl2(pred(in, in, in, out, mdi, muo) is cc_multi,
    in, in, out, mdi, muo) is cc_multi.
:- mode foldl2(pred(in, in, in, out, di, uo) is cc_multi,
    in, in, out, di, uo) is cc_multi.
:- mode foldl2(pred(in, in, di, uo, di, uo) is cc_multi,
    in, di, uo, di, uo) is cc_multi.

:- pred foldl3(pred(K, V, A, A, B, B, C, C), tree234(K, V),
    A, A, B, B, C, C).
:- mode foldl3(pred(in, in, in, out, in, out, in, out) is det,
    in, in, out, in, out, in, out) is det.
:- mode foldl3(pred(in, in, in, out, in, out, mdi, muo) is det,
    in, in, out, in, out, mdi, muo) is det.
:- mode foldl3(pred(in, in, in, out, in, out, di, uo) is det,
    in, in, out, in, out, di, uo) is det.
:- mode foldl3(pred(in, in, in, out, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo) is det.
:- mode foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, di, uo) is det.
:- mode foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
    in, in, out, in, out, in, out) is semidet.
:- mode foldl3(pred(in, in, in, out, in, out, mdi, muo) is semidet,
    in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3(pred(in, in, in, out, in, out, di, uo) is semidet,
    in, in, out, in, out, di, uo) is semidet.

:- pred foldl4(pred(K, V, A, A, B, B, C, C, D, D), tree234(K, V),
    A, A, B, B, C, C, D, D).
:- mode foldl4(pred(in, in, in, out, in, out, in, out, in, out)
    is det,
    in, in, out, in, out, in, out, in, out) is det.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, mdi, muo)
    is det,
    in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, di, uo) is det,
    in, in, out, in, out, in, out, di, uo) is det.
:- mode foldl4(pred(in, in, in, out, in, out, di, uo, di, uo) is det,
    in, in, out, in, out, di, uo, di, uo) is det.
:- mode foldl4(pred(in, in, in, out, di, uo, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo, di, uo) is det.
:- mode foldl4(pred(in, in, di, uo, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, di, uo, di, uo) is det.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, in, out)
    is semidet,
    in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl4(pred(in, in, in, out, in, out, in, out, di, uo)
    is semidet,
    in, in, out, in, out, in, out, di, uo) is semidet.

:- pred foldl5(pred(K, V, A, A, B, B, C, C, D, D, E, E), tree234(K, V),
    A, A, B, B, C, C, D, D, E, E).
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, in, out)
    is det,
    in, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, mdi, muo)
    is det,
    in, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, di, uo)
    is det,
    in, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, in, out)
    is semidet,
    in, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl5(pred(in, in, in, out, in, out, in, out, in, out, di, uo)
    is semidet,
    in, in, out, in, out, in, out, in, out, di, uo) is semidet.

:- pred foldl6(pred(K, V, A, A, B, B, C, C, D, D, E, E, F, F), tree234(K, V),
    A, A, B, B, C, C, D, D, E, E, F, F).
:- mode foldl6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, in, out) is det,
    in, in, out, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldl6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is det,
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, di, uo) is det,
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldl6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, in, out) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, di, uo) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet.

:- pred foldl_values(pred(V, A, A), tree234(K, V), A, A).
:- mode foldl_values(pred(in, in, out) is det, in, in, out) is det.
:- mode foldl_values(pred(in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldl_values(pred(in, di, uo) is det, in, di, uo) is det.
:- mode foldl_values(pred(in, in, out) is semidet, in, in, out)
    is semidet.
:- mode foldl_values(pred(in, mdi, muo) is semidet, in, mdi, muo)
    is semidet.
:- mode foldl_values(pred(in, di, uo) is semidet, in, di, uo)
    is semidet.
:- mode foldl_values(pred(in, in, out) is cc_multi, in, in, out)
    is cc_multi.
:- mode foldl_values(pred(in, di, uo) is cc_multi, in, di, uo)
    is cc_multi.
:- mode foldl_values(pred(in, mdi, muo) is cc_multi, in, mdi, muo)
    is cc_multi.

:- pred foldl2_values(pred(V, A, A, B, B), tree234(K, V), A, A, B, B).
:- mode foldl2_values(pred(in, in, out, in, out) is det, in,
    in, out, in, out) is det.
:- mode foldl2_values(pred(in, in, out, mdi, muo) is det, in,
    in, out, mdi, muo) is det.
:- mode foldl2_values(pred(in, in, out, di, uo) is det, in,
    in, out, di, uo) is det.
:- mode foldl2_values(pred(in, in, out, in, out) is semidet, in,
    in, out, in, out) is semidet.
:- mode foldl2_values(pred(in, in, out, mdi, muo) is semidet, in,
    in, out, mdi, muo) is semidet.
:- mode foldl2_values(pred(in, in, out, di, uo) is semidet, in,
    in, out, di, uo) is semidet.
:- mode foldl2_values(pred(in, in, out, in, out) is cc_multi, in,
    in, out, in, out) is cc_multi.
:- mode foldl2_values(pred(in, in, out, mdi, muo) is cc_multi, in,
    in, out, mdi, muo) is cc_multi.
:- mode foldl2_values(pred(in, in, out, di, uo) is cc_multi, in,
    in, out, di, uo) is cc_multi.

:- pred foldl3_values(pred(V, A, A, B, B, C, C), tree234(K, V),
    A, A, B, B, C, C).
:- mode foldl3_values(pred(in, in, out, in, out, in, out) is det,
    in, in, out, in, out, in, out) is det.
:- mode foldl3_values(pred(in, in, out, in, out, mdi, muo) is det,
    in, in, out, in, out, mdi, muo) is det.
:- mode foldl3_values(pred(in, in, out, in, out, di, uo) is det,
    in, in, out, in, out, di, uo) is det.
:- mode foldl3_values(pred(in, in, out, in, out, in, out) is semidet,
    in, in, out, in, out, in, out) is semidet.
:- mode foldl3_values(pred(in, in, out, in, out, mdi, muo) is semidet,
    in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3_values(pred(in, in, out, in, out, di, uo) is semidet,
    in, in, out, in, out, di, uo) is semidet.
:- mode foldl3_values(pred(in, in, out, in, out, in, out) is cc_multi,
    in, in, out, in, out, in, out) is cc_multi.
:- mode foldl3_values(pred(in, in, out, in, out, mdi, muo) is cc_multi,
    in, in, out, in, out, mdi, muo) is cc_multi.
:- mode foldl3_values(pred(in, in, out, in, out, di, uo) is cc_multi,
    in, in, out, in, out, di, uo) is cc_multi.

:- pred foldl4_values(pred(V, A, A, B, B, C, C, D, D), tree234(K, V),
    A, A, B, B, C, C, D, D).
:- mode foldl4_values(pred(in, in, out, in, out, in, out, in, out)
    is det,
    in, in, out, in, out, in, out, in, out) is det.
:- mode foldl4_values(pred(in, in, out, in, out, in, out, mdi, muo)
    is det,
    in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl4_values(pred(in, in, out, in, out, in, out, di, uo) is det,
    in, in, out, in, out, in, out, di, uo) is det.
:- mode foldl4_values(pred(in, in, out, in, out, di, uo, di, uo) is det,
    in, in, out, in, out, di, uo, di, uo) is det.
:- mode foldl4_values(pred(in, in, out, di, uo, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo, di, uo) is det.
:- mode foldl4_values(pred(in, di, uo, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, di, uo, di, uo) is det.
:- mode foldl4_values(pred(in, in, out, in, out, in, out, in, out)
    is semidet,
    in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl4_values(pred(in, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl4_values(pred(in, in, out, in, out, in, out, di, uo)
    is semidet,
    in, in, out, in, out, in, out, di, uo) is semidet.

:- pred foldl5_values(pred(V, A, A, B, B, C, C, D, D, E, E), tree234(K, V),
    A, A, B, B, C, C, D, D, E, E).
:- mode foldl5_values(pred(in, in, out, in, out, in, out, in, out, in, out)
    is det,
    in, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldl5_values(pred(in, in, out, in, out, in, out, in, out, mdi, muo)
    is det,
    in, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl5_values(pred(in, in, out, in, out, in, out, in, out, di, uo)
    is det,
    in, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldl5_values(pred(in, in, out, in, out, in, out, in, out, in, out)
    is semidet,
    in, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl5_values(pred(in, in, out, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl5_values(pred(in, in, out, in, out, in, out, in, out, di, uo)
    is semidet,
    in, in, out, in, out, in, out, in, out, di, uo) is semidet.

:- pred foldl6_values(pred(V, A, A, B, B, C, C, D, D, E, E, F, F),
    tree234(K, V), A, A, B, B, C, C, D, D, E, E, F, F).
:- mode foldl6_values(pred(in, in, out, in, out, in, out, in, out,
    in, out, in, out) is det,
    in, in, out, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldl6_values(pred(in, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is det,
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl6_values(pred(in, in, out, in, out, in, out, in, out,
    in, out, di, uo) is det,
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldl6_values(pred(in, in, out, in, out, in, out, in, out,
    in, out, in, out) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl6_values(pred(in, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl6_values(pred(in, in, out, in, out, in, out, in, out,
    in, out, di, uo) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet.

:- func foldr(func(K, V, A) = A, tree234(K, V), A) = A.

:- pred foldr(pred(K, V, A, A), tree234(K, V), A, A).
:- mode foldr(pred(in, in, in, out) is det, in, in, out) is det.
:- mode foldr(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldr(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode foldr(pred(in, in, in, out) is semidet, in, in, out) is semidet.
:- mode foldr(pred(in, in, mdi, muo) is semidet, in, mdi, muo) is semidet.
:- mode foldr(pred(in, in, di, uo) is semidet, in, di, uo) is semidet.
:- mode foldr(pred(in, in, in, out) is cc_multi, in, in, out) is cc_multi.
:- mode foldr(pred(in, in, di, uo) is cc_multi, in, di, uo) is cc_multi.
:- mode foldr(pred(in, in, mdi, muo) is cc_multi, in, mdi, muo) is cc_multi.

:- pred foldr2(pred(K, V, A, A, B, B), tree234(K, V), A, A, B, B).
:- mode foldr2(pred(in, in, in, out, in, out) is det,
    in, in, out, in, out) is det.
:- mode foldr2(pred(in, in, in, out, mdi, muo) is det,
    in, in, out, mdi, muo) is det.
:- mode foldr2(pred(in, in, in, out, di, uo) is det,
    in, in, out, di, uo) is det.
:- mode foldr2(pred(in, in, di, uo, di, uo) is det,
    in, di, uo, di, uo) is det.
:- mode foldr2(pred(in, in, in, out, in, out) is semidet,
    in, in, out, in, out) is semidet.
:- mode foldr2(pred(in, in, in, out, mdi, muo) is semidet,
    in, in, out, mdi, muo) is semidet.
:- mode foldr2(pred(in, in, in, out, di, uo) is semidet,
    in, in, out, di, uo) is semidet.

:- pred foldr3(pred(K, V, A, A, B, B, C, C), tree234(K, V),
    A, A, B, B, C, C).
:- mode foldr3(pred(in, in, in, out, in, out, in, out) is det,
    in, in, out, in, out, in, out) is det.
:- mode foldr3(pred(in, in, in, out, in, out, mdi, muo) is det,
    in, in, out, in, out, mdi, muo) is det.
:- mode foldr3(pred(in, in, in, out, in, out, di, uo) is det,
    in, in, out, in, out, di, uo) is det.
:- mode foldr3(pred(in, in, in, out, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo) is det.
:- mode foldr3(pred(in, in, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, di, uo) is det.
:- mode foldr3(pred(in, in, in, out, in, out, in, out) is semidet,
    in, in, out, in, out, in, out) is semidet.
:- mode foldr3(pred(in, in, in, out, in, out, mdi, muo) is semidet,
    in, in, out, in, out, mdi, muo) is semidet.
:- mode foldr3(pred(in, in, in, out, in, out, di, uo) is semidet,
    in, in, out, in, out, di, uo) is semidet.

:- pred foldr4(pred(K, V, A, A, B, B, C, C, D, D), tree234(K, V),
    A, A, B, B, C, C, D, D).
:- mode foldr4(pred(in, in, in, out, in, out, in, out, in, out)
    is det,
    in, in, out, in, out, in, out, in, out) is det.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, mdi, muo)
    is det,
    in, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, di, uo) is det,
    in, in, out, in, out, in, out, di, uo) is det.
:- mode foldr4(pred(in, in, in, out, in, out, di, uo, di, uo) is det,
    in, in, out, in, out, di, uo, di, uo) is det.
:- mode foldr4(pred(in, in, in, out, di, uo, di, uo, di, uo) is det,
    in, in, out, di, uo, di, uo, di, uo) is det.
:- mode foldr4(pred(in, in, di, uo, di, uo, di, uo, di, uo) is det,
    in, di, uo, di, uo, di, uo, di, uo) is det.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, in, out)
    is semidet,
    in, in, out, in, out, in, out, in, out) is semidet.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldr4(pred(in, in, in, out, in, out, in, out, di, uo)
    is semidet,
    in, in, out, in, out, in, out, di, uo) is semidet.

:- pred foldr5(pred(K, V, A, A, B, B, C, C, D, D, E, E), tree234(K, V),
    A, A, B, B, C, C, D, D, E, E).
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, in, out)
    is det,
    in, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, mdi, muo)
    is det,
    in, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, di, uo)
    is det,
    in, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, in, out)
    is semidet,
    in, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldr5(pred(in, in, in, out, in, out, in, out, in, out, di, uo)
    is semidet,
    in, in, out, in, out, in, out, in, out, di, uo) is semidet.

:- pred foldr6(pred(K, V, A, A, B, B, C, C, D, D, E, E, F, F), tree234(K, V),
    A, A, B, B, C, C, D, D, E, E, F, F).
:- mode foldr6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, in, out) is det,
    in, in, out, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldr6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is det,
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldr6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, di, uo) is det,
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldr6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, in, out) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldr6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, mdi, muo) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldr6(pred(in, in, in, out, in, out, in, out, in, out,
    in, out, di, uo) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet.

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

:- func map_values(func(K, V) = W, tree234(K, V)) = tree234(K, W).

:- pred map_values(pred(K, V, W), tree234(K, V), tree234(K, W)).
:- mode map_values(pred(in, in, out) is det, in, out) is det.
:- mode map_values(pred(in, in, out) is semidet, in, out) is semidet.

:- func map_values_only(func(V) = W, tree234(K, V)) = tree234(K, W).

:- pred map_values_only(pred(V, W), tree234(K, V), tree234(K, W)).
:- mode map_values_only(pred(in, out) is det, in, out) is det.
:- mode map_values_only(pred(in, out) is semidet, in, out) is semidet.

:- pred filter_map_values(pred(K, V, W)::in(pred(in, in, out) is semidet),
    tree234(K, V)::in, tree234(K, W)::out) is det.

:- pred filter_map_values_only(pred(V, W)::in(pred(in, out) is semidet),
    tree234(K, V)::in, tree234(K, W)::out) is det.

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

:- pred map_foldl(pred(K, V, W, A, A),
    tree234(K, V), tree234(K, W), A, A).
:- mode map_foldl(pred(in, in, out, in, out) is det,
    in, out, in, out) is det.
:- mode map_foldl(pred(in, in, out, mdi, muo) is det,
    in, out, mdi, muo) is det.
:- mode map_foldl(pred(in, in, out, di, uo) is det,
    in, out, di, uo) is det.
:- mode map_foldl(pred(in, in, out, in, out) is semidet,
    in, out, in, out) is semidet.
:- mode map_foldl(pred(in, in, out, mdi, muo) is semidet,
    in, out, mdi, muo) is semidet.
:- mode map_foldl(pred(in, in, out, di, uo) is semidet,
    in, out, di, uo) is semidet.

:- pred map_foldl2(pred(K, V, W, A, A, B, B),
    tree234(K, V), tree234(K, W), A, A, B, B).
:- mode map_foldl2(pred(in, in, out, in, out, in, out) is det,
    in, out, in, out, in, out) is det.
:- mode map_foldl2(pred(in, in, out, in, out, mdi, muo) is det,
    in, out, in, out, mdi, muo) is det.
:- mode map_foldl2(pred(in, in, out, di, uo, di, uo) is det,
    in, out, di, uo, di, uo) is det.
:- mode map_foldl2(pred(in, in, out, in, out, di, uo) is det,
    in, out, in, out, di, uo) is det.
:- mode map_foldl2(pred(in, in, out, in, out, in, out) is semidet,
    in, out, in, out, in, out) is semidet.
:- mode map_foldl2(pred(in, in, out, in, out, mdi, muo) is semidet,
    in, out, in, out, mdi, muo) is semidet.
:- mode map_foldl2(pred(in, in, out, in, out, di, uo) is semidet,
    in, out, in, out, di, uo) is semidet.

:- pred map_foldl3(pred(K, V, W, A, A, B, B, C, C),
    tree234(K, V), tree234(K, W), A, A, B, B, C, C).
:- mode map_foldl3(pred(in, in, out, in, out, in, out, in, out) is det,
    in, out, in, out, in, out, in, out) is det.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, mdi, muo) is det,
    in, out, in, out, in, out, mdi, muo) is det.
:- mode map_foldl3(pred(in, in, out, di, uo, di, uo, di, uo) is det,
    in, out, di, uo, di, uo, di, uo) is det.
:- mode map_foldl3(pred(in, in, out, in, out, di, uo, di, uo) is det,
    in, out, in, out, di, uo, di, uo) is det.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, di, uo) is det,
    in, out, in, out, in, out, di, uo) is det.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, in, out)
    is semidet,
    in, out, in, out, in, out, in, out) is semidet.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, out, in, out, in, out, mdi, muo) is semidet.
:- mode map_foldl3(pred(in, in, out, in, out, in, out, di, uo)
    is semidet,
    in, out, in, out, in, out, di, uo) is semidet.

:- pred map_foldl4(pred(K, V, W, A, A, B, B, C, C, D, D),
    tree234(K, V), tree234(K, W), A, A, B, B, C, C, D, D).
:- mode map_foldl4(pred(in, in, out, in, out, in, out, in, out, in, out)
    is det,
    in, out, in, out, in, out, in, out, in, out) is det.
:- mode map_foldl4(pred(in, in, out, in, out, in, out, in, out, mdi, muo)
    is det,
    in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode map_foldl4(pred(in, in, out, in, out, di, uo, di, uo, di, uo) is det,
    in, out, in, out, di, uo, di, uo, di, uo) is det.
:- mode map_foldl4(pred(in, in, out, in, out, in, out, di, uo, di, uo) is det,
    in, out, in, out, in, out, di, uo, di, uo) is det.
:- mode map_foldl4(pred(in, in, out, in, out, in, out, in, out, di, uo) is det,
    in, out, in, out, in, out, in, out, di, uo) is det.
:- mode map_foldl4(pred(in, in, out, in, out, in, out, in, out, in, out)
    is semidet,
    in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode map_foldl4(pred(in, in, out, in, out, in, out, in, out, mdi, muo)
    is semidet,
    in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode map_foldl4(pred(in, in, out, in, out, in, out, in, out, di, uo)
    is semidet,
    in, out, in, out, in, out, in, out, di, uo) is semidet.

:- pred map_values_foldl(pred(V, W, A, A),
    tree234(K, V), tree234(K, W), A, A).
:- mode map_values_foldl(pred(in, out, di, uo) is det,
    in, out, di, uo) is det.
:- mode map_values_foldl(pred(in, out, in, out) is det,
    in, out, in, out) is det.
:- mode map_values_foldl(pred(in, out, in, out) is semidet,
    in, out, in, out) is semidet.

:- pred map_values_foldl2(pred(V, W, A, A, B, B),
    tree234(K, V), tree234(K, W), A, A, B, B).
:- mode map_values_foldl2(pred(in, out, di, uo, di, uo) is det,
    in, out, di, uo, di, uo) is det.
:- mode map_values_foldl2(pred(in, out, in, out, di, uo) is det,
    in, out, in, out, di, uo) is det.
:- mode map_values_foldl2(pred(in, out, in, out, in, out) is det,
    in, out, in, out, in, out) is det.
:- mode map_values_foldl2(pred(in, out, in, out, in, out) is semidet,
    in, out, in, out, in, out) is semidet.

:- pred map_values_foldl3(pred(V, W, A, A, B, B, C, C),
    tree234(K, V), tree234(K, W), A, A, B, B, C, C).
:- mode map_values_foldl3(
    pred(in, out, di, uo, di, uo, di, uo) is det,
    in, out, di, uo, di, uo, di, uo) is det.
:- mode map_values_foldl3(
    pred(in, out, in, out, di, uo, di, uo) is det,
    in, out, in, out, di, uo, di, uo) is det.
:- mode map_values_foldl3(
    pred(in, out, in, out, in, out, di, uo) is det,
    in, out, in, out, in, out, di, uo) is det.
:- mode map_values_foldl3(
    pred(in, out, in, out, in, out, in, out) is det,
    in, out, in, out, in, out, in, out) is det.
:- mode map_values_foldl3(
    pred(in, out, in, out, in, out, in, out) is semidet,
    in, out, in, out, in, out, in, out) is semidet.

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

    % Convert a tree234 into a pretty_printer.doc. A tree mapping
    % K1 to V1, K2 to V2, ... is formatted as
    % "map([K1 -> V1, K2 -> V2, ...])". The functor "map" is used
    % because tree234 values are almost exclusively maps.
    %
:- func tree234_to_doc(tree234(K, V)) = pretty_printer.doc.

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


Next: , Previous: time, Up: Top   [Contents]