more problems with t234.
Zoltan Somogyi
zs at cs.mu.oz.au
Sat Apr 5 18:16:17 AEST 1997
Chris wrote:
> I think that a solution to the problem would be to have seperate
> predicates for set, set2 and set3. The case for the empty and four
> nodes would be handled in set. I think that this implementation could
> also be made to run more efficiently than the previous implementation.
Yesterday I modified set and insert to make sure that we always got balanced
trees (and to make variable names more meaningful), and applied the
optimization that reduces the number of variables saved across calls.
The results were excellent: a speedup of around 35%.
Today I followed Chris's suggestion. While using separate set2 and set3
predicates eliminates indexing in the called predicate, it requires extra
indexing in the called predicate. Previously, we used an if-then-else
to check for whether the selected subnode was a four-node or not; we
must now also check whether it is a two-node, three-node or empty, and
act accordingly. The result is no speedup, but no real slowdown either.
The numbers are a bit fuzzy. Here they are:
holly:
batch/crs.mercury_compile.1 54.62u 0.53s 1:03.64 86.6%
batch/crs.mercury_compile.1 55.44u 0.49s 1:04.42 86.8%
batch/crs.mercury_compile.1 55.64u 0.50s 1:06.13 84.8%
batch/crs.mercury_compile.1 55.33u 0.56s 1:06.27 84.3%
batch/crs.mercury_compile.2 38.75u 0.63s 0:47.34 83.1%
batch/crs.mercury_compile.2 39.93u 0.35s 0:44.09 91.3%
batch/crs.mercury_compile.2 39.89u 0.39s 0:44.25 91.0%
batch/crs.mercury_compile.2 40.34u 0.38s 0:45.90 88.7%
batch/crs.mercury_compile.3 41.00u 0.52s 0:45.74 90.7%
batch/crs.mercury_compile.3 39.80u 0.49s 0:45.72 88.1%
batch/crs.mercury_compile.3 40.54u 0.30s 0:45.06 90.6%
batch/crs.mercury_compile.3 38.85u 0.45s 0:44.11 89.0%
kryten:
batch/crs.mercury_compile.1 156.66u 2.65s 2:40.02 99.5%
batch/crs.mercury_compile.1 149.96u 2.13s 2:32.47 99.7%
batch/crs.mercury_compile.1 151.12u 2.18s 2:33.63 99.7%
batch/crs.mercury_compile.1 152.86u 2.27s 2:37.62 98.4%
batch/crs.mercury_compile.2 114.24u 1.84s 1:56.50 99.6%
batch/crs.mercury_compile.2 112.63u 1.87s 1:54.78 99.7%
batch/crs.mercury_compile.2 116.05u 1.77s 2:01.05 97.3%
batch/crs.mercury_compile.2 127.99u 2.21s 2:13.98 97.1%
batch/crs.mercury_compile.3 116.41u 2.05s 2:01.60 97.4%
batch/crs.mercury_compile.3 117.08u 1.77s 2:01.14 98.1%
batch/crs.mercury_compile.3 114.96u 1.87s 1:58.23 98.8%
batch/crs.mercury_compile.3 117.82u 1.81s 2:00.38 99.3%
The benchmark task was compiling make_hlds.m. There are four measurements
of three different executables, each with a different version of tree234.m.
batch/crs.mercury_compile.1 used the old tree234.m;
batch/crs.mercury_compile.2 uses a version with my changes from yesterday,
while batch/crs.mercury_compile.3 has those changes plus separate set2 and set3
(and insert2 and insert3) predicates as well.
Given that the third version is at worst marginally worse than the second,
and that termination analysis should do better on it, that's the one I intend
to check in. Any objections?
> As an aside, i couldnt help noticing when looking at tree234 how
> unbalanced a tree becomes after a deletion. it would be reasonably easy
> to modify deletion so that it possibly made the tree slightly
> unbalanced, instead of the current implementation which doubles the
> depth of 1 branch of the tree.
I will look into this later.
Zoltan.
The diff for tree234.m is unreadable. Here is the affected portion of the
new version of the file.
%------------------------------------------------------------------------------%
tree234__search(T, K, V) :-
(
T = empty,
fail
;
T = two(K0, _, _, _),
compare(Result, K, K0),
(
Result = (<),
T = two(_, _, T0, _),
tree234__search(T0, K, V)
;
Result = (=),
T = two(_, V0, _, _),
V = V0
;
Result = (>),
T = two(_, _, _, T1),
tree234__search(T1, K, V)
)
;
T = three(K0, _, _, _, _, _, _),
compare(Result0, K, K0),
(
Result0 = (<),
T = three(_, _, _, _, T0, _, _),
tree234__search(T0, K, V)
;
Result0 = (=),
T = three(_, V0, _, _, _, _, _),
V = V0
;
Result0 = (>),
T = three(_, _, K1, _, _, _, _),
compare(Result1, K, K1),
(
Result1 = (<),
T = three(_, _, _, _, _, T1, _),
tree234__search(T1, K, V)
;
Result1 = (=),
T = three(_, _, _, V1, _, _, _),
V = V1
;
Result1 = (>),
T = three(_, _, _, _, _, _, T2),
tree234__search(T2, K, V)
)
)
;
T = four(_, _, K1, _, _, _, _, _, _, _),
compare(Result1, K, K1),
(
Result1 = (<),
T = four(K0, _, _, _, _, _, _, _, _, _),
compare(Result0, K, K0),
(
Result0 = (<),
T = four(_, _, _, _, _, _, T0, _, _, _),
tree234__search(T0, K, V)
;
Result0 = (=),
T = four(_, V0, _, _, _, _, _, _, _, _),
V = V0
;
Result0 = (>),
T = four(_, _, _, _, _, _, _, T1, _, _),
tree234__search(T1, K, V)
)
;
Result1 = (=),
T = four(_, _, _, V1, _, _, _, _, _, _),
V = V1
;
Result1 = (>),
T = four(_, _, _, _, K2, _, _, _, _, _),
compare(Result2, K, K2),
(
Result2 = (<),
T = four(_, _, _, _, _, _, _, _, T2, _),
tree234__search(T2, K, V)
;
Result2 = (=),
T = four(_, _, _, _, _, V2, _, _, _, _),
V = V2
;
Result2 = (>),
T = four(_, _, _, _, _, _, _, _, _, T3),
tree234__search(T3, K, V)
)
)
).
%------------------------------------------------------------------------------%
tree234__update(Tin, K, V, Tout) :-
(
Tin = empty,
fail
;
Tin = two(K0, _, _, _),
compare(Result, K, K0),
(
Result = (<),
Tin = two(_, _, T0, _),
tree234__update(T0, K, V, NewT0),
Tin = two(_, V0, _, T1),
Tout = two(K0, V0, NewT0, T1)
;
Result = (=),
Tin = two(_, _, T0, T1),
Tout = two(K0, V, T0, T1)
;
Result = (>),
Tin = two(_, _, _, T1),
tree234__update(T1, K, V, NewT1),
Tin = two(_, V0, T0, _),
Tout = two(K0, V0, T0, NewT1)
)
;
Tin = three(K0, _, _, _, _, _, _),
compare(Result0, K, K0),
(
Result0 = (<),
Tin = three(_, _, _, _, T0, _, _),
tree234__update(T0, K, V, NewT0),
Tin = three(_, V0, K1, V1, _, T1, T2),
Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
Result0 = (=),
Tin = three(_, _, K1, V1, T0, T1, T2),
Tout = three(K0, V, K1, V1, T0, T1, T2)
;
Result0 = (>),
Tin = three(_, _, K1, _, _, _, _),
compare(Result1, K, K1),
(
Result1 = (<),
Tin = three(_, _, _, _, _, T1, _),
tree234__update(T1, K, V, NewT1),
Tin = three(_, V0, _, V1, T0, _, T2),
Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
Result1 = (=),
Tin = three(_, V0, _, _, T0, T1, T2),
Tout = three(K0, V0, K1, V, T0, T1, T2)
;
Result1 = (>),
Tin = three(_, _, _, _, _, _, T2),
tree234__update(T2, K, V, NewT2),
Tin = three(_, V0, _, V1, T0, T1, _),
Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
)
)
;
Tin = four(_, _, K1, _, _, _, _, _, _, _),
compare(Result1, K, K1),
(
Result1 = (<),
Tin = four(K0, _, _, _, _, _, _, _, _, _),
compare(Result0, K, K0),
(
Result0 = (<),
Tin = four(_, _, _, _, _, _, T0, _, _, _),
tree234__update(T0, K, V, NewT0),
Tin = four(_, V0, _, V1, K2, V2, _, T1, T2, T3),
Tout = four(K0, V0, K1, V1, K2, V2,
NewT0, T1, T2, T3)
;
Result0 = (=),
Tin = four(_, _, _, V1, K2, V2, T0, T1, T2, T3),
Tout = four(K0, V, K1, V1, K2, V2,
T0, T1, T2, T3)
;
Result0 = (>),
Tin = four(_, _, _, _, _, _, _, T1, _, _),
tree234__update(T1, K, V, NewT1),
Tin = four(_, V0, _, V1, K2, V2, T0, _, T2, T3),
Tout = four(K0, V0, K1, V1, K2, V2,
T0, NewT1, T2, T3)
)
;
Result1 = (=),
Tin = four(K0, V0, _, _, K2, V2, T0, T1, T2, T3),
Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
;
Result1 = (>),
Tin = four(_, _, _, _, K2, _, _, _, _, _),
compare(Result2, K, K2),
(
Result2 = (<),
Tin = four(_, _, _, _, _, _, _, _, T2, _),
tree234__update(T2, K, V, NewT2),
Tin = four(K0, V0, _, V1, _, V2, T0, T1, _, T3),
Tout = four(K0, V0, K1, V1, K2, V2,
T0, T1, NewT2, T3)
;
Result2 = (=),
Tin = four(K0, V0, _, V1, _, _, T0, T1, T2, T3),
Tout = four(K0, V0, K1, V1, K2, V,
T0, T1, T2, T3)
;
Result2 = (>),
Tin = four(_, _, _, _, _, _, _, _, _, T3),
tree234__update(T3, K, V, NewT3),
Tin = four(K0, V0, _, V1, _, V2, T0, T1, T2, _),
Tout = four(K0, V0, K1, V1, K2, V2,
T0, T1, T2, NewT3)
)
)
).
%------------------------------------------------------------------------------%
tree234__lookup(T, K, V) :-
(
tree234__search(T, K, V0)
->
V = V0
;
error("tree234__lookup: key not found.")
).
%------------------------------------------------------------------------------%
:- inst two(K, V, T) =
bound(
two(K, V, T, T)
).
:- inst uniq_two(K, V, T) =
unique(
two(K, V, T, T)
).
:- inst three(K, V, T) =
bound(
three(K, V, K, V, T, T, T)
).
:- inst uniq_three(K, V, T) =
unique(
three(K, V, K, V, T, T, T)
).
:- inst four(K, V, T) =
bound(
four(K, V, K, V, K, V, T, T, T, T)
).
:- inst uniq_four(K, V, T) =
unique(
four(K, V, K, V, K, V, T, T, T, T)
).
:- 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)).
%------------------------------------------------------------------------------%
:- pred tree234__split_four(tree234(K, V), K, V, tree234(K, V), tree234(K, V)).
:- mode tree234__split_four(di_four, uo, uo, uo_two, uo_two) is det.
:- mode tree234__split_four(sdi_four, out, out, suo_two, suo_two) is det.
:- mode tree234__split_four(in_four, out, out, out_two, out_two) is det.
tree234__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).
%------------------------------------------------------------------------------%
% tree234__insert is implemented using the simple top-down
% approach described in eg Sedgwick which 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 already split 4 nodes into 2 nodes), or if the
% tree itself is empty.
% This algorithm is O(lgN).
tree234__insert(Tin, K, V, 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 tree234__insert2(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__insert2(di_two, di, di, uo) is semidet.
:- mode tree234__insert2(sdi_two, in, in, uo_tree234) is semidet.
:- mode tree234__insert2(in_two, in, in, out) is semidet.
tree234__insert2(two(K0, V0, T0, T1), K, V, Tout) :-
(
T0 = empty,
T1 = empty
->
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)
)
;
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 tree234__insert3(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__insert3(di_three, di, di, uo) is semidet.
:- mode tree234__insert3(sdi_three, in, in, uo_tree234) is semidet.
:- mode tree234__insert3(in_three, in, in, out) is semidet.
tree234__insert3(three(K0, V0, K1, V1, T0, T1, T2), K, V, Tout) :-
(
T0 = empty,
T1 = empty,
T2 = empty
->
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)
)
)
;
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)
)
)
)
).
%------------------------------------------------------------------------------%
% tree234__set uses the same algorithm as used for tree234__insert,
% except that instead of failing for equal keys, we replace the value.
tree234__set(Tin, K, V, Tout) :-
(
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 tree234__set2(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__set2(di_two, di, di, uo) is det.
:- mode tree234__set2(sdi_two, in, in, uo_tree234) is det.
:- mode tree234__set2(in_two, in, in, out) is det.
tree234__set2(two(K0, V0, T0, T1), K, V, Tout) :-
(
T0 = empty,
T1 = empty
->
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)
)
;
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 tree234__set3(tree234(K, V), K, V, tree234(K, V)).
:- mode tree234__set3(di_three, di, di, uo) is det.
:- mode tree234__set3(sdi_three, in, in, uo_tree234) is det.
:- mode tree234__set3(in_three, in, in, out) is det.
tree234__set3(three(K0, V0, K1, V1, T0, T1, T2), K, V, Tout) :-
(
T0 = empty,
T1 = empty,
T2 = empty
->
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)
)
)
;
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)
)
)
)
).
%------------------------------------------------------------------------------%
More information about the developers
mailing list