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

## 73 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-2019, 2022-2024 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.

%--------------------------------------------------%
%
% 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. Note that min_int
% cannot be represented in any set.
%
:- func universe = ranges.

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

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

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

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

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

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

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

% range_member(Lo, Hi, Set):
%
% 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 range_member(int::out, int::out, ranges::in) is nondet.

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

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

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

% delete(X, Set0, Set) is true iff 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.
%
:- func delete(int, ranges) = ranges.

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

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

% disjoint(SetA, SetB) is true iff 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.

% intersection(SetA, SetB): return the set that contains all the integers
% in both SetA and SetB.
:- func intersection(ranges, ranges) = ranges.

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

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

% split(Set, Lo, Hi, Rest) is true iff 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 from_list(list(int)) = ranges.

% Convert from a set of integers.
%
:- 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 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.
%
:- func median(ranges) = int.

% least(Set, X) is true iff 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 iff 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 iff 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.

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

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

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

```

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