[m-rev.] for post-commit review: three speedups
Zoltan Somogyi
zs at unimelb.edu.au
Thu Jun 14 13:32:20 AEST 2012
For post-commit review by anyone.
Zoltan.
This diff makes three main changes to try to speed up the compiler:
- Avoid a double traversal of a map in const_struct.m.
- Speed up that double traversal in const_struct.m when possible.
- Remove any variables eliminated by the conversion of
from_ground_term_construct scopes to const structs from the procedure's
varset and vartypes. Do so in bulk, if that seems to be worthwhile.
These together speed up the compiler by about 7% when compiling
training_cars_full.m. About two-thirds of that is from the first change,
almost a third is from the second, and a tiny bit from the third.
----------------------------
Two of the above changes rely on changes in the library.
library/tree234.m:
Add a new predicate, search_insert(K, V, MaybeOldV, !Tree). If K
is in !.Tree with value OldV, it sets MaybeOldV to yes(OldV) and
leaves !Tree unchanged. If K is not in !.Tree, it inserts it into
!Tree with value V. Basically, it does a search and an insert
in ONE traversal, and is the map equivalent of the insert_new
predicates I added to all the set modules recently.
Put all the predicates in the module into a logical order.
Replace all the calls to error with calls to unexpected. Replace
all the sanity checks that called to require with calls to expect,
and put them inside conditionally-enable trace scopes.
Add a predicate for a quick-and-dirty estimate of the size of a tree.
This is to support delete_sorted_list in map.m.
library/map.m:
Make the new tree234.search_insert predicate accessible in the
map module.
Add a predicate for removing a *sorted* list of elements from a map,
since this is more efficient if we are removing a large fraction
of the map's elements.
library/varset.m:
Implement a predicate that is analogous to the new delete_sorted_list
predicate in map.m, and is implemented using it.
Speed up varset.delete_vars even if the vars aren't sorted.
NEWS:
Note the new predicates.
----------------------------
compiler/const_struct.m:
Use the new capability of map.m to combine two traversals into one.
(Change 1 at the top.)
Divide the csdb_struct_map into two maps, one whose cons_ids are
cons/3, and one for every other cons_id. Make the key of the map
for the cons/3 cons_ids a structure that has its most distinctive
components at the start, to reduce the cost of comparisons in lookups.
(Change 2 at the top.)
----------------------------
compiler/simplify.m:
When converting from_ground_term_construct scopes into constant
structures, remove the eliminated variables from the varset and
vartypes. (Change 3 at the top.)
Restructure the simplify_info and its access predicates, in several
respects:
- Make all accesses to the fields through access predicates,
to allow profiling to count how frequently each is used.
- Instead of including the det_info in the simplify_info, include
its components.
- Separate the simplify_info into a main and a sub info, with the
main one being an 8 word structure containing only the most
frequently accessed fields. Some of these previously required
going through two structures (simplify_info and det_info).
- Eliminate a field that was unused. (We no longer need to recompute
instmap deltas for atomic goals.)
- Eliminate some other unused access predicates (setters for read-only
fields).
- Separate the remaining access predicates from simple wrappers around
them. Put all the access predicates in an order that mirrors the
order of the fields in the simplify_info and sub_simplify_info
structures.
- Give some predicates better names.
compiler/pd_util.m:
compiler/common.m:
Conform to the above changes.
----------------------------
compiler/det_util.m:
Put the arguments of a predicate into a more logical order.
compiler/det_analysis.m:
Give some predicates more meaningful names.
cvs diff: Diffing .
Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.611
diff -u -b -r1.611 NEWS
--- NEWS 5 Jun 2012 18:19:30 -0000 1.611
+++ NEWS 14 Jun 2012 03:28:10 -0000
@@ -13,6 +13,14 @@
the item, otherwise it fails. The other is all_true: it succeeds if
and only if all elements in the set pass a test.
+* The map and varset modules each have a new predicate that deletes
+ a sorted list of items from a map or varset, and can do so faster than
+ usual exploiting the order.
+
+* The map and tree234 modules each have a new predicate that does a search,
+ and if the search is unsuccessful, does an insertion during the *same*
+ traversal.
+
* The argument order of the following predicates has been changed so as to
make them more conducive to the use of state variable notation:
pqueue.insert/4, pqueue.remove/4, stack.push/3, stack.push_list/3,
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/extra
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/extra
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing boehm_gc/libatomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/doc
cvs diff: Diffing boehm_gc/libatomic_ops/src
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/armcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/gcc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/hpc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/ibmc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/icc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/msftc
cvs diff: Diffing boehm_gc/libatomic_ops/src/atomic_ops/sysdeps/sunc
cvs diff: Diffing boehm_gc/libatomic_ops/tests
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/tests
cvs diff: Diffing boehm_gc/m4
cvs diff: Diffing boehm_gc/tests
cvs diff: Diffing browser
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/common.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/common.m,v
retrieving revision 1.118
diff -u -b -r1.118 common.m
--- compiler/common.m 27 Mar 2012 23:21:27 -0000 1.118
+++ compiler/common.m 14 Jun 2012 03:28:10 -0000
@@ -585,7 +585,7 @@
[always(PrevPieces)])]),
Spec = error_spec(Severity, phase_simplify(report_in_any_mode),
[Msg, PrevMsg]),
- simplify_info_do_add_error_spec(Spec, !Info)
+ simplify_info_add_error_spec(Spec, !Info)
;
true
),
Index: compiler/const_struct.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/const_struct.m,v
retrieving revision 1.3
diff -u -b -r1.3 const_struct.m
--- compiler/const_struct.m 11 Jun 2012 03:13:20 -0000 1.3
+++ compiler/const_struct.m 14 Jun 2012 03:28:10 -0000
@@ -34,7 +34,7 @@
% The type and inst of the term.
cs_term_type :: mer_type,
- cs_term_int :: mer_inst
+ cs_term_inst :: mer_inst
).
:- type const_struct_arg
@@ -119,8 +119,11 @@
:- import_module libs.options.
:- import_module libs.trace_params.
+:- import_module mdbcomp.
+:- import_module mdbcomp.prim_data.
:- import_module int.
+:- import_module maybe.
:- import_module pair.
:- import_module require.
@@ -182,33 +185,56 @@
GroundTermEnabled = no
),
Db = const_struct_db(PolyEnabled, GroundTermEnabled, 0,
- map.init, map.init, map.init).
+ map.init, map.init, map.init, map.init).
lookup_insert_const_struct(ConstStruct, ConstNum, !Db) :-
- const_struct_db_get_struct_map(!.Db, StructMap0),
- ( map.search(StructMap0, ConstStruct, ConstNumPrime) ->
- ConstNum = ConstNumPrime
- ;
- % Since we expect many searches to be successful if enabled,
- % we don't test the enabled flag on every search. We just test
- % it on insertions. Without successful insertions, searches
- % cannot succeed, so this is enough.
const_struct_db_get_poly_enabled(!.Db, Enabled),
(
Enabled = no,
unexpected($module, $pred, "not enabled")
;
Enabled = yes,
- const_struct_db_get_next_num(!.Db, ConstNum),
- const_struct_db_set_next_num(ConstNum + 1, !Db),
-
- map.det_insert(ConstStruct, ConstNum, StructMap0, StructMap),
- const_struct_db_set_struct_map(StructMap, !Db),
+ ConstStruct = const_struct(ConsId, Args, Type, Inst),
+ ( ConsId = cons(SymName, _, _) ->
+ Name = unqualify_name(SymName),
+ ConsProxyStruct = cons_proxy_struct(Name, Args, ConsId,
+ Type, Inst),
+ const_struct_db_get_next_num(!.Db, NextConstNum),
+ const_struct_db_get_cons_proxy_map(!.Db, ConsMap0),
+ map.search_insert(ConsProxyStruct, NextConstNum, MaybeOldConstNum,
+ ConsMap0, ConsMap),
+ (
+ MaybeOldConstNum = yes(ConstNum)
+ % ConsMap should be the same as ConsMap0.
+ ;
+ MaybeOldConstNum = no,
+ ConstNum = NextConstNum,
+ const_struct_db_get_num_map(!.Db, NumMap0),
+ map.det_insert(ConstNum, ConstStruct, NumMap0, NumMap),
+ const_struct_db_set_next_num(NextConstNum + 1, !Db),
+ const_struct_db_set_cons_proxy_map(ConsMap, !Db),
+ const_struct_db_set_num_map(NumMap, !Db)
+ )
+ ;
+ const_struct_db_get_next_num(!.Db, NextConstNum),
+ const_struct_db_get_other_struct_map(!.Db, OtherMap0),
+ map.search_insert(ConstStruct, NextConstNum, MaybeOldConstNum,
+ OtherMap0, OtherMap),
+ (
+ MaybeOldConstNum = yes(ConstNum)
+ % OtherMap should be the same as OtherMap0.
+ ;
+ MaybeOldConstNum = no,
+ ConstNum = NextConstNum,
const_struct_db_get_num_map(!.Db, NumMap0),
map.det_insert(ConstNum, ConstStruct, NumMap0, NumMap),
+
+ const_struct_db_set_next_num(NextConstNum + 1, !Db),
+ const_struct_db_set_other_struct_map(OtherMap, !Db),
const_struct_db_set_num_map(NumMap, !Db)
)
+ )
).
lookup_const_struct_num(Db, ConstNum, ConstStruct) :-
@@ -229,9 +255,18 @@
map.det_remove(ConstNum, ConstStruct, NumMap0, NumMap),
const_struct_db_set_num_map(NumMap, !Db),
- const_struct_db_get_struct_map(!.Db, StructMap0),
- map.det_remove(ConstStruct, _ConstNum, StructMap0, StructMap),
- const_struct_db_set_struct_map(StructMap, !Db).
+ ConstStruct = const_struct(ConsId, Args, Type, Inst),
+ ( ConsId = cons(SymName, _, _) ->
+ Name = unqualify_name(SymName),
+ ConsProxyStruct = cons_proxy_struct(Name, Args, ConsId, Type, Inst),
+ const_struct_db_get_cons_proxy_map(!.Db, ConsMap0),
+ map.det_remove(ConsProxyStruct, _ConstNum, ConsMap0, ConsMap),
+ const_struct_db_set_cons_proxy_map(ConsMap, !Db)
+ ;
+ const_struct_db_get_other_struct_map(!.Db, OtherMap0),
+ map.det_remove(ConstStruct, _ConstNum, OtherMap0, OtherMap),
+ const_struct_db_set_other_struct_map(OtherMap, !Db)
+ ).
const_struct_db_get_structs(Db, Structs) :-
const_struct_db_get_num_map(Db, NumMap),
@@ -239,18 +274,37 @@
%-----------------------------------------------------------------------------%
+ % Values of this type contain the same information as values of type
+ % const_struct, but in a form that should allow significantly faster
+ % comparisons, because it copies to the front the data item most useful
+ % for comparisons, the name of the function symbol. If two proxy structs
+ % match on the first two fields, they are almost certain to match
+ % on the other three as well.
+ %
+:- type cons_proxy_struct
+ ---> cons_proxy_struct(
+ cps_name :: string,
+ cps_args :: list(const_struct_arg),
+ cps_cons_id :: cons_id,
+ cps_term_type :: mer_type,
+ cps_term_inst :: mer_inst
+ ).
+
:- type const_struct_db
---> const_struct_db(
csdb_poly_enabled :: bool,
csdb_ground_term_enabled :: bool,
csdb_next_num :: int,
- csdb_struct_map :: map(const_struct, int),
+ csdb_cons_proxy_map :: map(cons_proxy_struct, int),
+ csdb_other_struct_map :: map(const_struct, int),
csdb_num_map :: map(int, const_struct),
csdb_instance_map :: const_instance_map
).
:- pred const_struct_db_get_next_num(const_struct_db::in, int::out) is det.
-:- pred const_struct_db_get_struct_map(const_struct_db::in,
+:- pred const_struct_db_get_cons_proxy_map(const_struct_db::in,
+ map(cons_proxy_struct, int)::out) is det.
+:- pred const_struct_db_get_other_struct_map(const_struct_db::in,
map(const_struct, int)::out) is det.
:- pred const_struct_db_get_num_map(const_struct_db::in,
map(int, const_struct)::out) is det.
@@ -260,13 +314,16 @@
const_struct_db_get_poly_enabled(Db, Db ^ csdb_poly_enabled).
const_struct_db_get_ground_term_enabled(Db, Db ^ csdb_ground_term_enabled).
const_struct_db_get_next_num(Db, Db ^ csdb_next_num).
-const_struct_db_get_struct_map(Db, Db ^ csdb_struct_map).
+const_struct_db_get_cons_proxy_map(Db, Db ^ csdb_cons_proxy_map).
+const_struct_db_get_other_struct_map(Db, Db ^ csdb_other_struct_map).
const_struct_db_get_num_map(Db, Db ^ csdb_num_map).
const_struct_db_get_instance_map(Db, Db ^ csdb_instance_map).
:- pred const_struct_db_set_next_num(int::in,
const_struct_db::in, const_struct_db::out) is det.
-:- pred const_struct_db_set_struct_map(map(const_struct, int)::in,
+:- pred const_struct_db_set_cons_proxy_map(map(cons_proxy_struct, int)::in,
+ const_struct_db::in, const_struct_db::out) is det.
+:- pred const_struct_db_set_other_struct_map(map(const_struct, int)::in,
const_struct_db::in, const_struct_db::out) is det.
:- pred const_struct_db_set_num_map(map(int, const_struct)::in,
const_struct_db::in, const_struct_db::out) is det.
@@ -275,8 +332,10 @@
const_struct_db_set_next_num(Num, !Db) :-
!Db ^ csdb_next_num := Num.
-const_struct_db_set_struct_map(StructMap, !Db) :-
- !Db ^ csdb_struct_map := StructMap.
+const_struct_db_set_cons_proxy_map(ConsMap, !Db) :-
+ !Db ^ csdb_cons_proxy_map := ConsMap.
+const_struct_db_set_other_struct_map(OtherMap, !Db) :-
+ !Db ^ csdb_other_struct_map := OtherMap.
const_struct_db_set_num_map(NumMap, !Db) :-
!Db ^ csdb_num_map := NumMap.
const_struct_db_set_instance_map(InstanceMap, !Db) :-
Index: compiler/det_analysis.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/det_analysis.m,v
retrieving revision 1.238
diff -u -b -r1.238 det_analysis.m
--- compiler/det_analysis.m 24 Apr 2012 09:18:22 -0000 1.238
+++ compiler/det_analysis.m 14 Jun 2012 03:28:10 -0000
@@ -430,7 +430,7 @@
% If a pure or semipure goal has no output variables, then the goal
% is in a single-solution context.
(
- det_no_output_vars(NonLocalVars, InstMap0, InstmapDelta, !.DetInfo),
+ det_no_output_vars(!.DetInfo, InstMap0, InstmapDelta, NonLocalVars),
Purity = goal_info_get_purity(GoalInfo0),
(
Purity = purity_impure
@@ -444,19 +444,18 @@
;
AddPruning = no
),
+ det_infer_goal_known_pruning(Goal0, Goal, InstMap0, !.SolnContext,
+ RightFailingContexts, MaybePromiseEqvSolutionSets, AddPruning,
+ Detism, GoalFailingContexts, !DetInfo).
- det_infer_goal_1(Goal0, Goal, InstMap0, !.SolnContext, RightFailingContexts,
- MaybePromiseEqvSolutionSets, AddPruning, Detism, GoalFailingContexts,
- !DetInfo).
-
-:- pred det_infer_goal_1(hlds_goal::in, hlds_goal::out, instmap::in,
- soln_context::in, list(failing_context)::in, maybe(pess_info)::in,
- bool::in, determinism::out, list(failing_context)::out,
- det_info::in, det_info::out) is det.
+:- pred det_infer_goal_known_pruning(hlds_goal::in, hlds_goal::out,
+ instmap::in, soln_context::in, list(failing_context)::in,
+ maybe(pess_info)::in, bool::in, determinism::out,
+ list(failing_context)::out, det_info::in, det_info::out) is det.
-det_infer_goal_1(Goal0, Goal, InstMap0, !.SolnContext, RightFailingContexts,
- MaybePromiseEqvSolutionSets, AddPruning, Detism, GoalFailingContexts,
- !DetInfo) :-
+det_infer_goal_known_pruning(Goal0, Goal, InstMap0, !.SolnContext,
+ RightFailingContexts, MaybePromiseEqvSolutionSets, AddPruning,
+ Detism, GoalFailingContexts, !DetInfo) :-
Goal0 = hlds_goal(GoalExpr0, GoalInfo0),
InstmapDelta = goal_info_get_instmap_delta(GoalInfo0),
@@ -485,8 +484,8 @@
Prune = AddPruning
),
- det_infer_goal_2(GoalExpr0, GoalExpr1, GoalInfo0, InstMap0, !.SolnContext,
- RightFailingContexts, MaybePromiseEqvSolutionSets,
+ det_infer_goal_expr(GoalExpr0, GoalExpr1, GoalInfo0, InstMap0,
+ !.SolnContext, RightFailingContexts, MaybePromiseEqvSolutionSets,
InternalDetism0, GoalFailingContexts, !DetInfo),
determinism_components(InternalDetism0, InternalCanFail, InternalSolns0),
@@ -593,13 +592,13 @@
%-----------------------------------------------------------------------------%
-:- pred det_infer_goal_2(hlds_goal_expr::in, hlds_goal_expr::out,
+:- pred det_infer_goal_expr(hlds_goal_expr::in, hlds_goal_expr::out,
hlds_goal_info::in, instmap::in, soln_context::in,
list(failing_context)::in, maybe(pess_info)::in,
determinism::out, list(failing_context)::out,
det_info::in, det_info::out) is det.
-det_infer_goal_2(GoalExpr0, GoalExpr, GoalInfo, InstMap0, SolnContext,
+det_infer_goal_expr(GoalExpr0, GoalExpr, GoalInfo, InstMap0, SolnContext,
RightFailingContexts, MaybePromiseEqvSolutionSets, Detism,
GoalFailingContexts, !DetInfo) :-
(
@@ -698,12 +697,12 @@
OrElseGoals, OrElseInners)
;
ShortHand0 = try_goal(MaybeIO, ResultVar, TryGoal0),
- % Don't allow det_infer_goal_1 to insert a commit scope around the
- % code that's standing in place for the code we'll actually create
- % for a try goal.
- det_infer_goal_1(TryGoal0, TryGoal, InstMap0, SolnContext,
- RightFailingContexts, MaybePromiseEqvSolutionSets, no, Detism,
- GoalFailingContexts, !DetInfo),
+ % Don't allow det_infer_goal_known_pruning to insert a commit scope
+ % around the code that is standing in place for the code we will
+ % actually create for a try goal.
+ det_infer_goal_known_pruning(TryGoal0, TryGoal, InstMap0,
+ SolnContext, RightFailingContexts, MaybePromiseEqvSolutionSets,
+ no, Detism, GoalFailingContexts, !DetInfo),
ShortHand = try_goal(MaybeIO, ResultVar, TryGoal)
;
ShortHand0 = bi_implication(_, _),
@@ -1840,12 +1839,13 @@
map.lookup(PredTable, PredId, PredInfo),
pred_info_get_procedures(PredInfo, ProcTable),
map.to_assoc_list(ProcTable, ProcList),
- det_find_matching_non_cc_mode_2(ProcList, ModuleInfo, PredInfo, !ProcId).
+ det_find_matching_non_cc_mode_procs(ProcList, ModuleInfo, PredInfo,
+ !ProcId).
-:- pred det_find_matching_non_cc_mode_2(assoc_list(proc_id, proc_info)::in,
+:- pred det_find_matching_non_cc_mode_procs(assoc_list(proc_id, proc_info)::in,
module_info::in, pred_info::in, proc_id::in, proc_id::out) is semidet.
-det_find_matching_non_cc_mode_2([TestProcId - ProcInfo | Rest],
+det_find_matching_non_cc_mode_procs([TestProcId - ProcInfo | Rest],
ModuleInfo, PredInfo, !ProcId) :-
(
TestProcId \= !.ProcId,
@@ -1856,7 +1856,8 @@
->
!:ProcId = TestProcId
;
- det_find_matching_non_cc_mode_2(Rest, ModuleInfo, PredInfo, !ProcId)
+ det_find_matching_non_cc_mode_procs(Rest, ModuleInfo, PredInfo,
+ !ProcId)
).
%-----------------------------------------------------------------------------%
Index: compiler/det_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/det_util.m,v
retrieving revision 1.56
diff -u -b -r1.56 det_util.m
--- compiler/det_util.m 24 Apr 2012 09:18:23 -0000 1.56
+++ compiler/det_util.m 14 Jun 2012 03:28:10 -0000
@@ -98,8 +98,8 @@
:- pred det_lookup_var_type(module_info::in, proc_info::in, prog_var::in,
hlds_type_defn::out) is semidet.
-:- pred det_no_output_vars(set_of_progvar::in, instmap::in, instmap_delta::in,
- det_info::in) is semidet.
+:- pred det_no_output_vars(det_info::in, instmap::in, instmap_delta::in,
+ set_of_progvar::in) is semidet.
:- pred det_info_add_error_spec(error_spec::in, det_info::in, det_info::out)
is det.
@@ -213,7 +213,7 @@
module_info_get_type_table(ModuleInfo, TypeTable),
search_type_ctor_defn(TypeTable, TypeCtor, TypeDefn).
-det_no_output_vars(Vars, InstMap, InstMapDelta, DetInfo) :-
+det_no_output_vars(DetInfo, InstMap, InstMapDelta, Vars) :-
det_info_get_module_info(DetInfo, ModuleInfo),
VarTypes = DetInfo ^ di_vartypes,
instmap_delta_no_output_vars(ModuleInfo, VarTypes, InstMap, InstMapDelta,
Index: compiler/pd_util.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/pd_util.m,v
retrieving revision 1.88
diff -u -b -r1.88 pd_util.m
--- compiler/pd_util.m 23 Apr 2012 03:34:48 -0000 1.88
+++ compiler/pd_util.m 14 Jun 2012 03:28:10 -0000
@@ -245,13 +245,10 @@
% Construct a simplify_info.
pd_info_get_module_info(!.PDInfo, ModuleInfo0),
pd_info_get_pred_proc_id(!.PDInfo, proc(PredId, ProcId)),
- proc_info_get_vartypes(ProcInfo0, VarTypes0),
- det_info_init(ModuleInfo0, VarTypes0, PredId, ProcId,
- pess_extra_vars_ignore, [], DetInfo0),
- pd_info_get_instmap(!.PDInfo, InstMap0),
pd_info_get_proc_info(!.PDInfo, ProcInfo0),
- simplify_info_init(DetInfo0, Simplifications, InstMap0, ProcInfo0,
- SimplifyInfo0),
+ pd_info_get_instmap(!.PDInfo, InstMap0),
+ simplify_info_init(ModuleInfo0, PredId, ProcId, ProcInfo0,
+ InstMap0, Simplifications, SimplifyInfo0),
simplify_process_clause_body_goal(Goal0, Goal,
SimplifyInfo0, SimplifyInfo),
Index: compiler/simplify.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/compiler/simplify.m,v
retrieving revision 1.279
diff -u -b -r1.279 simplify.m
--- compiler/simplify.m 11 Jun 2012 03:13:21 -0000 1.279
+++ compiler/simplify.m 14 Jun 2012 03:28:10 -0000
@@ -32,7 +32,6 @@
:- interface.
:- import_module check_hlds.common.
-:- import_module check_hlds.det_util.
:- import_module hlds.
:- import_module hlds.hlds_goal.
:- import_module hlds.hlds_module.
@@ -42,6 +41,7 @@
:- import_module libs.
:- import_module libs.globals.
:- import_module parse_tree.error_util.
+:- import_module parse_tree.prog_data.
:- import_module bool.
:- import_module list.
@@ -127,6 +127,7 @@
:- implementation.
:- import_module check_hlds.det_analysis.
+:- import_module check_hlds.det_util.
:- import_module check_hlds.format_call.
:- import_module check_hlds.inst_match.
:- import_module check_hlds.mode_util.
@@ -150,7 +151,6 @@
:- import_module mdbcomp.prim_data.
:- import_module parse_tree.
:- import_module parse_tree.builtin_lib_types.
-:- import_module parse_tree.prog_data.
:- import_module parse_tree.prog_mode.
:- import_module parse_tree.prog_type.
:- import_module parse_tree.prog_type_subst.
@@ -161,6 +161,7 @@
:- import_module transform_hlds.pd_cost.
:- import_module int.
+:- import_module io.
:- import_module map.
:- import_module maybe.
:- import_module pair.
@@ -431,30 +432,34 @@
FormatSpecs = []
),
- proc_info_get_vartypes(!.ProcInfo, VarTypes0),
- det_info_init(!.ModuleInfo, VarTypes0, PredId, ProcId,
- pess_extra_vars_report, [], DetInfo0),
proc_info_get_initial_instmap(!.ProcInfo, !.ModuleInfo, InstMap0),
- simplify_info_init(DetInfo0, Simplifications, InstMap0, !.ProcInfo, Info0),
+ simplify_info_init(!.ModuleInfo, PredId, ProcId, !.ProcInfo,
+ InstMap0, Simplifications, Info0),
proc_info_get_goal(!.ProcInfo, Goal0),
simplify_process_clause_body_goal(Goal0, Goal, Info0, Info),
proc_info_set_goal(Goal, !ProcInfo),
- simplify_info_get_var_types(Info, VarTypes),
- simplify_info_get_rtti_varmaps(Info, RttiVarMaps),
- proc_info_set_vartypes(VarTypes, !ProcInfo),
- proc_info_set_rtti_varmaps(RttiVarMaps, !ProcInfo),
-
simplify_info_get_varset(Info, VarSet0),
+ simplify_info_get_var_types(Info, VarTypes1),
+ simplify_info_get_rtti_varmaps(Info, RttiVarMaps),
+ simplify_info_get_elim_vars(Info, ElimVarsLists0),
+ % We sort the lists basically on the number of the first variable.
+ list.sort(ElimVarsLists0, ElimVarsLists),
+ list.condense(ElimVarsLists, ElimVars),
+ varset.delete_sorted_vars(ElimVars, VarSet0, VarSet1),
+ map.delete_sorted_list(ElimVars, VarTypes1, VarTypes),
+ % We only eliminate vars that cannot occur in RttiVarMaps.
( simplify_do_after_front_end(Info) ->
proc_info_get_var_name_remap(!.ProcInfo, VarNameRemap),
- map.foldl(varset.name_var, VarNameRemap, VarSet0, VarSet),
+ map.foldl(varset.name_var, VarNameRemap, VarSet1, VarSet),
proc_info_set_var_name_remap(map.init, !ProcInfo)
;
VarSet = VarSet0
),
proc_info_set_varset(VarSet, !ProcInfo),
+ proc_info_set_vartypes(VarTypes, !ProcInfo),
+ proc_info_set_rtti_varmaps(RttiVarMaps, !ProcInfo),
simplify_info_get_has_parallel_conj(Info, HasParallelConj),
proc_info_set_has_parallel_conj(HasParallelConj, !ProcInfo),
@@ -718,7 +723,7 @@
% in the instmap_delta for a goal.
% In the alias branch this is necessary anyway.
simplify_info_get_module_info(!.Info, !:ModuleInfo),
- InstVarSet = !.Info ^ simp_inst_varset,
+ simplify_info_get_inst_varset(!.Info, InstVarSet),
recompute_instmap_delta(recompute_atomic_instmap_deltas, !Goal,
!.VarTypes, InstVarSet, InstMap0, !ModuleInfo),
simplify_info_set_module_info(!.ModuleInfo, !Info)
@@ -727,8 +732,7 @@
true
),
( simplify_info_rerun_det(!.Info) ->
- some [!VarSet, !VarTypes, !RttiVarMaps, !ModuleInfo, !ProcInfo,
- !DetInfo]
+ some [!VarSet, !VarTypes, !RttiVarMaps, !ModuleInfo, !ProcInfo]
(
det_get_soln_context(Detism, SolnContext),
@@ -739,9 +743,7 @@
simplify_info_get_varset(!.Info, !:VarSet),
simplify_info_get_var_types(!.Info, !:VarTypes),
simplify_info_get_rtti_varmaps(!.Info, !:RttiVarMaps),
- simplify_info_get_det_info(!.Info, !:DetInfo),
- det_info_get_pred_id(!.DetInfo, PredId),
- det_info_get_proc_id(!.DetInfo, ProcId),
+ simplify_info_get_pred_proc_id(!.Info, PredId, ProcId),
module_info_pred_proc_info(!.ModuleInfo, PredId, ProcId,
PredInfo, !:ProcInfo),
proc_info_set_vartypes(!.VarTypes, !ProcInfo),
@@ -751,10 +753,14 @@
PredInfo, !.ProcInfo, !ModuleInfo),
simplify_info_set_module_info(!.ModuleInfo, !Info),
- simplify_info_get_det_info(!.Info, !:DetInfo),
+ det_info_init(!.ModuleInfo, !.VarTypes, PredId, ProcId,
+ pess_extra_vars_report, [], DetInfo0),
det_infer_goal(!Goal, InstMap0, SolnContext, [], no,
- _, _, !DetInfo),
- simplify_info_set_det_info(!.DetInfo, !Info)
+ _, _, DetInfo0, DetInfo),
+ det_info_get_module_info(DetInfo, !:ModuleInfo),
+ det_info_get_vartypes(DetInfo, !:VarTypes),
+ simplify_info_set_module_info(!.ModuleInfo, !Info),
+ simplify_info_set_var_types(!.VarTypes, !Info)
)
;
true
@@ -781,7 +787,6 @@
Goal0ContainsTrace = contains_no_trace_goal
),
Detism = goal_info_get_determinism(GoalInfo0),
- simplify_info_get_det_info(!.Info, DetInfo),
simplify_info_get_module_info(!.Info, ModuleInfo0),
goal_can_loop_or_throw(Goal0, Goal0CanLoopOrThrow,
ModuleInfo0, ModuleInfo),
@@ -796,7 +801,7 @@
; Purity = purity_semipure
),
Goal0ContainsTrace = contains_no_trace_goal,
- ( det_info_get_fully_strict(DetInfo, no)
+ ( simplify_info_get_fully_strict(!.Info, no)
; Goal0CanLoopOrThrow = cannot_loop_or_throw
)
->
@@ -826,7 +831,7 @@
severity_warning, no),
Spec = error_spec(Severity,
phase_simplify(report_only_if_in_all_modes), [Msg]),
- simplify_info_add_error_spec(Spec, !Info)
+ simplify_info_add_simple_code_spec(Spec, !Info)
;
true
),
@@ -852,13 +857,16 @@
MaxSoln \= at_most_zero,
InstMapDelta = goal_info_get_instmap_delta(GoalInfo0),
NonLocalVars = goal_info_get_nonlocals(GoalInfo0),
+ simplify_info_get_module_info(!.Info, ModuleInfo),
+ simplify_info_get_var_types(!.Info, VarTypes),
simplify_info_get_instmap(!.Info, InstMap0),
- det_no_output_vars(NonLocalVars, InstMap0, InstMapDelta, DetInfo),
+ instmap_delta_no_output_vars(ModuleInfo, VarTypes,
+ InstMap0, InstMapDelta, NonLocalVars),
( Purity = purity_pure
; Purity = purity_semipure
),
Goal0ContainsTrace = contains_no_trace_goal,
- ( det_info_get_fully_strict(DetInfo, no)
+ ( simplify_info_get_fully_strict(!.Info, no)
; Goal0CanLoopOrThrow = cannot_loop_or_throw
)
->
@@ -893,7 +901,7 @@
% ->
% Msg = det_goal_has_no_outputs,
% ContextMsg = context_det_msg(Context, Msg),
-% simplify_info_add_error_spec(ContextMsg, !Info)
+% simplify_info_add_simple_code_spec(ContextMsg, !Info)
% ;
% true
% ),
@@ -1501,7 +1509,7 @@
severity_warning, no),
Spec = error_spec(Severity,
phase_simplify(report_only_if_in_all_modes), [Msg]),
- simplify_info_add_error_spec(Spec, !Info)
+ simplify_info_add_simple_code_spec(Spec, !Info)
),
simplify_info_set_requantify(!Info),
simplify_info_set_rerun_det(!Info)
@@ -1565,7 +1573,7 @@
severity_warning, no),
Spec = error_spec(Severity,
phase_simplify(report_only_if_in_all_modes), [Msg]),
- simplify_info_add_error_spec(Spec, !Info)
+ simplify_info_add_simple_code_spec(Spec, !Info)
),
simplify_info_set_requantify(!Info),
simplify_info_set_rerun_det(!Info)
@@ -1652,7 +1660,7 @@
(
CanSwitch = cond_can_switch_on(SwitchVar),
Context = goal_info_get_context(CondInfo),
- VarSet = !.Info ^ simp_varset,
+ simplify_info_get_varset(!.Info, VarSet),
Pieces0 = [words("Warning: this if-then-else"),
words("could be replaced by a switch")],
( varset.search_name(VarSet, SwitchVar, SwitchVarName) ->
@@ -1668,7 +1676,7 @@
yes, severity_informational, no),
Spec = error_spec(Severity, phase_simplify(report_in_any_mode),
[Msg]),
- simplify_info_add_error_spec(Spec, !Info)
+ simplify_info_add_simple_code_spec(Spec, !Info)
;
CanSwitch = cond_can_switch_uncommitted
;
@@ -1868,7 +1876,7 @@
severity_warning, no),
Spec = error_spec(Severity,
phase_simplify(report_only_if_in_all_modes), [Msg]),
- simplify_info_add_error_spec(Spec, !Info)
+ simplify_info_add_simple_code_spec(Spec, !Info)
; MaxSoln = at_most_zero ->
Pieces = [words("Warning: the negated goal cannot succeed.")],
Msg = simple_msg(Context,
@@ -1877,7 +1885,7 @@
severity_warning, no),
Spec = error_spec(Severity,
phase_simplify(report_only_if_in_all_modes), [Msg]),
- simplify_info_add_error_spec(Spec, !Info)
+ simplify_info_add_simple_code_spec(Spec, !Info)
;
true
),
@@ -1929,8 +1937,8 @@
% Traversing the construction unifications inside the scope
% would allow common.m to
%
- % - replace some of those constructions with references to other
- % variables that were constructed the same way, and
+ % - replace some of those constructions with references to
+ % other variables that were constructed the same way, and
% - remember those constructions, so that other constructions
% outside the scope could be replaced with references to
% variables built inside the scope.
@@ -1977,18 +1985,12 @@
"from_ground_term_construct scope is not conjunction")
),
simplify_info_get_var_types(!.Info, VarTypes),
- % XXX We could record _ElimVars in !Info as being eliminated.
- % When we have finished simplifying the code of a procedure,
- % we could delete all the eliminated vars from the varset
- % and the vartypes. This would speed up all future lookups.
- % However, it is not (yet) clear whether the savings on those
- % lookups would pay for cost of the deletions themselves,
- % as well as the cost of having an extra field in !Info.
simplify_construct_ground_terms(TermVar, VarTypes,
- HeadConjunct, TailConjuncts, [], _ElimVars,
+ HeadConjunct, TailConjuncts, [], ElimVars,
map.init, VarArgMap, ConstStructDb0, ConstStructDb),
module_info_set_const_struct_db(ConstStructDb,
ModuleInfo0, ModuleInfo),
+ simplify_info_add_elim_vars(ElimVars, !Info),
simplify_info_set_module_info(ModuleInfo, !Info),
map.to_assoc_list(VarArgMap, VarArgs),
@@ -2426,9 +2428,9 @@
inequality_goal(TI, X, Y, Inequality, Invert, GoalInfo, GoalExpr, GoalInfo,
!Info) :-
% Construct the variable to hold the comparison result.
- VarSet0 = !.Info ^ simp_varset,
+ simplify_info_get_varset(!.Info, VarSet0),
varset.new_var(R, VarSet0, VarSet),
- !Info ^ simp_varset := VarSet,
+ simplify_info_set_varset(VarSet, !Info),
% We have to add the type of R to the var_types.
simplify_info_get_var_types(!.Info, VarTypes0),
@@ -2508,12 +2510,10 @@
pred_info_get_markers(PredInfo, Markers),
check_marker(Markers, marker_obsolete),
- simplify_info_get_det_info(!.Info, DetInfo0),
- det_info_get_pred_id(DetInfo0, ThisPredId),
-
% Don't warn about directly recursive calls. (That would cause
% spurious warnings, particularly with builtin predicates,
% or preds defined using foreign_procs.)
+ simplify_info_get_pred_proc_id(!.Info, ThisPredId, _),
PredId \= ThisPredId,
% Don't warn about calls from predicates that also have a
@@ -2535,7 +2535,7 @@
severity_warning, no),
ObsoleteSpec = error_spec(ObsoleteSeverity,
phase_simplify(report_in_any_mode), [ObsoleteMsg]),
- simplify_info_add_error_spec(ObsoleteSpec, !Info)
+ simplify_info_add_simple_code_spec(ObsoleteSpec, !Info)
;
true
),
@@ -2547,9 +2547,7 @@
% Is this a (directly) recursive call, i.e. is the procedure being
% called the same as the procedure we're analyzing?
- simplify_info_get_det_info(!.Info, DetInfo),
- det_info_get_pred_id(DetInfo, PredId),
- det_info_get_proc_id(DetInfo, ProcId),
+ simplify_info_get_pred_proc_id(!.Info, PredId, ProcId),
% Don't count inline builtins. (The compiler generates code for
% builtins that looks recursive, so that you can take their address,
@@ -2621,7 +2619,7 @@
severity_warning, no),
InfiniteRecSpec = error_spec(InfiniteRecSeverity,
phase_simplify(report_in_any_mode), [InfiniteRecMsg]),
- simplify_info_add_error_spec(InfiniteRecSpec, !Info)
+ simplify_info_add_simple_code_spec(InfiniteRecSpec, !Info)
;
true
),
@@ -3109,13 +3107,11 @@
make_type_info_vars(Types, TypeInfoVars, TypeInfoGoals, !Info) :-
% Extract the information from simplify_info.
- simplify_info_get_det_info(!.Info, DetInfo0),
simplify_info_get_varset(!.Info, VarSet0),
simplify_info_get_var_types(!.Info, VarTypes0),
simplify_info_get_rtti_varmaps(!.Info, RttiVarMaps0),
- det_info_get_module_info(DetInfo0, ModuleInfo0),
- det_info_get_pred_id(DetInfo0, PredId),
- det_info_get_proc_id(DetInfo0, ProcId),
+ simplify_info_get_module_info(!.Info, ModuleInfo0),
+ simplify_info_get_pred_proc_id(!.Info, PredId, ProcId),
some [!PredInfo, !ProcInfo, !PolyInfo] (
% The varset, vartypes and rtti_varmaps get updated by the call to
@@ -3695,7 +3691,7 @@
severity_warning, no),
Spec = error_spec(Severity,
phase_simplify(report_only_if_in_all_modes), [Msg]),
- simplify_info_add_error_spec(Spec, !Info)
+ simplify_info_add_simple_code_spec(Spec, !Info)
;
true
),
@@ -3707,8 +3703,7 @@
;
% Only remove disjuncts that might loop
% or call error/1 if --no-fully-strict.
- simplify_info_get_det_info(!.Info, DetInfo),
- det_info_get_fully_strict(DetInfo, no)
+ simplify_info_get_fully_strict(!.Info, no)
)
->
RevGoals1 = RevGoals0
@@ -3961,275 +3956,13 @@
case_list_contains_trace(Cases0, Cases, !ContainsTrace).
%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
-:- type simplify_info
- ---> simplify_info(
- simp_det_info :: det_info,
- simp_error_specs :: list(error_spec),
- simp_simplifications :: simplifications,
-
- % Info about common subexpressions.
- simp_common_info :: common_info,
-
- simp_instmap :: instmap,
- simp_varset :: prog_varset,
- simp_inst_varset :: inst_varset,
-
- % Does the goal need requantification?
- simp_requantify :: bool,
-
- % Do we need to recompute instmap_deltas for atomic goals?
- simp_recompute_atomic :: bool,
-
- % Does determinism analysis need to be rerun?
- simp_rerun_det :: bool,
-
- % Measure of the improvement in the goal from simplification.
- simp_cost_delta :: int,
-
- % Count of the number of lambdas which enclose
- % the current goal.
- simp_lambdas :: int,
-
- % Information about type_infos and typeclass_infos.
- simp_rtti_varmaps :: rtti_varmaps,
-
- % Are we currently inside a goal that was duplicated
- % for a switch?
- simp_inside_dupl_for_switch :: bool,
-
- % Have we seen a parallel conjunction?
- simp_has_parallel_conj :: bool,
-
- % Have we seen a goal with a feature that says it contains
- % a trace goal?
- simp_found_contains_trace :: bool,
-
- % Have we seen an event call?
- simp_has_user_event :: bool
- ).
-
-simplify_info_init(DetInfo, Simplifications, InstMap, ProcInfo, Info) :-
- proc_info_get_varset(ProcInfo, VarSet),
- proc_info_get_inst_varset(ProcInfo, InstVarSet),
- proc_info_get_rtti_varmaps(ProcInfo, RttiVarMaps),
- Info = simplify_info(DetInfo, [], Simplifications,
- common_info_init, InstMap, VarSet, InstVarSet,
- no, no, no, 0, 0, RttiVarMaps, no, no, no, no).
-
- % Reinitialise the simplify_info before reprocessing a goal.
- %
-:- pred simplify_info_reinit(simplifications::in, instmap::in,
- simplify_info::in, simplify_info::out) is det.
-
-simplify_info_reinit(Simplifications, InstMap0, !Info) :-
- !Info ^ simp_simplifications := Simplifications,
- !Info ^ simp_common_info := common_info_init,
- !Info ^ simp_instmap := InstMap0,
- !Info ^ simp_requantify := no,
- !Info ^ simp_recompute_atomic := no,
- !Info ^ simp_rerun_det := no,
- !Info ^ simp_lambdas := 0,
- !Info ^ simp_has_parallel_conj := no,
- !Info ^ simp_has_user_event := no.
-
- % exported for common.m
:- interface.
-
-:- import_module parse_tree.prog_data.
-
-:- pred simplify_info_init(det_info::in, simplifications::in,
- instmap::in, proc_info::in, simplify_info::out) is det.
-
-:- pred simplify_info_get_det_info(simplify_info::in, det_info::out) is det.
-:- pred simplify_info_get_error_specs(simplify_info::in, list(error_spec)::out)
- is det.
-:- pred simplify_info_get_simplifications(simplify_info::in,
- simplifications::out) is det.
-:- pred simplify_info_get_common_info(simplify_info::in, common_info::out)
- is det.
-:- pred simplify_info_get_instmap(simplify_info::in, instmap::out) is det.
-:- pred simplify_info_get_varset(simplify_info::in, prog_varset::out) is det.
-:- pred simplify_info_get_var_types(simplify_info::in, vartypes::out) is det.
-:- pred simplify_info_requantify(simplify_info::in) is semidet.
-:- pred simplify_info_recompute_atomic(simplify_info::in) is semidet.
-:- pred simplify_info_rerun_det(simplify_info::in) is semidet.
-:- pred simplify_info_get_cost_delta(simplify_info::in, int::out) is det.
-:- pred simplify_info_get_rtti_varmaps(simplify_info::in, rtti_varmaps::out)
- is det.
-
-:- pred simplify_info_get_module_info(simplify_info::in, module_info::out)
- is det.
-:- pred simplify_info_get_pred_proc_info(simplify_info::in, pred_info::out,
- proc_info::out) is det.
-
-:- pred simplify_info_set_common_info(common_info::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_requantify(
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_rerun_det(
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_rtti_varmaps(rtti_varmaps::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_do_add_error_spec(error_spec::in,
- simplify_info::in, simplify_info::out) is det.
-
-:- pred simplify_info_incr_cost_delta(int::in,
- simplify_info::in, simplify_info::out) is det.
-
:- pred simplify_info_apply_substitutions_and_duplicate(prog_var::in,
prog_var::in, tsubst::in, simplify_info::in, simplify_info::out) is det.
-
:- implementation.
-:- pred simplify_info_get_inside_duplicated_for_switch(simplify_info::in,
- bool::out) is det.
-:- pred simplify_info_get_has_parallel_conj(simplify_info::in, bool::out)
- is det.
-:- pred simplify_info_get_found_contains_trace(simplify_info::in, bool::out)
- is det.
-:- pred simplify_info_get_has_user_event(simplify_info::in, bool::out) is det.
-
-simplify_info_get_det_info(Info, Info ^ simp_det_info).
-simplify_info_get_error_specs(Info, Info ^ simp_error_specs).
-simplify_info_get_simplifications(Info, Info ^ simp_simplifications).
-simplify_info_get_common_info(Info, Info ^ simp_common_info).
-simplify_info_get_instmap(Info, Info ^ simp_instmap).
-simplify_info_get_varset(Info, Info ^ simp_varset).
-simplify_info_get_var_types(Info, VarTypes) :-
- det_info_get_vartypes(Info ^ simp_det_info, VarTypes).
-simplify_info_requantify(Info) :-
- Info ^ simp_requantify = yes.
-simplify_info_recompute_atomic(Info) :-
- Info ^ simp_recompute_atomic = yes.
-simplify_info_rerun_det(Info) :-
- Info ^ simp_rerun_det = yes.
-simplify_info_get_cost_delta(Info, Info ^ simp_cost_delta).
-simplify_info_get_rtti_varmaps(Info, Info ^ simp_rtti_varmaps).
-simplify_info_get_inside_duplicated_for_switch(Info,
- Info ^ simp_inside_dupl_for_switch).
-simplify_info_get_has_parallel_conj(Info, Info ^ simp_has_parallel_conj).
-simplify_info_get_found_contains_trace(Info, Info ^ simp_found_contains_trace).
-simplify_info_get_has_user_event(Info, Info ^ simp_has_user_event).
-
-simplify_info_get_module_info(Info, ModuleInfo) :-
- simplify_info_get_det_info(Info, DetInfo),
- det_info_get_module_info(DetInfo, ModuleInfo).
-
-simplify_info_get_pred_proc_info(Info, PredInfo, ProcInfo) :-
- simplify_info_get_det_info(Info, DetInfo),
- det_info_get_module_info(DetInfo, ModuleInfo),
- det_info_get_pred_id(DetInfo, PredId),
- det_info_get_proc_id(DetInfo, ProcId),
- module_info_pred_info(ModuleInfo, PredId, PredInfo),
- module_info_proc_info(ModuleInfo, PredId, ProcId, ProcInfo).
-
-:- pred simplify_info_set_det_info(det_info::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_error_specs(list(error_spec)::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_simplifications(simplifications::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_instmap(instmap::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_varset(prog_varset::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_var_types(vartypes::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_recompute_atomic(
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_inside_duplicated_for_switch(bool::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_has_parallel_conj(bool::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_found_contains_trace(bool::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_has_user_event(bool::in,
- simplify_info::in, simplify_info::out) is det.
-
-:- pred simplify_info_add_error_spec(error_spec::in,
- simplify_info::in, simplify_info::out) is det.
-:- pred simplify_info_set_cost_delta(int::in,
- simplify_info::in, simplify_info::out) is det.
-
-:- pred simplify_info_enter_lambda(simplify_info::in, simplify_info::out)
- is det.
-:- pred simplify_info_leave_lambda(simplify_info::in, simplify_info::out)
- is det.
-:- pred simplify_info_inside_lambda(simplify_info::in) is semidet.
-
-:- pred simplify_info_set_module_info(module_info::in,
- simplify_info::in, simplify_info::out) is det.
-
-simplify_info_set_det_info(Det, !Info) :-
- !Info ^ simp_det_info := Det.
-simplify_info_set_error_specs(Specs, !Info) :-
- !Info ^ simp_error_specs := Specs.
-simplify_info_set_simplifications(Simp, !Info) :-
- !Info ^ simp_simplifications := Simp.
-simplify_info_set_instmap(InstMap, !Info) :-
- !Info ^ simp_instmap := InstMap.
-simplify_info_set_common_info(Common, !Info) :-
- !Info ^ simp_common_info := Common.
-simplify_info_set_varset(VarSet, !Info) :-
- !Info ^ simp_varset := VarSet.
-simplify_info_set_var_types(VarTypes, !Info) :-
- DetInfo0 = !.Info ^ simp_det_info,
- det_info_set_vartypes(VarTypes, DetInfo0, DetInfo),
- !Info ^ simp_det_info := DetInfo.
-simplify_info_set_requantify(!Info) :-
- !Info ^ simp_requantify := yes.
-simplify_info_set_recompute_atomic(!Info) :-
- !Info ^ simp_recompute_atomic := yes.
-simplify_info_set_rerun_det(!Info) :-
- !Info ^ simp_rerun_det := yes.
-simplify_info_set_cost_delta(Delta, !Info) :-
- !Info ^ simp_cost_delta := Delta.
-simplify_info_set_rtti_varmaps(Rtti, !Info) :-
- !Info ^ simp_rtti_varmaps := Rtti.
-simplify_info_set_inside_duplicated_for_switch(IDFS, !Info) :-
- !Info ^ simp_inside_dupl_for_switch := IDFS.
-simplify_info_set_has_parallel_conj(MHPC, !Info) :-
- !Info ^ simp_has_parallel_conj := MHPC.
-simplify_info_set_found_contains_trace(FCT, !Info) :-
- !Info ^ simp_found_contains_trace := FCT.
-simplify_info_set_has_user_event(HUE, !Info) :-
- !Info ^ simp_has_user_event := HUE.
-
-simplify_info_incr_cost_delta(Incr, !Info) :-
- !Info ^ simp_cost_delta := !.Info ^ simp_cost_delta + Incr.
-
-simplify_info_add_error_spec(Spec, !Info) :-
- ( simplify_do_warn_simple_code(!.Info) ->
- simplify_info_do_add_error_spec(Spec, !Info)
- ;
- true
- ).
-
-simplify_info_do_add_error_spec(Spec, !Info) :-
- simplify_info_get_error_specs(!.Info, Specs0),
- Specs = [Spec | Specs0],
- simplify_info_set_error_specs(Specs, !Info).
-
-simplify_info_enter_lambda(!Info) :-
- !Info ^ simp_lambdas := !.Info ^ simp_lambdas + 1.
-
-simplify_info_leave_lambda(!Info) :-
- LambdaCount = !.Info ^ simp_lambdas - 1,
- ( LambdaCount >= 0 ->
- !Info ^ simp_lambdas := LambdaCount
- ;
- unexpected($module, $pred, "left too many lambdas")
- ).
-
-simplify_info_inside_lambda(Info) :-
- Info ^ simp_lambdas > 0.
-
-simplify_info_set_module_info(ModuleInfo, !Info) :-
- simplify_info_get_det_info(!.Info, DetInfo0),
- det_info_set_module_info(ModuleInfo, DetInfo0, DetInfo),
- simplify_info_set_det_info(DetInfo, !Info).
-
simplify_info_apply_substitutions_and_duplicate(ToVar, FromVar, TSubst,
!Info) :-
simplify_info_get_var_types(!.Info, VarTypes0),
@@ -4242,11 +3975,42 @@
simplify_info_set_var_types(VarTypes, !Info),
simplify_info_set_rtti_varmaps(RttiVarMaps, !Info).
+%-----------------------------------------------------------------------------%
+
:- pred simplify_info_update_instmap(hlds_goal::in,
simplify_info::in, simplify_info::out) is det.
-simplify_info_update_instmap(Goal, Info, Info ^ simp_instmap := InstMap) :-
- update_instmap(Goal, Info ^ simp_instmap, InstMap).
+simplify_info_update_instmap(Goal, !Info) :-
+ simplify_info_get_instmap(!.Info, InstMap0),
+ update_instmap(Goal, InstMap0, InstMap),
+ simplify_info_set_instmap(InstMap, !Info).
+
+%-----------------------------------------------------------------------------%
+
+ % Reset the instmap and seen calls for the next branch.
+ %
+:- pred simplify_info_post_branch_update(simplify_info::in, simplify_info::in,
+ simplify_info::out) is det.
+
+simplify_info_post_branch_update(PreBranchInfo, PostBranchInfo0, Info) :-
+ simplify_info_get_instmap(PreBranchInfo, InstMap),
+ simplify_info_set_instmap(InstMap, PostBranchInfo0, PostBranchInfo1),
+ simplify_info_get_common_info(PreBranchInfo, Common),
+ simplify_info_set_common_info(Common, PostBranchInfo1, Info).
+
+ % Undo updates to the simplify_info before redoing simplification
+ % on a goal.
+ %
+:- pred simplify_info_undo_goal_updates(simplify_info::in, simplify_info::in,
+ simplify_info::out) is det.
+
+simplify_info_undo_goal_updates(Info0, !Info) :-
+ simplify_info_get_common_info(Info0, CommonInfo0),
+ simplify_info_set_common_info(CommonInfo0, !Info),
+ simplify_info_get_instmap(Info0, InstMap),
+ simplify_info_set_instmap(InstMap, !Info).
+
+%-----------------------------------------------------------------------------%
:- type before_after
---> before
@@ -4375,28 +4139,364 @@
unexpected($module, $pred, "bi_implication")
).
- % Reset the instmap and seen calls for the next branch.
- %
-:- pred simplify_info_post_branch_update(simplify_info::in, simplify_info::in,
- simplify_info::out) is det.
+%-----------------------------------------------------------------------------%
-simplify_info_post_branch_update(PreBranchInfo, PostBranchInfo0, Info) :-
- simplify_info_get_instmap(PreBranchInfo, InstMap),
- simplify_info_set_instmap(InstMap, PostBranchInfo0, PostBranchInfo1),
- simplify_info_get_common_info(PreBranchInfo, Common),
- simplify_info_set_common_info(Common, PostBranchInfo1, Info).
+:- pred simplify_info_get_pred_proc_id(simplify_info::in,
+ pred_id::out, proc_id::out) is det.
- % Undo updates to the simplify_info before redoing simplification
- % on a goal.
+:- pred simplify_info_get_pred_proc_info(simplify_info::in, pred_info::out,
+ proc_info::out) is det.
+
+simplify_info_get_pred_proc_id(Info, PredId, ProcId) :-
+ SubInfo = Info ^ simp_sub_info,
+ PredId = SubInfo ^ ssimp_pred_id,
+ ProcId = SubInfo ^ ssimp_proc_id.
+
+simplify_info_get_pred_proc_info(Info, PredInfo, ProcInfo) :-
+ simplify_info_get_module_info(Info, ModuleInfo),
+ simplify_info_get_pred_proc_id(Info, PredId, ProcId),
+ module_info_pred_proc_info(ModuleInfo, PredId, ProcId, PredInfo, ProcInfo).
+
+%-----------------------------------------------------------------------------%
+
+:- pred simplify_info_add_elim_vars(list(prog_var)::in,
+ simplify_info::in, simplify_info::out) is det.
+
+simplify_info_add_elim_vars(ElimVars, !Info) :-
+ simplify_info_get_elim_vars(!.Info, ElimVarsLists0),
+ ElimVarsLists = [ElimVars | ElimVarsLists0],
+ simplify_info_set_elim_vars(ElimVarsLists, !Info).
+
+%-----------------------------------------------------------------------------%
+
+:- interface.
+:- pred simplify_info_add_error_spec(error_spec::in,
+ simplify_info::in, simplify_info::out) is det.
+:- implementation.
+
+simplify_info_add_error_spec(Spec, !Info) :-
+ simplify_info_get_error_specs(!.Info, Specs0),
+ Specs = [Spec | Specs0],
+ simplify_info_set_error_specs(Specs, !Info).
+
+:- pred simplify_info_add_simple_code_spec(error_spec::in,
+ simplify_info::in, simplify_info::out) is det.
+
+simplify_info_add_simple_code_spec(Spec, !Info) :-
+ ( simplify_do_warn_simple_code(!.Info) ->
+ simplify_info_add_error_spec(Spec, !Info)
+ ;
+ true
+ ).
+
+%-----------------------------------------------------------------------------%
+
+:- interface.
+:- pred simplify_info_requantify(simplify_info::in) is semidet.
+:- pred simplify_info_rerun_det(simplify_info::in) is semidet.
+:- implementation.
+
+simplify_info_requantify(Info) :-
+ Info ^ simp_sub_info ^ ssimp_requantify = yes.
+simplify_info_rerun_det(Info) :-
+ Info ^ simp_sub_info ^ ssimp_rerun_det = yes.
+
+%-----------------------------------------------------------------------------%
+
+:- interface.
+:- pred simplify_info_incr_cost_delta(int::in,
+ simplify_info::in, simplify_info::out) is det.
+:- implementation.
+
+simplify_info_incr_cost_delta(Incr, !Info) :-
+ simplify_info_get_cost_delta(!.Info, CostDelta0),
+ CostDelta = CostDelta0 + Incr,
+ simplify_info_set_cost_delta(CostDelta, !Info).
+
+%-----------------------------------------------------------------------------%
+
+:- pred simplify_info_enter_lambda(simplify_info::in, simplify_info::out)
+ is det.
+:- pred simplify_info_leave_lambda(simplify_info::in, simplify_info::out)
+ is det.
+:- pred simplify_info_inside_lambda(simplify_info::in) is semidet.
+
+simplify_info_enter_lambda(!Info) :-
+ simplify_info_get_lambdas(!.Info, Lambdas0),
+ Lambdas = Lambdas0 + 1,
+ simplify_info_set_lambdas(Lambdas, !Info).
+
+simplify_info_leave_lambda(!Info) :-
+ simplify_info_get_lambdas(!.Info, Lambdas0),
+ Lambdas = Lambdas0 - 1,
+ ( Lambdas >= 0 ->
+ simplify_info_set_lambdas(Lambdas, !Info)
+ ;
+ unexpected($module, $pred, "left too many lambdas")
+ ).
+
+simplify_info_inside_lambda(Info) :-
+ simplify_info_get_lambdas(Info, Lambdas),
+ Lambdas > 0.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- type simplify_info
+ ---> simplify_info(
+ % The eight most frequently used fields.
+
+ % The tasks we do in this invocation of simplification.
+/* 1 */ simp_simplifications :: simplifications,
+
+ % The whole module. Those parts of it that are also contained
+ % in other fields of simplify_info and simplify_sub_info
+ % may be out of date in the module_info.
+/* 2 */ simp_module_info :: module_info,
+
+ % The types of the variables in the procedure being simplified.
+/* 3 */ simp_vartypes :: vartypes,
+
+ % The instmap at the current point in the procedure.
+/* 4 */ simp_instmap :: instmap,
+
+ % Are we currently inside a goal that was duplicated
+ % for a switch?
+/* 5 */ simp_inside_dupl_for_switch :: bool,
+
+ % The value of the --fully-strict option.
+/* 6 */ simp_fully_strict :: bool,
+
+ % Info about common subexpressions.
+/* 7 */ simp_common_info :: common_info,
+
+/* 8 */ simp_sub_info :: simplify_sub_info
+ ).
+
+:- type simplify_sub_info
+ ---> simplify_sub_info(
+ % The id of the procedure we are simplifying, and some of the
+ % fields of its proc_infos.
+ ssimp_pred_id :: pred_id,
+ ssimp_proc_id :: proc_id,
+ ssimp_varset :: prog_varset,
+ ssimp_inst_varset :: inst_varset,
+ ssimp_rtti_varmaps :: rtti_varmaps,
+
+ % The variables we have eliminated. Each list of vars consists
+ % of a list of consecutive variable numbers in ascending order.
+ % The relative order of the lists is unknown.
+ ssimp_elim_vars :: list(list(prog_var)),
+
+ ssimp_error_specs :: list(error_spec),
+
+ % Does the goal need requantification?
+ ssimp_requantify :: bool,
+
+ % Does determinism analysis need to be rerun?
+ ssimp_rerun_det :: bool,
+
+ % Measure of the improvement in the goal from simplification.
+ ssimp_cost_delta :: int,
+
+ % Count of the number of lambdas which enclose
+ % the current goal.
+ ssimp_lambdas :: int,
+
+ % Have we seen a parallel conjunction?
+ ssimp_has_parallel_conj :: bool,
+
+ % Have we seen a goal with a feature that says it contains
+ % a trace goal?
+ ssimp_found_contains_trace :: bool,
+
+ % Have we seen an event call?
+ ssimp_has_user_event :: bool
+ ).
+
+:- interface.
+:- pred simplify_info_init(module_info::in, pred_id::in, proc_id::in,
+ proc_info::in, instmap::in, simplifications::in, simplify_info::out)
+ is det.
+:- implementation.
+
+simplify_info_init(ModuleInfo, PredId, ProcId, ProcInfo, InstMap,
+ Simplifications, Info) :-
+ module_info_get_globals(ModuleInfo, Globals),
+ globals.lookup_bool_option(Globals, fully_strict, FullyStrict),
+ proc_info_get_varset(ProcInfo, VarSet),
+ proc_info_get_vartypes(ProcInfo, VarTypes),
+ proc_info_get_inst_varset(ProcInfo, InstVarSet),
+ proc_info_get_rtti_varmaps(ProcInfo, RttiVarMaps),
+ SubInfo = simplify_sub_info(PredId, ProcId, VarSet, InstVarSet,
+ RttiVarMaps, [], [], no, no, 0, 0, no, no, no),
+ Info = simplify_info(Simplifications, ModuleInfo, VarTypes, InstMap, no,
+ FullyStrict, common_info_init, SubInfo).
+
+ % Reinitialise the simplify_info before reprocessing a goal.
%
-:- pred simplify_info_undo_goal_updates(simplify_info::in, simplify_info::in,
- simplify_info::out) is det.
+:- pred simplify_info_reinit(simplifications::in, instmap::in,
+ simplify_info::in, simplify_info::out) is det.
-simplify_info_undo_goal_updates(Info0, !Info) :-
- simplify_info_get_common_info(Info0, CommonInfo0),
- simplify_info_set_common_info(CommonInfo0, !Info),
- simplify_info_get_instmap(Info0, InstMap),
- simplify_info_set_instmap(InstMap, !Info).
+simplify_info_reinit(Simplifications, InstMap0, !Info) :-
+ !Info ^ simp_simplifications := Simplifications,
+ !Info ^ simp_common_info := common_info_init,
+ !Info ^ simp_instmap := InstMap0,
+ !Info ^ simp_sub_info ^ ssimp_requantify := no,
+ !Info ^ simp_sub_info ^ ssimp_rerun_det := no,
+ !Info ^ simp_sub_info ^ ssimp_lambdas := 0,
+ !Info ^ simp_sub_info ^ ssimp_has_parallel_conj := no,
+ !Info ^ simp_sub_info ^ ssimp_has_user_event := no.
+
+%-----------------------------------------------------------------------------%
+
+% Simple getters of fields in the simplify_info.
+:- pred simplify_info_get_simplifications(simplify_info::in,
+ simplifications::out) is det.
+:- interface.
+:- pred simplify_info_get_module_info(simplify_info::in, module_info::out)
+ is det.
+:- pred simplify_info_get_var_types(simplify_info::in, vartypes::out) is det.
+:- implementation.
+:- pred simplify_info_get_instmap(simplify_info::in, instmap::out) is det.
+:- pred simplify_info_get_inside_duplicated_for_switch(simplify_info::in,
+ bool::out) is det.
+:- pred simplify_info_get_fully_strict(simplify_info::in, bool::out) is det.
+:- interface.
+:- pred simplify_info_get_common_info(simplify_info::in, common_info::out)
+ is det.
+:- implementation.
+
+% Simple getters of fields in the sub_simplify_info.
+:- interface.
+:- pred simplify_info_get_varset(simplify_info::in, prog_varset::out) is det.
+:- implementation.
+:- pred simplify_info_get_inst_varset(simplify_info::in,
+ inst_varset::out) is det.
+:- interface.
+:- pred simplify_info_get_rtti_varmaps(simplify_info::in, rtti_varmaps::out)
+ is det.
+:- implementation.
+:- pred simplify_info_get_elim_vars(simplify_info::in,
+ list(list(prog_var))::out) is det.
+:- pred simplify_info_get_error_specs(simplify_info::in, list(error_spec)::out)
+ is det.
+:- interface.
+:- pred simplify_info_get_cost_delta(simplify_info::in, int::out) is det.
+:- implementation.
+:- pred simplify_info_get_lambdas(simplify_info::in, int::out) is det.
+:- pred simplify_info_get_has_parallel_conj(simplify_info::in, bool::out)
+ is det.
+:- pred simplify_info_get_found_contains_trace(simplify_info::in, bool::out)
+ is det.
+:- pred simplify_info_get_has_user_event(simplify_info::in, bool::out) is det.
+
+% Simple setters of fields in the simplify_info.
+:- pred simplify_info_set_simplifications(simplifications::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_module_info(module_info::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_var_types(vartypes::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_instmap(instmap::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_inside_duplicated_for_switch(bool::in,
+ simplify_info::in, simplify_info::out) is det.
+:- interface.
+:- pred simplify_info_set_common_info(common_info::in,
+ simplify_info::in, simplify_info::out) is det.
+:- implementation.
+
+% Simple setters of fields in the sub_simplify_info.
+
+:- pred simplify_info_set_varset(prog_varset::in,
+ simplify_info::in, simplify_info::out) is det.
+:- interface.
+:- pred simplify_info_set_rtti_varmaps(rtti_varmaps::in,
+ simplify_info::in, simplify_info::out) is det.
+:- implementation.
+:- pred simplify_info_set_elim_vars(list(list(prog_var))::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_error_specs(list(error_spec)::in,
+ simplify_info::in, simplify_info::out) is det.
+:- interface.
+:- pred simplify_info_set_requantify(
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_rerun_det(
+ simplify_info::in, simplify_info::out) is det.
+:- implementation.
+:- pred simplify_info_set_cost_delta(int::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_lambdas(int::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_has_parallel_conj(bool::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_found_contains_trace(bool::in,
+ simplify_info::in, simplify_info::out) is det.
+:- pred simplify_info_set_has_user_event(bool::in,
+ simplify_info::in, simplify_info::out) is det.
+
+%-----------------------------------------------------------------------------%
+
+simplify_info_get_simplifications(Info, Info ^ simp_simplifications).
+simplify_info_get_module_info(Info, Info ^ simp_module_info).
+simplify_info_get_var_types(Info, Info ^ simp_vartypes).
+simplify_info_get_instmap(Info, Info ^ simp_instmap).
+simplify_info_get_inside_duplicated_for_switch(Info,
+ Info ^ simp_inside_dupl_for_switch).
+simplify_info_get_fully_strict(Info, Info ^ simp_fully_strict).
+simplify_info_get_common_info(Info, Info ^ simp_common_info).
+
+simplify_info_get_varset(Info, Info ^ simp_sub_info ^ ssimp_varset).
+simplify_info_get_inst_varset(Info, Info ^ simp_sub_info ^ ssimp_inst_varset).
+simplify_info_get_rtti_varmaps(Info,
+ Info ^ simp_sub_info ^ ssimp_rtti_varmaps).
+simplify_info_get_elim_vars(Info, Info ^ simp_sub_info ^ ssimp_elim_vars).
+simplify_info_get_error_specs(Info, Info ^ simp_sub_info ^ ssimp_error_specs).
+simplify_info_get_cost_delta(Info, Info ^ simp_sub_info ^ ssimp_cost_delta).
+simplify_info_get_lambdas(Info, Info ^ simp_sub_info ^ ssimp_lambdas).
+simplify_info_get_has_parallel_conj(Info,
+ Info ^ simp_sub_info ^ ssimp_has_parallel_conj).
+simplify_info_get_found_contains_trace(Info,
+ Info ^ simp_sub_info ^ ssimp_found_contains_trace).
+simplify_info_get_has_user_event(Info,
+ Info ^ simp_sub_info ^ ssimp_has_user_event).
+
+simplify_info_set_simplifications(Simp, !Info) :-
+ !Info ^ simp_simplifications := Simp.
+simplify_info_set_module_info(ModuleInfo, !Info) :-
+ !Info ^ simp_module_info := ModuleInfo.
+simplify_info_set_var_types(VarTypes, !Info) :-
+ !Info ^ simp_vartypes := VarTypes.
+simplify_info_set_instmap(InstMap, !Info) :-
+ !Info ^ simp_instmap := InstMap.
+simplify_info_set_inside_duplicated_for_switch(IDFS, !Info) :-
+ !Info ^ simp_inside_dupl_for_switch := IDFS.
+simplify_info_set_common_info(Common, !Info) :-
+ !Info ^ simp_common_info := Common.
+
+simplify_info_set_varset(VarSet, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_varset := VarSet.
+simplify_info_set_rtti_varmaps(Rtti, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_rtti_varmaps := Rtti.
+simplify_info_set_elim_vars(EV, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_elim_vars := EV.
+simplify_info_set_error_specs(Specs, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_error_specs := Specs.
+simplify_info_set_requantify(!Info) :-
+ !Info ^ simp_sub_info ^ ssimp_requantify := yes.
+simplify_info_set_rerun_det(!Info) :-
+ !Info ^ simp_sub_info ^ ssimp_rerun_det := yes.
+simplify_info_set_cost_delta(Delta, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_cost_delta := Delta.
+simplify_info_set_lambdas(Lambdas, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_lambdas := Lambdas.
+simplify_info_set_has_parallel_conj(MHPC, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_has_parallel_conj := MHPC.
+simplify_info_set_found_contains_trace(FCT, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_found_contains_trace := FCT.
+simplify_info_set_has_user_event(HUE, !Info) :-
+ !Info ^ simp_sub_info ^ ssimp_has_user_event := HUE.
%-----------------------------------------------------------------------------%
:- end_module check_hlds.simplify.
cvs diff: Diffing compiler/notes
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/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_cairo
cvs diff: Diffing extras/graphics/mercury_cairo/samples
cvs diff: Diffing extras/graphics/mercury_cairo/samples/data
cvs diff: Diffing extras/graphics/mercury_cairo/tutorial
cvs diff: Diffing extras/graphics/mercury_glfw
cvs diff: Diffing extras/graphics/mercury_glfw/samples
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/monte
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.129
diff -u -b -r1.129 map.m
--- library/map.m 14 Apr 2012 15:00:21 -0000 1.129
+++ library/map.m 14 Jun 2012 03:28:10 -0000
@@ -27,6 +27,7 @@
:- import_module assoc_list.
:- import_module list.
+:- import_module maybe.
:- import_module set.
%-----------------------------------------------------------------------------%
@@ -151,6 +152,15 @@
:- func map.det_update(map(K, V), K, V) = map(K, V).
:- pred map.det_update(K::in, V::in, map(K, V)::in, map(K, V)::out) is det.
+ % map.search_insert(K, V, MaybeOldV, !Map):
+ %
+ % Search for the key K in the map. If the key is already in the map,
+ % with corresponding value OldV, set MaybeOldV to yes(OldV). If it
+ % is not in the map, then insert it into the map with value V.
+ %
+:- pred map.search_insert(K::in, V::in, maybe(V)::out,
+ map(K, V)::in, map(K, V)::out) is det.
+
% Update the value at the given key by applying the supplied
% transformation to it. Fails if the key is not found. This is faster
% than first searching for the value and then updating it.
@@ -228,6 +238,13 @@
:- func map.delete_list(map(K, V), list(K)) = map(K, V).
:- pred map.delete_list(list(K)::in, map(K, V)::in, map(K, V)::out) is det.
+ % Apply map.delete/3 to a sorted list of keys. The fact that the list
+ % is sorted may make this more efficient.
+ %
+:- func map.delete_sorted_list(map(K, V), list(K)) = map(K, V).
+:- pred map.delete_sorted_list(list(K)::in, map(K, V)::in, map(K, V)::out)
+ is det.
+
% Delete a key-value pair from a map and return the value.
% Fail if the key is not present.
%
@@ -733,6 +750,9 @@
:- pragma type_spec(map.det_update/4, K = var(_)).
:- pragma type_spec(map.det_update/4, K = int).
+:- pragma type_spec(map.search_insert/5, K = var(_)).
+:- pragma type_spec(map.search_insert/5, K = int).
+
:- pragma type_spec(map.overlay/2, K = var(_)).
:- pragma type_spec(map.overlay/3, K = var(_)).
@@ -756,6 +776,7 @@
:- implementation.
+:- import_module int.
:- import_module pair.
:- import_module require.
@@ -880,14 +901,14 @@
map.set(K, V, !Map),
map.set_from_assoc_list(KVs, !Map).
-map.update(M1, K, V) = M2 :-
- map.update(K, V, M1, M2).
+map.update(M0, K, V) = M :-
+ map.update(K, V, M0, M).
map.update(K, V, !Map) :-
tree234.update(K, V, !Map).
-map.det_update(M1, K, V) = M2 :-
- map.det_update(K, V, M1, M2).
+map.det_update(M0, K, V) = M :-
+ map.det_update(K, V, M0, M).
map.det_update(K, V, !Map) :-
( tree234.update(K, V, !.Map, NewMap) ->
@@ -896,6 +917,9 @@
report_lookup_error("map.det_update: key not found", K, V)
).
+map.search_insert(K, V, MaybeOldV, !Map) :-
+ tree234.search_insert(K, V, MaybeOldV, !Map).
+
map.transform_value(P, K, !Map) :-
tree234.transform_value(P, K, !Map).
@@ -969,19 +993,69 @@
map.from_rev_sorted_assoc_list(L, M) :-
tree234.from_rev_sorted_assoc_list(L, M).
-map.delete(M1, K) = M2 :-
- map.delete(K, M1, M2).
+map.delete(M0, K) = M :-
+ map.delete(K, M0, M).
map.delete(Key, !Map) :-
tree234.delete(Key, !Map).
-map.delete_list(M1, Ks) = M2 :-
- map.delete_list(Ks, M1, M2).
+map.delete_list(M0, Ks) = M :-
+ map.delete_list(Ks, M0, M).
map.delete_list([], !Map).
-map.delete_list([Key | Keys], !Map) :-
- map.delete(Key, !Map),
- map.delete_list(Keys, !Map).
+map.delete_list([DeleteKey | DeleteKeys], !Map) :-
+ map.delete(DeleteKey, !Map),
+ map.delete_list(DeleteKeys, !Map).
+
+map.delete_sorted_list(M0, Ks) = M :-
+ map.delete_sorted_list(Ks, M0, M).
+
+map.delete_sorted_list(DeleteKeys, !Map) :-
+ list.length(DeleteKeys, NumDeleteKeys),
+ find_min_size_based_on_depth(!.Map, MinSize),
+ ( NumDeleteKeys * 5 < MinSize ->
+ % Use this technique when we delete fewer than 20% of the keys.
+ map.delete_list(DeleteKeys, !Map)
+ ;
+ % Use this technique when we delete at least 20% of the keys.
+ map.to_assoc_list(!.Map, Pairs0),
+ map.delete_sorted_list_loop(DeleteKeys, Pairs0, [], RevPairs,
+ LeftOverPairs),
+ reverse_list_acc(RevPairs, LeftOverPairs, Pairs),
+ % Pairs = list.reverse(RevPairs) ++ LeftOverPairs,
+ map.from_assoc_list(Pairs, !:Map)
+ ).
+
+:- pred map.delete_sorted_list_loop(list(K)::in,
+ assoc_list(K, V)::in, assoc_list(K, V)::in, assoc_list(K, V)::out,
+ assoc_list(K, V)::out) is det.
+
+map.delete_sorted_list_loop([], Pairs, !RevPairs, Pairs).
+map.delete_sorted_list_loop([_ | _], [], !RevPairs, []).
+map.delete_sorted_list_loop([DeleteKey | DeleteKeys], [Pair0 | Pairs0],
+ !RevPairs, LeftOverPairs) :-
+ Pair0 = Key0 - _,
+ compare(Result, DeleteKey, Key0),
+ (
+ Result = (<),
+ map.delete_sorted_list_loop(DeleteKeys, [Pair0 | Pairs0],
+ !RevPairs, LeftOverPairs)
+ ;
+ Result = (=),
+ map.delete_sorted_list_loop(DeleteKeys, Pairs0,
+ !RevPairs, LeftOverPairs)
+ ;
+ Result = (>),
+ !:RevPairs = [Pair0 | !.RevPairs],
+ map.delete_sorted_list_loop([DeleteKey | DeleteKeys], Pairs0,
+ !RevPairs, LeftOverPairs)
+ ).
+
+:- pred reverse_list_acc(list(T)::in, list(T)::in, list(T)::out) is det.
+
+reverse_list_acc([], L, L).
+reverse_list_acc([X | Xs], L0, L) :-
+ reverse_list_acc(Xs, [X | L0], L).
map.remove(Key, Value, !Map) :-
tree234.remove(Key, Value, !Map).
Index: library/tree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/tree234.m,v
retrieving revision 1.76
diff -u -b -r1.76 tree234.m
--- library/tree234.m 14 Apr 2012 15:00:21 -0000 1.76
+++ library/tree234.m 14 Jun 2012 03:28:10 -0000
@@ -28,6 +28,8 @@
:- type tree234(K, V).
+%----------------------%
+
:- func tree234.init = tree234(K, V).
:- pred tree234.init(tree234(K, V)::uo) is det.
@@ -35,6 +37,8 @@
:- pred tree234.is_empty(tree234(K, V)::in) is semidet.
+%----------------------%
+
:- pred tree234.member(tree234(K, V)::in, K::out, V::out) is nondet.
:- pred tree234.search(tree234(K, V)::in, K::in, V::out) is semidet.
@@ -74,60 +78,122 @@
:- func tree234.min_key(tree234(K, V)) = K is semidet.
+%----------------------%
+
+ % Insert the given key/value pair into the tree. If the key is already
+ % in the tree, fail.
+ %
:- pred tree234.insert(K::in, V::in, tree234(K, V)::in, tree234(K, V)::out)
is semidet.
+ % tree234.search_insert(K, V, MaybeOldV, !Tree):
+ %
+ % Search for the key K in the tree. If the key is already in the tree,
+ % with corresponding value OldV, set MaybeOldV to yes(OldV). If it is
+ % not in the tree, then insert it into the tree with value V.
+ %
+:- pred tree234.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 tree234.update(K::in, V::in, tree234(K, V)::in, tree234(K, V)::out)
+ is semidet.
+
+ % tree234.set(K, V, !Tree):
+ %
+ % Set the value corresponding to K to V, regardless of whether K is
+ % already in the tree or not.
+ %
:- func tree234.set(tree234(K, V), K, V) = tree234(K, V).
:- pred tree234.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 tree234.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 tree234.delete(tree234(K, V), K) = tree234(K, V).
:- pred tree234.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 tree234.remove(K, V, tree234(K, V), tree234(K, V)).
:- mode tree234.remove(in, out, in, out) is semidet.
+ % Remove the smallest key from the tree, and return both it and the value
+ % corresponding to it. If the tree is empty, fail.
+ %
:- pred tree234.remove_smallest(K, V, tree234(K, V), tree234(K, V)).
:- mode tree234.remove_smallest(out, out, in, out) is semidet.
+%----------------------%
+
% Given a tree234, return a list of all the keys in the tree.
- % The list that is returned is in sorted order.
+ % The list that is returned is in sorted order (ascending on keys).
%
:- func tree234.keys(tree234(K, V)) = list(K).
:- pred tree234.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 tree234.values(tree234(K, V)) = list(V).
:- pred tree234.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 tree234.keys_and_values(tree234(K, V)::in, list(K)::out, list(V)::out)
is det.
-:- pred tree234.update(K::in, V::in, tree234(K, V)::in, tree234(K, V)::out)
- is semidet.
-
- % 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 tree234.transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
- tree234(K, V)::in, tree234(K, V)::out) is semidet.
+%----------------------%
% Count the number of elements in a tree.
%
:- func tree234.count(tree234(K, V)) = int.
:- pred tree234.count(tree234(K, V)::in, int::out) is det.
+ % Given a tree234, return an association list of all the keys and values
+ % in the tree. The association list that is returned is sorted on the keys.
+ %
+:- func tree234.tree234_to_assoc_list(tree234(K, V)) = assoc_list(K, V).
+:- pred tree234.tree234_to_assoc_list(tree234(K, V)::in,
+ assoc_list(K, V)::out) is det.
+
:- func tree234.assoc_list_to_tree234(assoc_list(K, V)) = tree234(K, V).
:- pred tree234.assoc_list_to_tree234(assoc_list(K, V)::in,
tree234(K, V)::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.
+ % 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.
%
-:- func tree234.tree234_to_assoc_list(tree234(K, V)) = assoc_list(K, V).
-:- pred tree234.tree234_to_assoc_list(tree234(K, V)::in,
- assoc_list(K, V)::out) is det.
+:- 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.
+
+%----------------------%
:- func tree234.foldl(func(K, V, A) = A, tree234(K, V), A) = A.
@@ -305,6 +371,8 @@
is semidet,
in, in, out, in, out, in, out, di, uo) is semidet.
+%----------------------%
+
:- func tree234.map_values(func(K, V) = W, tree234(K, V)) = tree234(K, W).
:- pred tree234.map_values(pred(K, V, W), tree234(K, V), tree234(K, W)).
@@ -317,6 +385,8 @@
:- mode tree234.map_values_only(pred(in, out) is det, in, out) is det.
:- mode tree234.map_values_only(pred(in, out) is semidet, in, out) is semidet.
+%----------------------%
+
:- pred tree234.map_foldl(pred(K, V, W, A, A), tree234(K, V), tree234(K, W),
A, A).
:- mode tree234.map_foldl(pred(in, in, out, in, out) is det,
@@ -409,6 +479,8 @@
pred(in, out, in, out, in, out, in, out) is semidet,
in, out, in, out, in, out, in, out) is semidet.
+%----------------------%
+
% Convert a tree234 into a pretty_printer.doc. A tree mapping
% K1 to V1, K2 to V2, ... is formatted as
% "map([K1 -> V1, K2 -> V2, ...])". The functor "map" is used
@@ -416,30 +488,16 @@
%
:- 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.
-
%------------------------------------------------------------------------------%
%------------------------------------------------------------------------------%
:- 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(tree234.search/3, K = var(_)).
:- pragma type_spec(tree234.search/3, K = int).
@@ -451,20 +509,7 @@
:- pragma type_spec(tree234.update(in, in, in, out), K = int).
%-----------------------------------------------------------------------------%
-
-:- implementation.
-
-:- 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.
%
@@ -500,6 +545,12 @@
:- mode uo_tree234(K, V) == free >> uniq_tree234(K, V).
:- mode uo_tree234 == free >> uniq_tree234(ground, ground).
+ % 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'.
%
@@ -507,17 +558,56 @@
%
:- pred well_formed(tree234(K, V)::in, maybe(int)::out) is det.
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
:- implementation.
+:- import_module bool.
+:- import_module int.
+:- import_module io.
+:- import_module pair.
+:- import_module require.
+:- import_module set.
+:- import_module string.
+
+:- inst two(K, V, T) ---> two(K, V, T, T).
+:- inst three(K, V, T) ---> three(K, V, K, V, T, T, T).
+:- inst four(K, V, T) ---> four(K, V, K, V, K, V, T, T, T, T).
+
+:- inst uniq_two(K, V, T) == unique(two(K, V, T, T)).
+:- inst uniq_three(K, V, T) == unique(three(K, V, K, V, 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)).
+
%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+tree234.init = empty.
tree234.init(empty).
+tree234.singleton(K, V) = two(K, V, empty, empty).
+
tree234.is_empty(Tree) :-
Tree = empty.
-tree234.singleton(K, V) = two(K, V, empty, empty).
-
+%------------------------------------------------------------------------------%
%------------------------------------------------------------------------------%
tree234.member(empty, _K, _V) :- fail.
@@ -565,6 +655,7 @@
).
%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
tree234.search(T, K, V) :-
(
@@ -641,6 +732,10 @@
)
).
+
+tree234.lookup(T, K) = V :-
+ tree234.lookup(T, K, V).
+
tree234.lookup(T, K, V) :-
( tree234.search(T, K, V0) ->
V = V0
@@ -932,321 +1027,103 @@
).
%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
-tree234.update(K, V, Tin, Tout) :-
+% tree234.insert is implemented using the simple top-down approach described
+% in Sedgwick 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).
+
+tree234.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
;
- Tin = two(K0, V0, T0, T1),
+ 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 implied by T0 = empty.
+ ->
compare(Result, K, K0),
(
Result = (<),
- tree234.update(K, V, T0, NewT0),
- Tout = two(K0, V0, NewT0, T1)
+ Tout = three(K, V, K0, V0, empty, empty, empty)
;
Result = (=),
- Tout = two(K0, V, T0, T1)
+ fail
;
Result = (>),
- tree234.update(K, V, T1, NewT1),
- Tout = two(K0, V0, T0, NewT1)
+ Tout = three(K0, V0, K, V, empty, empty, empty)
)
;
- Tin = three(K0, V0, K1, V1, T0, T1, T2),
- compare(Result0, K, K0),
+ compare(Result, 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),
+ Result = (<),
+ (
+ T0 = four(_, _, _, _, _, _, _, _, _, _),
+ tree234.split_four(T0, MT0K, MT0V, T00, T01),
+ compare(Result1, K, MT0K),
(
Result1 = (<),
- tree234.update(K, V, T1, NewT1),
- Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
+ tree234.insert2(T00, K, V, NewT00),
+ Tout = three(MT0K, MT0V, K0, V0, NewT00, T01, T1)
;
Result1 = (=),
- Tout = three(K0, V0, K1, V, T0, T1, T2)
+ fail
;
Result1 = (>),
- tree234.update(K, V, T2, NewT2),
- Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
- )
+ tree234.insert2(T01, K, V, NewT01),
+ Tout = three(MT0K, MT0V, K0, V0, T00, NewT01, T1)
)
;
- 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)
+ T0 = three(_, _, _, _, _, _, _),
+ tree234.insert3(T0, K, V, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
;
- Result0 = (=),
- Tout = four(K0, V, K1, V1, K2, V2, T0, T1, T2, T3)
+ T0 = two(_, _, _, _),
+ tree234.insert2(T0, K, V, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
;
- Result0 = (>),
- tree234.update(K, V, T1, NewT1),
- Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3)
+ T0 = empty,
+ NewT0 = two(K, V, empty, empty),
+ Tout = two(K0, V0, NewT0, T1)
)
;
- Result1 = (=),
- Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
+ Result = (=),
+ fail
;
- 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)
- )
- )
- ).
-
-%------------------------------------------------------------------------------%
-
-tree234.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)
- )
- )
- ).
-
-%------------------------------------------------------------------------------%
-%------------------------------------------------------------------------------%
-
-:- inst two(K, V, T) ---> two(K, V, T, T).
-:- inst three(K, V, T) ---> three(K, V, K, V, T, T, T).
-:- inst four(K, V, T) ---> four(K, V, K, V, K, V, T, T, T, T).
-
-:- inst uniq_two(K, V, T) == unique(two(K, V, T, T)).
-:- inst uniq_three(K, V, T) == unique(three(K, V, K, V, 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 Sedgwick 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).
-
-tree234.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 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 implied by T0 = 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 = (>),
+ Result = (>),
(
T1 = four(_, _, _, _, _, _, _, _, _, _),
tree234.split_four(T1, MT1K, MT1V, T10, T11),
@@ -1428,47 +1305,53 @@
%------------------------------------------------------------------------------%
-% 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(K, V, Tin, Tout) :-
+tree234.search_insert(K, V, MaybeOldV, Tin, Tout) :-
(
Tin = empty,
+ MaybeOldV = no,
Tout = two(K, V, empty, empty)
;
Tin = two(_, _, _, _),
- tree234.set2(Tin, K, V, Tout)
+ tree234.search_insert2(Tin, K, V, MaybeOldV, Tout)
;
Tin = three(_, _, _, _, _, _, _),
- tree234.set3(Tin, K, V, Tout)
+ tree234.search_insert3(Tin, K, V, MaybeOldV, Tout)
;
- Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
- compare(Result1, K, K1),
+ Tin = four(_, _, _, _, _, _, _, _, _, _),
+ tree234.split_four(Tin, MidK, MidV, Sub0, Sub1),
+ compare(Result1, K, MidK),
(
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)
+ tree234.search_insert2(Sub0, K, V, MaybeOldV, NewSub0),
+ (
+ MaybeOldV = no,
+ Tout = two(MidK, MidV, NewSub0, Sub1)
+ ;
+ MaybeOldV = yes(_),
+ Tout = Tin
+ )
;
Result1 = (=),
- Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
+ MaybeOldV = yes(MidV),
+ Tout = Tin
;
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)
+ tree234.search_insert2(Sub1, K, V, MaybeOldV, NewSub1),
+ (
+ MaybeOldV = no,
+ Tout = two(MidK, MidV, Sub0, NewSub1)
+ ;
+ MaybeOldV = yes(_),
+ Tout = Tin
+ )
)
).
-:- 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.
-:- pragma type_spec(tree234.set2(in_two, in, in, out), K = var(_)).
+:- pred tree234.search_insert2(tree234(K, V), K, V, maybe(V), tree234(K, V)).
+:- mode tree234.search_insert2(in_two, in, in, out, out) is det.
-tree234.set2(two(K0, V0, T0, T1), K, V, Tout) :-
+tree234.search_insert2(Tin, K, V, MaybeOldV, Tout) :-
+ Tin = two(K0, V0, T0, T1),
(
T0 = empty
% T1 = empty implied by T0 = empty.
@@ -1476,12 +1359,15 @@
compare(Result, K, K0),
(
Result = (<),
+ MaybeOldV = no,
Tout = three(K, V, K0, V0, empty, empty, empty)
;
Result = (=),
- Tout = two(K, V, T0, T1)
+ MaybeOldV = yes(V0),
+ Tout = Tin
;
Result = (>),
+ MaybeOldV = no,
Tout = three(K0, V0, K, V, empty, empty, empty)
)
;
@@ -1494,32 +1380,54 @@
compare(Result1, K, MT0K),
(
Result1 = (<),
- tree234.set2(T00, K, V, NewT00),
+ tree234.search_insert2(T00, K, V, MaybeOldV, NewT00),
+ (
+ MaybeOldV = no,
Tout = three(MT0K, MT0V, K0, V0, NewT00, T01, T1)
;
+ MaybeOldV = yes(_),
+ Tout = Tin
+ )
+ ;
Result1 = (=),
- Tout = three(MT0K, V, K0, V0, T00, T01, T1)
+ MaybeOldV = yes(MT0V),
+ Tout = Tin
;
Result1 = (>),
- tree234.set2(T01, K, V, NewT01),
+ 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.set3(T0, K, V, NewT0),
- Tout = two(K0, V0, NewT0, T1)
+ tree234.search_insert3(T0, K, V, MaybeOldV, NewT0)
;
T0 = two(_, _, _, _),
- tree234.set2(T0, K, V, NewT0),
+ 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 = (=),
- Tout = two(K, V, T0, T1)
+ MaybeOldV = yes(V0),
+ Tout = Tin
;
Result = (>),
(
@@ -1528,62 +1436,86 @@
compare(Result1, K, MT1K),
(
Result1 = (<),
- tree234.set2(T10, K, V, NewT10),
+ tree234.search_insert2(T10, K, V, MaybeOldV, NewT10),
+ (
+ MaybeOldV = no,
Tout = three(K0, V0, MT1K, MT1V, T0, NewT10, T11)
;
+ MaybeOldV = yes(_),
+ Tout = Tin
+ )
+ ;
Result1 = (=),
- Tout = three(K0, V0, MT1K, V, T0, T10, T11)
+ MaybeOldV = yes(MT1V),
+ Tout = Tin
;
Result1 = (>),
- tree234.set2(T11, K, V, NewT11),
+ 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.set3(T1, K, V, NewT1),
- Tout = two(K0, V0, T0, NewT1)
+ tree234.search_insert3(T1, K, V, MaybeOldV, NewT1)
;
T1 = two(_, _, _, _),
- tree234.set2(T1, K, V, NewT1),
+ 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 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.
-:- pragma type_spec(tree234.set3(in_three, in, in, out), K = var(_)).
+:- pred tree234.search_insert3(tree234(K, V), K, V, maybe(V), tree234(K, V)).
+:- mode tree234.search_insert3(in_three, in, in, out, out) is det.
-tree234.set3(three(K0, V0, K1, V1, T0, T1, T2), K, V, Tout) :-
+tree234.search_insert3(Tin, K, V, MaybeOldV, Tout) :-
+ Tin = three(K0, V0, K1, V1, T0, T1, T2),
(
T0 = empty
- % T1 = empty implied by T0 = empty
- % T2 = empty implied by T0 = empty
+ % T1 = empty implied by T0 = empty.
+ % T2 = empty implied by T0 = empty.
->
compare(Result0, K, K0),
(
Result0 = (<),
+ MaybeOldV = no,
Tout = four(K, V, K0, V0, K1, V1, empty, empty, empty, empty)
;
Result0 = (=),
- Tout = three(K0, V, K1, V1, empty, empty, empty)
+ 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 = (=),
- Tout = three(K0, V0, K1, V, empty, empty, empty)
+ MaybeOldV = yes(V1),
+ Tout = Tin
;
Result1 = (>),
+ MaybeOldV = no,
Tout = four(K0, V0, K1, V1, K, V, empty, empty, empty, empty)
)
)
@@ -1597,34 +1529,56 @@
compare(ResultM, K, MT0K),
(
ResultM = (<),
- tree234.set2(T00, K, V, NewT00),
+ 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 = (=),
- Tout = four(MT0K, V, K0, V0, K1, V1, T00, T01, T1, T2)
+ MaybeOldV = yes(MT0V),
+ Tout = Tin
;
ResultM = (>),
- tree234.set2(T01, K, V, NewT01),
+ 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.set3(T0, K, V, NewT0),
- Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
+ tree234.search_insert3(T0, K, V, MaybeOldV, NewT0)
;
T0 = two(_, _, _, _),
- tree234.set2(T0, K, V, NewT0),
+ 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 = (=),
- Tout = three(K0, V, K1, V1, T0, T1, T2)
+ MaybeOldV = yes(V0),
+ Tout = Tin
;
Result0 = (>),
compare(Result1, K, K1),
@@ -1636,34 +1590,56 @@
compare(ResultM, K, MT1K),
(
ResultM = (<),
- tree234.set2(T10, K, V, NewT10),
+ 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 = (=),
- Tout = four(K0, V0, MT1K, V, K1, V1, T0, T10, T11, T2)
+ MaybeOldV = yes(MT1V),
+ Tout = Tin
;
ResultM = (>),
- tree234.set2(T11, K, V, NewT11),
+ 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.set3(T1, K, V, NewT1),
- Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
+ tree234.search_insert3(T1, K, V, MaybeOldV, NewT1)
;
T1 = two(_, _, _, _),
- tree234.set2(T1, K, V, NewT1),
+ 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 = (=),
- Tout = three(K0, V0, K, V, T0, T1, T2)
+ MaybeOldV = yes(V1),
+ Tout = Tin
;
Result1 = (>),
(
@@ -1672,28 +1648,49 @@
compare(ResultM, K, MT2K),
(
ResultM = (<),
- tree234.set2(T20, K, V, NewT20),
+ 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 = (=),
- Tout = four(K0, V0, K1, V1, MT2K, V, T0, T1, T20, T21)
+ MaybeOldV = yes(MT2V),
+ Tout = Tin
;
ResultM = (>),
- tree234.set2(T21, K, V, NewT21),
+ 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.set3(T2, K, V, NewT2),
- Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
+ tree234.search_insert3(T2, K, V, MaybeOldV, NewT2)
;
T2 = two(_, _, _, _),
- tree234.set2(T2, K, V, NewT2),
+ 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)
)
@@ -1702,138 +1699,50 @@
).
%------------------------------------------------------------------------------%
-%------------------------------------------------------------------------------%
-
-tree234.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 tree234.delete_2(tree234(K, V), K, tree234(K, V), bool).
-%:- mode tree234.delete_2(di, in, uo, out) is det.
-:- mode tree234.delete_2(in, in, out, out) is det.
-tree234.delete_2(Tin, K, Tout, RH) :-
+tree234.update(K, V, Tin, Tout) :-
(
Tin = empty,
- Tout = empty,
- RH = no
+ fail
;
Tin = two(K0, V0, T0, T1),
- compare(Result0, K, K0),
- (
- Result0 = (<),
- tree234.delete_2(T0, K, NewT0, RHT0),
- (
- RHT0 = yes,
- fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
- ;
- RHT0 = no,
- Tout = two(K0, V0, NewT0, T1),
- RH = no
- )
- ;
- Result0 = (=),
- ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
+ compare(Result, K, K0),
(
- RHT1 = yes,
- fix_2node_t1(ST1K, ST1V, T0, NewT1, Tout, RH)
- ;
- RHT1 = no,
- Tout = two(ST1K, ST1V, T0, NewT1),
- RH = no
- )
- ;
- % T1 must be empty
- Tout = T0,
- RH = yes
- )
+ Result = (<),
+ tree234.update(K, V, T0, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
;
- Result0 = (>),
- tree234.delete_2(T1, K, NewT1, RHT1),
- (
- RHT1 = yes,
- fix_2node_t1(K0, V0, T0, NewT1, Tout, RH)
+ Result = (=),
+ Tout = two(K0, V, T0, T1)
;
- RHT1 = no,
- Tout = two(K0, V0, T0, NewT1),
- RH = no
- )
+ 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.delete_2(T0, K, NewT0, RHT0),
- (
- RHT0 = yes,
- fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
- ;
- RHT0 = no,
- Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
- RH = no
- )
+ tree234.update(K, V, T0, NewT0),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
Result0 = (=),
- ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1)
- ->
- (
- RHT1 = yes,
- fix_3node_t1(ST1K, ST1V, K1, V1, T0, NewT1, T2, Tout, RH)
- ;
- RHT1 = no,
- Tout = three(ST1K, ST1V, K1, V1, T0, NewT1, T2),
- RH = no
- )
- ;
- % T1 must be empty
- Tout = two(K1, V1, T0, T2),
- RH = no
- )
+ Tout = three(K0, V, K1, V1, T0, T1, T2)
;
Result0 = (>),
compare(Result1, K, K1),
(
Result1 = (<),
- tree234.delete_2(T1, K, NewT1, RHT1),
- (
- RHT1 = yes,
- fix_3node_t1(K0, V0, K1, V1, T0, NewT1, T2, Tout, RH)
- ;
- RHT1 = no,
- Tout = three(K0, V0, K1, V1, T0, NewT1, T2),
- RH = no
- )
+ tree234.update(K, V, T1, NewT1),
+ Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
Result1 = (=),
- ( tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) ->
- (
- RHT2 = yes,
- fix_3node_t2(K0, V0, ST2K, ST2V, T0, T1, NewT2, Tout,
- RH)
- ;
- RHT2 = no,
- Tout = three(K0, V0, ST2K, ST2V, T0, T1, NewT2),
- RH = no
- )
- ;
- % T2 must be empty.
- Tout = two(K0, V0, T0, T1),
- RH = no
- )
+ Tout = three(K0, V0, K1, V, T0, T1, T2)
;
Result1 = (>),
- tree234.delete_2(T2, K, NewT2, RHT2),
- (
- RHT2 = yes,
- fix_3node_t2(K0, V0, K1, V1, T0, T1, NewT2, Tout, RH)
- ;
- RHT2 = no,
- Tout = three(K0, V0, K1, V1, T0, T1, NewT2),
- RH = no
- )
+ tree234.update(K, V, T2, NewT2),
+ Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
)
)
;
@@ -1844,871 +1753,1788 @@
compare(Result0, K, K0),
(
Result0 = (<),
- tree234.delete_2(T0, K, NewT0, RHT0),
- (
- RHT0 = yes,
- fix_4node_t0(K0, V0, K1, V1, K2, V2,
- NewT0, T1, T2, T3, Tout, RH)
- ;
- RHT0 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
- RH = no
- )
+ tree234.update(K, V, T0, NewT0),
+ Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3)
;
Result0 = (=),
- ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
- (
- RHT1 = yes,
- fix_4node_t1(ST1K, ST1V, K1, V1, K2, V2,
- T0, NewT1, T2, T3, Tout, RH)
- ;
- RHT1 = no,
- Tout = four(ST1K, ST1V, K1, V1, K2, V2,
- T0, NewT1, T2, T3),
- RH = no
- )
- ;
- % T1 must be empty.
- Tout = three(K1, V1, K2, V2, T0, T2, T3),
- RH = no
- )
+ Tout = four(K0, V, K1, V1, K2, V2, T0, T1, T2, T3)
;
Result0 = (>),
- tree234.delete_2(T1, K, NewT1, RHT1),
- (
- RHT1 = yes,
- fix_4node_t1(K0, V0, K1, V1, K2, V2,
- T0, NewT1, T2, T3, Tout, RH)
- ;
- RHT1 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3),
- RH = no
- )
+ tree234.update(K, V, T1, NewT1),
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3)
)
;
Result1 = (=),
- ( tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) ->
- (
- RHT2 = yes,
- fix_4node_t2(K0, V0, ST2K, ST2V, K2, V2,
- T0, T1, NewT2, T3, Tout, RH)
- ;
- RHT2 = no,
- Tout = four(K0, V0, ST2K, ST2V, K2, V2,
- T0, T1, NewT2, T3),
- RH = no
- )
- ;
- % T2 must be empty
- Tout = three(K0, V0, K2, V2, T0, T1, T3),
- RH = no
- )
+ Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
;
Result1 = (>),
compare(Result2, K, K2),
(
Result2 = (<),
- tree234.delete_2(T2, K, NewT2, RHT2),
- (
- RHT2 = yes,
- fix_4node_t2(K0, V0, K1, V1, K2, V2,
- T0, T1, NewT2, T3, Tout, RH)
- ;
- RHT2 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3),
- RH = no
- )
+ tree234.update(K, V, T2, NewT2),
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3)
;
Result2 = (=),
- ( tree234.remove_smallest_2(T3, ST3K, ST3V, NewT3, RHT3) ->
- (
- RHT3 = yes,
- fix_4node_t3(K0, V0, K1, V1, ST3K, ST3V,
- T0, T1, T2, NewT3, Tout, RH)
- ;
- RHT3 = no,
- Tout = four(K0, V0, K1, V1, ST3K, ST3V,
- T0, T1, T2, NewT3),
- RH = no
- )
- ;
- % T3 must be empty
- Tout = three(K0, V0, K1, V1, T0, T1, T2),
- RH = no
- )
+ Tout = four(K0, V0, K1, V1, K2, V, T0, T1, T2, T3)
;
Result2 = (>),
- tree234.delete_2(T3, K, NewT3, RHT3),
- (
- RHT3 = yes,
- fix_4node_t3(K0, V0, K1, V1, K2, V2,
- T0, T1, T2, NewT3, Tout, RH)
- ;
- RHT3 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3),
- RH = no
- )
+ tree234.update(K, V, T3, NewT3),
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3)
)
)
).
%------------------------------------------------------------------------------%
- % We use the same algorithm as tree234.delete.
-
-tree234.remove(K, V, Tin, Tout) :-
- tree234.remove_2(Tin, K, V, Tout, _).
-
-:- pred tree234.remove_2(tree234(K, V), K, V, tree234(K, V), bool).
-%:- mode tree234.remove_2(di, in, uo, uo, out) is semidet.
-:- mode tree234.remove_2(in, in, out, out, out) is semidet.
+tree234.set(!.T, K, V) = !:T :-
+ tree234.set(K, V, !T).
-tree234.remove_2(Tin, K, V, Tout, RH) :-
+tree234.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,
- fail
+ Tout = two(K, V, empty, empty)
;
- Tin = two(K0, V0, T0, T1),
- compare(Result0, K, K0),
- (
- Result0 = (<),
- tree234.remove_2(T0, K, V, NewT0, RHT0),
- (
- RHT0 = yes,
- fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
+ Tin = two(_, _, _, _),
+ tree234.set2(Tin, K, V, Tout)
;
- RHT0 = no,
- Tout = two(K0, V0, NewT0, T1),
- RH = no
- )
+ Tin = three(_, _, _, _, _, _, _),
+ tree234.set3(Tin, K, V, Tout)
;
- Result0 = (=),
- ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
+ Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ compare(Result1, K, K1),
(
- RHT1 = yes,
- fix_2node_t1(ST1K, ST1V, T0, NewT1, Tout, RH)
- ;
- RHT1 = no,
- Tout = two(ST1K, ST1V, T0, NewT1),
- RH = no
- )
+ 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)
;
- % T1 must be empty.
- Tout = T0,
- RH = yes
- ),
- V = V0
+ Result1 = (=),
+ Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
;
- Result0 = (>),
- tree234.remove_2(T1, K, V, NewT1, RHT1),
+ 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.
+:- pragma type_spec(tree234.set2(in_two, in, in, out), K = var(_)).
+
+tree234.set2(two(K0, V0, T0, T1), K, V, Tout) :-
(
- RHT1 = yes,
- fix_2node_t1(K0, V0, T0, NewT1, Tout, RH)
+ T0 = empty
+ % T1 = empty implied by T0 = empty.
+ ->
+ compare(Result, K, K0),
+ (
+ Result = (<),
+ Tout = three(K, V, K0, V0, empty, empty, empty)
;
- RHT1 = no,
- Tout = two(K0, V0, T0, NewT1),
- RH = no
- )
+ Result = (=),
+ Tout = two(K, V, T0, T1)
+ ;
+ Result = (>),
+ Tout = three(K0, V0, K, V, empty, empty, empty)
)
;
- Tin = three(K0, V0, K1, V1, T0, T1, T2),
- compare(Result0, K, K0),
+ compare(Result, K, K0),
(
- Result0 = (<),
- tree234.remove_2(T0, K, V, NewT0, RHT0),
+ Result = (<),
(
- RHT0 = yes,
- fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
+ 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)
;
- RHT0 = no,
- Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
- RH = no
+ 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)
)
;
- Result0 = (=),
- ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
- (
- RHT1 = yes,
- fix_3node_t1(ST1K, ST1V, K1, V1, T0, NewT1, T2, Tout, RH)
+ T0 = three(_, _, _, _, _, _, _),
+ tree234.set3(T0, K, V, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
;
- RHT1 = no,
- Tout = three(ST1K, ST1V, K1, V1, T0, NewT1, T2),
- RH = no
+ 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)
)
;
- % T1 must be empty.
- Tout = two(K1, V1, T0, T2),
- RH = no
- ),
- V = V0
+ Result = (=),
+ Tout = two(K, V, T0, T1)
;
- Result0 = (>),
- compare(Result1, K, K1),
+ Result = (>),
(
- Result1 = (<),
- tree234.remove_2(T1, K, V, NewT1, RHT1),
+ T1 = four(_, _, _, _, _, _, _, _, _, _),
+ tree234.split_four(T1, MT1K, MT1V, T10, T11),
+ compare(Result1, K, MT1K),
(
- RHT1 = yes,
- fix_3node_t1(K0, V0, K1, V1, T0, NewT1, T2, Tout, RH)
- ;
- RHT1 = no,
- Tout = three(K0, V0, K1, V1, T0, NewT1, T2),
- RH = no
- )
+ Result1 = (<),
+ tree234.set2(T10, K, V, NewT10),
+ Tout = three(K0, V0, MT1K, MT1V, T0, NewT10, T11)
;
Result1 = (=),
- ( tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) ->
- (
- RHT2 = yes,
- fix_3node_t2(K0, V0, ST2K, ST2V,
- T0, T1, NewT2, Tout, RH)
+ Tout = three(K0, V0, MT1K, V, T0, T10, T11)
;
- RHT2 = no,
- Tout = three(K0, V0, ST2K, ST2V, T0, T1, NewT2),
- RH = no
+ Result1 = (>),
+ tree234.set2(T11, K, V, NewT11),
+ Tout = three(K0, V0, MT1K, MT1V, T0, T10, NewT11)
)
;
- % T2 must be empty.
- Tout = two(K0, V0, T0, T1),
- RH = no
- ),
- V = V1
+ T1 = three(_, _, _, _, _, _, _),
+ tree234.set3(T1, K, V, NewT1),
+ Tout = two(K0, V0, T0, NewT1)
;
- Result1 = (>),
- tree234.remove_2(T2, K, V, NewT2, RHT2),
- (
- RHT2 = yes,
- fix_3node_t2(K0, V0, K1, V1, T0, T1, NewT2, Tout, RH)
+ T1 = two(_, _, _, _),
+ tree234.set2(T1, K, V, NewT1),
+ Tout = two(K0, V0, T0, NewT1)
;
- RHT2 = no,
- Tout = three(K0, V0, K1, V1, T0, T1, NewT2),
- RH = no
- )
+ 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.
+:- pragma type_spec(tree234.set3(in_three, in, in, out), K = var(_)).
+
+tree234.set3(three(K0, V0, K1, V1, T0, T1, T2), K, V, Tout) :-
+ (
+ T0 = empty
+ % T1 = empty implied by T0 = empty
+ % T2 = empty implied by T0 = empty
+ ->
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ Tout = four(K, V, K0, V0, K1, V1, empty, empty, empty, empty)
;
- Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ 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 = (<),
- tree234.remove_2(T0, K, V, NewT0, RHT0),
(
- RHT0 = yes,
- fix_4node_t0(K0, V0, K1, V1, K2, V2,
- NewT0, T1, T2, T3, Tout, RH)
+ 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)
;
- RHT0 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
- RH = no
+ 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)
)
;
- Result0 = (=),
- ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
- (
- RHT1 = yes,
- fix_4node_t1(ST1K, ST1V, K1, V1, K2, V2,
- T0, NewT1, T2, T3, Tout, RH)
+ T0 = three(_, _, _, _, _, _, _),
+ tree234.set3(T0, K, V, NewT0),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
- RHT1 = no,
- Tout = four(ST1K, ST1V, K1, V1, K2, V2,
- T0, NewT1, T2, T3),
- RH = no
+ 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)
)
;
- % T1 must be empty.
- Tout = three(K1, V1, K2, V2, T0, T2, T3),
- RH = no
- ),
- V = V0
+ Result0 = (=),
+ Tout = three(K0, V, K1, V1, T0, T1, T2)
;
Result0 = (>),
- tree234.remove_2(T1, K, V, NewT1, RHT1),
+ compare(Result1, K, K1),
(
- RHT1 = yes,
- fix_4node_t1(K0, V0, K1, V1, K2, V2,
- T0, NewT1, T2, T3, Tout, RH)
+ 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)
;
- RHT1 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3),
- RH = no
- )
+ 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)
)
;
- Result1 = (=),
- ( tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) ->
- (
- RHT2 = yes,
- fix_4node_t2(K0, V0, ST2K, ST2V, K2, V2,
- T0, T1, NewT2, T3, Tout, RH)
+ T1 = three(_, _, _, _, _, _, _),
+ tree234.set3(T1, K, V, NewT1),
+ Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
- RHT2 = no,
- Tout = four(K0, V0, ST2K, ST2V, K2, V2, T0, T1, NewT2, T3),
- RH = no
+ 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)
)
;
- % T2 must be empty.
- Tout = three(K0, V0, K2, V2, T0, T1, T3),
- RH = no
- ),
- V = V1
+ Result1 = (=),
+ Tout = three(K0, V0, K, V, T0, T1, T2)
;
Result1 = (>),
- compare(Result2, K, K2),
(
- Result2 = (<),
- tree234.remove_2(T2, K, V, NewT2, RHT2),
+ T2 = four(_, _, _, _, _, _, _, _, _, _),
+ tree234.split_four(T2, MT2K, MT2V, T20, T21),
+ compare(ResultM, K, MT2K),
(
- RHT2 = yes,
- fix_4node_t2(K0, V0, K1, V1, K2, V2,
- T0, T1, NewT2, T3, Tout, RH)
- ;
- RHT2 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3),
- RH = no
- )
+ ResultM = (<),
+ tree234.set2(T20, K, V, NewT20),
+ Tout = four(K0, V0, K1, V1, MT2K, MT2V,
+ T0, T1, NewT20, T21)
;
- Result2 = (=),
- ( tree234.remove_smallest_2(T3, ST3K, ST3V, NewT3, RHT3) ->
- (
- RHT3 = yes,
- fix_4node_t3(K0, V0, K1, V1, ST3K, ST3V,
- T0, T1, T2, NewT3, Tout, RH)
+ ResultM = (=),
+ Tout = four(K0, V0, K1, V1, MT2K, V, T0, T1, T20, T21)
;
- RHT3 = no,
- Tout = four(K0, V0, K1, V1, ST3K, ST3V,
- T0, T1, T2, NewT3),
- RH = no
+ ResultM = (>),
+ tree234.set2(T21, K, V, NewT21),
+ Tout = four(K0, V0, K1, V1, MT2K, MT2V,
+ T0, T1, T20, NewT21)
)
;
- % T3 must be empty.
- Tout = three(K0, V0, K1, V1, T0, T1, T2),
- RH = no
- ),
- V = V2
+ T2 = three(_, _, _, _, _, _, _),
+ tree234.set3(T2, K, V, NewT2),
+ Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
;
- Result2 = (>),
- tree234.remove_2(T3, K, V, NewT3, RHT3),
- (
- RHT3 = yes,
- fix_4node_t3(K0, V0, K1, V1, K2, V2,
- T0, T1, T2, NewT3, Tout, RH)
+ T2 = two(_, _, _, _),
+ tree234.set2(T2, K, V, NewT2),
+ Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
;
- RHT3 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3),
- RH = no
+ T2 = empty,
+ NewT2 = two(K, V, empty, empty),
+ Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
)
)
)
).
%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
- % The algorithm we use similar to tree234.delete, except that we
- % always go down the left subtree.
-
-tree234.remove_smallest(K, V, Tin, Tout) :-
- tree234.remove_smallest_2(Tin, K, V, Tout, _).
-
-:- pred tree234.remove_smallest_2(tree234(K, V), K, V, tree234(K, V), bool).
-%:- mode tree234.remove_smallest_2(di, uo, uo, uo, out) is semidet.
-:- mode tree234.remove_smallest_2(in, out, out, out, out) is semidet.
-
-tree234.remove_smallest_2(Tin, K, V, Tout, RH) :-
+tree234.transform_value(P, K, Tin, Tout) :-
(
Tin = empty,
fail
;
Tin = two(K0, V0, T0, T1),
- ( T0 = empty ->
- K = K0,
- V = V0,
- Tout = T1,
- RH = yes
- ;
- tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
+ compare(Result, K, K0),
(
- RHT0 = yes,
- fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
+ Result = (<),
+ tree234.transform_value(P, K, T0, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
;
- RHT0 = no,
- Tout = two(K0, V0, NewT0, T1),
- RH = no
- )
+ 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),
- ( T0 = empty ->
- K = K0,
- V = V0,
- Tout = two(K1, V1, T1, T2),
- RH = no
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ tree234.transform_value(P, K, T0, NewT0),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
;
- tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
+ Result0 = (=),
+ P(V0, VNew),
+ Tout = three(K0, VNew, K1, V1, T0, T1, T2)
+ ;
+ Result0 = (>),
+ compare(Result1, K, K1),
(
- RHT0 = yes,
- fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
+ Result1 = (<),
+ tree234.transform_value(P, K, T1, NewT1),
+ Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
;
- RHT0 = no,
- Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
- RH = no
+ 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),
- ( T0 = empty ->
- K = K0,
- V = V0,
- Tout = three(K1, V1, K2, V2, T1, T2, T3),
- RH = no
+ 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)
;
- tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
+ 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),
(
- RHT0 = yes,
- fix_4node_t0(K0, V0, K1, V1, K2, V2,
- NewT0, T1, T2, T3, Tout, RH)
+ Result2 = (<),
+ tree234.transform_value(P, K, T2, NewT2),
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3)
;
- RHT0 = no,
- Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
- RH = no
+ 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 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.delete(!.T, K) = !:T :-
+ tree234.delete(K, !T).
+
+tree234.delete(K, Tin, Tout) :-
+ tree234.delete_2(Tin, K, Tout, _).
- % 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.
+ % 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 fix_2node_t0(K, V, tree234(K, V), tree234(K, V), tree234(K, V), bool).
-:- mode fix_2node_t0(di, di, di, di, uo, out) is det.
-:- mode fix_2node_t0(in, in, in, in, out, out) is det.
+:- pred tree234.delete_2(tree234(K, V), K, tree234(K, V), bool).
+%:- mode tree234.delete_2(di, in, uo, out) is det.
+:- mode tree234.delete_2(in, in, out, out) is det.
-fix_2node_t0(K0, V0, T0, T1, Tout, RH) :-
+tree234.delete_2(Tin, K, 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),
+ Tin = empty,
+ Tout = empty,
RH = no
;
- % 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 = no
+ Tin = two(K0, V0, T0, T1),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ tree234.delete_2(T0, K, NewT0, RHT0),
+ (
+ RHT0 = yes,
+ fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
;
- % 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 = yes
+ RHT0 = no,
+ Tout = two(K0, V0, NewT0, T1),
+ RH = no
+ )
;
- T1 = empty,
- error("unbalanced 234 tree")
- % Tout = two(K0, V0, T0, T1),
- % RH = yes
- ).
-
-:- pred fix_2node_t1(K, V, tree234(K, V), tree234(K, V), tree234(K, V), bool).
-:- 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) :-
+ Result0 = (=),
+ ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
(
- % 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 = no
+ RHT1 = yes,
+ fix_2node_t1(ST1K, ST1V, T0, NewT1, Tout, RH)
;
- % 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),
+ RHT1 = no,
+ Tout = two(ST1K, ST1V, T0, NewT1),
RH = no
+ )
;
- % 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),
+ % T1 must be empty
+ Tout = T0,
RH = yes
+ )
;
- T0 = empty,
- error("unbalanced 234 tree")
- % Tout = two(K0, V0, T0, T1),
- % RH = yes
- ).
-
-:- pred fix_3node_t0(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
- tree234(K, V), bool).
-:- 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) :-
+ Result0 = (>),
+ tree234.delete_2(T1, K, NewT1, RHT1),
(
- % 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 = no
+ RHT1 = yes,
+ fix_2node_t1(K0, V0, T0, NewT1, Tout, RH)
;
- % 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),
+ RHT1 = no,
+ Tout = two(K0, V0, T0, NewT1),
RH = no
+ )
+ )
;
- % 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),
+ Tin = three(K0, V0, K1, V1, T0, T1, T2),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ tree234.delete_2(T0, K, NewT0, RHT0),
+ (
+ RHT0 = yes,
+ fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
+ ;
+ RHT0 = no,
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
RH = no
+ )
;
- T1 = empty,
- error("unbalanced 234 tree")
- % Tout = three(K0, V0, K1, V1, T0, T1, T2),
- % The heights of T1 and T2 are unchanged
- % RH = no
- ).
-
-:- pred fix_3node_t1(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
- tree234(K, V), bool).
-%:- 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) :-
+ Result0 = (=),
+ ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1)
+ ->
(
- % 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 = no
+ RHT1 = yes,
+ fix_3node_t1(ST1K, ST1V, K1, V1, T0, NewT1, T2, Tout, RH)
;
- % 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),
+ RHT1 = no,
+ Tout = three(ST1K, ST1V, K1, V1, T0, NewT1, T2),
RH = no
+ )
;
- % 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),
+ % T1 must be empty
+ Tout = two(K1, V1, T0, T2),
RH = no
+ )
;
- T0 = empty,
- error("unbalanced 234 tree")
- % Tout = three(K0, V0, K1, V1, T0, T1, T2),
- % The heights of T0 and T2 are unchanged
- % RH = no
- ).
-
-:- pred fix_3node_t2(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
- tree234(K, V), bool).
-%:- 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) :-
+ Result0 = (>),
+ compare(Result1, K, K1),
(
- % 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),
+ Result1 = (<),
+ tree234.delete_2(T1, K, NewT1, RHT1),
+ (
+ RHT1 = yes,
+ fix_3node_t1(K0, V0, K1, V1, T0, NewT1, T2, Tout, RH)
+ ;
+ RHT1 = no,
+ Tout = three(K0, V0, K1, V1, T0, NewT1, T2),
RH = no
+ )
;
- % 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),
+ Result1 = (=),
+ ( tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) ->
+ (
+ RHT2 = yes,
+ fix_3node_t2(K0, V0, ST2K, ST2V, T0, T1, NewT2, Tout,
+ RH)
+ ;
+ RHT2 = no,
+ Tout = three(K0, V0, ST2K, ST2V, T0, T1, NewT2),
RH = no
+ )
;
- % 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),
+ % T2 must be empty.
+ Tout = two(K0, V0, T0, T1),
RH = no
+ )
;
- T1 = empty,
- error("unbalanced 234 tree")
- % Tout = three(K0, V0, K1, V1, T0, T1, T2),
- % The heights of T0 and T1 are unchanged
- % RH = no
- ).
-
-:- 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), bool).
-%:- 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) :-
+ Result1 = (>),
+ tree234.delete_2(T2, K, NewT2, RHT2),
(
- % 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 = no
+ RHT2 = yes,
+ fix_3node_t2(K0, V0, K1, V1, T0, T1, NewT2, Tout, RH)
;
- % 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),
+ RHT2 = no,
+ Tout = three(K0, V0, K1, V1, T0, T1, NewT2),
RH = no
+ )
+ )
+ )
;
- % 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),
+ 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 = yes,
+ fix_4node_t0(K0, V0, K1, V1, K2, V2,
+ NewT0, T1, T2, T3, Tout, RH)
+ ;
+ RHT0 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
RH = no
+ )
;
- T1 = empty,
- error("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 = no
- ).
-
-:- 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), bool).
-%:- 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) :-
+ Result0 = (=),
+ ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
(
- % 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 = no
+ RHT1 = yes,
+ fix_4node_t1(ST1K, ST1V, K1, V1, K2, V2,
+ T0, NewT1, T2, T3, Tout, RH)
;
- % 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),
+ RHT1 = no,
+ Tout = four(ST1K, ST1V, K1, V1, K2, V2,
+ T0, NewT1, T2, T3),
RH = no
+ )
;
- % 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),
+ % T1 must be empty.
+ Tout = three(K1, V1, K2, V2, T0, T2, T3),
RH = no
+ )
;
- T2 = empty,
- error("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 = no
- ).
-
-:- 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), bool).
-%:- 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) :-
+ Result0 = (>),
+ tree234.delete_2(T1, K, NewT1, RHT1),
(
- % 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),
+ RHT1 = yes,
+ fix_4node_t1(K0, V0, K1, V1, K2, V2,
+ T0, NewT1, T2, T3, Tout, RH)
+ ;
+ RHT1 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3),
RH = no
+ )
+ )
;
- % 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),
+ Result1 = (=),
+ ( tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) ->
+ (
+ RHT2 = yes,
+ fix_4node_t2(K0, V0, ST2K, ST2V, K2, V2,
+ T0, T1, NewT2, T3, Tout, RH)
+ ;
+ RHT2 = no,
+ Tout = four(K0, V0, ST2K, ST2V, K2, V2,
+ T0, T1, NewT2, T3),
RH = no
+ )
;
- % 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),
+ % T2 must be empty
+ Tout = three(K0, V0, K2, V2, T0, T1, T3),
RH = no
+ )
;
- T3 = empty,
- error("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 = no
- ).
-
-:- 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), bool).
-%:- 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) :-
+ Result1 = (>),
+ compare(Result2, K, K2),
(
- % 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),
+ Result2 = (<),
+ tree234.delete_2(T2, K, NewT2, RHT2),
+ (
+ RHT2 = yes,
+ fix_4node_t2(K0, V0, K1, V1, K2, V2,
+ T0, T1, NewT2, T3, Tout, RH)
+ ;
+ RHT2 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3),
RH = no
+ )
;
- % 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),
+ Result2 = (=),
+ ( tree234.remove_smallest_2(T3, ST3K, ST3V, NewT3, RHT3) ->
+ (
+ RHT3 = yes,
+ fix_4node_t3(K0, V0, K1, V1, ST3K, ST3V,
+ T0, T1, T2, NewT3, Tout, RH)
+ ;
+ RHT3 = no,
+ Tout = four(K0, V0, K1, V1, ST3K, ST3V,
+ T0, T1, T2, NewT3),
RH = no
+ )
;
- % 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),
+ % T3 must be empty
+ Tout = three(K0, V0, K1, V1, T0, T1, T2),
RH = no
+ )
;
- T2 = empty,
- error("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 = no
- ).
-
-%------------------------------------------------------------------------------%
-
-tree234.keys(Tree, Keys) :-
- tree234.keys_2(Tree, [], Keys).
-
-:- pred tree234.keys_2(tree234(K, V), list(K), list(K)).
-:- mode tree234.keys_2(in, in, out) is det.
+ Result2 = (>),
+ tree234.delete_2(T3, K, NewT3, RHT3),
+ (
+ RHT3 = yes,
+ fix_4node_t3(K0, V0, K1, V1, K2, V2,
+ T0, T1, T2, NewT3, Tout, RH)
+ ;
+ RHT3 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3),
+ RH = no
+ )
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+
+tree234.remove(K, V, Tin, Tout) :-
+ % We use the same algorithm as tree234.delete.
+ tree234.remove_2(Tin, K, V, Tout, _).
+
+:- pred tree234.remove_2(tree234(K, V), K, V, tree234(K, V), bool).
+%:- mode tree234.remove_2(di, in, uo, uo, out) is semidet.
+:- mode tree234.remove_2(in, in, out, out, out) is semidet.
+
+tree234.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 = yes,
+ fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
+ ;
+ RHT0 = no,
+ Tout = two(K0, V0, NewT0, T1),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
+ (
+ RHT1 = yes,
+ fix_2node_t1(ST1K, ST1V, T0, NewT1, Tout, RH)
+ ;
+ RHT1 = no,
+ Tout = two(ST1K, ST1V, T0, NewT1),
+ RH = no
+ )
+ ;
+ % T1 must be empty.
+ Tout = T0,
+ RH = yes
+ ),
+ V = V0
+ ;
+ Result0 = (>),
+ tree234.remove_2(T1, K, V, NewT1, RHT1),
+ (
+ RHT1 = yes,
+ fix_2node_t1(K0, V0, T0, NewT1, Tout, RH)
+ ;
+ RHT1 = no,
+ Tout = two(K0, V0, T0, NewT1),
+ RH = no
+ )
+ )
+ ;
+ Tin = three(K0, V0, K1, V1, T0, T1, T2),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ tree234.remove_2(T0, K, V, NewT0, RHT0),
+ (
+ RHT0 = yes,
+ fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
+ ;
+ RHT0 = no,
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
+ (
+ RHT1 = yes,
+ fix_3node_t1(ST1K, ST1V, K1, V1, T0, NewT1, T2, Tout, RH)
+ ;
+ RHT1 = no,
+ Tout = three(ST1K, ST1V, K1, V1, T0, NewT1, T2),
+ RH = no
+ )
+ ;
+ % T1 must be empty.
+ Tout = two(K1, V1, T0, T2),
+ RH = no
+ ),
+ V = V0
+ ;
+ Result0 = (>),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ tree234.remove_2(T1, K, V, NewT1, RHT1),
+ (
+ RHT1 = yes,
+ fix_3node_t1(K0, V0, K1, V1, T0, NewT1, T2, Tout, RH)
+ ;
+ RHT1 = no,
+ Tout = three(K0, V0, K1, V1, T0, NewT1, T2),
+ RH = no
+ )
+ ;
+ Result1 = (=),
+ ( tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) ->
+ (
+ RHT2 = yes,
+ fix_3node_t2(K0, V0, ST2K, ST2V,
+ T0, T1, NewT2, Tout, RH)
+ ;
+ RHT2 = no,
+ Tout = three(K0, V0, ST2K, ST2V, T0, T1, NewT2),
+ RH = no
+ )
+ ;
+ % T2 must be empty.
+ Tout = two(K0, V0, T0, T1),
+ RH = no
+ ),
+ V = V1
+ ;
+ Result1 = (>),
+ tree234.remove_2(T2, K, V, NewT2, RHT2),
+ (
+ RHT2 = yes,
+ fix_3node_t2(K0, V0, K1, V1, T0, T1, NewT2, Tout, RH)
+ ;
+ RHT2 = no,
+ Tout = three(K0, V0, K1, V1, T0, T1, NewT2),
+ RH = no
+ )
+ )
+ )
+ ;
+ 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 = yes,
+ fix_4node_t0(K0, V0, K1, V1, K2, V2,
+ NewT0, T1, T2, T3, Tout, RH)
+ ;
+ RHT0 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ ( tree234.remove_smallest_2(T1, ST1K, ST1V, NewT1, RHT1) ->
+ (
+ RHT1 = yes,
+ fix_4node_t1(ST1K, ST1V, K1, V1, K2, V2,
+ T0, NewT1, T2, T3, Tout, RH)
+ ;
+ RHT1 = no,
+ Tout = four(ST1K, ST1V, K1, V1, K2, V2,
+ T0, NewT1, T2, T3),
+ RH = no
+ )
+ ;
+ % T1 must be empty.
+ Tout = three(K1, V1, K2, V2, T0, T2, T3),
+ RH = no
+ ),
+ V = V0
+ ;
+ Result0 = (>),
+ tree234.remove_2(T1, K, V, NewT1, RHT1),
+ (
+ RHT1 = yes,
+ fix_4node_t1(K0, V0, K1, V1, K2, V2,
+ T0, NewT1, T2, T3, Tout, RH)
+ ;
+ RHT1 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, NewT1, T2, T3),
+ RH = no
+ )
+ )
+ ;
+ Result1 = (=),
+ ( tree234.remove_smallest_2(T2, ST2K, ST2V, NewT2, RHT2) ->
+ (
+ RHT2 = yes,
+ fix_4node_t2(K0, V0, ST2K, ST2V, K2, V2,
+ T0, T1, NewT2, T3, Tout, RH)
+ ;
+ RHT2 = no,
+ Tout = four(K0, V0, ST2K, ST2V, K2, V2, T0, T1, NewT2, T3),
+ RH = no
+ )
+ ;
+ % T2 must be empty.
+ Tout = three(K0, V0, K2, V2, T0, T1, T3),
+ RH = no
+ ),
+ V = V1
+ ;
+ Result1 = (>),
+ compare(Result2, K, K2),
+ (
+ Result2 = (<),
+ tree234.remove_2(T2, K, V, NewT2, RHT2),
+ (
+ RHT2 = yes,
+ fix_4node_t2(K0, V0, K1, V1, K2, V2,
+ T0, T1, NewT2, T3, Tout, RH)
+ ;
+ RHT2 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, NewT2, T3),
+ RH = no
+ )
+ ;
+ Result2 = (=),
+ ( tree234.remove_smallest_2(T3, ST3K, ST3V, NewT3, RHT3) ->
+ (
+ RHT3 = yes,
+ fix_4node_t3(K0, V0, K1, V1, ST3K, ST3V,
+ T0, T1, T2, NewT3, Tout, RH)
+ ;
+ RHT3 = no,
+ Tout = four(K0, V0, K1, V1, ST3K, ST3V,
+ T0, T1, T2, NewT3),
+ RH = no
+ )
+ ;
+ % T3 must be empty.
+ Tout = three(K0, V0, K1, V1, T0, T1, T2),
+ RH = no
+ ),
+ V = V2
+ ;
+ Result2 = (>),
+ tree234.remove_2(T3, K, V, NewT3, RHT3),
+ (
+ RHT3 = yes,
+ fix_4node_t3(K0, V0, K1, V1, K2, V2,
+ T0, T1, T2, NewT3, Tout, RH)
+ ;
+ RHT3 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, NewT3),
+ RH = no
+ )
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+
+ % The algorithm we use similar to tree234.delete, except that we
+ % always go down the left subtree.
+
+tree234.remove_smallest(K, V, Tin, Tout) :-
+ tree234.remove_smallest_2(Tin, K, V, Tout, _).
+
+:- pred tree234.remove_smallest_2(tree234(K, V), K, V, tree234(K, V), bool).
+%:- mode tree234.remove_smallest_2(di, uo, uo, uo, out) is semidet.
+:- mode tree234.remove_smallest_2(in, out, out, out, out) is semidet.
+
+tree234.remove_smallest_2(Tin, K, V, Tout, RH) :-
+ (
+ Tin = empty,
+ fail
+ ;
+ Tin = two(K0, V0, T0, T1),
+ ( T0 = empty ->
+ K = K0,
+ V = V0,
+ Tout = T1,
+ RH = yes
+ ;
+ tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
+ (
+ RHT0 = yes,
+ fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
+ ;
+ RHT0 = no,
+ Tout = two(K0, V0, NewT0, T1),
+ RH = no
+ )
+ )
+ ;
+ Tin = three(K0, V0, K1, V1, T0, T1, T2),
+ ( T0 = empty ->
+ K = K0,
+ V = V0,
+ Tout = two(K1, V1, T1, T2),
+ RH = no
+ ;
+ tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
+ (
+ RHT0 = yes,
+ fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2, Tout, RH)
+ ;
+ RHT0 = no,
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
+ RH = no
+ )
+ )
+ ;
+ Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ ( T0 = empty ->
+ K = K0,
+ V = V0,
+ Tout = three(K1, V1, K2, V2, T1, T2, T3),
+ RH = no
+ ;
+ tree234.remove_smallest_2(T0, K, V, NewT0, RHT0),
+ (
+ RHT0 = yes,
+ fix_4node_t0(K0, V0, K1, V1, K2, V2,
+ NewT0, T1, T2, T3, Tout, RH)
+ ;
+ RHT0 = no,
+ Tout = four(K0, V0, K1, V1, K2, V2, NewT0, T1, T2, T3),
+ RH = no
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+%
+% 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), bool).
+:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = yes
+ ;
+ T1 = empty,
+ unexpected($module, $pred, "unbalanced 234 tree")
+ % Tout = two(K0, V0, T0, T1),
+ % RH = yes
+ ).
+
+:- pred fix_2node_t1(K, V, tree234(K, V), tree234(K, V), tree234(K, V), bool).
+:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = yes
+ ;
+ T0 = empty,
+ unexpected($module, $pred, "unbalanced 234 tree")
+ % Tout = two(K0, V0, T0, T1),
+ % RH = yes
+ ).
+
+:- pred fix_3node_t0(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
+ tree234(K, V), bool).
+:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = no
+ ;
+ T1 = empty,
+ unexpected($module, $pred, "unbalanced 234 tree")
+ % Tout = three(K0, V0, K1, V1, T0, T1, T2),
+ % The heights of T1 and T2 are unchanged
+ % RH = no
+ ).
+
+:- pred fix_3node_t1(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
+ tree234(K, V), bool).
+%:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = no
+ ;
+ T0 = empty,
+ unexpected($module, $pred, "unbalanced 234 tree")
+ % Tout = three(K0, V0, K1, V1, T0, T1, T2),
+ % The heights of T0 and T2 are unchanged
+ % RH = no
+ ).
+
+:- pred fix_3node_t2(K, V, K, V, tree234(K, V), tree234(K, V), tree234(K, V),
+ tree234(K, V), bool).
+%:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = no
+ ;
+ T1 = empty,
+ unexpected($module, $pred, "unbalanced 234 tree")
+ % Tout = three(K0, V0, K1, V1, T0, T1, T2),
+ % The heights of T0 and T1 are unchanged
+ % RH = no
+ ).
+
+:- 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), bool).
+%:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = no
+ ;
+ T1 = empty,
+ unexpected($module, $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 = no
+ ).
+
+:- 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), bool).
+%:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = no
+ ;
+ T2 = empty,
+ unexpected($module, $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 = no
+ ).
+
+:- 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), bool).
+%:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = no
+ ;
+ T3 = empty,
+ unexpected($module, $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 = no
+ ).
+
+:- 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), bool).
+%:- 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 = no
+ ;
+ % 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 = no
+ ;
+ % 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 = no
+ ;
+ T2 = empty,
+ unexpected($module, $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 = no
+ ).
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+tree234.keys(T) = Ks :-
+ tree234.keys(T, Ks).
+
+tree234.keys(Tree, Keys) :-
+ tree234.keys_acc(Tree, [], Keys).
+
+:- pred tree234.keys_acc(tree234(K, V), list(K), list(K)).
+:- mode tree234.keys_acc(in, in, out) is det.
+
+tree234.keys_acc(empty, List, List).
+tree234.keys_acc(two(K0, _V0, T0, T1), L0, L) :-
+ tree234.keys_acc(T1, L0, L1),
+ tree234.keys_acc(T0, [K0 | L1], L).
+tree234.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).
+tree234.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).
+
+%------------------------------------------------------------------------------%
+
+tree234.values(T) = Vs :-
+ tree234.values(T, Vs).
+
+tree234.values(Tree, Values) :-
+ tree234.values_acc(Tree, [], Values).
+
+:- pred tree234.values_acc(tree234(K, V), list(V), list(V)).
+:- mode tree234.values_acc(in, in, out) is det.
+
+tree234.values_acc(empty, List, List).
+tree234.values_acc(two(_K0, V0, T0, T1), L0, L) :-
+ tree234.values_acc(T1, L0, L1),
+ tree234.values_acc(T0, [V0 | L1], L).
+tree234.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).
+tree234.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).
+
+%------------------------------------------------------------------------------%
+
+tree234.keys_and_values(Tree, Keys, Values) :-
+ tree234.keys_and_values_acc(Tree, [], Keys, [], Values).
+
+:- pred tree234.keys_and_values_acc(tree234(K, V)::in,
+ list(K)::in, list(K)::out, list(V)::in, list(V)::out) is det.
+
+tree234.keys_and_values_acc(empty, !Keys, !Values).
+tree234.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).
+tree234.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).
+tree234.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).
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+tree234.count(T) = N :-
+ tree234.count(T, N).
+
+tree234.count(empty, 0).
+tree234.count(two(_, _, T0, T1), N) :-
+ tree234.count(T0, N0),
+ tree234.count(T1, N1),
+ N = 1 + N0 + N1.
+tree234.count(three(_, _, _, _, T0, T1, T2), N) :-
+ tree234.count(T0, N0),
+ tree234.count(T1, N1),
+ tree234.count(T2, N2),
+ N = 2 + N0 + N1 + N2.
+tree234.count(four(_, _, _, _, _, _, T0, T1, T2, T3), N) :-
+ tree234.count(T0, N0),
+ tree234.count(T1, N1),
+ tree234.count(T2, N2),
+ tree234.count(T3, N3),
+ N = 3 + N0 + N1 + N2 + N3.
+
+%-----------------------------------------------------------------------------%
+
+tree234.tree234_to_assoc_list(T) = AL :-
+ tree234.tree234_to_assoc_list(T, AL).
+
+tree234.tree234_to_assoc_list(Tree, AssocList) :-
+ tree234.tree234_to_assoc_list_acc(Tree, [], AssocList).
+
+:- pred tree234.tree234_to_assoc_list_acc(tree234(K, V)::in,
+ assoc_list(K, V)::in, assoc_list(K, V)::out) is det.
+
+tree234.tree234_to_assoc_list_acc(empty, L, L).
+tree234.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.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.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).
+
+%------------------------------------------------------------------------------%
+
+tree234.assoc_list_to_tree234(AL) = T :-
+ tree234.assoc_list_to_tree234(AL, T).
-tree234.keys_2(empty, List, List).
-tree234.keys_2(two(K0, _V0, T0, T1), L0, L) :-
- tree234.keys_2(T1, L0, L1),
- tree234.keys_2(T0, [K0 | L1], L).
-tree234.keys_2(three(K0, _V0, K1, _V1, T0, T1, T2), L0, L) :-
- tree234.keys_2(T2, L0, L1),
- tree234.keys_2(T1, [K1 | L1], L2),
- tree234.keys_2(T0, [K0 | L2], L).
-tree234.keys_2(four(K0, _V0, K1, _V1, K2, _V2, T0, T1, T2, T3), L0, L) :-
- tree234.keys_2(T3, L0, L1),
- tree234.keys_2(T2, [K2 | L1], L2),
- tree234.keys_2(T1, [K1 | L2], L3),
- tree234.keys_2(T0, [K0 | L3], L).
+tree234.assoc_list_to_tree234(AssocList, Tree) :-
+ tree234.assoc_list_to_tree234_acc(AssocList, empty, Tree).
+
+:- pred tree234.assoc_list_to_tree234_acc(assoc_list(K, V)::in,
+ tree234(K, V)::in, tree234(K, V)::out) is det.
+
+tree234.assoc_list_to_tree234_acc([], Tree, Tree).
+tree234.assoc_list_to_tree234_acc([K - V | Rest], !Tree) :-
+ tree234.set(K, V, !Tree),
+ tree234.assoc_list_to_tree234_acc(Rest, !Tree).
%------------------------------------------------------------------------------%
-tree234.values(Tree, Values) :-
- tree234.values_2(Tree, [], Values).
+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),
+ trace [compiletime(flag("tree234_sanity_checks"))] (
+ expect(unify(LeftOver, []), $module, $pred, "leftovers")
+ )
+ ).
-:- pred tree234.values_2(tree234(K, V), list(V), list(V)).
-:- mode tree234.values_2(in, in, out) is det.
+:- 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.
-tree234.values_2(empty, List, List).
-tree234.values_2(two(_K0, V0, T0, T1), L0, L) :-
- tree234.values_2(T1, L0, L1),
- tree234.values_2(T0, [V0 | L1], L).
-tree234.values_2(three(_K0, V0, _K1, V1, T0, T1, T2), L0, L) :-
- tree234.values_2(T2, L0, L1),
- tree234.values_2(T1, [V1 | L1], L2),
- tree234.values_2(T0, [V0 | L2], L).
-tree234.values_2(four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3), L0, L) :-
- tree234.values_2(T3, L0, L1),
- tree234.values_2(T2, [V2 | L1], L2),
- tree234.values_2(T1, [V1 | L2], L3),
- tree234.values_2(T0, [V0 | L3], L).
+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 = [],
+ unexpected($module, $pred, "len 1 nil")
+ )
+ ; Len = 2 ->
+ trace [compiletime(flag("tree234_sanity_checks"))] (
+ expect(unify(Level0, 1), $module, $pred,
+ "Len = 2 but Level != 1")
+ ),
+ (
+ !.List = [K1 - V1, K2 - V2 | !:List],
+ Tree = three(K1, V1, K2, V2, empty, empty, empty)
+ ;
+ !.List = [_],
+ unexpected($module, $pred, "len 2 one")
+ ;
+ !.List = [],
+ unexpected($module, $pred, "len 2 nil")
+ )
+ ;
+ unexpected($module, $pred, "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
+ ;
+ trace [compiletime(flag("tree234_sanity_checks"))] (
+ expect(unify(Diff, 2), $module, $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.format("splitting %d into three: %d, %d, %d\n",
+ [i(Len), i(SubLen1), i(SubLen2), i(SubLen3)], !IO)
+ ),
-tree234.keys_and_values(Tree, Keys, Values) :-
- tree234.keys_and_values_2(Tree, [], Keys, [], Values).
+ do_from_sorted_assoc_list(SubLen1, !List, Level, AllThrees,
+ SubTree1),
+ (
+ !.List = [K1 - V1 | !:List]
+ ;
+ !.List = [],
+ unexpected($module, $pred, "tree K1 V1 nil")
+ ),
+ do_from_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
+ SubTree2),
+ (
+ !.List = [K2 - V2 | !:List]
+ ;
+ !.List = [],
+ unexpected($module, $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.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
+ ;
+ trace [compiletime(flag("tree234_sanity_checks"))] (
+ expect(unify(Diff, 1), $module, $pred, "Diff != 1")
+ ),
+ % Len = BaseSubLen * 2 + 1:
+ % (BaseSubLen) + 1 + (BaseSubLen)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen
+ ),
-:- pred tree234.keys_and_values_2(tree234(K, V)::in, list(K)::in, list(K)::out,
- list(V)::in, list(V)::out) is det.
+ 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)
+ ),
-tree234.keys_and_values_2(empty, !Keys, !Values).
-tree234.keys_and_values_2(two(K0, V0, T0, T1), !Keys, !Values) :-
- tree234.keys_and_values_2(T1, !Keys, !Values),
- !:Keys = [K0 | !.Keys],
- !:Values = [V0 | !.Values],
- tree234.keys_and_values_2(T0, !Keys, !Values).
-tree234.keys_and_values_2(three(K0, V0, K1, V1, T0, T1, T2), !Keys, !Values) :-
- tree234.keys_and_values_2(T2, !Keys, !Values),
- !:Keys = [K1 | !.Keys],
- !:Values = [V1 | !.Values],
- tree234.keys_and_values_2(T1, !Keys, !Values),
- !:Keys = [K0 | !.Keys],
- !:Values = [V0 | !.Values],
- tree234.keys_and_values_2(T0, !Keys, !Values).
-tree234.keys_and_values_2(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
- !Keys, !Values) :-
- tree234.keys_and_values_2(T3, !Keys, !Values),
- !:Keys = [K2 | !.Keys],
- !:Values = [V2 | !.Values],
- tree234.keys_and_values_2(T2, !Keys, !Values),
- !:Keys = [K1 | !.Keys],
- !:Values = [V1 | !.Values],
- tree234.keys_and_values_2(T1, !Keys, !Values),
- !:Keys = [K0 | !.Keys],
- !:Values = [V0 | !.Values],
- tree234.keys_and_values_2(T0, !Keys, !Values).
+ do_from_sorted_assoc_list(SubLen1, !List, Level, AllThrees,
+ SubTree1),
+ (
+ !.List = [K1 - V1 | !:List]
+ ;
+ !.List = [],
+ unexpected($module, $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.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),
+ trace [compiletime(flag("tree234_sanity_checks"))] (
+ expect(unify(LeftOver, []), $module, $pred, "leftovers")
+ )
+ ).
-tree234.assoc_list_to_tree234(AssocList, Tree) :-
- tree234.assoc_list_to_tree234_2(AssocList, empty, Tree).
+:- 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.
-:- pred tree234.assoc_list_to_tree234_2(assoc_list(K, V)::in,
- tree234(K, V)::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 = [],
+ unexpected($module, $pred, "len 1 nil")
+ )
+ ; Len = 2 ->
+ trace [compiletime(flag("tree234_sanity_checks"))] (
+ expect(unify(Level0, 1), $module, $pred,
+ "Len = 2 but Level != 1")
+ ),
+ (
+ !.List = [K2 - V2, K1 - V1 | !:List],
+ Tree = three(K1, V1, K2, V2, empty, empty, empty)
+ ;
+ !.List = [_],
+ unexpected($module, $pred, "len 2 one")
+ ;
+ !.List = [],
+ unexpected($module, $pred, "len 2 nil")
+ )
+ ;
+ unexpected($module, $pred, "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
+ ;
+ trace [compiletime(flag("tree234_sanity_checks"))] (
+ expect(unify(Diff, 2), $module, $pred, "Diff != 2")
+ ),
+ % Len = BaseSubLen * 3 + 2:
+ % (BaseSubLen) + 1 + (BaseSubLen) + 1 + (BaseSubLen)
+ SubLen1 = BaseSubLen,
+ SubLen2 = BaseSubLen,
+ SubLen3 = BaseSubLen
+ ),
-tree234.assoc_list_to_tree234_2([], Tree, Tree).
-tree234.assoc_list_to_tree234_2([K - V | Rest], !Tree) :-
- tree234.set(K, V, !Tree),
- tree234.assoc_list_to_tree234_2(Rest, !Tree).
+ 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 = [],
+ unexpected($module, $pred, "tree K2 V2 nil")
+ ),
+ do_from_rev_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
+ SubTree2),
+ (
+ !.List = [K1 - V1 | !:List]
+ ;
+ !.List = [],
+ unexpected($module, $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.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
+ ;
+ trace [compiletime(flag("tree234_sanity_checks"))] (
+ expect(unify(Diff, 1), $module, $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.format("splitting %d into two: %d, %d\n",
+ [i(Len), i(SubLen1), i(SubLen2)], !IO)
+ ),
-tree234.tree234_to_assoc_list(Tree, AssocList) :-
- tree234.tree234_to_assoc_list_2(Tree, [], AssocList).
+ do_from_rev_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
+ SubTree2),
+ (
+ !.List = [K1 - V1 | !:List]
+ ;
+ !.List = [],
+ unexpected($module, $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.format("tree for %d\n", [i(Len)], !IO),
+ io.write(Tree, !IO),
+ io.nl(!IO)
+ )
+ )
+ ).
-:- pred tree234.tree234_to_assoc_list_2(tree234(K, V)::in,
- assoc_list(K, V)::in, assoc_list(K, V)::out) is det.
+:- pred find_level(int::in, int::in, int::out,
+ int::in, int::out) is det.
-tree234.tree234_to_assoc_list_2(empty, List, List).
-tree234.tree234_to_assoc_list_2(two(K0, V0, T0, T1), L0, L) :-
- tree234.tree234_to_assoc_list_2(T1, L0, L1),
- tree234.tree234_to_assoc_list_2(T0, [K0 - V0 | L1], L).
-tree234.tree234_to_assoc_list_2(three(K0, V0, K1, V1, T0, T1, T2), L0, L) :-
- tree234.tree234_to_assoc_list_2(T2, L0, L1),
- tree234.tree234_to_assoc_list_2(T1, [K1 - V1 | L1], L2),
- tree234.tree234_to_assoc_list_2(T0, [K0 - V0 | L2], L).
-tree234.tree234_to_assoc_list_2(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
- L0, L) :-
- tree234.tree234_to_assoc_list_2(T3, L0, L1),
- tree234.tree234_to_assoc_list_2(T2, [K2 - V2 | L1], L2),
- tree234.tree234_to_assoc_list_2(T1, [K1 - V1 | L2], L3),
- tree234.tree234_to_assoc_list_2(T0, [K0 - V0 | L3], L).
+find_level(Len, !Level, !AllThrees) :-
+ ( Len =< !.AllThrees ->
+ true
+ ;
+ !:Level = !.Level + 1,
+ !:AllThrees = !.AllThrees * 3 + 2,
+ find_level(Len, !Level, !AllThrees)
+ ).
%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+tree234.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).
tree234.foldl(_Pred, empty, !A).
tree234.foldl(Pred, two(K, V, T0, T1), !A) :-
@@ -2815,6 +3641,10 @@
%------------------------------------------------------------------------------%
+tree234.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).
+
tree234.foldr(_Pred, empty, !A).
tree234.foldr(Pred, two(K, V, T0, T1), !A) :-
tree234.foldr(Pred, T1, !A),
@@ -2898,6 +3728,11 @@
tree234.foldr4(Pred, T0, !A, !B, !C, !D).
%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+tree234.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).
tree234.map_values(_Pred, empty, empty).
tree234.map_values(Pred, Tree0, Tree) :-
@@ -2925,6 +3760,10 @@
tree234.map_values(Pred, Right0, Right),
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
+tree234.map_values_only(F, T1) = T2 :-
+ P = (pred(Y::in, Z::out) is det :- Z = F(Y) ),
+ tree234.map_values_only(P, T1, T2).
+
tree234.map_values_only(_Pred, empty, empty).
tree234.map_values_only(Pred, Tree0, Tree) :-
Tree0 = two(K0, V0, Left0, Right0),
@@ -2952,6 +3791,7 @@
Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
tree234.map_foldl(_Pred, empty, empty, !A).
tree234.map_foldl(Pred, Tree0, Tree, !A) :-
@@ -3085,445 +3925,110 @@
tree234.map_values_foldl3(_Pred, empty, empty, !A, !B, !C).
tree234.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).
-tree234.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).
-tree234.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).
-
-%------------------------------------------------------------------------------%
-
-tree234.count(empty, 0).
-tree234.count(two(_, _, T0, T1), N) :-
- tree234.count(T0, N0),
- tree234.count(T1, N1),
- N = 1 + N0 + N1.
-tree234.count(three(_, _, _, _, T0, T1, T2), N) :-
- tree234.count(T0, N0),
- tree234.count(T1, N1),
- tree234.count(T2, N2),
- N = 2 + N0 + N1 + N2.
-tree234.count(four(_, _, _, _, _, _, T0, T1, T2, T3), N) :-
- tree234.count(T0, N0),
- tree234.count(T1, N1),
- tree234.count(T2, N2),
- tree234.count(T3, N3),
- N = 3 + N0 + N1 + N2 + N3.
-
-%-----------------------------------------------------------------------------%
-%-----------------------------------------------------------------------------%
-% Ralph Becket <rwab1 at cl.cam.ac.uk> 30/04/99
-% Function forms added.
-
-tree234.init = T :-
- tree234.init(T).
-
-tree234.lookup(T, K) = V :-
- tree234.lookup(T, K, V).
-
-tree234.set(!.T, K, V) = !:T :-
- tree234.set(K, V, !T).
-
-tree234.delete(!.T, K) = !:T :-
- tree234.delete(K, !T).
-
-tree234.keys(T) = Ks :-
- tree234.keys(T, Ks).
-
-tree234.values(T) = Vs :-
- tree234.values(T, Vs).
-
-tree234.count(T) = N :-
- tree234.count(T, N).
-
-tree234.assoc_list_to_tree234(AL) = T :-
- tree234.assoc_list_to_tree234(AL, T).
-
-tree234.tree234_to_assoc_list(T) = AL :-
- tree234.tree234_to_assoc_list(T, AL).
-
-tree234.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).
-
-tree234.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).
-
-tree234.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).
-
-tree234.map_values_only(F, T1) = T2 :-
- P = (pred(Y::in, Z::out) is det :- Z = F(Y) ),
- tree234.map_values_only(P, T1, T2).
-
-%-----------------------------------------------------------------------------%
-
- % The default pretty_printer formatting for key_value_pair will do what
- % we want.
- %
-:- type key_value_pair(K, V)
- ---> (K -> V).
-
-tree234_to_doc(T) =
- indent([
- str("map(["),
- tree234_to_doc_2(tree234_to_lazy_list(T, empty)),
- str("])")
- ]).
-
-:- func tree234_to_doc_2(lazy_list(K, V)) = doc.
-
-tree234_to_doc_2(empty) = str("").
-tree234_to_doc_2(lazy_cons(K, V, Susp)) = Doc :-
- LL = apply(Susp),
- (
- LL = empty,
- Doc = group([nl, format_arg(format((K -> V)))])
- ;
- LL = lazy_cons(_, _, _),
- Doc = docs([
- group([nl, format_arg(format((K -> V))), str(", ")]),
- format_susp((func) = tree234_to_doc_2(LL))
- ])
- ).
-
-%-----------------------------------------------------------------------------%
-
-:- type lazy_list(K, V)
- ---> empty
- ; lazy_cons(K, V, (func) = lazy_list(K, V)).
-
-:- func tree234_to_lazy_list(tree234(K, V), lazy_list(K, V)) = lazy_list(K, V).
-
-tree234_to_lazy_list(empty, LL) = LL.
-tree234_to_lazy_list(two(K1, V1, T1, T2), LL) =
- tree234_to_lazy_list(T1,
- 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,
- 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,
- lazy_cons(K1, V1,
- (func) = tree234_to_lazy_list(
- 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
- ),
+ 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).
+tree234.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).
+tree234.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).
- 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
- ),
+ % The default pretty_printer formatting for key_value_pair will do what
+ % we want.
+ %
+:- type key_value_pair(K, V)
+ ---> (K -> V).
- 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)
- ),
+tree234_to_doc(T) =
+ indent([
+ str("map(["),
+ tree234_to_doc_2(tree234_to_lazy_list(T, empty)),
+ str("])")
+ ]).
- do_from_sorted_assoc_list(SubLen1, !List, Level, AllThrees,
- SubTree1),
+:- func tree234_to_doc_2(lazy_list(K, V)) = doc.
+
+tree234_to_doc_2(empty) = str("").
+tree234_to_doc_2(lazy_cons(K, V, Susp)) = Doc :-
+ LL = apply(Susp),
(
- !.List = [K1 - V1 | !:List]
+ LL = empty,
+ Doc = group([nl, format_arg(format((K -> V)))])
;
- !.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)
- )
- )
+ LL = lazy_cons(_, _, _),
+ Doc = docs([
+ group([nl, format_arg(format((K -> V))), str(", ")]),
+ format_susp((func) = tree234_to_doc_2(LL))
+ ])
).
-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.
+:- type lazy_list(K, V)
+ ---> empty
+ ; lazy_cons(K, V, (func) = lazy_list(K, V)).
-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
- ),
+:- func tree234_to_lazy_list(tree234(K, V), lazy_list(K, V)) = lazy_list(K, V).
- 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)
- ),
+tree234_to_lazy_list(empty, LL) = LL.
+tree234_to_lazy_list(two(K1, V1, T1, T2), LL) =
+ tree234_to_lazy_list(T1,
+ 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,
+ 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,
+ lazy_cons(K1, V1,
+ (func) = tree234_to_lazy_list(
+ three(K2, V2, K3, V3, T2, T3, T4), LL))).
- 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)
- ),
+find_min_size_based_on_depth(T, MinSize) :-
+ find_depth(T, Depth),
+ min_size_based_on_depth(Depth, MinSize).
- do_from_rev_sorted_assoc_list(SubLen2, !List, Level, AllThrees,
- SubTree2),
- (
- !.List = [K1 - V1 | !:List]
+:- pred min_size_based_on_depth(int::in, int::out) is det.
+
+min_size_based_on_depth(Depth, MinSize) :-
+ ( Depth = 0 ->
+ MinSize = 0
;
- !.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)
- )
- )
+ min_size_based_on_depth(Depth - 1, MinSizeBelow),
+ MinSize = MinSizeBelow * 2 + 1
).
-:- pred find_level(int::in, int::in, int::out,
- int::in, int::out) is det.
+:- pred find_depth(tree234(K, V)::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)
- ).
+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).
%-----------------------------------------------------------------------------%
Index: library/varset.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/varset.m,v
retrieving revision 1.91
diff -u -b -r1.91 varset.m
--- library/varset.m 25 Jul 2011 07:54:21 -0000 1.91
+++ library/varset.m 14 Jun 2012 03:28:10 -0000
@@ -89,6 +89,12 @@
:- pred varset.delete_vars(list(var(T))::in, varset(T)::in, varset(T)::out)
is det.
+ % Delete the names and values for a sorted list of variables.
+ %
+:- func varset.delete_sorted_vars(varset(T), list(var(T))) = varset(T).
+:- pred varset.delete_sorted_vars(list(var(T))::in,
+ varset(T)::in, varset(T)::out) is det.
+
% Return a list of all the variables in a varset.
%
:- func varset.vars(varset(T)) = list(var(T)).
@@ -350,17 +356,25 @@
%-----------------------------------------------------------------------------%
-varset.delete_var(Var, varset(MaxId, !.Names, !.Values),
- varset(MaxId, !:Names, !:Values)) :-
- map.delete(Var, !Names),
- map.delete(Var, !Values).
+varset.delete_var(DeleteVar, !VarSet) :-
+ !.VarSet = varset(MaxId, Names0, Values0),
+ map.delete(DeleteVar, Names0, Names),
+ map.delete(DeleteVar, Values0, Values),
+ !:VarSet = varset(MaxId, Names, Values).
%-----------------------------------------------------------------------------%
-varset.delete_vars([], !VarSet).
-varset.delete_vars([Var | Vars], !VarSet) :-
- varset.delete_var(Var, !VarSet),
- varset.delete_vars(Vars, !VarSet).
+varset.delete_vars(DeleteVars, !VarSet) :-
+ !.VarSet = varset(MaxId, Names0, Values0),
+ map.delete_list(DeleteVars, Names0, Names),
+ map.delete_list(DeleteVars, Values0, Values),
+ !:VarSet = varset(MaxId, Names, Values).
+
+varset.delete_sorted_vars(DeleteVars, !VarSet) :-
+ !.VarSet = varset(MaxId, Names0, Values0),
+ map.delete_sorted_list(DeleteVars, Names0, Names),
+ map.delete_sorted_list(DeleteVars, Values0, Values),
+ !:VarSet = varset(MaxId, Names, Values).
%-----------------------------------------------------------------------------%
@@ -711,6 +725,9 @@
varset.delete_vars(!.VS, Vs) = !:VS :-
varset.delete_vars(Vs, !VS).
+varset.delete_sorted_vars(!.VS, Vs) = !:VS :-
+ varset.delete_sorted_vars(Vs, !VS).
+
varset.vars(VS) = Vs :-
varset.vars(VS, Vs).
cvs diff: Diffing m4
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/appengine
cvs diff: Diffing samples/appengine/war
cvs diff: Diffing samples/appengine/war/WEB-INF
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/concurrency
cvs diff: Diffing samples/concurrency/dining_philosophers
cvs diff: Diffing samples/concurrency/midimon
cvs diff: Diffing samples/diff
cvs diff: Diffing samples/java_interface
cvs diff: Diffing samples/java_interface/java_calls_mercury
cvs diff: Diffing samples/java_interface/mercury_calls_java
cvs diff: Diffing samples/lazy_list
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/feedback
cvs diff: Diffing tests/feedback/mandelbrot
cvs diff: Diffing tests/feedback/mmc
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
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