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]