Next: , Previous: random, Up: Top   [Contents]


55 ranges

%--------------------------------------------------%
% 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 The Mercury team.
% 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.
%--------------------------------------------------%
%
% 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 an 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.
%
% int ML_ranges_is_empty(ML_Ranges ranges);
% Succeeds iff ranges is the empty set.
%
% MR_Integer ML_ranges_size(ML_Ranges ranges);
% Return the number of distinct integers in a range.a
%
% int ML_ranges_split(ML_Ranges d, MR_Integer *l, MR_Integer *h,
%       ML_Ranges *rest);
% If `d' is not the empty set, then set `l' and `h"'to the lower
% and upper bound of the first range in `d'; `rest' is set to `d'
% with the first range removed.
%
% 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'.
%
%--------------------------------------------------%
%--------------------------------------------------%


Next: , Previous: random, Up: Top   [Contents]