Next: benchmarking, Previous: assoc_list, Up: Top [Contents]
%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 1994-1999, 2003-2007, 2011 The University of Melbourne.
% Copyright (C) 2013-2015, 2017-2018 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: bag.m.
% Main authors: conway, crs.
% Stability: medium.
%
% An implementation of multisets.
%
%--------------------------------------------------%
%--------------------------------------------------%
:- module bag.
:- interface.
:- import_module assoc_list.
:- import_module list.
:- import_module set.
%--------------------------------------------------%
:- type bag(T).
%--------------------------------------------------%
% Create an empty bag.
%
:- func init = bag(T).
:- pred init(bag(T)::out) is det.
% Create a bag containing the given item.
%
:- func singleton(T) = bag(T).
% Check whether a bag is empty.
%
:- pred is_empty(bag(T)::in) is semidet.
%--------------------------------------------------%
% contains(Bag, X):
%
% Check whether Bag contains X.
%
:- pred contains(bag(T)::in, T::in) is semidet.
% count_value(Bag, X):
%
% Return how many occurrences of X Bag contains.
% Return 0 if X is not in Bag.
%
:- func count_value(bag(T), T) = int.
:- pred count_value(bag(T)::in, T::in, int::out) is det.
% member(X, Bag):
%
% True iff `Bag' contains at least one occurrence of `X'.
%
:- pred member(T::in, bag(T)::in) is semidet.
% member(X, Bag, BagMinusX):
%
% Nondeterministically returns all values X from Bag, and the corresponding
% bag after X has been removed. Duplicate values are returned as
% many times as they occur in the Bag.
%
:- pred member(T::out, bag(T)::in, bag(T)::out) is nondet.
%--------------------------------------------------%
% Insert a particular value into a bag.
%
:- func insert(bag(T), T) = bag(T).
:- pred insert(T::in, bag(T)::in, bag(T)::out) is det.
% Insert a list of values into a bag.
%
:- func insert_list(bag(T), list(T)) = bag(T).
:- pred insert_list(list(T)::in, bag(T)::in, bag(T)::out) is det.
% Insert N copies of a particular value into a bag.
% Fails if N < 0.
%
:- pred insert_duplicates(int::in, T::in, bag(T)::in, bag(T)::out)
is semidet.
% As above, but throws an exception if N < 0.
%
:- func det_insert_duplicates(bag(T), int, T) = bag(T).
:- pred det_insert_duplicates(int::in, T::in, bag(T)::in, bag(T)::out) is det.
% Insert a set of values into a bag.
%
:- func insert_set(bag(T), set(T)) = bag(T).
:- pred insert_set(set(T)::in, bag(T)::in, bag(T)::out) is det.
%--------------------------------------------------%
% Remove one occurrence of the smallest value from a bag.
% Fails if the bag is empty.
%
:- pred remove_smallest(T::out, bag(T)::in, bag(T)::out) is semidet.
% Remove one occurrence of a particular value from a bag.
% Fail if the item does not exist in the bag.
%
:- pred remove(T::in, bag(T)::in, bag(T)::out) is semidet.
% Remove one occurrence of a particular value from a bag.
% Throw an exception if the item does not exist in the bag.
%
:- func det_remove(bag(T), T) = bag(T).
:- pred det_remove(T::in, bag(T)::in, bag(T)::out) is det.
% Remove a list of values from a bag. Duplicates are removed from the bag
% the appropriate number of times. Fail if any of the items in the list
% do not exist in the bag.
%
% This call is logically equivalent to:
%
% remove_list(Bag0, RemoveList, Bag) :-
% from_list(RemoveList, RemoveBag),
% is_subbag(RemoveBag, Bag0),
% subtract(Bag0, RemoveBag, Bag).
%
:- pred remove_list(list(T)::in, bag(T)::in, bag(T)::out) is semidet.
% Remove a list of values from a bag. Duplicates are removed from the bag
% the appropriate number of times. Throw an exception if any of the items
% in the list do not exist in the bag.
%
:- func det_remove_list(bag(T), list(T)) = bag(T).
:- pred det_remove_list(list(T)::in, bag(T)::in, bag(T)::out) is det.
% Remove a set of values from a bag. Each value is removed once.
% Fail if any of the items in the set do not exist in the bag.
%
:- pred remove_set(set(T)::in, bag(T)::in, bag(T)::out) is semidet.
% Remove a set of values from a bag. Each value is removed once.
% Throw an exception if any of the items in the set do not exist in the
% bag.
%
:- func det_remove_set(bag(T), set(T)) = bag(T).
:- pred det_remove_set(set(T)::in, bag(T)::in, bag(T)::out) is det.
% Delete one occurrence of a particular value from a bag.
% If the key is not present, leave the bag unchanged.
%
:- func delete(bag(T), T) = bag(T).
:- pred delete(T::in, bag(T)::in, bag(T)::out) is det.
% Remove all occurrences of a particular value from a bag.
% Fail if the item does not exist in the bag.
%
:- pred remove_all(T::in, bag(T)::in, bag(T)::out) is semidet.
% Delete all occurrences of a particular value from a bag.
%
:- func delete_all(bag(T), T) = bag(T).
:- pred delete_all(T::in, bag(T)::in, bag(T)::out) is det.
%--------------------------------------------------%
% Make a bag from a list.
%
:- func bag(list(T)) = bag(T).
:- func from_list(list(T)) = bag(T).
:- pred from_list(list(T)::in, bag(T)::out) is det.
% Make a bag from a sorted list.
%
:- func from_sorted_list(list(T)) = bag(T).
:- pred from_sorted_list(list(T)::in, bag(T)::out) is det.
% Make a bag from a set.
%
:- func from_set(set(T)) = bag(T).
:- pred from_set(set(T)::in, bag(T)::out) is det.
% Given a bag, produce a sorted list containing all the values in the bag.
% Each value will appear in the list the same number of times that it
% appears in the bag.
%
:- func to_list(bag(T)) = list(T).
:- pred to_list(bag(T)::in, list(T)::out) is det.
% Given a bag, produce a sorted list containing all the values in the bag.
% Each value will appear in the list once, with the associated integer
% giving the number of times that it appears in the bag.
%
:- func to_assoc_list(bag(T)) = assoc_list(T, int).
:- pred to_assoc_list(bag(T)::in, assoc_list(T, int)::out) is det.
% Given a bag, produce a sorted list with no duplicates containing
% all the values in the bag.
%
:- func to_list_without_duplicates(bag(T)) = list(T).
:- pred to_list_without_duplicates(bag(T)::in, list(T)::out) is det.
% Given a bag, produce a sorted list containing one copy each
% of all the values that have *more* than one copy in the bag.
%
:- func to_list_only_duplicates(bag(T)) = list(T).
:- pred to_list_only_duplicates(bag(T)::in, list(T)::out) is det.
% Given a bag, produce a set containing all the values in the bag.
%
:- func to_set(bag(T)) = set(T).
%--------------------------------------------------%
% subtract(BagA, BagB, BagAmB):
%
% Subtracts BagB from BagA to produce BagAmB. Each element in BagB is
% removed from BagA to produce BagAmB.
%
% An example:
% subtract({1, 1, 2, 2, 3 }, {1, 1, 2, 3, 3, 3}, {2}).
%
% Use one of the subtract_small variants if BagB is expected to be
% significantly smaller than BagA.
%
:- func subtract(bag(T), bag(T)) = bag(T).
:- pred subtract(bag(T)::in, bag(T)::in, bag(T)::out) is det.
:- func subtract_small(bag(T), bag(T)) = bag(T).
:- pred subtract_small(bag(T)::in, bag(T)::in, bag(T)::out) is det.
% least_upper_bound(BagA, BagB, BagAlubB):
%
% BagAlubB is the least upper bound of BagA and BagB.
% It is the smallest bag that contains at least as many copies
% of each element as BagA, and at least as many copies as BagB.
% If an element X is present AXN in BagA and BXN times in BagB,
% X will be present int.max(AXN, BXN) times in BagAlubB.
%
% An example:
% least_upper_bound({1, 1, 2}, {2, 2, 3}, {1, 1, 2, 2, 3}).
%
% Use one of the least_upper_bound_small variants if BagB is expected
% to be significantly smaller than BagA. (If BagA is expected to be
% significantly smaller than BagB, then switch the operands around.)
%
:- func least_upper_bound(bag(T), bag(T)) = bag(T).
:- pred least_upper_bound(bag(T)::in, bag(T)::in, bag(T)::out) is det.
:- func least_upper_bound_small(bag(T), bag(T)) = bag(T).
:- pred least_upper_bound_small(bag(T)::in, bag(T)::in, bag(T)::out) is det.
% union(BagA, BagB, BagAuB):
%
% BagAuB is the union of BagA and BagB.
%
% An example:
% e.g. {1, 1, 2, 2} U {2, 2, 3, 3} = {1, 1, 2, 2, 2, 2, 3, 3}.
%
% Use one of the union_small variants if BagB is expected to be
% significantly smaller than BagA. (If BagA is expected to be
% significantly smaller than BagB, then switch the operands around.)
%
:- func union(bag(T), bag(T)) = bag(T).
:- pred union(bag(T)::in, bag(T)::in, bag(T)::out) is det.
:- func union_small(bag(T), bag(T)) = bag(T).
:- pred union_small(bag(T)::in, bag(T)::in, bag(T)::out) is det.
% intersect(BagA, BagB, BagAuB):
%
% BagAiB is the intersection of BagA and BagB.
%
% An example:
% intersect({1, 2, 2, 3, 3}, {2, 2, 3, 4}, {2, 2, 3}).
%
% Use one of the intersect_small variants if BagB is expected to be
% significantly smaller than BagA. (If BagA is expected to be
% significantly smaller than BagB, then switch the operands around.)
%
:- func intersect(bag(T), bag(T)) = bag(T).
:- pred intersect(bag(T)::in, bag(T)::in, bag(T)::out) is det.
:- func intersect_small(bag(T), bag(T)) = bag(T).
:- pred intersect_small(bag(T)::in, bag(T)::in, bag(T)::out) is det.
% Fails if there is no intersection between the 2 bags.
% intersect(A, B) :- intersect(A, B, C), not is_empty(C).
%
:- pred intersect(bag(T)::in, bag(T)::in) is semidet.
%--------------------------------------------------%
% Tests whether the first bag is a subbag of the second.
% is_subbag(BagA, BagB) implies that every element in the BagA
% is also in the BagB. If an element is in BagA multiple times,
% it must be in BagB at least as many times.
% e.g. is_subbag({1, 1, 2}, {1, 1, 2, 2, 3}).
% e.g. is_subbag({1, 1, 2}, {1, 2, 3}) :- fail.
%
:- pred is_subbag(bag(T)::in, bag(T)::in) is semidet.
% Compares the two bags, and returns whether the first bag is a
% subset (<), is equal (=), or is a superset (>) of the second.
% Fails if the two bags are incomparable.
%
% Examples:
% subset_compare(<, {apple, orange}, {apple, apple, orange}).
% subset_compare(=, {apple, orange}, {apple, orange}).
% subset_compare(>, {apple, apple, orange}, {apple, orange}).
% subset_compare(_, {apple, apple}, {orange, orange}) :- fail.
%
:- pred subset_compare(comparison_result::out, bag(T)::in, bag(T)::in)
is semidet.
%--------------------------------------------------%
% Perform a traversal of the bag, applying an accumulator predicate
% to each value - count pair.
%
:- pred foldl(pred(T, int, A, A), bag(T), A, A).
:- mode foldl(pred(in, in, in, out) is det, in, in, out) is det.
:- mode foldl(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
:- mode foldl(pred(in, in, in, out) is semidet, in, in, out) is semidet.
:- mode foldl(pred(in, in, mdi, muo) is semidet, in, mdi, muo) is semidet.
:- mode foldl(pred(in, in, di, uo) is semidet, in, di, uo) is semidet.
% As above, but with two accumulators.
%
:- pred foldl2(pred(T, int, A, A, B, B), bag(T), A, A, B, B).
:- mode foldl2(pred(in, in, in, out, in, out) is det, in, in, out,
in, out) is det.
:- mode foldl2(pred(in, in, in, out, mdi, muo) is det, in, in, out,
mdi, muo) is det.
:- mode foldl2(pred(in, in, in, out, di, uo) is det, in, in, out,
di, uo) is det.
:- mode foldl2(pred(in, in, in, out, in, out) is semidet, in, in, out,
in, out) is semidet.
:- mode foldl2(pred(in, in, in, out, mdi, muo) is semidet, in, in, out,
mdi, muo) is semidet.
:- mode foldl2(pred(in, in, in, out, di, uo) is semidet, in, in, out,
di, uo) is semidet.
%--------------------------------------------------%
% Return the number of values in a bag.
% If an element X is present N times, count it N times.
%
:- func count(bag(T)) = int.
% Return the number of unique values in a bag.
% Even if an element X is present N times, count it just one.
%
:- func count_unique(bag(T)) = int.
%--------------------------------------------------%
%--------------------------------------------------%
Next: benchmarking, Previous: assoc_list, Up: Top [Contents]