[m-rev.] for post-commit review: build 234 trees dorectly
Zoltan Somogyi
zs at csse.unimelb.edu.au
Fri Jan 2 14:10:41 AEDT 2009
Add and use the capability of building 234 trees directly.
library/tree234.m:
Add new predicates for converting sorted assoc lists (both ascending
and descending) directly to trees. These should be significantly more
efficient than the existing assoc_list_to_tree234 predicate, which
does not assume sortedness, and thus inserts each element individually.
The main source of the efficiency improvement is that we avoid the
creation of lots of intermediate trees.
Add some sanity check predicates in the part of the module that
is not included in the documentation.
library/map.m:
Add a new predicate for creating a map from a reverse sorted assoc
list.
Modify the existing predicate for creating a map from a sorted assoc
list to use the new predicate in tree234.m, which should be more
efficient.
Since the new implementation of this predicate doesn't allow
duplicates, modify map.old_merge, which cannot ensure the absence of
duplicates, to call the old general implementation (which is not
reliant on sortedness or duplicate-freedom) instead.
NEWS:
Mention the publically visible new predicates, and the change in
map.from_sorted_assoc_list.
compiler/code_info.m:
compiler/equiv_type.m:
compiler/intermod.m:
compiler/var_locn.m:
Use the new, faster predicates when possible.
compiler/hlds_goal.m:
compiler/instmap.m:
Give some variables better names.
tests/hard_coded/tree234_sorted_insert.{m,exp}:
New test case to check the new functionality.
tests/hard_coded/Mmakefile:
Enable the new test case.
cvs diff: Diffing .
Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.497
diff -u -b -r1.497 NEWS
--- NEWS 23 Sep 2008 06:42:24 -0000 1.497
+++ NEWS 30 Dec 2008 09:38:45 -0000
@@ -225,6 +225,15 @@
construct.find_functor/5
type_desc.same_type/2
+* We have added new predicates to the tree234 and map modules for constructing
+ 2-3-4 trees and maps directly (without the creation of intermediate trees)
+ from sorted lists:
+ tree234.from_sorted_assoc_list/2
+ tree234.from_rev_sorted_assoc_list/2
+ map.from_rev_sorted_assoc_list/2
+ map.from_sorted_assoc_list now also constructs the tree directly, so now
+ it requires its input list to be duplicate-free.
+
Changes to the Mercury compiler:
* We have added support for trail segments, which allow programs to grow
cvs diff: Diffing analysis
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/doc
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops-1.2
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/doc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops-1.2/tests
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing boehm_gc/windows-untested
cvs diff: Diffing boehm_gc/windows-untested/vc60
cvs diff: Diffing boehm_gc/windows-untested/vc70
cvs diff: Diffing boehm_gc/windows-untested/vc71
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/code_info.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/code_info.m,v
retrieving revision 1.369
diff -u -b -r1.369 code_info.m
--- compiler/code_info.m 23 Dec 2008 01:37:30 -0000 1.369
+++ compiler/code_info.m 30 Dec 2008 06:28:10 -0000
@@ -1252,10 +1252,9 @@
% afterwards, since every goal following a branched control structure
% must in any case be annotated with its own follow_var set.
map.to_assoc_list(StoreMap, AbsVarLocs),
- map.from_assoc_list(AbsVarLocs, FollowVarsMap),
assoc_list.values(AbsVarLocs, AbsLocs),
code_util.max_mentioned_abs_reg(AbsLocs, MaxMentionedReg),
- set_follow_vars(abs_follow_vars(FollowVarsMap, MaxMentionedReg + 1), !CI),
+ set_follow_vars(abs_follow_vars(StoreMap, MaxMentionedReg + 1), !CI),
get_instmap(!.CI, InstMap),
( instmap_is_reachable(InstMap) ->
VarLocs = assoc_list.map_values(key_abs_locn_to_lval, AbsVarLocs),
@@ -2897,7 +2896,7 @@
StackList0 = assoc_list.map_values(key_stack_slot_to_lval,
AbsStackList),
make_singleton_sets(StackList0, StackList),
- map.from_assoc_list(StackList, StackMap)
+ map.from_sorted_assoc_list(StackList, StackMap)
;
MaybeFailVars = no,
map.init(StackMap)
@@ -2999,15 +2998,15 @@
map.to_assoc_list(StackMap0, AbsStackList),
StackList0 = assoc_list.map_values(key_stack_slot_to_lval, AbsStackList),
make_singleton_sets(StackList0, StackList),
- map.from_assoc_list(StackList, StackMap).
+ map.from_sorted_assoc_list(StackList, StackMap).
:- pred make_singleton_sets(assoc_list(prog_var, lval)::in,
assoc_list(prog_var, set(lval))::out) is det.
make_singleton_sets([], []).
-make_singleton_sets([V - L | Rest0], [V - Ls | Rest]) :-
- set.singleton_set(Ls, L),
- make_singleton_sets(Rest0, Rest).
+make_singleton_sets([Var - Lval | Tail], [Var - Lvals | SetTail]) :-
+ set.singleton_set(Lvals, Lval),
+ make_singleton_sets(Tail, SetTail).
%---------------------------------------------------------------------------%
Index: compiler/equiv_type.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/equiv_type.m,v
retrieving revision 1.82
diff -u -b -r1.82 equiv_type.m
--- compiler/equiv_type.m 28 Jul 2008 08:34:16 -0000 1.82
+++ compiler/equiv_type.m 30 Dec 2008 06:28:57 -0000
@@ -151,7 +151,7 @@
map.to_assoc_list(EventSpecMap0, EventSpecList0),
replace_in_event_spec_list(EventSpecList0, EventSpecList,
EqvMap, EqvInstMap, !RecompInfo, !UsedModules, !Specs),
- map.from_assoc_list(EventSpecList, EventSpecMap).
+ map.from_sorted_assoc_list(EventSpecList, EventSpecMap).
% We need to expand equivalence insts in
% `:- pred p `with_inst` i' declarations.
Index: compiler/hlds_goal.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/hlds_goal.m,v
retrieving revision 1.201
diff -u -b -r1.201 hlds_goal.m
--- compiler/hlds_goal.m 23 Dec 2008 01:37:33 -0000 1.201
+++ compiler/hlds_goal.m 30 Dec 2008 06:20:55 -0000
@@ -2671,17 +2671,19 @@
assoc_list(var(V), T)::in, assoc_list(var(V), T)::out) is det.
rename_var_maps_2(_Must, _Subn, [], []).
-rename_var_maps_2(Must, Subn, [V - L | Vs], [N - L | Ns]) :-
- rename_var(Must, Subn, V, N),
- rename_var_maps_2(Must, Subn, Vs, Ns).
+rename_var_maps_2(Must, Subn,
+ [Var - Item | VarItems], [NewVar - Item | NewVarItems]) :-
+ rename_var(Must, Subn, Var, NewVar),
+ rename_var_maps_2(Must, Subn, VarItems, NewVarItems).
:- pred rename_var_pair_list(must_rename::in, prog_var_renaming::in,
assoc_list(prog_var, T)::in, list(pair(prog_var, T))::out) is det.
rename_var_pair_list(_Must, _Subn, [], []).
-rename_var_pair_list(Must, Subn, [V - D | VDs], [N - D | NDs]) :-
- rename_var(Must, Subn, V, N),
- rename_var_pair_list(Must, Subn, VDs, NDs).
+rename_var_pair_list(Must, Subn,
+ [Var - Item | VarItems], [NewVar - Item | NewVarItems]) :-
+ rename_var(Must, Subn, Var, NewVar),
+ rename_var_pair_list(Must, Subn, VarItems, NewVarItems).
%-----------------------------------------------------------------------------%
%
Index: compiler/instmap.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/instmap.m,v
retrieving revision 1.62
diff -u -b -r1.62 instmap.m
--- compiler/instmap.m 23 Dec 2008 01:37:34 -0000 1.62
+++ compiler/instmap.m 30 Dec 2008 09:18:09 -0000
@@ -1174,14 +1174,14 @@
compute_instmap_delta_2([], _, _, []).
compute_instmap_delta_2([Var | Vars], InstMapA, InstMapB, AssocList) :-
+ compute_instmap_delta_2(Vars, InstMapA, InstMapB, AssocListTail),
instmapping_lookup_var(InstMapA, Var, InstA),
instmapping_lookup_var(InstMapB, Var, InstB),
( InstA = InstB ->
- AssocList1 = AssocList
+ AssocList = AssocListTail
;
- AssocList = [Var - InstB | AssocList1]
- ),
- compute_instmap_delta_2(Vars, InstMapA, InstMapB, AssocList1).
+ AssocList = [Var - InstB | AssocListTail]
+ ).
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
Index: compiler/intermod.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/intermod.m,v
retrieving revision 1.239
diff -u -b -r1.239 intermod.m
--- compiler/intermod.m 23 Dec 2008 01:37:34 -0000 1.239
+++ compiler/intermod.m 30 Dec 2008 06:18:12 -0000
@@ -2128,7 +2128,7 @@
module_info_get_type_table(!.ModuleInfo, Types0),
map.to_assoc_list(Types0, TypesAL0),
list.map_foldl(adjust_type_status_2, TypesAL0, TypesAL, !ModuleInfo),
- map.from_assoc_list(TypesAL, Types),
+ map.from_sorted_assoc_list(TypesAL, Types),
module_info_set_type_table(Types, !ModuleInfo).
:- pred adjust_type_status_2(pair(type_ctor, hlds_type_defn)::in,
@@ -2161,7 +2161,7 @@
module_info_get_class_table(!.ModuleInfo, Classes0),
map.to_assoc_list(Classes0, ClassAL0),
list.map_foldl(adjust_class_status_2, ClassAL0, ClassAL, !ModuleInfo),
- map.from_assoc_list(ClassAL, Classes),
+ map.from_sorted_assoc_list(ClassAL, Classes),
module_info_set_class_table(Classes, !ModuleInfo).
:- pred adjust_class_status_2(pair(class_id, hlds_class_defn)::in,
@@ -2196,7 +2196,7 @@
map.to_assoc_list(Instances0, InstanceAL0),
list.map_foldl(adjust_instance_status_2, InstanceAL0, InstanceAL,
!ModuleInfo),
- map.from_assoc_list(InstanceAL, Instances),
+ map.from_sorted_assoc_list(InstanceAL, Instances),
module_info_set_instance_table(Instances, !ModuleInfo).
:- pred adjust_instance_status_2(pair(class_id, list(hlds_instance_defn))::in,
Index: compiler/var_locn.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/var_locn.m,v
retrieving revision 1.65
diff -u -b -r1.65 var_locn.m
--- compiler/var_locn.m 8 Sep 2008 03:39:06 -0000 1.65
+++ compiler/var_locn.m 30 Dec 2008 06:30:37 -0000
@@ -557,7 +557,7 @@
var_locn_get_var_state_map(VLI, VarStateMap),
map.to_assoc_list(VarStateMap, VarLocList),
list.filter_map(convert_live_to_lval_set, VarLocList, LiveVarLocList),
- map.from_assoc_list(LiveVarLocList, VarLocations).
+ map.from_sorted_assoc_list(LiveVarLocList, VarLocations).
:- pred convert_live_to_lval_set(pair(prog_var, var_state)::in,
pair(prog_var, set(lval))::out) is semidet.
cvs diff: Diffing compiler/notes
cvs diff: Diffing debian
cvs diff: Diffing debian/patches
cvs diff: Diffing deep_profiler
cvs diff: Diffing deep_profiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/base64
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing extras/concurrency
cvs diff: Diffing extras/curs
cvs diff: Diffing extras/curs/samples
cvs diff: Diffing extras/curses
cvs diff: Diffing extras/curses/sample
cvs diff: Diffing extras/dynamic_linking
cvs diff: Diffing extras/error
cvs diff: Diffing extras/fixed
cvs diff: Diffing extras/gator
cvs diff: Diffing extras/gator/generations
cvs diff: Diffing extras/gator/generations/1
cvs diff: Diffing extras/graphics
cvs diff: Diffing extras/graphics/easyx
cvs diff: Diffing extras/graphics/easyx/samples
cvs diff: Diffing extras/graphics/mercury_allegro
cvs diff: Diffing extras/graphics/mercury_allegro/examples
cvs diff: Diffing extras/graphics/mercury_allegro/samples
cvs diff: Diffing extras/graphics/mercury_allegro/samples/demo
cvs diff: Diffing extras/graphics/mercury_allegro/samples/mandel
cvs diff: Diffing extras/graphics/mercury_allegro/samples/pendulum2
cvs diff: Diffing extras/graphics/mercury_allegro/samples/speed
cvs diff: Diffing extras/graphics/mercury_glut
cvs diff: Diffing extras/graphics/mercury_opengl
cvs diff: Diffing extras/graphics/mercury_tcltk
cvs diff: Diffing extras/graphics/samples
cvs diff: Diffing extras/graphics/samples/calc
cvs diff: Diffing extras/graphics/samples/gears
cvs diff: Diffing extras/graphics/samples/maze
cvs diff: Diffing extras/graphics/samples/pent
cvs diff: Diffing extras/lazy_evaluation
cvs diff: Diffing extras/lex
cvs diff: Diffing extras/lex/samples
cvs diff: Diffing extras/lex/tests
cvs diff: Diffing extras/log4m
cvs diff: Diffing extras/logged_output
cvs diff: Diffing extras/moose
cvs diff: Diffing extras/moose/samples
cvs diff: Diffing extras/moose/tests
cvs diff: Diffing extras/mopenssl
cvs diff: Diffing extras/morphine
cvs diff: Diffing extras/morphine/non-regression-tests
cvs diff: Diffing extras/morphine/scripts
cvs diff: Diffing extras/morphine/source
cvs diff: Diffing extras/net
cvs diff: Diffing extras/odbc
cvs diff: Diffing extras/posix
cvs diff: Diffing extras/posix/samples
cvs diff: Diffing extras/quickcheck
cvs diff: Diffing extras/quickcheck/tutes
cvs diff: Diffing extras/references
cvs diff: Diffing extras/references/samples
cvs diff: Diffing extras/references/tests
cvs diff: Diffing extras/solver_types
cvs diff: Diffing extras/solver_types/library
cvs diff: Diffing extras/trailed_update
cvs diff: Diffing extras/trailed_update/samples
cvs diff: Diffing extras/trailed_update/tests
cvs diff: Diffing extras/windows_installer_generator
cvs diff: Diffing extras/windows_installer_generator/sample
cvs diff: Diffing extras/windows_installer_generator/sample/images
cvs diff: Diffing extras/xml
cvs diff: Diffing extras/xml/samples
cvs diff: Diffing extras/xml_stylesheets
cvs diff: Diffing java
cvs diff: Diffing java/runtime
cvs diff: Diffing library
Index: library/map.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.112
diff -u -b -r1.112 map.m
--- library/map.m 31 Jul 2008 06:34:41 -0000 1.112
+++ library/map.m 30 Dec 2008 09:29:32 -0000
@@ -199,12 +199,19 @@
:- func map.from_assoc_list(assoc_list(K, V)) = map(K, V).
:- pred map.from_assoc_list(assoc_list(K, V)::in, map(K, V)::out) is det.
- % Convert a sorted association list to a map.
+ % Convert a sorted association list with no duplicated keys to a map.
%
:- func map.from_sorted_assoc_list(assoc_list(K, V)) = map(K, V).
:- pred map.from_sorted_assoc_list(assoc_list(K, V)::in, map(K, V)::out)
is det.
+ % Convert a reverse sorted association list with no duplicated keys
+ % to a map.
+ %
+:- func map.from_rev_sorted_assoc_list(assoc_list(K, V)) = map(K, V).
+:- pred map.from_rev_sorted_assoc_list(assoc_list(K, V)::in, map(K, V)::out)
+ is det.
+
% Delete a key-value pair from a map.
% If the key is not present, leave the map unchanged.
%
@@ -738,7 +745,10 @@
tree234.assoc_list_to_tree234(L, M).
map.from_sorted_assoc_list(L, M) :-
- tree234.assoc_list_to_tree234(L, M).
+ tree234.from_sorted_assoc_list(L, M).
+
+map.from_rev_sorted_assoc_list(L, M) :-
+ tree234.from_rev_sorted_assoc_list(L, M).
map.delete(Map0, Key, Map) :-
tree234.delete(Map0, Key, Map).
@@ -787,7 +797,8 @@
map.to_assoc_list(M0, ML0),
map.to_assoc_list(M1, ML1),
list.merge(ML0, ML1, ML),
- map.from_sorted_assoc_list(ML, M).
+ % ML may be sorted, but it may contain duplicates.
+ map.from_assoc_list(ML, M).
%-----------------------------------------------------------------------------%
@@ -1103,6 +1114,9 @@
map.from_sorted_assoc_list(AL) = M :-
map.from_sorted_assoc_list(AL, M).
+map.from_rev_sorted_assoc_list(AL) = M :-
+ map.from_rev_sorted_assoc_list(AL, M).
+
map.delete(M1, K) = M2 :-
map.delete(M1, K, M2).
Index: library/tree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/tree234.m,v
retrieving revision 1.62
diff -u -b -r1.62 tree234.m
--- library/tree234.m 8 Aug 2008 05:02:21 -0000 1.62
+++ library/tree234.m 30 Dec 2008 09:28:24 -0000
@@ -1,5 +1,5 @@
%-----------------------------------------------------------------------------%
-% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+% vim: ft=mercury ts=4 sw=4 et
%-----------------------------------------------------------------------------%
% Copyright (C) 1994-1997,1999-2000,2002-2008 The University of Melbourne.
% This file may only be copied under the terms of the GNU Library General
@@ -269,6 +269,20 @@
%
:- func tree234_to_doc(tree234(K, V)) = pretty_printer.doc.
+ % 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 tree234.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 tree234.from_rev_sorted_assoc_list(assoc_list(K, V)::in,
+ tree234(K, V)::out) is det.
+
%------------------------------------------------------------------------------%
%------------------------------------------------------------------------------%
@@ -295,11 +309,16 @@
:- import_module bool.
:- import_module int.
+:- import_module io.
:- import_module pair.
:- import_module require.
+:- import_module set.
+:- import_module string.
:- interface.
+:- import_module maybe.
+
% This should be abstract, but needs to be exported for insts.
%
:- type tree234(K, V)
@@ -334,6 +353,13 @@
:- mode uo_tree234(K, V) == free >> uniq_tree234(K, V).
:- mode uo_tree234 == free >> uniq_tree234(ground, ground).
+ % 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.
%------------------------------------------------------------------------------%
@@ -2866,4 +2892,330 @@
three(K2, V2, K3, V3, T2, T3, T4), LL))).
%-----------------------------------------------------------------------------%
+
+from_sorted_assoc_list(List, Tree) :-
+ list.length(List, Len),
+ ( Len = 0 ->
+ % 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
+ ;
+ find_level(Len, 0, Level, 0, AllThrees),
+ do_from_sorted_assoc_list(Len, List, LeftOver, Level, AllThrees, Tree),
+ require(unify(LeftOver, []), "from_sorted_assoc_list: 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) :-
+ ( Level0 = 1 ->
+ ( Len = 1 ->
+ (
+ !.List = [K1 - V1 | !:List],
+ Tree = two(K1, V1, empty, empty)
+ ;
+ !.List = [],
+ error("do_from_sorted_assoc_list: len 1 nil")
+ )
+ ; Len = 2 ->
+ require(unify(Level0, 1), "Len = 2 but Level != 1"),
+ (
+ !.List = [K1 - V1, K2 - V2 | !:List],
+ Tree = three(K1, V1, K2, V2, empty, empty, empty)
+ ;
+ !.List = [_],
+ error("do_from_sorted_assoc_list: len 2 one")
+ ;
+ !.List = [],
+ error("do_from_sorted_assoc_list: len 2 nil")
+ )
+ ;
+ error("do_from_sorted_assoc_list: level 1, but len not 1 or 2")
+ )
+ ;
+ Level = Level0 - 1,
+ AllThrees = (AllThrees0 - 2) / 3,
+ ( Len > 2 * AllThrees ->
+ BaseSubLen = (Len / 3),
+ Diff = Len - (BaseSubLen * 3),
+ ( Diff = 0 ->
+ % Len = BaseSubLen * 3:
+ % (BaseSubLen) + 1 + (BaseSubLen - 1) + 1 + (BaseSubLen - 1)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen - 1,
+ SubLen3 = BaseSubLen - 1
+ ; Diff = 1 ->
+ % Len = BaseSubLen * 3 + 1:
+ % (BaseSubLen) + 1 + (BaseSubLen) + 1 + (BaseSubLen - 1)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen,
+ SubLen3 = BaseSubLen - 1
+ ;
+ require(unify(Diff, 2),
+ "do_from_sorted_assoc_list: 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.format("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 = [],
+ error("do_from_sorted_assoc_list: tree K1 V1 nil")
+ ),
+ do_from_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
+ SubTree2),
+ (
+ !.List = [K2 - V2 | !:List]
+ ;
+ !.List = [],
+ error("do_from_sorted_assoc_list: 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.format("tree for %d\n", [i(Len)], !IO),
+ io.write(Tree, !IO),
+ io.nl(!IO)
+ )
+ ;
+ BaseSubLen = (Len) / 2,
+ Diff = Len - (BaseSubLen * 2),
+ ( Diff = 0 ->
+ % Len = BaseSubLen * 2:
+ % (BaseSubLen) + 1 + (BaseSubLen - 1)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen - 1
+ ;
+ require(unify(Diff, 1),
+ "do_from_sorted_assoc_list: Diff != 1"),
+ % Len = BaseSubLen * 2 + 1:
+ % (BaseSubLen) + 1 + (BaseSubLen)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen
+ ),
+
+ trace [io(!IO), compile_time(flag("from_sorted_assoc_list"))] (
+ io.format("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 = [],
+ error("do_from_sorted_assoc_list: 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.format("tree for %d\n", [i(Len)], !IO),
+ io.write(Tree, !IO),
+ io.nl(!IO)
+ )
+ )
+ ).
+
+from_rev_sorted_assoc_list(List, Tree) :-
+ list.length(List, Len),
+ ( Len = 0 ->
+ % 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
+ ;
+ find_level(Len, 0, Level, 0, AllThrees),
+ do_from_rev_sorted_assoc_list(Len, List, LeftOver, Level, AllThrees,
+ Tree),
+ require(unify(LeftOver, []), "from_rev_sorted_assoc_list: 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) :-
+ ( Level0 = 1 ->
+ ( Len = 1 ->
+ (
+ !.List = [K1 - V1 | !:List],
+ Tree = two(K1, V1, empty, empty)
+ ;
+ !.List = [],
+ error("do_from_rev_sorted_assoc_list: len 1 nil")
+ )
+ ; Len = 2 ->
+ require(unify(Level0, 1), "Len = 2 but Level != 1"),
+ (
+ !.List = [K2 - V2, K1 - V1 | !:List],
+ Tree = three(K1, V1, K2, V2, empty, empty, empty)
+ ;
+ !.List = [_],
+ error("do_from_rev_sorted_assoc_list: len 2 one")
+ ;
+ !.List = [],
+ error("do_from_rev_sorted_assoc_list: len 2 nil")
+ )
+ ;
+ error("do_from_rev_sorted_assoc_list: level 1, but len not 1 or 2")
+ )
+ ;
+ Level = Level0 - 1,
+ AllThrees = (AllThrees0 - 2) / 3,
+ ( Len > 2 * AllThrees ->
+ BaseSubLen = (Len / 3),
+ Diff = Len - (BaseSubLen * 3),
+ ( Diff = 0 ->
+ % Len = BaseSubLen * 3:
+ % (BaseSubLen) + 1 + (BaseSubLen - 1) + 1 + (BaseSubLen - 1)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen - 1,
+ SubLen3 = BaseSubLen - 1
+ ; Diff = 1 ->
+ % Len = BaseSubLen * 3 + 1:
+ % (BaseSubLen) + 1 + (BaseSubLen) + 1 + (BaseSubLen - 1)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen,
+ SubLen3 = BaseSubLen - 1
+ ;
+ require(unify(Diff, 2),
+ "do_from_rev_sorted_assoc_list: 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.format("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 = [],
+ error("do_from_rev_sorted_assoc_list: tree K2 V2 nil")
+ ),
+ do_from_rev_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
+ SubTree2),
+ (
+ !.List = [K1 - V1 | !:List]
+ ;
+ !.List = [],
+ error("do_from_rev_sorted_assoc_list: 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.format("tree for %d\n", [i(Len)], !IO),
+ io.write(Tree, !IO),
+ io.nl(!IO)
+ )
+ ;
+ BaseSubLen = (Len) / 2,
+ Diff = Len - (BaseSubLen * 2),
+ ( Diff = 0 ->
+ % Len = BaseSubLen * 2:
+ % (BaseSubLen) + 1 + (BaseSubLen - 1)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen - 1
+ ;
+ require(unify(Diff, 1),
+ "from_rev_sorted_assoc_list: 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.format("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 = [],
+ error("do_from_rev_sorted_assoc_list: 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.format("tree for %d\n", [i(Len)], !IO),
+ io.write(Tree, !IO),
+ io.nl(!IO)
+ )
+ )
+ ).
+
+:- pred find_level(int::in, int::in, int::out,
+ int::in, int::out) is det.
+
+find_level(Len, !Level, !AllThrees) :-
+ ( Len =< !.AllThrees ->
+ true
+ ;
+ !:Level = !.Level + 1,
+ !:AllThrees = !.AllThrees * 3 + 2,
+ find_level(Len, !Level, !AllThrees)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+well_formed(Tree, WellFormed) :-
+ depth_levels(Tree, 0, set.init, Depths),
+ ( set.singleton_set(Depths, Depth) ->
+ WellFormed = yes(Depth)
+ ;
+ 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(!.Depths, 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).
+
+%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
cvs diff: Diffing mdbcomp
cvs diff: Diffing profiler
cvs diff: Diffing robdd
cvs diff: Diffing runtime
cvs diff: Diffing runtime/GETOPT
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/standalone_c
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/muz
cvs diff: Diffing samples/rot13
cvs diff: Diffing samples/solutions
cvs diff: Diffing samples/solver_types
cvs diff: Diffing samples/tests
cvs diff: Diffing samples/tests/c_interface
cvs diff: Diffing samples/tests/c_interface/c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/tests/c_interface/mercury_calls_c
cvs diff: Diffing samples/tests/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/tests/c_interface/mercury_calls_fortran
cvs diff: Diffing samples/tests/c_interface/simpler_c_calls_mercury
cvs diff: Diffing samples/tests/c_interface/simpler_cplusplus_calls_mercury
cvs diff: Diffing samples/tests/diff
cvs diff: Diffing samples/tests/muz
cvs diff: Diffing samples/tests/rot13
cvs diff: Diffing samples/tests/solutions
cvs diff: Diffing samples/tests/toplevel
cvs diff: Diffing scripts
cvs diff: Diffing slice
cvs diff: Diffing ssdb
cvs diff: Diffing tests
cvs diff: Diffing tests/analysis
cvs diff: Diffing tests/analysis/ctgc
cvs diff: Diffing tests/analysis/excp
cvs diff: Diffing tests/analysis/ext
cvs diff: Diffing tests/analysis/sharing
cvs diff: Diffing tests/analysis/table
cvs diff: Diffing tests/analysis/trail
cvs diff: Diffing tests/analysis/unused_args
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/debugger
cvs diff: Diffing tests/debugger/declarative
cvs diff: Diffing tests/dppd
cvs diff: Diffing tests/general
cvs diff: Diffing tests/general/accumulator
cvs diff: Diffing tests/general/string_format
cvs diff: Diffing tests/general/structure_reuse
cvs diff: Diffing tests/grade_subdirs
cvs diff: Diffing tests/hard_coded
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.361
diff -u -b -r1.361 Mmakefile
--- tests/hard_coded/Mmakefile 1 Dec 2008 00:32:55 -0000 1.361
+++ tests/hard_coded/Mmakefile 30 Dec 2008 04:57:16 -0000
@@ -226,6 +226,7 @@
target_mlobjs \
term_io_test \
term_to_univ_test \
+ test234_sorted_insert \
test_bitset \
test_cord \
test_imported_no_tag \
Index: tests/hard_coded/test234_sorted_insert.exp
===================================================================
RCS file: tests/hard_coded/test234_sorted_insert.exp
diff -N tests/hard_coded/test234_sorted_insert.exp
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/test234_sorted_insert.exp 30 Dec 2008 04:56:48 -0000
@@ -0,0 +1 @@
+all tests passed
Index: tests/hard_coded/test234_sorted_insert.m
===================================================================
RCS file: tests/hard_coded/test234_sorted_insert.m
diff -N tests/hard_coded/test234_sorted_insert.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/test234_sorted_insert.m 30 Dec 2008 14:12:17 -0000
@@ -0,0 +1,119 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+%
+% This test case tests the tree234 library module's conversion of sorted lists
+% directly to trees.
+%
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- module test234_sorted_insert.
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module assoc_list.
+:- import_module int.
+:- import_module list.
+:- import_module maybe.
+:- import_module pair.
+:- import_module string.
+:- import_module tree234.
+
+main(!IO) :-
+ test_upto(1000, 0, 0, Failed, !IO),
+ ( Failed = 0 ->
+ io.write_string("all tests passed\n", !IO)
+ ;
+ io.format("%d tests failed\n", [i(Failed)], !IO)
+ ).
+
+:- pred test_upto(int::in, int::in, int::in, int::out, io::di, io::uo) is det.
+
+test_upto(Max, Cur, !Failed, !IO) :-
+ ( Cur > Max ->
+ true
+ ;
+ test(Cur, !Failed, !IO),
+ test_upto(Max, Cur + 1, !Failed, !IO)
+ ).
+
+:- pred test(int::in, int::in, int::out, io::di, io::uo) is det.
+
+test(N, !Failed, !IO) :-
+ trace [io(!IO), compile_time(flag("progress"))] (
+ io.format("test %d:\n", [i(N)], !IO)
+ ),
+
+ iota(N, List),
+ tree234.from_sorted_assoc_list(List, Tree),
+
+ trace [io(!IO), compile_time(flag("print_tree"))] (
+ io.format("test %d tree:\n", [i(N)], !IO),
+ io.write(Tree, !IO),
+ io.nl(!IO)
+ ),
+
+ well_formed(Tree, MaybeDepth),
+ tree234_to_assoc_list(Tree, TreeList),
+ list.sort(TreeList, SortedTreeList),
+
+ rev_iota(N, RevList),
+ tree234.from_rev_sorted_assoc_list(RevList, RevTree),
+
+ trace [io(!IO), compile_time(flag("print_tree"))] (
+ io.format("test %d tree:\n", [i(N)], !IO),
+ io.write(RevTree, !IO),
+ io.nl(!IO)
+ ),
+
+ well_formed(RevTree, RevMaybeDepth),
+ tree234_to_assoc_list(RevTree, RevTreeList),
+ list.sort(RevTreeList, RevSortedTreeList),
+
+ (
+ MaybeDepth = yes(_),
+ RevMaybeDepth = yes(_),
+ TreeList = SortedTreeList,
+ RevTreeList = RevSortedTreeList
+ ->
+ true
+ ;
+ !:Failed = !.Failed + 1
+ ),
+
+ trace [io(!IO), compile_time(flag("progress"))] (
+ io.nl(!IO)
+ ).
+
+:- pred iota(int::in, assoc_list(int)::out) is det.
+
+iota(N, List) :-
+ iota_2(N, 1, [], RevList),
+ list.reverse(RevList, List).
+
+:- pred rev_iota(int::in, assoc_list(int)::out) is det.
+
+rev_iota(N, RevList) :-
+ iota_2(N, 1, [], RevList).
+
+:- pred iota_2(int::in, int::in,
+ assoc_list(int, int)::in, assoc_list(int, int)::out) is det.
+
+iota_2(Max, N, !RevList) :-
+ ( N > Max ->
+ true
+ ;
+ !:RevList = [N - N | !.RevList],
+ iota_2(Max, N + 1, !RevList)
+ ).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
cvs diff: Diffing tests/hard_coded/exceptions
cvs diff: Diffing tests/hard_coded/purity
cvs diff: Diffing tests/hard_coded/sub-modules
cvs diff: Diffing tests/hard_coded/typeclasses
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/invalid/purity
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/mmc_make
cvs diff: Diffing tests/mmc_make/lib
cvs diff: Diffing tests/par_conj
cvs diff: Diffing tests/recompilation
cvs diff: Diffing tests/stm
cvs diff: Diffing tests/stm/orig
cvs diff: Diffing tests/stm/orig/stm-compiler
cvs diff: Diffing tests/stm/orig/stm-compiler/test1
cvs diff: Diffing tests/stm/orig/stm-compiler/test10
cvs diff: Diffing tests/stm/orig/stm-compiler/test2
cvs diff: Diffing tests/stm/orig/stm-compiler/test3
cvs diff: Diffing tests/stm/orig/stm-compiler/test4
cvs diff: Diffing tests/stm/orig/stm-compiler/test5
cvs diff: Diffing tests/stm/orig/stm-compiler/test6
cvs diff: Diffing tests/stm/orig/stm-compiler/test7
cvs diff: Diffing tests/stm/orig/stm-compiler/test8
cvs diff: Diffing tests/stm/orig/stm-compiler/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/bm2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/stmqueue
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test10
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test11
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par/test9
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test1
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test2
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test3
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test4
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test5
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test6
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test7
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test8
cvs diff: Diffing tests/stm/orig/stm-compiler-par-asm_fast/test9
cvs diff: Diffing tests/tabling
cvs diff: Diffing tests/term
cvs diff: Diffing tests/trailing
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trace
cvs diff: Diffing util
cvs diff: Diffing vim
cvs diff: Diffing vim/after
cvs diff: Diffing vim/ftplugin
cvs diff: Diffing vim/syntax
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list