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


4 bag

%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%--------------------------------------------------%
% Copyright (C) 1994-1999, 2003-2007, 2011 The University of Melbourne.
% 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: 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.
    % Abort 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.  Abort 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.
    % Abort 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).
:- func to_set_without_duplicates(bag(T)) = set(T).
:- pred to_set_without_duplicates(bag(T)::in, set(T)::out) is det.
:- pragma obsolete(to_set_without_duplicates/1).
:- pragma obsolete(to_set_without_duplicates/2).

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

    % 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: , Previous: assoc_list, Up: Top   [Contents]