[m-rev.] For review: added any_list, any_map, any_array, any_assoc_list to extras
Ralph Becket
rafe at cs.mu.OZ.AU
Fri Sep 9 16:10:13 AEST 2005
Estimated hours taken: 24
Add list, map, assoc_list, and array ADTs for collections of solver type
values.
extras/solver_types:
extras/solver_types/library:
extras/solver_types/library/Mmakefile:
extras/solver_types/library/any.m:
extras/solver_types/library/any_map.m:
extras/solver_types/library/any_array.m:
extras/solver_types/library/any_tree234.m:
extras/solver_types/library/any_assoc_list.m:
extras/solver_types/library/any_list.m:
Added.
extras/solver_types/library/any_util.m:
Defines unsafe_cast_to_ground/1 which is used very carefully
in any_{map,tree234,assoc_list}.m to cast polymorphic key
values from inst any to ground. This is necessary because
the code needs to compare key values, but they have a polymorphic type
and the compiler cannot statically infer that any = ground for
polymorphically typed variables.
Index: extras/solver_types/library/Mmakefile
===================================================================
RCS file: extras/solver_types/library/Mmakefile
diff -N extras/solver_types/library/Mmakefile
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ extras/solver_types/library/Mmakefile 9 Sep 2005 05:57:47 -0000
@@ -0,0 +1,21 @@
+#-----------------------------------------------------------------------------#
+# Copyright (C) 2000, 2002-2003 The University of Melbourne.
+# This file may only be copied under the terms of the GNU Library General
+# Public License - see the file COPYING.LIB in the Mercury distribution.
+#-----------------------------------------------------------------------------#
+
+INSTALL_PREFIX := $(INSTALL_PREFIX)/extras
+
+-include ../Mmake.params
+
+MAIN_TARGET = all
+
+all: libany
+
+depend: any.depend
+
+install: libany.install
+
+.PHONY: check
+check:
+ true
Index: extras/solver_types/library/any.m
===================================================================
RCS file: extras/solver_types/library/any.m
diff -N extras/solver_types/library/any.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ extras/solver_types/library/any.m 9 Sep 2005 05:58:33 -0000
@@ -0,0 +1,11 @@
+% This module is just used to collect the other any_* modules together
+% to form a library.
+%
+:- module any.
+:- interface.
+:- import_module any_array.
+:- import_module any_assoc_list.
+:- import_module any_list.
+:- import_module any_map.
+:- import_module any_tree234.
+:- import_module any_util.
Index: extras/solver_types/library/any_array.m
===================================================================
RCS file: extras/solver_types/library/any_array.m
diff -N extras/solver_types/library/any_array.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ extras/solver_types/library/any_array.m 9 Sep 2005 05:55:53 -0000
@@ -0,0 +1,895 @@
+%-----------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 1993-1995, 1997-2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+% any_array.m
+% Ralph Becket <rafe at cs.mu.oz.au>
+% Thu Sep 8 15:18:38 EST 2005
+%
+% A copy of array.m adapted for arrays of values with inst any.
+%
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- module any_array.
+:- interface.
+
+:- import_module any_list.
+:- import_module random.
+
+:- type any_array(T).
+
+:- inst any_array(I) == bound(any_array(I)).
+:- inst any_array == any_array(any).
+:- inst any_array_skel == any_array(free).
+
+ % XXX the current Mercury compiler doesn't support `ui' modes,
+ % so to work-around that problem, we currently don't use
+ % unique modes in this module.
+
+% :- inst uniq_any_array(I) == unique(any_array(I)).
+% :- inst uniq_any_array == uniq_any_array(unique).
+:- inst uniq_any_array(I) == bound(any_array(I)). % XXX work-around
+:- inst uniq_any_array == uniq_any_array(ground). % XXX work-around
+:- inst uniq_any_array_skel == uniq_any_array(free).
+
+:- mode any_array_di == di(uniq_any_array).
+:- mode any_array_uo == out(uniq_any_array).
+:- mode any_array_ui == in(uniq_any_array).
+
+% :- inst mostly_uniq_any_array(I) == mostly_unique(any_array(I)).
+% :- inst mostly_uniq_any_array == mostly_uniq_any_array(mostly_unique).
+:- inst mostly_uniq_any_array(I) == bound(any_array(I)). % XXX work-around
+:- inst mostly_uniq_any_array == mostly_uniq_any_array(ground). % XXX ditto.
+:- inst mostly_uniq_any_array_skel == mostly_uniq_any_array(free).
+
+:- mode any_array_mdi == mdi(mostly_uniq_any_array).
+:- mode any_array_muo == out(mostly_uniq_any_array).
+:- mode any_array_mui == in(mostly_uniq_any_array).
+
+ % An `any_array__index_out_of_bounds' is the exception thrown
+ % on out-of-bounds any_array accesses. The string describes
+ % the predicate or function reporting the error.
+:- type any_array__index_out_of_bounds
+ ---> any_array__index_out_of_bounds(string).
+
+%-----------------------------------------------------------------------------%
+
+ % any_array__make_empty_array(Array) creates an any_array of size zero
+ % starting at lower bound 0.
+ %
+:- pred any_array__make_empty_array(any_array(T)::any_array_uo) is det.
+:- func any_array__make_empty_array = (any_array(T)::any_array_uo) is det.
+
+ % any_array__init(Size, Init, Array) creates an any_array with bounds from
+ % 0 to Size-1, with each element initialized to Init.
+ %
+:- pred any_array__init(int, T, any_array(T)).
+:- mode any_array__init(in, ia, any_array_uo) is det.
+
+:- func any_array__init(int, T) = any_array(T).
+:- mode any_array__init(in, ia) = any_array_uo is det.
+
+ % any_array/1 is a function that constructs an any_array from a list.
+ % (It does the same thing as the predicate any_array__from_any_list/2.)
+ % The syntax `any_array([...])' is used to represent any_arrays
+ % for io__read, io__write, term_to_type, and type_to_term.
+ %
+:- func any_array(any_list(T)) = any_array(T).
+:- mode any_array(ia) = any_array_uo is det.
+
+%-----------------------------------------------------------------------------%
+
+ % any_array__min returns the lower bound of the any_array.
+ % Note: in this implementation, the lower bound is always zero.
+ %
+:- pred any_array__min(any_array(_T), int).
+:- mode any_array__min(any_array_ui, out) is det.
+
+:- func any_array__min(any_array(_T)) = int.
+:- mode any_array__min(any_array_ui) = out is det.
+
+:- func any_array__least_index(any_array(T)) = int.
+:- mode any_array__least_index(any_array_ui) = out is det.
+
+ % any_array__max returns the upper bound of the any_array.
+ %
+:- pred any_array__max(any_array(_T), int).
+:- mode any_array__max(any_array_ui, out) is det.
+
+:- func any_array__max(any_array(_T)) = int.
+:- mode any_array__max(any_array_ui) = out is det.
+
+:- func any_array__greatest_index(any_array(T)) = int.
+:- mode any_array__greatest_index(any_array_ui) = out is det.
+
+ % any_array__size returns the length of the any_array,
+ % i.e. upper bound - lower bound + 1.
+ %
+:- pred any_array__size(any_array(_T), int).
+:- mode any_array__size(any_array_ui, out) is det.
+
+:- func any_array__size(any_array(_T)) = int.
+:- mode any_array__size(any_array_ui) = out is det.
+
+ % any_array__bounds returns the upper and lower bounds of an any_array.
+ % Note: in this implementation, the lower bound is always zero.
+ %
+:- pred any_array__bounds(any_array(_T), int, int).
+:- mode any_array__bounds(any_array_ui, out, out) is det.
+
+ % any_array__in_bounds checks whether an index is in the bounds of an
+ % any_array.
+ %
+:- pred any_array__in_bounds(any_array(_T), int).
+:- mode any_array__in_bounds(any_array_ui, in) is semidet.
+
+%-----------------------------------------------------------------------------%
+
+ % any_array__lookup returns the Nth element of an any_array.
+ % Throws an exception if the index is out of bounds.
+ %
+:- pred any_array__lookup(any_array(T), int, T).
+:- mode any_array__lookup(any_array_ui, in, oa) is det.
+
+:- func any_array__lookup(any_array(T), int) = T.
+:- mode any_array__lookup(any_array_ui, in) = oa is det.
+
+ % any_array__semidet_lookup returns the Nth element of an any_array.
+ % It fails if the index is out of bounds.
+ %
+:- pred any_array__semidet_lookup(any_array(T), int, T).
+:- mode any_array__semidet_lookup(any_array_ui, in, oa) is semidet.
+
+ % any_array__set sets the nth element of an any_array, and returns the
+ % resulting any_array (good opportunity for destructive update ;-).
+ % Throws an exception if the index is out of bounds.
+ %
+:- pred any_array__set(any_array(T), int, T, any_array(T)).
+:- mode any_array__set(any_array_di, in, ia, any_array_uo) is det.
+
+:- func any_array__set(any_array(T), int, T) = any_array(T).
+:- mode any_array__set(any_array_di, in, ia) = any_array_uo is det.
+
+ % any_array__semidet_set sets the nth element of an any_array, and returns
+ % the resulting any_array. It fails if the index is out of bounds.
+ %
+:- pred any_array__semidet_set(any_array(T), int, T, any_array(T)).
+:- mode any_array__semidet_set(any_array_di, in, ia, any_array_uo) is semidet.
+
+ % any_array__slow_set sets the nth element of an any_array, and returns the
+ % resulting any_array. The initial any_array is not required to be unique,
+ % so the implementation may not be able to use destructive update.
+ % It is an error if the index is out of bounds.
+ %
+:- pred any_array__slow_set(any_array(T), int, T, any_array(T)).
+:- mode any_array__slow_set(any_array_ui, in, ia, any_array_uo) is det.
+
+:- func any_array__slow_set(any_array(T), int, T) = any_array(T).
+:- mode any_array__slow_set(any_array_ui, in, ia) = any_array_uo is det.
+
+ % any_array__semidet_slow_set sets the nth element of an any_array, and
+ % returns the resulting any_array. The initial any_array is not required to
+ % be unique, so the implementation may not be able to use destructive
+ % update. It fails if the index is out of bounds.
+ %
+:- pred any_array__semidet_slow_set(any_array(T), int, T, any_array(T)).
+:- mode any_array__semidet_slow_set(any_array_ui, in, ia, any_array_uo)
+ is semidet.
+
+ % Field selection for any_arrays.
+ % Array ^ elem(Index) = any_array__lookup(Array, Index).
+ %
+:- func any_array__elem(int, any_array(T)) = T.
+:- mode any_array__elem(in, any_array_ui) = oa is det.
+
+ % Field update for any_arrays.
+ % (Array ^ elem(Index) := Value) = any_array__set(Array, Index, Value).
+ %
+:- func 'any_array__elem :='(int, any_array(T), T) = any_array(T).
+:- mode 'any_array__elem :='(in, any_array_di, ia) = any_array_uo is det.
+
+%-----------------------------------------------------------------------------%
+
+ % any_array__copy(Array0, Array):
+ % Makes a new unique copy of an any_array.
+ %
+:- pred any_array__copy(any_array(T), any_array(T)).
+:- mode any_array__copy(any_array_ui, any_array_uo) is det.
+
+:- func any_array__copy(any_array(T)) = any_array(T).
+:- mode any_array__copy(any_array_ui) = any_array_uo is det.
+
+ % any_array__resize(Array0, Size, Init, Array):
+ % The any_array is expanded or shrunk to make it fit the new size `Size'.
+ % Any new entries are filled with `Init'.
+ %
+:- pred any_array__resize(any_array(T), int, T, any_array(T)).
+:- mode any_array__resize(any_array_di, in, ia, any_array_uo) is det.
+
+:- func any_array__resize(any_array(T), int, T) = any_array(T).
+:- mode any_array__resize(any_array_di, in, ia) = any_array_uo is det.
+
+ % any_array__shrink(Array0, Size, Array):
+ % The any_array is shrunk to make it fit the new size `Size'.
+ % Throws an exception if `Size' is larger than the size of `Array0'.
+ %
+:- pred any_array__shrink(any_array(T), int, any_array(T)).
+:- mode any_array__shrink(any_array_di, in, any_array_uo) is det.
+
+:- func any_array__shrink(any_array(T), int) = any_array(T).
+:- mode any_array__shrink(any_array_di, in) = any_array_uo is det.
+
+ % any_array__from_any_list takes a list, and returns an any_array
+ % containing those elements in the same order that they occurred in the
+ % list.
+ %
+:- pred any_array__from_any_list(any_list(T), any_array(T)).
+:- mode any_array__from_any_list(ia, any_array_uo) is det.
+
+:- func any_array__from_any_list(any_list(T)) = any_array(T).
+:- mode any_array__from_any_list(ia) = any_array_uo is det.
+
+ % any_array__to_any_list takes an any_array and returns an any_list
+ % containing the elements of the any_array in the same order that they
+ % occurred in the any_array.
+ %
+:- pred any_array__to_any_list(any_array(T), any_list(T)).
+:- mode any_array__to_any_list(any_array_ui, oa) is det.
+
+:- func any_array__to_any_list(any_array(T)) = any_list(T).
+:- mode any_array__to_any_list(any_array_ui) = oa is det.
+
+ % any_array__fetch_items takes an any_array and a lower and upper index,
+ % and places those items in the any_array between these indices into a list.
+ % It is an error if either index is out of bounds.
+ %
+:- pred any_array__fetch_items(any_array(T), int, int, any_list(T)).
+:- mode any_array__fetch_items(any_array_ui, in, in, oa) is det.
+
+:- func any_array__fetch_items(any_array(T), int, int) = any_list(T).
+:- mode any_array__fetch_items(any_array_ui, in, in) = oa is det.
+
+ % any_array__map(Closure, OldArray, NewArray) applies `Closure' to
+ % each of the elements of `OldArray' to create `NewArray'.
+ %
+:- pred any_array__map(pred(T1, T2), any_array(T1), any_array(T2)).
+:- mode any_array__map(pred(ia, oa) is det, any_array_di, any_array_uo) is det.
+
+:- func any_array__map(func(T1) = T2, any_array(T1)) = any_array(T2).
+:- mode any_array__map(func(ia) = oa is det, any_array_di) = any_array_uo
+ is det.
+
+ % any_array__foldl(Fn, Array, X) is equivalent to
+ % any_list__foldl(Fn, any_array__to_any_list(Array), X)
+ % but more efficient.
+ %
+:- func any_array__foldl(func(T1, T2) = T2, any_array(T1), T2) = T2.
+:- mode any_array__foldl(func(ia, in) = out is det, any_array_ui, in) = out
+ is det.
+:- mode any_array__foldl(func(ia, ia) = oa is det, any_array_ui, ia) = oa
+ is det.
+
+ % any_array__foldr(Fn, Array, X) is equivalent to
+ % list__foldr(Fn, any_array__to_any_list(Array), X)
+ % but more efficient.
+ %
+:- func any_array__foldr(func(T1, T2) = T2, any_array(T1), T2) = T2.
+:- mode any_array__foldr(func(ia, in) = out is det, any_array_ui, in) = out
+ is det.
+:- mode any_array__foldr(func(ia, ia) = oa is det, any_array_ui, ia) = oa
+ is det.
+
+ % any_array__random_permutation(A0, A, RS0, RS) permutes the elements in
+ % A0 given random seed RS0 and returns the permuted any_array in A
+ % and the next random seed in RS.
+ %
+:- pred any_array__random_permutation(any_array(T), any_array(T),
+ random__supply, random__supply).
+:- mode any_array__random_permutation(any_array_di, any_array_uo,
+ mdi, muo) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module exception.
+:- import_module int.
+:- import_module list.
+:- import_module require.
+:- import_module string.
+
+ % MR_ArrayPtr is defined in runtime/mercury_library_types.h.
+:- pragma foreign_type("C", any_array(T), "MR_ArrayPtr").
+
+%-----------------------------------------------------------------------------%
+
+:- pred bounds_checks is semidet.
+:- pragma inline(bounds_checks/0).
+
+:- pragma foreign_proc("C",
+ bounds_checks,
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+#ifdef ML_OMIT_ARRAY_BOUNDS_CHECKS
+ SUCCESS_INDICATOR = MR_FALSE;
+#else
+ SUCCESS_INDICATOR = MR_TRUE;
+#endif
+").
+
+:- pragma foreign_proc("C#",
+ bounds_checks,
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+#if ML_OMIT_ARRAY_BOUNDS_CHECKS
+ SUCCESS_INDICATOR = false;
+#else
+ SUCCESS_INDICATOR = true;
+#endif
+").
+
+:- pragma foreign_proc("Java",
+ bounds_checks,
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ // never do bounds checking for Java (throw exceptions instead)
+ succeeded = false;
+").
+
+%-----------------------------------------------------------------------------%
+
+:- pragma foreign_decl("C", "
+#include ""mercury_heap.h"" /* for MR_maybe_record_allocation() */
+#include ""mercury_library_types.h"" /* for MR_ArrayPtr */
+
+/*
+** We do not yet record term sizes for any_arrays in term size profiling
+** grades. Doing so would require
+**
+** - modifying ML_alloc_any_array to allocate an extra word for the size;
+** - modifying all the predicates that call ML_alloc_any_array to compute the
+** size of the any_array (the sum of the sizes of the elements and the size of
+** the any_array itself);
+** - modifying all the predicates that update any_array elements to compute the
+** difference between the sizes of the terms being added to and deleted from
+** the any_array, and updating the any_array size accordingly.
+*/
+
+#define ML_alloc_any_array(newarray, any_arraysize, proclabel) \
+ do { \
+ MR_Word newarray_word; \
+ MR_offset_incr_hp_msg(newarray_word, 0, (any_arraysize), \
+ proclabel, ""any_array:any_array/1""); \
+ (newarray) = (MR_ArrayPtr) newarray_word; \
+ } while (0)
+").
+
+:- pragma foreign_decl("C", "
+void ML_init_array(MR_ArrayPtr, MR_Integer size, MR_Word item);
+").
+
+:- pragma foreign_code("C", "
+/*
+** The caller is responsible for allocating the memory for the any_array.
+** This routine does the job of initializing the already-allocated memory.
+*/
+void
+ML_init_array(MR_ArrayPtr any_array, MR_Integer size, MR_Word item)
+{
+ MR_Integer i;
+
+ any_array->size = size;
+ for (i = 0; i < size; i++) {
+ any_array->elements[i] = item;
+ }
+}
+").
+
+any_array__init(Size, Item, Array) :-
+ ( Size < 0 ->
+ error("any_array__init: negative size")
+ ;
+ any_array__init_2(Size, Item, Array)
+ ).
+
+:- pred any_array__init_2(int, T, any_array(T)).
+:- mode any_array__init_2(in, ia, any_array_uo) is det.
+
+:- pragma foreign_proc("C",
+ any_array__init_2(Size::in, Item::ia, Array::any_array_uo),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ ML_alloc_any_array(Array, Size + 1, MR_PROC_LABEL);
+ ML_init_array(Array, Size, Item);
+").
+
+:- pragma foreign_proc("C",
+ any_array__make_empty_array(Array::any_array_uo),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ ML_alloc_any_array(Array, 1, MR_PROC_LABEL);
+ ML_init_array(Array, 0, 0);
+").
+
+%-----------------------------------------------------------------------------%
+
+:- pragma foreign_proc("C",
+ any_array__min(Array::any_array_ui, Min::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ /* Array not used */
+ Min = 0;
+").
+
+:- pragma foreign_proc("C",
+ any_array__max(Array::any_array_ui, Max::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ Max = Array->size - 1;
+").
+
+any_array__bounds(Array, Min, Max) :-
+ any_array__min(Array, Min),
+ any_array__max(Array, Max).
+
+%-----------------------------------------------------------------------------%
+
+:- pragma foreign_proc("C",
+ any_array__size(Array::any_array_ui, Max::out),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ Max = Array->size;
+").
+
+%-----------------------------------------------------------------------------%
+
+any_array__in_bounds(Array, Index) :-
+ any_array__bounds(Array, Min, Max),
+ Min =< Index, Index =< Max.
+
+any_array__semidet_lookup(Array, Index, Item) :-
+ ( any_array__in_bounds(Array, Index) ->
+ any_array__unsafe_lookup(Array, Index, Item)
+ ;
+ fail
+ ).
+
+any_array__semidet_set(Array0, Index, Item, Array) :-
+ ( any_array__in_bounds(Array0, Index) ->
+ any_array__unsafe_set(Array0, Index, Item, Array)
+ ;
+ fail
+ ).
+
+any_array__semidet_slow_set(Array0, Index, Item, Array) :-
+ ( any_array__in_bounds(Array0, Index) ->
+ any_array__slow_set(Array0, Index, Item, Array)
+ ;
+ fail
+ ).
+
+any_array__slow_set(Array0, Index, Item, Array) :-
+ any_array__copy(Array0, Array1),
+ any_array__set(Array1, Index, Item, Array).
+
+%-----------------------------------------------------------------------------%
+
+any_array__lookup(Array, Index, Item) :-
+ ( bounds_checks, \+ any_array__in_bounds(Array, Index) ->
+ out_of_bounds_error(Array, Index, "any_array__lookup")
+ ;
+ any_array__unsafe_lookup(Array, Index, Item)
+ ).
+
+:- pred any_array__unsafe_lookup(any_array(T), int, T).
+:- mode any_array__unsafe_lookup(any_array_ui, in, oa) is det.
+
+:- pragma foreign_proc("C",
+ any_array__unsafe_lookup(Array::any_array_ui, Index::in, Item::oa),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ Item = Array->elements[Index];
+").
+
+%-----------------------------------------------------------------------------%
+
+any_array__set(Array0, Index, Item, Array) :-
+ ( bounds_checks, \+ any_array__in_bounds(Array0, Index) ->
+ out_of_bounds_error(Array0, Index, "any_array__set")
+ ;
+ any_array__unsafe_set(Array0, Index, Item, Array)
+ ).
+
+:- pred any_array__unsafe_set(any_array(T), int, T, any_array(T)).
+:- mode any_array__unsafe_set(any_array_di, in, ia, any_array_uo) is det.
+
+:- pragma foreign_proc("C",
+ any_array__unsafe_set(Array0::any_array_di, Index::in, Item::ia,
+ Array::any_array_uo),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ Array0->elements[Index] = Item; /* destructive update! */
+ Array = Array0;
+").
+
+%-----------------------------------------------------------------------------%
+
+% lower bounds other than zero are not supported
+% % any_array__resize takes an any_array and new lower and upper bounds.
+% % the any_array is expanded or shrunk at each end to make it fit
+% % the new bounds.
+% :- pred any_array__resize(any_array(T), int, int, any_array(T)).
+% :- mode any_array__resize(in, in, in, out) is det.
+
+:- pragma foreign_decl("C", "
+void ML_resize_array(MR_ArrayPtr new_array, MR_ArrayPtr old_array,
+ MR_Integer any_array_size, MR_Word item);
+").
+
+:- pragma foreign_code("C", "
+/*
+** The caller is responsible for allocating the storage for the new any_array.
+** This routine does the job of copying the old any_array elements to the
+** new any_array, initializing any additional elements in the new any_array,
+** and deallocating the old any_array.
+*/
+void
+ML_resize_array(MR_ArrayPtr any_array, MR_ArrayPtr old_array,
+ MR_Integer any_array_size, MR_Word item)
+{
+ MR_Integer i;
+ MR_Integer elements_to_copy;
+
+ elements_to_copy = old_array->size;
+ if (elements_to_copy > any_array_size) {
+ elements_to_copy = any_array_size;
+ }
+
+ any_array->size = any_array_size;
+ for (i = 0; i < elements_to_copy; i++) {
+ any_array->elements[i] = old_array->elements[i];
+ }
+ for (; i < any_array_size; i++) {
+ any_array->elements[i] = item;
+ }
+
+ /*
+ ** Since the mode on the old any_array is `any_array_di', it is safe to
+ ** deallocate the storage for it.
+ */
+#ifdef MR_CONSERVATIVE_GC
+ GC_FREE(old_array);
+#endif
+}
+").
+
+:- pragma foreign_proc("C",
+ any_array__resize(Array0::any_array_di, Size::in, Item::ia,
+ Array::any_array_uo),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ if ((Array0)->size == Size) {
+ Array = Array0;
+ } else {
+ ML_alloc_any_array(Array, Size + 1, MR_PROC_LABEL);
+ ML_resize_array(Array, Array0, Size, Item);
+ }
+").
+
+%-----------------------------------------------------------------------------%
+
+:- pragma foreign_decl("C", "
+void ML_shrink_array(MR_ArrayPtr any_array, MR_ArrayPtr old_array,
+ MR_Integer any_array_size);
+").
+
+:- pragma foreign_code("C", "
+/*
+** The caller is responsible for allocating the storage for the new any_array.
+** This routine does the job of copying the old any_array elements to the
+** new any_array and deallocating the old any_array.
+*/
+void
+ML_shrink_array(MR_ArrayPtr any_array, MR_ArrayPtr old_array,
+ MR_Integer any_array_size)
+{
+ MR_Integer i;
+
+ any_array->size = any_array_size;
+ for (i = 0; i < any_array_size; i++) {
+ any_array->elements[i] = old_array->elements[i];
+ }
+
+ /*
+ ** Since the mode on the old any_array is `any_array_di', it is safe to
+ ** deallocate the storage for it.
+ */
+#ifdef MR_CONSERVATIVE_GC
+ GC_FREE(old_array);
+#endif
+}
+").
+
+any_array__shrink(Array0, Size, Array) :-
+ OldSize = any_array__size(Array0),
+ ( Size > OldSize ->
+ error("any_array__shrink: can't shrink to a larger size")
+ ; Size = OldSize ->
+ Array = Array0
+ ;
+ any_array__shrink_2(Array0, Size, Array)
+ ).
+
+:- pred any_array__shrink_2(any_array(T)::any_array_di, int::in,
+ any_array(T)::any_array_uo) is det.
+
+:- pragma foreign_proc("C",
+ any_array__shrink_2(Array0::any_array_di, Size::in, Array::any_array_uo),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ ML_alloc_any_array(Array, Size + 1, MR_PROC_LABEL);
+ ML_shrink_array(Array, Array0, Size);
+").
+
+%-----------------------------------------------------------------------------%
+
+:- pragma foreign_decl("C", "
+void ML_copy_array(MR_ArrayPtr any_array, MR_ConstArrayPtr old_array);
+").
+
+:- pragma foreign_code("C", "
+/*
+** The caller is responsible for allocating the storage for the new any_array.
+** This routine does the job of copying the any_array elements.
+*/
+void
+ML_copy_array(MR_ArrayPtr any_array, MR_ConstArrayPtr old_array)
+{
+ /*
+ ** Any changes to this function will probably also require
+ ** changes to deepcopy() in runtime/deep_copy.c.
+ */
+
+ MR_Integer i;
+ MR_Integer any_array_size;
+
+ any_array_size = old_array->size;
+ any_array->size = any_array_size;
+ for (i = 0; i < any_array_size; i++) {
+ any_array->elements[i] = old_array->elements[i];
+ }
+}
+").
+
+:- pragma foreign_proc("C",
+ any_array__copy(Array0::any_array_ui, Array::any_array_uo),
+ [will_not_call_mercury, promise_pure, thread_safe],
+"
+ ML_alloc_any_array(Array, Array0->size + 1, MR_PROC_LABEL);
+ ML_copy_array(Array, (MR_ConstArrayPtr) Array0);
+").
+
+%-----------------------------------------------------------------------------%
+
+any_array(List) = Array :-
+ any_array__from_any_list(List, Array).
+
+any_array__from_any_list([], Array) :-
+ any_array__make_empty_array(Array).
+any_array__from_any_list(List, Array) :-
+ List = [Head | Tail],
+ Len = any_list__length(List),
+ any_array__init(Len, Head, Array0),
+ any_array__insert_items(Tail, 1, Array0, Array).
+
+%-----------------------------------------------------------------------------%
+
+:- pred any_array__insert_items(any_list(T)::ia, int::in,
+ any_array(T)::any_array_di, any_array(T)::any_array_uo) is det.
+
+any_array__insert_items([], _N, Array, Array).
+any_array__insert_items([Head|Tail], N, Array0, Array) :-
+ any_array__set(Array0, N, Head, Array1),
+ N1 = N + 1,
+ any_array__insert_items(Tail, N1, Array1, Array).
+
+%-----------------------------------------------------------------------------%
+
+any_array__to_any_list(Array, List) :-
+ any_array__bounds(Array, Low, High),
+ any_array__fetch_items(Array, Low, High, List).
+
+%-----------------------------------------------------------------------------%
+
+any_array__fetch_items(Array, Low, High, List) :-
+ List = foldr_0(func(X::ia, Xs::ia) = ([X | Xs]::oa) is det,
+ Array, [], Low, High).
+
+%-----------------------------------------------------------------------------%
+
+any_array__map(Closure, OldArray, NewArray) :-
+ ( any_array__semidet_lookup(OldArray, 0, Elem0) ->
+ any_array__size(OldArray, Size),
+ call(Closure, Elem0, Elem),
+ any_array__init(Size, Elem, NewArray0),
+ any_array__map_2(1, Size, Closure, OldArray,
+ NewArray0, NewArray)
+ ;
+ any_array__make_empty_array(NewArray)
+ ).
+
+:- pred any_array__map_2(int::in, int::in,
+ pred(T1, T2)::in(pred(ia, oa) is det), any_array(T1)::any_array_ui,
+ any_array(T2)::any_array_di, any_array(T2)::any_array_uo) is det.
+
+any_array__map_2(N, Size, Closure, OldArray, NewArray0, NewArray) :-
+ ( N >= Size ->
+ NewArray = NewArray0
+ ;
+ any_array__lookup(OldArray, N, OldElem),
+ Closure(OldElem, NewElem),
+ any_array__set(NewArray0, N, NewElem, NewArray1),
+ any_array__map_2(N + 1, Size, Closure, OldArray,
+ NewArray1, NewArray)
+ ).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+% Ralph Becket <rwab1 at cam.sri.com> 24/04/99
+% Function forms added.
+
+any_array__make_empty_array = A :-
+ any_array__make_empty_array(A).
+
+any_array__init(N, X) = A :-
+ any_array__init(N, X, A).
+
+any_array__min(A) = N :-
+ any_array__min(A, N).
+
+any_array__max(A) = N :-
+ any_array__max(A, N).
+
+any_array__size(A) = N :-
+ any_array__size(A, N).
+
+any_array__lookup(A, N) = X :-
+ any_array__lookup(A, N, X).
+
+any_array__set(A1, N, X) = A2 :-
+ any_array__set(A1, N, X, A2).
+
+any_array__slow_set(A1, N, X) = A2 :-
+ any_array__slow_set(A1, N, X, A2).
+
+any_array__copy(A1) = A2 :-
+ any_array__copy(A1, A2).
+
+any_array__resize(A1, N, X) = A2 :-
+ any_array__resize(A1, N, X, A2).
+
+any_array__shrink(A1, N) = A2 :-
+ any_array__shrink(A1, N, A2).
+
+any_array__from_any_list(Xs) = A :-
+ any_array__from_any_list(Xs, A).
+
+any_array__to_any_list(A) = Xs :-
+ any_array__to_any_list(A, Xs).
+
+any_array__fetch_items(A, N1, N2) = Xs :-
+ any_array__fetch_items(A, N1, N2, Xs).
+
+any_array__map(F, A1) = A2 :-
+ P = ( pred(X::ia, Y::oa) is det :- Y = F(X) ),
+ any_array__map(P, A1, A2).
+
+any_array__elem(Index, Array) =
+ any_array__lookup(Array, Index).
+
+'any_array__elem :='(Index, Array, Value) =
+ any_array__set(Array, Index, Value).
+
+%------------------------------------------------------------------------------%
+
+any_array__random_permutation(A0, A, RS0, RS) :-
+ Lo = any_array__min(A0),
+ Hi = any_array__max(A0),
+ Sz = any_array__size(A0),
+ permutation_2(Lo, Lo, Hi, Sz, A0, A, RS0, RS).
+
+:- pred permutation_2(int, int, int, int, any_array(T), any_array(T),
+ random__supply, random__supply).
+:- mode permutation_2(in, in, in, in, any_array_di, any_array_uo, mdi, muo) is det.
+
+permutation_2(I, Lo, Hi, Sz, A0, A, RS0, RS) :-
+ ( I > Hi ->
+ A = A0,
+ RS = RS0
+ ;
+ random__random(R, RS0, RS1),
+ J = Lo + (R `rem` Sz),
+ A1 = swap_elems(A0, I, J),
+ permutation_2(I + 1, Lo, Hi, Sz, A1, A, RS1, RS)
+ ).
+
+%------------------------------------------------------------------------------%
+
+:- func swap_elems(any_array(T), int, int) = any_array(T).
+:- mode swap_elems(any_array_di, in, in) = any_array_uo is det.
+
+swap_elems(A0, I, J) = A :-
+ XI = A0 ^ elem(I),
+ XJ = A0 ^ elem(J),
+ A = ((A0 ^ elem(I) := XJ) ^ elem(J) := XI).
+
+%------------------------------------------------------------------------------%
+
+any_array__foldl(Fn, A, X) =
+ foldl_0(Fn, A, X, any_array__min(A), any_array__max(A)).
+
+:- func foldl_0(func(T1, T2) = T2, any_array(T1), T2, int, int) = T2.
+:- mode foldl_0(func(ia, in) = out is det, any_array_ui, in, in, in) = out
+ is det.
+:- mode foldl_0(func(ia, ia) = oa is det, any_array_ui, ia, in, in) = oa
+ is det.
+
+foldl_0(Fn, A, X, I, Max) =
+ ( Max < I ->
+ X
+ ;
+ foldl_0(Fn, A, Fn(A ^ elem(I), X), I + 1, Max)
+ ).
+
+%-----------------------------------------------------------------------------%
+
+any_array__foldr(Fn, A, X) =
+ foldr_0(Fn, A, X, any_array__min(A), any_array__max(A)).
+
+:- func foldr_0(func(T1, T2) = T2, any_array(T1), T2, int, int) = T2.
+:- mode foldr_0(func(ia, in) = out is det, any_array_ui, in, in, in) = out
+ is det.
+:- mode foldr_0(func(ia, ia) = oa is det, any_array_ui, ia, in, in) = oa
+ is det.
+:- mode foldr_0(func(ia, di) = uo is det, any_array_ui, di, in, in) = uo
+ is det.
+
+foldr_0(Fn, A, X, Min, I) =
+ ( I < Min ->
+ X
+ ;
+ foldr_0(Fn, A, Fn(A ^ elem(I), X), Min, I - 1)
+ ).
+
+%------------------------------------------------------------------------------%
+
+ % throw an exception indicating an any_array bounds error
+:- pred out_of_bounds_error(any_array(T), int, string).
+:- mode out_of_bounds_error(any_array_ui, in, in) is erroneous.
+
+out_of_bounds_error(Array, Index, PredName) :-
+ % Note: we deliberately do not include the any_array element type name in
+ % the error message here, for performance reasons: using the type name
+ % could prevent the compiler from optimizing away the construction of the
+ % type_info in the caller, because it would prevent unused argument
+ % elimination. Performance is important here, because any_array__set and
+ % any_array__lookup are likely to be used in the inner loops of
+ % performance-critical applications.
+ any_array__bounds(Array, Min, Max),
+ throw(any_array__index_out_of_bounds(
+ string__format("%s: index %d not in range [%d, %d]",
+ [s(PredName), i(Index), i(Min), i(Max)]))).
+
+%-----------------------------------------------------------------------------%
+
+any_array__least_index(A) = any_array__min(A).
+
+any_array__greatest_index(A) = any_array__max(A).
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
Index: extras/solver_types/library/any_assoc_list.m
===================================================================
RCS file: extras/solver_types/library/any_assoc_list.m
diff -N extras/solver_types/library/any_assoc_list.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ extras/solver_types/library/any_assoc_list.m 9 Sep 2005 05:55:53 -0000
@@ -0,0 +1,184 @@
+% vim ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+%
+% any_any_assoc_list.m
+% Ralph Becket <rafe at cs.mu.oz.au>
+% Wed Sep 7 14:53:47 EST 2005
+%
+% A port of any_assoc_list.m for values with inst any.
+% This is needed by any_map.m.
+%-----------------------------------------------------------------------------%
+
+:- module any_assoc_list.
+
+:- interface.
+
+:- import_module any_list.
+:- import_module list.
+:- import_module std_util.
+
+%-----------------------------------------------------------------------------%
+
+:- type any_assoc_list(K,V) == any_list(pair(K,V)).
+
+:- type any_assoc_list(T) == any_list(pair(T,T)).
+
+ % Zip together two lists; abort if they are of different lengths.
+ %
+:- pred any_assoc_list__from_corresponding_lists(list(K)::in, any_list(V)::ia,
+ any_assoc_list(K,V)::oa) is det.
+:- func any_assoc_list__from_corresponding_lists(list(K)::in, any_list(V)::ia)
+ = (any_assoc_list(K,V)::oa) is det.
+
+ % Return the first member of each pair.
+ %
+:- pred any_assoc_list__keys(any_assoc_list(K, V)::ia, list(K)::out) is det.
+:- func any_assoc_list__keys(any_assoc_list(K, V)::ia) = (list(K)::out) is det.
+
+ % Return the second member of each pair.
+ %
+:- pred any_assoc_list__values(any_assoc_list(K, V)::ia, any_list(V)::oa)
+ is det.
+:- func any_assoc_list__values(any_assoc_list(K, V)::ia) = (any_list(V)::oa)
+ is det.
+
+ % Return the two lists contain respectively the first and second member
+ % of each pair in the any_assoc_list.
+ %
+:- pred any_assoc_list__keys_and_values(any_assoc_list(K, V)::ia,
+ list(K)::out, any_list(V)::oa) is det.
+
+ % Find the first element of the association list that matches
+ % the given key, and return the associated value.
+ %
+:- pred any_assoc_list__search(any_assoc_list(K, V)::ia, K::in, V::oa)
+ is semidet.
+
+ % An alternative version of any_assoc_list__search.
+ %
+:- func (any_assoc_list(K, V)::ia) ^ elem(K::in) = (V::oa) is semidet.
+
+ % An alternative version of any_assoc_list__search that throws an
+ % exception if the key in question does not appear in the
+ % any_assoc_list.
+ %
+:- func (any_assoc_list(K, V)::ia) ^ det_elem(K::in) = (V::oa) is det.
+
+ % Find the first element of the association list that matches
+ % the given key. Return the associated value, and the original
+ % list with the selected element removed.
+ %
+:- pred any_assoc_list__remove(any_assoc_list(K, V)::ia, K::in, V::oa,
+ any_assoc_list(K, V)::oa) is semidet.
+
+:- func any_assoc_list__map_values(func(K, V) = W, any_assoc_list(K, V))
+ = any_assoc_list(K, W).
+:- mode any_assoc_list__map_values(func(in, ia) = oa is det, ia) = oa is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module any_util.
+:- import_module require.
+:- import_module string.
+
+any_assoc_list__from_corresponding_lists(Ks, Vs, KVs) :-
+ ( any_assoc_list__from_corresponding_2(Ks, Vs, KVs0) ->
+ KVs = KVs0
+ ;
+ KeyType = type_name(type_of(Ks)),
+ list__length(Ks, KeyLength),
+ string__int_to_string(KeyLength, KeyLengthString),
+ ValueType = type_name(type_of(Vs)),
+ ValueLength = any_list__length(Vs),
+ string__int_to_string(ValueLength, ValueLengthString),
+ string__append_list(
+ ["any_assoc_list__from_corresponding_lists: " ++
+ "lists have different lengths.\n",
+ "\tKey list type: ",
+ KeyType,
+ "\n\tKey list length: ",
+ KeyLengthString,
+ "\n\tValue list type: ",
+ ValueType,
+ "\n\tValue list length: ",
+ ValueLengthString
+ ],
+ ErrorString),
+ error(ErrorString)
+ ).
+
+:- pred any_assoc_list__from_corresponding_2(list(K)::in, any_list(V)::ia,
+ any_assoc_list(K,V)::oa) is semidet.
+
+any_assoc_list__from_corresponding_2([], [], []).
+any_assoc_list__from_corresponding_2([A | As], [B | Bs], [A - B | ABs]) :-
+ any_assoc_list__from_corresponding_2(As, Bs, ABs).
+
+any_assoc_list__keys([], []).
+any_assoc_list__keys([K - _ | KVs], [K | Ks]) :-
+ unsafe_cast_to_ground(K),
+ any_assoc_list__keys(KVs, Ks).
+
+any_assoc_list__values([], []).
+any_assoc_list__values([_ - V | KVs], [V | Vs]) :-
+ any_assoc_list__values(KVs, Vs).
+
+any_assoc_list__keys_and_values([], [], []).
+any_assoc_list__keys_and_values([K - V | KVs], [K | Ks], [V | Vs]) :-
+ unsafe_cast_to_ground(K),
+ any_assoc_list__keys_and_values(KVs, Ks, Vs).
+
+any_assoc_list__search([K - V | KVs], Key, Value) :-
+ unsafe_cast_to_ground(K),
+ ( K = Key ->
+ Value = V
+ ;
+ any_assoc_list__search(KVs, Key, Value)
+ ).
+
+any_assoc_list__remove([K - V | KVs], Key, Value, Rest) :-
+ unsafe_cast_to_ground(K),
+ ( K = Key ->
+ Value = V,
+ Rest = KVs
+ ;
+ any_assoc_list__remove(KVs, Key, Value, Rest1),
+ Rest = [K - V | Rest1]
+ ).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+any_assoc_list__from_corresponding_lists(Ks, Vs) = AL :-
+ any_assoc_list__from_corresponding_lists(Ks, Vs, AL).
+
+any_assoc_list__keys(AL) = Ks :-
+ any_assoc_list__keys(AL, Ks).
+
+any_assoc_list__values(AL) = Vs :-
+ any_assoc_list__values(AL, Vs).
+
+any_assoc_list__map_values(_F, []) = [].
+any_assoc_list__map_values(F, [K - V0 | KVs0]) = [K - V | KVs] :-
+ unsafe_cast_to_ground(K),
+ V = apply(F, K, V0),
+ KVs = any_assoc_list__map_values(F, KVs0).
+
+AL ^ elem(K) = V :-
+ any_assoc_list__search(AL, K, V).
+
+AL ^ det_elem(K) = V :-
+ ( if any_assoc_list__search(AL, K, V0)
+ then V = V0
+ else report_lookup_error("any_assoc_list__det_elem: key not found", K)
+ ).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: extras/solver_types/library/any_list.m
===================================================================
RCS file: extras/solver_types/library/any_list.m
diff -N extras/solver_types/library/any_list.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ extras/solver_types/library/any_list.m 9 Sep 2005 05:55:53 -0000
@@ -0,0 +1,1186 @@
+%---------------------------------------------------------------------------%
+% Copyright (C) 2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%---------------------------------------------------------------------------%
+% vim: ft=mercury ts=4 sw=4 et
+% any_list.m
+% Ralph Becket <rafe at cs.mu.oz.au>
+% Started Wed Aug 10 18:17:22 EST 2005
+%
+% A version of the list module adapted for lists whose members have
+% inst `any' (typically [types containing] solver types).
+%
+%---------------------------------------------------------------------------%
+
+:- module any_list.
+:- interface.
+:- import_module int.
+
+
+
+:- type any_list(T) ---> [] ; [T | any_list(T)].
+
+%-----------------------------------------------------------------------------%
+
+:- pred is_empty(any_list(T)::ia) is semidet.
+
+:- pred is_not_empty(any_list(T)::ia) is semidet.
+
+:- func cons(T, any_list(T)) = any_list(T).
+
+ % Standard append predicate:
+ % append(Start, End, List) is true iff
+ % `List' is the result of concatenating `Start' and `End'.
+ %
+:- pred append(any_list(T), any_list(T), any_list(T)).
+:- mode append(ia, ia, oa) is det.
+:- mode append(oa, oa, ia) is multi.
+
+ % L1 ++ L2 = L :- append(L1, L2, L).
+ %
+:- func any_list(T) ++ any_list(T) = any_list(T).
+:- mode ia ++ ia = oa is det.
+
+ % member(Elem, List) :
+ % True iff `List' contains `Elem'.
+ %
+:- pred member(T::oa, any_list(T)::ia) is nondet.
+
+ % member(Elem, List, SubList) :
+ % True iff `List' contains `Elem', and `SubList' is
+ % a suffix of `List' beginning with `Elem'.
+ % Same as `SubList = [Elem | _], append(_, SubList, List)'.
+ %
+:- pred member(T::oa, any_list(T)::ia, any_list(T)::oa) is nondet.
+
+ % length(List, Length) :
+ % True iff `Length' is the length of `List', i.e. if
+ % `List' contains `Length' elements.
+ %
+:- func length(any_list(T)::ia) = (int::out) is det.
+
+ % same_length(ListA, ListB) :
+ % True iff `ListA' and `ListB' have the same length,
+ % i.e. iff they both contain the same number of elements.
+ %
+:- pred same_length(any_list(T1)::ia, any_list(T2)::ia) is semidet.
+
+ % split_list(Len, List, Start, End):
+ % splits `List' into a prefix `Start' of length `Len',
+ % and a remainder `End'.
+ % See also: take, drop.
+ %
+:- pred split_list(int::in, any_list(T)::ia, any_list(T)::oa, any_list(T)::oa)
+ is semidet.
+
+ % take(Len, List, Start):
+ % `Start' is the first `Len' elements of `List'.
+ % Fails if `List' has less than `Len' elements.
+ % See also: split_list.
+ %
+:- pred take(int::in, any_list(T)::ia, any_list(T)::oa) is semidet.
+
+ % take_upto(Len, List, Start):
+ % `Start' is the first `Len' elements of `List'.
+ % If `List' has less than `Len' elements, return the entire list.
+ %
+:- func take_upto(int::in, any_list(T)::ia) = (any_list(T)::oa) is det.
+
+ % drop(Len, List) = End:
+ % `End' is the remainder of `List' after removing the
+ % first `Len' elements.
+ % See also: split_list.
+ %
+:- func drop(int::in, any_list(T)::ia) = (any_list(T)::oa) is semidet.
+
+ % insert(Elem, List0, List):
+ % `List' is the result of inserting `Elem' somewhere in `List0'.
+ % Same as `delete(List, Elem, List0)'.
+ %
+:- pred insert(T, any_list(T), any_list(T)).
+:- mode insert(oa, oa, ia) is nondet.
+:- mode insert(ia, ia, oa) is multi.
+
+ % list__delete(List, Elem, Remainder):
+ % True iff `Elem' occurs in `List', and
+ % `Remainder' is the result of deleting one occurrence of
+ % `Elem' from `List'.
+ %
+:- pred delete(any_list(T)::ia, T::oa, any_list(T)::oa) is nondet.
+
+ % replace_nth(List0, N, R) = List is true iff List is List0
+ % with Nth element replaced with R.
+ % Fails if N < 1 or if length of List0 < N.
+ % (Position numbers start from 1.)
+ %
+:- func replace_nth(any_list(T)::ia, int::in, T::ia) = (any_list(T)::oa)
+ is semidet.
+
+ % replace_nth_det(List0, N, R, List) is true iff List is List0
+ % with Nth element replaced with R.
+ % Aborts if N < 1 or if length of List0 < N.
+ % (Position numbers start from 1.)
+ %
+:- func replace_nth_det(any_list(T)::ia, int::in, T::ia) = (any_list(T)::oa)
+ is det.
+
+ % reverse(List) = Reverse:
+ % `Reverse' is a list containing the same elements as `List'
+ % but in reverse order.
+ %
+:- func reverse(any_list(T)::ia) = (any_list(T)::oa) is det.
+
+ % perm(List0, List):
+ % True iff `List' is a permutation of `List0'.
+ %
+:- pred perm(any_list(T)::ia, any_list(T)::oa) is multi.
+
+ % index*(List, Position, Elem):
+ % These predicates select an element in a list from it's
+ % position. The `index0' preds consider the first element
+ % element to be element number zero, whereas the `index1' preds
+ % consider the first element to be element number one.
+ % The `_det' preds call error/1 if the index is out of
+ % range, whereas the semidet preds fail if the index is out of
+ % range.
+ %
+:- func index0_det(any_list(T)::ia, int::in) = (T::oa) is det.
+:- func index1_det(any_list(T)::ia, int::in) = (T::oa) is det.
+
+ % zip(ListA, ListB) = List:
+ % List is the result of alternating the elements
+ % of ListA and ListB, starting with the first element
+ % of ListA (followed by the first element of ListB,
+ % then the second element of listA, then the second
+ % element of ListB, etc.). When there are no more
+ % elements remaining in one of the lists,
+ % the remainder of the nonempty list is appended.
+ %
+:- func zip(any_list(T)::ia, any_list(T)::ia) = (any_list(T)::oa) is det.
+
+ % duplicate(Count, Elem) = List is true iff List is a list
+ % containing Count duplicate copies of Elem.
+ %
+:- func duplicate(int::in, T::ia) = (any_list(T)::oa) is det.
+
+ % condense(ListOfLists) = List:
+ % `List' is the result of concatenating all the
+ % elements of `ListOfLists'.
+ %
+:- func condense(any_list(any_list(T))::ia) = (any_list(T)::oa) is det.
+
+ % chunk(List, ChunkSize, Chunks):
+ % Takes a list `List' and breaks it into a list of lists
+ % `Chunks', such that the length of each list in `Chunks'
+ % is at most `ChunkSize. (More precisely, the length of
+ % each list in `Chunks' other than the last one is exactly
+ % `ChunkSize', and the length of the last list in `Chunks'
+ % is between one and `ChunkSize'.)
+ %
+:- func chunk(any_list(T)::ia, int::in) = (any_list(any_list(T))::oa) is det.
+
+ % all_same(List) is true
+ % if all elements of the list are the same
+ %
+:- pred all_same(any_list(T)::ia) is semidet.
+
+ % last(List, Last) is true
+ % if Last is the last element of List.
+ %
+:- pred last(any_list(T)::ia, T::oa) is semidet.
+
+ % A deterministic version of last, which aborts instead of
+ % failing if the input list is empty.
+ %
+:- func det_last(any_list(T)::ia) = (T::oa) is det.
+
+ % split_last(List, AllButLast, Last) is true
+ % if Last is the last element of List and AllButLast is the list
+ % of elements before it.
+ %
+:- pred split_last(any_list(T)::ia, any_list(T)::oa, T::oa) is semidet.
+
+ % A deterministic version of split_last, which aborts instead of
+ % failing if the input list is empty.
+ %
+:- pred split_last_det(any_list(T)::ia, any_list(T)::oa, T::oa) is det.
+
+%-----------------------------------------------------------------------------%
+%
+% The following group of predicates use higher-order terms to simplify
+% various list processing tasks. They implement pretty much standard
+% sorts of operations provided by standard libraries for functional languages.
+%
+%-----------------------------------------------------------------------------%
+
+ % map(T, L, M) uses the closure T
+ % to transform the elements of L into the elements of M.
+:- pred map(pred(X, Y), any_list(X), any_list(Y)).
+:- mode map(pred(ia, oa) is det, ia, oa) is det.
+:- mode map(pred(ia, oa) is cc_multi, ia, oa) is cc_multi.
+:- mode map(pred(ia, oa) is semidet, ia, oa) is semidet.
+:- mode map(pred(ia, oa) is multi, ia, oa) is multi.
+:- mode map(pred(ia, oa) is nondet, ia, oa) is nondet.
+:- mode map(pred(ia, ia) is semidet, ia, ia) is semidet.
+
+:- func map(func(X) = Y, any_list(X)) = any_list(Y).
+:- mode map(func(ia) = oa is det, ia) = oa is det.
+
+ % map2(T, L, M1, M2) uses the closure T
+ % to transform the elements of L into the elements of M1 and M2.
+:- pred map2(pred(A, B, C), any_list(A), any_list(B), any_list(C)).
+:- mode map2(pred(ia, oa, oa) is det, ia, oa, oa) is det.
+:- mode map2(pred(ia, oa, oa) is cc_multi, ia, oa, oa) is cc_multi.
+:- mode map2(pred(ia, oa, oa) is semidet, ia, oa, oa) is semidet.
+:- mode map2(pred(ia, oa, oa) is multi, ia, oa, oa) is multi.
+:- mode map2(pred(ia, oa, oa) is nondet, ia, oa, oa) is nondet.
+:- mode map2(pred(ia, ia, ia) is semidet, ia, ia, ia) is semidet.
+
+ % map3(T, L, M1, M2, M3) uses the closure T
+ % to transform the elements of L into the elements of M1, M2 and M3.
+:- pred map3(pred(A, B, C, D), any_list(A), any_list(B), any_list(C),
+ any_list(D)).
+:- mode map3(pred(ia, oa, oa, oa) is det, ia, oa, oa, oa) is det.
+:- mode map3(pred(ia, oa, oa, oa) is cc_multi, ia, oa, oa, oa) is cc_multi.
+:- mode map3(pred(ia, oa, oa, oa) is semidet, ia, oa, oa, oa) is semidet.
+:- mode map3(pred(ia, oa, oa, oa) is multi, ia, oa, oa, oa) is multi.
+:- mode map3(pred(ia, oa, oa, oa) is nondet, ia, oa, oa, oa) is nondet.
+:- mode map3(pred(ia, ia, ia, ia) is semidet, ia, ia, ia, ia) is semidet.
+
+ % map4(T, L, M1, M2, M3, M4) uses the closure T
+ % to transform the elements of L into the elements of M1, M2, M3 and
+ % M4.
+:- pred map4(pred(A, B, C, D, E), any_list(A), any_list(B), any_list(C),
+ any_list(D), any_list(E)).
+:- mode map4(pred(ia, oa, oa, oa, oa) is det, ia, oa, oa, oa, oa)
+ is det.
+:- mode map4(pred(ia, oa, oa, oa, oa) is cc_multi, ia, oa, oa, oa, oa)
+ is cc_multi.
+:- mode map4(pred(ia, oa, oa, oa, oa) is semidet, ia, oa, oa, oa, oa)
+ is semidet.
+:- mode map4(pred(ia, oa, oa, oa, oa) is multi, ia, oa, oa, oa, oa)
+ is multi.
+:- mode map4(pred(ia, oa, oa, oa, oa) is nondet, ia, oa, oa, oa, oa)
+ is nondet.
+:- mode map4(pred(ia, ia, ia, ia, ia) is semidet, ia, ia, ia, ia, ia)
+ is semidet.
+
+ % map5(T, L, M1, M2, M3, M4, M5) uses the closure T
+ % to transform the elements of L into the elements of M1, M2, M3, M4
+ % and M5.
+:- pred map5(pred(A, B, C, D, E, F), any_list(A), any_list(B), any_list(C),
+ any_list(D), any_list(E), any_list(F)).
+:- mode map5(pred(ia, oa, oa, oa, oa, oa) is det, ia, oa, oa, oa,
+ oa, oa) is det.
+:- mode map5(pred(ia, oa, oa, oa, oa, oa) is cc_multi, ia, oa, oa,
+ oa, oa, oa) is cc_multi.
+:- mode map5(pred(ia, oa, oa, oa, oa, oa) is semidet, ia, oa, oa,
+ oa, oa, oa) is semidet.
+:- mode map5(pred(ia, oa, oa, oa, oa, oa) is multi, ia, oa, oa,
+ oa, oa, oa) is multi.
+:- mode map5(pred(ia, oa, oa, oa, oa, oa) is nondet, ia, oa, oa,
+ oa, oa, oa) is nondet.
+:- mode map5(pred(ia, ia, ia, ia, ia, ia) is semidet, ia, ia, ia,
+ ia, ia, ia) is semidet.
+
+ % map6(T, L, M1, M2, M3, M4, M5, M6) uses the closure T
+ % to transform the elements of L into the elements of M1, M2, M3, M4,
+ % M5 and M6.
+:- pred map6(pred(A, B, C, D, E, F, G), any_list(A), any_list(B), any_list(C),
+ any_list(D), any_list(E), any_list(F), any_list(G)).
+:- mode map6(pred(ia, oa, oa, oa, oa, oa, oa) is det, ia, oa, oa,
+ oa, oa, oa, oa) is det.
+:- mode map6(pred(ia, oa, oa, oa, oa, oa, oa) is cc_multi, ia, oa,
+ oa, oa, oa, oa, oa) is cc_multi.
+:- mode map6(pred(ia, oa, oa, oa, oa, oa, oa) is semidet, ia, oa,
+ oa, oa, oa, oa, oa) is semidet.
+:- mode map6(pred(ia, oa, oa, oa, oa, oa, oa) is multi, ia, oa,
+ oa, oa, oa, oa, oa) is multi.
+:- mode map6(pred(ia, oa, oa, oa, oa, oa, oa) is nondet, ia, oa,
+ oa, oa, oa, oa, oa) is nondet.
+:- mode map6(pred(ia, ia, ia, ia, ia, ia, ia) is semidet, ia, ia,
+ ia, ia, ia, ia, ia) is semidet.
+
+ % map7(T, L, M1, M2, M3, M4, M5, M6, M7) uses the closure T
+ % to transform the elements of L into the elements of M1, M2, M3, M4,
+ % M5, M6 and M7.
+:- pred map7(pred(A, B, C, D, E, F, G, H), any_list(A), any_list(B),
+ any_list(C), any_list(D), any_list(E), any_list(F), any_list(G),
+ any_list(H)).
+:- mode map7(pred(ia, oa, oa, oa, oa, oa, oa, oa) is det,
+ ia, oa, oa, oa, oa, oa, oa, oa) is det.
+:- mode map7(pred(ia, oa, oa, oa, oa, oa, oa, oa) is cc_multi,
+ ia, oa, oa, oa, oa, oa, oa, oa) is cc_multi.
+:- mode map7(pred(ia, oa, oa, oa, oa, oa, oa, oa) is semidet,
+ ia, oa, oa, oa, oa, oa, oa, oa) is semidet.
+:- mode map7(pred(ia, oa, oa, oa, oa, oa, oa, oa) is multi,
+ ia, oa, oa, oa, oa, oa, oa, oa) is multi.
+:- mode map7(pred(ia, oa, oa, oa, oa, oa, oa, oa) is nondet,
+ ia, oa, oa, oa, oa, oa, oa, oa) is nondet.
+:- mode map7(pred(ia, ia, ia, ia, ia, ia, ia, ia) is semidet,
+ ia, ia, ia, ia, ia, ia, ia, ia) is semidet.
+
+ % map8(T, L, M1, M2, M3, M4, M5, M6, M7) uses the closure T
+ % to transform the elements of L into the elements of M1, M2, M3, M4,
+ % M5, M6, M7 and M8.
+:- pred map8(pred(A, B, C, D, E, F, G, H, I), any_list(A), any_list(B),
+ any_list(C), any_list(D), any_list(E), any_list(F), any_list(G),
+ any_list(H), any_list(I)).
+:- mode map8(pred(ia, oa, oa, oa, oa, oa, oa, oa, oa) is det,
+ ia, oa, oa, oa, oa, oa, oa, oa, oa) is det.
+:- mode map8(pred(ia, oa, oa, oa, oa, oa, oa, oa, oa) is cc_multi,
+ ia, oa, oa, oa, oa, oa, oa, oa, oa) is cc_multi.
+:- mode map8(pred(ia, oa, oa, oa, oa, oa, oa, oa, oa) is semidet,
+ ia, oa, oa, oa, oa, oa, oa, oa, oa) is semidet.
+:- mode map8(pred(ia, oa, oa, oa, oa, oa, oa, oa, oa) is multi,
+ ia, oa, oa, oa, oa, oa, oa, oa, oa) is multi.
+:- mode map8(pred(ia, oa, oa, oa, oa, oa, oa, oa, oa) is nondet,
+ ia, oa, oa, oa, oa, oa, oa, oa, oa) is nondet.
+:- mode map8(pred(ia, ia, ia, ia, ia, ia, ia, ia, ia) is semidet,
+ ia, ia, ia, ia, ia, ia, ia, ia, ia) is semidet.
+
+ % map_corresponding(F, [A1, .. An], [B1, .. Bn]) =
+ % [F(A1, B1), .., F(An, Bn)].
+ %
+ % An exception is raised if the list arguments differ in length.
+ %
+:- func map_corresponding(func(A, B) = C, any_list(A), any_list(B)) =
+ any_list(C).
+:- mode map_corresponding(func(ia, ia) = oa is det, ia, ia) = oa is det.
+
+ % map_corresponding3(F, [A1, .. An], [B1, .. Bn], [C1, .. Cn]) =
+ % [F(A1, B1, C1), .., F(An, Bn, Cn)].
+ %
+ % An exception is raised if the list arguments differ in length.
+ %
+:- func map_corresponding3(func(A, B, C) = D, any_list(A), any_list(B),
+ any_list(C)) = any_list(D).
+:- mode map_corresponding3(func(ia, ia, ia) = oa is det, ia, ia, ia) = oa
+ is det.
+
+ % foldl(Pred, List, Start, End) calls Pred with each
+ % element of List (working left-to-right) and an accumulator
+ % (with the initial value of Start), and returns the final
+ % value in End.
+ %
+:- pred foldl(pred(L, A, A), any_list(L), A, A).
+:- mode foldl(pred(ia, di, uo) is det, ia, di, uo) is det.
+:- mode foldl(pred(ia, ia, oa) is det, ia, ia, oa) is det.
+:- mode foldl(pred(ia, ia, oa) is semidet, ia, ia, oa) is semidet.
+:- mode foldl(pred(ia, ia, oa) is nondet, ia, ia, oa) is nondet.
+:- mode foldl(pred(ia, di, uo) is cc_multi, ia, di, uo) is cc_multi.
+:- mode foldl(pred(ia, ia, oa) is cc_multi, ia, ia, oa) is cc_multi.
+
+:- func foldl(func(L, A) = A, any_list(L), A) = A.
+:- mode foldl(func(ia, ia) = oa is det, ia, ia) = oa is det.
+
+ % foldr(Pred, List, Start, End) calls Pred with each
+ % element of List (working right-to-left) and an accumulator
+ % (with the initial value of Start), and returns the final
+ % value in End.
+ %
+:- pred foldr(pred(L, A, A), any_list(L), A, A).
+:- mode foldr(pred(ia, di, uo) is det, ia, di, uo) is det.
+:- mode foldr(pred(ia, ia, oa) is det, ia, ia, oa) is det.
+:- mode foldr(pred(ia, ia, oa) is semidet, ia, ia, oa) is semidet.
+:- mode foldr(pred(ia, ia, oa) is nondet, ia, ia, oa) is nondet.
+:- mode foldr(pred(ia, di, uo) is cc_multi, ia, di, uo) is cc_multi.
+:- mode foldr(pred(ia, ia, oa) is cc_multi, ia, ia, oa) is cc_multi.
+
+:- func foldr(func(L, A) = A, any_list(L), A) = A.
+:- mode foldr(func(ia, ia) = oa is det, ia, ia) = oa is det.
+
+ % foldl2(Pred, List, !Acc1, !Acc2)
+ % Does the same job as foldl, but with two accumulators.
+ % (Although no more expressive than foldl, this is often
+ % a more convenient format, and a little more efficient).
+ %
+:- pred foldl2(pred(L, A, A, Z, Z), any_list(L), A, A, Z, Z).
+:- mode foldl2(pred(ia, ia, oa, ia, oa) is det,
+ ia, ia, oa, ia, oa) is det.
+:- mode foldl2(pred(ia, ia, oa, ia, oa) is cc_multi,
+ ia, ia, oa, ia, oa) is cc_multi.
+:- mode foldl2(pred(ia, ia, oa, ia, oa) is semidet,
+ ia, ia, oa, ia, oa) is semidet.
+:- mode foldl2(pred(ia, ia, oa, ia, oa) is nondet,
+ ia, ia, oa, ia, oa) is nondet.
+:- mode foldl2(pred(ia, ia, oa, mdi, muo) is det,
+ ia, ia, oa, mdi, muo) is det.
+:- mode foldl2(pred(ia, ia, oa, di, uo) is det,
+ ia, ia, oa, di, uo) is det.
+:- mode foldl2(pred(ia, di, uo, di, uo) is det,
+ ia, di, uo, di, uo) is det.
+:- mode foldl2(pred(ia, ia, oa, mdi, muo) is cc_multi,
+ ia, ia, oa, mdi, muo) is cc_multi.
+:- mode foldl2(pred(ia, ia, oa, di, uo) is cc_multi,
+ ia, ia, oa, di, uo) is cc_multi.
+:- mode foldl2(pred(ia, di, uo, di, uo) is cc_multi,
+ ia, di, uo, di, uo) is cc_multi.
+
+ % foldl3(Pred, List, !Acc1, !Acc2, !Acc3)
+ % Does the same job as foldl, but with three accumulators.
+ % (Although no more expressive than foldl, this is often
+ % a more convenient format, and a little more efficient).
+ %
+:- pred foldl3(pred(L, A, A, B, B, C, C), any_list(L),
+ A, A, B, B, C, C).
+:- mode foldl3(pred(ia, ia, oa, ia, oa, ia, oa) is det,
+ ia, ia, oa, ia, oa, ia, oa) is det.
+:- mode foldl3(pred(ia, ia, oa, ia, oa, ia, oa) is cc_multi,
+ ia, ia, oa, ia, oa, ia, oa) is cc_multi.
+:- mode foldl3(pred(ia, ia, oa, ia, oa, ia, oa) is semidet,
+ ia, ia, oa, ia, oa, ia, oa) is semidet.
+:- mode foldl3(pred(ia, ia, oa, ia, oa, ia, oa) is nondet,
+ ia, ia, oa, ia, oa, ia, oa) is nondet.
+:- mode foldl3(pred(ia, ia, oa, ia, oa, di, uo) is det,
+ ia, ia, oa, ia, oa, di, uo) is det.
+:- mode foldl3(pred(ia, ia, oa, ia, oa, di, uo) is cc_multi,
+ ia, ia, oa, ia, oa, di, uo) is cc_multi.
+
+ % foldl4(Pred, List, !Acc1, !Acc2, !Acc3, !Acc4)
+ % Does the same job as foldl, but with four accumulators.
+ % (Although no more expressive than foldl, this is often
+ % a more convenient format, and a little more efficient).
+ %
+:- pred foldl4(pred(L, A, A, B, B, C, C, D, D), any_list(L),
+ A, A, B, B, C, C, D, D).
+:- mode foldl4(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa) is det,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa) is det.
+:- mode foldl4(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa) is cc_multi,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa) is cc_multi.
+:- mode foldl4(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa) is semidet,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa) is semidet.
+:- mode foldl4(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa) is nondet,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa) is nondet.
+:- mode foldl4(pred(ia, ia, oa, ia, oa, ia, oa, di, uo) is det,
+ ia, ia, oa, ia, oa, ia, oa, di, uo) is det.
+:- mode foldl4(pred(ia, ia, oa, ia, oa, ia, oa, di, uo) is cc_multi,
+ ia, ia, oa, ia, oa, ia, oa, di, uo) is cc_multi.
+
+ % foldl5(Pred, List, !Acc1, !Acc2, !Acc3, !Acc4, !Acc5)
+ % Does the same job as foldl, but with five accumulators.
+ % (Although no more expressive than foldl, this is often
+ % a more convenient format, and a little more efficient).
+ %
+:- pred foldl5(pred(L, A, A, B, B, C, C, D, D, E, E), any_list(L),
+ A, A, B, B, C, C, D, D, E, E).
+:- mode foldl5(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is det,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is det.
+:- mode foldl5(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is cc_multi,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is cc_multi.
+:- mode foldl5(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is semidet,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is semidet.
+:- mode foldl5(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is nondet,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is nondet.
+:- mode foldl5(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, di, uo)
+ is det,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is det.
+:- mode foldl5(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, di, uo)
+ is cc_multi,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is cc_multi.
+
+ % foldl6(Pred, List, !Acc1, !Acc2, !Acc3, !Acc4, !Acc5, !Acc6)
+ % Does the same job as foldl, but with six accumulators.
+ % (Although no more expressive than foldl, this is often
+ % a more convenient format, and a little more efficient).
+ %
+:- pred foldl6(pred(L, A, A, B, B, C, C, D, D, E, E, F, F), any_list(L),
+ A, A, B, B, C, C, D, D, E, E, F, F).
+:- mode foldl6(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa) is det,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is det.
+:- mode foldl6(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa) is cc_multi,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is cc_multi.
+:- mode foldl6(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa) is semidet,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is semidet.
+:- mode foldl6(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa) is nondet,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is nondet.
+:- mode foldl6(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ di, uo) is det,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is det.
+:- mode foldl6(pred(ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ di, uo) is cc_multi,
+ ia, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is cc_multi.
+
+ % foldl_corresponding(F, As, Bs, !Acc)
+ % Does the same job as foldl, but works on two lists ia
+ % parallel. An exception is raised if the list arguments differ
+ % in length.
+ %
+:- pred foldl_corresponding(pred(A, B, C, C), any_list(A), any_list(B), C, C).
+:- mode foldl_corresponding(pred(ia, ia, ia, oa) is det,
+ ia, ia, ia, oa) is det.
+:- mode foldl_corresponding(pred(ia, ia, ia, oa) is cc_multi,
+ ia, ia, ia, oa) is cc_multi.
+:- mode foldl_corresponding(pred(ia, ia, ia, oa) is semidet,
+ ia, ia, ia, oa) is semidet.
+:- mode foldl_corresponding(pred(ia, ia, ia, oa) is nondet,
+ ia, ia, ia, oa) is nondet.
+:- mode foldl_corresponding(pred(ia, ia, di, uo) is det,
+ ia, ia, di, uo) is det.
+:- mode foldl_corresponding(pred(ia, ia, di, uo) is cc_multi,
+ ia, ia, di, uo) is cc_multi.
+
+ % foldl2_corresponding(F, As, Bs, !Acc1, !Acc2)
+ % Does the same job as foldl_corresponding, but has two
+ % accumulators.
+ %
+:- pred foldl2_corresponding(pred(A, B, C, C, D, D), any_list(A), any_list(B),
+ C, C, D, D).
+:- mode foldl2_corresponding(pred(ia, ia, ia, oa, ia, oa) is det,
+ ia, ia, ia, oa, ia, oa) is det.
+:- mode foldl2_corresponding(pred(ia, ia, ia, oa, ia, oa) is cc_multi,
+ ia, ia, ia, oa, ia, oa) is cc_multi.
+:- mode foldl2_corresponding(pred(ia, ia, ia, oa, ia, oa) is semidet,
+ ia, ia, ia, oa, ia, oa) is semidet.
+:- mode foldl2_corresponding(pred(ia, ia, ia, oa, ia, oa) is nondet,
+ ia, ia, ia, oa, ia, oa) is nondet.
+:- mode foldl2_corresponding(pred(ia, ia, ia, oa, di, uo) is det,
+ ia, ia, ia, oa, di, uo) is det.
+:- mode foldl2_corresponding(pred(ia, ia, ia, oa, di, uo) is cc_multi,
+ ia, ia, ia, oa, di, uo) is cc_multi.
+
+ % map_foldl(Pred, InList, OutList, Start, End) calls Pred
+ % with an accumulator (with the initial value of Start) on
+ % each element of InList (working left-to-right) to transform
+ % InList into OutList. The final value of the accumulator is
+ % returned in End.
+ %
+:- pred map_foldl(pred(L, M, A, A), any_list(L), any_list(M), A, A).
+:- mode map_foldl(pred(ia, oa, di, uo) is det, ia, oa, di, uo)
+ is det.
+:- mode map_foldl(pred(ia, oa, ia, oa) is det, ia, oa, ia, oa)
+ is det.
+:- mode map_foldl(pred(ia, oa, di, uo) is cc_multi, ia, oa, di, uo)
+ is cc_multi.
+:- mode map_foldl(pred(ia, oa, ia, oa) is cc_multi, ia, oa, ia, oa)
+ is cc_multi.
+:- mode map_foldl(pred(ia, oa, ia, oa) is semidet, ia, oa, ia, oa)
+ is semidet.
+:- mode map_foldl(pred(ia, oa, ia, oa) is nondet, ia, oa, ia, oa)
+ is nondet.
+
+ % Same as map_foldl, but with two mapped outputs.
+ %
+:- pred map2_foldl(pred(L, M, N, A, A), any_list(L), any_list(M), any_list(N),
+ A, A).
+:- mode map2_foldl(pred(ia, oa, oa, di, uo) is det, ia, oa, oa,
+ di, uo) is det.
+:- mode map2_foldl(pred(ia, oa, oa, ia, oa) is det, ia, oa, oa,
+ ia, oa) is det.
+:- mode map2_foldl(pred(ia, oa, oa, di, uo) is cc_multi, ia, oa, oa,
+ di, uo) is cc_multi.
+:- mode map2_foldl(pred(ia, oa, oa, ia, oa) is cc_multi, ia, oa, oa,
+ ia, oa) is cc_multi.
+:- mode map2_foldl(pred(ia, oa, oa, ia, oa) is semidet, ia, oa, oa,
+ ia, oa) is semidet.
+:- mode map2_foldl(pred(ia, oa, oa, ia, oa) is nondet, ia, oa, oa,
+ ia, oa) is nondet.
+
+ % Same as map_foldl, but with two accumulators.
+ %
+:- pred map_foldl2(pred(L, M, A, A, B, B), any_list(L), any_list(M),
+ A, A, B, B).
+:- mode map_foldl2(pred(ia, oa, ia, oa, di, uo) is det,
+ ia, oa, ia, oa, di, uo) is det.
+:- mode map_foldl2(pred(ia, oa, ia, oa, ia, oa) is det,
+ ia, oa, ia, oa, ia, oa) is det.
+:- mode map_foldl2(pred(ia, oa, ia, oa, di, uo) is cc_multi,
+ ia, oa, ia, oa, di, uo) is cc_multi.
+:- mode map_foldl2(pred(ia, oa, ia, oa, ia, oa) is cc_multi,
+ ia, oa, ia, oa, ia, oa) is cc_multi.
+:- mode map_foldl2(pred(ia, oa, ia, oa, ia, oa) is semidet,
+ ia, oa, ia, oa, ia, oa) is semidet.
+:- mode map_foldl2(pred(ia, oa, ia, oa, ia, oa) is nondet,
+ ia, oa, ia, oa, ia, oa) is nondet.
+
+ % Same as map_foldl, but with three accumulators.
+ %
+:- pred map_foldl3(pred(L, M, A, A, B, B, C, C), any_list(L), any_list(M),
+ A, A, B, B, C, C).
+:- mode map_foldl3(pred(ia, oa, ia, oa, ia, oa, di, uo) is det,
+ ia, oa, ia, oa, ia, oa, di, uo) is det.
+:- mode map_foldl3(pred(ia, oa, ia, oa, ia, oa, ia, oa) is det,
+ ia, oa, ia, oa, ia, oa, ia, oa) is det.
+:- mode map_foldl3(pred(ia, oa, ia, oa, ia, oa, di, uo) is cc_multi,
+ ia, oa, ia, oa, ia, oa, di, uo) is cc_multi.
+:- mode map_foldl3(pred(ia, oa, ia, oa, ia, oa, ia, oa) is cc_multi,
+ ia, oa, ia, oa, ia, oa, ia, oa) is cc_multi.
+:- mode map_foldl3(pred(ia, oa, ia, oa, ia, oa, ia, oa) is semidet,
+ ia, oa, ia, oa, ia, oa, ia, oa) is semidet.
+:- mode map_foldl3(pred(ia, oa, ia, oa, ia, oa, ia, oa) is nondet,
+ ia, oa, ia, oa, ia, oa, ia, oa) is nondet.
+
+ % Same as map_foldl, but with four accumulators.
+ %
+:- pred map_foldl4(pred(L, M, A, A, B, B, C, C, D, D),
+ any_list(L), any_list(M), A, A, B, B, C, C, D, D).
+:- mode map_foldl4(pred(ia, oa, ia, oa, ia, oa, ia, oa, di, uo)
+ is det,
+ ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is det.
+:- mode map_foldl4(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is det,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is det.
+:- mode map_foldl4(pred(ia, oa, ia, oa, ia, oa, ia, oa, di, uo)
+ is cc_multi,
+ ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is cc_multi.
+:- mode map_foldl4(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is cc_multi,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is cc_multi.
+:- mode map_foldl4(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is semidet,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is semidet.
+:- mode map_foldl4(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is nondet,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is nondet.
+
+ % Same as map_foldl, but with five accumulators.
+ %
+:- pred map_foldl5(pred(L, M, A, A, B, B, C, C, D, D, E, E),
+ any_list(L), any_list(M), A, A, B, B, C, C, D, D, E, E).
+:- mode map_foldl5(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ di, uo) is det,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is det.
+:- mode map_foldl5(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa) is det,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is det.
+:- mode map_foldl5(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ di, uo) is cc_multi,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is cc_multi.
+:- mode map_foldl5(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa) is cc_multi,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is cc_multi.
+:- mode map_foldl5(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa) is semidet,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is semidet.
+:- mode map_foldl5(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa) is nondet,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is nondet.
+
+ % Same as map_foldl, but with six accumulators.
+ %
+:- pred map_foldl6(pred(L, M, A, A, B, B, C, C, D, D, E, E, F, F),
+ any_list(L), any_list(M), A, A, B, B, C, C, D, D, E, E, F, F).
+:- mode map_foldl6(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa, di, uo) is det,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, di, uo) is det.
+:- mode map_foldl6(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa, ia, oa) is det,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa) is det.
+:- mode map_foldl6(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa, di, uo) is cc_multi,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, di, uo)
+ is cc_multi.
+:- mode map_foldl6(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa, ia, oa) is cc_multi,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is cc_multi.
+:- mode map_foldl6(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa, ia, oa) is semidet,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is semidet.
+:- mode map_foldl6(pred(ia, oa, ia, oa, ia, oa, ia, oa, ia, oa,
+ ia, oa, ia, oa) is nondet,
+ ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa, ia, oa)
+ is nondet.
+
+ % all_true(Pred, List) takes a closure with one input argument.
+ % If Pred succeeds for every member of List, all_true succeeds.
+ % If Pred fails for any member of List, all_true fails.
+ %
+:- pred all_true(pred(X)::(pred(ia) is semidet), any_list(X)::ia) is semidet.
+
+%-----------------------------------------------------------------------------%
+
+:- func head(any_list(T)::ia) = (T::oa) is semidet.
+
+:- func tail(any_list(T)::ia) = (any_list(T)::oa) is semidet.
+
+ % det_head(List) returns the first element of List,
+ % calling error/1 if List is empty.
+ %
+:- func det_head(any_list(T)::ia) = (T::oa) is det.
+
+ % det_tail(List) returns the tail of List,
+ % calling error/1 if List is empty.
+ %
+:- func det_tail(any_list(T)::ia) = (any_list(T)::oa) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module require.
+:- import_module set_tree234.
+:- import_module std_util.
+:- import_module string.
+
+%-----------------------------------------------------------------------------%
+
+is_empty([]).
+
+is_not_empty([_ | _]).
+
+cons(H, T) = [H | T].
+
+append([], Ys, Ys).
+append([X | Xs], Ys, [X | Zs]) :-
+ append(Xs, Ys, Zs).
+
+%-----------------------------------------------------------------------------%
+
+index0_det(List, N) = Elem :-
+ ( index0(List, N, Elem0) ->
+ Elem = Elem0
+ ;
+ error("index: index out of range")
+ ).
+
+:- pred index0(any_list(T)::ia, int::in, T::oa) is semidet.
+
+index0([X | Xs], N, Y) :-
+ ( if N = 0 then Y = X else index0(Xs, N, Y) ).
+
+index1_det(List, N) = index0_det(List, N - 1).
+
+%-----------------------------------------------------------------------------%
+
+condense([]) = [].
+condense([L | Ls]) = L ++ condense(Ls).
+
+%-----------------------------------------------------------------------------%
+
+same_length([], []).
+same_length([_ | L1], [_ | L2]) :-
+ same_length(L1, L2).
+
+%-----------------------------------------------------------------------------%
+
+insert(X, Ys, [X | Ys]).
+insert(X, [Y | Ys], [Y | Zs]) :-
+ insert(X, Ys, Zs).
+
+%-----------------------------------------------------------------------------%
+
+delete(List, Elem, Remainder) :-
+ insert(Elem, Remainder, List).
+
+%-----------------------------------------------------------------------------%
+
+replace_nth(Xs, P, R) = L :-
+ P > 0,
+ replace_nth_2(Xs, P, R, L).
+
+replace_nth_det(Xs, P, R) = L :-
+ ( P > 0 ->
+ ( replace_nth_2(Xs, P, R, L0) ->
+ L = L0
+ ;
+ error("replace_nth_det: " ++
+ "Can't replace element whose index " ++
+ "position is past the end of the list")
+ )
+ ;
+ error("replace_nth_det: " ++
+ "Can't replace element whose index " ++
+ "position is less than 1.")
+ ).
+
+:- pred replace_nth_2(any_list(T)::ia, int::in, T::ia, any_list(T)::oa)
+ is semidet.
+
+replace_nth_2([X | Xs], P, R, L) :-
+ ( P = 1 ->
+ L = [R | Xs]
+ ;
+ replace_nth_2(Xs, P - 1, R, L0),
+ L = [X | L0]
+ ).
+
+%-----------------------------------------------------------------------------%
+
+member(X, [X | _]).
+member(X, [_ | Xs]) :-
+ member(X, Xs).
+
+member(Element, List, SubList) :-
+ SubList = [Element | _],
+ append(_, SubList, List).
+
+%-----------------------------------------------------------------------------%
+
+% Note - it is not possible to write a version of
+% length/1 in pure Mercury that works in both directions
+% unless you make it semidet rather than det.
+
+length(L) = N :-
+ length_2(L, 0, N).
+
+:- pred length_2(any_list(T)::ia, int::in, int::out) is det.
+
+length_2([], N, N).
+length_2([_ | L1], N0, N) :-
+ N1 = N0 + 1,
+ length_2(L1, N1, N).
+
+%-----------------------------------------------------------------------------%
+
+reverse(L0) = L :-
+ reverse_2(L0, [], L).
+
+:- pred reverse_2(any_list(T)::ia, any_list(T)::ia, any_list(T)::oa) is det.
+
+reverse_2([], L, L).
+reverse_2([X | Xs], L0, L) :-
+ reverse_2(Xs, [X | L0], L).
+
+%-----------------------------------------------------------------------------%
+
+zip([], Bs) = Bs.
+zip([A | As], Bs) = [A | Cs] :-
+ zip2(As, Bs, Cs).
+
+:- pred zip2(any_list(T)::ia, any_list(T)::ia, any_list(T)::oa) is det.
+
+zip2(As, [], As).
+zip2(As, [B | Bs], [B | Cs]) :-
+ zip2(As, Bs, Cs).
+
+%-----------------------------------------------------------------------------%
+
+split_list(N, List, Start, End) :-
+ ( N = 0 ->
+ Start = [],
+ End = List
+ ;
+ N > 0,
+ List = [Head | List1],
+ Start = [Head | Start1],
+ split_list(N - 1, List1, Start1, End)
+ ).
+
+take(N, As, Bs) :-
+ ( N > 0 ->
+ As = [A | As1],
+ take(N - 1, As1, Bs1),
+ Bs = [A | Bs1]
+ ;
+ Bs = []
+ ).
+
+take_upto(N, As) = Bs :-
+ ( take(N, As, Bs0) ->
+ Bs = Bs0
+ ;
+ Bs = As
+ ).
+
+drop(N, As) = Bs :-
+ ( N > 0 ->
+ As = [_ | Cs],
+ Bs = drop(N - 1, Cs)
+ ;
+ As = Bs
+ ).
+
+%-----------------------------------------------------------------------------%
+
+duplicate(N, X) = duplicate(N, X, []).
+
+:- func duplicate(int::in, T::ia, any_list(T)::ia) = (any_list(T)::oa) is det.
+
+duplicate(N, X, Xs) =
+ ( N > 0 ->
+ duplicate(N-1, X, [X|Xs])
+ ;
+ Xs
+ ).
+
+%-----------------------------------------------------------------------------%
+
+chunk(List, ChunkSize) = ListOfSmallLists :-
+ chunk_2(List, ChunkSize, [], ChunkSize, ListOfSmallLists).
+
+:- pred chunk_2(any_list(T)::ia, int::in, any_list(T)::ia, int::in,
+ any_list(any_list(T))::oa) is det.
+
+chunk_2([], _ChunkSize, List0, _N, Lists) :-
+ ( List0 = [] ->
+ Lists = []
+ ;
+ List = reverse(List0),
+ Lists = [List]
+ ).
+chunk_2([X | Xs], ChunkSize, List0, N, Lists) :-
+ ( N > 1 ->
+ chunk_2(Xs, ChunkSize, [X | List0], N - 1, Lists)
+ ;
+ List = reverse([X | List0]),
+ chunk_2(Xs, ChunkSize, [], ChunkSize, Lists1),
+ Lists = [List | Lists1]
+ ).
+
+%-----------------------------------------------------------------------------%
+
+perm([], []).
+perm([X | Xs], Ys) :-
+ perm(Xs, Ys0),
+ insert(X, Ys0, Ys).
+
+%-----------------------------------------------------------------------------%
+
+all_same([]).
+all_same([H | T]) :-
+ all_same_2(H, T).
+
+:- pred all_same_2(T::ia, any_list(T)::ia) is semidet.
+
+all_same_2(_, []).
+all_same_2(H, [H | T]) :-
+ all_same_2(H, T).
+
+%-----------------------------------------------------------------------------%
+
+last([H | T], Last) :-
+ (
+ T = [],
+ Last = H
+ ;
+ T = [_ | _],
+ last(T, Last)
+ ).
+
+det_last(List) = Last :-
+ ( last(List, LastPrime) ->
+ Last = LastPrime
+ ;
+ error("last_det: empty list")
+ ).
+
+split_last([H | T], AllButLast, Last) :-
+ (
+ T = [],
+ AllButLast = [],
+ Last = H
+ ;
+ T = [_ | _],
+ split_last(T, AllButLast1, Last),
+ AllButLast = [H | AllButLast1]
+ ).
+
+split_last_det(List, AllButLast, Last) :-
+ ( split_last(List, AllButLastPrime, LastPrime) ->
+ AllButLast = AllButLastPrime,
+ Last = LastPrime
+ ;
+ error("split_last_det: empty list")
+ ).
+
+%-----------------------------------------------------------------------------%
+
+map(_, [], []).
+map(P, [H0 | T0], [H | T]) :-
+ call(P, H0, H),
+ map(P, T0, T).
+
+map2(_, [], [], []).
+map2(P, [H0 | T0], [H1 | T1], [H2 | T2]) :-
+ call(P, H0, H1, H2),
+ map2(P, T0, T1, T2).
+
+map3(_, [], [], [], []).
+map3(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3]) :-
+ call(P, H0, H1, H2, H3),
+ map3(P, T0, T1, T2, T3).
+
+map4(_, [], [], [], [], []).
+map4(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4]) :-
+ call(P, H0, H1, H2, H3, H4),
+ map4(P, T0, T1, T2, T3, T4).
+
+map5(_, [], [], [], [], [], []).
+map5(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], [H5 | T5])
+ :-
+ call(P, H0, H1, H2, H3, H4, H5),
+ map5(P, T0, T1, T2, T3, T4, T5).
+
+map6(_, [], [], [], [], [], [], []).
+map6(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], [H5 | T5],
+ [H6 | T6]) :-
+ call(P, H0, H1, H2, H3, H4, H5, H6),
+ map6(P, T0, T1, T2, T3, T4, T5, T6).
+
+map7(_, [], [], [], [], [], [], [], []).
+map7(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], [H5 | T5],
+ [H6 | T6], [H7 | T7]) :-
+ call(P, H0, H1, H2, H3, H4, H5, H6, H7),
+ map7(P, T0, T1, T2, T3, T4, T5, T6, T7).
+
+map8(_, [], [], [], [], [], [], [], [], []).
+map8(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], [H5 | T5],
+ [H6 | T6], [H7 | T7], [H8 | T8]) :-
+ call(P, H0, H1, H2, H3, H4, H5, H6, H7, H8),
+ map8(P, T0, T1, T2, T3, T4, T5, T6, T7, T8).
+
+map_corresponding(_, [], []) = [].
+map_corresponding(_, [], [_ | _]) =
+ func_error("map_corresponding/3: mismatched list arguments").
+map_corresponding(_, [_ | _], []) =
+ func_error("map_corresponding/3: mismatched list arguments").
+map_corresponding(F, [A | As], [B | Bs]) =
+ [F(A, B) | map_corresponding(F, As, Bs)].
+
+map_corresponding3(F, As, Bs, Cs) =
+ (
+ As = [A | As0],
+ Bs = [B | Bs0],
+ Cs = [C | Cs0]
+ ->
+ [F(A, B, C) | map_corresponding3(F, As0, Bs0, Cs0)]
+ ;
+ As = [],
+ Bs = [],
+ Cs = []
+ ->
+ []
+ ;
+ func_error("map_corresponding3: " ++
+ "mismatched list arguments")
+ ).
+
+foldl(_, [], !A).
+foldl(P, [H | T], !A) :-
+ call(P, H, !A),
+ foldl(P, T, !A).
+
+foldl2(_, [], !A, !B).
+foldl2(P, [H | T], !A, !B) :-
+ call(P, H, !A, !B),
+ foldl2(P, T, !A, !B).
+
+foldl3(_, [], !A, !B, !C).
+foldl3(P, [H | T], !A, !B, !C) :-
+ call(P, H, !A, !B, !C),
+ foldl3(P, T, !A, !B, !C).
+
+foldl4(_, [], !A, !B, !C, !D).
+foldl4(P, [H | T], !A, !B, !C, !D) :-
+ call(P, H, !A, !B, !C, !D),
+ foldl4(P, T, !A, !B, !C, !D).
+
+foldl5(_, [], !A, !B, !C, !D, !E).
+foldl5(P, [H | T], !A, !B, !C, !D, !E) :-
+ call(P, H, !A, !B, !C, !D, !E),
+ foldl5(P, T, !A, !B, !C, !D, !E).
+
+foldl6(_, [], !A, !B, !C, !D, !E, !F).
+foldl6(P, [H | T], !A, !B, !C, !D, !E, !F) :-
+ call(P, H, !A, !B, !C, !D, !E, !F),
+ foldl6(P, T, !A, !B, !C, !D, !E, !F).
+
+foldl_corresponding(_, [], [], !Acc).
+foldl_corresponding(_, [], [_ | _], _, _) :-
+ error("foldl_corresponding/5: mismatched list arguments").
+foldl_corresponding(_, [_ | _], [], _, _) :-
+ error("foldl_corresponding/5: mismatched list arguments").
+foldl_corresponding(P, [A | As], [B | Bs], !Acc) :-
+ P(A, B, !Acc),
+ foldl_corresponding(P, As, Bs, !Acc).
+
+foldl2_corresponding(_, [], [], !Acc1, !Acc2).
+foldl2_corresponding(_, [], [_ | _], _, _, _, _) :-
+ error("foldl2_corresponding/7: mismatched list arguments").
+foldl2_corresponding(_, [_ | _], [], _, _, _, _) :-
+ error("foldl2_corresponding/7: mismatched list arguments").
+foldl2_corresponding(P, [A | As], [B | Bs], !Acc1, !Acc2) :-
+ P(A, B, !Acc1, !Acc2),
+ foldl2_corresponding(P, As, Bs, !Acc1, !Acc2).
+
+map_foldl(_, [], [], !A).
+map_foldl(P, [H0 | T0], [H | T], !A) :-
+ call(P, H0, H, !A),
+ map_foldl(P, T0, T, !A).
+
+map2_foldl(_, [], [], [], !A).
+map2_foldl(P, [H0 | T0], [H1 | T1], [H2 | T2], !A) :-
+ call(P, H0, H1, H2, !A),
+ map2_foldl(P, T0, T1, T2, !A).
+
+map_foldl2(_, [], [], !A, !B).
+map_foldl2(P, [H0 | T0], [H | T], !A, !B) :-
+ call(P, H0, H, !A, !B),
+ map_foldl2(P, T0, T, !A, !B).
+
+map_foldl3(_, [], [], !A, !B, !C).
+map_foldl3(P, [H0 | T0], [H | T], !A, !B, !C) :-
+ call(P, H0, H, !A, !B, !C),
+ map_foldl3(P, T0, T, !A, !B, !C).
+
+map_foldl4(_, [], [], !A, !B, !C, !D).
+map_foldl4(P, [H0 | T0], [H | T], !A, !B, !C, !D) :-
+ call(P, H0, H, !A, !B, !C, !D),
+ map_foldl4(P, T0, T, !A, !B, !C, !D).
+
+map_foldl5(_, [], [], !A, !B, !C, !D, !E).
+map_foldl5(P, [H0 | T0], [H | T], !A, !B, !C, !D, !E) :-
+ call(P, H0, H, !A, !B, !C, !D, !E),
+ map_foldl5(P, T0, T, !A, !B, !C, !D, !E).
+
+map_foldl6(_, [], [], !A, !B, !C, !D, !E, !F).
+map_foldl6(P, [H0 | T0], [H | T], !A, !B, !C, !D, !E, !F) :-
+ call(P, H0, H, !A, !B, !C, !D, !E, !F),
+ map_foldl6(P, T0, T, !A, !B, !C, !D, !E, !F).
+
+foldr(_, [], !A).
+foldr(P, [H | T], !A) :-
+ foldr(P, T, !A),
+ call(P, H, !A).
+
+all_true(_P, []).
+all_true(P, [X | Xs]) :-
+ P(X),
+ all_true(P, Xs).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+% Ralph Becket <rwab1 at cam.sri.com> 27/04/99
+% Function forms added.
+
+det_head([]) = _ :-
+ error("det_head/1: empty list as argument").
+det_head([X | _]) = X.
+
+det_tail([]) = _ :-
+ error("det_tail/1: empty list as argument").
+det_tail([_ | Xs]) = Xs.
+
+head([X | _]) = X.
+
+tail([_ | Xs]) = Xs.
+
+map(F, Xs) = Ys :-
+ P = ( pred(X::ia, Y::oa) is det :- Y = F(X) ),
+ map(P, Xs, Ys).
+
+foldl(F, Xs, A) = B :-
+ P = ( pred(X::ia, Y::ia, Z::oa) is det :- Z = F(X, Y) ),
+ foldl(P, Xs, A, B).
+
+foldr(F, Xs, A) = B :-
+ P = ( pred(X::ia, Y::ia, Z::oa) is det :- Z = F(X, Y) ),
+ foldr(P, Xs, A, B).
+
+L1 ++ L2 = L3 :-
+ append(L1, L2, L3).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: extras/solver_types/library/any_map.m
===================================================================
RCS file: extras/solver_types/library/any_map.m
diff -N extras/solver_types/library/any_map.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ extras/solver_types/library/any_map.m 9 Sep 2005 05:55:53 -0000
@@ -0,0 +1,1145 @@
+% vim: ft=mercury ts=4 sw=4 et
+%-----------------------------------------------------------------------------%
+% Copyright (C) 1993-2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%-----------------------------------------------------------------------------%
+% any_map.m
+% Ralph Becket <rafe at cs.mu.oz.au>
+% Mon Sep 5 18:23:35 EST 2005
+%
+% A copy of map.m adapted for maps from ground keys to values with inst any.
+%
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- module any_map.
+:- interface.
+
+:- import_module any_assoc_list.
+:- import_module any_list.
+:- import_module list.
+:- import_module set.
+
+%-----------------------------------------------------------------------------%
+
+:- type any_map(K, V).
+
+%-----------------------------------------------------------------------------%
+
+ % Initialize an empty map.
+ %
+:- pred any_map__init(any_map(K, V)::oa) is det.
+:- func any_map__init = (any_map(K, V)::oa) is det.
+
+ % Check whether a map is empty.
+ %
+:- pred any_map__is_empty(any_map(K, V)::ia) is semidet.
+
+ % Check whether map contains key
+ %
+:- pred any_map__contains(any_map(K, V)::ia, K::in) is semidet.
+
+:- pred any_map__member(any_map(K, V)::ia, K::out, V::oa) is nondet.
+
+ % Search map for key.
+ %
+:- pred any_map__search(any_map(K, V)::ia, K::in, V::oa) is semidet.
+:- func any_map__search(any_map(K, V)::ia, K::in) = (V::oa) is semidet.
+
+ % Search map for key, but abort if search fails.
+ %
+:- pred any_map__lookup(any_map(K, V)::ia, K::in, V::oa) is det.
+:- func any_map__lookup(any_map(K, V)::ia, K::in) = (V::oa) is det.
+
+ % Search for a key-value pair using the key. If there is no entry
+ % for the given key, returns the pair for the next lower key instead.
+ % Fails if there is no key with the given or lower value.
+ %
+:- pred any_map__lower_bound_search(any_map(K, V)::ia, K::in, K::out, V::oa)
+ is semidet.
+
+ % Search for a key-value pair using the key. If there is no entry
+ % for the given key, returns the pair for the next lower key instead.
+ % Aborts if there is no key with the given or lower value.
+ %
+:- pred any_map__lower_bound_lookup(any_map(K, V)::ia, K::in, K::out, V::oa)
+ is det.
+
+ % Search for a key-value pair using the key. If there is no entry
+ % for the given key, returns the pair for the next higher key instead.
+ % Fails if there is no key with the given or higher value.
+ %
+:- pred any_map__upper_bound_search(any_map(K, V)::ia, K::in, K::out, V::oa)
+ is semidet.
+
+ % Search for a key-value pair using the key. If there is no entry
+ % for the given key, returns the pair for the next higher key instead.
+ % Aborts if there is no key with the given or higher value.
+ %
+:- pred any_map__upper_bound_lookup(any_map(K, V)::ia, K::in, K::out, V::oa)
+ is det.
+
+ % Return the largest key in the map, if there is one.
+ %
+:- func any_map__max_key(any_map(K,V)::ia) = (K::out) is semidet.
+
+ % Return the smallest key in the map, if there is one.
+ %
+:- func any_map__min_key(any_map(K,V)::ia) = (K::out) is semidet.
+
+ % Search map for data.
+ %
+:- pred any_map__inverse_search(any_map(K, V)::ia, V::ia, K::out) is nondet.
+
+ % Insert a new key and corresponding value into a map.
+ % Fail if the key already exists.
+ %
+:- pred any_map__insert(any_map(K, V)::ia, K::in, V::ia, any_map(K, V)::oa)
+ is semidet.
+:- func any_map__insert(any_map(K, V)::ia, K::in, V::ia) = (any_map(K, V)::oa)
+ is semidet.
+
+ % Insert a new key and corresponding value into a map.
+ % Abort if the key already exists.
+ %
+:- pred any_map__det_insert(any_map(K, V)::ia, K::in, V::ia, any_map(K, V)::oa)
+ is det.
+:- func any_map__det_insert(any_map(K, V)::ia, K::in, V::ia)
+ = (any_map(K, V)::oa) is det.
+
+ % Apply any_map__det_insert to key - value pairs from corresponding lists.
+ % NOTE: this is not defined if the key values are not (semantically)
+ % ground.
+ %
+:- pred any_map__det_insert_from_corresponding_lists(any_map(K, V)::ia,
+ list(K)::in, list(V)::ia, any_map(K, V)::oa) is det.
+:- func any_map__det_insert_from_corresponding_lists(any_map(K, V)::ia,
+ list(K)::in, list(V)::ia) = (any_map(K, V)::oa) is det.
+
+ % Apply any_map__det_insert to key - value pairs from the any_assoc_lists.
+ % NOTE: this is not defined if the key values are not (semantically)
+ % ground.
+ %
+:- pred any_map__det_insert_from_any_assoc_list(any_map(K, V)::ia,
+ any_assoc_list(K, V)::ia, any_map(K, V)::oa) is det.
+:- func any_map__det_insert_from_any_assoc_list(any_map(K, V)::ia,
+ any_assoc_list(K, V)::ia) = (any_map(K, V)::oa) is det.
+
+ % Apply any_map__set to key - value pairs from corresponding lists.
+ %
+:- pred any_map__set_from_corresponding_lists(any_map(K, V)::ia, list(K)::in,
+ list(V)::ia, any_map(K, V)::oa) is det.
+:- func any_map__set_from_corresponding_lists(any_map(K, V)::ia, list(K)::in,
+ list(V)::ia) = (any_map(K, V)::oa) is det.
+
+:- pred any_map__set_from_any_assoc_list(any_map(K, V)::ia,
+ any_assoc_list(K, V)::ia, any_map(K, V)::oa) is det.
+:- func any_map__set_from_any_assoc_list(any_map(K, V)::ia,
+ any_assoc_list(K, V)::ia) = (any_map(K, V)::oa) is det.
+
+ % Update the value corresponding to a given key
+ % Fail if the key doesn't already exist.
+ %
+:- pred any_map__update(any_map(K, V)::ia, K::in, V::ia, any_map(K, V)::oa)
+ is semidet.
+:- func any_map__update(any_map(K, V)::ia, K::in, V::ia) = (any_map(K, V)::oa)
+ is semidet.
+
+ % Update the value corresponding to a given key
+ % Abort if the key doesn't already exist.
+ %
+:- pred any_map__det_update(any_map(K, V)::ia, K::in, V::ia, any_map(K, V)::oa)
+ is det.
+:- func any_map__det_update(any_map(K, V)::ia, K::in, V::ia)
+ = (any_map(K, V)::oa) 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.
+ %
+:- pred any_map__transform_value(pred(V, V)::in(pred(ia, oa) is det), K::in,
+ any_map(K, V)::ia, any_map(K, V)::oa) is semidet.
+
+ % Same as transform_value/4, but aborts instead of failing if the
+ % key is not found.
+ %
+:- pred any_map__det_transform_value(pred(V, V)::in(pred(ia, oa) is det),
+ K::in, any_map(K, V)::ia, any_map(K, V)::oa) is det.
+:- func any_map__det_transform_value((func(V) = V)::in(func(ia) = oa is det),
+ K::in, any_map(K, V)::ia) = (any_map(K, V)::oa) is det.
+
+ % Update value if the key is already present, otherwise
+ % insert new key and value.
+ %
+:- func any_map__set(any_map(K, V)::ia, K::in, V::ia) = (any_map(K, V)::oa)
+ is det.
+:- pred any_map__set(any_map(K, V)::ia, K::in, V::ia, any_map(K, V)::oa)
+ is det.
+
+ % Given a map, return a list of all the keys in the map.
+ %
+:- func any_map__keys(any_map(K, V)::ia) = (list(K)::out) is det.
+:- pred any_map__keys(any_map(K, V)::ia, list(K)::out) is det.
+
+ % Given a map, return a list of all the keys in the map,
+ % in sorted order.
+ %
+:- func any_map__sorted_keys(any_map(K, V)::ia) = (list(K)::out) is det.
+:- pred any_map__sorted_keys(any_map(K, V)::ia, list(K)::out) is det.
+
+ % Given a map, return a list of all the data values in the map.
+ %
+:- func any_map__values(any_map(K, V)::ia) = (any_list(V)::oa) is det.
+:- pred any_map__values(any_map(K, V)::ia, any_list(V)::oa) is det.
+
+ % Convert a map to an association list.
+ %
+:- func any_map__to_any_assoc_list(any_map(K, V)::ia) =
+ (any_assoc_list(K, V)::oa) is det.
+:- pred any_map__to_any_assoc_list(any_map(K, V)::ia,
+ any_assoc_list(K, V)::out) is det.
+
+ % Convert a map to an association list which is sorted on the keys.
+ %
+:- func any_map__to_sorted_any_assoc_list(any_map(K, V)::ia)
+ = (any_assoc_list(K, V)::oa) is det.
+:- pred any_map__to_sorted_any_assoc_list(any_map(K, V)::ia,
+ any_assoc_list(K, V)::out) is det.
+
+ % Convert an association list to a map.
+ %
+:- func any_map__from_any_assoc_list(any_assoc_list(K, V)::ia)
+ = (any_map(K, V)::oa) is det.
+:- pred any_map__from_any_assoc_list(any_assoc_list(K, V)::ia,
+ any_map(K, V)::oa) is det.
+
+ % Convert a sorted association list to a map.
+ %
+:- func any_map__from_sorted_any_assoc_list(any_assoc_list(K, V)::ia)
+ = (any_map(K, V)::oa) is det.
+:- pred any_map__from_sorted_any_assoc_list(any_assoc_list(K, V)::ia,
+ any_map(K, V)::oa) is det.
+
+ % Delete a key-value pair from a map.
+ % If the key is not present, leave the map unchanged.
+ %
+:- func any_map__delete(any_map(K, V)::ia, K::in) = (any_map(K, V)::oa) is det.
+:- pred any_map__delete(any_map(K, V)::ia, K::in, any_map(K, V)::oa) is det.
+
+ % Apply any_map__delete/3 to a list of keys.
+ %
+:- func any_map__delete_list(any_map(K, V)::ia, list(K)::in)
+ = (any_map(K, V)::oa) is det.
+:- pred any_map__delete_list(any_map(K, V)::ia, list(K)::in,
+ any_map(K, V)::oa) is det.
+
+ % Delete a key-value pair from a map and return the value.
+ % Fail if the key is not present.
+ %
+:- pred any_map__remove(any_map(K, V)::ia, K::in, V::oa, any_map(K, V)::oa)
+ is semidet.
+
+ % Delete a key-value pair from a map and return the value.
+ % Abort if the key is not present.
+ %
+:- pred any_map__det_remove(any_map(K, V)::ia, K::in, V::oa, any_map(K, V)::oa)
+ is det.
+
+ % Count the number of elements in the map.
+ %
+:- func any_map__count(any_map(K, V)::ia) = (int::out) is det.
+:- pred any_map__count(any_map(K, V)::ia, int::out) is det.
+
+ % Convert a pair of lists (which must be of the same length)
+ % to a map.
+ %
+:- func any_map__from_corresponding_lists(list(K)::in, any_list(V)::ia)
+ = (any_map(K, V)::oa) is det.
+:- pred any_map__from_corresponding_lists(list(K)::in, any_list(V)::ia,
+ any_map(K, V)::oa) is det.
+
+ % For any_map__merge(MapA, MapB, Map), MapA and MapB must
+ % not both contain the same key.
+ %
+:- func any_map__merge(any_map(K, V)::ia, any_map(K, V)::ia)
+ = (any_map(K, V)::oa) is det.
+:- pred any_map__merge(any_map(K, V)::ia, any_map(K, V)::ia,
+ any_map(K, V)::oa) is det.
+
+ % For any_map__overlay(MapA, MapB, Map), if MapA and MapB both
+ % contain the same key, then Map will map that key to
+ % the value from MapB. In otherwords, MapB takes precedence
+ % over MapA.
+ %
+:- func any_map__overlay(any_map(K, V)::ia, any_map(K, V)::ia)
+ = (any_map(K, V)::oa) is det.
+:- pred any_map__overlay(any_map(K, V)::ia, any_map(K, V)::ia,
+ any_map(K, V)::oa) is det.
+
+ % any_map__overlay_large_map(MapA, MapB, Map) performs the same task as
+ % any_map__overlay(MapA, MapB, Map). However, while any_map__overlay takes
+ % time proportional to the size of MapB, any_map__overlay_large_map takes
+ % time proportional to the size of MapA. In other words, it preferable when
+ % MapB is a large map.
+ %
+:- func any_map__overlay_large_map(any_map(K, V)::ia, any_map(K, V)::ia)
+ = (any_map(K, V)::oa) is det.
+:- pred any_map__overlay_large_map(any_map(K, V)::ia, any_map(K, V)::ia,
+ any_map(K, V)::oa) is det.
+
+ % any_map__select takes a map and a set of keys and returns
+ % a map containing the keys in the set and their corresponding
+ % values.
+ %
+:- func any_map__select(any_map(K, V)::ia, set(K)::in) = (any_map(K, V)::oa)
+ is det.
+:- pred any_map__select(any_map(K, V)::ia, set(K)::in, any_map(K, V)::oa)
+ is det.
+
+ % Given a list of keys, produce a list of their corresponding
+ % values in a specified map.
+ %
+:- func any_map__apply_to_list(list(K)::in, any_map(K, V)::ia)
+ = (any_list(V)::oa) is det.
+:- pred any_map__apply_to_list(list(K)::in, any_map(K, V)::ia,
+ any_list(V)::oa) is det.
+
+ % Declaratively, a NOP.
+ % Operationally, a suggestion that the implementation
+ % optimize the representation of the map in the expectation
+ % of a number of lookups but few or no modifications.
+ %
+:- func any_map__optimize(any_map(K, V)::ia) = (any_map(K, V)::oa) is det.
+:- pred any_map__optimize(any_map(K, V)::ia, any_map(K, V)::oa) is det.
+
+ % Remove the smallest item from the map, fail if
+ % the map is empty.
+ %
+:- pred any_map__remove_smallest(any_map(K, V)::ia, K::out, V::oa,
+ any_map(K, V)::oa) is semidet.
+
+ % Perform an inorder traversal of the map, applying
+ % an accumulator predicate for each key-value pair.
+ %
+:- func any_map__foldl(func(K, V, T) = T, any_map(K, V), T) = T.
+:- mode any_map__foldl(func(in, ia, in) = out is det, ia, in) = out is det.
+:- mode any_map__foldl(func(in, ia, ia) = oa is det, ia, ia) = oa is det.
+
+:- pred any_map__foldl(pred(K, V, T, T), any_map(K, V), T, T).
+:- mode any_map__foldl(pred(in, ia, di, uo) is det, ia, di, uo)
+ is det.
+:- mode any_map__foldl(pred(in, ia, in, out) is det, ia, in, out)
+ is det.
+:- mode any_map__foldl(pred(in, ia, in, out) is semidet, ia, in, out)
+ is semidet.
+:- mode any_map__foldl(pred(in, ia, ia, oa) is det, ia, ia, oa)
+ is det.
+:- mode any_map__foldl(pred(in, ia, ia, oa) is semidet, ia, ia, oa)
+ is semidet.
+
+ % Perform an inorder traversal of the map, applying
+ % an accumulator predicate with two accumulators for
+ % each key-value pair.
+ % (Although no more expressive than any_map__foldl, this is often
+ % a more convenient format, and a little more efficient).
+ %
+:- pred any_map__foldl2(pred(K, V, T, T, U, U), any_map(K, V), T, T, U, U).
+:- mode any_map__foldl2(pred(in, ia, di, uo, di, uo) is det,
+ ia, di, uo, di, uo) is det.
+:- mode any_map__foldl2(pred(in, ia, in, out, di, uo) is det,
+ ia, in, out, di, uo) is det.
+:- mode any_map__foldl2(pred(in, ia, ia, oa, di, uo) is det,
+ ia, ia, oa, di, uo) is det.
+:- mode any_map__foldl2(pred(in, ia, in, out, in, out) is det,
+ ia, in, out, in, out) is det.
+:- mode any_map__foldl2(pred(in, ia, in, out, in, out) is semidet,
+ ia, in, out, in, out) is semidet.
+:- mode any_map__foldl2(pred(in, ia, ia, oa, in, out) is det,
+ ia, ia, oa, in, out) is det.
+:- mode any_map__foldl2(pred(in, ia, ia, oa, in, out) is semidet,
+ ia, ia, oa, in, out) is semidet.
+:- mode any_map__foldl2(pred(in, ia, ia, oa, ia, oa) is det,
+ ia, ia, oa, ia, oa) is det.
+:- mode any_map__foldl2(pred(in, ia, ia, oa, ia, oa) is semidet,
+ ia, ia, oa, ia, oa) is semidet.
+
+ % Perform an inorder traversal of the map, applying
+ % an accumulator predicate with three accumulators for
+ % each key-value pair.
+ % (Although no more expressive than any_map__foldl, this is often
+ % a more convenient format, and a little more efficient).
+ %
+:- pred any_map__foldl3(pred(K, V, T, T, U, U, W, W),
+ any_map(K, V), T, T, U, U, W, W).
+:- mode any_map__foldl3(pred(in, ia, di, uo, di, uo, di, uo) is det,
+ ia, di, uo, di, uo, di, uo) is det.
+:- mode any_map__foldl3(pred(in, ia, in, out, di, uo, di, uo) is det,
+ ia, in, out, di, uo, di, uo) is det.
+:- mode any_map__foldl3(pred(in, ia, in, out, in, out, di, uo) is det,
+ ia, in, out, in, out, di, uo) is det.
+:- mode any_map__foldl3(pred(in, ia, in, out, in, out, in, out) is det,
+ ia, in, out, in, out, in, out) is det.
+:- mode any_map__foldl3(pred(in, ia, in, out, in, out, in, out) is semidet,
+ ia, in, out, in, out, in, out) is semidet.
+:- mode any_map__foldl3(pred(in, ia, ia, oa, in, out, in, out) is det,
+ ia, ia, oa, in, out, in, out) is det.
+:- mode any_map__foldl3(pred(in, ia, ia, oa, in, out, in, out) is semidet,
+ ia, ia, oa, in, out, in, out) is semidet.
+:- mode any_map__foldl3(pred(in, ia, ia, oa, ia, oa, in, out) is det,
+ ia, ia, oa, ia, oa, in, out) is det.
+:- mode any_map__foldl3(pred(in, ia, ia, oa, ia, oa, in, out) is semidet,
+ ia, ia, oa, ia, oa, in, out) is semidet.
+:- mode any_map__foldl3(pred(in, ia, ia, oa, ia, oa, ia, oa) is det,
+ ia, ia, oa, ia, oa, ia, oa) is det.
+:- mode any_map__foldl3(pred(in, ia, ia, oa, ia, oa, ia, oa) is semidet,
+ ia, ia, oa, ia, oa, ia, oa) is semidet.
+
+ % Apply a transformation predicate to all the values
+ % in a map.
+ %
+:- func any_map__map_values(func(K, V) = W, any_map(K, V)) = any_map(K, W).
+:- mode any_map__map_values(func(in, ia) = oa is det, ia) = oa is det.
+
+:- pred any_map__map_values(pred(K, V, W), any_map(K, V), any_map(K, W)).
+:- mode any_map__map_values(pred(in, ia, oa) is det, ia, oa) is det.
+:- mode any_map__map_values(pred(in, ia, oa) is semidet, ia, oa) is semidet.
+
+ % Apply a transformation predicate to all the values
+ % in a map, while continuously updating an accumulator.
+ %
+:- pred any_map__map_foldl(pred(K, V, W, A, A), any_map(K, V), any_map(K, W),
+ A, A).
+:- mode any_map__map_foldl(pred(in, ia, oa, di, uo) is det, ia, oa,
+ di, uo) is det.
+:- mode any_map__map_foldl(pred(in, ia, oa, in, out) is det, ia, oa,
+ in, out) is det.
+:- mode any_map__map_foldl(pred(in, ia, oa, in, out) is semidet, ia, oa,
+ in, out) is semidet.
+:- mode any_map__map_foldl(pred(in, ia, oa, ia, oa) is det, ia, oa,
+ ia, oa) is det.
+:- mode any_map__map_foldl(pred(in, ia, oa, ia, oa) is semidet, ia, oa,
+ ia, oa) is semidet.
+
+ % As any_map__map_foldl, but with two accumulators.
+ %
+:- pred any_map__map_foldl2(pred(K, V, W, A, A, B, B),
+ any_map(K, V), any_map(K, W), A, A, B, B).
+:- mode any_map__map_foldl2(pred(in, ia, oa, in, out, di, uo) is det,
+ ia, oa, in, out, di, uo) is det.
+:- mode any_map__map_foldl2(pred(in, ia, oa, in, out, in, out) is det,
+ ia, oa, in, out, in, out) is det.
+:- mode any_map__map_foldl2(pred(in, ia, oa, in, out, in, out) is semidet,
+ ia, oa, in, out, in, out) is semidet.
+:- mode any_map__map_foldl2(pred(in, ia, oa, ia, oa, in, out) is det,
+ ia, oa, ia, oa, in, out) is det.
+:- mode any_map__map_foldl2(pred(in, ia, oa, ia, oa, in, out) is semidet,
+ ia, oa, ia, oa, in, out) is semidet.
+:- mode any_map__map_foldl2(pred(in, ia, oa, ia, oa, ia, oa) is det,
+ ia, oa, ia, oa, ia, oa) is det.
+:- mode any_map__map_foldl2(pred(in, ia, oa, ia, oa, ia, oa) is semidet,
+ ia, oa, ia, oa, ia, oa) is semidet.
+
+ % Given two maps M1 and M2, create a third map M3 that has only the
+ % keys that occur in both M1 and M2. For keys that occur in both M1
+ % and M2, compute the value in the final map by applying the supplied
+ % predicate to the values associated with the key in M1 and M2.
+ % Fail if and only if this predicate fails on the values associated
+ % with some common key.
+ %
+:- pred any_map__intersect(pred(V, V, V), any_map(K, V), any_map(K, V),
+ any_map(K, V)).
+:- mode any_map__intersect(pred(ia, ia, oa) is semidet, ia, ia, oa) is semidet.
+:- mode any_map__intersect(pred(ia, ia, oa) is det, ia, ia, oa) is det.
+
+:- func any_map__intersect(func(V, V) = V, any_map(K, V), any_map(K, V))
+ = any_map(K, V).
+:- mode any_map__intersect(func(ia, ia) = oa is det, ia, ia) = oa is det.
+
+ % Calls any_map__intersect. Aborts if any_map__intersect fails.
+ %
+:- pred any_map__det_intersect(pred(V, V, V), any_map(K, V), any_map(K, V),
+ any_map(K, V)).
+:- mode any_map__det_intersect(pred(ia, ia, oa) is semidet, ia, ia, oa) is det.
+
+:- func any_map__det_intersect(func(V, V) = V, any_map(K, V), any_map(K, V))
+ = any_map(K, V).
+:- mode any_map__det_intersect(func(ia, ia) = oa is semidet, ia, ia) = oa
+ is det.
+
+ % Given two maps M1 and M2, create a third map M3 that has only the
+ % keys that occur in both M1 and M2. For keys that occur in both M1
+ % and M2, compute the corresponding values. If they are the same,
+ % include the key/value pair in M3. If they differ, do not include the
+ % key in M3.
+ %
+ % This predicate effectively considers the input maps to be sets of
+ % key/value pairs, computes the intersection of those two sets, and
+ % returns the map corresponding to the intersection.
+ %
+ % any_map__common_subset is very similar to any_map__intersect, but can
+ % succeed even with an output map that does not contain an entry for a key
+ % value that occurs in both input maps.
+ %
+:- func any_map__common_subset(any_map(K, V)::ia, any_map(K, V)::ia)
+ = (any_map(K, V)::oa) is det.
+
+ % Given two maps M1 and M2, create a third map M3 that all the keys
+ % that occur in either M1 and M2. For keys that occur in both M1
+ % and M2, compute the value in the final map by applying the supplied
+ % predicate to the values associated with the key in M1 and M2.
+ % Fail if and only if this predicate fails on the values associated
+ % with some common key.
+ %
+:- func any_map__union(func(V, V) = V, any_map(K, V), any_map(K, V))
+ = any_map(K, V).
+:- mode any_map__union(func(ia, ia) = oa is det, ia, ia) = oa is det.
+
+:- pred any_map__union(pred(V, V, V), any_map(K, V), any_map(K, V),
+ any_map(K, V)).
+:- mode any_map__union(pred(ia, ia, oa) is semidet, ia, ia, oa) is semidet.
+:- mode any_map__union(pred(ia, ia, oa) is det, ia, ia, oa) is det.
+
+ % Calls any_map__union. Aborts if any_map__union fails.
+ %
+:- pred any_map__det_union(pred(V, V, V), any_map(K, V), any_map(K, V),
+ any_map(K, V)).
+:- mode any_map__det_union(pred(ia, ia, oa) is semidet, ia, ia, oa) is det.
+
+:- func any_map__det_union(func(V, V) = V, any_map(K, V), any_map(K, V))
+ = any_map(K, V).
+:- mode any_map__det_union(func(ia, ia) = oa is semidet, ia, ia) = oa is det.
+
+ % Field selection for maps.
+
+ % Map ^ elem(Key) = any_map__search(Map, Key).
+ %
+:- func any_map__elem(K::in, any_map(K, V)::ia) = (V::oa) is semidet.
+
+ % Map ^ det_elem(Key) = any_map__lookup(Map, Key).
+ %
+:- func any_map__det_elem(K::in, any_map(K, V)::ia) = (V::oa) is det.
+
+ % Field update for maps.
+
+ % (Map ^ elem(Key) := Value) = any_map__set(Map, Key, Value).
+ %
+:- func 'any_map__elem :='(K::in, any_map(K, V)::ia, V::ia)
+ = (any_map(K, V)::oa) is det.
+
+ % (Map ^ det_elem(Key) := Value) = any_map__det_update(Map, Key, Value).
+ %
+:- func 'any_map__det_elem :='(K::in, any_map(K, V)::ia, V::ia)
+ = (any_map(K, V)::oa) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module any_tree234.
+:- import_module any_util.
+:- import_module require.
+:- import_module std_util.
+:- import_module string.
+:- import_module svmap.
+:- import_module svset.
+
+:- type any_map(K, V) == any_tree234(K, V).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+any_map__init(M) :-
+ any_tree234__init(M).
+
+any_map__is_empty(M) :-
+ any_tree234__is_empty(M).
+
+any_map__contains(Map, K) :-
+ any_map__search(Map, K, _).
+
+any_map__member(Map, K, V) :-
+ any_tree234__member(Map, K, V).
+
+any_map__search(Map, K, V) :-
+ any_tree234__search(Map, K, V).
+
+any_map__lookup(Map, K, V) :-
+ ( any_tree234__search(Map, K, V1) ->
+ V = V1
+ ;
+ report_lookup_error("any_map__lookup: key not found", K, V)
+ ).
+
+any_map__lower_bound_search(Map, SearchK, K, V) :-
+ any_tree234__lower_bound_search(Map, SearchK, K, V).
+
+any_map__lower_bound_lookup(Map, SearchK, K, V) :-
+ ( any_tree234__lower_bound_search(Map, SearchK, K1, V1) ->
+ K = K1,
+ V = V1
+ ;
+ report_lookup_error("any_map__lower_bound_lookup: key not found",
+ SearchK, V)
+ ).
+
+any_map__upper_bound_search(Map, SearchK, K, V) :-
+ any_tree234__upper_bound_search(Map, SearchK, K, V).
+
+any_map__upper_bound_lookup(Map, SearchK, K, V) :-
+ ( any_tree234__upper_bound_search(Map, SearchK, K1, V1) ->
+ K = K1,
+ V = V1
+ ;
+ report_lookup_error("any_map__upper_bound_lookup: key not found",
+ SearchK, V)
+ ).
+
+any_map__max_key(M) = any_tree234__max_key(M).
+
+any_map__min_key(M) = any_tree234__min_key(M).
+
+any_map__insert(Map0, K, V, Map) :-
+ any_tree234__insert(Map0, K, V, Map).
+
+any_map__det_insert(Map0, K, V, Map) :-
+ ( any_tree234__insert(Map0, K, V, Map1) ->
+ Map = Map1
+ ;
+ report_lookup_error("any_map__det_insert: key already present",
+ K, V)
+ ).
+
+any_map__det_insert_from_corresponding_lists(Map0, Ks, Vs, Map) :-
+ (
+ Ks = [Key | Keys],
+ Vs = [Value | Values]
+ ->
+ any_map__det_insert(Map0, Key, Value, Map1),
+ any_map__det_insert_from_corresponding_lists(Map1, Keys, Values,
+ Map)
+ ;
+ Ks = [],
+ Vs = []
+ ->
+ Map = Map0
+ ;
+ error("any_map__det_insert_from_corresponding_lists - " ++
+ "lists do not correspond")
+ ).
+
+any_map__det_insert_from_any_assoc_list(Map, [], Map).
+any_map__det_insert_from_any_assoc_list(Map0, [K - V | KVs], Map) :-
+ unsafe_cast_to_ground(K),
+ any_map__det_insert(Map0, K, V, Map1),
+ any_map__det_insert_from_any_assoc_list(Map1, KVs, Map).
+
+any_map__set_from_corresponding_lists(Map0, Ks, Vs, Map) :-
+ (
+ Ks = [Key | Keys],
+ Vs = [Value | Values]
+ ->
+ any_map__set(Map0, Key, Value, Map1),
+ any_map__set_from_corresponding_lists(Map1, Keys, Values, Map)
+ ;
+ Ks = [],
+ Vs = []
+ ->
+ Map = Map0
+ ;
+ error("any_map__set_from_corresponding_lists - " ++
+ "lists do not correspond")
+ ).
+
+any_map__set_from_any_assoc_list(Map, [], Map).
+any_map__set_from_any_assoc_list(Map0, [K - V | KVs], Map) :-
+ unsafe_cast_to_ground(K),
+ any_map__set(Map0, K, V, Map1),
+ any_map__set_from_any_assoc_list(Map1, KVs, Map).
+
+any_map__update(Map0, K, V, Map) :-
+ any_tree234__update(Map0, K, V, Map).
+
+any_map__det_update(Map0, K, V, Map) :-
+ ( any_tree234__update(Map0, K, V, Map1) ->
+ Map = Map1
+ ;
+ report_lookup_error("any_map__det_update: key not found", K, V)
+ ).
+
+any_map__transform_value(P, K, !Map) :-
+ any_tree234__transform_value(P, K, !Map).
+
+any_map__det_transform_value(P, K, !Map) :-
+ (
+ any_map__transform_value(P, K, !.Map, NewMap)
+ ->
+ !:Map = NewMap
+ ;
+ report_lookup_error("any_map__det_transform_value: key not found",
+ K)
+ ).
+
+any_map__det_transform_value(F, K, Map0) = Map :-
+ any_map__det_transform_value(pred(V0::ia, V::oa) is det :- V = F(V0), K,
+ Map0, Map).
+
+any_map__set(Map0, K, V, Map) :-
+ any_tree234__set(Map0, K, V, Map).
+
+any_map__keys(Map, KeyList) :-
+ any_tree234__keys(Map, KeyList).
+
+any_map__sorted_keys(Map, KeyList) :-
+ % Guaranteed to yield sorted lists.
+ any_tree234__keys(Map, KeyList).
+
+any_map__values(Map, KeyList) :-
+ any_tree234__values(Map, KeyList).
+
+any_map__to_any_assoc_list(M, L) :-
+ any_tree234__any_tree234_to_any_assoc_list(M, L).
+
+any_map__to_sorted_any_assoc_list(M, L) :-
+ % Guaranteed to yield sorted lists.
+ any_tree234__any_tree234_to_any_assoc_list(M, L).
+
+any_map__from_any_assoc_list(L, M) :-
+ any_tree234__any_assoc_list_to_any_tree234(L, M).
+
+any_map__from_sorted_any_assoc_list(L, M) :-
+ any_tree234__any_assoc_list_to_any_tree234(L, M).
+
+any_map__delete(Map0, Key, Map) :-
+ any_tree234__delete(Map0, Key, Map).
+
+any_map__delete_list(Map, [], Map).
+any_map__delete_list(Map0, [Key | Keys], Map) :-
+ any_map__delete(Map0, Key, Map1),
+ any_map__delete_list(Map1, Keys, Map).
+
+any_map__remove(Map0, Key, Value, Map) :-
+ any_tree234__remove(Map0, Key, Value, Map).
+
+any_map__det_remove(Map0, Key, Value, Map) :-
+ ( any_tree234__remove(Map0, Key, Value1, Map1) ->
+ Value = Value1,
+ Map = Map1
+ ;
+ report_lookup_error("any_map__det_remove: key not found",
+ Key, Value)
+ ).
+
+any_map__count(Map, Count) :-
+ any_tree234__count(Map, Count).
+
+%-----------------------------------------------------------------------------%
+
+any_map__inverse_search(Map, V, K) :-
+ any_map__member(Map, K, V).
+
+%-----------------------------------------------------------------------------%
+
+any_map__from_corresponding_lists(Keys, Values, Map) :-
+ any_assoc_list__from_corresponding_lists(Keys, Values, AssocList),
+ any_tree234__any_assoc_list_to_any_tree234(AssocList, Map).
+
+%-----------------------------------------------------------------------------%
+
+any_map__merge(M0, M1, M) :-
+ any_map__overlay(M0, M1, M).
+
+%-----------------------------------------------------------------------------%
+
+any_map__optimize(Map, Map).
+
+%-----------------------------------------------------------------------------%
+
+any_map__overlay(Map0, Map1, Map) :-
+ any_map__to_any_assoc_list(Map1, AssocList),
+ any_map__overlay_2(AssocList, Map0, Map).
+
+:- pred any_map__overlay_2(any_assoc_list(K, V)::ia, any_map(K, V)::ia,
+ any_map(K, V)::oa) is det.
+
+any_map__overlay_2([], Map, Map).
+any_map__overlay_2([K - V | AssocList], Map0, Map) :-
+ unsafe_cast_to_ground(K),
+ any_map__set(Map0, K, V, Map1),
+ any_map__overlay_2(AssocList, Map1, Map).
+
+any_map__overlay_large_map(Map0, Map1, Map) :-
+ any_map__to_any_assoc_list(Map0, AssocList),
+ any_map__overlay_large_map_2(AssocList, Map1, Map).
+
+:- pred any_map__overlay_large_map_2(any_assoc_list(K, V)::ia,
+ any_map(K, V)::ia, any_map(K, V)::oa) is det.
+
+any_map__overlay_large_map_2([], Map, Map).
+any_map__overlay_large_map_2([K - V | AssocList], Map0, Map) :-
+ unsafe_cast_to_ground(K),
+ ( any_map__insert(Map0, K, V, Map1) ->
+ Map2 = Map1
+ ;
+ Map2 = Map0
+ ),
+ any_map__overlay_large_map_2(AssocList, Map2, Map).
+
+%-----------------------------------------------------------------------------%
+
+any_map__select(Original, KeySet, NewMap) :-
+ set__to_sorted_list(KeySet, KeyList),
+ any_map__init(NewMap0),
+ any_map__select_2(KeyList, Original, NewMap0, NewMap).
+
+:- pred any_map__select_2(list(K)::in, any_map(K, V)::ia, any_map(K, V)::ia,
+ any_map(K, V)::oa) is det.
+
+any_map__select_2([], _Original, New, New).
+any_map__select_2([K|Ks], Original, New0, New) :-
+ ( any_map__search(Original, K, V) ->
+ any_map__set(New0, K, V, New1)
+ ;
+ New1 = New0
+ ),
+ any_map__select_2(Ks, Original, New1, New).
+
+%-----------------------------------------------------------------------------%
+
+any_map__apply_to_list([], _, []).
+any_map__apply_to_list([K | Ks], Map, [V | Vs]) :-
+ any_map__lookup(Map, K, V),
+ any_map__apply_to_list(Ks, Map, Vs).
+
+%-----------------------------------------------------------------------------%
+
+any_map__remove_smallest(Map0, K, V, Map) :-
+ any_tree234__remove_smallest(Map0, K, V, Map).
+
+%-----------------------------------------------------------------------------%
+
+any_map__foldl(Pred, Map, !A) :-
+ any_tree234__foldl(Pred, Map, !A).
+
+any_map__foldl2(Pred, Map, !A, !B) :-
+ any_tree234__foldl2(Pred, Map, !A, !B).
+
+any_map__foldl3(Pred, Map, !A, !B, !C) :-
+ any_tree234__foldl3(Pred, Map, !A, !B, !C).
+
+%-----------------------------------------------------------------------------%
+
+any_map__map_values(Pred, Map0, Map) :-
+ any_tree234__map_values(Pred, Map0, Map).
+
+any_map__map_foldl(Pred, !Map, !Acc) :-
+ any_tree234__map_foldl(Pred, !Map, !Acc).
+
+any_map__map_foldl2(Pred, !Map, !Acc1, !Acc2) :-
+ any_tree234__map_foldl2(Pred, !Map, !Acc1, !Acc2).
+
+%-----------------------------------------------------------------------------%
+
+any_map__intersect(CommonPred, Map1, Map2, Common) :-
+ any_map__to_sorted_any_assoc_list(Map1, AssocList1),
+ any_map__to_sorted_any_assoc_list(Map2, AssocList2),
+ any_map__init(Common0),
+ any_map__intersect_2(AssocList1, AssocList2, CommonPred, Common0, Common).
+
+:- pred any_map__intersect_2(any_assoc_list(K, V), any_assoc_list(K, V),
+ pred(V, V, V), any_map(K, V), any_map(K, V)).
+:- mode any_map__intersect_2(ia, ia, pred(ia, ia, oa) is semidet, ia, oa)
+ is semidet.
+:- mode any_map__intersect_2(ia, ia, pred(ia, ia, oa) is det, ia, oa)
+ is det.
+
+any_map__intersect_2(AssocList1, AssocList2, CommonPred, Common0, Common) :-
+ (
+ AssocList1 = [],
+ AssocList2 = [],
+ Common = Common0
+ ;
+ AssocList1 = [_ | _],
+ AssocList2 = [],
+ Common = Common0
+ ;
+ AssocList1 = [],
+ AssocList2 = [_ | _],
+ Common = Common0
+ ;
+ AssocList1 = [Key1 - Value1 | AssocTail1],
+ AssocList2 = [Key2 - Value2 | AssocTail2],
+ unsafe_cast_to_ground(Key1),
+ unsafe_cast_to_ground(Key2),
+ compare(R, Key1, Key2),
+ (
+ R = (=),
+ call(CommonPred, Value1, Value2, Value),
+ any_map__det_insert(Common0, Key1, Value, Common1),
+ any_map__intersect_2(AssocTail1, AssocTail2, CommonPred,
+ Common1, Common)
+ ;
+ R = (<),
+ any_map__intersect_2(AssocTail1, AssocList2, CommonPred,
+ Common0, Common)
+ ;
+ R = (>),
+ any_map__intersect_2(AssocList1, AssocTail2, CommonPred,
+ Common0, Common)
+ )
+ ).
+
+any_map__det_intersect(CommonPred, Map1, Map2, Common) :-
+ ( any_map__intersect(CommonPred, Map1, Map2, CommonPrime) ->
+ Common = CommonPrime
+ ;
+ error("any_map__det_intersect: any_map__intersect failed")
+ ).
+
+%-----------------------------------------------------------------------------%
+
+any_map__common_subset(Map1, Map2) = Common :-
+ any_map__to_sorted_any_assoc_list(Map1, AssocList1),
+ any_map__to_sorted_any_assoc_list(Map2, AssocList2),
+ any_map__init(Common0),
+ any_map__common_subset_2(AssocList1, AssocList2, Common0) = Common.
+
+:- func any_map__common_subset_2(any_assoc_list(K, V)::ia,
+ any_assoc_list(K, V)::ia, any_map(K, V)::ia) = (any_map(K, V)::oa)
+ is det.
+
+any_map__common_subset_2(AssocList1, AssocList2, Common0) = Common :-
+ (
+ AssocList1 = [],
+ AssocList2 = [],
+ Common = Common0
+ ;
+ AssocList1 = [_ | _],
+ AssocList2 = [],
+ Common = Common0
+ ;
+ AssocList1 = [],
+ AssocList2 = [_ | _],
+ Common = Common0
+ ;
+ AssocList1 = [Key1 - Value1 | AssocTail1],
+ AssocList2 = [Key2 - Value2 | AssocTail2],
+ unsafe_cast_to_ground(Key1),
+ unsafe_cast_to_ground(Key2),
+ compare(R, Key1, Key2),
+ (
+ R = (=),
+ ( Value1 = Value2 ->
+ any_map__det_insert(Common0, Key1, Value1, Common1)
+ ;
+ Common1 = Common0
+ ),
+ Common = any_map__common_subset_2(AssocTail1, AssocTail2,
+ Common1)
+ ;
+ R = (<),
+ Common = any_map__common_subset_2(AssocTail1, AssocList2,
+ Common0)
+ ;
+ R = (>),
+ Common = any_map__common_subset_2(AssocList1, AssocTail2,
+ Common0)
+ )
+ ).
+
+%-----------------------------------------------------------------------------%
+
+any_map__union(CommonPred, Map1, Map2, Common) :-
+ any_map__to_sorted_any_assoc_list(Map1, AssocList1),
+ any_map__to_sorted_any_assoc_list(Map2, AssocList2),
+ any_map__init(Common0),
+ any_map__union_2(AssocList1, AssocList2, CommonPred, Common0, Common).
+
+:- pred any_map__union_2(any_assoc_list(K, V), any_assoc_list(K, V),
+ pred(V, V, V), any_map(K, V), any_map(K, V)).
+:- mode any_map__union_2(ia, ia, pred(ia, ia, oa) is semidet, ia, oa)
+ is semidet.
+:- mode any_map__union_2(ia, ia, pred(ia, ia, oa) is det, ia, oa)
+ is det.
+
+any_map__union_2(AssocList1, AssocList2, CommonPred, Common0, Common) :-
+ (
+ AssocList1 = [],
+ AssocList2 = [],
+ Common = Common0
+ ;
+ AssocList1 = [_ | _],
+ AssocList2 = [],
+ any_map__det_insert_from_any_assoc_list(Common0, AssocList1, Common)
+ ;
+ AssocList1 = [],
+ AssocList2 = [_ | _],
+ any_map__det_insert_from_any_assoc_list(Common0, AssocList2, Common)
+ ;
+ AssocList1 = [Key1 - Value1 | AssocTail1],
+ AssocList2 = [Key2 - Value2 | AssocTail2],
+ unsafe_cast_to_ground(Key1),
+ unsafe_cast_to_ground(Key2),
+ compare(R, Key1, Key2),
+ (
+ R = (=),
+ call(CommonPred, Value1, Value2, Value),
+ any_map__det_insert(Common0, Key1, Value, Common1),
+ any_map__union_2(AssocTail1, AssocTail2, CommonPred,
+ Common1, Common)
+ ;
+ R = (<),
+ any_map__det_insert(Common0, Key1, Value1, Common1),
+ any_map__union_2(AssocTail1, AssocList2, CommonPred,
+ Common1, Common)
+ ;
+ R = (>),
+ any_map__det_insert(Common0, Key2, Value2, Common1),
+ any_map__union_2(AssocList1, AssocTail2, CommonPred,
+ Common1, Common)
+ )
+ ).
+
+any_map__det_union(CommonPred, Map1, Map2, Union) :-
+ ( any_map__union(CommonPred, Map1, Map2, UnionPrime) ->
+ Union = UnionPrime
+ ;
+ error("any_map__det_union: any_map__union failed")
+ ).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+% Ralph Becket <rwab1 at cl.cam.ac.uk> 27/04/99
+% Functional forms added.
+
+any_map__init = M :-
+ any_map__init(M).
+
+any_map__search(M, K) = V :-
+ any_map__search(M, K, V).
+
+any_map__lookup(M, K) = V :-
+ any_map__lookup(M, K, V).
+
+any_map__insert(M1, K, V) = M2 :-
+ any_map__insert(M1, K, V, M2).
+
+any_map__det_insert(M1, K, V) = M2 :-
+ any_map__det_insert(M1, K, V, M2).
+
+any_map__det_insert_from_corresponding_lists(M1, Ks, Vs) = M2 :-
+ any_map__det_insert_from_corresponding_lists(M1, Ks, Vs, M2).
+
+any_map__det_insert_from_any_assoc_list(M1, AL) = M2 :-
+ any_map__det_insert_from_any_assoc_list(M1, AL, M2).
+
+any_map__set_from_corresponding_lists(M1, Ks, Vs) = M2 :-
+ any_map__set_from_corresponding_lists(M1, Ks, Vs, M2).
+
+any_map__set_from_any_assoc_list(M1, AL) = M2 :-
+ any_map__set_from_any_assoc_list(M1, AL, M2).
+
+any_map__update(M1, K, V) = M2 :-
+ any_map__update(M1, K, V, M2).
+
+any_map__det_update(M1, K, V) = M2 :-
+ any_map__det_update(M1, K, V, M2).
+
+any_map__set(M1, K, V) = M2 :-
+ any_map__set(M1, K, V, M2).
+
+any_map__keys(M) = Ks :-
+ any_map__keys(M, Ks).
+
+any_map__sorted_keys(M) = Ks :-
+ any_map__sorted_keys(M, Ks).
+
+any_map__values(M) = Vs :-
+ any_map__values(M, Vs).
+
+any_map__to_any_assoc_list(M) = AL :-
+ any_map__to_any_assoc_list(M, AL).
+
+any_map__to_sorted_any_assoc_list(M) = AL :-
+ any_map__to_sorted_any_assoc_list(M, AL).
+
+any_map__from_any_assoc_list(AL) = M :-
+ any_map__from_any_assoc_list(AL, M).
+
+any_map__from_sorted_any_assoc_list(AL) = M :-
+ any_map__from_sorted_any_assoc_list(AL, M).
+
+any_map__delete(M1, K) = M2 :-
+ any_map__delete(M1, K, M2).
+
+any_map__delete_list(M1, Ks) = M2 :-
+ any_map__delete_list(M1, Ks, M2).
+
+any_map__count(M) = N :-
+ any_map__count(M, N).
+any_map__from_corresponding_lists(Ks, Vs) = M :-
+ any_map__from_corresponding_lists(Ks, Vs, M).
+
+any_map__merge(M1, M2) = M3 :-
+ any_map__merge(M1, M2, M3).
+
+any_map__overlay(M1, M2) = M3 :-
+ any_map__overlay(M1, M2, M3).
+
+any_map__overlay_large_map(M1, M2) = M3 :-
+ any_map__overlay_large_map(M1, M2, M3).
+
+any_map__select(M1, S) = M2 :-
+ any_map__select(M1, S, M2).
+
+any_map__apply_to_list(Ks, M) = Vs :-
+ any_map__apply_to_list(Ks, M, Vs).
+
+any_map__optimize(M1) = M2 :-
+ any_map__optimize(M1, M2).
+
+:- pragma promise_pure(any_map__foldl/3).
+
+any_map__foldl(F::in(func(in, ia, in) = out is det), M::ia, A::in) = (B::out) :-
+ P = ( pred(W::in, X::ia, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
+ any_map__foldl(P, M, A, B).
+
+any_map__foldl(F::in(func(in, ia, ia) = oa is det), M::ia, A::ia) = (B::oa) :-
+ P = ( pred(W::in, X::ia, Y::ia, Z::oa) is det :- Z = F(W, X, Y) ),
+ any_map__foldl(P, M, A, B).
+
+any_map__map_values(F, M1) = M2 :-
+ P = ( pred(X::in, Y::ia, Z::oa) is det :- Z = F(X, Y) ),
+ any_map__map_values(P, M1, M2).
+
+any_map__intersect(F, M1, M2) = M3 :-
+ P = ( pred(X::ia, Y::ia, Z::oa) is det :- Z = F(X, Y) ),
+ any_map__intersect(P, M1, M2, M3).
+
+any_map__det_intersect(PF, M1, M2) = M3 :-
+ P = ( pred(X::ia, Y::ia, Z::oa) is semidet :- Z = PF(X, Y) ),
+ any_map__det_intersect(P, M1, M2, M3).
+
+any_map__union(F, M1, M2) = M3 :-
+ P = ( pred(X::ia, Y::ia, Z::oa) is det :- Z = F(X, Y) ),
+ any_map__union(P, M1, M2, M3).
+
+any_map__det_union(F, M1, M2) = M3 :-
+ P = ( pred(X::ia, Y::ia, Z::oa) is semidet :- Z = F(X, Y) ),
+ any_map__det_union(P, M1, M2, M3).
+
+any_map__elem(Key, Map) = any_map__search(Map, Key).
+
+any_map__det_elem(Key, Map) = any_map__lookup(Map, Key).
+
+'any_map__elem :='(Key, Map, Value) = any_map__set(Map, Key, Value).
+
+'any_map__det_elem :='(Key, Map, Value) = any_map__det_update(Map, Key, Value).
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
Index: extras/solver_types/library/any_tree234.m
===================================================================
RCS file: extras/solver_types/library/any_tree234.m
diff -N extras/solver_types/library/any_tree234.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ extras/solver_types/library/any_tree234.m 9 Sep 2005 05:55:53 -0000
@@ -0,0 +1,2803 @@
+% vim: ft=mercury ts=4 sw=4 et
+%---------------------------------------------------------------------------%
+% Copyright (C) 1994-1997,1999-2000,2002-2005 The University of Melbourne.
+% This file may only be copied under the terms of the GNU Library General
+% Public License - see the file COPYING.LIB in the Mercury distribution.
+%---------------------------------------------------------------------------%
+% any_tree234.m
+% Ralph Becket <rafe at cs.mu.oz.au>
+% Wed Sep 7 19:44:11 EST 2005
+%
+% A version of tree234.m for use with values with inst any.
+% This is needed by any_map.m.
+%---------------------------------------------------------------------------%
+
+:- module any_tree234.
+
+:- interface.
+
+:- import_module any_assoc_list.
+:- import_module any_list.
+:- import_module list.
+
+:- type any_tree234(K, V).
+
+:- func any_tree234__init = (any_tree234(K, V)::oa) is det.
+:- pred any_tree234__init(any_tree234(K, V)::oa) is det.
+
+:- pred any_tree234__is_empty(any_tree234(K, V)::ia) is semidet.
+
+:- pred any_tree234__member(any_tree234(K, V)::ia, K::out, V::oa) is nondet.
+
+:- pred any_tree234__search(any_tree234(K, V)::ia, K::in, V::oa) is semidet.
+
+:- func any_tree234__lookup(any_tree234(K, V)::ia, K::in) = (V::oa) is det.
+:- pred any_tree234__lookup(any_tree234(K, V)::ia, K::in, V::oa) is det.
+
+ % Search for a key-value pair using the key. If there is no entry
+ % for the given key, returns the pair for the next lower key instead.
+ % Fails if there is no key with the given or lower value.
+ %
+:- pred any_tree234__lower_bound_search(any_tree234(K, V)::ia, K::in, K::out,
+ V::oa) is semidet.
+
+ % Search for a key-value pair using the key. If there is no entry
+ % for the given key, returns the pair for the next lower key instead.
+ % Aborts if there is no key with the given or lower value.
+ %
+:- pred any_tree234__lower_bound_lookup(any_tree234(K, V)::ia, K::in, K::out,
+ V::oa) is det.
+
+ % Search for a key-value pair using the key. If there is no entry
+ % for the given key, returns the pair for the next higher key instead.
+ % Fails if there is no key with the given or higher value.
+ %
+:- pred any_tree234__upper_bound_search(any_tree234(K, V)::ia, K::in, K::out,
+ V::oa) is semidet.
+
+ % Search for a key-value pair using the key. If there is no entry
+ % for the given key, returns the pair for the next higher key instead.
+ % Aborts if there is no key with the given or higher value.
+ %
+:- pred any_tree234__upper_bound_lookup(any_tree234(K, V)::ia, K::in, K::out,
+ V::oa) is det.
+
+:- func any_tree234__max_key(any_tree234(K, V)::ia) = (K::out) is semidet.
+
+:- func any_tree234__min_key(any_tree234(K, V)::ia) = (K::out) is semidet.
+
+:- pred any_tree234__insert(any_tree234(K, V)::ia, K::in, V::ia,
+ any_tree234(K, V)::oa) is semidet.
+
+:- func any_tree234__set(any_tree234(K, V)::ia, K::in, V::ia)
+ = (any_tree234(K, V)::oa) is det.
+:- pred any_tree234__set(any_tree234(K, V)::ia, K::in, V::ia,
+ any_tree234(K, V)::oa) is det.
+
+:- func any_tree234__delete(any_tree234(K, V)::ia, K::in)
+ = (any_tree234(K, V)::oa) is det.
+:- pred any_tree234__delete(any_tree234(K, V)::ia, K::in,
+ any_tree234(K, V)::oa) is det.
+
+:- pred any_tree234__remove(any_tree234(K, V)::ia, K::in, V::oa,
+ any_tree234(K, V)::oa) is semidet.
+
+:- pred any_tree234__remove_smallest(any_tree234(K, V)::ia, K::out, V::oa,
+ any_tree234(K, V)::oa) is semidet.
+
+ % Given a any_tree234, return a list of all the keys ia the tree.
+ % The list that is returned is ia sorted order.
+ %
+:- func any_tree234__keys(any_tree234(K, V)::ia) = (list(K)::out) is det.
+:- pred any_tree234__keys(any_tree234(K, V)::ia, list(K)::out) is det.
+
+:- func any_tree234__values(any_tree234(K, V)::ia) = (any_list(V)::oa) is det.
+:- pred any_tree234__values(any_tree234(K, V)::ia, any_list(V)::oa) is det.
+
+:- pred any_tree234__update(any_tree234(K, V)::ia, K::in, V::ia,
+ any_tree234(K, V)::oa) 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 any_tree234__transform_value(pred(V, V)::in(pred(ia, oa) is det),
+ K::in, any_tree234(K, V)::ia, any_tree234(K, V)::oa) is semidet.
+
+ % Count the number of elements ia a tree.
+ %
+:- func any_tree234__count(any_tree234(K, V)::ia) = (int::out) is det.
+:- pred any_tree234__count(any_tree234(K, V)::ia, int::oa) is det.
+
+:- func any_tree234__any_assoc_list_to_any_tree234(any_assoc_list(K, V)::ia)
+ = (any_tree234(K, V)::oa) is det.
+:- pred any_tree234__any_assoc_list_to_any_tree234(any_assoc_list(K, V)::ia,
+ any_tree234(K, V)::oa) is det.
+
+ % Given a any_tree234, return an association list of all the
+ % keys and values ia the tree. The association list that
+ % is returned is sorted on the keys.
+ %
+:- func any_tree234__any_tree234_to_any_assoc_list(any_tree234(K, V)::ia)
+ = (any_assoc_list(K, V)::oa) is det.
+:- pred any_tree234__any_tree234_to_any_assoc_list(any_tree234(K, V)::ia,
+ any_assoc_list(K, V)::oa) is det.
+
+:- func any_tree234__foldl(func(K, V, T) = T, any_tree234(K, V), T) = T.
+:- mode any_tree234__foldl(func(in, ia, in) = out is det, ia, in) = out is det.
+:- mode any_tree234__foldl(func(in, ia, ia) = oa is det, ia, ia) = oa is det.
+
+:- pred any_tree234__foldl(pred(K, V, T, T), any_tree234(K, V), T, T).
+:- mode any_tree234__foldl(pred(in, ia, di, uo) is det, ia, di, uo)
+ is det.
+:- mode any_tree234__foldl(pred(in, ia, in, out) is det, ia, in, out)
+ is det.
+:- mode any_tree234__foldl(pred(in, ia, in, out) is semidet, ia, in, out)
+ is semidet.
+:- mode any_tree234__foldl(pred(in, ia, ia, oa) is det, ia, ia, oa)
+ is det.
+:- mode any_tree234__foldl(pred(in, ia, ia, oa) is semidet, ia, ia, oa)
+ is semidet.
+
+:- pred any_tree234__foldl2(pred(K, V, T, T, U, U),
+ any_tree234(K, V), T, T, U, U).
+:- mode any_tree234__foldl2(pred(in, ia, di, uo, di, uo) is det,
+ ia, di, uo, di, uo) is det.
+:- mode any_tree234__foldl2(pred(in, ia, in, out, di, uo) is det,
+ ia, in, out, di, uo) is det.
+:- mode any_tree234__foldl2(pred(in, ia, ia, oa, di, uo) is det,
+ ia, ia, oa, di, uo) is det.
+:- mode any_tree234__foldl2(pred(in, ia, in, out, in, out) is det,
+ ia, in, out, in, out) is det.
+:- mode any_tree234__foldl2(pred(in, ia, in, out, in, out) is semidet,
+ ia, in, out, in, out) is semidet.
+:- mode any_tree234__foldl2(pred(in, ia, ia, oa, in, out) is det,
+ ia, ia, oa, in, out) is det.
+:- mode any_tree234__foldl2(pred(in, ia, ia, oa, in, out) is semidet,
+ ia, ia, oa, in, out) is semidet.
+:- mode any_tree234__foldl2(pred(in, ia, ia, oa, ia, oa) is det,
+ ia, ia, oa, ia, oa) is det.
+:- mode any_tree234__foldl2(pred(in, ia, ia, oa, ia, oa) is semidet,
+ ia, ia, oa, ia, oa) is semidet.
+
+:- pred any_tree234__foldl3(pred(K, V, T, T, U, U, W, W), any_tree234(K, V),
+ T, T, U, U, W, W).
+:- mode any_tree234__foldl3(pred(in, ia, di, uo, di, uo, di, uo) is det,
+ ia, di, uo, di, uo, di, uo) is det.
+:- mode any_tree234__foldl3(pred(in, ia, in, out, di, uo, di, uo) is det,
+ ia, in, out, di, uo, di, uo) is det.
+:- mode any_tree234__foldl3(pred(in, ia, in, out, in, out, di, uo) is det,
+ ia, in, out, in, out, di, uo) is det.
+:- mode any_tree234__foldl3(pred(in, ia, in, out, in, out, in, out) is det,
+ ia, in, out, in, out, in, out) is det.
+:- mode any_tree234__foldl3(pred(in, ia, in, out, in, out, in, out) is semidet,
+ ia, in, out, in, out, in, out) is semidet.
+:- mode any_tree234__foldl3(pred(in, ia, ia, oa, in, out, in, out) is det,
+ ia, ia, oa, in, out, in, out) is det.
+:- mode any_tree234__foldl3(pred(in, ia, ia, oa, in, out, in, out) is semidet,
+ ia, ia, oa, in, out, in, out) is semidet.
+:- mode any_tree234__foldl3(pred(in, ia, ia, oa, ia, oa, in, out) is det,
+ ia, ia, oa, ia, oa, in, out) is det.
+:- mode any_tree234__foldl3(pred(in, ia, ia, oa, ia, oa, in, out) is semidet,
+ ia, ia, oa, ia, oa, in, out) is semidet.
+:- mode any_tree234__foldl3(pred(in, ia, ia, oa, ia, oa, ia, oa) is det,
+ ia, ia, oa, ia, oa, ia, oa) is det.
+:- mode any_tree234__foldl3(pred(in, ia, ia, oa, ia, oa, ia, oa) is semidet,
+ ia, ia, oa, ia, oa, ia, oa) is semidet.
+
+:- func any_tree234__map_values(func(K, V) = W, any_tree234(K, V))
+ = any_tree234(K, W).
+:- mode any_tree234__map_values(func(in, ia) = oa is det, ia)
+ = oa is det.
+
+:- pred any_tree234__map_values(pred(K, V, W), any_tree234(K, V),
+ any_tree234(K, W)).
+:- mode any_tree234__map_values(pred(in, ia, oa) is det, ia, oa)
+ is det.
+:- mode any_tree234__map_values(pred(in, ia, oa) is semidet, ia, oa)
+ is semidet.
+
+:- pred any_tree234__map_foldl(pred(K, V, W, A, A),
+ any_tree234(K, V), any_tree234(K, W), A, A).
+:- mode any_tree234__map_foldl(pred(in, ia, oa, di, uo) is det, ia, oa,
+ di, uo) is det.
+:- mode any_tree234__map_foldl(pred(in, ia, oa, in, out) is det, ia, oa,
+ in, out) is det.
+:- mode any_tree234__map_foldl(pred(in, ia, oa, in, out) is semidet, ia, oa,
+ in, out) is semidet.
+:- mode any_tree234__map_foldl(pred(in, ia, oa, ia, oa) is det, ia, oa,
+ ia, oa) is det.
+:- mode any_tree234__map_foldl(pred(in, ia, oa, ia, oa) is semidet, ia, oa,
+ ia, oa) is semidet.
+
+:- pred any_tree234__map_foldl2(pred(K, V, W, A, A, B, B),
+ any_tree234(K, V), any_tree234(K, W), A, A, B, B).
+:- mode any_tree234__map_foldl2(pred(in, ia, oa, in, out, di, uo) is det,
+ ia, oa, in, out, di, uo) is det.
+:- mode any_tree234__map_foldl2(pred(in, ia, oa, in, out, in, out) is det,
+ ia, oa, in, out, in, out) is det.
+:- mode any_tree234__map_foldl2(pred(in, ia, oa, in, out, in, out) is semidet,
+ ia, oa, in, out, in, out) is semidet.
+:- mode any_tree234__map_foldl2(pred(in, ia, oa, ia, oa, in, out) is det,
+ ia, oa, ia, oa, in, out) is det.
+:- mode any_tree234__map_foldl2(pred(in, ia, oa, ia, oa, in, out) is semidet,
+ ia, oa, ia, oa, in, out) is semidet.
+:- mode any_tree234__map_foldl2(pred(in, ia, oa, ia, oa, ia, oa) is det,
+ ia, oa, ia, oa, ia, oa) is det.
+:- mode any_tree234__map_foldl2(pred(in, ia, oa, ia, oa, ia, oa) is semidet,
+ ia, oa, ia, oa, ia, oa) is semidet.
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module any_util.
+:- import_module bool.
+:- import_module int.
+:- import_module require.
+:- import_module std_util.
+
+:- type any_tree234(K, V)
+ ---> empty
+ ; two(K, V,
+ any_tree234(K, V), any_tree234(K, V))
+ ; three(K, V, K, V,
+ any_tree234(K, V), any_tree234(K, V), any_tree234(K, V))
+ ; four(K, V, K, V, K, V,
+ any_tree234(K, V), any_tree234(K, V),
+ any_tree234(K, V), any_tree234(K, V)).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__init(empty).
+
+any_tree234__is_empty(Tree) :-
+ Tree = empty.
+
+%------------------------------------------------------------------------------%
+
+any_tree234__member(empty, _K, _V) :- fail.
+any_tree234__member(two(K0, V0, T0, T1), K, V) :-
+ (
+ unsafe_cast_to_ground(K0),
+ K = K0,
+ V = V0
+ ;
+ any_tree234__member(T0, K, V)
+ ;
+ any_tree234__member(T1, K, V)
+ ).
+any_tree234__member(three(K0, V0, K1, V1, T0, T1, T2), K, V) :-
+ (
+ unsafe_cast_to_ground(K0),
+ K = K0,
+ V = V0
+ ;
+ unsafe_cast_to_ground(K1),
+ K = K1,
+ V = V1
+ ;
+ any_tree234__member(T0, K, V)
+ ;
+ any_tree234__member(T1, K, V)
+ ;
+ any_tree234__member(T2, K, V)
+ ).
+any_tree234__member(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), K, V) :-
+ (
+ unsafe_cast_to_ground(K0),
+ K = K0,
+ V = V0
+ ;
+ unsafe_cast_to_ground(K1),
+ K = K1,
+ V = V1
+ ;
+ unsafe_cast_to_ground(K2),
+ K = K2,
+ V = V2
+ ;
+ any_tree234__member(T0, K, V)
+ ;
+ any_tree234__member(T1, K, V)
+ ;
+ any_tree234__member(T2, K, V)
+ ;
+ any_tree234__member(T3, K, V)
+ ).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__search(T, K, V) :-
+ (
+ T = empty,
+ fail
+ ;
+ T = two(K0, V0, T0, T1),
+ unsafe_cast_to_ground(K0),
+ compare(Result, K, K0),
+ (
+ Result = (<),
+ any_tree234__search(T0, K, V)
+ ;
+ Result = (=),
+ V = V0
+ ;
+ Result = (>),
+ any_tree234__search(T1, K, V)
+ )
+ ;
+ T = three(K0, V0, K1, V1, T0, T1, T2),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__search(T0, K, V)
+ ;
+ Result0 = (=),
+ V = V0
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ any_tree234__search(T1, K, V)
+ ;
+ Result1 = (=),
+ V = V1
+ ;
+ Result1 = (>),
+ any_tree234__search(T2, K, V)
+ )
+ )
+ ;
+ T = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__search(T0, K, V)
+ ;
+ Result0 = (=),
+ V = V0
+ ;
+ Result0 = (>),
+ any_tree234__search(T1, K, V)
+ )
+ ;
+ Result1 = (=),
+ V = V1
+ ;
+ Result1 = (>),
+ unsafe_cast_to_ground(K2),
+ compare(Result2, K, K2),
+ (
+ Result2 = (<),
+ any_tree234__search(T2, K, V)
+ ;
+ Result2 = (=),
+ V = V2
+ ;
+ Result2 = (>),
+ any_tree234__search(T3, K, V)
+ )
+ )
+ ).
+
+any_tree234__lookup(T, K, V) :-
+ ( any_tree234__search(T, K, V0) ->
+ V = V0
+ ;
+ report_lookup_error("any_tree234__lookup: key not found.", K, V)
+ ).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__lower_bound_search(T, SearchK, K, V) :-
+ (
+ T = empty,
+ fail
+ ;
+ T = two(K0, V0, T0, T1),
+ unsafe_cast_to_ground(K0),
+ compare(Result, SearchK, K0),
+ (
+ Result = (<),
+ any_tree234__lower_bound_search(T0, SearchK, K, V)
+ ;
+ Result = (=),
+ K = SearchK,
+ V = V0
+ ;
+ Result = (>),
+ ( any_tree234__lower_bound_search(T1, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ T = two(_, V0, _, _),
+ K = K0,
+ V = V0
+ )
+ )
+ ;
+ T = three(K0, V0, K1, V1, T0, T1, T2),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, SearchK, K0),
+ (
+ Result0 = (<),
+ any_tree234__lower_bound_search(T0, SearchK, K, V)
+ ;
+ Result0 = (=),
+ K = SearchK,
+ V = V0
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, SearchK, K1),
+ (
+ Result1 = (<),
+ ( any_tree234__lower_bound_search(T1, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ T = three(_, V0, _, _, _, _, _),
+ K = K0,
+ V = V0
+ )
+ ;
+ Result1 = (=),
+ K = SearchK,
+ V = V1
+ ;
+ Result1 = (>),
+ ( any_tree234__lower_bound_search(T2, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K1,
+ V = V1
+ )
+ )
+ )
+ ;
+ T = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, SearchK, K1),
+ (
+ Result1 = (<),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, SearchK, K0),
+ (
+ Result0 = (<),
+ any_tree234__lower_bound_search(T0, SearchK, K, V)
+ ;
+ Result0 = (=),
+ K = SearchK,
+ V = V0
+ ;
+ Result0 = (>),
+ ( any_tree234__lower_bound_search(T1, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K0,
+ V = V0
+ )
+ )
+ ;
+ Result1 = (=),
+ K = SearchK,
+ V = V1
+ ;
+ Result1 = (>),
+ unsafe_cast_to_ground(K2),
+ compare(Result2, SearchK, K2),
+ (
+ Result2 = (<),
+ ( any_tree234__lower_bound_search(T2, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K1,
+ V = V1
+ )
+ ;
+ Result2 = (=),
+ K = SearchK,
+ V = V2
+ ;
+ Result2 = (>),
+ ( any_tree234__lower_bound_search(T3, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K2,
+ V = V2
+ )
+ )
+ )
+ ).
+
+any_tree234__lower_bound_lookup(T, SearchK, K, V) :-
+ ( any_tree234__lower_bound_search(T, SearchK, K0, V0) ->
+ K = K0,
+ V = V0
+ ;
+ report_lookup_error("any_tree234__lower_bound_lookup: key not found.",
+ SearchK, V)
+ ).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__upper_bound_search(T, SearchK, K, V) :-
+ (
+ T = empty,
+ fail
+ ;
+ T = two(K0, V0, T0, T1),
+ unsafe_cast_to_ground(K0),
+ compare(Result, SearchK, K0),
+ (
+ Result = (<),
+ ( any_tree234__upper_bound_search(T0, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ T = two(_, V0, _, _),
+ K = K0,
+ V = V0
+ )
+ ;
+ Result = (=),
+ K = SearchK,
+ V = V0
+ ;
+ Result = (>),
+ any_tree234__upper_bound_search(T1, SearchK, K, V)
+ )
+ ;
+ T = three(K0, V0, K1, V1, T0, T1, T2),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, SearchK, K0),
+ (
+ Result0 = (<),
+ ( any_tree234__upper_bound_search(T0, SearchK, Kp, Vp) ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K0,
+ V = V0
+ )
+ ;
+ Result0 = (=),
+ K = SearchK,
+ V = V0
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, SearchK, K1),
+ (
+ Result1 = (<),
+ ( any_tree234__upper_bound_search(T1, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K1,
+ V = V1
+ )
+ ;
+ Result1 = (=),
+ K = SearchK,
+ V = V1
+ ;
+ Result1 = (>),
+ any_tree234__upper_bound_search(T2, SearchK, K, V)
+ )
+ )
+ ;
+ T = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, SearchK, K1),
+ (
+ Result1 = (<),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, SearchK, K0),
+ (
+ Result0 = (<),
+ ( any_tree234__upper_bound_search(T0, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K0,
+ V = V0
+ )
+ ;
+ Result0 = (=),
+ K = SearchK,
+ V = V0
+ ;
+ Result0 = (>),
+ ( any_tree234__upper_bound_search(T1, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K1,
+ V = V1
+ )
+ )
+ ;
+ Result1 = (=),
+ K = SearchK,
+ V = V1
+ ;
+ Result1 = (>),
+ unsafe_cast_to_ground(K2),
+ compare(Result2, SearchK, K2),
+ (
+ Result2 = (<),
+ ( any_tree234__upper_bound_search(T2, SearchK,
+ Kp, Vp)
+ ->
+ K = Kp,
+ V = Vp
+ ;
+ K = K2,
+ V = V2
+ )
+ ;
+ Result2 = (=),
+ K = SearchK,
+ V = V2
+ ;
+ Result2 = (>),
+ any_tree234__upper_bound_search(T3, SearchK, K, V)
+ )
+ )
+ ).
+
+any_tree234__upper_bound_lookup(T, SearchK, K, V) :-
+ ( any_tree234__upper_bound_search(T, SearchK, K0, V0) ->
+ K = K0,
+ V = V0
+ ;
+ report_lookup_error("any_tree234__upper_bound_lookup: key not found.",
+ SearchK, V)
+ ).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__max_key(T0) = MaxKey :-
+ ( T0 = two(NodeMaxKey, _, _, NodeMaxSubtree)
+ ; T0 = three(_, _, NodeMaxKey, _, _, _, NodeMaxSubtree)
+ ; T0 = four(_, _, _, _, NodeMaxKey, _, _, _, _, NodeMaxSubtree)
+ ),
+ ( MaxSubtreeKey = any_tree234__max_key(NodeMaxSubtree) ->
+ MaxKey = MaxSubtreeKey
+ ;
+ MaxKey = NodeMaxKey
+ ),
+ unsafe_cast_to_ground(MaxKey).
+
+any_tree234__min_key(T0) = MinKey :-
+ ( T0 = two(NodeMinKey, _, NodeMinSubtree, _)
+ ; T0 = three(NodeMinKey, _, _, _, NodeMinSubtree, _, _)
+ ; T0 = four(NodeMinKey, _, _, _, _, _, NodeMinSubtree, _, _, _)
+ ),
+ ( MinSubtreeKey = any_tree234__min_key(NodeMinSubtree) ->
+ MinKey = MinSubtreeKey
+ ;
+ MinKey = NodeMinKey
+ ),
+ unsafe_cast_to_ground(MinKey).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__update(Tin, K, V, Tout) :-
+ (
+ Tin = empty,
+ fail
+ ;
+ Tin = two(K0, V0, T0, T1),
+ unsafe_cast_to_ground(K0),
+ compare(Result, K, K0),
+ (
+ Result = (<),
+ any_tree234__update(T0, K, V, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
+ ;
+ Result = (=),
+ Tout = two(K0, V, T0, T1)
+ ;
+ Result = (>),
+ any_tree234__update(T1, K, V, NewT1),
+ Tout = two(K0, V0, T0, NewT1)
+ )
+ ;
+ Tin = three(K0, V0, K1, V1, T0, T1, T2),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__update(T0, K, V, NewT0),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
+ ;
+ Result0 = (=),
+ Tout = three(K0, V, K1, V1, T0, T1, T2)
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ any_tree234__update(T1, K, V, NewT1),
+ Tout = three(K0, V0, K1, V1, T0, NewT1, T2)
+ ;
+ Result1 = (=),
+ Tout = three(K0, V0, K1, V, T0, T1, T2)
+ ;
+ Result1 = (>),
+ any_tree234__update(T2, K, V, NewT2),
+ Tout = three(K0, V0, K1, V1, T0, T1, NewT2)
+ )
+ )
+ ;
+ Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__update(T0, K, V, NewT0),
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ NewT0, T1, T2, T3)
+ ;
+ Result0 = (=),
+ Tout = four(K0, V, K1, V1, K2, V2,
+ T0, T1, T2, T3)
+ ;
+ Result0 = (>),
+ any_tree234__update(T1, K, V, NewT1),
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ T0, NewT1, T2, T3)
+ )
+ ;
+ Result1 = (=),
+ Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
+ ;
+ Result1 = (>),
+ unsafe_cast_to_ground(K2),
+ compare(Result2, K, K2),
+ (
+ Result2 = (<),
+ any_tree234__update(T2, K, V, 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 = (>),
+ any_tree234__update(T3, K, V, NewT3),
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ T0, T1, T2, NewT3)
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__transform_value(P, K, Tin, Tout) :-
+ (
+ Tin = empty,
+ fail
+ ;
+ Tin = two(K0, V0, T0, T1),
+ unsafe_cast_to_ground(K0),
+ compare(Result, K, K0),
+ (
+ Result = (<),
+ any_tree234__transform_value(P, K, T0, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
+ ;
+ Result = (=),
+ P(V0, VNew),
+ Tout = two(K0, VNew, T0, T1)
+ ;
+ Result = (>),
+ any_tree234__transform_value(P, K, T1, NewT1),
+ Tout = two(K0, V0, T0, NewT1)
+ )
+ ;
+ Tin = three(K0, V0, K1, V1, T0, T1, T2),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_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 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ any_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 = (>),
+ any_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),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_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 = (>),
+ any_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 = (>),
+ unsafe_cast_to_ground(K2),
+ compare(Result2, K, K2),
+ (
+ Result2 = (<),
+ any_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 = (>),
+ any_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).
+
+%------------------------------------------------------------------------------%
+
+:- pred any_tree234__split_four(any_tree234(K, V)::in(four(any, any, any)),
+ K::oa, V::oa,
+ any_tree234(K, V)::out(two(any, any, any)),
+ any_tree234(K, V)::out(two(any, any, any))) is det.
+
+any_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).
+
+%------------------------------------------------------------------------------%
+
+% any_tree234__insert is implemented using the simple top-down
+% approach described ia eg Sedgwick which splits 4 nodes into
+% two 2 nodes on the downward traversal of the tree as we
+% search for the right place to insert the new key-value pair.
+% We know we have the right place if the subtrees of the node
+% are empty (ia which case we expand the node - which will always
+% work because we already split 4 nodes into 2 nodes), or if the
+% tree itself is empty.
+% This algorithm is O(lgN).
+
+any_tree234__insert(Tin, K, V, Tout) :-
+ (
+ Tin = empty,
+ Tout = two(K, V, empty, empty)
+ ;
+ Tin = two(_, _, _, _),
+ any_tree234__insert2(Tin, K, V, Tout)
+ ;
+ Tin = three(_, _, _, _, _, _, _),
+ any_tree234__insert3(Tin, K, V, Tout)
+ ;
+ Tin = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(Tin, MidK, MidV, Sub0, Sub1),
+ unsafe_cast_to_ground(MidK),
+ compare(Result1, K, MidK),
+ (
+ Result1 = (<),
+ any_tree234__insert2(Sub0, K, V, NewSub0),
+ Tout = two(MidK, MidV, NewSub0, Sub1)
+ ;
+ Result1 = (=),
+ fail
+ ;
+ Result1 = (>),
+ any_tree234__insert2(Sub1, K, V, NewSub1),
+ Tout = two(MidK, MidV, Sub0, NewSub1)
+ )
+ ).
+
+:- pred any_tree234__insert2(any_tree234(K, V)::ia, K::in, V::ia,
+ any_tree234(K, V)::oa) is semidet.
+
+any_tree234__insert2(two(K0, V0, T0, T1), K, V, Tout) :-
+ (
+ T0 = empty
+ % T1 = empty implied by T0 = empty
+ ->
+ unsafe_cast_to_ground(K0),
+ 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)
+ )
+ ;
+ unsafe_cast_to_ground(K0),
+ compare(Result, K, K0),
+ (
+ Result = (<),
+ (
+ T0 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T0, MT0K, MT0V, T00, T01),
+ unsafe_cast_to_ground(MT0K),
+ compare(Result1, K, MT0K),
+ (
+ Result1 = (<),
+ any_tree234__insert2(T00, K, V, NewT00),
+ Tout = three(MT0K, MT0V, K0, V0,
+ NewT00, T01, T1)
+ ;
+ Result1 = (=),
+ fail
+ ;
+ Result1 = (>),
+ any_tree234__insert2(T01, K, V, NewT01),
+ Tout = three(MT0K, MT0V, K0, V0,
+ T00, NewT01, T1)
+ )
+ ;
+ T0 = three(_, _, _, _, _, _, _),
+ any_tree234__insert3(T0, K, V, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
+ ;
+ T0 = two(_, _, _, _),
+ any_tree234__insert2(T0, K, V, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
+ ;
+ T0 = empty,
+ NewT0 = two(K, V, empty, empty),
+ Tout = two(K0, V0, NewT0, T1)
+ )
+ ;
+ Result = (=),
+ fail
+ ;
+ Result = (>),
+ (
+ T1 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T1, MT1K, MT1V, T10, T11),
+ unsafe_cast_to_ground(MT1K),
+ compare(Result1, K, MT1K),
+ (
+ Result1 = (<),
+ any_tree234__insert2(T10, K, V, NewT10),
+ Tout = three(K0, V0, MT1K, MT1V,
+ T0, NewT10, T11)
+ ;
+ Result1 = (=),
+ fail
+ ;
+ Result1 = (>),
+ any_tree234__insert2(T11, K, V, NewT11),
+ Tout = three(K0, V0, MT1K, MT1V,
+ T0, T10, NewT11)
+ )
+ ;
+ T1 = three(_, _, _, _, _, _, _),
+ any_tree234__insert3(T1, K, V, NewT1),
+ Tout = two(K0, V0, T0, NewT1)
+ ;
+ T1 = two(_, _, _, _),
+ any_tree234__insert2(T1, K, V, NewT1),
+ Tout = two(K0, V0, T0, NewT1)
+ ;
+ T1 = empty,
+ NewT1 = two(K, V, empty, empty),
+ Tout = two(K0, V0, T0, NewT1)
+ )
+ )
+ ).
+
+:- pred any_tree234__insert3(any_tree234(K, V)::ia, K::in, V::ia,
+ any_tree234(K, V)::oa) is semidet.
+
+any_tree234__insert3(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
+ ->
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ Tout = four(K, V, K0, V0, K1, V1,
+ empty, empty, empty, empty)
+ ;
+ Result0 = (=),
+ fail
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ Tout = four(K0, V0, K, V, K1, V1,
+ empty, empty, empty, empty)
+ ;
+ Result1 = (=),
+ fail
+ ;
+ Result1 = (>),
+ Tout = four(K0, V0, K1, V1, K, V,
+ empty, empty, empty, empty)
+ )
+ )
+ ;
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ (
+ T0 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T0, MT0K, MT0V, T00, T01),
+ unsafe_cast_to_ground(MT0K),
+ compare(ResultM, K, MT0K),
+ (
+ ResultM = (<),
+ any_tree234__insert2(T00, K, V, NewT00),
+ Tout = four(MT0K, MT0V, K0, V0, K1, V1,
+ NewT00, T01, T1, T2)
+ ;
+ ResultM = (=),
+ fail
+ ;
+ ResultM = (>),
+ any_tree234__insert2(T01, K, V, NewT01),
+ Tout = four(MT0K, MT0V, K0, V0, K1, V1,
+ T00, NewT01, T1, T2)
+ )
+ ;
+ T0 = three(_, _, _, _, _, _, _),
+ any_tree234__insert3(T0, K, V, NewT0),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
+ ;
+ T0 = two(_, _, _, _),
+ any_tree234__insert2(T0, K, V, NewT0),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
+ ;
+ T0 = empty,
+ NewT0 = two(K, V, empty, empty),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
+ )
+ ;
+ Result0 = (=),
+ fail
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ (
+ T1 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T1, MT1K, MT1V,
+ T10, T11),
+ unsafe_cast_to_ground(MT1K),
+ compare(ResultM, K, MT1K),
+ (
+ ResultM = (<),
+ any_tree234__insert2(T10, K, V,
+ NewT10),
+ Tout = four(K0, V0, MT1K, MT1V,
+ K1, V1,
+ T0, NewT10, T11, T2)
+ ;
+ ResultM = (=),
+ fail
+ ;
+ ResultM = (>),
+ any_tree234__insert2(T11, K, V,
+ NewT11),
+ Tout = four(K0, V0, MT1K, MT1V,
+ K1, V1,
+ T0, T10, NewT11, T2)
+ )
+ ;
+ T1 = three(_, _, _, _, _, _, _),
+ any_tree234__insert3(T1, K, V, NewT1),
+ Tout = three(K0, V0, K1, V1,
+ T0, NewT1, T2)
+ ;
+ T1 = two(_, _, _, _),
+ any_tree234__insert2(T1, K, V, NewT1),
+ Tout = three(K0, V0, K1, V1,
+ T0, NewT1, T2)
+ ;
+ T1 = empty,
+ NewT1 = two(K, V, empty, empty),
+ Tout = three(K0, V0, K1, V1,
+ T0, NewT1, T2)
+ )
+ ;
+ Result1 = (=),
+ fail
+ ;
+ Result1 = (>),
+ (
+ T2 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T2, MT2K, MT2V,
+ T20, T21),
+ unsafe_cast_to_ground(MT2K),
+ compare(ResultM, K, MT2K),
+ (
+ ResultM = (<),
+ any_tree234__insert2(T20, K, V,
+ NewT20),
+ Tout = four(K0, V0, K1, V1,
+ MT2K, MT2V,
+ T0, T1, NewT20, T21)
+ ;
+ ResultM = (=),
+ fail
+ ;
+ ResultM = (>),
+ any_tree234__insert2(T21, K, V,
+ NewT21),
+ Tout = four(K0, V0, K1, V1,
+ MT2K, MT2V,
+ T0, T1, T20, NewT21)
+ )
+ ;
+ T2 = three(_, _, _, _, _, _, _),
+ any_tree234__insert3(T2, K, V, NewT2),
+ Tout = three(K0, V0, K1, V1,
+ T0, T1, NewT2)
+ ;
+ T2 = two(_, _, _, _),
+ any_tree234__insert2(T2, K, V, NewT2),
+ Tout = three(K0, V0, K1, V1,
+ T0, T1, NewT2)
+ ;
+ T2 = empty,
+ NewT2 = two(K, V, empty, empty),
+ Tout = three(K0, V0, K1, V1,
+ T0, T1, NewT2)
+ )
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+
+% any_tree234__set uses the same algorithm as used for any_tree234__insert,
+% except that instead of failing for equal keys, we replace the value.
+
+any_tree234__set(Tin, K, V, Tout) :-
+ (
+ Tin = empty,
+ Tout = two(K, V, empty, empty)
+ ;
+ Tin = two(_, _, _, _),
+ any_tree234__set2(Tin, K, V, Tout)
+ ;
+ Tin = three(_, _, _, _, _, _, _),
+ any_tree234__set3(Tin, K, V, Tout)
+ ;
+ Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ Sub0 = two(K0, V0, T0, T1),
+ Sub1 = two(K2, V2, T2, T3),
+ any_tree234__set2(Sub0, K, V, NewSub0),
+ Tout = two(K1, V1, NewSub0, Sub1)
+ ;
+ Result1 = (=),
+ Tout = four(K0, V0, K1, V, K2, V2, T0, T1, T2, T3)
+ ;
+ Result1 = (>),
+ Sub0 = two(K0, V0, T0, T1),
+ Sub1 = two(K2, V2, T2, T3),
+ any_tree234__set2(Sub1, K, V, NewSub1),
+ Tout = two(K1, V1, Sub0, NewSub1)
+ )
+ ).
+
+:- pred any_tree234__set2(any_tree234(K, V)::in(two(any, any, any)),
+ K::in, V::ia, any_tree234(K, V)::oa) is det.
+
+any_tree234__set2(two(K0, V0, T0, T1), K, V, Tout) :-
+ (
+ T0 = empty
+ % T1 = empty implied by T0 = empty
+ ->
+ unsafe_cast_to_ground(K0),
+ compare(Result, K, K0),
+ (
+ Result = (<),
+ Tout = three(K, V, K0, V0, empty, empty, empty)
+ ;
+ Result = (=),
+ Tout = two(K, V, T0, T1)
+ ;
+ Result = (>),
+ Tout = three(K0, V0, K, V, empty, empty, empty)
+ )
+ ;
+ unsafe_cast_to_ground(K0),
+ compare(Result, K, K0),
+ (
+ Result = (<),
+ (
+ T0 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T0, MT0K, MT0V, T00, T01),
+ unsafe_cast_to_ground(MT0K),
+ compare(Result1, K, MT0K),
+ (
+ Result1 = (<),
+ any_tree234__set2(T00, K, V, NewT00),
+ Tout = three(MT0K, MT0V, K0, V0,
+ NewT00, T01, T1)
+ ;
+ Result1 = (=),
+ Tout = three(MT0K, V, K0, V0,
+ T00, T01, T1)
+ ;
+ Result1 = (>),
+ any_tree234__set2(T01, K, V, NewT01),
+ Tout = three(MT0K, MT0V, K0, V0,
+ T00, NewT01, T1)
+ )
+ ;
+ T0 = three(_, _, _, _, _, _, _),
+ any_tree234__set3(T0, K, V, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
+ ;
+ T0 = two(_, _, _, _),
+ any_tree234__set2(T0, K, V, NewT0),
+ Tout = two(K0, V0, NewT0, T1)
+ ;
+ T0 = empty,
+ NewT0 = two(K, V, empty, empty),
+ Tout = two(K0, V0, NewT0, T1)
+ )
+ ;
+ Result = (=),
+ Tout = two(K, V, T0, T1)
+ ;
+ Result = (>),
+ (
+ T1 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T1, MT1K, MT1V, T10, T11),
+ unsafe_cast_to_ground(MT1K),
+ compare(Result1, K, MT1K),
+ (
+ Result1 = (<),
+ any_tree234__set2(T10, K, V, NewT10),
+ Tout = three(K0, V0, MT1K, MT1V,
+ T0, NewT10, T11)
+ ;
+ Result1 = (=),
+ Tout = three(K0, V0, MT1K, V,
+ T0, T10, T11)
+ ;
+ Result1 = (>),
+ any_tree234__set2(T11, K, V, NewT11),
+ Tout = three(K0, V0, MT1K, MT1V,
+ T0, T10, NewT11)
+ )
+ ;
+ T1 = three(_, _, _, _, _, _, _),
+ any_tree234__set3(T1, K, V, NewT1),
+ Tout = two(K0, V0, T0, NewT1)
+ ;
+ T1 = two(_, _, _, _),
+ any_tree234__set2(T1, K, V, NewT1),
+ Tout = two(K0, V0, T0, NewT1)
+ ;
+ T1 = empty,
+ NewT1 = two(K, V, empty, empty),
+ Tout = two(K0, V0, T0, NewT1)
+ )
+ )
+ ).
+
+:- pred any_tree234__set3(any_tree234(K, V)::in(three(any, any, any)),
+ K::in, V::ia, any_tree234(K, V)::oa) is det.
+
+any_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
+ ->
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ Tout = four(K, V, K0, V0, K1, V1,
+ empty, empty, empty, empty)
+ ;
+ Result0 = (=),
+ Tout = three(K0, V, K1, V1,
+ empty, empty, empty)
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ 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)
+ )
+ )
+ ;
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ (
+ T0 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T0, MT0K, MT0V, T00, T01),
+ unsafe_cast_to_ground(MT0K),
+ compare(ResultM, K, MT0K),
+ (
+ ResultM = (<),
+ any_tree234__set2(T00, K, V, NewT00),
+ Tout = four(MT0K, MT0V, K0, V0, K1, V1,
+ NewT00, T01, T1, T2)
+ ;
+ ResultM = (=),
+ Tout = four(MT0K, V, K0, V0, K1, V1,
+ T00, T01, T1, T2)
+ ;
+ ResultM = (>),
+ any_tree234__set2(T01, K, V, NewT01),
+ Tout = four(MT0K, MT0V, K0, V0, K1, V1,
+ T00, NewT01, T1, T2)
+ )
+ ;
+ T0 = three(_, _, _, _, _, _, _),
+ any_tree234__set3(T0, K, V, NewT0),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
+ ;
+ T0 = two(_, _, _, _),
+ any_tree234__set2(T0, K, V, NewT0),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
+ ;
+ T0 = empty,
+ NewT0 = two(K, V, empty, empty),
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2)
+ )
+ ;
+ Result0 = (=),
+ Tout = three(K0, V, K1, V1, T0, T1, T2)
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ (
+ T1 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T1, MT1K, MT1V,
+ T10, T11),
+ unsafe_cast_to_ground(MT1K),
+ compare(ResultM, K, MT1K),
+ (
+ ResultM = (<),
+ any_tree234__set2(T10, K, V,
+ NewT10),
+ Tout = four(K0, V0, MT1K, MT1V,
+ K1, V1,
+ T0, NewT10, T11, T2)
+ ;
+ ResultM = (=),
+ Tout = four(K0, V0, MT1K, V,
+ K1, V1,
+ T0, T10, T11, T2)
+ ;
+ ResultM = (>),
+ any_tree234__set2(T11, K, V,
+ NewT11),
+ Tout = four(K0, V0, MT1K, MT1V,
+ K1, V1,
+ T0, T10, NewT11, T2)
+ )
+ ;
+ T1 = three(_, _, _, _, _, _, _),
+ any_tree234__set3(T1, K, V, NewT1),
+ Tout = three(K0, V0, K1, V1,
+ T0, NewT1, T2)
+ ;
+ T1 = two(_, _, _, _),
+ any_tree234__set2(T1, K, V, NewT1),
+ Tout = three(K0, V0, K1, V1,
+ T0, NewT1, T2)
+ ;
+ T1 = empty,
+ NewT1 = two(K, V, empty, empty),
+ Tout = three(K0, V0, K1, V1,
+ T0, NewT1, T2)
+ )
+ ;
+ Result1 = (=),
+ Tout = three(K0, V0, K, V, T0, T1, T2)
+ ;
+ Result1 = (>),
+ (
+ T2 = four(_, _, _, _, _, _, _, _, _, _),
+ any_tree234__split_four(T2, MT2K, MT2V,
+ T20, T21),
+ unsafe_cast_to_ground(MT2K),
+ compare(ResultM, K, MT2K),
+ (
+ ResultM = (<),
+ any_tree234__set2(T20, K, V,
+ NewT20),
+ Tout = four(K0, V0, K1, V1,
+ MT2K, MT2V,
+ T0, T1, NewT20, T21)
+ ;
+ ResultM = (=),
+ Tout = four(K0, V0, K1, V1,
+ MT2K, V,
+ T0, T1, T20, T21)
+ ;
+ ResultM = (>),
+ any_tree234__set2(T21, K, V,
+ NewT21),
+ Tout = four(K0, V0, K1, V1,
+ MT2K, MT2V,
+ T0, T1, T20, NewT21)
+ )
+ ;
+ T2 = three(_, _, _, _, _, _, _),
+ any_tree234__set3(T2, K, V, NewT2),
+ Tout = three(K0, V0, K1, V1,
+ T0, T1, NewT2)
+ ;
+ T2 = two(_, _, _, _),
+ any_tree234__set2(T2, K, V, NewT2),
+ Tout = three(K0, V0, K1, V1,
+ T0, T1, NewT2)
+ ;
+ T2 = empty,
+ NewT2 = two(K, V, empty, empty),
+ Tout = three(K0, V0, K1, V1,
+ T0, T1, NewT2)
+ )
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+any_tree234__delete(Tin, K, Tout) :-
+ any_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 any_tree234__delete_2(any_tree234(K, V)::ia, K::in,
+ any_tree234(K, V)::oa, bool::out) is det.
+
+any_tree234__delete_2(Tin, K, Tout, RH) :-
+ (
+ Tin = empty,
+ Tout = empty,
+ RH = no
+ ;
+ Tin = two(K0, V0, T0, T1),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__delete_2(T0, K, NewT0, RHT0),
+ ( RHT0 = yes ->
+ fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
+ ;
+ Tout = two(K0, V0, NewT0, T1),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ (
+ any_tree234__remove_smallest_2(T1, ST1K, ST1V,
+ NewT1, RHT1)
+ ->
+ ( RHT1 = yes ->
+ fix_2node_t1(ST1K, ST1V, T0, NewT1,
+ Tout, RH)
+ ;
+ Tout = two(ST1K, ST1V, T0, NewT1),
+ RH = no
+ )
+ ;
+ % T1 must be empty
+ Tout = T0,
+ RH = yes
+ )
+ ;
+ Result0 = (>),
+ any_tree234__delete_2(T1, K, NewT1, RHT1),
+ ( RHT1 = yes ->
+ fix_2node_t1(K0, V0, T0, NewT1, Tout, RH)
+ ;
+ Tout = two(K0, V0, T0, NewT1),
+ RH = no
+ )
+ )
+ ;
+ Tin = three(K0, V0, K1, V1, T0, T1, T2),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__delete_2(T0, K, NewT0, RHT0),
+ ( RHT0 = yes ->
+ fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2,
+ Tout, RH)
+ ;
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ (
+ any_tree234__remove_smallest_2(T1, ST1K, ST1V,
+ NewT1, RHT1)
+ ->
+ ( RHT1 = yes ->
+ fix_3node_t1(ST1K, ST1V, K1, V1,
+ T0, NewT1, T2, Tout, RH)
+ ;
+ Tout = three(ST1K, ST1V, K1, V1,
+ T0, NewT1, T2),
+ RH = no
+ )
+ ;
+ % T1 must be empty
+ Tout = two(K1, V1, T0, T2),
+ RH = no
+ )
+ ;
+ Result0 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ any_tree234__delete_2(T1, K, NewT1, RHT1),
+ ( RHT1 = yes ->
+ fix_3node_t1(K0, V0, K1, V1,
+ T0, NewT1, T2, Tout, RH)
+ ;
+ Tout = three(K0, V0, K1, V1,
+ T0, NewT1, T2),
+ RH = no
+ )
+ ;
+ Result1 = (=),
+ (
+ any_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, ST2K, ST2V,
+ T0, T1, NewT2),
+ RH = no
+ )
+ ;
+ % T2 must be empty
+ Tout = two(K0, V0, T0, T1),
+ RH = no
+ )
+ ;
+ Result1 = (>),
+ any_tree234__delete_2(T2, K, NewT2, RHT2),
+ ( RHT2 = yes ->
+ fix_3node_t2(K0, V0, K1, V1,
+ T0, T1, NewT2, Tout, RH)
+ ;
+ Tout = three(K0, V0, K1, V1,
+ T0, T1, NewT2),
+ RH = no
+ )
+ )
+ )
+ ;
+ Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__delete_2(T0, K, NewT0, RHT0),
+ ( RHT0 = yes ->
+ fix_4node_t0(K0, V0, K1, V1, K2, V2,
+ NewT0, T1, T2, T3, Tout, RH)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ NewT0, T1, T2, T3),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ (
+ any_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)
+ ;
+ 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
+ )
+ ;
+ Result0 = (>),
+ any_tree234__delete_2(T1, K, NewT1, RHT1),
+ ( RHT1 = yes ->
+ fix_4node_t1(K0, V0, K1, V1, K2, V2,
+ T0, NewT1, T2, T3, Tout, RH)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ T0, NewT1, T2, T3),
+ RH = no
+ )
+ )
+ ;
+ Result1 = (=),
+ (
+ any_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)
+ ;
+ 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
+ )
+ ;
+ Result1 = (>),
+ unsafe_cast_to_ground(K2),
+ compare(Result2, K, K2),
+ (
+ Result2 = (<),
+ any_tree234__delete_2(T2, K, NewT2, RHT2),
+ ( RHT2 = yes ->
+ fix_4node_t2(K0, V0, K1, V1, K2, V2,
+ T0, T1, NewT2, T3, Tout, RH)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ T0, T1, NewT2, T3),
+ RH = no
+ )
+ ;
+ Result2 = (=),
+ (
+ any_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)
+ ;
+ 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
+ )
+ ;
+ Result2 = (>),
+ any_tree234__delete_2(T3, K, NewT3, RHT3),
+ ( RHT3 = yes ->
+ fix_4node_t3(K0, V0, K1, V1, K2, V2,
+ T0, T1, T2, NewT3, Tout, RH)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ T0, T1, T2, NewT3),
+ RH = no
+ )
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+
+ % We use the same algorithm as any_tree234__delete.
+
+any_tree234__remove(Tin, K, V, Tout) :-
+ any_tree234__remove_2(Tin, K, V, Tout, _).
+
+:- pred any_tree234__remove_2(any_tree234(K, V)::ia, K::in, V::oa,
+ any_tree234(K, V)::oa, bool::out) is semidet.
+
+any_tree234__remove_2(Tin, K, V, Tout, RH) :-
+ (
+ Tin = empty,
+ fail
+ ;
+ Tin = two(K0, V0, T0, T1),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__remove_2(T0, K, V, NewT0, RHT0),
+ ( RHT0 = yes ->
+ fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
+ ;
+ Tout = two(K0, V0, NewT0, T1),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ (
+ any_tree234__remove_smallest_2(T1, ST1K, ST1V,
+ NewT1, RHT1)
+ ->
+ ( RHT1 = yes ->
+ fix_2node_t1(ST1K, ST1V, T0, NewT1,
+ Tout, RH)
+ ;
+ Tout = two(ST1K, ST1V, T0, NewT1),
+ RH = no
+ )
+ ;
+ % T1 must be empty
+ Tout = T0,
+ RH = yes
+ ),
+ V = V0
+ ;
+ Result0 = (>),
+ any_tree234__remove_2(T1, K, V, NewT1, RHT1),
+ ( RHT1 = yes ->
+ fix_2node_t1(K0, V0, T0, NewT1, Tout, RH)
+ ;
+ Tout = two(K0, V0, T0, NewT1),
+ RH = no
+ )
+ )
+ ;
+ Tin = three(K0, V0, K1, V1, T0, T1, T2),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_tree234__remove_2(T0, K, V, NewT0, RHT0),
+ ( RHT0 = yes ->
+ fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2,
+ Tout, RH)
+ ;
+ Tout = three(K0, V0, K1, V1, NewT0, T1, T2),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ (
+ any_tree234__remove_smallest_2(T1, ST1K, ST1V,
+ NewT1, RHT1)
+ ->
+ ( RHT1 = yes ->
+ fix_3node_t1(ST1K, ST1V, K1, V1,
+ T0, NewT1, T2, Tout, RH)
+ ;
+ 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 = (>),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ any_tree234__remove_2(T1, K, V, NewT1, RHT1),
+ ( RHT1 = yes ->
+ fix_3node_t1(K0, V0, K1, V1,
+ T0, NewT1, T2, Tout, RH)
+ ;
+ Tout = three(K0, V0, K1, V1,
+ T0, NewT1, T2),
+ RH = no
+ )
+ ;
+ Result1 = (=),
+ (
+ any_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, ST2K, ST2V,
+ T0, T1, NewT2),
+ RH = no
+ )
+ ;
+ % T2 must be empty
+ Tout = two(K0, V0, T0, T1),
+ RH = no
+ ),
+ V = V1
+ ;
+ Result1 = (>),
+ any_tree234__remove_2(T2, K, V, NewT2, RHT2),
+ ( RHT2 = yes ->
+ fix_3node_t2(K0, V0, K1, V1,
+ T0, T1, NewT2, Tout, RH)
+ ;
+ Tout = three(K0, V0, K1, V1,
+ T0, T1, NewT2),
+ RH = no
+ )
+ )
+ )
+ ;
+ Tin = four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ unsafe_cast_to_ground(K1),
+ compare(Result1, K, K1),
+ (
+ Result1 = (<),
+ unsafe_cast_to_ground(K0),
+ compare(Result0, K, K0),
+ (
+ Result0 = (<),
+ any_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)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ NewT0, T1, T2, T3),
+ RH = no
+ )
+ ;
+ Result0 = (=),
+ (
+ any_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)
+ ;
+ 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 = (>),
+ any_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)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ T0, NewT1, T2, T3),
+ RH = no
+ )
+ )
+ ;
+ Result1 = (=),
+ (
+ any_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)
+ ;
+ 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 = (>),
+ unsafe_cast_to_ground(K2),
+ compare(Result2, K, K2),
+ (
+ Result2 = (<),
+ any_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)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ T0, T1, NewT2, T3),
+ RH = no
+ )
+ ;
+ Result2 = (=),
+ (
+ any_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)
+ ;
+ 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 = (>),
+ any_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)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ T0, T1, T2, NewT3),
+ RH = no
+ )
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+
+ % The algorithm we use similar to any_tree234__delete, except that we
+ % always go down the left subtree.
+
+any_tree234__remove_smallest(Tin, K, V, Tout) :-
+ any_tree234__remove_smallest_2(Tin, K, V, Tout, _),
+ unsafe_cast_to_ground(K).
+
+:- pred any_tree234__remove_smallest_2(any_tree234(K, V)::ia, K::oa, V::oa,
+ any_tree234(K, V)::oa, bool::out) is semidet.
+
+any_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
+ ;
+ any_tree234__remove_smallest_2(T0, K, V, NewT0, RHT0),
+ ( RHT0 = yes ->
+ fix_2node_t0(K0, V0, NewT0, T1, Tout, RH)
+ ;
+ 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
+ ;
+ any_tree234__remove_smallest_2(T0, K, V, NewT0, RHT0),
+ ( RHT0 = yes ->
+ fix_3node_t0(K0, V0, K1, V1, NewT0, T1, T2,
+ Tout, RH)
+ ;
+ 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
+ ;
+ any_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)
+ ;
+ Tout = four(K0, V0, K1, V1, K2, V2,
+ NewT0, T1, T2, T3),
+ RH = no
+ )
+ )
+ ).
+
+%------------------------------------------------------------------------------%
+
+ % The input to the following group of predicates are the components
+ % of a two-, three- or four-node ia which the height of the indicated
+ % subtree is one less that 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::ia, V::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::oa, bool::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,
+ error("unbalanced 234 tree")
+ % Tout = two(K0, V0, T0, T1),
+ % RH = yes
+ ).
+
+:- pred fix_2node_t1(K::ia, V::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::oa, bool::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,
+ error("unbalanced 234 tree")
+ % Tout = two(K0, V0, T0, T1),
+ % RH = yes
+ ).
+
+:- pred fix_3node_t0(K::ia, V::ia, K::ia, V::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia, any_tree234(K, V)::oa,
+ bool::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,
+ 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::ia, V::ia, K::ia, V::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia, any_tree234(K, V)::oa,
+ bool::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,
+ 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::ia, V::ia, K::ia, V::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia, any_tree234(K, V)::oa,
+ bool::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,
+ 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::ia, V::ia, K::ia, V::ia, K::ia, V::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::oa, bool::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,
+ 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::ia, V::ia, K::ia, V::ia, K::ia, V::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::oa, bool::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,
+ 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::ia, V::ia, K::ia, V::ia, K::ia, V::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::oa, bool::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,
+ 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::ia, V::ia, K::ia, V::ia, K::ia, V::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::ia,
+ any_tree234(K, V)::oa, bool::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,
+ 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
+ ).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__keys(Tree, Keys) :-
+ any_tree234__keys_2(Tree, [], Keys),
+ unsafe_cast_to_ground(Keys).
+
+:- pred any_tree234__keys_2(any_tree234(K, V)::ia, list(K)::ia,
+ list(K)::oa) is det.
+
+any_tree234__keys_2(empty, List, List).
+any_tree234__keys_2(two(K0, _V0, T0, T1), L0, L) :-
+ any_tree234__keys_2(T1, L0, L1),
+ any_tree234__keys_2(T0, [K0 | L1], L).
+any_tree234__keys_2(three(K0, _V0, K1, _V1, T0, T1, T2), L0, L) :-
+ any_tree234__keys_2(T2, L0, L1),
+ any_tree234__keys_2(T1, [K1 | L1], L2),
+ any_tree234__keys_2(T0, [K0 | L2], L).
+any_tree234__keys_2(four(K0, _V0, K1, _V1, K2, _V2, T0, T1, T2, T3), L0, L) :-
+ any_tree234__keys_2(T3, L0, L1),
+ any_tree234__keys_2(T2, [K2 | L1], L2),
+ any_tree234__keys_2(T1, [K1 | L2], L3),
+ any_tree234__keys_2(T0, [K0 | L3], L).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__values(Tree, Values) :-
+ any_tree234__values_2(Tree, [], Values).
+
+:- pred any_tree234__values_2(any_tree234(K, V)::ia, any_list(V)::ia,
+ any_list(V)::oa) is det.
+
+any_tree234__values_2(empty, List, List).
+any_tree234__values_2(two(_K0, V0, T0, T1), L0, L) :-
+ any_tree234__values_2(T1, L0, L1),
+ any_tree234__values_2(T0, [V0 | L1], L).
+any_tree234__values_2(three(_K0, V0, _K1, V1, T0, T1, T2), L0, L) :-
+ any_tree234__values_2(T2, L0, L1),
+ any_tree234__values_2(T1, [V1 | L1], L2),
+ any_tree234__values_2(T0, [V0 | L2], L).
+any_tree234__values_2(four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3), L0, L) :-
+ any_tree234__values_2(T3, L0, L1),
+ any_tree234__values_2(T2, [V2 | L1], L2),
+ any_tree234__values_2(T1, [V1 | L2], L3),
+ any_tree234__values_2(T0, [V0 | L3], L).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__any_assoc_list_to_any_tree234(AssocList, Tree) :-
+ any_tree234__any_assoc_list_to_any_tree234_2(AssocList, empty, Tree).
+
+:- pred any_tree234__any_assoc_list_to_any_tree234_2(any_assoc_list(K, V)::ia,
+ any_tree234(K, V)::ia, any_tree234(K, V)::oa) is det.
+
+any_tree234__any_assoc_list_to_any_tree234_2([], Tree, Tree).
+any_tree234__any_assoc_list_to_any_tree234_2([K - V | Rest], Tree0, Tree) :-
+ unsafe_cast_to_ground(K),
+ any_tree234__set(Tree0, K, V, Tree1),
+ any_tree234__any_assoc_list_to_any_tree234_2(Rest, Tree1, Tree).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__any_tree234_to_any_assoc_list(Tree, AssocList) :-
+ any_tree234__any_tree234_to_any_assoc_list_2(Tree, [], AssocList).
+
+:- pred any_tree234__any_tree234_to_any_assoc_list_2(any_tree234(K, V)::ia,
+ any_assoc_list(K, V)::ia, any_assoc_list(K, V)::oa) is det.
+
+any_tree234__any_tree234_to_any_assoc_list_2(empty, List, List).
+any_tree234__any_tree234_to_any_assoc_list_2(two(K0, V0, T0, T1), L0, L) :-
+ any_tree234__any_tree234_to_any_assoc_list_2(T1, L0, L1),
+ any_tree234__any_tree234_to_any_assoc_list_2(T0, [K0 - V0 | L1], L).
+any_tree234__any_tree234_to_any_assoc_list_2(three(K0, V0, K1, V1, T0, T1, T2),
+ L0, L) :-
+ any_tree234__any_tree234_to_any_assoc_list_2(T2, L0, L1),
+ any_tree234__any_tree234_to_any_assoc_list_2(T1, [K1 - V1 | L1], L2),
+ any_tree234__any_tree234_to_any_assoc_list_2(T0, [K0 - V0 | L2], L).
+any_tree234__any_tree234_to_any_assoc_list_2(four(K0, V0, K1, V1, K2, V2,
+ T0, T1, T2, T3), L0, L) :-
+ any_tree234__any_tree234_to_any_assoc_list_2(T3, L0, L1),
+ any_tree234__any_tree234_to_any_assoc_list_2(T2, [K2 - V2 | L1], L2),
+ any_tree234__any_tree234_to_any_assoc_list_2(T1, [K1 - V1 | L2], L3),
+ any_tree234__any_tree234_to_any_assoc_list_2(T0, [K0 - V0 | L3], L).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__foldl(_Pred, empty, !A).
+any_tree234__foldl(Pred, two(K, V, T0, T1), !A) :-
+ unsafe_cast_to_ground(K),
+ any_tree234__foldl(Pred, T0, !A),
+ call(Pred, K, V, !A),
+ any_tree234__foldl(Pred, T1, !A).
+any_tree234__foldl(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A) :-
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ any_tree234__foldl(Pred, T0, !A),
+ call(Pred, K0, V0, !A),
+ any_tree234__foldl(Pred, T1, !A),
+ call(Pred, K1, V1, !A),
+ any_tree234__foldl(Pred, T2, !A).
+any_tree234__foldl(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3), !A) :-
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ unsafe_cast_to_ground(K2),
+ any_tree234__foldl(Pred, T0, !A),
+ call(Pred, K0, V0, !A),
+ any_tree234__foldl(Pred, T1, !A),
+ call(Pred, K1, V1, !A),
+ any_tree234__foldl(Pred, T2, !A),
+ call(Pred, K2, V2, !A),
+ any_tree234__foldl(Pred, T3, !A).
+
+any_tree234__foldl2(_Pred, empty, !A, !B).
+any_tree234__foldl2(Pred, two(K, V, T0, T1), !A, !B) :-
+ unsafe_cast_to_ground(K),
+ any_tree234__foldl2(Pred, T0, !A, !B),
+ call(Pred, K, V, !A, !B),
+ any_tree234__foldl2(Pred, T1, !A, !B).
+any_tree234__foldl2(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B) :-
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ any_tree234__foldl2(Pred, T0, !A, !B),
+ call(Pred, K0, V0, !A, !B),
+ any_tree234__foldl2(Pred, T1, !A, !B),
+ call(Pred, K1, V1, !A, !B),
+ any_tree234__foldl2(Pred, T2, !A, !B).
+any_tree234__foldl2(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ !A, !B) :-
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ unsafe_cast_to_ground(K2),
+ any_tree234__foldl2(Pred, T0, !A, !B),
+ call(Pred, K0, V0, !A, !B),
+ any_tree234__foldl2(Pred, T1, !A, !B),
+ call(Pred, K1, V1, !A, !B),
+ any_tree234__foldl2(Pred, T2, !A, !B),
+ call(Pred, K2, V2, !A, !B),
+ any_tree234__foldl2(Pred, T3, !A, !B).
+
+any_tree234__foldl3(_Pred, empty, !A, !B, !C).
+any_tree234__foldl3(Pred, two(K, V, T0, T1), !A, !B, !C) :-
+ unsafe_cast_to_ground(K),
+ any_tree234__foldl3(Pred, T0, !A, !B, !C),
+ call(Pred, K, V, !A, !B, !C),
+ any_tree234__foldl3(Pred, T1, !A, !B, !C).
+any_tree234__foldl3(Pred, three(K0, V0, K1, V1, T0, T1, T2), !A, !B, !C) :-
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ any_tree234__foldl3(Pred, T0, !A, !B, !C),
+ call(Pred, K0, V0, !A, !B, !C),
+ any_tree234__foldl3(Pred, T1, !A, !B, !C),
+ call(Pred, K1, V1, !A, !B, !C),
+ any_tree234__foldl3(Pred, T2, !A, !B, !C).
+any_tree234__foldl3(Pred, four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
+ !A, !B, !C) :-
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ unsafe_cast_to_ground(K2),
+ any_tree234__foldl3(Pred, T0, !A, !B, !C),
+ call(Pred, K0, V0, !A, !B, !C),
+ any_tree234__foldl3(Pred, T1, !A, !B, !C),
+ call(Pred, K1, V1, !A, !B, !C),
+ any_tree234__foldl3(Pred, T2, !A, !B, !C),
+ call(Pred, K2, V2, !A, !B, !C),
+ any_tree234__foldl3(Pred, T3, !A, !B, !C).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__map_values(_Pred, empty, empty).
+any_tree234__map_values(Pred, Tree0, Tree) :-
+ Tree0 = two(K0, V0, Left0, Right0),
+ unsafe_cast_to_ground(K0),
+ call(Pred, K0, V0, W0),
+ any_tree234__map_values(Pred, Left0, Left),
+ any_tree234__map_values(Pred, Right0, Right),
+ Tree = two(K0, W0, Left, Right).
+any_tree234__map_values(Pred, Tree0, Tree) :-
+ Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ call(Pred, K0, V0, W0),
+ call(Pred, K1, V1, W1),
+ any_tree234__map_values(Pred, Left0, Left),
+ any_tree234__map_values(Pred, Middle0, Middle),
+ any_tree234__map_values(Pred, Right0, Right),
+ Tree = three(K0, W0, K1, W1, Left, Middle, Right).
+any_tree234__map_values(Pred, Tree0, Tree) :-
+ Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ unsafe_cast_to_ground(K2),
+ call(Pred, K0, V0, W0),
+ call(Pred, K1, V1, W1),
+ call(Pred, K2, V2, W2),
+ any_tree234__map_values(Pred, Left0, Left),
+ any_tree234__map_values(Pred, LMid0, LMid),
+ any_tree234__map_values(Pred, RMid0, RMid),
+ any_tree234__map_values(Pred, Right0, Right),
+ Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right).
+
+%------------------------------------------------------------------------------%
+
+any_tree234__map_foldl(_Pred, empty, empty, !A).
+any_tree234__map_foldl(Pred, Tree0, Tree, !A) :-
+ Tree0 = two(K0, V0, Left0, Right0),
+ Tree = two(K0, W0, Left, Right),
+ unsafe_cast_to_ground(K0),
+ any_tree234__map_foldl(Pred, Left0, Left, !A),
+ call(Pred, K0, V0, W0, !A),
+ any_tree234__map_foldl(Pred, Right0, Right, !A).
+any_tree234__map_foldl(Pred, Tree0, Tree, !A) :-
+ Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
+ Tree = three(K0, W0, K1, W1, Left, Middle, Right),
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ any_tree234__map_foldl(Pred, Left0, Left, !A),
+ call(Pred, K0, V0, W0, !A),
+ any_tree234__map_foldl(Pred, Middle0, Middle, !A),
+ call(Pred, K1, V1, W1, !A),
+ any_tree234__map_foldl(Pred, Right0, Right, !A).
+any_tree234__map_foldl(Pred, Tree0, Tree, !A) :-
+ Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
+ Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right),
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ unsafe_cast_to_ground(K2),
+ any_tree234__map_foldl(Pred, Left0, Left, !A),
+ call(Pred, K0, V0, W0, !A),
+ any_tree234__map_foldl(Pred, LMid0, LMid, !A),
+ call(Pred, K1, V1, W1, !A),
+ any_tree234__map_foldl(Pred, RMid0, RMid, !A),
+ call(Pred, K2, V2, W2, !A),
+ any_tree234__map_foldl(Pred, Right0, Right, !A).
+
+any_tree234__map_foldl2(_Pred, empty, empty, !A, !B).
+any_tree234__map_foldl2(Pred, Tree0, Tree, !A, !B) :-
+ Tree0 = two(K0, V0, Left0, Right0),
+ Tree = two(K0, W0, Left, Right),
+ unsafe_cast_to_ground(K0),
+ any_tree234__map_foldl2(Pred, Left0, Left, !A, !B),
+ call(Pred, K0, V0, W0, !A, !B),
+ any_tree234__map_foldl2(Pred, Right0, Right, !A, !B).
+any_tree234__map_foldl2(Pred, Tree0, Tree, !A, !B) :-
+ Tree0 = three(K0, V0, K1, V1, Left0, Middle0, Right0),
+ Tree = three(K0, W0, K1, W1, Left, Middle, Right),
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ any_tree234__map_foldl2(Pred, Left0, Left, !A, !B),
+ call(Pred, K0, V0, W0, !A, !B),
+ any_tree234__map_foldl2(Pred, Middle0, Middle, !A, !B),
+ call(Pred, K1, V1, W1, !A, !B),
+ any_tree234__map_foldl2(Pred, Right0, Right, !A, !B).
+any_tree234__map_foldl2(Pred, Tree0, Tree, !A, !B) :-
+ Tree0 = four(K0, V0, K1, V1, K2, V2, Left0, LMid0, RMid0, Right0),
+ Tree = four(K0, W0, K1, W1, K2, W2, Left, LMid, RMid, Right),
+ unsafe_cast_to_ground(K0),
+ unsafe_cast_to_ground(K1),
+ unsafe_cast_to_ground(K2),
+ any_tree234__map_foldl2(Pred, Left0, Left, !A, !B),
+ call(Pred, K0, V0, W0, !A, !B),
+ any_tree234__map_foldl2(Pred, LMid0, LMid, !A, !B),
+ call(Pred, K1, V1, W1, !A, !B),
+ any_tree234__map_foldl2(Pred, RMid0, RMid, !A, !B),
+ call(Pred, K2, V2, W2, !A, !B),
+ any_tree234__map_foldl2(Pred, Right0, Right, !A, !B).
+
+%------------------------------------------------------------------------------%
+
+ % count the number of elements ia a tree
+any_tree234__count(empty, 0).
+any_tree234__count(two(_, _, T0, T1), N) :-
+ any_tree234__count(T0, N0),
+ any_tree234__count(T1, N1),
+ N = 1 + N0 + N1.
+any_tree234__count(three(_, _, _, _, T0, T1, T2), N) :-
+ any_tree234__count(T0, N0),
+ any_tree234__count(T1, N1),
+ any_tree234__count(T2, N2),
+ N = 2 + N0 + N1 + N2.
+any_tree234__count(four(_, _, _, _, _, _, T0, T1, T2, T3), N) :-
+ any_tree234__count(T0, N0),
+ any_tree234__count(T1, N1),
+ any_tree234__count(T2, N2),
+ any_tree234__count(T3, N3),
+ N = 3 + N0 + N1 + N2 + N3.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+% Ralph Becket <rwab1 at cl.cam.ac.uk> 30/04/99
+% Function forms added.
+
+any_tree234__init = T :-
+ any_tree234__init(T).
+
+any_tree234__lookup(T, K) = V :-
+ any_tree234__lookup(T, K, V).
+
+any_tree234__set(T1, K, V) = T2 :-
+ any_tree234__set(T1, K, V, T2).
+
+any_tree234__delete(T1, K) = T2 :-
+ any_tree234__delete(T1, K, T2).
+
+any_tree234__keys(T) = Ks :-
+ any_tree234__keys(T, Ks).
+
+any_tree234__values(T) = Vs :-
+ any_tree234__values(T, Vs).
+
+any_tree234__count(T) = N :-
+ any_tree234__count(T, N).
+
+any_tree234__any_assoc_list_to_any_tree234(AL) = T :-
+ any_tree234__any_assoc_list_to_any_tree234(AL, T).
+
+any_tree234__any_tree234_to_any_assoc_list(T) = AL :-
+ any_tree234__any_tree234_to_any_assoc_list(T, AL).
+
+:- pragma promise_pure(any_tree234__foldl/3).
+
+any_tree234__foldl(F::in(func(in, ia, in) = out is det), M::ia, A::in) =
+ (B::out) :-
+ P = ( pred(W::in, X::ia, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
+ any_tree234__foldl(P, M, A, B).
+
+any_tree234__foldl(F::in(func(in, ia, ia) = oa is det), M::ia, A::ia) =
+ (B::oa) :-
+ P = ( pred(W::in, X::ia, Y::ia, Z::oa) is det :- Z = F(W, X, Y) ),
+ any_tree234__foldl(P, M, A, B).
+
+any_tree234__map_values(F, T1) = T2 :-
+ P = ( pred(X::in, Y::ia, Z::oa) is det :- Z = F(X, Y) ),
+ any_tree234__map_values(P, T1, T2).
Index: extras/solver_types/library/any_util.m
===================================================================
RCS file: extras/solver_types/library/any_util.m
diff -N extras/solver_types/library/any_util.m
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ extras/solver_types/library/any_util.m 9 Sep 2005 05:55:53 -0000
@@ -0,0 +1,39 @@
+%-----------------------------------------------------------------------------%
+% any_util.m
+% Ralph Becket <rafe at cs.mu.OZ.AU>
+% Wed Sep 7 14:54:39 EST 2005
+% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
+%
+% Utility predicates for use with inst any values.
+%
+%-----------------------------------------------------------------------------%
+
+:- module any_util.
+
+:- interface.
+
+
+
+ % This predicate is useful for converting polymorphic non-solver type
+ % values with inst any to inst ground (the compiler recognises that inst
+ % any is equivalent to ground for non-polymorphic non-solver types).
+ %
+ % DON'T call this on solver type values unless you're absolutely sure they
+ % are semantically ground.
+ %
+:- pred unsafe_cast_to_ground(T::(any >> ground)) is det.
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
+
+:- implementation.
+
+%-----------------------------------------------------------------------------%
+
+:- pragma foreign_proc("C",
+ unsafe_cast_to_ground(_X::(any >> ground)),
+ [promise_pure, will_not_call_mercury, thread_safe],
+"").
+
+%-----------------------------------------------------------------------------%
+%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post: mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the reviews
mailing list