%--------------------------------------------------%
% 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-2025 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
% (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.

    % 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.
    %
:- 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.
    %
:- 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.
    %
:- 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.

    % A synonym for count/1.
    %
:- 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.
%

    % 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'.
%
%--------------------------------------------------%
%--------------------------------------------------%