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

## 20 diet

```%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 2014 The Mercury team.
% Copyright (C) 2012-2014 YesLogic Pty. Ltd.
% 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: diet.m.
% Author: wangp.
% Stability: medium.
%
% Discrete Interval Encoding Trees are a highly efficient set implementation
% for fat sets, i.e. densely populated sets over a discrete linear order.
%
% M. Erwig: Diets for Fat Sets,
% Journal of Functional Programming, Vol. 8, No. 6, pp. 627-632.
%
% O. Friedmann, M. Lange: More on Balanced Diets,
% Journal of Functional Programming, volume 21, issue 02, pp. 135-157.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module diet.
:- interface.

:- import_module bool.
:- import_module enum.
:- import_module list.

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

:- type diet(T). % <= diet_element(T).

:- typeclass diet_element(T) where [
% less_than(X, Y) succeeds iff X < Y.
pred less_than(T::in, T::in) is semidet,

% successor(X) returns the successor of X, e.g. X + 1.
func successor(T) = T,

% predecessor(X) returns the predecessor of X, e.g. X - 1.
func predecessor(T) = T
].

:- instance diet_element(int).

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

% Return an empty set.
%
:- func init = diet(T).
:- pred init(diet(T)::out) is det.

:- pred empty(diet(T)).
:- mode empty(in) is semidet.
:- mode empty(out) is det.

:- pred is_empty(diet(T)::in) is semidet.

:- pred is_non_empty(diet(T)::in) is semidet.

% `equal(SetA, SetB)' is true iff `SetA' and `SetB' contain the same
% elements.
%
:- pred equal(diet(T)::in, diet(T)::in) is semidet <= diet_element(T).

% `make_singleton_set(Elem)' returns a set containing just the single
% element `Elem'.
%
:- func make_singleton_set(T) = diet(T) <= diet_element(T).

% `make_interval_set(X, Y)' returns a set containing just the elements in
% the interval [X, Y]. Throws an exception if Y < X.
%
:- func make_interval_set(T, T) = diet(T) <= diet_element(T).

% `is_singleton(Set, X)' is true iff `Set' is a singleton containing the
% element `X'.
%
:- pred is_singleton(diet(T)::in, T::out) is semidet <= diet_element(T).

% `contains(Set, X)' is true iff `X' is a member of `Set'.
%
:- pred contains(diet(T)::in, T::in) is semidet <= diet_element(T).

% `member(X, Set)' is true iff `X' is a member of `Set'.
%
:- pred member(T, diet(T)) <= diet_element(T).
:- mode member(in, in) is semidet.
:- mode member(out, in) is nondet.

% `subset(Subset, Set)' is true iff `Subset' is a subset of `Set'.
%
:- pred subset(diet(T)::in, diet(T)::in) is semidet <= diet_element(T).

% `superset(Superset, Set)' is true iff `Superset' is a superset of `Set'.
%
:- pred superset(diet(T)::in, diet(T)::in) is semidet <= diet_element(T).

% `insert(X, Set0, Set)' is true iff `Set' is the union of
% `Set0' and the set containing only `X'.
%
:- func insert(diet(T), T) = diet(T) <= diet_element(T).
:- pred insert(T::in, diet(T)::in, diet(T)::out) is det <= diet_element(T).

% `insert_new(X, Set0, Set)' is true iff `Set0' does not contain
% `X', and `Set' is the union of `Set0' and the set containing only `X'.
%
:- pred insert_new(T::in, diet(T)::in, diet(T)::out) is semidet
<= diet_element(T).

% `insert_list(Xs, Set0, Set)' is true iff `Set' is the union of
% `Set0' and the set containing only the members of `Xs'.
%
:- func insert_list(diet(T), list(T)) = diet(T) <= diet_element(T).
:- pred insert_list(list(T)::in, diet(T)::in, diet(T)::out) is det
<= diet_element(T).

% `insert_interval(X, Y, Set0, Set)' is true iff `Set' is the union of
% `Set0' and the set containing only the elements of the interval [X, Y].
% Throws an exception if Y < X.
%
:- pred insert_interval(T::in, T::in, diet(T)::in, diet(T)::out) is det
<= diet_element(T).

% `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(diet(T), T) = diet(T) <= diet_element(T).
:- pred delete(T::in, diet(T)::in, diet(T)::out) is det <= diet_element(T).

% `delete_list(Set, X)' returns the difference of `Set' and the set
% containing only the members of `X'. Same as
% `difference(Set, list_to_set(X))', but may be more efficient.
%
:- func delete_list(diet(T), list(T)) = diet(T) <= diet_element(T).
:- pred delete_list(list(T)::in, diet(T)::in, diet(T)::out) is det
<= diet_element(T).

% `remove(X, Set0, Set)' is true iff `Set0' contains `X',
% and `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'.
%
:- pred remove(T::in, diet(T)::in, diet(T)::out) is semidet <= diet_element(T).

% `remove_list(X, Set0, Set)' returns in `Set' the difference of `Set0'
% and the set containing all the elements of `X', failing if any element
% of `X' is not in `Set0'. Same as `subset(list_to_set(X), Set0),
% difference(Set0, list_to_set(X), Set)', but may be more efficient.
%
:- pred remove_list(list(T)::in, diet(T)::in, diet(T)::out) is semidet
<= diet_element(T).

% `remove_least(X, Set0, Set)' is true iff `X' is the least element in
% `Set0', and `Set' is the set which contains all the elements of `Set0'
% except `X'.
%
:- pred remove_least(T::out, diet(T)::in, diet(T)::out) is semidet
<= diet_element(T).

% `split(X, Set, Lesser, IsPresent, Greater)' is true iff `Lesser' is the
% set of elements in `Set' which are less than `X' and `Greater' is the set
% of elements in `Set' which are greater than `X'.
% `IsPresent' is `yes' if `Set' contains `X', and `no' otherwise.
%
:- pred split(T::in, diet(T)::in, diet(T)::out, bool::out, diet(T)::out) is det
<= diet_element(T).

% `union(SetA, SetB, Set)' is true iff `Set' is the union of
% `SetA' and `SetB'.
%
:- func union(diet(T), diet(T)) = diet(T) <= diet_element(T).
:- pred union(diet(T)::in, diet(T)::in, diet(T)::out) is det
<= diet_element(T).

% `union_list(Sets, Set)' returns the union of all the sets in Sets.
%
:- func union_list(list(diet(T))) = diet(T) <= diet_element(T).
:- pred union_list(list(diet(T))::in, diet(T)::out) is det <= diet_element(T).

% `intersect(SetA, SetB, Set)' is true iff `Set' is the
% intersection of `SetA' and `SetB'.
%
:- func intersect(diet(T), diet(T)) = diet(T) <= diet_element(T).
:- pred intersect(diet(T)::in, diet(T)::in, diet(T)::out) is det
<= diet_element(T).

% `intersect_list(Sets, Set)' returns the intersection of all the sets
% in Sets.
%
:- func intersect_list(list(diet(T))) = diet(T) <= diet_element(T).
:- pred intersect_list(list(diet(T))::in, diet(T)::out) is det
<= diet_element(T).

% `difference(SetA, SetB)' returns the set containing all the elements
% of `SetA' except those that occur in `SetB'.
%
:- func difference(diet(T), diet(T)) = diet(T) <= diet_element(T).
:- pred difference(diet(T)::in, diet(T)::in, diet(T)::out) is det
<= diet_element(T).

% divide(Pred, Set, InPart, OutPart):
% InPart consists of those elements of Set for which Pred succeeds;
% OutPart consists of those elements of Set for which Pred fails.
%
:- pred divide(pred(T)::in(pred(in) is semidet), diet(T)::in,
diet(T)::out, diet(T)::out) is det <= diet_element(T).

% divide_by_set(DivideBySet, Set, InPart, OutPart):
% InPart consists of those elements of Set which are also in DivideBySet;
% OutPart consists of those elements of Set which are not in DivideBySet.
%
:- pred divide_by_set(diet(T)::in, diet(T)::in, diet(T)::out, diet(T)::out)
is det <= diet_element(T).

% `count(Set)' returns the number of elements in Set.
%
:- func count(diet(T)) = int <= enum(T).

% `foldl_intervals(Pred, Set, Start)' calls Pred with each interval of
% `Set' (in sorted order) and an accumulator (with the initial value of
% `Start'), and returns the final value.
%
:- pred foldl_intervals(pred(T, T, A, A), diet(T), A, A) <= diet_element(T).
:- mode foldl_intervals(pred(in, in, in, out) is det, in, in, out) is det.
:- mode foldl_intervals(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode foldl_intervals(pred(in, in, in, out) is semidet, in, in, out)
is semidet.

% `foldr_intervals(Pred, Set, Start)' calls Pred with each interval of
% `Set' (in reverse sorted order) and an accumulator (with the initial
% value of `Start'), and returns the final value.
%
:- pred foldr_intervals(pred(T, T, A, A), diet(T), A, A) <= diet_element(T).
:- mode foldr_intervals(pred(in, in, in, out) is det, in, in, out) is det.
:- mode foldr_intervals(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode foldr_intervals(pred(in, in, in, out) is semidet, in, in, out)
is semidet.

% `foldl(Func, Set, Start)' calls Func with each element of `Set'
% (in sorted order) and an accumulator (with the initial value of `Start'),
% and returns the final value.
%
:- func foldl(func(T, A) = A, diet(T), A) = A <= diet_element(T).

:- pred foldl(pred(T, A, A), diet(T), A, A) <= diet_element(T).
:- 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(T, A, A, B, B), diet(T), A, A, B, B) <= diet_element(T).
:- 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(T, A, A, B, B, C, C), diet(T),
A, A, B, B, C, C) <= diet_element(T).
:- 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, in, out) is semidet, in,
in, out, in, out, in, out) is semidet.
:- mode foldl3(pred(in, in, out, in, out, mdi, muo) is semidet, in,
in, out, in, out, mdi, muo) is semidet.
:- mode foldl3(pred(in, in, out, in, out, di, uo) is semidet, in,
in, out, in, out, di, uo) is semidet.

:- pred foldl4(pred(T, A, A, B, B, C, C, D, D), diet(T),
A, A, B, B, C, C, D, D) <= diet_element(T).
:- mode foldl4(pred(in, in, out, in, out, in, out, in, out) is det, in,
in, out, in, out, in, out, in, out) is det.
:- mode foldl4(pred(in, in, out, in, out, in, out, mdi, muo) is det, in,
in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl4(pred(in, in, out, in, out, in, out, di, uo) is det, in,
in, out, in, out, in, out, di, uo) is det.
:- mode foldl4(pred(in, in, out, in, out, in, out, in, out) is semidet, in,
in, out, in, out, in, out, in, out) is semidet.
:- mode foldl4(pred(in, in, out, in, out, in, out, mdi, muo) is semidet, in,
in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl4(pred(in, in, out, in, out, in, out, di, uo) is semidet, in,
in, out, in, out, in, out, di, uo) is semidet.

:- pred foldl5(pred(T, A, A, B, B, C, C, D, D, E, E), diet(T),
A, A, B, B, C, C, D, D, E, E) <= diet_element(T).
:- mode foldl5(
pred(in, in, out, in, out, in, out, in, out, in, out) is det,
in, in, out, in, out, in, out, in, out, in, out) is det.
:- mode foldl5(
pred(in, in, out, in, out, in, out, in, out, mdi, muo) is det,
in, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode foldl5(
pred(in, in, out, in, out, in, out, in, out, di, uo) is det,
in, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode foldl5(
pred(in, in, out, in, out, in, out, in, out, in, out) is semidet,
in, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode foldl5(
pred(in, in, out, in, out, in, out, in, out, mdi, muo) is semidet,
in, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode foldl5(
pred(in, in, out, in, out, in, out, in, out, di, uo) is semidet,
in, in, out, in, out, in, out, in, out, di, uo) is semidet.

:- func foldr(func(T, A) = A, diet(T), A) = A <= diet_element(T).

:- pred foldr(pred(T, A, A), diet(T), A, A) <= diet_element(T).
:- 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.

% all_true(Pred, Set) succeeds iff Pred(Element) succeeds
% for all the elements of Set.
%
:- pred all_true(pred(T)::in(pred(in) is semidet), diet(T)::in) is semidet
<= diet_element(T).

% `filter(Pred, Set) = TrueSet' returns the elements of Set for which
% Pred succeeds.
%
:- func filter(pred(T), diet(T)) = diet(T) <= diet_element(T).
:- mode filter(pred(in) is semidet, in) = out is det.

% `filter(Pred, Set, TrueSet, FalseSet)' returns the elements of Set
% for which Pred succeeds, and those for which it fails.
%
:- pred filter(pred(T), diet(T), diet(T), diet(T)) <= diet_element(T).
:- mode filter(pred(in) is semidet, in, out, out) is det.

% `list_to_set(List)' returns a set containing only the members of `List'.
%
:- func list_to_set(list(T)) = diet(T) <= diet_element(T).
:- pred list_to_set(list(T)::in, diet(T)::out) is det <= diet_element(T).

:- func from_list(list(T)) = diet(T) <= diet_element(T).
:- pred from_list(list(T)::in, diet(T)::out) is det <= diet_element(T).

% `sorted_list_to_set(List)' returns a set containing only the members
% of `List'. `List' must be sorted.
%
:- func sorted_list_to_set(list(T)) = diet(T) <= diet_element(T).
:- pred sorted_list_to_set(list(T)::in, diet(T)::out) is det
<= diet_element(T).

% `to_sorted_list(Set)' returns a list containing all the members of `Set',
% in sorted order.
%
:- func to_sorted_list(diet(T)) = list(T) <= diet_element(T).
:- pred to_sorted_list(diet(T)::in, list(T)::out) is det <= diet_element(T).

% `to_sorted_interval_list(Set)' returns a list of intervals in `Set'
% in sorted order, where each interval is represented by a tuple.
% The intervals do not overlap.
%
:- pred to_sorted_interval_list(diet(T)::in, list({T, T})::out) is det
<= diet_element(T).

% `from_interval_list(Intervals, Set)' returns a Set containing the
% elements of all intervals [X, Y] in Intervals, where each interval is
% represented by a tuple. Throws an exception if any interval has Y < X.
% The intervals may overlap.
%
:- pred from_interval_list(list({T, T})::in, diet(T)::out) is det
<= diet_element(T).

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

```

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