mercurylang/mercury
1
0
Fork 0
mirror of https://github.com/Mercury-Language/mercury.git synced 2026-04-15 01:13:30 +00:00
Code Issues Projects Releases Wiki Activity
Files
master
mercury/library/tree234.m
Julien Fischer 63ab40f515 More library documentation fixes. 
library/*.m:

libary/map.m:
   Fix a variable name that was obviously the reuslt of a
   copy-and-paste error.
2026-02-20 21:05:08 +11:00

5044 lines
186 KiB
Mathematica
Raw Permalink Blame History

%---------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%---------------------------------------------------------------------------%
% Copyright (C) 1994-1997,1999-2000,2002-2012 The University of Melbourne.
% Copyright (C) 2013-2022, 2025-2026 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%---------------------------------------------------------------------------%
%
% File: tree234.m.
% Main author: conway.
% Stability: high.
%
% 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.
:- pred is_non_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.
% NOTE_TO_IMPLEMENTORS CFF :- pragma obsolete(func(max_key/1), [max_key/2]).
:- pred max_key(tree234(K, V)::in, K::out) is semidet.
:- func min_key(tree234(K, V)) = K is semidet.
% NOTE_TO_IMPLEMENTORS CFF :- pragma obsolete(func(min_key/1), [min_key/2]).
:- pred min_key(tree234(K, V)::in, K::out) 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 !.Tree, with corresponding value OldV,
% then set MaybeOldV to yes(OldV), and leave !Tree unchanged.
%
% If the key is not already in !.Tree, then insert it into !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::in, V::out, tree234(K, V)::in, tree234(K, V)::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::out, V::out,
tree234(K, V)::in, tree234(K, V)::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.
% Given a tree234, succeed if and only if the given list is the list
% of all the keys in the tree.
%
% `sorted_keys_match(Tree, List)' is equivalent to the conjunction,
% `sorted_keys(Tree, Keys), Keys = List', but it allocates no memory,
% and it traverses Tree only up to the first mismatch.
%
:- pred sorted_keys_match(tree234(K, V)::in, list(K)::in) is semidet.
%---------------------%
% Count the number of elements in a tree.
%
:- func count(tree234(K, V)) = int.
:- pred count(tree234(K, V)::in, int::out) is det.
:- func ucount(tree234(K, V)) = uint.
:- pred ucount(tree234(K, V)::in, uint::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(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode foldl(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode foldl(in(pred(in, in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldl(in(pred(in, in, di, uo) is semidet), in, di, uo) is semidet.
:- mode foldl(in(pred(in, in, in, out) is cc_multi), in, in, out) is cc_multi.
:- mode foldl(in(pred(in, in, di, uo) is cc_multi), in, di, uo) is cc_multi.
:- mode foldl(in(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(in(pred(in, in, in, out, in, out) is det),
in, in, out, in, out) is det.
:- mode foldl2(in(pred(in, in, in, out, mdi, muo) is det),
in, in, out, mdi, muo) is det.
:- mode foldl2(in(pred(in, in, in, out, di, uo) is det),
in, in, out, di, uo) is det.
:- mode foldl2(in(pred(in, in, di, uo, di, uo) is det),
in, di, uo, di, uo) is det.
:- mode foldl2(in(pred(in, in, in, out, in, out) is semidet),
in, in, out, in, out) is semidet.
:- mode foldl2(in(pred(in, in, in, out, mdi, muo) is semidet),
in, in, out, mdi, muo) is semidet.
:- mode foldl2(in(pred(in, in, in, out, di, uo) is semidet),
in, in, out, di, uo) is semidet.
:- mode foldl2(in(pred(in, in, in, out, in, out) is cc_multi),
in, in, out, in, out) is cc_multi.
:- mode foldl2(in(pred(in, in, in, out, mdi, muo) is cc_multi),
in, in, out, mdi, muo) is cc_multi.
:- mode foldl2(in(pred(in, in, in, out, di, uo) is cc_multi),
in, in, out, di, uo) is cc_multi.
:- mode foldl2(in(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(in(pred(in, in, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out) is det.
:- mode foldl3(in(pred(in, in, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, mdi, muo) is det.
:- mode foldl3(in(pred(in, in, in, out, in, out, di, uo) is det),
in, in, out, in, out, di, uo) is det.
:- mode foldl3(in(pred(in, in, in, out, di, uo, di, uo) is det),
in, in, out, di, uo, di, uo) is det.
:- mode foldl3(in(pred(in, in, di, uo, di, uo, di, uo) is det),
in, di, uo, di, uo, di, uo) is det.
:- mode foldl3(in(pred(in, in, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out) is semidet.
:- mode foldl3(in(pred(in, in, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl_values(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl_values(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldl_values(in(pred(in, in, out) is semidet), in, in, out)
is semidet.
:- mode foldl_values(in(pred(in, mdi, muo) is semidet), in, mdi, muo)
is semidet.
:- mode foldl_values(in(pred(in, di, uo) is semidet), in, di, uo)
is semidet.
:- mode foldl_values(in(pred(in, in, out) is cc_multi), in, in, out)
is cc_multi.
:- mode foldl_values(in(pred(in, di, uo) is cc_multi), in, di, uo)
is cc_multi.
:- mode foldl_values(in(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(in(pred(in, in, out, in, out) is det), in,
in, out, in, out) is det.
:- mode foldl2_values(in(pred(in, in, out, mdi, muo) is det), in,
in, out, mdi, muo) is det.
:- mode foldl2_values(in(pred(in, in, out, di, uo) is det), in,
in, out, di, uo) is det.
:- mode foldl2_values(in(pred(in, in, out, in, out) is semidet), in,
in, out, in, out) is semidet.
:- mode foldl2_values(in(pred(in, in, out, mdi, muo) is semidet), in,
in, out, mdi, muo) is semidet.
:- mode foldl2_values(in(pred(in, in, out, di, uo) is semidet), in,
in, out, di, uo) is semidet.
:- mode foldl2_values(in(pred(in, in, out, in, out) is cc_multi), in,
in, out, in, out) is cc_multi.
:- mode foldl2_values(in(pred(in, in, out, mdi, muo) is cc_multi), in,
in, out, mdi, muo) is cc_multi.
:- mode foldl2_values(in(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(in(pred(in, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out) is det.
:- mode foldl3_values(in(pred(in, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, mdi, muo) is det.
:- mode foldl3_values(in(pred(in, in, out, in, out, di, uo) is det),
in, in, out, in, out, di, uo) is det.
:- mode foldl3_values(in(pred(in, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out) is semidet.
:- mode foldl3_values(in(pred(in, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, mdi, muo) is semidet.
:- mode foldl3_values(in(pred(in, in, out, in, out, di, uo) is semidet),
in, in, out, in, out, di, uo) is semidet.
:- mode foldl3_values(in(pred(in, in, out, in, out, in, out) is cc_multi),
in, in, out, in, out, in, out) is cc_multi.
:- mode foldl3_values(in(pred(in, in, out, in, out, mdi, muo) is cc_multi),
in, in, out, in, out, mdi, muo) is cc_multi.
:- mode foldl3_values(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode foldr(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldr(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode foldr(in(pred(in, in, in, out) is semidet), in, in, out) is semidet.
:- mode foldr(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldr(in(pred(in, in, di, uo) is semidet), in, di, uo) is semidet.
:- mode foldr(in(pred(in, in, in, out) is cc_multi), in, in, out) is cc_multi.
:- mode foldr(in(pred(in, in, di, uo) is cc_multi), in, di, uo) is cc_multi.
:- mode foldr(in(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(in(pred(in, in, in, out, in, out) is det),
in, in, out, in, out) is det.
:- mode foldr2(in(pred(in, in, in, out, mdi, muo) is det),
in, in, out, mdi, muo) is det.
:- mode foldr2(in(pred(in, in, in, out, di, uo) is det),
in, in, out, di, uo) is det.
:- mode foldr2(in(pred(in, in, di, uo, di, uo) is det),
in, di, uo, di, uo) is det.
:- mode foldr2(in(pred(in, in, in, out, in, out) is semidet),
in, in, out, in, out) is semidet.
:- mode foldr2(in(pred(in, in, in, out, mdi, muo) is semidet),
in, in, out, mdi, muo) is semidet.
:- mode foldr2(in(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(in(pred(in, in, in, out, in, out, in, out) is det),
in, in, out, in, out, in, out) is det.
:- mode foldr3(in(pred(in, in, in, out, in, out, mdi, muo) is det),
in, in, out, in, out, mdi, muo) is det.
:- mode foldr3(in(pred(in, in, in, out, in, out, di, uo) is det),
in, in, out, in, out, di, uo) is det.
:- mode foldr3(in(pred(in, in, in, out, di, uo, di, uo) is det),
in, in, out, di, uo, di, uo) is det.
:- mode foldr3(in(pred(in, in, di, uo, di, uo, di, uo) is det),
in, di, uo, di, uo, di, uo) is det.
:- mode foldr3(in(pred(in, in, in, out, in, out, in, out) is semidet),
in, in, out, in, out, in, out) is semidet.
:- mode foldr3(in(pred(in, in, in, out, in, out, mdi, muo) is semidet),
in, in, out, in, out, mdi, muo) is semidet.
:- mode foldr3(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(pred(in, in, out) is det), in, out) is det.
:- mode map_values(in(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(in(pred(in, out) is det), in, out) is det.
:- mode map_values_only(in(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(in(pred(in, in, out, in, out) is det),
in, out, in, out) is det.
:- mode map_foldl(in(pred(in, in, out, mdi, muo) is det),
in, out, mdi, muo) is det.
:- mode map_foldl(in(pred(in, in, out, di, uo) is det),
in, out, di, uo) is det.
:- mode map_foldl(in(pred(in, in, out, in, out) is semidet),
in, out, in, out) is semidet.
:- mode map_foldl(in(pred(in, in, out, mdi, muo) is semidet),
in, out, mdi, muo) is semidet.
:- mode map_foldl(in(pred(in, in, out, di, uo) is semidet),
in, out, di, uo) is semidet.
:- mode map_foldl(in(pred(in, in, out, in, out) is cc_multi),
in, out, in, out) is cc_multi.
:- mode map_foldl(in(pred(in, in, out, mdi, muo) is cc_multi),
in, out, mdi, muo) is cc_multi.
:- mode map_foldl(in(pred(in, in, out, di, uo) is cc_multi),
in, out, di, uo) is cc_multi.
:- pred map_foldl2(pred(K, V, W, A, A, B, B),
tree234(K, V), tree234(K, W), A, A, B, B).
:- mode map_foldl2(in(pred(in, in, out, in, out, in, out) is det),
in, out, in, out, in, out) is det.
:- mode map_foldl2(in(pred(in, in, out, in, out, mdi, muo) is det),
in, out, in, out, mdi, muo) is det.
:- mode map_foldl2(in(pred(in, in, out, di, uo, di, uo) is det),
in, out, di, uo, di, uo) is det.
:- mode map_foldl2(in(pred(in, in, out, in, out, di, uo) is det),
in, out, in, out, di, uo) is det.
:- mode map_foldl2(in(pred(in, in, out, in, out, in, out) is semidet),
in, out, in, out, in, out) is semidet.
:- mode map_foldl2(in(pred(in, in, out, in, out, mdi, muo) is semidet),
in, out, in, out, mdi, muo) is semidet.
:- mode map_foldl2(in(pred(in, in, out, in, out, di, uo) is semidet),
in, out, in, out, di, uo) is semidet.
:- mode map_foldl2(in(pred(in, in, out, in, out, in, out) is cc_multi),
in, out, in, out, in, out) is cc_multi.
:- mode map_foldl2(in(pred(in, in, out, in, out, mdi, muo) is cc_multi),
in, out, in, out, mdi, muo) is cc_multi.
:- mode map_foldl2(in(pred(in, in, out, in, out, di, uo) is cc_multi),
in, out, in, out, di, uo) is cc_multi.
:- 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(in(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(in(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(in(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(in(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(in(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(in(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(in(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(in(pred(in, in, out, in, out, in, out, di, uo)
is semidet),
in, out, in, out, in, out, di, uo) is semidet.
:- mode map_foldl3(in(pred(in, in, out, in, out, in, out, in, out) is cc_multi),
in, out, in, out, in, out, in, out) is cc_multi.
:- mode map_foldl3(in(pred(in, in, out, in, out, in, out, mdi, muo) is cc_multi),
in, out, in, out, in, out, mdi, muo) is cc_multi.
:- mode map_foldl3(in(pred(in, in, out, di, uo, di, uo, di, uo) is cc_multi),
in, out, di, uo, di, uo, di, uo) is cc_multi.
:- 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(
in(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(
in(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(
in(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(
in(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(
in(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(
in(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(
in(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(
in(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.
:- mode map_foldl4(
in(pred(in, in, out, in, out, in, out, in, out, in, out) is cc_multi),
in, out, in, out, in, out, in, out, in, out) is cc_multi.
:- mode map_foldl4(
in(pred(in, in, out, in, out, in, out, in, out, mdi, muo) is cc_multi),
in, out, in, out, in, out, in, out, mdi, muo) is cc_multi.
:- mode map_foldl4(
in(pred(in, in, out, in, out, di, uo, di, uo, di, uo) is cc_multi),
in, out, in, out, di, uo, di, uo, di, uo) is cc_multi.
:- pred map_values_foldl(pred(V, W, A, A),
tree234(K, V), tree234(K, W), A, A).
:- mode map_values_foldl(in(pred(in, out, in, out) is det),
in, out, in, out) is det.
:- mode map_values_foldl(in(pred(in, out, di, uo) is det),
in, out, di, uo) is det.
:- mode map_values_foldl(in(pred(in, out, in, out) is semidet),
in, out, in, out) is semidet.
:- mode map_values_foldl(in(pred(in, out, in, out) is cc_multi),
in, out, in, out) is cc_multi.
:- mode map_values_foldl(in(pred(in, out, di, uo) is cc_multi),
in, out, di, uo) is cc_multi.
:- pred map_values_only_foldl(pred(V, W, A, A),
tree234(K, V), tree234(K, W), A, A).
:- mode map_values_only_foldl(in(pred(in, out, in, out) is det),
in, out, in, out) is det.
:- mode map_values_only_foldl(in(pred(in, out, di, uo) is det),
in, out, di, uo) is det.
:- mode map_values_only_foldl(in(pred(in, out, in, out) is semidet),
in, out, in, out) is semidet.
:- mode map_values_only_foldl(in(pred(in, out, in, out) is cc_multi),
in, out, in, out) is cc_multi.
:- mode map_values_only_foldl(in(pred(in, out, di, uo) is cc_multi),
in, out, di, uo) is cc_multi.
:- 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(in(pred(in, out, in, out, in, out) is det),
in, out, in, out, in, out) is det.
:- mode map_values_foldl2(in(pred(in, out, in, out, di, uo) is det),
in, out, in, out, di, uo) is det.
:- mode map_values_foldl2(in(pred(in, out, di, uo, di, uo) is det),
in, out, di, uo, di, uo) is det.
:- mode map_values_foldl2(in(pred(in, out, in, out, in, out) is semidet),
in, out, in, out, in, out) is semidet.
:- mode map_values_foldl2(in(pred(in, out, in, out, in, out) is cc_multi),
in, out, in, out, in, out) is cc_multi.
:- mode map_values_foldl2(in(pred(in, out, in, out, di, uo) is cc_multi),
in, out, in, out, di, uo) is cc_multi.
:- pred map_values_only_foldl2(pred(V, W, A, A, B, B),
tree234(K, V), tree234(K, W), A, A, B, B).
:- mode map_values_only_foldl2(in(pred(in, out, in, out, in, out) is det),
in, out, in, out, in, out) is det.
:- mode map_values_only_foldl2(in(pred(in, out, in, out, di, uo) is det),
in, out, in, out, di, uo) is det.
:- mode map_values_only_foldl2(in(pred(in, out, di, uo, di, uo) is det),
in, out, di, uo, di, uo) is det.
:- mode map_values_only_foldl2(in(pred(in, out, in, out, in, out) is semidet),
in, out, in, out, in, out) is semidet.
:- mode map_values_only_foldl2(in(pred(in, out, in, out, in, out) is cc_multi),
in, out, in, out, in, out) is cc_multi.
:- mode map_values_only_foldl2(in(pred(in, out, in, out, di, uo) is cc_multi),
in, out, in, out, di, uo) is cc_multi.
:- 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(
in(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(
in(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(
in(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(
in(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(
in(pred(in, out, in, out, in, out, in, out) is semidet),
in, out, in, out, in, out, in, out) is semidet.
:- mode map_values_foldl3(
in(pred(in, out, in, out, in, out, in, out) is cc_multi),
in, out, in, out, in, out, in, out) is cc_multi.
:- mode map_values_foldl3(
in(pred(in, out, in, out, in, out, di, uo) is cc_multi),
in, out, in, out, in, out, di, uo) is cc_multi.
:- pred map_values_only_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_only_foldl3(
in(pred(in, out, in, out, in, out, in, out) is det),
in, out, in, out, in, out, in, out) is det.
:- mode map_values_only_foldl3(
in(pred(in, out, in, out, in, out, di, uo) is det),
in, out, in, out, in, out, di, uo) is det.
:- mode map_values_only_foldl3(
in(pred(in, out, in, out, di, uo, di, uo) is det),
in, out, in, out, di, uo, di, uo) is det.
:- mode map_values_only_foldl3(
in(pred(in, out, di, uo, di, uo, di, uo) is det),
in, out, di, uo, di, uo, di, uo) is det.
:- mode map_values_only_foldl3(
in(pred(in, out, in, out, in, out, in, out) is semidet),
in, out, in, out, in, out, in, out) is semidet.
:- mode map_values_only_foldl3(
in(pred(in, out, in, out, in, out, in, out) is cc_multi),
in, out, in, out, in, out, in, out) is cc_multi.
:- mode map_values_only_foldl3(
in(pred(in, out, in, out, in, out, di, uo) is cc_multi),
in, out, in, out, in, out, di, uo) is cc_multi.
%---------------------%
% 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.
:- pragma obsolete(func(tree234_to_doc/1), [pretty_printer.tree234_to_doc/1]).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
:- implementation.
% Everything below here is not intended to be part of the public interface,
% and will not be included in the Mercury library reference manual.
:- interface.
:- import_module maybe.
:- pragma type_spec(pred(tree234.search/3), K = var(_)).
:- pragma type_spec(pred(tree234.search/3), K = int).
:- pragma type_spec(pred(tree234.lookup/3), K = var(_)).
:- pragma type_spec(tree234.set(in, in, in, out), K = var(_)).
:- pragma type_spec(tree234.update(in, in, in, out), K = var(_)).
:- pragma type_spec(tree234.update(in, in, in, out), K = int).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
% This should be abstract, but needs to be exported for insts.
%
:- type tree234(K, V)
---> empty
; two(K, V, tree234(K, V), tree234(K, V))
; three(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V))
; four(K, V, K, V, K, V, tree234(K, V), tree234(K, V),
tree234(K, V), tree234(K, V)).
:- inst uniq_tree234(K, V) for tree234/2 ==
unique((
empty
; two(K, V, uniq_tree234(K, V), uniq_tree234(K, V))
; three(K, V, K, V, uniq_tree234(K, V), uniq_tree234(K, V),
uniq_tree234(K, V))
; four(K, V, K, V, K, V, uniq_tree234(K, V), uniq_tree234(K, V),
uniq_tree234(K, V), uniq_tree234(K, V))
)).
:- inst uniq_tree234_gg for tree234/2 ==
unique((
empty
; two(ground, ground, uniq_tree234_gg, uniq_tree234_gg)
; three(ground, ground, ground, ground,
uniq_tree234_gg, uniq_tree234_gg, uniq_tree234_gg)
; four(ground, ground, ground, ground, ground, ground,
uniq_tree234_gg, uniq_tree234_gg, uniq_tree234_gg, uniq_tree234_gg)
)).
:- mode di_tree234(K, V) == uniq_tree234(K, V) >> dead.
:- mode di_tree234 == uniq_tree234(ground, ground) >> dead.
:- mode uo_tree234(K, V) == free >> uniq_tree234(K, V).
:- mode uo_tree234 == free >> uniq_tree234(ground, ground).
:- type maybe_reduced_height
---> did_not_reduce_height
; reduced_height.
%---------------------------------------------------------------------------%
%
% Exported to pretty_printer.m.
%
:- type tree234_lazy_list(K, V)
---> tll_nil
; tll_lazy_cons(K, V, (func) = tree234_lazy_list(K, V)).
:- func tree234_to_lazy_list(tree234(K, V), tree234_lazy_list(K, V))
= tree234_lazy_list(K, V).
%---------------------------------------------------------------------------%
% Return the minimum number of key/value pairs in the tree, given its
% depth. This is obviously not as accurate as tree234.count, but it
% is computed *much* faster, in time O(log Count), not O(Count).
%
:- pred find_min_size_based_on_depth(tree234(K, V)::in, int::out) is det.
% Check whether the given tree is well formed, i.e. all the empty nodes
% are at the same depth. If yes, return that depth. Otherwise, return `no'.
%
% This predicate is a sanity check; it should *never* return `no'.
%
:- pred well_formed(tree234(K, V)::in, maybe(int)::out) is det.
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
:- implementation.
:- import_module int.
:- import_module io.
:- import_module pair.
:- import_module require.
:- import_module set.
:- import_module string.
:- import_module uint.
:- inst two(K, V, T) for tree234/2
---> two(K, V, T, T).
:- inst three(K, V, T) for tree234/2
---> three(K, V, K, V, T, T, T).
:- inst four(K, V, T) for tree234/2
---> four(K, V, K, V, K, V, T, T, T, T).
:- inst uniq_two(K, V, T) for tree234/2
== unique(two(K, V, T, T)).
:- inst uniq_three(K, V, T) for tree234/2
== unique(three(K, V, K, V, T, T, T)).
:- inst uniq_four(K, V, T) for tree234/2
== unique(four(K, V, K, V, K, V, T, T, T, T)).
:- inst tree234_nonempty for tree234/2
---> two(ground, ground, ground, ground)
; three(ground, ground, ground, ground,
ground, ground, ground)
; four(ground, ground, ground, ground, ground, ground,
ground, ground, ground, ground).
:- mode uo_two == out(uniq_two(unique, unique, unique)).
:- mode suo_two == out(uniq_two(ground, ground, uniq_tree234_gg)).
:- mode out_two == out(two(ground, ground, ground)).
:- mode di_two == di(uniq_two(unique, unique, unique)).
:- mode sdi_two == di(uniq_two(ground, ground, uniq_tree234_gg)).
:- mode in_two == in(two(ground, ground, ground)).
:- mode di_three == di(uniq_three(unique, unique, unique)).
:- mode sdi_three == di(uniq_three(ground, ground, uniq_tree234_gg)).
:- mode in_three == in(three(ground, ground, ground)).
:- mode di_four == di(uniq_four(unique, unique, unique)).
:- mode sdi_four == di(uniq_four(ground, ground, uniq_tree234_gg)).
:- mode in_four == in(four(ground, ground, ground)).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
init = empty.
init(empty).
singleton(K, V) = two(K, V, empty, empty).
is_empty(Tree) :-
require_complete_switch [Tree]
(
Tree = empty
;
( Tree = two(_, _, _, _)
; Tree = three(_, _, _, _, _, _, _)
; Tree = four(_, _, _, _, _, _, _, _, _, _)
),
fail
).
is_non_empty(Tree) :-
require_complete_switch [Tree]
(
Tree = empty,
fail
;
( Tree = two(_, _, _, _)
; Tree = three(_, _, _, _, _, _, _)
; Tree = four(_, _, _, _, _, _, _, _, _, _)
)
).
equal(TreeA, TreeB) :-
% We first try to see if the two trees are identical, since this can
% save a large amount of work. If they aren't, then we must compare
% their structures. To do this, we use a stack to store the
% as-yet-unexplored parts of TreeB in their original order while the
% match_tree_against_stack predicate recurses on TreeA.
( if private_builtin.pointer_equal(TreeA, TreeB) then
true
else
require_complete_switch [TreeB]
(
TreeB = empty,
TreeA = empty
;
( TreeB = two(_, _, _, _)
; TreeB = three(_, _, _, _, _, _, _)
; TreeB = four(_, _, _, _, _, _, _, _, _, _)
),
StackB0 = [TreeB],
match_tree_against_stack(TreeA, StackB0, StackB),
% Note that StackB can never contain empty trees (see the
% comment on match_tree_against_stack) therefore testing that
% the whole of TreeB has been matched is trivial.
StackB = []
)
).
% match_tree_against_stack(SubtreeA, StackB0, StackB),
%
% True if the key-value pairs of SubtreeA match the key-value pairs of
% the subtrees in StackB0, StackB contains any subtrees from StackB0
% that were not matched.
%
% StackB0 can never contain an empty node because:
% + match_tree_against_stack/3's caller will never put an empty node in
% StackB0.
% + match_tree_against_stack/3 and its callees will never put an empty
% node on the stack. Arbitrary nodes are checked before they're
% placed on the stack and other nodes are constructed deliberately.
% The inst subtyping on these arguments enforces this.
%
:- pred match_tree_against_stack(tree234(K, V)::in,
list(tree234(K, V))::in(list(tree234_nonempty)),
list(tree234(K, V))::out(list(tree234_nonempty))) is semidet.
match_tree_against_stack(SubtreeA, !StackB) :-
( if
!.StackB = [LeftmostSubtreeB | !:StackB],
private_builtin.pointer_equal(SubtreeA, LeftmostSubtreeB)
then
true
else
require_complete_switch [SubtreeA]
(
SubtreeA = empty
;
SubtreeA = two(K, V, Left, Right),
match_tree_against_stack(Left, !StackB),
match_kv_against_stack(K, V, !StackB),
match_tree_against_stack(Right, !StackB)
;
SubtreeA = three(K1, V1, K2, V2, Left, Middle, Right),
match_tree_against_stack(Left, !StackB),
match_kv_against_stack(K1, V1, !StackB),
match_tree_against_stack(Middle, !StackB),
match_kv_against_stack(K2, V2, !StackB),
match_tree_against_stack(Right, !StackB)
;
SubtreeA = four(K1, V1, K2, V2, K3, V3,
Left, MidLeft, MidRight, Right),
match_tree_against_stack(Left, !StackB),
match_kv_against_stack(K1, V1, !StackB),
match_tree_against_stack(MidLeft, !StackB),
match_kv_against_stack(K2, V2, !StackB),
match_tree_against_stack(MidRight, !StackB),
match_kv_against_stack(K3, V3, !StackB),
match_tree_against_stack(Right, !StackB)
)
).
% match_kv_against_stack(KA, VA, !StackB)
%
% Match a key-value pair against the leftmost key-value pair in the
% stack of subtrees. The first item on the stack is the leftmost
% subtree. The matched key-value pair is removed from the stack.
%
:- pred match_kv_against_stack(K::in, V::in,
list(tree234(K, V))::in(list(tree234_nonempty)),
list(tree234(K, V))::out(list(tree234_nonempty))) is semidet.
match_kv_against_stack(KA, VA, !StackB) :-
!.StackB = [LeftmostB | !:StackB],
match_kv_against_subtree_and_stack(KA, VA, LeftmostB, !StackB).
% match_kv_against_subtree_and_stack(KA, VA, LeftmostB, !StackB)
%
% Like match_kv_against_stack/4 except that LeftmostB is the subtree to
% the left of !.StackB.
%
:- pred match_kv_against_subtree_and_stack(K::in, V::in,
tree234(K, V)::in(tree234_nonempty),
list(tree234(K, V))::in(list(tree234_nonempty)),
list(tree234(K, V))::out(list(tree234_nonempty))) is semidet.
match_kv_against_subtree_and_stack(KA, VA, LeftmostB, !StackB) :-
require_complete_switch [LeftmostB]
(
LeftmostB = two(KB1, VB1, Left, Right),
require_complete_switch [Left]
(
Left = empty,
% Try to match the items.
KA = KB1,
VA = VB1,
% Update stack and return.
(
( Right = two(_, _, _, _)
; Right = three(_, _, _, _, _, _, _)
; Right = four(_, _, _, _, _, _, _, _, _, _)
),
!:StackB = [Right | !.StackB]
;
Right = empty
)
;
( Left = two(_, _, _, _)
; Left = three(_, _, _, _, _, _, _)
; Left = four(_, _, _, _, _, _, _, _, _, _)
),
% Break up this node and recurse
!:StackB = [two(KB1, VB1, empty, Right) | !.StackB],
match_kv_against_subtree_and_stack(KA, VA, Left, !StackB)
)
;
LeftmostB = three(KB1, VB1, KB2, VB2, Left, Middle, Right),
% This case has the same structure as the one above.
require_complete_switch [Left]
(
Left = empty,
KA = KB1,
VA = VB1,
% We've eliminated Left and VB1-VB2, so we can build a two node
% from the rest of the three node.
!:StackB = [two(KB2, VB2, Middle, Right) | !.StackB]
;
( Left = two(_, _, _, _)
; Left = three(_, _, _, _, _, _, _)
; Left = four(_, _, _, _, _, _, _, _, _, _)
),
!:StackB = [three(KB1, VB1, KB2, VB2, empty, Middle, Right) |
!.StackB],
% Pull the leftmost node out and try to match on it.
match_kv_against_subtree_and_stack(KA, VA, Left, !StackB)
)
;
LeftmostB = four(KB1, VB1, KB2, VB2, KB3, VB3,
Left, MidLeft, MidRight, Right),
% This case has the same structure as the previous two cases.
require_complete_switch [Left]
(
Left = empty,
KA = KB1,
VA = VB1,
!:StackB = [three(KB2, VB2, KB3, VB3, MidLeft, MidRight, Right) |
!.StackB]
;
( Left = two(_, _, _, _)
; Left = three(_, _, _, _, _, _, _)
; Left = four(_, _, _, _, _, _, _, _, _, _)
),
!:StackB = [four(KB1, VB1, KB2, VB2, KB3, VB3,
empty, MidLeft, MidRight, Right)
| !.StackB],
match_kv_against_subtree_and_stack(KA, VA, Left, !StackB)
)
).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
member(empty, _K, _V) :- fail.
member(two(K0, V0, T0, T1), K, V) :-
(
K = K0,
V = V0
;
tree234.member(T0, K, V)
;
tree234.member(T1, K, V)
).
member(three(K0, V0, K1, V1, T0, T1, T2), K, V) :-
(
K = K0,
V = V0
;
K = K1,
V = V1
;
tree234.member(T0, K, V)
;
tree234.member(T1, K, V)
;
tree234.member(T2, K, V)
).
member(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), K, V) :-
(
K = K0,
V = V0
;
K = K1,
V = V1
;
K = K2,
V = V2
;
tree234.member(T0, K, V)
;
tree234.member(T1, K, V)
;
tree234.member(T2, K, V)
;
tree234.member(T3, K, V)
).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
search(T, K, V) :-
(
T = empty,
fail
;
T = two(K0, V0, T0, T1),
compare(Result, K, K0),
(
Result = (<),
tree234.search(T0, K, V)
;
Result = (=),
V = V0
;
Result = (>),
tree234.search(T1, K, V)
)
;
T = three(K0, V0, K1, V1, T0, T1, T2),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.search(T0, K, V)
;
Result0 = (=),
V = V0
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
tree234.search(T1, K, V)
;
Result1 = (=),
V = V1
;
Result1 = (>),
tree234.search(T2, K, V)
)
)
;
T = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
compare(Result1, K, K1),
(
Result1 = (<),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.search(T0, K, V)
;
Result0 = (=),
V = V0
;
Result0 = (>),
tree234.search(T1, K, V)
)
;
Result1 = (=),
V = V1
;
Result1 = (>),
compare(Result2, K, K2),
(
Result2 = (<),
tree234.search(T2, K, V)
;
Result2 = (=),
V = V2
;
Result2 = (>),
tree234.search(T3, K, V)
)
)
).
lookup(T, K) = V :-
tree234.lookup(T, K, V).
lookup(T, K, V) :-
( if tree234.search(T, K, V0) then
V = V0
else
report_lookup_error("tree234.lookup: key not found.", K, V)
).
%---------------------------------------------------------------------------%
lower_bound_search(T, SearchK, K, V) :-
(
T = empty,
fail
;
T = two(K0, V0, T0, T1),
compare(Result, SearchK, K0),
(
Result = (<),
tree234.lower_bound_search(T0, SearchK, K, V)
;
Result = (=),
K = SearchK,
V = V0
;
Result = (>),
( if tree234.lower_bound_search(T1, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
T = two(_, V0, _, _),
K = K0,
V = V0
)
)
;
T = three(K0, V0, K1, V1, T0, T1, T2),
compare(Result0, SearchK, K0),
(
Result0 = (<),
tree234.lower_bound_search(T0, SearchK, K, V)
;
Result0 = (=),
K = SearchK,
V = V0
;
Result0 = (>),
compare(Result1, SearchK, K1),
(
Result1 = (<),
( if tree234.lower_bound_search(T1, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
T = three(_, V0, _, _, _, _, _),
K = K0,
V = V0
)
;
Result1 = (=),
K = SearchK,
V = V1
;
Result1 = (>),
( if tree234.lower_bound_search(T2, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K1,
V = V1
)
)
)
;
T = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
compare(Result1, SearchK, K1),
(
Result1 = (<),
compare(Result0, SearchK, K0),
(
Result0 = (<),
tree234.lower_bound_search(T0, SearchK, K, V)
;
Result0 = (=),
K = SearchK,
V = V0
;
Result0 = (>),
( if tree234.lower_bound_search(T1, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K0,
V = V0
)
)
;
Result1 = (=),
K = SearchK,
V = V1
;
Result1 = (>),
compare(Result2, SearchK, K2),
(
Result2 = (<),
( if tree234.lower_bound_search(T2, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K1,
V = V1
)
;
Result2 = (=),
K = SearchK,
V = V2
;
Result2 = (>),
( if tree234.lower_bound_search(T3, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K2,
V = V2
)
)
)
).
lower_bound_lookup(T, SearchK, K, V) :-
( if tree234.lower_bound_search(T, SearchK, K0, V0) then
K = K0,
V = V0
else
report_lookup_error("tree234.lower_bound_lookup: key not found.",
SearchK, V)
).
%---------------------------------------------------------------------------%
upper_bound_search(T, SearchK, K, V) :-
(
T = empty,
fail
;
T = two(K0, V0, T0, T1),
compare(Result, SearchK, K0),
(
Result = (<),
( if tree234.upper_bound_search(T0, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
T = two(_, V0, _, _),
K = K0,
V = V0
)
;
Result = (=),
K = SearchK,
V = V0
;
Result = (>),
tree234.upper_bound_search(T1, SearchK, K, V)
)
;
T = three(K0, V0, K1, V1, T0, T1, T2),
compare(Result0, SearchK, K0),
(
Result0 = (<),
( if tree234.upper_bound_search(T0, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K0,
V = V0
)
;
Result0 = (=),
K = SearchK,
V = V0
;
Result0 = (>),
compare(Result1, SearchK, K1),
(
Result1 = (<),
( if tree234.upper_bound_search(T1, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K1,
V = V1
)
;
Result1 = (=),
K = SearchK,
V = V1
;
Result1 = (>),
tree234.upper_bound_search(T2, SearchK, K, V)
)
)
;
T = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
compare(Result1, SearchK, K1),
(
Result1 = (<),
compare(Result0, SearchK, K0),
(
Result0 = (<),
( if tree234.upper_bound_search(T0, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K0,
V = V0
)
;
Result0 = (=),
K = SearchK,
V = V0
;
Result0 = (>),
( if tree234.upper_bound_search(T1, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K1,
V = V1
)
)
;
Result1 = (=),
K = SearchK,
V = V1
;
Result1 = (>),
compare(Result2, SearchK, K2),
(
Result2 = (<),
( if tree234.upper_bound_search(T2, SearchK, Kp, Vp) then
K = Kp,
V = Vp
else
K = K2,
V = V2
)
;
Result2 = (=),
K = SearchK,
V = V2
;
Result2 = (>),
tree234.upper_bound_search(T3, SearchK, K, V)
)
)
).
upper_bound_lookup(T, SearchK, K, V) :-
( if tree234.upper_bound_search(T, SearchK, K0, V0) then
K = K0,
V = V0
else
report_lookup_error("tree234.upper_bound_lookup: key not found.",
SearchK, V)
).
%---------------------------------------------------------------------------%
max_key(T0) = MaxKey :-
max_key(T0, MaxKey).
max_key(T0, MaxKey) :-
( T0 = two(NodeMaxKey, _, _, NodeMaxSubtree)
; T0 = three(_, _, NodeMaxKey, _, _, _, NodeMaxSubtree)
; T0 = four(_, _, _, _, NodeMaxKey, _, _, _, _, NodeMaxSubtree)
),
( if tree234.max_key(NodeMaxSubtree, MaxSubtreeKey) then
MaxKey = MaxSubtreeKey
else
MaxKey = NodeMaxKey
).
min_key(T0) = MinKey :-
min_key(T0, MinKey).
min_key(T0, MinKey) :-
( T0 = two(NodeMinKey, _, NodeMinSubtree, _)
; T0 = three(NodeMinKey, _, _, _, NodeMinSubtree, _, _)
; T0 = four(NodeMinKey, _, _, _, _, _, NodeMinSubtree, _, _, _)
),
( if tree234.min_key(NodeMinSubtree, MinSubtreeKey) then
MinKey = MinSubtreeKey
else
MinKey = NodeMinKey
).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
% tree234.insert is implemented using the simple top-down approach described
% in Sedgewick that splits 4-nodes into two 2-nodes on the downward traversal
% of the tree as we search for the right place to insert the new key-value
% pair. We know we have the right place if the subtrees of the node are
% empty (in which case we expand the node - which will always work because
% we have already split 4-nodes into 2-nodes), or if the tree itself is
% empty. This algorithm is O(lgN).
insert(K, V, Tin, Tout) :-
(
Tin = empty,
Tout = two(K, V, empty, empty)
;
Tin = two(_, _, _, _),
tree234.insert2(Tin, K, V, Tout)
;
Tin = three(_, _, _, _, _, _, _),
tree234.insert3(Tin, K, V, Tout)
;
Tin = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(Tin, MidK, MidV, Sub0, Sub1),
compare(Result1, K, MidK),
(
Result1 = (<),
tree234.insert2(Sub0, K, V, NewSub0),
Tout = two(MidK, MidV, NewSub0, Sub1)
;
Result1 = (=),
fail
;
Result1 = (>),
tree234.insert2(Sub1, K, V, NewSub1),
Tout = two(MidK, MidV, Sub0, NewSub1)
)
).
:- pred insert2(tree234(K, V), K, V, tree234(K, V)).
% :- mode insert2(di_two, di, di, uo) is semidet.
% :- mode insert2(sdi_two, in, in, uo_tree234) is semidet.
:- mode insert2(in_two, in, in, out) is semidet.
insert2(two(K0, V0, T0, T1), K, V, Tout) :-
( if
T0 = empty
% T1 = empty implied by T0 = empty.
then
compare(Result, K, K0),
(
Result = (<),
Tout = three(K, V, K0, V0, empty, empty, empty)
;
Result = (=),
fail
;
Result = (>),
Tout = three(K0, V0, K, V, empty, empty, empty)
)
else
compare(Result, K, K0),
(
Result = (<),
(
T0 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T0, MT0K, MT0V, T00, T01),
compare(Result1, K, MT0K),
(
Result1 = (<),
tree234.insert2(T00, K, V, NewT00),
Tout = three(MT0K, MT0V, K0, V0, NewT00, T01, T1)
;
Result1 = (=),
fail
;
Result1 = (>),
tree234.insert2(T01, K, V, NewT01),
Tout = three(MT0K, MT0V, K0, V0, T00, NewT01, T1)
)
;
T0 = three(_, _, _, _, _, _, _),
tree234.insert3(T0, K, V, NewT0),
Tout = two(K0, V0, NewT0, T1)
;
T0 = two(_, _, _, _),
tree234.insert2(T0, K, V, NewT0),
Tout = two(K0, V0, NewT0, T1)
;
T0 = empty,
NewT0 = two(K, V, empty, empty),
Tout = two(K0, V0, NewT0, T1)
)
;
Result = (=),
fail
;
Result = (>),
(
T1 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T1, MT1K, MT1V, T10, T11),
compare(Result1, K, MT1K),
(
Result1 = (<),
tree234.insert2(T10, K, V, NewT10),
Tout = three(K0, V0, MT1K, MT1V, T0, NewT10, T11)
;
Result1 = (=),
fail
;
Result1 = (>),
tree234.insert2(T11, K, V, NewT11),
Tout = three(K0, V0, MT1K, MT1V, T0, T10, NewT11)
)
;
T1 = three(_, _, _, _, _, _, _),
tree234.insert3(T1, K, V, NewT1),
Tout = two(K0, V0, T0, NewT1)
;
T1 = two(_, _, _, _),
tree234.insert2(T1, K, V, NewT1),
Tout = two(K0, V0, T0, NewT1)
;
T1 = empty,
NewT1 = two(K, V, empty, empty),
Tout = two(K0, V0, T0, NewT1)
)
)
).
:- pred insert3(tree234(K, V), K, V, tree234(K, V)).
% :- mode insert3(di_three, di, di, uo) is semidet.
% :- mode insert3(sdi_three, in, in, uo_tree234) is semidet.
:- mode insert3(in_three, in, in, out) is semidet.
insert3(three(K0, V0, K1, V1, T0, T1, T2), K, V, Tout) :-
( if
T0 = empty
% T1 = empty implied by T0 = empty.
% T2 = empty implied by T0 = empty.
then
compare(Result0, K, K0),
(
Result0 = (<),
Tout = four(K, V, K0, V0, K1, V1, empty, empty, empty, empty)
;
Result0 = (=),
fail
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
Tout = four(K0, V0, K, V, K1, V1, empty, empty, empty, empty)
;
Result1 = (=),
fail
;
Result1 = (>),
Tout = four(K0, V0, K1, V1, K, V, empty, empty, empty, empty)
)
)
else
compare(Result0, K, K0),
(
Result0 = (<),
(
T0 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T0, MT0K, MT0V, T00, T01),
compare(ResultM, K, MT0K),
(
ResultM = (<),
tree234.insert2(T00, K, V, NewT00),
Tout = four(MT0K, MT0V, K0, V0, K1, V1,
NewT00, T01, T1, T2)
;
ResultM = (=),
fail
;
ResultM = (>),
tree234.insert2(T01, K, V, NewT01),
Tout = four(MT0K, MT0V, K0, V0, K1, V1,
T00, NewT01, T1, T2)
)
;
T0 = three(_, _, _, _, _, _, _),
tree234.insert3(T0, K, V, NewT0),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
T0 = two(_, _, _, _),
tree234.insert2(T0, K, V, NewT0),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
T0 = empty,
NewT0 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
)
;
Result0 = (=),
fail
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
(
T1 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T1, MT1K, MT1V, T10, T11),
compare(ResultM, K, MT1K),
(
ResultM = (<),
tree234.insert2(T10, K, V, NewT10),
Tout = four(K0, V0, MT1K, MT1V, K1, V1,
T0, NewT10, T11, T2)
;
ResultM = (=),
fail
;
ResultM = (>),
tree234.insert2(T11, K, V, NewT11),
Tout = four(K0, V0, MT1K, MT1V, K1, V1,
T0, T10, NewT11, T2)
)
;
T1 = three(_, _, _, _, _, _, _),
tree234.insert3(T1, K, V, NewT1),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
T1 = two(_, _, _, _),
tree234.insert2(T1, K, V, NewT1),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
T1 = empty,
NewT1 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
)
;
Result1 = (=),
fail
;
Result1 = (>),
(
T2 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T2, MT2K, MT2V,
T20, T21),
compare(ResultM, K, MT2K),
(
ResultM = (<),
tree234.insert2(T20, K, V, NewT20),
Tout = four(K0, V0, K1, V1, MT2K, MT2V,
T0, T1, NewT20, T21)
;
ResultM = (=),
fail
;
ResultM = (>),
tree234.insert2(T21, K, V, NewT21),
Tout = four(K0, V0, K1, V1, MT2K, MT2V,
T0, T1, T20, NewT21)
)
;
T2 = three(_, _, _, _, _, _, _),
tree234.insert3(T2, K, V, NewT2),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
;
T2 = two(_, _, _, _),
tree234.insert2(T2, K, V, NewT2),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
;
T2 = empty,
NewT2 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
)
)
)
).
%---------------------------------------------------------------------------%
search_insert(K, V, MaybeOldV, Tin, Tout) :-
(
Tin = empty,
MaybeOldV = no,
Tout = two(K, V, empty, empty)
;
Tin = two(_, _, _, _),
tree234.search_insert2(Tin, K, V, MaybeOldV, Tout)
;
Tin = three(_, _, _, _, _, _, _),
tree234.search_insert3(Tin, K, V, MaybeOldV, Tout)
;
Tin = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(Tin, MidK, MidV, Sub0, Sub1),
compare(Result1, K, MidK),
(
Result1 = (<),
tree234.search_insert2(Sub0, K, V, MaybeOldV, NewSub0),
(
MaybeOldV = no,
Tout = two(MidK, MidV, NewSub0, Sub1)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
Result1 = (=),
MaybeOldV = yes(MidV),
Tout = Tin
;
Result1 = (>),
tree234.search_insert2(Sub1, K, V, MaybeOldV, NewSub1),
(
MaybeOldV = no,
Tout = two(MidK, MidV, Sub0, NewSub1)
;
MaybeOldV = yes(_),
Tout = Tin
)
)
).
:- pred search_insert2(tree234(K, V)::in_two, K::in, V::in,
maybe(V)::out, tree234(K, V)::out) is det.
search_insert2(Tin, K, V, MaybeOldV, Tout) :-
Tin = two(K0, V0, T0, T1),
( if
T0 = empty
% T1 = empty implied by T0 = empty.
then
compare(Result, K, K0),
(
Result = (<),
MaybeOldV = no,
Tout = three(K, V, K0, V0, empty, empty, empty)
;
Result = (=),
MaybeOldV = yes(V0),
Tout = Tin
;
Result = (>),
MaybeOldV = no,
Tout = three(K0, V0, K, V, empty, empty, empty)
)
else
compare(Result, K, K0),
(
Result = (<),
(
T0 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T0, MT0K, MT0V, T00, T01),
compare(Result1, K, MT0K),
(
Result1 = (<),
tree234.search_insert2(T00, K, V, MaybeOldV, NewT00),
(
MaybeOldV = no,
Tout = three(MT0K, MT0V, K0, V0, NewT00, T01, T1)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
Result1 = (=),
MaybeOldV = yes(MT0V),
Tout = Tin
;
Result1 = (>),
tree234.search_insert2(T01, K, V, MaybeOldV, NewT01),
(
MaybeOldV = no,
Tout = three(MT0K, MT0V, K0, V0, T00, NewT01, T1)
;
MaybeOldV = yes(_),
Tout = Tin
)
)
;
(
T0 = three(_, _, _, _, _, _, _),
tree234.search_insert3(T0, K, V, MaybeOldV, NewT0)
;
T0 = two(_, _, _, _),
tree234.search_insert2(T0, K, V, MaybeOldV, NewT0)
),
(
MaybeOldV = no,
Tout = two(K0, V0, NewT0, T1)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
T0 = empty,
MaybeOldV = no,
NewT0 = two(K, V, empty, empty),
Tout = two(K0, V0, NewT0, T1)
)
;
Result = (=),
MaybeOldV = yes(V0),
Tout = Tin
;
Result = (>),
(
T1 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T1, MT1K, MT1V, T10, T11),
compare(Result1, K, MT1K),
(
Result1 = (<),
tree234.search_insert2(T10, K, V, MaybeOldV, NewT10),
(
MaybeOldV = no,
Tout = three(K0, V0, MT1K, MT1V, T0, NewT10, T11)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
Result1 = (=),
MaybeOldV = yes(MT1V),
Tout = Tin
;
Result1 = (>),
tree234.search_insert2(T11, K, V, MaybeOldV, NewT11),
(
MaybeOldV = no,
Tout = three(K0, V0, MT1K, MT1V, T0, T10, NewT11)
;
MaybeOldV = yes(_),
Tout = Tin
)
)
;
(
T1 = three(_, _, _, _, _, _, _),
tree234.search_insert3(T1, K, V, MaybeOldV, NewT1)
;
T1 = two(_, _, _, _),
tree234.search_insert2(T1, K, V, MaybeOldV, NewT1)
),
(
MaybeOldV = no,
Tout = two(K0, V0, T0, NewT1)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
T1 = empty,
MaybeOldV = no,
NewT1 = two(K, V, empty, empty),
Tout = two(K0, V0, T0, NewT1)
)
)
).
:- pred search_insert3(tree234(K, V)::in_three, K::in, V::in,
maybe(V)::out, tree234(K, V)::out) is det.
search_insert3(Tin, K, V, MaybeOldV, Tout) :-
Tin = three(K0, V0, K1, V1, T0, T1, T2),
( if
T0 = empty
% T1 = empty implied by T0 = empty.
% T2 = empty implied by T0 = empty.
then
compare(Result0, K, K0),
(
Result0 = (<),
MaybeOldV = no,
Tout = four(K, V, K0, V0, K1, V1, empty, empty, empty, empty)
;
Result0 = (=),
MaybeOldV = yes(V0),
Tout = Tin
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
MaybeOldV = no,
Tout = four(K0, V0, K, V, K1, V1, empty, empty, empty, empty)
;
Result1 = (=),
MaybeOldV = yes(V1),
Tout = Tin
;
Result1 = (>),
MaybeOldV = no,
Tout = four(K0, V0, K1, V1, K, V, empty, empty, empty, empty)
)
)
else
compare(Result0, K, K0),
(
Result0 = (<),
(
T0 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T0, MT0K, MT0V, T00, T01),
compare(ResultM, K, MT0K),
(
ResultM = (<),
tree234.search_insert2(T00, K, V, MaybeOldV, NewT00),
(
MaybeOldV = no,
Tout = four(MT0K, MT0V, K0, V0, K1, V1,
NewT00, T01, T1, T2)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
ResultM = (=),
MaybeOldV = yes(MT0V),
Tout = Tin
;
ResultM = (>),
tree234.search_insert2(T01, K, V, MaybeOldV, NewT01),
(
MaybeOldV = no,
Tout = four(MT0K, MT0V, K0, V0, K1, V1,
T00, NewT01, T1, T2)
;
MaybeOldV = yes(_),
Tout = Tin
)
)
;
(
T0 = three(_, _, _, _, _, _, _),
tree234.search_insert3(T0, K, V, MaybeOldV, NewT0)
;
T0 = two(_, _, _, _),
tree234.search_insert2(T0, K, V, MaybeOldV, NewT0)
),
(
MaybeOldV = no,
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
T0 = empty,
MaybeOldV = no,
NewT0 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
)
;
Result0 = (=),
MaybeOldV = yes(V0),
Tout = Tin
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
(
T1 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T1, MT1K, MT1V, T10, T11),
compare(ResultM, K, MT1K),
(
ResultM = (<),
tree234.search_insert2(T10, K, V, MaybeOldV, NewT10),
(
MaybeOldV = no,
Tout = four(K0, V0, MT1K, MT1V, K1, V1,
T0, NewT10, T11, T2)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
ResultM = (=),
MaybeOldV = yes(MT1V),
Tout = Tin
;
ResultM = (>),
tree234.search_insert2(T11, K, V, MaybeOldV, NewT11),
(
MaybeOldV = no,
Tout = four(K0, V0, MT1K, MT1V, K1, V1,
T0, T10, NewT11, T2)
;
MaybeOldV = yes(_),
Tout = Tin
)
)
;
(
T1 = three(_, _, _, _, _, _, _),
tree234.search_insert3(T1, K, V, MaybeOldV, NewT1)
;
T1 = two(_, _, _, _),
tree234.search_insert2(T1, K, V, MaybeOldV, NewT1)
),
(
MaybeOldV = no,
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
T1 = empty,
MaybeOldV = no,
NewT1 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
)
;
Result1 = (=),
MaybeOldV = yes(V1),
Tout = Tin
;
Result1 = (>),
(
T2 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T2, MT2K, MT2V, T20, T21),
compare(ResultM, K, MT2K),
(
ResultM = (<),
tree234.search_insert2(T20, K, V, MaybeOldV, NewT20),
(
MaybeOldV = no,
Tout = four(K0, V0, K1, V1, MT2K, MT2V,
T0, T1, NewT20, T21)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
ResultM = (=),
MaybeOldV = yes(MT2V),
Tout = Tin
;
ResultM = (>),
tree234.search_insert2(T21, K, V, MaybeOldV, NewT21),
(
MaybeOldV = no,
Tout = four(K0, V0, K1, V1, MT2K, MT2V,
T0, T1, T20, NewT21)
;
MaybeOldV = yes(_),
Tout = Tin
)
)
;
(
T2 = three(_, _, _, _, _, _, _),
tree234.search_insert3(T2, K, V, MaybeOldV, NewT2)
;
T2 = two(_, _, _, _),
tree234.search_insert2(T2, K, V, MaybeOldV, NewT2)
),
(
MaybeOldV = no,
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
;
MaybeOldV = yes(_),
Tout = Tin
)
;
T2 = empty,
MaybeOldV = no,
NewT2 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
)
)
)
).
%---------------------------------------------------------------------------%
update(K, V, Tin, Tout) :-
(
Tin = empty,
fail
;
Tin = two(K0, V0, T0, T1),
compare(Result, K, K0),
(
Result = (<),
tree234.update(K, V, T0, NewT0),
Tout = two(K0, V0, NewT0, T1)
;
Result = (=),
Tout = two(K0, V, T0, T1)
;
Result = (>),
tree234.update(K, V, T1, NewT1),
Tout = two(K0, V0, T0, NewT1)
)
;
Tin = three(K0, V0, K1, V1, T0, T1, T2),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.update(K, V, T0, NewT0),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
Result0 = (=),
Tout = three(K0, V, K1, V1, T0, T1, T2)
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
tree234.update(K, V, T1, NewT1),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
Result1 = (=),
Tout = three(K0, V0, K1, V, T0, T1, T2)
;
Result1 = (>),
tree234.update(K, V, T2, NewT2),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
)
)
;
Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
compare(Result1, K, K1),
(
Result1 = (<),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.update(K, V, T0, NewT0),
Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3)
;
Result0 = (=),
Tout = four(K0, V, K1, V1, K2, V2, T0, T1, T2, T3)
;
Result0 = (>),
tree234.update(K, V, T1, NewT1),
Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3)
)
;
Result1 = (=),
Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
;
Result1 = (>),
compare(Result2, K, K2),
(
Result2 = (<),
tree234.update(K, V, T2, NewT2),
Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3)
;
Result2 = (=),
Tout = four(K0, V0, K1, V1, K2, V, T0, T1, T2, T3)
;
Result2 = (>),
tree234.update(K, V, T3, NewT3),
Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3)
)
)
).
%---------------------------------------------------------------------------%
set(!.T, K, V) = !:T :-
tree234.set(K, V, !T).
set(K, V, Tin, Tout) :-
% tree234.set uses the same algorithm as used for tree234.insert,
% except that instead of failing for equal keys, we replace the value.
(
Tin = empty,
Tout = two(K, V, empty, empty)
;
Tin = two(_, _, _, _),
tree234.set2(Tin, K, V, Tout)
;
Tin = three(_, _, _, _, _, _, _),
tree234.set3(Tin, K, V, Tout)
;
Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
compare(Result1, K, K1),
(
Result1 = (<),
Sub0 = two(K0, V0, T0, T1),
Sub1 = two(K2, V2, T2, T3),
tree234.set2(Sub0, K, V, NewSub0),
Tout = two(K1, V1, NewSub0, Sub1)
;
Result1 = (=),
Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
;
Result1 = (>),
Sub0 = two(K0, V0, T0, T1),
Sub1 = two(K2, V2, T2, T3),
tree234.set2(Sub1, K, V, NewSub1),
Tout = two(K1, V1, Sub0, NewSub1)
)
).
:- pred set2(tree234(K, V), K, V, tree234(K, V)).
:- mode set2(di_two, di, di, uo) is det.
% :- mode set2(sdi_two, in, in, uo_tree234) is det.
:- mode set2(in_two, in, in, out) is det.
:- pragma type_spec(set2(in_two, in, in, out), K = var(_)).
set2(two(K0, V0, T0, T1), K, V, Tout) :-
( if
T0 = empty
% T1 = empty implied by T0 = empty.
then
compare(Result, K, K0),
(
Result = (<),
Tout = three(K, V, K0, V0, empty, empty, empty)
;
Result = (=),
Tout = two(K, V, T0, T1)
;
Result = (>),
Tout = three(K0, V0, K, V, empty, empty, empty)
)
else
compare(Result, K, K0),
(
Result = (<),
(
T0 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T0, MT0K, MT0V, T00, T01),
compare(Result1, K, MT0K),
(
Result1 = (<),
tree234.set2(T00, K, V, NewT00),
Tout = three(MT0K, MT0V, K0, V0, NewT00, T01, T1)
;
Result1 = (=),
Tout = three(MT0K, V, K0, V0, T00, T01, T1)
;
Result1 = (>),
tree234.set2(T01, K, V, NewT01),
Tout = three(MT0K, MT0V, K0, V0, T00, NewT01, T1)
)
;
T0 = three(_, _, _, _, _, _, _),
tree234.set3(T0, K, V, NewT0),
Tout = two(K0, V0, NewT0, T1)
;
T0 = two(_, _, _, _),
tree234.set2(T0, K, V, NewT0),
Tout = two(K0, V0, NewT0, T1)
;
T0 = empty,
NewT0 = two(K, V, empty, empty),
Tout = two(K0, V0, NewT0, T1)
)
;
Result = (=),
Tout = two(K, V, T0, T1)
;
Result = (>),
(
T1 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T1, MT1K, MT1V, T10, T11),
compare(Result1, K, MT1K),
(
Result1 = (<),
tree234.set2(T10, K, V, NewT10),
Tout = three(K0, V0, MT1K, MT1V, T0, NewT10, T11)
;
Result1 = (=),
Tout = three(K0, V0, MT1K, V, T0, T10, T11)
;
Result1 = (>),
tree234.set2(T11, K, V, NewT11),
Tout = three(K0, V0, MT1K, MT1V, T0, T10, NewT11)
)
;
T1 = three(_, _, _, _, _, _, _),
tree234.set3(T1, K, V, NewT1),
Tout = two(K0, V0, T0, NewT1)
;
T1 = two(_, _, _, _),
tree234.set2(T1, K, V, NewT1),
Tout = two(K0, V0, T0, NewT1)
;
T1 = empty,
NewT1 = two(K, V, empty, empty),
Tout = two(K0, V0, T0, NewT1)
)
)
).
:- pred set3(tree234(K, V), K, V, tree234(K, V)).
:- mode set3(di_three, di, di, uo) is det.
% :- mode set3(sdi_three, in, in, uo_tree234) is det.
:- mode set3(in_three, in, in, out) is det.
:- pragma type_spec(set3(in_three, in, in, out), K = var(_)).
set3(three(K0, V0, K1, V1, T0, T1, T2), K, V, Tout) :-
( if
T0 = empty
% T1 = empty implied by T0 = empty
% T2 = empty implied by T0 = empty
then
compare(Result0, K, K0),
(
Result0 = (<),
Tout = four(K, V, K0, V0, K1, V1, empty, empty, empty, empty)
;
Result0 = (=),
Tout = three(K0, V, K1, V1, empty, empty, empty)
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
Tout = four(K0, V0, K, V, K1, V1, empty, empty, empty, empty)
;
Result1 = (=),
Tout = three(K0, V0, K1, V, empty, empty, empty)
;
Result1 = (>),
Tout = four(K0, V0, K1, V1, K, V, empty, empty, empty, empty)
)
)
else
compare(Result0, K, K0),
(
Result0 = (<),
(
T0 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T0, MT0K, MT0V, T00, T01),
compare(ResultM, K, MT0K),
(
ResultM = (<),
tree234.set2(T00, K, V, NewT00),
Tout = four(MT0K, MT0V, K0, V0, K1, V1,
NewT00, T01, T1, T2)
;
ResultM = (=),
Tout = four(MT0K, V, K0, V0, K1, V1, T00, T01, T1, T2)
;
ResultM = (>),
tree234.set2(T01, K, V, NewT01),
Tout = four(MT0K, MT0V, K0, V0, K1, V1,
T00, NewT01, T1, T2)
)
;
T0 = three(_, _, _, _, _, _, _),
tree234.set3(T0, K, V, NewT0),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
T0 = two(_, _, _, _),
tree234.set2(T0, K, V, NewT0),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
T0 = empty,
NewT0 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
)
;
Result0 = (=),
Tout = three(K0, V, K1, V1, T0, T1, T2)
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
(
T1 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T1, MT1K, MT1V, T10, T11),
compare(ResultM, K, MT1K),
(
ResultM = (<),
tree234.set2(T10, K, V, NewT10),
Tout = four(K0, V0, MT1K, MT1V, K1, V1,
T0, NewT10, T11, T2)
;
ResultM = (=),
Tout = four(K0, V0, MT1K, V, K1, V1, T0, T10, T11, T2)
;
ResultM = (>),
tree234.set2(T11, K, V, NewT11),
Tout = four(K0, V0, MT1K, MT1V, K1, V1,
T0, T10, NewT11, T2)
)
;
T1 = three(_, _, _, _, _, _, _),
tree234.set3(T1, K, V, NewT1),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
T1 = two(_, _, _, _),
tree234.set2(T1, K, V, NewT1),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
T1 = empty,
NewT1 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
)
;
Result1 = (=),
Tout = three(K0, V0, K, V, T0, T1, T2)
;
Result1 = (>),
(
T2 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T2, MT2K, MT2V, T20, T21),
compare(ResultM, K, MT2K),
(
ResultM = (<),
tree234.set2(T20, K, V, NewT20),
Tout = four(K0, V0, K1, V1, MT2K, MT2V,
T0, T1, NewT20, T21)
;
ResultM = (=),
Tout = four(K0, V0, K1, V1, MT2K, V, T0, T1, T20, T21)
;
ResultM = (>),
tree234.set2(T21, K, V, NewT21),
Tout = four(K0, V0, K1, V1, MT2K, MT2V,
T0, T1, T20, NewT21)
)
;
T2 = three(_, _, _, _, _, _, _),
tree234.set3(T2, K, V, NewT2),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
;
T2 = two(_, _, _, _),
tree234.set2(T2, K, V, NewT2),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
;
T2 = empty,
NewT2 = two(K, V, empty, empty),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
)
)
)
).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
transform_value(P, K, Tin, Tout) :-
(
Tin = empty,
fail
;
Tin = two(K0, V0, T0, T1),
compare(Result, K, K0),
(
Result = (<),
tree234.transform_value(P, K, T0, NewT0),
Tout = two(K0, V0, NewT0, T1)
;
Result = (=),
P(V0, VNew),
Tout = two(K0, VNew, T0, T1)
;
Result = (>),
tree234.transform_value(P, K, T1, NewT1),
Tout = two(K0, V0, T0, NewT1)
)
;
Tin = three(K0, V0, K1, V1, T0, T1, T2),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.transform_value(P, K, T0, NewT0),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
Result0 = (=),
P(V0, VNew),
Tout = three(K0, VNew, K1, V1, T0, T1, T2)
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
tree234.transform_value(P, K, T1, NewT1),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
Result1 = (=),
P(V1, VNew),
Tout = three(K0, V0, K1, VNew, T0, T1, T2)
;
Result1 = (>),
tree234.transform_value(P, K, T2, NewT2),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
)
)
;
Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
compare(Result1, K, K1),
(
Result1 = (<),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.transform_value(P, K, T0, NewT0),
Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3)
;
Result0 = (=),
P(V0, VNew),
Tout = four(K0, VNew, K1, V1, K2, V2, T0, T1, T2, T3)
;
Result0 = (>),
tree234.transform_value(P, K, T1, NewT1),
Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3)
)
;
Result1 = (=),
P(V1, VNew),
Tout = four(K0, V0, K1, VNew, K2, V2, T0, T1, T2, T3)
;
Result1 = (>),
compare(Result2, K, K2),
(
Result2 = (<),
tree234.transform_value(P, K, T2, NewT2),
Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3)
;
Result2 = (=),
P(V2, VNew),
Tout = four(K0, V0, K1, V1, K2, VNew, T0, T1, T2, T3)
;
Result2 = (>),
tree234.transform_value(P, K, T3, NewT3),
Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3)
)
)
).
%---------------------------------------------------------------------------%
%
% Utilities used by the insertion predicates.
%
:- pred split_four(tree234(K, V), K, V, tree234(K, V), tree234(K, V)).
:- mode split_four(di_four, uo, uo, uo_two, uo_two) is det.
% :- mode split_four(sdi_four, out, out, suo_two, suo_two) is det.
:- mode split_four(in_four, out, out, out_two, out_two) is det.
split_four(Tin, MidK, MidV, Sub0, Sub1) :-
Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
Sub0 = two(K0, V0, T0, T1),
MidK = K1,
MidV = V1,
Sub1 = two(K2, V2, T2, T3).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
delete(!.T, K) = !:T :-
tree234.delete(K, !T).
delete(K, Tin, Tout) :-
tree234.delete_2(Tin, K, Tout, _).
% When deleting an item from a tree, the height of the tree may be
% reduced by one. The last argument says whether this has occurred.
%
:- pred delete_2(tree234(K, V), K, tree234(K, V), maybe_reduced_height).
%:- mode delete_2(di, in, uo, out) is det.
:- mode delete_2(in, in, out, out) is det.
delete_2(Tin, K, Tout, RH) :-
(
Tin = empty,
Tout = empty,
RH = did_not_reduce_height
;
Tin = two(K0, V0, T0, T1),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.delete_2(T0, K, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = two(K0, V0, NewT0, T1),
RH = did_not_reduce_height
)
;
Result0 = (=),
( if tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) then
(
RHT1 = reduced_height,
fix_2node_t1(ST1K, ST1V, T0, NewT1, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = two(ST1K, ST1V, T0, NewT1),
RH = did_not_reduce_height
)
else
% T1 must be empty
Tout = T0,
RH = reduced_height
)
;
Result0 = (>),
tree234.delete_2(T1, K, NewT1, RHT1),
(
RHT1 = reduced_height,
fix_2node_t1(K0, V0, T0, NewT1, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = two(K0, V0, T0, NewT1),
RH = did_not_reduce_height
)
)
;
Tin = three(K0, V0, K1, V1, T0, T1, T2),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.delete_2(T0, K, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
RH = did_not_reduce_height
)
;
Result0 = (=),
( if tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) then
(
RHT1 = reduced_height,
fix_3node_t1(ST1K, ST1V, K1, V1, T0, NewT1, T2, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = three(ST1K, ST1V, K1, V1, T0, NewT1, T2),
RH = did_not_reduce_height
)
else
% T1 must be empty
Tout = two(K1, V1, T0, T2),
RH = did_not_reduce_height
)
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
tree234.delete_2(T1, K, NewT1, RHT1),
(
RHT1 = reduced_height,
fix_3node_t1(K0, V0, K1, V1, T0, NewT1, T2, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = three(K0, V0, K1, V1, T0, NewT1, T2),
RH = did_not_reduce_height
)
;
Result1 = (=),
( if
tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2)
then
(
RHT2 = reduced_height,
fix_3node_t2(K0, V0, ST2K, ST2V, T0, T1, NewT2, Tout,
RH)
;
RHT2 = did_not_reduce_height,
Tout = three(K0, V0, ST2K, ST2V, T0, T1, NewT2),
RH = did_not_reduce_height
)
else
% T2 must be empty.
Tout = two(K0, V0, T0, T1),
RH = did_not_reduce_height
)
;
Result1 = (>),
tree234.delete_2(T2, K, NewT2, RHT2),
(
RHT2 = reduced_height,
fix_3node_t2(K0, V0, K1, V1, T0, T1, NewT2, Tout, RH)
;
RHT2 = did_not_reduce_height,
Tout = three(K0, V0, K1, V1, T0, T1, NewT2),
RH = did_not_reduce_height
)
)
)
;
Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
compare(Result1, K, K1),
(
Result1 = (<),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.delete_2(T0, K, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_4node_t0(K0, V0, K1, V1, K2, V2,
NewT0, T1, T2, T3, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
RH = did_not_reduce_height
)
;
Result0 = (=),
( if
tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1)
then
(
RHT1 = reduced_height,
fix_4node_t1(ST1K, ST1V, K1, V1, K2, V2,
T0, NewT1, T2, T3, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = four(ST1K, ST1V, K1, V1, K2, V2,
T0, NewT1, T2, T3),
RH = did_not_reduce_height
)
else
% T1 must be empty.
Tout = three(K1, V1, K2, V2, T0, T2, T3),
RH = did_not_reduce_height
)
;
Result0 = (>),
tree234.delete_2(T1, K, NewT1, RHT1),
(
RHT1 = reduced_height,
fix_4node_t1(K0, V0, K1, V1, K2, V2,
T0, NewT1, T2, T3, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3),
RH = did_not_reduce_height
)
)
;
Result1 = (=),
( if tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) then
(
RHT2 = reduced_height,
fix_4node_t2(K0, V0, ST2K, ST2V, K2, V2,
T0, T1, NewT2, T3, Tout, RH)
;
RHT2 = did_not_reduce_height,
Tout = four(K0, V0, ST2K, ST2V, K2, V2,
T0, T1, NewT2, T3),
RH = did_not_reduce_height
)
else
% T2 must be empty
Tout = three(K0, V0, K2, V2, T0, T1, T3),
RH = did_not_reduce_height
)
;
Result1 = (>),
compare(Result2, K, K2),
(
Result2 = (<),
tree234.delete_2(T2, K, NewT2, RHT2),
(
RHT2 = reduced_height,
fix_4node_t2(K0, V0, K1, V1, K2, V2,
T0, T1, NewT2, T3, Tout, RH)
;
RHT2 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3),
RH = did_not_reduce_height
)
;
Result2 = (=),
( if
tree234.remove_smallest_2(T3, ST3K, ST3V, NewT3, RHT3)
then
(
RHT3 = reduced_height,
fix_4node_t3(K0, V0, K1, V1, ST3K, ST3V,
T0, T1, T2, NewT3, Tout, RH)
;
RHT3 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, ST3K, ST3V,
T0, T1, T2, NewT3),
RH = did_not_reduce_height
)
else
% T3 must be empty
Tout = three(K0, V0, K1, V1, T0, T1, T2),
RH = did_not_reduce_height
)
;
Result2 = (>),
tree234.delete_2(T3, K, NewT3, RHT3),
(
RHT3 = reduced_height,
fix_4node_t3(K0, V0, K1, V1, K2, V2,
T0, T1, T2, NewT3, Tout, RH)
;
RHT3 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3),
RH = did_not_reduce_height
)
)
)
).
%---------------------------------------------------------------------------%
remove(K, V, Tin, Tout) :-
% We use the same algorithm as tree234.delete.
tree234.remove_2(Tin, K, V, Tout, _).
:- pred remove_2(tree234(K, V), K, V, tree234(K, V), maybe_reduced_height).
%:- mode remove_2(di, in, uo, uo, out) is semidet.
:- mode remove_2(in, in, out, out, out) is semidet.
remove_2(Tin, K, V, Tout, RH) :-
(
Tin = empty,
fail
;
Tin = two(K0, V0, T0, T1),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.remove_2(T0, K, V, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = two(K0, V0, NewT0, T1),
RH = did_not_reduce_height
)
;
Result0 = (=),
( if tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) then
(
RHT1 = reduced_height,
fix_2node_t1(ST1K, ST1V, T0, NewT1, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = two(ST1K, ST1V, T0, NewT1),
RH = did_not_reduce_height
)
else
% T1 must be empty.
Tout = T0,
RH = reduced_height
),
V = V0
;
Result0 = (>),
tree234.remove_2(T1, K, V, NewT1, RHT1),
(
RHT1 = reduced_height,
fix_2node_t1(K0, V0, T0, NewT1, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = two(K0, V0, T0, NewT1),
RH = did_not_reduce_height
)
)
;
Tin = three(K0, V0, K1, V1, T0, T1, T2),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.remove_2(T0, K, V, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
RH = did_not_reduce_height
)
;
Result0 = (=),
( if tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) then
(
RHT1 = reduced_height,
fix_3node_t1(ST1K, ST1V, K1, V1, T0, NewT1, T2, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = three(ST1K, ST1V, K1, V1, T0, NewT1, T2),
RH = did_not_reduce_height
)
else
% T1 must be empty.
Tout = two(K1, V1, T0, T2),
RH = did_not_reduce_height
),
V = V0
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
tree234.remove_2(T1, K, V, NewT1, RHT1),
(
RHT1 = reduced_height,
fix_3node_t1(K0, V0, K1, V1, T0, NewT1, T2, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = three(K0, V0, K1, V1, T0, NewT1, T2),
RH = did_not_reduce_height
)
;
Result1 = (=),
( if
tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2)
then
(
RHT2 = reduced_height,
fix_3node_t2(K0, V0, ST2K, ST2V,
T0, T1, NewT2, Tout, RH)
;
RHT2 = did_not_reduce_height,
Tout = three(K0, V0, ST2K, ST2V, T0, T1, NewT2),
RH = did_not_reduce_height
)
else
% T2 must be empty.
Tout = two(K0, V0, T0, T1),
RH = did_not_reduce_height
),
V = V1
;
Result1 = (>),
tree234.remove_2(T2, K, V, NewT2, RHT2),
(
RHT2 = reduced_height,
fix_3node_t2(K0, V0, K1, V1, T0, T1, NewT2, Tout, RH)
;
RHT2 = did_not_reduce_height,
Tout = three(K0, V0, K1, V1, T0, T1, NewT2),
RH = did_not_reduce_height
)
)
)
;
Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
compare(Result1, K, K1),
(
Result1 = (<),
compare(Result0, K, K0),
(
Result0 = (<),
tree234.remove_2(T0, K, V, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_4node_t0(K0, V0, K1, V1, K2, V2,
NewT0, T1, T2, T3, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
RH = did_not_reduce_height
)
;
Result0 = (=),
( if
tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1)
then
(
RHT1 = reduced_height,
fix_4node_t1(ST1K, ST1V, K1, V1, K2, V2,
T0, NewT1, T2, T3, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = four(ST1K, ST1V, K1, V1, K2, V2,
T0, NewT1, T2, T3),
RH = did_not_reduce_height
)
else
% T1 must be empty.
Tout = three(K1, V1, K2, V2, T0, T2, T3),
RH = did_not_reduce_height
),
V = V0
;
Result0 = (>),
tree234.remove_2(T1, K, V, NewT1, RHT1),
(
RHT1 = reduced_height,
fix_4node_t1(K0, V0, K1, V1, K2, V2,
T0, NewT1, T2, T3, Tout, RH)
;
RHT1 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3),
RH = did_not_reduce_height
)
)
;
Result1 = (=),
( if tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) then
(
RHT2 = reduced_height,
fix_4node_t2(K0, V0, ST2K, ST2V, K2, V2,
T0, T1, NewT2, T3, Tout, RH)
;
RHT2 = did_not_reduce_height,
Tout = four(K0, V0, ST2K, ST2V, K2, V2, T0, T1, NewT2, T3),
RH = did_not_reduce_height
)
else
% T2 must be empty.
Tout = three(K0, V0, K2, V2, T0, T1, T3),
RH = did_not_reduce_height
),
V = V1
;
Result1 = (>),
compare(Result2, K, K2),
(
Result2 = (<),
tree234.remove_2(T2, K, V, NewT2, RHT2),
(
RHT2 = reduced_height,
fix_4node_t2(K0, V0, K1, V1, K2, V2,
T0, T1, NewT2, T3, Tout, RH)
;
RHT2 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3),
RH = did_not_reduce_height
)
;
Result2 = (=),
( if
tree234.remove_smallest_2(T3, ST3K, ST3V, NewT3, RHT3)
then
(
RHT3 = reduced_height,
fix_4node_t3(K0, V0, K1, V1, ST3K, ST3V,
T0, T1, T2, NewT3, Tout, RH)
;
RHT3 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, ST3K, ST3V,
T0, T1, T2, NewT3),
RH = did_not_reduce_height
)
else
% T3 must be empty.
Tout = three(K0, V0, K1, V1, T0, T1, T2),
RH = did_not_reduce_height
),
V = V2
;
Result2 = (>),
tree234.remove_2(T3, K, V, NewT3, RHT3),
(
RHT3 = reduced_height,
fix_4node_t3(K0, V0, K1, V1, K2, V2,
T0, T1, T2, NewT3, Tout, RH)
;
RHT3 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3),
RH = did_not_reduce_height
)
)
)
).
%---------------------------------------------------------------------------%
% The algorithm we use is similar to tree234.delete, except that we
% always go down the left subtree.
remove_smallest(K, V, Tin, Tout) :-
tree234.remove_smallest_2(Tin, K, V, Tout, _).
:- pred remove_smallest_2(tree234(K, V), K, V, tree234(K, V),
maybe_reduced_height).
%:- mode remove_smallest_2(di, uo, uo, uo, out) is semidet.
:- mode remove_smallest_2(in, out, out, out, out) is semidet.
remove_smallest_2(Tin, K, V, Tout, RH) :-
(
Tin = empty,
fail
;
Tin = two(K0, V0, T0, T1),
( if T0 = empty then
K = K0,
V = V0,
Tout = T1,
RH = reduced_height
else
tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = two(K0, V0, NewT0, T1),
RH = did_not_reduce_height
)
)
;
Tin = three(K0, V0, K1, V1, T0, T1, T2),
( if T0 = empty then
K = K0,
V = V0,
Tout = two(K1, V1, T1, T2),
RH = did_not_reduce_height
else
tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
RH = did_not_reduce_height
)
)
;
Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
( if T0 = empty then
K = K0,
V = V0,
Tout = three(K1, V1, K2, V2, T1, T2, T3),
RH = did_not_reduce_height
else
tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
(
RHT0 = reduced_height,
fix_4node_t0(K0, V0, K1, V1, K2, V2,
NewT0, T1, T2, T3, Tout, RH)
;
RHT0 = did_not_reduce_height,
Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
RH = did_not_reduce_height
)
)
).
%---------------------------------------------------------------------------%
%
% Utilities used by the deletion predicates.
%
% The input to the following group of predicates are the components of a two-,
% three- or four-node in which the height of the indicated subtree is one less
% than it should be. If it is possible to increase the height of that subtree
% by moving into it elements from its neighboring subtrees, do so, and return
% the resulting tree with RH set to no. Otherwise, return a balanced tree
% whose height is reduced by one, with RH set to yes to indicate the
% reduced height.
%
:- pred fix_2node_t0(K, V, tree234(K, V), tree234(K, V), tree234(K, V),
maybe_reduced_height).
:- mode fix_2node_t0(di, di, di, di, uo, out) is det.
:- mode fix_2node_t0(in, in, in, in, out, out) is det.
fix_2node_t0(K0, V0, T0, T1, Tout, RH) :-
(
% Steal T1's leftmost subtree and combine it with T0.
T1 = four(K10, V10, K11, V11, K12, V12, T10, T11, T12, T13),
NewT1 = three(K11, V11, K12, V12, T11, T12, T13),
Node = two(K0, V0, T0, T10),
Tout = two(K10, V10, Node, NewT1),
RH = did_not_reduce_height
;
% Steal T1's leftmost subtree and combine it with T0.
T1 = three(K10, V10, K11, V11, T10, T11, T12),
NewT1 = two(K11, V11, T11, T12),
Node = two(K0, V0, T0, T10),
Tout = two(K10, V10, Node, NewT1),
RH = did_not_reduce_height
;
% Move T0 one level down and combine it with the subtrees of T1
% this reduces the depth of the tree.
T1 = two(K10, V10, T10, T11),
Tout = three(K0, V0, K10, V10, T0, T10, T11),
RH = reduced_height
;
T1 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = two(K0, V0, T0, T1),
% RH = reduced_height
).
:- pred fix_2node_t1(K, V, tree234(K, V), tree234(K, V), tree234(K, V),
maybe_reduced_height).
:- mode fix_2node_t1(di, di, di, di, uo, out) is det.
:- mode fix_2node_t1(in, in, in, in, out, out) is det.
fix_2node_t1(K0, V0, T0, T1, Tout, RH) :-
(
% Steal T0's leftmost subtree and combine it with T1.
T0 = four(K00, V00, K01, V01, K02, V02, T00, T01, T02, T03),
NewT0 = three(K00, V00, K01, V01, T00, T01, T02),
Node = two(K0, V0, T03, T1),
Tout = two(K02, V02, NewT0, Node),
RH = did_not_reduce_height
;
% Steal T0's leftmost subtree and combine it with T1.
T0 = three(K00, V00, K01, V01, T00, T01, T02),
NewT0 = two(K00, V00, T00, T01),
Node = two(K0, V0, T02, T1),
Tout = two(K01, V01, NewT0, Node),
RH = did_not_reduce_height
;
% Move T1 one level down and combine it with the subtrees of T0
% this reduces the depth of the tree.
T0 = two(K00, V00, T00, T01),
Tout = three(K00, V00, K0, V0, T00, T01, T1),
RH = reduced_height
;
T0 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = two(K0, V0, T0, T1),
% RH = reduced_height
).
:- pred fix_3node_t0(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
tree234(K, V), maybe_reduced_height).
:- mode fix_3node_t0(di, di, di, di, di, di, di, uo, out) is det.
:- mode fix_3node_t0(in, in, in, in, in, in, in, out, out) is det.
fix_3node_t0(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :-
(
% Steal T1's leftmost subtree and combine it with T0.
T1 = four(K10, V10, K11, V11, K12, V12, T10, T11, T12, T13),
NewT1 = three(K11, V11, K12, V12, T11, T12, T13),
Node = two(K0, V0, T0, T10),
Tout = three(K10, V10, K1, V1, Node, NewT1, T2),
RH = did_not_reduce_height
;
% Steal T1's leftmost subtree and combine it with T0.
T1 = three(K10, V10, K11, V11, T10, T11, T12),
NewT1 = two(K11, V11, T11, T12),
Node = two(K0, V0, T0, T10),
Tout = three(K10, V10, K1, V1, Node, NewT1, T2),
RH = did_not_reduce_height
;
% Move T0 one level down to become the leftmost subtree of T1.
T1 = two(K10, V10, T10, T11),
NewT1 = three(K0, V0, K10, V10, T0, T10, T11),
Tout = two(K1, V1, NewT1, T2),
RH = did_not_reduce_height
;
T1 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = three(K0, V0, K1, V1, T0, T1, T2),
% The heights of T1 and T2 are unchanged
% RH = did_not_reduce_height
).
:- pred fix_3node_t1(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
tree234(K, V), maybe_reduced_height).
%:- mode fix_3node_t1(di, di, di, di, di, di, di, uo, out) is det.
:- mode fix_3node_t1(in, in, in, in, in, in, in, out, out) is det.
fix_3node_t1(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :-
(
% Steal T0's rightmost subtree and combine it with T1.
T0 = four(K00, V00, K01, V01, K02, V02, T00, T01, T02, T03),
NewT0 = three(K00, V00, K01, V01, T00, T01, T02),
Node = two(K0, V0, T03, T1),
Tout = three(K02, V02, K1, V1, NewT0, Node, T2),
RH = did_not_reduce_height
;
% Steal T0's rightmost subtree and combine it with T1.
T0 = three(K00, V00, K01, V01, T00, T01, T02),
NewT0 = two(K00, V00, T00, T01),
Node = two(K0, V0, T02, T1),
Tout = three(K01, V01, K1, V1, NewT0, Node, T2),
RH = did_not_reduce_height
;
% Move T1 one level down to become the rightmost subtree of T0.
T0 = two(K00, V00, T00, T01),
NewT0 = three(K00, V00, K0, V0, T00, T01, T1),
Tout = two(K1, V1, NewT0, T2),
RH = did_not_reduce_height
;
T0 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = three(K0, V0, K1, V1, T0, T1, T2),
% The heights of T0 and T2 are unchanged
% RH = did_not_reduce_height
).
:- pred fix_3node_t2(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
tree234(K, V), maybe_reduced_height).
%:- mode fix_3node_t2(di, di, di, di, di, di, di, uo, out) is det.
:- mode fix_3node_t2(in, in, in, in, in, in, in, out, out) is det.
fix_3node_t2(K0, V0, K1, V1, T0, T1, T2, Tout, RH) :-
(
% Steal T1's rightmost subtree and combine it with T2.
T1 = four(K10, V10, K11, V11, K12, V12, T10, T11, T12, T13),
NewT1 = three(K10, V10, K11, V11, T10, T11, T12),
Node = two(K1, V1, T13, T2),
Tout = three(K0, V0, K12, V12, T0, NewT1, Node),
RH = did_not_reduce_height
;
% Steal T1's rightmost subtree and combine it with T2.
T1 = three(K10, V10, K11, V11, T10, T11, T12),
NewT1 = two(K10, V10, T10, T11),
Node = two(K1, V1, T12, T2),
Tout = three(K0, V0, K11, V11, T0, NewT1, Node),
RH = did_not_reduce_height
;
% Move T2 one level down to become the rightmost subtree of T1.
T1 = two(K10, V10, T10, T11),
NewT1 = three(K10, V10, K1, V1, T10, T11, T2),
Tout = two(K0, V0, T0, NewT1),
RH = did_not_reduce_height
;
T1 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = three(K0, V0, K1, V1, T0, T1, T2),
% The heights of T0 and T1 are unchanged
% RH = did_not_reduce_height
).
:- pred fix_4node_t0(K, V, K, V, K, V,
tree234(K, V), tree234(K, V), tree234(K, V), tree234(K, V),
tree234(K, V), maybe_reduced_height).
%:- mode fix_4node_t0(di, di, di, di, di, di, di, di, di, di, uo, out) is det.
:- mode fix_4node_t0(in, in, in, in, in, in, in, in, in, in, out, out) is det.
fix_4node_t0(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :-
(
% Steal T1's leftmost subtree and combine it with T0.
T1 = four(K10, V10, K11, V11, K12, V12, T10, T11, T12, T13),
NewT1 = three(K11, V11, K12, V12, T11, T12, T13),
Node = two(K0, V0, T0, T10),
Tout = four(K10, V10, K1, V1, K2, V2, Node, NewT1, T2, T3),
RH = did_not_reduce_height
;
% Steal T1's leftmost subtree and combine it with T0.
T1 = three(K10, V10, K11, V11, T10, T11, T12),
NewT1 = two(K11, V11, T11, T12),
Node = two(K0, V0, T0, T10),
Tout = four(K10, V10, K1, V1, K2, V2, Node, NewT1, T2, T3),
RH = did_not_reduce_height
;
% Move T0 one level down to become the leftmost subtree of T1.
T1 = two(K10, V10, T10, T11),
NewT1 = three(K0, V0, K10, V10, T0, T10, T11),
Tout = three(K1, V1, K2, V2, NewT1, T2, T3),
RH = did_not_reduce_height
;
T1 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
% The heights of T1, T2 and T3 are unchanged
% RH = did_not_reduce_height
).
:- pred fix_4node_t1(K, V, K, V, K, V,
tree234(K, V), tree234(K, V), tree234(K, V), tree234(K, V),
tree234(K, V), maybe_reduced_height).
%:- mode fix_4node_t1(di, di, di, di, di, di, di, di, di, di, uo, out) is det.
:- mode fix_4node_t1(in, in, in, in, in, in, in, in, in, in, out, out) is det.
fix_4node_t1(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :-
(
% Steal T2's leftmost subtree and combine it with T1.
T2 = four(K20, V20, K21, V21, K22, V22, T20, T21, T22, T23),
NewT2 = three(K21, V21, K22, V22, T21, T22, T23),
Node = two(K1, V1, T1, T20),
Tout = four(K0, V0, K20, V20, K2, V2, T0, Node, NewT2, T3),
RH = did_not_reduce_height
;
% Steal T2's leftmost subtree and combine it with T1.
T2 = three(K20, V20, K21, V21, T20, T21, T22),
NewT2 = two(K21, V21, T21, T22),
Node = two(K1, V1, T1, T20),
Tout = four(K0, V0, K20, V20, K2, V2, T0, Node, NewT2, T3),
RH = did_not_reduce_height
;
% Move T1 one level down to become the leftmost subtree of T2.
T2 = two(K20, V20, T20, T21),
NewT2 = three(K1, V1, K20, V20, T1, T20, T21),
Tout = three(K0, V0, K2, V2, T0, NewT2, T3),
RH = did_not_reduce_height
;
T2 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
% The heights of T0, T2 and T3 are unchanged
% RH = did_not_reduce_height
).
:- pred fix_4node_t2(K, V, K, V, K, V,
tree234(K, V), tree234(K, V), tree234(K, V), tree234(K, V),
tree234(K, V), maybe_reduced_height).
%:- mode fix_4node_t2(di, di, di, di, di, di, di, di, di, di, uo, out) is det.
:- mode fix_4node_t2(in, in, in, in, in, in, in, in, in, in, out, out) is det.
fix_4node_t2(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :-
(
% Steal T3's leftmost subtree and combine it with T2.
T3 = four(K30, V30, K31, V31, K32, V32, T30, T31, T32, T33),
NewT3 = three(K31, V31, K32, V32, T31, T32, T33),
Node = two(K2, V2, T2, T30),
Tout = four(K0, V0, K1, V1, K30, V30, T0, T1, Node, NewT3),
RH = did_not_reduce_height
;
% Steal T3's leftmost subtree and combine it with T2.
T3 = three(K30, V30, K31, V31, T30, T31, T32),
NewT3 = two(K31, V31, T31, T32),
Node = two(K2, V2, T2, T30),
Tout = four(K0, V0, K1, V1, K30, V30, T0, T1, Node, NewT3),
RH = did_not_reduce_height
;
% Move T2 one level down to become the leftmost subtree of T3.
T3 = two(K30, V30, T30, T31),
NewT3 = three(K2, V2, K30, V30, T2, T30, T31),
Tout = three(K0, V0, K1, V1, T0, T1, NewT3),
RH = did_not_reduce_height
;
T3 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
% The heights of T0, T1 and T3 are unchanged
% RH = did_not_reduce_height
).
:- pred fix_4node_t3(K, V, K, V, K, V,
tree234(K, V), tree234(K, V), tree234(K, V), tree234(K, V),
tree234(K, V), maybe_reduced_height).
%:- mode fix_4node_t3(di, di, di, di, di, di, di, di, di, di, uo, out) is det.
:- mode fix_4node_t3(in, in, in, in, in, in, in, in, in, in, out, out) is det.
fix_4node_t3(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3, Tout, RH) :-
(
% Steal T2's rightmost subtree and combine it with T3.
T2 = four(K20, V20, K21, V21, K22, V22, T20, T21, T22, T23),
NewT2 = three(K20, V20, K21, V21, T20, T21, T22),
Node = two(K2, V2, T23, T3),
Tout = four(K0, V0, K1, V1, K22, V22, T0, T1, NewT2, Node),
RH = did_not_reduce_height
;
% Steal T2's rightmost subtree and combine it with T3.
T2 = three(K20, V20, K21, V21, T20, T21, T22),
NewT2 = two(K20, V20, T20, T21),
Node = two(K2, V2, T22, T3),
Tout = four(K0, V0, K1, V1, K21, V21, T0, T1, NewT2, Node),
RH = did_not_reduce_height
;
% Move T3 one level down to become the rightmost subtree of T2.
T2 = two(K20, V20, T20, T21),
NewT2 = three(K20, V20, K2, V2, T20, T21, T3),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2),
RH = did_not_reduce_height
;
T2 = empty,
unexpected($pred, "unbalanced 234 tree")
% Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
% The heights of T0, T1 and T2 are unchanged
% RH = did_not_reduce_height
).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
keys(T) = Ks :-
tree234.keys(T, Ks).
keys(Tree, Keys) :-
tree234.keys_acc(Tree, [], Keys).
:- pred keys_acc(tree234(K, V)::in, list(K)::in, list(K)::out) is det.
keys_acc(empty, List, List).
keys_acc(two(K0, _V0, T0, T1), L0, L) :-
tree234.keys_acc(T1, L0, L1),
tree234.keys_acc(T0, [K0 | L1], L).
keys_acc(three(K0, _V0, K1, _V1, T0, T1, T2), L0, L) :-
tree234.keys_acc(T2, L0, L1),
tree234.keys_acc(T1, [K1 | L1], L2),
tree234.keys_acc(T0, [K0 | L2], L).
keys_acc(four(K0, _V0, K1, _V1, K2, _V2, T0, T1, T2, T3), L0, L) :-
tree234.keys_acc(T3, L0, L1),
tree234.keys_acc(T2, [K2 | L1], L2),
tree234.keys_acc(T1, [K1 | L2], L3),
tree234.keys_acc(T0, [K0 | L3], L).
%---------------------------------------------------------------------------%
values(T) = Vs :-
tree234.values(T, Vs).
values(Tree, Values) :-
tree234.values_acc(Tree, [], Values).
:- pred values_acc(tree234(K, V)::in, list(V)::in, list(V)::out) is det.
values_acc(empty, List, List).
values_acc(two(_K0, V0, T0, T1), L0, L) :-
tree234.values_acc(T1, L0, L1),
tree234.values_acc(T0, [V0 | L1], L).
values_acc(three(_K0, V0, _K1, V1, T0, T1, T2), L0, L) :-
tree234.values_acc(T2, L0, L1),
tree234.values_acc(T1, [V1 | L1], L2),
tree234.values_acc(T0, [V0 | L2], L).
values_acc(four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3), L0, L) :-
tree234.values_acc(T3, L0, L1),
tree234.values_acc(T2, [V2 | L1], L2),
tree234.values_acc(T1, [V1 | L2], L3),
tree234.values_acc(T0, [V0 | L3], L).
%---------------------------------------------------------------------------%
keys_and_values(Tree, Keys, Values) :-
tree234.keys_and_values_acc(Tree, [], Keys, [], Values).
:- pred keys_and_values_acc(tree234(K, V)::in,
list(K)::in, list(K)::out, list(V)::in, list(V)::out) is det.
keys_and_values_acc(empty, !Keys, !Values).
keys_and_values_acc(two(K0, V0, T0, T1), !Keys, !Values) :-
tree234.keys_and_values_acc(T1, !Keys, !Values),
!:Keys = [K0 | !.Keys],
!:Values = [V0 | !.Values],
tree234.keys_and_values_acc(T0, !Keys, !Values).
keys_and_values_acc(three(K0, V0, K1, V1, T0, T1, T2),
!Keys, !Values) :-
tree234.keys_and_values_acc(T2, !Keys, !Values),
!:Keys = [K1 | !.Keys],
!:Values = [V1 | !.Values],
tree234.keys_and_values_acc(T1, !Keys, !Values),
!:Keys = [K0 | !.Keys],
!:Values = [V0 | !.Values],
tree234.keys_and_values_acc(T0, !Keys, !Values).
keys_and_values_acc(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!Keys, !Values) :-
tree234.keys_and_values_acc(T3, !Keys, !Values),
!:Keys = [K2 | !.Keys],
!:Values = [V2 | !.Values],
tree234.keys_and_values_acc(T2, !Keys, !Values),
!:Keys = [K1 | !.Keys],
!:Values = [V1 | !.Values],
tree234.keys_and_values_acc(T1, !Keys, !Values),
!:Keys = [K0 | !.Keys],
!:Values = [V0 | !.Values],
tree234.keys_and_values_acc(T0, !Keys, !Values).
%---------------------------------------------------------------------------%
sorted_keys_match(Tree, List) :-
sorted_keys_match_in_tree(Tree, List, LeftOver),
LeftOver = [].
:- pred sorted_keys_match_in_tree(tree234(K, V)::in,
list(K)::in, list(K)::out) is semidet.
sorted_keys_match_in_tree(empty, L, L).
sorted_keys_match_in_tree(two(K0, _V0, T0, T1), L0, L) :-
sorted_keys_match_in_tree(T0, L0, L1),
L1 = [K0 | L2],
sorted_keys_match_in_tree(T1, L2, L).
sorted_keys_match_in_tree(three(K0, _V0, K1, _V1, T0, T1, T2), L0, L) :-
sorted_keys_match_in_tree(T0, L0, L1),
L1 = [K0 | L2],
sorted_keys_match_in_tree(T1, L2, L3),
L3 = [K1 | L4],
sorted_keys_match_in_tree(T2, L4, L).
sorted_keys_match_in_tree(four(K0, _V0, K1, _V1, K2, _V2, T0, T1, T2, T3),
L0, L) :-
sorted_keys_match_in_tree(T0, L0, L1),
L1 = [K0 | L2],
sorted_keys_match_in_tree(T1, L2, L3),
L3 = [K1 | L4],
sorted_keys_match_in_tree(T2, L4, L5),
L5 = [K2 | L6],
sorted_keys_match_in_tree(T3, L6, L).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
count(T) = uint.cast_to_int(N) :-
ucount_acc(T, 0u, N).
count(T, uint.cast_to_int(N)) :-
ucount_acc(T, 0u, N).
ucount(T) = N :-
ucount_acc(T, 0u, N).
ucount(T, N) :-
ucount_acc(T, 0u, N).
:- pred ucount_acc(tree234(K, V)::in, uint::in, uint::out) is det.
ucount_acc(T, !N) :-
(
T = empty
;
T = two(_, _, T0, T1),
!:N = !.N + 1u,
ucount_acc(T0, !N),
ucount_acc(T1, !N)
;
T = three(_, _, _, _, T0, T1, T2),
!:N = !.N + 2u,
ucount_acc(T0, !N),
ucount_acc(T1, !N),
ucount_acc(T2, !N)
;
T = four(_, _, _, _, _, _, T0, T1, T2, T3),
!:N = !.N + 3u,
ucount_acc(T0, !N),
ucount_acc(T1, !N),
ucount_acc(T2, !N),
ucount_acc(T3, !N)
).
%---------------------------------------------------------------------------%
tree234_to_assoc_list(T) = AL :-
tree234.tree234_to_assoc_list(T, AL).
tree234_to_assoc_list(Tree, AssocList) :-
tree234.tree234_to_assoc_list_acc(Tree, [], AssocList).
:- pred tree234_to_assoc_list_acc(tree234(K, V)::in,
assoc_list(K, V)::in, assoc_list(K, V)::out) is det.
tree234_to_assoc_list_acc(empty, L, L).
tree234_to_assoc_list_acc(two(K0, V0, T0, T1), L0, L) :-
tree234.tree234_to_assoc_list_acc(T1, L0, L1),
tree234.tree234_to_assoc_list_acc(T0, [K0 - V0 | L1], L).
tree234_to_assoc_list_acc(three(K0, V0, K1, V1, T0, T1, T2), L0, L) :-
tree234.tree234_to_assoc_list_acc(T2, L0, L1),
tree234.tree234_to_assoc_list_acc(T1, [K1 - V1 | L1], L2),
tree234.tree234_to_assoc_list_acc(T0, [K0 - V0 | L2], L).
tree234_to_assoc_list_acc(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
L0, L) :-
tree234.tree234_to_assoc_list_acc(T3, L0, L1),
tree234.tree234_to_assoc_list_acc(T2, [K2 - V2 | L1], L2),
tree234.tree234_to_assoc_list_acc(T1, [K1 - V1 | L2], L3),
tree234.tree234_to_assoc_list_acc(T0, [K0 - V0 | L3], L).
%---------------------------------------------------------------------------%
assoc_list_to_tree234(AL) = T :-
tree234.assoc_list_to_tree234(AL, T).
assoc_list_to_tree234(AssocList, Tree) :-
tree234.assoc_list_to_tree234_acc(AssocList, empty, Tree).
:- pred assoc_list_to_tree234_acc(assoc_list(K, V)::in,
tree234(K, V)::in, tree234(K, V)::out) is det.
assoc_list_to_tree234_acc([], Tree, Tree).
assoc_list_to_tree234_acc([K - V | Rest], !Tree) :-
tree234.set(K, V, !Tree),
tree234.assoc_list_to_tree234_acc(Rest, !Tree).
%---------------------------------------------------------------------------%
from_sorted_assoc_list(List, Tree) :-
list.length(List, Len),
( if Len = 0 then
% We can handle the Len = 0 case here just once, or we can handle it
% lots of times in do_from_sorted_assoc_list. The former is more
% efficient.
Tree = empty
else
find_num_234_levels(Len, Level, AllThrees),
do_from_sorted_assoc_list(Len, List, LeftOver, Level, AllThrees, Tree),
trace [compiletime(flag("tree234_sanity_checks"))] (
expect(unify(LeftOver, []), $pred, "leftovers")
)
).
:- pred do_from_sorted_assoc_list(int::in,
assoc_list(K, V)::in, assoc_list(K, V)::out,
int::in, int::in, tree234(K, V)::out) is det.
do_from_sorted_assoc_list(Len, !List, Level0, AllThrees0, Tree) :-
( if Level0 = 1 then
( if Len = 1 then
(
!.List = [K1 - V1 | !:List],
Tree = two(K1, V1, empty, empty)
;
!.List = [],
unexpected($pred, "len 1 nil")
)
else if Len = 2 then
trace [compiletime(flag("tree234_sanity_checks"))] (
expect(unify(Level0, 1), $pred, "Len = 2 but Level != 1")
),
(
!.List = [K1 - V1, K2 - V2 | !:List],
Tree = three(K1, V1, K2, V2, empty, empty, empty)
;
!.List = [_],
unexpected($pred, "len 2 one")
;
!.List = [],
unexpected($pred, "len 2 nil")
)
else
unexpected($pred, "level 1, but len not 1 or 2")
)
else
Level = Level0 - 1,
AllThrees = (AllThrees0 - 2) / 3,
( if Len > 2 * AllThrees then
BaseSubLen = (Len / 3),
Diff = Len - (BaseSubLen * 3),
( if Diff = 0 then
% Len = BaseSubLen * 3:
% (BaseSubLen) + 1 + (BaseSubLen - 1) + 1 + (BaseSubLen - 1)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen - 1,
SubLen3 = BaseSubLen - 1
else if Diff = 1 then
% Len = BaseSubLen * 3 + 1:
% (BaseSubLen) + 1 + (BaseSubLen) + 1 + (BaseSubLen - 1)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen,
SubLen3 = BaseSubLen - 1
else
trace [compiletime(flag("tree234_sanity_checks"))] (
expect(unify(Diff, 2), $pred, "Diff != 2")
),
% Len = BaseSubLen * 3 + 2:
% (BaseSubLen) + 1 + (BaseSubLen) + 1 + (BaseSubLen)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen,
SubLen3 = BaseSubLen
),
trace [io(!IO), compile_time(flag("from_sorted_assoc_list"))] (
io.output_stream(SplitStream, !IO),
io.format(SplitStream,
"splitting %d into three: %d, %d, %d\n",
[i(Len), i(SubLen1), i(SubLen2), i(SubLen3)], !IO)
),
do_from_sorted_assoc_list(SubLen1, !List, Level, AllThrees,
SubTree1),
(
!.List = [K1 - V1 | !:List]
;
!.List = [],
unexpected($pred, "tree K1 V1 nil")
),
do_from_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
SubTree2),
(
!.List = [K2 - V2 | !:List]
;
!.List = [],
unexpected($pred, "tree K2 V2 nil")
),
do_from_sorted_assoc_list(SubLen3, !List, Level, AllThrees,
SubTree3),
Tree = three(K1, V1, K2, V2, SubTree1, SubTree2, SubTree3),
trace [io(!IO), compile_time(flag("from_sorted_assoc_list"))] (
io.output_stream(TreeStream, !IO),
io.format(TreeStream, "tree for %d\n", [i(Len)], !IO),
io.write(TreeStream, Tree, !IO),
io.nl(TreeStream, !IO)
)
else
BaseSubLen = (Len) / 2,
Diff = Len - (BaseSubLen * 2),
( if Diff = 0 then
% Len = BaseSubLen * 2:
% (BaseSubLen) + 1 + (BaseSubLen - 1)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen - 1
else
trace [compiletime(flag("tree234_sanity_checks"))] (
expect(unify(Diff, 1), $pred, "Diff != 1")
),
% Len = BaseSubLen * 2 + 1:
% (BaseSubLen) + 1 + (BaseSubLen)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen
),
trace [io(!IO), compile_time(flag("from_sorted_assoc_list"))] (
io.output_stream(SplitStream, !IO),
io.format(SplitStream,
"splitting %d into two: %d, %d\n",
[i(Len), i(SubLen1), i(SubLen2)], !IO)
),
do_from_sorted_assoc_list(SubLen1, !List, Level, AllThrees,
SubTree1),
(
!.List = [K1 - V1 | !:List]
;
!.List = [],
unexpected($pred, "two K1 V1 nil")
),
do_from_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
SubTree2),
Tree = two(K1, V1, SubTree1, SubTree2),
trace [io(!IO), compile_time(flag("from_sorted_assoc_list"))] (
io.output_stream(TreeStream, !IO),
io.format(TreeStream, "tree for %d\n", [i(Len)], !IO),
io.write(TreeStream, Tree, !IO),
io.nl(TreeStream, !IO)
)
)
).
from_rev_sorted_assoc_list(List, Tree) :-
list.length(List, Len),
( if Len = 0 then
% We can handle the Len = 0 case here just once, or we can handle it
% lots of times in do_from_rev_sorted_assoc_list. The former is more
% efficient.
Tree = empty
else
find_num_234_levels(Len, Level, AllThrees),
do_from_rev_sorted_assoc_list(Len, List, LeftOver, Level, AllThrees,
Tree),
trace [compiletime(flag("tree234_sanity_checks"))] (
expect(unify(LeftOver, []), $pred, "leftovers")
)
).
:- pred do_from_rev_sorted_assoc_list(int::in,
assoc_list(K, V)::in, assoc_list(K, V)::out,
int::in, int::in, tree234(K, V)::out) is det.
do_from_rev_sorted_assoc_list(Len, !List, Level0, AllThrees0, Tree) :-
( if Level0 = 1 then
( if Len = 1 then
(
!.List = [K1 - V1 | !:List],
Tree = two(K1, V1, empty, empty)
;
!.List = [],
unexpected($pred, "len 1 nil")
)
else if Len = 2 then
trace [compiletime(flag("tree234_sanity_checks"))] (
expect(unify(Level0, 1), $pred, "Len = 2 but Level != 1")
),
(
!.List = [K2 - V2, K1 - V1 | !:List],
Tree = three(K1, V1, K2, V2, empty, empty, empty)
;
!.List = [_],
unexpected($pred, "len 2 one")
;
!.List = [],
unexpected($pred, "len 2 nil")
)
else
unexpected($pred, "level 1, but len not 1 or 2")
)
else
Level = Level0 - 1,
AllThrees = (AllThrees0 - 2) / 3,
( if Len > 2 * AllThrees then
BaseSubLen = (Len / 3),
Diff = Len - (BaseSubLen * 3),
( if Diff = 0 then
% Len = BaseSubLen * 3:
% (BaseSubLen) + 1 + (BaseSubLen - 1) + 1 + (BaseSubLen - 1)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen - 1,
SubLen3 = BaseSubLen - 1
else if Diff = 1 then
% Len = BaseSubLen * 3 + 1:
% (BaseSubLen) + 1 + (BaseSubLen) + 1 + (BaseSubLen - 1)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen,
SubLen3 = BaseSubLen - 1
else
trace [compiletime(flag("tree234_sanity_checks"))] (
expect(unify(Diff, 2), $pred, "Diff != 2")
),
% Len = BaseSubLen * 3 + 2:
% (BaseSubLen) + 1 + (BaseSubLen) + 1 + (BaseSubLen)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen,
SubLen3 = BaseSubLen
),
trace [io(!IO), compile_time(flag("from_rev_sorted_assoc_list"))] (
io.output_stream(SplitStream, !IO),
io.format(SplitStream,
"splitting %d into three: %d, %d, %d\n",
[i(Len), i(SubLen1), i(SubLen2), i(SubLen3)], !IO)
),
do_from_rev_sorted_assoc_list(SubLen3, !List, Level, AllThrees,
SubTree3),
(
!.List = [K2 - V2 | !:List]
;
!.List = [],
unexpected($pred, "tree K2 V2 nil")
),
do_from_rev_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
SubTree2),
(
!.List = [K1 - V1 | !:List]
;
!.List = [],
unexpected($pred, "tree K1 V1 nil")
),
do_from_rev_sorted_assoc_list(SubLen1, !List, Level, AllThrees,
SubTree1),
Tree = three(K1, V1, K2, V2, SubTree1, SubTree2, SubTree3),
trace [io(!IO), compile_time(flag("from_rev_sorted_assoc_list"))] (
io.output_stream(TreeStream, !IO),
io.format(TreeStream, "tree for %d\n", [i(Len)], !IO),
io.write(TreeStream, Tree, !IO),
io.nl(TreeStream, !IO)
)
else
BaseSubLen = (Len) / 2,
Diff = Len - (BaseSubLen * 2),
( if Diff = 0 then
% Len = BaseSubLen * 2:
% (BaseSubLen) + 1 + (BaseSubLen - 1)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen - 1
else
trace [compiletime(flag("tree234_sanity_checks"))] (
expect(unify(Diff, 1), $pred, "Diff != 1")
),
% Len = BaseSubLen * 2 + 1:
% (BaseSubLen) + 1 + (BaseSubLen)
SubLen1 = BaseSubLen,
SubLen2 = BaseSubLen
),
trace [io(!IO), compile_time(flag("from_rev_sorted_assoc_list"))] (
io.output_stream(SplitStream, !IO),
io.format(SplitStream,
"splitting %d into two: %d, %d\n",
[i(Len), i(SubLen1), i(SubLen2)], !IO)
),
do_from_rev_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
SubTree2),
(
!.List = [K1 - V1 | !:List]
;
!.List = [],
unexpected($pred, "two K1 V1 nil")
),
do_from_rev_sorted_assoc_list(SubLen1, !List, Level, AllThrees,
SubTree1),
Tree = two(K1, V1, SubTree1, SubTree2),
trace [io(!IO), compile_time(flag("from_rev_sorted_assoc_list"))] (
io.output_stream(TreeStream, !IO),
io.format(TreeStream, "tree for %d\n", [i(Len)], !IO),
io.write(TreeStream, Tree, !IO),
io.nl(TreeStream, !IO)
)
)
).
:- pred find_num_234_levels(int::in, int::out, int::out) is det.
find_num_234_levels(Len, Level, AllThrees) :-
find_num_234_levels_loop(Len, 0, Level, 0, AllThrees).
:- pred find_num_234_levels_loop(int::in,
int::in, int::out, int::in, int::out) is det.
find_num_234_levels_loop(Len, Level0, Level, !AllThrees) :-
( if Len =< !.AllThrees then
Level = Level0
else
Level1 = Level0 + 1,
!:AllThrees = !.AllThrees * 3 + 2,
find_num_234_levels_loop(Len, Level1, Level, !AllThrees)
).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
foldl(F, T, A) = B :-
P = (pred(W::in, X::in, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
tree234.foldl(P, T, A, B).
foldl(_Pred, empty, !A).
foldl(Pred, two(K, V, T0, T1), !A) :-
tree234.foldl(Pred, T0, !A),
Pred(K, V, !A),
tree234.foldl(Pred, T1, !A).
foldl(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A) :-
tree234.foldl(Pred, T0, !A),
Pred(K0, V0, !A),
tree234.foldl(Pred, T1, !A),
Pred(K1, V1, !A),
tree234.foldl(Pred, T2, !A).
foldl(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), !A) :-
tree234.foldl(Pred, T0, !A),
Pred(K0, V0, !A),
tree234.foldl(Pred, T1, !A),
Pred(K1, V1, !A),
tree234.foldl(Pred, T2, !A),
Pred(K2, V2, !A),
tree234.foldl(Pred, T3, !A).
foldl2(_Pred, empty, !A, !B).
foldl2(Pred, two(K, V, T0, T1), !A, !B) :-
tree234.foldl2(Pred, T0, !A, !B),
Pred(K, V, !A, !B),
tree234.foldl2(Pred, T1, !A, !B).
foldl2(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B) :-
tree234.foldl2(Pred, T0, !A, !B),
Pred(K0, V0, !A, !B),
tree234.foldl2(Pred, T1, !A, !B),
Pred(K1, V1, !A, !B),
tree234.foldl2(Pred, T2, !A, !B).
foldl2(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), !A, !B) :-
tree234.foldl2(Pred, T0, !A, !B),
Pred(K0, V0, !A, !B),
tree234.foldl2(Pred, T1, !A, !B),
Pred(K1, V1, !A, !B),
tree234.foldl2(Pred, T2, !A, !B),
Pred(K2, V2, !A, !B),
tree234.foldl2(Pred, T3, !A, !B).
foldl3(_Pred, empty, !A, !B, !C).
foldl3(Pred, two(K, V, T0, T1), !A, !B, !C) :-
tree234.foldl3(Pred, T0, !A, !B, !C),
Pred(K, V, !A, !B, !C),
tree234.foldl3(Pred, T1, !A, !B, !C).
foldl3(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C) :-
tree234.foldl3(Pred, T0, !A, !B, !C),
Pred(K0, V0, !A, !B, !C),
tree234.foldl3(Pred, T1, !A, !B, !C),
Pred(K1, V1, !A, !B, !C),
tree234.foldl3(Pred, T2, !A, !B, !C).
foldl3(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!A, !B, !C) :-
tree234.foldl3(Pred, T0, !A, !B, !C),
Pred(K0, V0, !A, !B, !C),
tree234.foldl3(Pred, T1, !A, !B, !C),
Pred(K1, V1, !A, !B, !C),
tree234.foldl3(Pred, T2, !A, !B, !C),
Pred(K2, V2, !A, !B, !C),
tree234.foldl3(Pred, T3, !A, !B, !C).
foldl4(_Pred, empty, !A, !B, !C, !D).
foldl4(Pred, two(K, V, T0, T1), !A, !B, !C, !D) :-
tree234.foldl4(Pred, T0, !A, !B, !C, !D),
Pred(K, V, !A, !B, !C, !D),
tree234.foldl4(Pred, T1, !A, !B, !C, !D).
foldl4(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C, !D) :-
tree234.foldl4(Pred, T0, !A, !B, !C, !D),
Pred(K0, V0, !A, !B, !C, !D),
tree234.foldl4(Pred, T1, !A, !B, !C, !D),
Pred(K1, V1, !A, !B, !C, !D),
tree234.foldl4(Pred, T2, !A, !B, !C, !D).
foldl4(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D) :-
tree234.foldl4(Pred, T0, !A, !B, !C, !D),
Pred(K0, V0, !A, !B, !C, !D),
tree234.foldl4(Pred, T1, !A, !B, !C, !D),
Pred(K1, V1, !A, !B, !C, !D),
tree234.foldl4(Pred, T2, !A, !B, !C, !D),
Pred(K2, V2, !A, !B, !C, !D),
tree234.foldl4(Pred, T3, !A, !B, !C, !D).
foldl5(_Pred, empty, !A, !B, !C, !D, !E).
foldl5(Pred, two(K, V, T0, T1), !A, !B, !C, !D, !E) :-
tree234.foldl5(Pred, T0, !A, !B, !C, !D, !E),
Pred(K, V, !A, !B, !C, !D, !E),
tree234.foldl5(Pred, T1, !A, !B, !C, !D, !E).
foldl5(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C, !D, !E) :-
tree234.foldl5(Pred, T0, !A, !B, !C, !D, !E),
Pred(K0, V0, !A, !B, !C, !D, !E),
tree234.foldl5(Pred, T1, !A, !B, !C, !D, !E),
Pred(K1, V1, !A, !B, !C, !D, !E),
tree234.foldl5(Pred, T2, !A, !B, !C, !D, !E).
foldl5(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D, !E) :-
tree234.foldl5(Pred, T0, !A, !B, !C, !D, !E),
Pred(K0, V0, !A, !B, !C, !D, !E),
tree234.foldl5(Pred, T1, !A, !B, !C, !D, !E),
Pred(K1, V1, !A, !B, !C, !D, !E),
tree234.foldl5(Pred, T2, !A, !B, !C, !D, !E),
Pred(K2, V2, !A, !B, !C, !D, !E),
tree234.foldl5(Pred, T3, !A, !B, !C, !D, !E).
foldl6(_Pred, empty, !A, !B, !C, !D, !E, !F).
foldl6(Pred, two(K, V, T0, T1), !A, !B, !C, !D, !E, !F) :-
tree234.foldl6(Pred, T0, !A, !B, !C, !D, !E, !F),
Pred(K, V, !A, !B, !C, !D, !E, !F),
tree234.foldl6(Pred, T1, !A, !B, !C, !D, !E, !F).
foldl6(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C, !D, !E, !F) :-
tree234.foldl6(Pred, T0, !A, !B, !C, !D, !E, !F),
Pred(K0, V0, !A, !B, !C, !D, !E, !F),
tree234.foldl6(Pred, T1, !A, !B, !C, !D, !E, !F),
Pred(K1, V1, !A, !B, !C, !D, !E, !F),
tree234.foldl6(Pred, T2, !A, !B, !C, !D, !E, !F).
foldl6(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D, !E, !F) :-
tree234.foldl6(Pred, T0, !A, !B, !C, !D, !E, !F),
Pred(K0, V0, !A, !B, !C, !D, !E, !F),
tree234.foldl6(Pred, T1, !A, !B, !C, !D, !E, !F),
Pred(K1, V1, !A, !B, !C, !D, !E, !F),
tree234.foldl6(Pred, T2, !A, !B, !C, !D, !E, !F),
Pred(K2, V2, !A, !B, !C, !D, !E, !F),
tree234.foldl6(Pred, T3, !A, !B, !C, !D, !E, !F).
foldl_values(_Pred, empty, !A).
foldl_values(Pred, two(_K, V, T0, T1), !A) :-
tree234.foldl_values(Pred, T0, !A),
Pred(V, !A),
tree234.foldl_values(Pred, T1, !A).
foldl_values(Pred, three(_K0, V0, _K1, V1, T0, T1, T2), !A) :-
tree234.foldl_values(Pred, T0, !A),
Pred(V0, !A),
tree234.foldl_values(Pred, T1, !A),
Pred(V1, !A),
tree234.foldl_values(Pred, T2, !A).
foldl_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
!A) :-
tree234.foldl_values(Pred, T0, !A),
Pred(V0, !A),
tree234.foldl_values(Pred, T1, !A),
Pred(V1, !A),
tree234.foldl_values(Pred, T2, !A),
Pred(V2, !A),
tree234.foldl_values(Pred, T3, !A).
foldl2_values(_Pred, empty, !A, !B).
foldl2_values(Pred, two(_K, V, T0, T1), !A, !B) :-
tree234.foldl2_values(Pred, T0, !A, !B),
Pred(V, !A, !B),
tree234.foldl2_values(Pred, T1, !A, !B).
foldl2_values(Pred, three(_K0, V0, _K1, V1, T0, T1, T2), !A, !B) :-
tree234.foldl2_values(Pred, T0, !A, !B),
Pred(V0, !A, !B),
tree234.foldl2_values(Pred, T1, !A, !B),
Pred(V1, !A, !B),
tree234.foldl2_values(Pred, T2, !A, !B).
foldl2_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
!A, !B) :-
tree234.foldl2_values(Pred, T0, !A, !B),
Pred(V0, !A, !B),
tree234.foldl2_values(Pred, T1, !A, !B),
Pred(V1, !A, !B),
tree234.foldl2_values(Pred, T2, !A, !B),
Pred(V2, !A, !B),
tree234.foldl2_values(Pred, T3, !A, !B).
foldl3_values(_Pred, empty, !A, !B, !C).
foldl3_values(Pred, two(_K, V, T0, T1), !A, !B, !C) :-
tree234.foldl3_values(Pred, T0, !A, !B, !C),
Pred(V, !A, !B, !C),
tree234.foldl3_values(Pred, T1, !A, !B, !C).
foldl3_values(Pred, three(_K0, V0, _K1, V1, T0, T1, T2), !A, !B, !C) :-
tree234.foldl3_values(Pred, T0, !A, !B, !C),
Pred(V0, !A, !B, !C),
tree234.foldl3_values(Pred, T1, !A, !B, !C),
Pred(V1, !A, !B, !C),
tree234.foldl3_values(Pred, T2, !A, !B, !C).
foldl3_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
!A, !B, !C) :-
tree234.foldl3_values(Pred, T0, !A, !B, !C),
Pred(V0, !A, !B, !C),
tree234.foldl3_values(Pred, T1, !A, !B, !C),
Pred(V1, !A, !B, !C),
tree234.foldl3_values(Pred, T2, !A, !B, !C),
Pred(V2, !A, !B, !C),
tree234.foldl3_values(Pred, T3, !A, !B, !C).
foldl4_values(_Pred, empty, !A, !B, !C, !D).
foldl4_values(Pred, two(_K, V, T0, T1), !A, !B, !C, !D) :-
tree234.foldl4_values(Pred, T0, !A, !B, !C, !D),
Pred(V, !A, !B, !C, !D),
tree234.foldl4_values(Pred, T1, !A, !B, !C, !D).
foldl4_values(Pred, three(_K0, V0, _K1, V1, T0, T1, T2), !A, !B, !C, !D) :-
tree234.foldl4_values(Pred, T0, !A, !B, !C, !D),
Pred(V0, !A, !B, !C, !D),
tree234.foldl4_values(Pred, T1, !A, !B, !C, !D),
Pred(V1, !A, !B, !C, !D),
tree234.foldl4_values(Pred, T2, !A, !B, !C, !D).
foldl4_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D) :-
tree234.foldl4_values(Pred, T0, !A, !B, !C, !D),
Pred(V0, !A, !B, !C, !D),
tree234.foldl4_values(Pred, T1, !A, !B, !C, !D),
Pred(V1, !A, !B, !C, !D),
tree234.foldl4_values(Pred, T2, !A, !B, !C, !D),
Pred(V2, !A, !B, !C, !D),
tree234.foldl4_values(Pred, T3, !A, !B, !C, !D).
foldl5_values(_Pred, empty, !A, !B, !C, !D, !E).
foldl5_values(Pred, two(_K, V, T0, T1), !A, !B, !C, !D, !E) :-
tree234.foldl5_values(Pred, T0, !A, !B, !C, !D, !E),
Pred(V, !A, !B, !C, !D, !E),
tree234.foldl5_values(Pred, T1, !A, !B, !C, !D, !E).
foldl5_values(Pred, three(_K0, V0, _K1, V1, T0, T1, T2), !A, !B, !C, !D, !E) :-
tree234.foldl5_values(Pred, T0, !A, !B, !C, !D, !E),
Pred(V0, !A, !B, !C, !D, !E),
tree234.foldl5_values(Pred, T1, !A, !B, !C, !D, !E),
Pred(V1, !A, !B, !C, !D, !E),
tree234.foldl5_values(Pred, T2, !A, !B, !C, !D, !E).
foldl5_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D, !E) :-
tree234.foldl5_values(Pred, T0, !A, !B, !C, !D, !E),
Pred(V0, !A, !B, !C, !D, !E),
tree234.foldl5_values(Pred, T1, !A, !B, !C, !D, !E),
Pred(V1, !A, !B, !C, !D, !E),
tree234.foldl5_values(Pred, T2, !A, !B, !C, !D, !E),
Pred(V2, !A, !B, !C, !D, !E),
tree234.foldl5_values(Pred, T3, !A, !B, !C, !D, !E).
foldl6_values(_Pred, empty, !A, !B, !C, !D, !E, !F).
foldl6_values(Pred, two(_K, V, T0, T1), !A, !B, !C, !D, !E, !F) :-
tree234.foldl6_values(Pred, T0, !A, !B, !C, !D, !E, !F),
Pred(V, !A, !B, !C, !D, !E, !F),
tree234.foldl6_values(Pred, T1, !A, !B, !C, !D, !E, !F).
foldl6_values(Pred, three(_K0, V0, _K1, V1, T0, T1, T2),
!A, !B, !C, !D, !E, !F) :-
tree234.foldl6_values(Pred, T0, !A, !B, !C, !D, !E, !F),
Pred(V0, !A, !B, !C, !D, !E, !F),
tree234.foldl6_values(Pred, T1, !A, !B, !C, !D, !E, !F),
Pred(V1, !A, !B, !C, !D, !E, !F),
tree234.foldl6_values(Pred, T2, !A, !B, !C, !D, !E, !F).
foldl6_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D, !E, !F) :-
tree234.foldl6_values(Pred, T0, !A, !B, !C, !D, !E, !F),
Pred(V0, !A, !B, !C, !D, !E, !F),
tree234.foldl6_values(Pred, T1, !A, !B, !C, !D, !E, !F),
Pred(V1, !A, !B, !C, !D, !E, !F),
tree234.foldl6_values(Pred, T2, !A, !B, !C, !D, !E, !F),
Pred(V2, !A, !B, !C, !D, !E, !F),
tree234.foldl6_values(Pred, T3, !A, !B, !C, !D, !E, !F).
%---------------------------------------------------------------------------%
foldr(F, T, A) = B :-
P = (pred(W::in, X::in, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
tree234.foldr(P, T, A, B).
foldr(_Pred, empty, !A).
foldr(Pred, two(K, V, T0, T1), !A) :-
tree234.foldr(Pred, T1, !A),
Pred(K, V, !A),
tree234.foldr(Pred, T0, !A).
foldr(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A) :-
tree234.foldr(Pred, T2, !A),
Pred(K1, V1, !A),
tree234.foldr(Pred, T1, !A),
Pred(K0, V0, !A),
tree234.foldr(Pred, T0, !A).
foldr(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), !A) :-
tree234.foldr(Pred, T3, !A),
Pred(K2, V2, !A),
tree234.foldr(Pred, T2, !A),
Pred(K1, V1, !A),
tree234.foldr(Pred, T1, !A),
Pred(K0, V0, !A),
tree234.foldr(Pred, T0, !A).
foldr2(_Pred, empty, !A, !B).
foldr2(Pred, two(K, V, T0, T1), !A, !B) :-
tree234.foldr2(Pred, T1, !A, !B),
Pred(K, V, !A, !B),
tree234.foldr2(Pred, T0, !A, !B).
foldr2(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B) :-
tree234.foldr2(Pred, T2, !A, !B),
Pred(K1, V1, !A, !B),
tree234.foldr2(Pred, T1, !A, !B),
Pred(K0, V0, !A, !B),
tree234.foldr2(Pred, T0, !A, !B).
foldr2(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), !A, !B) :-
tree234.foldr2(Pred, T3, !A, !B),
Pred(K2, V2, !A, !B),
tree234.foldr2(Pred, T2, !A, !B),
Pred(K1, V1, !A, !B),
tree234.foldr2(Pred, T1, !A, !B),
Pred(K0, V0, !A, !B),
tree234.foldr2(Pred, T0, !A, !B).
foldr3(_Pred, empty, !A, !B, !C).
foldr3(Pred, two(K, V, T0, T1), !A, !B, !C) :-
tree234.foldr3(Pred, T1, !A, !B, !C),
Pred(K, V, !A, !B, !C),
tree234.foldr3(Pred, T0, !A, !B, !C).
foldr3(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C) :-
tree234.foldr3(Pred, T2, !A, !B, !C),
Pred(K1, V1, !A, !B, !C),
tree234.foldr3(Pred, T1, !A, !B, !C),
Pred(K0, V0, !A, !B, !C),
tree234.foldr3(Pred, T0, !A, !B, !C).
foldr3(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!A, !B, !C) :-
tree234.foldr3(Pred, T3, !A, !B, !C),
Pred(K2, V2, !A, !B, !C),
tree234.foldr3(Pred, T2, !A, !B, !C),
Pred(K1, V1, !A, !B, !C),
tree234.foldr3(Pred, T1, !A, !B, !C),
Pred(K0, V0, !A, !B, !C),
tree234.foldr3(Pred, T0, !A, !B, !C).
foldr4(_Pred, empty, !A, !B, !C, !D).
foldr4(Pred, two(K, V, T0, T1), !A, !B, !C, !D) :-
tree234.foldr4(Pred, T1, !A, !B, !C, !D),
Pred(K, V, !A, !B, !C, !D),
tree234.foldr4(Pred, T0, !A, !B, !C, !D).
foldr4(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C, !D) :-
tree234.foldr4(Pred, T2, !A, !B, !C, !D),
Pred(K1, V1, !A, !B, !C, !D),
tree234.foldr4(Pred, T1, !A, !B, !C, !D),
Pred(K0, V0, !A, !B, !C, !D),
tree234.foldr4(Pred, T0, !A, !B, !C, !D).
foldr4(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D) :-
tree234.foldr4(Pred, T3, !A, !B, !C, !D),
Pred(K2, V2, !A, !B, !C, !D),
tree234.foldr4(Pred, T2, !A, !B, !C, !D),
Pred(K1, V1, !A, !B, !C, !D),
tree234.foldr4(Pred, T1, !A, !B, !C, !D),
Pred(K0, V0, !A, !B, !C, !D),
tree234.foldr4(Pred, T0, !A, !B, !C, !D).
foldr5(_Pred, empty, !A, !B, !C, !D, !E).
foldr5(Pred, two(K, V, T0, T1), !A, !B, !C, !D, !E) :-
tree234.foldr5(Pred, T1, !A, !B, !C, !D, !E),
Pred(K, V, !A, !B, !C, !D, !E),
tree234.foldr5(Pred, T0, !A, !B, !C, !D, !E).
foldr5(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C, !D, !E) :-
tree234.foldr5(Pred, T2, !A, !B, !C, !D, !E),
Pred(K1, V1, !A, !B, !C, !D, !E),
tree234.foldr5(Pred, T1, !A, !B, !C, !D, !E),
Pred(K0, V0, !A, !B, !C, !D, !E),
tree234.foldr5(Pred, T0, !A, !B, !C, !D, !E).
foldr5(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D, !E) :-
tree234.foldr5(Pred, T3, !A, !B, !C, !D, !E),
Pred(K2, V2, !A, !B, !C, !D, !E),
tree234.foldr5(Pred, T2, !A, !B, !C, !D, !E),
Pred(K1, V1, !A, !B, !C, !D, !E),
tree234.foldr5(Pred, T1, !A, !B, !C, !D, !E),
Pred(K0, V0, !A, !B, !C, !D, !E),
tree234.foldr5(Pred, T0, !A, !B, !C, !D, !E).
foldr6(_Pred, empty, !A, !B, !C, !D, !E, !F).
foldr6(Pred, two(K, V, T0, T1), !A, !B, !C, !D, !E, !F) :-
tree234.foldr6(Pred, T1, !A, !B, !C, !D, !E, !F),
Pred(K, V, !A, !B, !C, !D, !E, !F),
tree234.foldr6(Pred, T0, !A, !B, !C, !D, !E, !F).
foldr6(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C, !D, !E, !F) :-
tree234.foldr6(Pred, T2, !A, !B, !C, !D, !E, !F),
Pred(K1, V1, !A, !B, !C, !D, !E, !F),
tree234.foldr6(Pred, T1, !A, !B, !C, !D, !E, !F),
Pred(K0, V0, !A, !B, !C, !D, !E, !F),
tree234.foldr6(Pred, T0, !A, !B, !C, !D, !E, !F).
foldr6(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
!A, !B, !C, !D, !E, !F) :-
tree234.foldr6(Pred, T3, !A, !B, !C, !D, !E, !F),
Pred(K2, V2, !A, !B, !C, !D, !E, !F),
tree234.foldr6(Pred, T2, !A, !B, !C, !D, !E, !F),
Pred(K1, V1, !A, !B, !C, !D, !E, !F),
tree234.foldr6(Pred, T1, !A, !B, !C, !D, !E, !F),
Pred(K0, V0, !A, !B, !C, !D, !E, !F),
tree234.foldr6(Pred, T0, !A, !B, !C, !D, !E, !F).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
map_values(F, T1) = T2 :-
P = (pred(X::in, Y::in, Z::out) is det :- Z = F(X, Y) ),
tree234.map_values(P, T1, T2).
map_values(_Pred, empty, empty).
map_values(Pred, Tree0, Tree) :-
Tree0 = two(K0, V0, Left0, Right0),
Pred(K0, V0, W0),
tree234.map_values(Pred, Left0, Left),
tree234.map_values(Pred, Right0, Right),
Tree = two(K0, W0, Left, Right).
map_values(Pred, Tree0, Tree) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
Pred(K0, V0, W0),
Pred(K1, V1, W1),
tree234.map_values(Pred, Left0, Left),
tree234.map_values(Pred, Middle0, Middle),
tree234.map_values(Pred, Right0, Right),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_values(Pred, Tree0, Tree) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
Pred(K0, V0, W0),
Pred(K1, V1, W1),
Pred(K2, V2, W2),
tree234.map_values(Pred, Left0, Left),
tree234.map_values(Pred, LMid0, LMid),
tree234.map_values(Pred, RMid0, RMid),
tree234.map_values(Pred, Right0, Right),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_values_only(F, T1) = T2 :-
P = (pred(Y::in, Z::out) is det :- Z = F(Y) ),
tree234.map_values_only(P, T1, T2).
map_values_only(_Pred, empty, empty).
map_values_only(Pred, Tree0, Tree) :-
Tree0 = two(K0, V0, Left0, Right0),
Pred(V0, W0),
tree234.map_values_only(Pred, Left0, Left),
tree234.map_values_only(Pred, Right0, Right),
Tree = two(K0, W0, Left, Right).
map_values_only(Pred, Tree0, Tree) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
Pred(V0, W0),
Pred(V1, W1),
tree234.map_values_only(Pred, Left0, Left),
tree234.map_values_only(Pred, Middle0, Middle),
tree234.map_values_only(Pred, Right0, Right),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_values_only(Pred, Tree0, Tree) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
Pred(V0, W0),
Pred(V1, W1),
Pred(V2, W2),
tree234.map_values_only(Pred, Left0, Left),
tree234.map_values_only(Pred, LMid0, LMid),
tree234.map_values_only(Pred, RMid0, RMid),
tree234.map_values_only(Pred, Right0, Right),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
filter_map_values(Pred, Tree0, Tree) :-
filter_map_values_acc(Pred, Tree0, [], KVs),
tree234.from_sorted_assoc_list(KVs, Tree).
:- pred filter_map_values_acc(pred(K, V, W)::in(pred(in, in, out) is semidet),
tree234(K, V)::in, assoc_list(K, W)::in, assoc_list(K, W)::out) is det.
filter_map_values_acc(_Pred, empty, !KVs).
filter_map_values_acc(Pred, Tree0, !KVs) :-
Tree0 = two(K0, V0, Left, Right),
tree234.filter_map_values_acc(Pred, Right, !KVs),
( if Pred(K0, V0, W0) then !:KVs = [K0 - W0 | !.KVs] else true ),
tree234.filter_map_values_acc(Pred, Left, !KVs).
filter_map_values_acc(Pred, Tree0, !KVs) :-
Tree0 = three(K0, V0, K1, V1, Left, Middle, Right),
tree234.filter_map_values_acc(Pred, Right, !KVs),
( if Pred(K1, V1, W1) then !:KVs = [K1 - W1 | !.KVs] else true ),
tree234.filter_map_values_acc(Pred, Middle, !KVs),
( if Pred(K0, V0, W0) then !:KVs = [K0 - W0 | !.KVs] else true ),
tree234.filter_map_values_acc(Pred, Left, !KVs).
filter_map_values_acc(Pred, Tree0, !KVs) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left, LMid, RMid, Right),
tree234.filter_map_values_acc(Pred, Right, !KVs),
( if Pred(K2, V2, W2) then !:KVs = [K2 - W2 | !.KVs] else true ),
tree234.filter_map_values_acc(Pred, RMid, !KVs),
( if Pred(K1, V1, W1) then !:KVs = [K1 - W1 | !.KVs] else true ),
tree234.filter_map_values_acc(Pred, LMid, !KVs),
( if Pred(K0, V0, W0) then !:KVs = [K0 - W0 | !.KVs] else true ),
tree234.filter_map_values_acc(Pred, Left, !KVs).
filter_map_values_only(Pred, Tree0, Tree) :-
filter_map_values_only_acc(Pred, Tree0, [], KVs),
tree234.from_sorted_assoc_list(KVs, Tree).
:- pred filter_map_values_only_acc(pred(V, W)::in(pred(in, out) is semidet),
tree234(K, V)::in, assoc_list(K, W)::in, assoc_list(K, W)::out) is det.
filter_map_values_only_acc(_Pred, empty, !KVs).
filter_map_values_only_acc(Pred, Tree0, !KVs) :-
Tree0 = two(K0, V0, Left, Right),
tree234.filter_map_values_only_acc(Pred, Right, !KVs),
( if Pred(V0, W0) then !:KVs = [K0 - W0 | !.KVs] else true ),
tree234.filter_map_values_only_acc(Pred, Left, !KVs).
filter_map_values_only_acc(Pred, Tree0, !KVs) :-
Tree0 = three(K0, V0, K1, V1, Left, Middle, Right),
tree234.filter_map_values_only_acc(Pred, Right, !KVs),
( if Pred(V1, W1) then !:KVs = [K1 - W1 | !.KVs] else true ),
tree234.filter_map_values_only_acc(Pred, Middle, !KVs),
( if Pred(V0, W0) then !:KVs = [K0 - W0 | !.KVs] else true ),
tree234.filter_map_values_only_acc(Pred, Left, !KVs).
filter_map_values_only_acc(Pred, Tree0, !KVs) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left, LMid, RMid, Right),
tree234.filter_map_values_only_acc(Pred, Right, !KVs),
( if Pred(V2, W2) then !:KVs = [K2 - W2 | !.KVs] else true ),
tree234.filter_map_values_only_acc(Pred, RMid, !KVs),
( if Pred(V1, W1) then !:KVs = [K1 - W1 | !.KVs] else true ),
tree234.filter_map_values_only_acc(Pred, LMid, !KVs),
( if Pred(V0, W0) then !:KVs = [K0 - W0 | !.KVs] else true ),
tree234.filter_map_values_only_acc(Pred, Left, !KVs).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
map_foldl(_Pred, empty, empty, !A).
map_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_foldl(Pred, Left0, Left, !A),
Pred(K0, V0, W0, !A),
tree234.map_foldl(Pred, Right0, Right, !A),
Tree = two(K0, W0, Left, Right).
map_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_foldl(Pred, Left0, Left, !A),
Pred(K0, V0, W0, !A),
tree234.map_foldl(Pred, Middle0, Middle, !A),
Pred(K1, V1, W1, !A),
tree234.map_foldl(Pred, Right0, Right, !A),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_foldl(Pred, Left0, Left, !A),
Pred(K0, V0, W0, !A),
tree234.map_foldl(Pred, LMid0, LMid, !A),
Pred(K1, V1, W1, !A),
tree234.map_foldl(Pred, RMid0, RMid, !A),
Pred(K2, V2, W2, !A),
tree234.map_foldl(Pred, Right0, Right, !A),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_foldl2(_Pred, empty, empty, !A, !B).
map_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_foldl2(Pred, Left0, Left, !A, !B),
Pred(K0, V0, W0, !A, !B),
tree234.map_foldl2(Pred, Right0, Right, !A, !B),
Tree = two(K0, W0, Left, Right).
map_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_foldl2(Pred, Left0, Left, !A, !B),
Pred(K0, V0, W0, !A, !B),
tree234.map_foldl2(Pred, Middle0, Middle, !A, !B),
Pred(K1, V1, W1, !A, !B),
tree234.map_foldl2(Pred, Right0, Right, !A, !B),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_foldl2(Pred, Left0, Left, !A, !B),
Pred(K0, V0, W0, !A, !B),
tree234.map_foldl2(Pred, LMid0, LMid, !A, !B),
Pred(K1, V1, W1, !A, !B),
tree234.map_foldl2(Pred, RMid0, RMid, !A, !B),
Pred(K2, V2, W2, !A, !B),
tree234.map_foldl2(Pred, Right0, Right, !A, !B),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_foldl3(_Pred, empty, empty, !A, !B, !C).
map_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(K0, V0, W0, !A, !B, !C),
tree234.map_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = two(K0, W0, Left, Right).
map_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(K0, V0, W0, !A, !B, !C),
tree234.map_foldl3(Pred, Middle0, Middle, !A, !B, !C),
Pred(K1, V1, W1, !A, !B, !C),
tree234.map_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(K0, V0, W0, !A, !B, !C),
tree234.map_foldl3(Pred, LMid0, LMid, !A, !B, !C),
Pred(K1, V1, W1, !A, !B, !C),
tree234.map_foldl3(Pred, RMid0, RMid, !A, !B, !C),
Pred(K2, V2, W2, !A, !B, !C),
tree234.map_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_foldl4(_Pred, empty, empty, !A, !B, !C, !D).
map_foldl4(Pred, Tree0, Tree, !A, !B, !C, !D) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_foldl4(Pred, Left0, Left, !A, !B, !C, !D),
Pred(K0, V0, W0, !A, !B, !C, !D),
tree234.map_foldl4(Pred, Right0, Right, !A, !B, !C, !D),
Tree = two(K0, W0, Left, Right).
map_foldl4(Pred, Tree0, Tree, !A, !B, !C, !D) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_foldl4(Pred, Left0, Left, !A, !B, !C, !D),
Pred(K0, V0, W0, !A, !B, !C, !D),
tree234.map_foldl4(Pred, Middle0, Middle, !A, !B, !C, !D),
Pred(K1, V1, W1, !A, !B, !C, !D),
tree234.map_foldl4(Pred, Right0, Right, !A, !B, !C, !D),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_foldl4(Pred, Tree0, Tree, !A, !B, !C, !D) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_foldl4(Pred, Left0, Left, !A, !B, !C, !D),
Pred(K0, V0, W0, !A, !B, !C, !D),
tree234.map_foldl4(Pred, LMid0, LMid, !A, !B, !C, !D),
Pred(K1, V1, W1, !A, !B, !C, !D),
tree234.map_foldl4(Pred, RMid0, RMid, !A, !B, !C, !D),
Pred(K2, V2, W2, !A, !B, !C, !D),
tree234.map_foldl4(Pred, Right0, Right, !A, !B, !C, !D),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_values_foldl(_Pred, empty, empty, !A).
map_values_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_values_foldl(Pred, Left0, Left, !A),
Pred(V0, W0, !A),
tree234.map_values_foldl(Pred, Right0, Right, !A),
Tree = two(K0, W0, Left, Right).
map_values_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_values_foldl(Pred, Left0, Left, !A),
Pred(V0, W0, !A),
tree234.map_values_foldl(Pred, Middle0, Middle, !A),
Pred(V1, W1, !A),
tree234.map_values_foldl(Pred, Right0, Right, !A),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_values_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_values_foldl(Pred, Left0, Left, !A),
Pred(V0, W0, !A),
tree234.map_values_foldl(Pred, LMid0, LMid, !A),
Pred(V1, W1, !A),
tree234.map_values_foldl(Pred, RMid0, RMid, !A),
Pred(V2, W2, !A),
tree234.map_values_foldl(Pred, Right0, Right, !A),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_values_only_foldl(_Pred, empty, empty, !A).
map_values_only_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_values_only_foldl(Pred, Left0, Left, !A),
Pred(V0, W0, !A),
tree234.map_values_only_foldl(Pred, Right0, Right, !A),
Tree = two(K0, W0, Left, Right).
map_values_only_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_values_only_foldl(Pred, Left0, Left, !A),
Pred(V0, W0, !A),
tree234.map_values_only_foldl(Pred, Middle0, Middle, !A),
Pred(V1, W1, !A),
tree234.map_values_only_foldl(Pred, Right0, Right, !A),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_values_only_foldl(Pred, Tree0, Tree, !A) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_values_only_foldl(Pred, Left0, Left, !A),
Pred(V0, W0, !A),
tree234.map_values_only_foldl(Pred, LMid0, LMid, !A),
Pred(V1, W1, !A),
tree234.map_values_only_foldl(Pred, RMid0, RMid, !A),
Pred(V2, W2, !A),
tree234.map_values_only_foldl(Pred, Right0, Right, !A),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_values_foldl2(_Pred, empty, empty, !A, !B).
map_values_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_values_foldl2(Pred, Left0, Left, !A, !B),
Pred(V0, W0, !A, !B),
tree234.map_values_foldl2(Pred, Right0, Right, !A, !B),
Tree = two(K0, W0, Left, Right).
map_values_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_values_foldl2(Pred, Left0, Left, !A, !B),
Pred(V0, W0, !A, !B),
tree234.map_values_foldl2(Pred, Middle0, Middle, !A, !B),
Pred(V1, W1, !A, !B),
tree234.map_values_foldl2(Pred, Right0, Right, !A, !B),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_values_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_values_foldl2(Pred, Left0, Left, !A, !B),
Pred(V0, W0, !A, !B),
tree234.map_values_foldl2(Pred, LMid0, LMid, !A, !B),
Pred(V1, W1, !A, !B),
tree234.map_values_foldl2(Pred, RMid0, RMid, !A, !B),
Pred(V2, W2, !A, !B),
tree234.map_values_foldl2(Pred, Right0, Right, !A, !B),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_values_only_foldl2(_Pred, empty, empty, !A, !B).
map_values_only_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_values_only_foldl2(Pred, Left0, Left, !A, !B),
Pred(V0, W0, !A, !B),
tree234.map_values_only_foldl2(Pred, Right0, Right, !A, !B),
Tree = two(K0, W0, Left, Right).
map_values_only_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_values_only_foldl2(Pred, Left0, Left, !A, !B),
Pred(V0, W0, !A, !B),
tree234.map_values_only_foldl2(Pred, Middle0, Middle, !A, !B),
Pred(V1, W1, !A, !B),
tree234.map_values_only_foldl2(Pred, Right0, Right, !A, !B),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_values_only_foldl2(Pred, Tree0, Tree, !A, !B) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_values_only_foldl2(Pred, Left0, Left, !A, !B),
Pred(V0, W0, !A, !B),
tree234.map_values_only_foldl2(Pred, LMid0, LMid, !A, !B),
Pred(V1, W1, !A, !B),
tree234.map_values_only_foldl2(Pred, RMid0, RMid, !A, !B),
Pred(V2, W2, !A, !B),
tree234.map_values_only_foldl2(Pred, Right0, Right, !A, !B),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_values_foldl3(_Pred, empty, empty, !A, !B, !C).
map_values_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_values_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(V0, W0, !A, !B, !C),
tree234.map_values_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = two(K0, W0, Left, Right).
map_values_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_values_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(V0, W0, !A, !B, !C),
tree234.map_values_foldl3(Pred, Middle0, Middle, !A, !B, !C),
Pred(V1, W1, !A, !B, !C),
tree234.map_values_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_values_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_values_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(V0, W0, !A, !B, !C),
tree234.map_values_foldl3(Pred, LMid0, LMid, !A, !B, !C),
Pred(V1, W1, !A, !B, !C),
tree234.map_values_foldl3(Pred, RMid0, RMid, !A, !B, !C),
Pred(V2, W2, !A, !B, !C),
tree234.map_values_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
map_values_only_foldl3(_Pred, empty, empty, !A, !B, !C).
map_values_only_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = two(K0, V0, Left0, Right0),
tree234.map_values_only_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(V0, W0, !A, !B, !C),
tree234.map_values_only_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = two(K0, W0, Left, Right).
map_values_only_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
tree234.map_values_only_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(V0, W0, !A, !B, !C),
tree234.map_values_only_foldl3(Pred, Middle0, Middle, !A, !B, !C),
Pred(V1, W1, !A, !B, !C),
tree234.map_values_only_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = three(K0, W0, K1, W1, Left, Middle, Right).
map_values_only_foldl3(Pred, Tree0, Tree, !A, !B, !C) :-
Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
tree234.map_values_only_foldl3(Pred, Left0, Left, !A, !B, !C),
Pred(V0, W0, !A, !B, !C),
tree234.map_values_only_foldl3(Pred, LMid0, LMid, !A, !B, !C),
Pred(V1, W1, !A, !B, !C),
tree234.map_values_only_foldl3(Pred, RMid0, RMid, !A, !B, !C),
Pred(V2, W2, !A, !B, !C),
tree234.map_values_only_foldl3(Pred, Right0, Right, !A, !B, !C),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
tree234_to_doc(T) = pretty_printer.tree234_to_doc(T).
tree234_to_lazy_list(empty, LL) = LL.
tree234_to_lazy_list(two(K1, V1, T1, T2), LL) =
tree234_to_lazy_list(T1,
tll_lazy_cons(K1, V1,
(func) = tree234_to_lazy_list(T2, LL))).
tree234_to_lazy_list(three(K1, V1, K2, V2, T1, T2, T3), LL) =
tree234_to_lazy_list(T1,
tll_lazy_cons(K1, V1,
(func) = tree234_to_lazy_list(two(K2, V2, T2, T3), LL))).
tree234_to_lazy_list(four(K1, V1, K2, V2, K3, V3, T1, T2, T3, T4), LL) =
tree234_to_lazy_list(T1,
tll_lazy_cons(K1, V1,
(func) = tree234_to_lazy_list(
three(K2, V2, K3, V3, T2, T3, T4), LL))).
%---------------------------------------------------------------------------%
find_min_size_based_on_depth(T, MinSize) :-
find_depth(T, Depth),
min_size_based_on_depth(Depth, MinSize).
:- pred min_size_based_on_depth(int::in, int::out) is det.
min_size_based_on_depth(Depth, MinSize) :-
( if Depth = 0 then
MinSize = 0
else
min_size_based_on_depth(Depth - 1, MinSizeBelow),
MinSize = MinSizeBelow * 2 + 1
).
:- pred find_depth(tree234(K, V)::in, int::out) is det.
find_depth(empty, 0).
find_depth(two(_, _, T1, _), Depth + 1) :-
find_depth(T1, Depth).
find_depth(three(_, _, _, _, T1, _, _), Depth + 1) :-
find_depth(T1, Depth).
find_depth(four(_, _, _, _, _, _, T1, _, _, _), Depth + 1) :-
find_depth(T1, Depth).
%---------------------------------------------------------------------------%
well_formed(Tree, WellFormed) :-
depth_levels(Tree, 0, set.init, Depths),
( if set.is_singleton(Depths, Depth) then
WellFormed = yes(Depth)
else
WellFormed = no
).
:- pred depth_levels(tree234(K, V)::in, int::in,
set(int)::in, set(int)::out) is det.
depth_levels(empty, Depth, !Depths) :-
set.insert(Depth, !Depths).
depth_levels(two(_, _, T1, T2), Depth, !Depths) :-
NextDepth = Depth + 1,
depth_levels(T1, NextDepth, !Depths),
depth_levels(T2, NextDepth, !Depths).
depth_levels(three(_, _, _, _, T1, T2, T3), Depth, !Depths) :-
NextDepth = Depth + 1,
depth_levels(T1, NextDepth, !Depths),
depth_levels(T2, NextDepth, !Depths),
depth_levels(T3, NextDepth, !Depths).
depth_levels(four(_, _, _, _, _, _, T1, T2, T3, T4), Depth, !Depths) :-
NextDepth = Depth + 1,
depth_levels(T1, NextDepth, !Depths),
depth_levels(T2, NextDepth, !Depths),
depth_levels(T3, NextDepth, !Depths),
depth_levels(T4, NextDepth, !Depths).
%---------------------------------------------------------------------------%
:- end_module tree234.
%---------------------------------------------------------------------------%
Reference in New Issue View Git Blame Copy Permalink