mercury/library/ranges.m

%---------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%---------------------------------------------------------------------------%
% Copyright (C) 2006-2009 The University of Melbourne.
% Copyright (C) 2013-2016 Opturion Pty Ltd.
% Copyright (C) 2017-2019, 2022-2026 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%---------------------------------------------------------------------------%
%
% File: ranges.m.
% Authors: Mark Brown.
% Stability: medium.
%
% This module provides sets of integers represented using a range list.
% Each contiguous block of integers in a set is stored as a range that
% specifies the bounds of the block, and these ranges are kept in a list-like
% structure. Elements of these sets must be in (min_int + 1) .. max_int
% (both inclusive). The value min_int cannot be included in any set.
% Predicates and functions in this module that attempt to construct sets
% containing min_int will throw an exception.
%
% This module provides predicates and functions that operate on either the
% individual elements in a set, or on the pairs of integers that define the
% bounds of the blocks used in the representation. Predicates and functions
% that do the latter have names containing "range" (e.g. range_foldr,
% nondet_range_member).
%
%---------------------------------------------------------------------------%

:- module ranges.
:- interface.

:- import_module list.
:- import_module set.

%---------------------------------------------------------------------------%

:- type ranges.

%---------------------------------------------------------------------------%
%
% Initial creation of sets.
%

    % empty returns the empty set.
    %
:- func empty = ranges.

    % universe returns the largest set that can be handled by this module.
    % This is the set of integers (min_int + 1) .. max_int (inclusive).
    %
:- func universe = ranges.

    % range(Lo, Hi) is the set of all integers from Lo to Hi both inclusive.
    %
:- func range(int, int) = ranges.

    % make_singleton_set(Elem) returns the set containing just the single
    % element Elem.
    %
:- func make_singleton_set(int) = ranges.

%---------------------------------------------------------------------------%
%
% Emptiness and other tests.
%

    % is_empty(Set) is true if-and-only-if Set is the empty set.
    %
:- pred is_empty(ranges::in) is semidet.

    % is_non_empty(Set) is true if-and-only-if Set is not the empty set.
    %
:- pred is_non_empty(ranges::in) is semidet.

    % is_contiguous(Set, Lo, Hi) is true if-and-only-if Set
    % is the set of all integers from Lo to Hi, both inclusive.
    %
:- pred is_contiguous(ranges::in, int::out, int::out) is semidet.

    % is_singleton(Set, Elem) is true if-and-only-if Set contains
    % the single element Elem.
    %
:- pred is_singleton(ranges::in, int::out) is semidet.

%---------------------------------------------------------------------------%
%
% Membership tests.
%

    % member(X, Set) is true if-and-only-if X is a member of Set.
    %
:- pred member(int::in, ranges::in) is semidet.

    % contains(Set, X) is true if-and-only-if X is a member of Set.
    %
:- pred contains(ranges::in, int::in) is semidet.

    % nondet_member(Set, X):
    %
    % Nondeterministically produce each element in Set.
    % Each time this call succeeds, X will be bound to an element in Set.
    %
:- pred nondet_member(ranges::in, int::out) is nondet.

    % nondet_range_member(Set, Lo, Hi):
    %
    % Nondeterministically produce each range in Set.
    % Each time this call succeeds, Lo and Hi will be bound to
    % the smallest and largest integers respectively in a range in Set.
    %
:- pred nondet_range_member(ranges::in, int::out, int::out) is nondet.

    % Obsolete synonym for nondet_range_member/3.
    %
:- pred range_member(int::out, int::out, ranges::in) is nondet.
:- pragma obsolete(pred(range_member/3), [nondet_range_member/3]).

%---------------------------------------------------------------------------%
%
% Insertions and deletions.
%

    % insert(X, Set0, Set) is true if-and-only-if Set is the union of Set0 and
    % the set containing only X.
    % Throws an exception if X = min_int.
    %
:- func insert(int, ranges) = ranges.
:- pred insert(int::in, ranges::in, ranges::out) is det.

    % insert_list(Xs, Set0, Set) is true if-and-only-if Set is
    % the union of Set0 and the set containing only the members of Xs.
    %
:- func insert_list(list(int), ranges) = ranges.
:- pred insert_list(list(int)::in, ranges::in, ranges::out) is det.

    % delete(X, Set0, Set) is true if-and-only-if Set is
    % the relative complement of Set0 and the set containing only X,
    % i.e. if Set is the set which contains all the elements of Set0 except X.
    % Throws an exception if X = min_int.
    %
:- func delete(int, ranges) = ranges.
:- pred delete(int::in, ranges::in, ranges::out) is det.
% NOTE_TO_IMPLEMENTORS XXX add semidet remove predicate,
% NOTE_TO_IMPLEMENTORS which fails if the item to delete is not in the set

    % delete_list(Xs, Set0, Set) is true if-and-only-if Set is
    % the relative complement of Set0 and the set containing
    % only the members of Xs.
    %
:- func delete_list(list(int), ranges) = ranges.
:- pred delete_list(list(int)::in, ranges::in, ranges::out) is det.

%---------------------------------------------------------------------------%
%
% Comparisons between sets.
%

    % subset(SetA, SetB) is true if-and-only-if every value in SetA is in SetB.
    %
:- pred subset(ranges::in, ranges::in) is semidet.

    % disjoint(SetA, SetB) is true if-and-only-if SetA and SetB
    % have no values in common.
    %
:- pred disjoint(ranges::in, ranges::in) is semidet.

    % Compare the sets of integers given by the two ranges using lexicographic
    % ordering on the sorted set form.
    %
:- pred compare_lex(comparison_result::uo, ranges::in, ranges::in) is det.

%---------------------------------------------------------------------------%
%
% Operations on two or more sets.
%

    % union(SetA, SetB): return the set that contains all the integers in SetA
    % and SetB.
    %
:- func union(ranges, ranges) = ranges.
:- pred union(ranges::in, ranges::in, ranges::out) is det.

    % intersect(SetA, SetB): return the set that contains all the integers
    % in both SetA and SetB.
    %
:- func intersect(ranges, ranges) = ranges.
:- pred intersect(ranges::in, ranges::in, ranges::out) is det.

    % An obsolete synonym for intersect/2.
    %
:- func intersection(ranges, ranges) = ranges.
:- pragma obsolete(func(intersection/2), [intersect/2]).

    % difference(SetA, SetB): return the set that contains all of the integers
    % that are in SetA but not in SetB.
    %
:- func difference(ranges, ranges) = ranges.
:- pred difference(ranges::in, ranges::in, ranges::out) is det.

%---------------------------------------------------------------------------%
%
% Operations that divide a set into two parts.
%

    % split(Set, Lo, Hi, Rest) is true if-and-only-if Lo..Hi is the first range
    % (i.e. the range containing the smallest integers) in Set, and
    % Rest is the set Set with this range removed.
    %
    % Fails if Set is empty.
    %
:- pred split(ranges::in, int::out, int::out, ranges::out) is semidet.

    % prune_to_next_non_member(Set0, Set, X0, X):
    %
    % Bind X to the smallest integer greater than or equal to X0
    % that is *not* in Set0, and bind Set to the set of integers in Set0
    % that are greater than X.
    % NOTE_TO_IMPLEMENTORS XXX This seems a strange predicate and name.
    %
:- pred prune_to_next_non_member(ranges::in, ranges::out,
    int::in, int::out) is det.

    % prune_to_prev_non_member(Set0, Set, X0, X):
    %
    % Bind X to the largest integer less than or equal to X0
    % that is *not* in Set0, and bind Set to the set of integers in Set0
    % that are less than X.
    % NOTE_TO_IMPLEMENTORS XXX This seems a strange predicate and name.
    %
:- pred prune_to_prev_non_member(ranges::in, ranges::out,
    int::in, int::out) is det.

%---------------------------------------------------------------------------%
%
% Converting lists and sets to ranges.
%

    % Convert from a list of integers.
    % NOTE_TO_IMPLEMENTORS XXX Should have sorted_list_to_ranges version.
    %
:- func list_to_ranges(list(int)) = ranges.
:- pred list_to_ranges(list(int)::in, ranges::out) is det.

    % Synonym for list_to_ranges/1.
    %
:- func from_list(list(int)) = ranges.

    % Convert from a set of integers.
    %
:- func set_to_ranges(set(int)) = ranges.
:- pred set_to_ranges(set(int)::in, ranges::out) is det.

    % Synonym for set_to_ranges/1.
    %
:- func from_set(set(int)) = ranges.

%---------------------------------------------------------------------------%
%
% Converting sets to lists.
%

    % Convert to a sorted list of integers.
    %
:- func to_sorted_list(ranges) = list(int).

%---------------------------------------------------------------------------%
%
% Counting.
%

    % Return the number of distinct integers that are in the set
    % (as opposed to the number of ranges).
    %
:- func count(ranges) = int.
:- func ucount(ranges) = uint.

    % A synonym for count/1.
    % NOTE_TO_IMPLEMENTORS XXX mark this obsolete and eventually remove it.
    %
:- func size(ranges) = int.

%---------------------------------------------------------------------------%
%
% Selecting individual elements from a set.
%

    % Returns the median value of the set. In the case of a tie,
    % returns the smaller of the two integers in the middle of the set.
    % Throws an exception if the set is empty.
    %
:- func median(ranges) = int.

    % least(Set, X) is true if-and-only-if X is the smallest element of Set.
    % Fails if the set is empty.
    %
:- pred least(ranges::in, int::out) is semidet.

    % greatest(Set, X) is true if-and-only-if X is the greatest element of Set.
    % Fails if the set is empty.
    %
:- pred greatest(ranges::in, int::out) is semidet.

    % next(Set, X0, X) is true if-and-only-if X is the least element of Set
    % greater than X0.
    %
:- pred next(ranges::in, int::in, int::out) is semidet.

    % search_range(X, Set, Lo, Hi):
    %
    % If X is in Set, then succeed, setting Lo and Hi to the endpoints
    % of the range in which it is contained. If X is not in Set, fail.
    %
:- pred search_range(int::in, ranges::in, int::out, int::out) is semidet.

%---------------------------------------------------------------------------%
%
% Filtering elements in a set.
%

    % restrict_min(Min, Set): return the set that contains
    % all the integers in Set that are greater than or equal to Min.
    %
:- func restrict_min(int, ranges) = ranges.
:- pred restrict_min(int::in, ranges::in, ranges::out) is det.

    % restrict_max(Max, Set): return the set that contains
    % all the integers in Set that are less than or equal to Max.
    %
:- func restrict_max(int, ranges) = ranges.
:- pred restrict_max(int::in, ranges::in, ranges::out) is det.

    % restrict_range(Min, Max, Set): return the set that contains
    % all the integers X in Set that satisfy Min =< X =< Max.
    %
:- func restrict_range(int, int, ranges) = ranges.
:- pred restrict_range(int::in, int::in, ranges::in, ranges::out) is det.

%---------------------------------------------------------------------------%
%
% Transformations of a set.
% NOTE_TO_IMPLEMENTORS These names are uninformative
%

    % Negate all numbers: X in Set <=> -X in negate(Set)
    %
:- func negate(ranges) = ranges.

    % The sum of two ranges.
    %
:- func plus(ranges, ranges) = ranges.

    % Shift a range by a constant C.
    %
:- func shift(ranges, int) = ranges.

    % Dilate a range by a constant C.
    %
:- func dilation(ranges, int) = ranges.

    % Contract a range by a constant C.
    %
:- func contraction(ranges, int) = ranges.

%---------------------------------------------------------------------------%
%
% Standard higher-order functions on elements in a set.
%

:- pred foldl(pred(int, A, A), ranges, A, A).
:- mode foldl(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldl(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldl(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldl(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldl(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldl(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.

:- pred foldl2(pred(int, A, A, B, B), ranges, A, A, B, B).
:- mode foldl2(in(pred(in, in, out, in, out) is det), in, in, out,
    in, out) is det.
:- mode foldl2(in(pred(in, in, out, mdi, muo) is det), in, in, out,
    mdi, muo) is det.
:- mode foldl2(in(pred(in, in, out, di, uo) is det), in, in, out,
    di, uo) is det.
:- mode foldl2(in(pred(in, in, out, in, out) is semidet), in, in, out,
    in, out) is semidet.
:- mode foldl2(in(pred(in, in, out, mdi, muo) is semidet), in, in, out,
    mdi, muo) is semidet.
:- mode foldl2(in(pred(in, in, out, di, uo) is semidet), in, in, out,
    di, uo) is semidet.

:- pred foldl3(pred(int, A, A, B, B, C, C), ranges, A, A, B, B, C, C).
:- mode foldl3(in(pred(in, in, out, in, out, in, out) is det), in,
    in, out, in, out, in, out) is det.
:- mode foldl3(in(pred(in, in, out, in, out, mdi, muo) is det), in,
    in, out, in, out, mdi, muo) is det.
:- mode foldl3(in(pred(in, in, out, in, out, di, uo) is det), in,
    in, out, in, out, di, uo) is det.
:- mode foldl3(in(pred(in, in, out, in, out, di, uo) is semidet), in,
    in, out, in, out, di, uo) is semidet.

:- pred foldr(pred(int, A, A), ranges, A, A).
:- mode foldr(in(pred(in, in, out) is det), in, in, out) is det.
:- mode foldr(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
:- mode foldr(in(pred(in, di, uo) is det), in, di, uo) is det.
:- mode foldr(in(pred(in, in, out) is semidet), in, in, out) is semidet.
:- mode foldr(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
:- mode foldr(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.

%---------------------------------------------------------------------------%
%
% Standard higher-order functions on range endpoint pairs in set.
%

    % For each range, call the predicate, passing it the lower and
    % upper bound and threading through an accumulator.
    %
:- pred range_foldl(pred(int, int, A, A), ranges, A, A).
:- mode range_foldl(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode range_foldl(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode range_foldl(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode range_foldl(in(pred(in, in, in, out) is semidet), in, in, out)
    is semidet.
:- mode range_foldl(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo)
    is semidet.
:- mode range_foldl(in(pred(in, in, di, uo) is semidet), in, di, uo)
    is semidet.

    % As above, but with two accumulators.
    %
:- pred range_foldl2(pred(int, int, A, A, B, B), ranges, A, A, B, B).
:- mode range_foldl2(in(pred(in, in, in, out, in, out) is det),
    in, in, out, in, out) is det.
:- mode range_foldl2(in(pred(in, in, in, out, mdi, muo) is det),
    in, in, out, mdi, muo) is det.
:- mode range_foldl2(in(pred(in, in, in, out, di, uo) is det),
    in, in, out, di, uo) is det.
:- mode range_foldl2(in(pred(in, in, in, out, in, out) is semidet),
    in, in, out, in, out) is semidet.
:- mode range_foldl2(in(pred(in, in, in, out, mdi, muo) is semidet),
    in, in, out, mdi, muo) is semidet.
:- mode range_foldl2(in(pred(in, in, in, out, di, uo) is semidet),
    in, in, out, di, uo) is semidet.

:- pred range_foldr(pred(int, int, A, A), ranges, A, A).
:- mode range_foldr(in(pred(in, in, in, out) is det), in, in, out) is det.
:- mode range_foldr(in(pred(in, in, mdi, muo) is det), in, mdi, muo) is det.
:- mode range_foldr(in(pred(in, in, di, uo) is det), in, di, uo) is det.
:- mode range_foldr(in(pred(in, in, in, out) is semidet), in, in, out)
    is semidet.
:- mode range_foldr(in(pred(in, in, mdi, muo) is semidet), in, mdi, muo)
    is semidet.
:- mode range_foldr(in(pred(in, in, di, uo) is semidet), in, di, uo)
    is semidet.

%---------------------------------------------------------------------------%
%
% C interface to ranges.
%
% This section describes the C interface to the ranges/0 type
% that is exported by this module.
%
% In C the ranges/0 type is represented by the ML_Ranges type.
% The following operations are exported and may be called from C or C++ code.
%
% ML_Ranges ML_ranges_empty(void)
%   Return the empty set.
%
% ML_Ranges ML_ranges_universe(void)
%   Return the set of integers from (min_int+1)..max_int.
%
% ML_Ranges ML_ranges_range(MR_Integer l, MR_Integer h)
%   Return the set of integers from `l' to `h' inclusive.
%
% int ML_ranges_is_empty(ML_Ranges r)
%   Return true if-and-only-if `r` is the empty set.
%
% MR_Integer ML_ranges_count(ML_Ranges r)
%  Return the number of distinct integers in `r`.
%
% MR_Integer ML_ranges_size(ML_Ranges r)
%   Return the number of distinct integers in `r'.
%   (Synonym for ML_ranges_count).
%
% int ML_ranges_split(ML_Ranges d, MR_Integer *l, MR_Integer *h,
%       ML_Ranges *rest)
%   Return true if `d' is not the empty set, setting `l' and `h' to the
%   lower and upper bound of the first range in `d', and setting `rest'
%   to `d' with the first range removed.
%   Return false if `d' is the empty set.
%
% ML_Ranges ML_ranges_insert(MR_Integer i, ML_ranges r)
%   Return the ranges value that is the result of inserting
%   the integer `i' into the ranges value `r'.
%
%---------------------------------------------------------------------------%
%
% Java interface to ranges.
%
% This section describes the Java interface to the ranges/0 type that is
% exported by this module.
%
% In Java the ranges/0 type is represented by the ranges.Ranges_0 class.
% The following operations are exported as public static methods of the ranges
% module and may be called from Java code.
%
% ranges.Ranges_0 empty()
%   Return the empty set.
%
% ranges.Ranges_0 universe()
%   Return the set of integers from (min_int+1)..max_int.
%
% ranges.Ranges_0 range(int l, int h)
%   Return the set of integers from `l' to `h' inclusive.
%
% boolean is_empty(ranges.Ranges_0 r)
%   Return true if-and-only-if `r' is the empty set.
%
% int count(ranges.Ranges_0 r)
%   Return the number of distinct integers in `r'.
%
% int size(ranges.Ranges_0 r)
%   Return the number of distinct integers in `r'.
%   (Synonym for count).
%
% boolean split(ranges.Ranges_0 d,
%     jmercury.runtime.Ref<Integer> l,
%     jmercury.runtime.Ref<Integer> h,
%     jmercury.runtime.Ref<ranges.Ranges_0> rest)
%   Return true if `d' is not the empty set, setting `l' and `h' to the
%   lower and upper bound of the first range in `d', and setting `rest'
%   to `d' with the first range removed.
%   Return false if `d' is the empty set.
%
% ranges.Ranges_0 insert(int i, ranges.Ranges_0 r)
%   Return the ranges value that is the result of inserting the integer
%   `i' into the ranges value `r'.
%
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%

:- implementation.

:- import_module int.
:- import_module require.
:- import_module uint.

%---------------------------------------------------------------------------%

    % Values of this type represent finite sets of integers.
    % They are interpreted in the following way.
    %
    %     S[[ nil ]]                 = {}
    %     S[[ range(Lo, Hi, Rest) ]] = {N | Lo < N =< Hi} \/ S[[ Rest ]]
    %
    % For example, `range(1, 4, nil)' represents the set {2, 3, 4}.
    %
    % The invariants on this type are:
    %
    %   1) Each range must be non-empty, i.e. Lo must be strictly less than Hi.
    %   2) The ranges must not overlap or abut.
    %   3) The ranges must be in sorted order.
    %
    % The second and third invariants together require that for any value
    % `range(_, Hi1, range(Lo2, _, _)', we must have Hi1 < Lo2.
    %
    % These invariants ensure that the representation is canonical.
    %
    % Note that it is not possible to represent a set containing min_int.
    % Attempting to create such a set will result in an exception being thrown.
    %
:- type ranges
    --->    nil
    ;       range(int, int, ranges).

:- pragma foreign_decl("C",
"
typedef MR_Word ML_Ranges;
").

%---------------------------------------------------------------------------%

:- pragma foreign_export("C",    ranges.empty = out, "ML_ranges_empty").
:- pragma foreign_export("Java", ranges.empty = out, "empty").

empty = nil.

:- pragma foreign_export("C",    ranges.universe = out, "ML_ranges_universe").
:- pragma foreign_export("Java", ranges.universe = out, "universe").

universe = range(min_int, max_int, nil).

:- pragma foreign_export("C",
    ranges.range(in, in) = out, "ML_ranges_range").
:- pragma foreign_export("Java",
    ranges.range(in, in) = out, "range").

range(Lo, Hi) = Ranges :-
    ( if Lo = min_int then
        error($pred, "cannot represent min_int")
    else if Lo > Hi then
        Ranges = nil
    else
        Ranges = range(Lo - 1, Hi, nil)
    ).

make_singleton_set(Elem) = Ranges :-
    ( if Elem = min_int then
        error($pred, "cannot represent min_int")
    else
        Ranges = range(Elem - 1, Elem, nil)
    ).

%---------------------------------------------------------------------------%

:- pragma foreign_export("C",    ranges.is_empty(in), "ML_ranges_is_empty").
:- pragma foreign_export("Java", ranges.is_empty(in), "is_empty").

is_empty(nil).

is_non_empty(range(_, _, _)).

is_contiguous(Range, Lo + 1, Hi) :-
    Range = range(Lo, Hi, nil).

is_singleton(range(N - 1, N, nil), N).

%---------------------------------------------------------------------------%

member(N, range(Lo, Hi, Rest)) :-
    (
        N > Lo,
        N =< Hi
    ;
        ranges.member(N, Rest)
    ).

contains(Set, E) :-
    member(E, Set).

nondet_member(Set, N) :-
    nondet_range_member(Set, Lo, Hi),
    int.nondet_int_in_range(Lo, Hi, N).

nondet_range_member(range(Lo0, Hi0, Rest), Lo, Hi) :-
    (
        Lo = Lo0 + 1,
        Hi = Hi0
    ;
        nondet_range_member(Rest, Lo, Hi)
    ).

range_member(Lo, Hi, Ranges) :-
    nondet_range_member(Ranges, Lo, Hi).

%---------------------------------------------------------------------------%

:- pragma foreign_export("C",
    ranges.insert(in, in) = out, "ML_ranges_insert").
:- pragma foreign_export("Java",
    ranges.insert(in, in) = out, "insert").

insert(E, Set0) = Set :-
    insert(E, Set0, Set).

insert(E, Set0, Set) :-
    union(Set0, make_singleton_set(E), Set).

insert_list(Es, Set0) = Set :-
    insert_list(Es, Set0, Set).

insert_list([], !Set).
insert_list([E | Es], !Set) :-
    insert(E, !Set),
    insert_list(Es, !Set).

%---------------------%

delete(E, Set0) = Set :-
    delete(E, Set0, Set).

delete(E, Set0, Set) :-
    difference(Set0, make_singleton_set(E), Set).

delete_list(Es, Set0) = Set:-
    delete_list(Es, Set0, Set).

delete_list([], !Set).
delete_list([E | Es], !Set) :-
    delete(E, !Set),
    delete_list(Es, !Set).

%---------------------------------------------------------------------------%

subset(SetA, SetB) :-
    % XXX Should implement this more efficiently.
    ranges.difference(SetA, SetB) = nil.

disjoint(SetA, SetB) :-
    % XXX Should implement this more efficiently.
    ranges.intersect(SetA, SetB) = nil.

%---------------------------------------------------------------------------%

compare_lex(Result, A, B) :-
    (
        A = nil,
        B = nil,
        Result = (=)
    ;
        A = nil,
        B = range(_, _, _),
        Result = (<)
    ;
        A = range(_, _, _),
        B = nil,
        Result = (>)
    ;
        A = range(LBA, UBA, APrime),
        B = range(LBB, UBB, BPrime),
        % NOTE: when we unpack a range/3 constructor we must add one
        % to the first argument since that is the lowest value in that
        % subset.
        % XXX Why? Given that compare_lex is a symmetrical operation,
        % and the result of comparing X and Y is guaranteed to be the same
        % as comparing X+1 and Y+1, why bother?
        compare_lex_2(Result, LBA + 1, UBA, LBB + 1, UBB, APrime, BPrime)
    ).

:- pred compare_lex_2(comparison_result::uo, int::in, int::in,
    int::in, int::in, ranges::in, ranges::in) is det.

compare_lex_2(Result, !.LBA, !.UBA, !.LBB, !.UBB, !.NextA, !.NextB) :-
    compare(LBResult, !.LBA, !.LBB),
    (
        ( LBResult = (<)
        ; LBResult = (>)
        ),
        Result = LBResult
    ;
        LBResult = (=),
        compare(UBResult, !.UBA, !.UBB),
        (
            UBResult = (=),
            compare_lex(Result, !.NextA, !.NextB)
        ;
            ( UBResult = (<)
            ; UBResult = (>)
            ),
            ( if
                !.LBA = !.UBA,
                !.LBB = !.UBB
            then
                compare_lex(Result, !.NextA, !.NextB)
            else if
                !.LBA < !.UBA,
                !.LBB = !.UBB
            then
                !:LBA = !.LBA + 1,
                (
                    !.NextB = nil,
                    Result = (>)
                ;
                    !.NextB = range(!:LBB, !:UBB, !:NextB),
                    compare_lex_2(Result, !.LBA, !.UBA, !.LBB + 1, !.UBB,
                        !.NextA, !.NextB)
                )
            else if
                !.LBA = !.UBA,
                !.LBB < !.UBB
            then
                !:LBB = !.LBB + 1,
                (
                    !.NextA = nil,
                    Result = (<)
                ;
                    !.NextA = range(!:LBA, !:UBA, !:NextA),
                    compare_lex_2(Result, !.LBA + 1, !.UBA, !.LBB, !.UBB,
                        !.NextA, !.NextB)
                )
            else
                !:LBA = !.LBA + 1,
                !:LBB = !.LBB + 1,
                disable_warning [suspicious_recursion] (
                    compare_lex_2(Result, !.LBA, !.UBA, !.LBB, !.UBB,
                        !.NextA, !.NextB)
                )
            )
        )
    ).

%---------------------------------------------------------------------------%

    % union(A, B) = A \/ B
    %
union(nil, Bs) = Bs.
union(As @ range(_, _, _), nil) = As.
union(As @ range(LA, UA, As0), Bs @ range(LB, UB, Bs0)) = Result :-
    compare(R, LA, LB),
    (
        R = (<),
        Result = n_diff_na_b(LA, UA, As0, Bs)
    ;
        R = (=),
        Result = n_int_na_nb(LA, UA, As0, UB, Bs0)
    ;
        R = (>),
        Result = n_diff_na_b(LB, UB, Bs0, As)
    ).

union(Xs, Ys, Union) :-
    Union = union(Xs, Ys).

    % n_union_a_nb(L, A, U, B) =
    %   {X | X > L} \ (A \/ ({Y | Y > U} \ B))
    %
    % assuming L < min(A), L < U and U < min(B).
    %
:- func n_union_a_nb(int, ranges, int, ranges) = ranges.

n_union_a_nb(L, nil, U, Bs) = range(L, U, Bs).
n_union_a_nb(L, As @ range(LA, UA, As0), UB, Bs0) = Result :-
    compare(R, LA, UB),
    (
        R = (<),
        Result = range(L, LA, diff_na_nb(UA, As0, UB, Bs0))
    ;
        R = (=),
        Result = range(L, LA, int_na_b(UA, As0, Bs0))
    ;
        R = (>),
        Result = range(L, UB, ranges.difference(Bs0, As))
    ).

    % n_union_na_b(L, U, A, B) =
    %   {X | X > L} \ (({Y | Y > U} \ A) \/ B)
    %
    % assuming L < U, U < min(A) and L < min(B).
    %
:- func n_union_na_b(int, int, ranges, ranges) = ranges.

n_union_na_b(L, U, As, nil) = range(L, U, As).
n_union_na_b(L, UA, As0, Bs @ range(LB, UB, Bs0)) = Result :-
    compare(R, UA, LB),
    (
        R = (<),
        Result = range(L, UA, ranges.difference(As0, Bs))
    ;
        R = (=),
        Result = range(L, UA, int_a_nb(As0, UB, Bs0))
    ;
        R = (>),
        Result = range(L, LB, diff_na_nb(UB, Bs0, UA, As0))
    ).

    % n_union_na_nb(L, UA, A, UB, B) =
    %   {X | X > L} \ (({Y | Y > UA} \ A) \/ ({Z | Z > UB} \ B))
    %
    % assuming L < UA, UA < min(A), L < UB and UB < min(B).
    %
:- func n_union_na_nb(int, int, ranges, int, ranges) = ranges.

n_union_na_nb(L, UA, As0, UB, Bs0) = Result :-
    compare(R, UA, UB),
    (
        R = (<),
        Result = range(L, UA, diff_a_nb(As0, UB, Bs0))
    ;
        R = (=),
        Result = range(L, UA, ranges.intersect(As0, Bs0))
    ;
        R = (>),
        Result = range(L, UB, diff_a_nb(Bs0, UA, As0))
    ).

%---------------------------------------------------------------------------%

    % intersect(A, B) = A /\ B
    %
intersect(nil, _) = nil.
intersect(range(_, _, _), nil) = nil.
intersect(As @ range(LA, UA, As0), Bs @ range(LB, UB, Bs0)) = Result :-
    compare(R, LA, LB),
    (
        R = (<),
        Result = diff_a_nb(Bs, UA, As0)
    ;
        R = (=),
        Result = n_union_na_nb(LA, UA, As0, UB, Bs0)
    ;
        R = (>),
        Result = diff_a_nb(As, UB, Bs0)
    ).

intersect(Xs, Ys, Intersection) :-
    Intersection = intersect(Xs, Ys).

intersection(Xs, Ys) =
    intersect(Xs, Ys).

    % int_na_b(U, A, B) = ({X | X > U} \ A) /\ B
    %
    % assuming U < min(A).
    %
:- func int_na_b(int, ranges, ranges) = ranges.

int_na_b(_, _, nil) = nil.
int_na_b(UA, As0, Bs @ range(LB, UB, Bs0)) = Result :-
    compare(R, UA, LB),
    (
        R = (<),
        Result = ranges.difference(Bs, As0)
    ;
        R = (=),
        Result = n_union_a_nb(UA, As0, UB, Bs0)
    ;
        R = (>),
        Result = diff_na_nb(UA, As0, UB, Bs0)
    ).

    % n_int_na_nb(L, UA, A, UB, B) =
    %   {X | X > L} (({Y | Y > UA} \ A) /\ ({Z | Z > UB} \ B))
    %
    % assuming L < UA, UA < min(A), L < UB and UB < min(B).
    %
:- func n_int_na_nb(int, int, ranges, int, ranges) = ranges.

n_int_na_nb(L, UA, As0, UB, Bs0) = Result :-
    compare(R, UA, UB),
    (
        R = (<),
        Result = n_diff_na_b(L, UB, Bs0, As0)
    ;
        R = (=),
        Result = range(L, UA, ranges.union(As0, Bs0))
    ;
        R = (>),
        Result = n_diff_na_b(L, UA, As0, Bs0)
    ).

    % int_a_nb(A, U, B) = A /\ ({X | X > U} \ B)
    %
    % assuming U < min(B).
    %
:- func int_a_nb(ranges, int, ranges) = ranges.

int_a_nb(nil, _, _) = nil.
int_a_nb(As @ range(LA, UA, As0), UB, Bs0) = Result :-
    compare(R, LA, UB),
    (
        R = (<),
        Result = diff_na_nb(UB, Bs0, UA, As0)
    ;
        R = (=),
        Result = n_union_na_b(LA, UA, As0, Bs0)
    ;
        R = (>),
        Result = ranges.difference(As, Bs0)
    ).

%---------------------------------------------------------------------------%

    % difference(A, B) = A \ B
    %
difference(nil, _) = nil.
difference(As @ range(_, _, _), nil) = As.
difference(As @ range(LA, UA, As0), Bs @ range(LB, UB, Bs0)) = Result :-
    compare(R, LA, LB),
    (
        R = (<),
        Result = n_union_na_b(LA, UA, As0, Bs)
    ;
        R = (=),
        Result = diff_na_nb(UB, Bs0, UA, As0)
    ;
        R = (>),
        Result = int_a_nb(As, UB, Bs0)
    ).

difference(Xs, Ys, Difference) :-
    Difference = difference(Xs, Ys).

    % n_diff_na_b(L, U, A, B) = {X | X > L} \ (({Y | Y > U} \ A) \ B)
    %
    % assuming L < U, U < min(A) and L < min(B).
    %
:- func n_diff_na_b(int, int, ranges, ranges) = ranges.

n_diff_na_b(L, U, As, nil) = range(L, U, As).
n_diff_na_b(L, UA, As0, Bs @ range(LB, UB, Bs0)) = Result :-
    compare(R, UA, LB),
    (
        R = (<),
        Result = range(L, UA, ranges.union(As0, Bs))
    ;
        R = (=),
        Result = n_diff_na_b(L, UB, Bs0, As0)
    ;
        R = (>),
        Result = n_int_na_nb(L, UA, As0, UB, Bs0)
    ).

    % diff_a_nb(A, U, B) = A \ ({X | X > U} \ B)
    %
    % assuming U < min(B).
    %
:- func diff_a_nb(ranges, int, ranges) = ranges.

diff_a_nb(nil, _, _) = nil.
diff_a_nb(As @ range(LA, UA, As0), UB, Bs0) = Result :-
    compare(R, LA, UB),
    (
        R = (<),
        Result = n_union_na_nb(LA, UA, As0, UB, Bs0)
    ;
        R = (=),
        Result = diff_a_nb(Bs0, UA, As0)
    ;
        R = (>),
        Result = ranges.intersect(As, Bs0)
    ).

    % diff_na_nb(UA, A, UB, B) = ({X | X > UA} \ A) \ ({Y | Y > UB} \ B)
    %
    % assuming UA < min(A) and UB < min(B).
    %
:- func diff_na_nb(int, ranges, int, ranges) = ranges.

diff_na_nb(UA, As0, UB, Bs0) = Result :-
    compare(R, UA, UB),
    (
        R = (<),
        Result = n_union_a_nb(UA, As0, UB, Bs0)
    ;
        R = (=),
        Result = ranges.difference(Bs0, As0)
    ;
        R = (>),
        Result = int_na_b(UA, As0, Bs0)
    ).

%---------------------------------------------------------------------------%

:- pragma foreign_export("C",
    ranges.split(in, out, out, out), "ML_ranges_split").
:- pragma foreign_export("Java",
    ranges.split(in, out, out, out), "split").

split(range(Lo, Hi, Rest), Lo + 1, Hi, Rest).

%---------------------------------------------------------------------------%

prune_to_next_non_member(nil, nil, !N).
prune_to_next_non_member(As @ range(LA, UA, As0), Result, !N) :-
    ( if !.N =< LA then
        Result = As
    else if !.N =< UA then
        !:N = UA + 1,
        Result = As0
    else
        prune_to_next_non_member(As0, Result, !N)
    ).

prune_to_prev_non_member(nil, nil, !N).
prune_to_prev_non_member(range(LA, UA, As0), Result, !N) :-
    ( if !.N =< LA then
        Result = nil
    else if !.N =< UA then
        !:N = LA,
        Result = nil
    else
        prune_to_prev_non_member(As0, Result0, !N),
        Result = range(LA, UA, Result0)
    ).

%---------------------------------------------------------------------------%

list_to_ranges(List) = Set :-
    list_to_ranges(List, Set).

list_to_ranges(List, Set) :-
    list.foldl(ranges.insert, List, ranges.empty, Set).

from_list(List) = list_to_ranges(List).

set_to_ranges(Set) = Ranges :-
    set_to_ranges(Set, Ranges).

set_to_ranges(Set, Ranges) :-
    set.foldl(ranges.insert, Set, ranges.empty, Ranges).

from_set(Set) = set_to_ranges(Set).

%---------------------------------------------------------------------------%

to_sorted_list(nil) = [].
to_sorted_list(range(Lo, Hi, Rest)) =
    to_sorted_list_2(Lo, Hi, to_sorted_list(Rest)).

:- func to_sorted_list_2(int, int, list(int)) = list(int).

to_sorted_list_2(Lo, Hi, List) =
    ( if Hi = Lo then
        List
    else
        to_sorted_list_2(Lo, Hi - 1, [Hi | List])
    ).

%---------------------------------------------------------------------------%

:- pragma foreign_export("C",    ranges.count(in) = out, "ML_ranges_count").
:- pragma foreign_export("Java", ranges.count(in) = out, "count").

count(Set) = N :-
    ucount_acc(Set, 0u, UN),
    N = uint.cast_to_int(UN).

ucount(Set) = N :-
    ucount_acc(Set, 0u, N).

:- pred ucount_acc(ranges::in, uint::in, uint::out) is det.

ucount_acc(nil, !N).
ucount_acc(range(Lo, Hi, Rest), !N) :-
    !:N = !.N + uint.cast_from_int(Hi - Lo),
    ucount_acc(Rest, !N).

:- pragma foreign_export("C",    ranges.size(in) = out, "ML_ranges_size").
:- pragma foreign_export("Java", ranges.size(in) = out, "size").

size(Xs) = count(Xs).

%---------------------------------------------------------------------------%

median(Set) = Median :-
    Count = count(Set),
    ( if Count > 0 then
        MiddleIndex = (Count + 1) / 2
    else
        error($pred, "empty set")
    ),
    Median = element_index(Set, MiddleIndex).

    % element_index(Intervals, I) returns the I'th largest value in the set
    % represented by Intervals (the least item in the set having index 1).
    %
:- func element_index(ranges, int) = int.

element_index(nil, _) =
    func_error($pred, "index out of range").
element_index(range(L, U, Rest), I) = N :-
    N0 = L + I,
    ( if N0 =< U then
        N = N0
    else
        N = element_index(Rest, N0 - U)
    ).

%---------------------------------------------------------------------------%

least(range(L, _, _), L + 1).

greatest(range(_, U0, As), U) :-
    greatest_loop(U0, As, U).

:- pred greatest_loop(int::in, ranges::in, int::out) is det.

greatest_loop(U, nil, U).
greatest_loop(_, range(_, U0, As), U) :-
    greatest_loop(U0, As, U).

next(range(L, U, As), N0, N) :-
    ( if N0 < U then
        N = int.max(L, N0) + 1
    else
        ranges.next(As, N0, N)
    ).

search_range(N, range(Lo0, Hi0, Rest), Lo, Hi) :-
    ( if
        N > Lo0,
        N =< Hi0
    then
        Lo = Lo0 + 1,
        Hi = Hi0
    else
        search_range(N, Rest, Lo, Hi)
    ).

%---------------------------------------------------------------------------%

restrict_min(_, nil) = nil.
restrict_min(Min, As0 @ range(L, U, As1)) = As :-
    ( if Min =< L then
        As = As0
    else if Min =< U then
        As = range(Min - 1, U, As1)
    else
        As = restrict_min(Min, As1)
    ).

restrict_min(Min, !Set) :-
    !:Set = restrict_min(Min, !.Set).

%---------------------%

restrict_max(_, nil) = nil.
restrict_max(Max, range(L, U, As0)) = As :-
    ( if Max =< L then
        As = nil
    else if Max =< U then
        As = range(L, Max, nil)
    else
        As = range(L, U, restrict_max(Max, As0))
    ).

restrict_max(Max, !Set) :-
    !:Set = restrict_max(Max, !.Set).

%---------------------%

restrict_range(Min, Max, As) =
    ranges.intersect(range(Min - 1, Max, nil), As).

restrict_range(Min, Max, !Set) :-
    !:Set = restrict_range(Min, Max, !.Set).

%---------------------------------------------------------------------------%

negate(As) = negate_aux(As, nil).

:- func negate_aux(ranges::in, ranges::in) = (ranges::out) is det.

negate_aux(nil, As) = As.
negate_aux(range(L, U, As), A) = negate_aux(As, range(-U-1, -L-1, A)).

%---------------------%

plus(nil, nil) = nil.
plus(nil, range(_,_,_)) = nil.
plus(range(_,_,_), nil) = nil.
plus(range(La, Ha, nil), range(L, H, nil)) = range(La + L + 1, Ha + H, nil).
plus(range(Lx0, Hx0, Xs0 @ range(Lx1, Hx1, Xs1)), range(L, H, nil)) = Result :-
    ( if Lx1 - Hx0 < H - L then
        Result = plus(range(Lx0, Hx1, Xs1), range(L, H, nil))
    else
        Result = range(Lx0 + L + 1, Hx0 + H, plus(Xs0, range(L, H, nil)))
    ).
plus(range(Lx, Hx, Xs), range(L, H, S @ range(_,_,_))) = Result :-
    A = plus(range(Lx, Hx, Xs), range(L, H, nil)),
    B = plus(range(Lx, Hx, Xs), S),
    Result = union(A,B).

%---------------------%

shift(nil, _) = nil.
shift(As @ range(L, H, As0), C) = Result :-
    ( if C = 0 then
        Result = As
    else
        Result = range(L + C, H + C, shift(As0, C))
    ).

%---------------------%

dilation(nil, _) = nil.
dilation(A @ range(_,_,_) , C) = Result :-
    ( if C < 0 then
        Result = dilation(negate(A), -C)
    else if C = 0 then
        Result = range(-1, 0, nil)
    else if C = 1 then
        Result = A
    else
        L = to_sorted_list(A),
        list.map(*(C), L) = L0,
        Result = from_list(L0)
    ).

%---------------------%

contraction(nil, _) = nil.
contraction(A @ range(L, H, As), C) = Result :-
    ( if C < 0 then
        Result = contraction(negate(A), -C)
    else if C = 0 then
        Result = range(-1, 0, nil)
    else if C = 1 then
        Result = A
    else
        L0 = div_up_xp(L + 1, C) - 1,
        H0 = div_down_xp(H, C),
        Result = contraction_0(L0, H0, As, C)
    ).

:- func contraction_0(int, int, ranges, int) = ranges.

contraction_0(L0, H0, nil, _) = range(L0, H0, nil).
contraction_0(L0, H0, range(L1, H1, As), C) = Result :-
    L1N = div_up_xp(L1 + 1, C) - 1,
    H1N = div_down_xp(H1, C),
    ( if H0 >= L1N then
        Result = contraction_0(L0, H1N, As, C)
    else
        Result = range(L0, H0, contraction_0(L1N, H1N, As, C))
    ).

%---------------------%

   % 0 < B. Round up.
   %
:- func div_up_xp(int::in, int::in) = (int::out) is det.

div_up_xp(A, B) = (A > 0 -> div_up_pp(A, B) ; div_up_np(A, B)).

    % 0 < A,B. Round up.
    %
:- func div_up_pp(int::in, int::in) = (int::out) is det.

div_up_pp(A, B) = int.unchecked_quotient(A + B - 1, B).

   % A < 0 < B. Round up.
   %
:- func div_up_np(int::in, int::in) = (int::out) is det.

div_up_np(A, B) = int.unchecked_quotient(A, B).

   % 0 < B. Round down.
   %
:- func div_down_xp(int::in, int::in) = (int::out) is det.

div_down_xp(A, B) = (A > 0 -> div_down_pp(A, B) ; div_down_np(A, B)).

    % 0 < A,B. Round down.
    %
:- func div_down_pp(int::in, int::in) = (int::out) is det.

div_down_pp(A, B) = int.unchecked_quotient(A, B).

    % A < 0 < B. Round down.
    %
:- func div_down_np(int::in, int::in) = (int::out) is det.

div_down_np(A, B) = int.unchecked_quotient(A - B + 1, B).

%---------------------------------------------------------------------------%

foldl(P, Ranges, !Acc) :-
    (
        Ranges = nil
    ;
        Ranges = range(L, U, Rest),
        int.fold_up(P, L + 1, U, !Acc),
        foldl(P, Rest, !Acc)
    ).

foldl2(P, Ranges, !Acc1, !Acc2) :-
    (
        Ranges = nil
    ;
        Ranges = range(L, U, Rest),
        int.fold_up2(P, L + 1, U, !Acc1, !Acc2),
        foldl2(P, Rest, !Acc1, !Acc2)
    ).

foldl3(P, Ranges, !Acc1, !Acc2, !Acc3) :-
    (
        Ranges = nil
    ;
        Ranges = range(L, U, Rest),
        int.fold_up3(P, L + 1, U, !Acc1, !Acc2, !Acc3),
        foldl3(P, Rest, !Acc1, !Acc2, !Acc3)
    ).

foldr(P, Ranges, !Acc) :-
    (
        Ranges = nil
    ;
        Ranges = range(L, H, Rest),
        foldr(P, Rest, !Acc),
        int.fold_down(P, L + 1, H, !Acc)
    ).

%---------------------------------------------------------------------------%

range_foldl(_, nil, !Acc).
range_foldl(P, range(L, U, Rest), !Acc) :-
    P(L + 1, U, !Acc),
    range_foldl(P, Rest, !Acc).

range_foldl2(_, nil, !Acc1, !Acc2).
range_foldl2(P, range(L, U, Rest), !Acc1, !Acc2) :-
    P(L + 1, U, !Acc1, !Acc2),
    range_foldl2(P, Rest, !Acc1, !Acc2).

range_foldr(_, nil, !Acc).
range_foldr(P, range(L, U, Rest), !Acc) :-
    range_foldr(P, Rest, !Acc),
    P(L + 1, U, !Acc).

%---------------------------------------------------------------------------%
:- end_module ranges.
%---------------------------------------------------------------------------%