%--------------------------------------------------%
% 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-2018 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: ranges.m.
% Authors: Mark Brown.
% Stability: medium.
%
% This module defines the ranges abstract type.
%
%--------------------------------------------------%

:- module ranges.
:- interface.

:- import_module list.
:- import_module set.

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

    % Range lists represent sets of integers. Each contiguous block
    % of integers in the set is stored as a range which specifies
    % the bounds of the block, and these ranges are kept in a list-like
    % structure.
    %
:- type ranges.

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

    % is_empty(Set):
    % Succeeds iff Set is the empty set.
    %
:- pred is_empty(ranges::in) is semidet.

    % is_non_empty(Set):
    % Succeeds iff Set is not the empty set.
    %
:- pred is_non_empty(ranges::in) is semidet.

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

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

    % split(D, L, H, Rest) is true iff L..H is the first range
    % in D, and Rest is the domain D with this range removed.
    %
:- pred split(ranges::in, int::out, int::out, ranges::out) is semidet.

    % is_contiguous(R, L, H) <=> split(R, L, H, empty):
    % Test if the set is a contiguous set of integers and return the endpoints
    % of this set if this is the case.
    %
:- pred is_contiguous(ranges::in, int::out, int::out) is semidet.

    % Add an integer to the set.
    %
:- func insert(int, ranges) = ranges.
:- pred insert(int::in, ranges::in, ranges::out) is det.

    % Delete an integer from the set.
    %
:- func delete(int, ranges) = ranges.

    % Return the number of distinct integers which are in the ranges
    % (as opposed to the number of ranges).
    %
:- func size(ranges) = int.

    % Returns the median value of the set. In case of a tie, returns
    % the lower of the two options.
    %
:- func median(ranges) = int.

    % least(A, N) is true iff N is the least element of A.
    %
:- pred least(ranges::in, int::out) is semidet.

    % greatest(A, N) is true iff N is the greatest element of A.
    %
:- pred greatest(ranges::in, int::out) is semidet.

    % next(A, N0, N) is true iff N is the least element of A greater
    % than N0.
    %
:- pred next(ranges::in, int::in, int::out) is semidet.

    % Test set membership.
    %
:- pred member(int::in, ranges::in) is semidet.

    % Nondeterministically produce each range.
    %
:- pred range_member(int::out, int::out, ranges::in) is nondet.

    % Nondeterministically produce each element.
    %
:- pred nondet_member(int::out, ranges::in) is nondet.

    % subset(A, B) is true iff every value in A is in B.
    %
:- pred subset(ranges::in, ranges::in) is semidet.

    % disjoint(A, B) is true iff A and B have no values in common.
    %
:- pred disjoint(ranges::in, ranges::in) is semidet.

    % union(A, B) contains all the integers in either A or B.
    %
:- func union(ranges, ranges) = ranges.

    % intersection(A, B) contains all the integers in both A and B.
    %
:- func intersection(ranges, ranges) = ranges.

    % difference(A, B) contains all the integers which are in A but
    % not in B.
    %
:- func difference(ranges, ranges) = ranges.

    % restrict_min(Min, A) contains all integers in A which are greater
    % than or equal to Min.
    %
:- func restrict_min(int, ranges) = ranges.

    % restrict_max(Max, A) contains all integers in A which are less than
    % or equal to Max.
    %
:- func restrict_max(int, ranges) = ranges.

    % restrict_range(Min, Max, A) contains all integers I in A which
    % satisfy Min =< I =< Max.
    %
:- func restrict_range(int, int, ranges) = ranges.

    % prune_to_next_non_member(A0, A, N0, N):
    %
    % N is the smallest integer larger than or equal to N0 which is not
    % in A0. A is the set A0 restricted to values greater than N.
    %
:- pred prune_to_next_non_member(ranges::in, ranges::out,
    int::in, int::out) is det.

    % prune_to_prev_non_member(A0, A, N0, N):
    %
    % N is the largest integer smaller than or equal to N0 which is not
    % in A0. A is the set A0 restricted to values less than N.
    %
:- pred prune_to_prev_non_member(ranges::in, ranges::out,
    int::in, int::out) is det.

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

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

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

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

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

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

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

    % Convert from a list of integers.
    %
:- func from_list(list(int)) = ranges.

    % Convert from a set of integers.
    %
:- func from_set(set(int)) = ranges.

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

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

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

:- pred foldl(pred(int, A, A), ranges, A, A).
:- mode foldl(pred(in, in, out) is det, in, in, out) is det.
:- mode foldl(pred(in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldl(pred(in, di, uo) is det, in, di, uo) is det.
:- mode foldl(pred(in, in, out) is semidet, in, in, out) is semidet.
:- mode foldl(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet.
:- mode foldl(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(pred(in, in, out, in, out) is det, in, in, out,
    in, out) is det.
:- mode foldl2(pred(in, in, out, mdi, muo) is det, in, in, out,
    mdi, muo) is det.
:- mode foldl2(pred(in, in, out, di, uo) is det, in, in, out,
    di, uo) is det.
:- mode foldl2(pred(in, in, out, in, out) is semidet, in, in, out,
    in, out) is semidet.
:- mode foldl2(pred(in, in, out, mdi, muo) is semidet, in, in, out,
    mdi, muo) is semidet.
:- mode foldl2(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(pred(in, in, out, in, out, in, out) is det, in,
    in, out, in, out, in, out) is det.
:- mode foldl3(pred(in, in, out, in, out, mdi, muo) is det, in,
    in, out, in, out, mdi, muo) is det.
:- mode foldl3(pred(in, in, out, in, out, di, uo) is det, in,
    in, out, in, out, di, uo) is det.
:- mode foldl3(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(pred(in, in, out) is det, in, in, out) is det.
:- mode foldr(pred(in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldr(pred(in, di, uo) is det, in, di, uo) is det.
:- mode foldr(pred(in, in, out) is semidet, in, in, out) is semidet.
:- mode foldr(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet.
:- mode foldr(pred(in, di, uo) is semidet, in, di, uo) is semidet.

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

    % 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(pred(in, in, in, out) is det, in, in, out) is det.
:- mode range_foldl(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
:- mode range_foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode range_foldl(pred(in, in, in, out) is semidet, in, in, out) is semidet.
:- mode range_foldl(pred(in, in, mdi, muo) is semidet, in, mdi, muo)
    is semidet.
:- mode range_foldl(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(pred(in, in, in, out, in, out) is det,
    in, in, out, in, out) is det.
:- mode range_foldl2(pred(in, in, in, out, mdi, muo) is det,
    in, in, out, mdi, muo) is det.
:- mode range_foldl2(pred(in, in, in, out, di, uo) is det,
    in, in, out, di, uo) is det.
:- mode range_foldl2(pred(in, in, in, out, in, out) is semidet,
    in, in, out, in, out) is semidet.
:- mode range_foldl2(pred(in, in, in, out, mdi, muo) is semidet,
    in, in, out, mdi, muo) is semidet.
:- mode range_foldl2(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(pred(in, in, in, out) is det, in, in, out) is det.
:- mode range_foldr(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
:- mode range_foldr(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode range_foldr(pred(in, in, in, out) is semidet, in, in, out)
    is semidet.
:- mode range_foldr(pred(in, in, mdi, muo) is semidet, in, mdi, muo)
    is semidet.
:- mode range_foldr(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 iff `r` is the empty set.
%
% MR_Integer ML_ranges_size(ML_Ranges r);
% Return the number of distinct integers in `r'.
%
% 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 iff `r' is the empty set.
%
% int size(ranges.Ranges_0 r);
% Return the number of distinct integers in `r'.
%
% 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'.

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