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


59 set_bbbtree

%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 1995-1997, 1999-2006, 2010-2012 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: set_bbbtree.m.
% Main authors: benyi.
% Stability: low.
%
% This module implements sets using bounded balanced binary trees.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module set_bbbtree.
:- interface.

:- import_module bool.
:- import_module list.

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

:- type set_bbbtree(T).

    % `set_bbbtree.init(Set)' returns an initialized empty set.
    %
:- func set_bbbtree.init = set_bbbtree(T).
:- pred set_bbbtree.init(set_bbbtree(T)::uo) is det.

    % `set_bbbtree.empty(Set) is true iff `Set' is contains no elements.
    %
:- pred set_bbbtree.empty(set_bbbtree(T)::in) is semidet.

    % A synonym for the above.
    %
:- pred set_bbbtree.is_empty(set_bbbtree(T)::in) is semidet.

:- pred set_bbbtree.non_empty(set_bbbtree(T)::in) is semidet.

    % `set_bbbtree.count(Set, Count)' is true iff `Set' has `Count' elements.
    % i.e. `Count' is the cardinality (size) of the set.
    %
:- func set_bbbtree.count(set_bbbtree(T)) = int.
:- pred set_bbbtree.count(set_bbbtree(T)::in, int::out) is det.

    % `set_bbbtree.member(X, Set)' is true iff `X' is a member of `Set'.
    % O(lg n) for (in, in) and O(1) for (out, in).
    %
:- pred set_bbbtree.member(T, set_bbbtree(T)).
:- mode set_bbbtree.member(in, in) is semidet.
:- mode set_bbbtree.member(out, in) is nondet.

    % `set_bbbtree.is_member(X, Set, Result)' is true iff `X' is a member
    % of `Set'.
    %
:- pred set_bbbtree.is_member(T::in, set_bbbtree(T)::in, bool::out) is det.

    % `set_bbbtree.contains(Set, X)' is true iff `X' is a member of `Set'.
    % O(lg n).
    %
:- pred set_bbbtree.contains(set_bbbtree(T)::in, T::in) is semidet.

    % `set_bbbtree.least(Set, X)' is true iff `X' is smaller than all
    % the other members of `Set'.
    %
:- pred set_bbbtree.least(set_bbbtree(T), T).
:- mode set_bbbtree.least(in, out) is semidet.
:- mode set_bbbtree.least(in, in) is semidet.

    % `set_bbbtree.largest(Set, X)' is true iff `X' is larger than all
    % the other members of `Set'.
    %
:- pred set_bbbtree.largest(set_bbbtree(T), T).
:- mode set_bbbtree.largest(in, out) is semidet.
:- mode set_bbbtree.largest(in, in) is semidet.

    % `set_bbbtree.singleton_set(X, Set)' is true iff `Set' is the set
    % containing just the single element `X'.
    %
:- pred set_bbbtree.singleton_set(T, set_bbbtree(T)).
:- mode set_bbbtree.singleton_set(in, out) is det.
:- mode set_bbbtree.singleton_set(in, in) is semidet.
:- mode set_bbbtree.singleton_set(out, in) is semidet.

:- func set_bbbtree.make_singleton_set(T) = set_bbbtree(T).

:- pred set_bbbtree.is_singleton(set_bbbtree(T)::in, T::out) is semidet.

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

    % `set_bbbtree.insert(X, Set0, Set)' is true iff `Set' is the union of
    % `Set0' and the set containing only `X'.
    %
:- pred set_bbbtree.insert(T, set_bbbtree(T), set_bbbtree(T)).
:- mode set_bbbtree.insert(di, di, uo) is det.
:- mode set_bbbtree.insert(in, in, out) is det.

:- func set_bbbtree.insert(set_bbbtree(T), T) = set_bbbtree(T).

    % `set_bbbtree.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 set_bbbtree.insert_new(T::in,
    set_bbbtree(T)::in, set_bbbtree(T)::out) is semidet.

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

:- func set_bbbtree.insert_list(set_bbbtree(T), list(T)) = set_bbbtree(T).

    % `set_bbbtree.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'.
    %
:- pred set_bbbtree.delete(T, set_bbbtree(T), set_bbbtree(T)).
:- mode set_bbbtree.delete(in, di, uo) is det.
:- mode set_bbbtree.delete(in, in, out) is det.

:- func set_bbbtree.delete(set_bbbtree(T), T) = set_bbbtree(T).

    % `set_bbbtree.delete_list(Xs, Set0, Set)' is true iff `Set' is the
    % relative complement of `Set0' and the set containing only the members
    % of `Xs'.
    %
:- pred set_bbbtree.delete_list(list(T)::in,
    set_bbbtree(T)::in, set_bbbtree(T)::out) is det.

:- func set_bbbtree.delete_list(set_bbbtree(T), list(T)) = set_bbbtree(T).

    % `set_bbbtree.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 set_bbbtree.remove(T::in, set_bbbtree(T)::in, set_bbbtree(T)::out)
    is semidet.

    % `set_bbbtree.remove_list(Xs, Set0, Set)' is true iff Xs does not
    % contain any duplicates, `Set0' contains every member of `Xs',
    % and `Set' is the relative complement of `Set0' and the set
    % containing only the members of `Xs'.
    %
:- pred set_bbbtree.remove_list(list(T)::in,
    set_bbbtree(T)::in, set_bbbtree(T)::out) is semidet.

    % `set_bbbtree.remove_least(X, Set0, Set)' is true iff the union if
    % `X' and `Set' is `Set0' and `X' is smaller than all the elements of
    % `Set'.
    %
:- pred set_bbbtree.remove_least(T::out,
    set_bbbtree(T)::in, set_bbbtree(T)::out) is semidet.

    % `set_bbbtree.remove_largest(X, Set0, Set)' is true iff the union if
    % `X' and `Set' is `Set0' and `X' is larger than all the elements of
    % `Set'.
    %
:- pred set_bbbtree.remove_largest(T::out,
    set_bbbtree(T)::in, set_bbbtree(T)::out) is semidet.

    % `set_bbbtree.list_to_set(List, Set)' is true iff `Set' is the set
    % containing only the members of `List'. O(n lg n)
    %
:- pred set_bbbtree.list_to_set(list(T)::in, set_bbbtree(T)::out) is det.

:- func set_bbbtree.list_to_set(list(T)) = set_bbbtree(T).

    % A synonym for set_bbtree.list_to_set/1.
    %
:- func set_bbbtree.from_list(list(T)) = set_bbbtree(T).

    % `set_bbbtree.sorted_list_to_set(List, Set)' is true iff `Set' is the
    % set containing only the members of `List'.
    % `List' must be sorted. O(n).
    %
:- pred set_bbbtree.sorted_list_to_set(list(T)::in, set_bbbtree(T)::out)
    is det.

:- func set_bbbtree.sorted_list_to_set(list(T)) = set_bbbtree(T).

    % A synonym for set_bbbtree.sorted_list_to_set/1.
    %
:- func set_bbbtree.from_sorted_list(list(T)) = set_bbbtree(T).

    % `set_bbbtree.sorted_list_to_set_len(List, Set, N)' is true iff
    % `Set' is the set containing only the members of `List' and `N'
    % is the length of the list. If the length of the list is already known
    % then a noticeable speed improvement can be expected over
    % `set_bbbtree.sorted_list_to_set' as a significant cost involved
    % with `set_bbbtree.sorted_list_to_set' is the call to list.length.
    % `List' must be sorted. O(n).
    %
:- pred set_bbbtree.sorted_list_to_set_len(list(T)::in, set_bbbtree(T)::out,
    int::in) is det.

    % `set_bbbtree.to_sorted_list(Set, List)' is true iff `List' is the
    % list of all the members of `Set', in sorted order. O(n).
    %
:- pred set_bbbtree.to_sorted_list(set_bbbtree(T), list(T)).
:- mode set_bbbtree.to_sorted_list(di, uo) is det.
:- mode set_bbbtree.to_sorted_list(in, out) is det.

:- func set_bbbtree.to_sorted_list(set_bbbtree(T)) = list(T).

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

:- func set_bbbtree.union(set_bbbtree(T), set_bbbtree(T)) = set_bbbtree(T).

    % `set_bbbtree.union_list(Sets) = Set' is true iff `Set' is the union
    % of all the sets in `Sets'
    %
:- func set_bbbtree.union_list(list(set_bbbtree(T))) = set_bbbtree(T).

    % `set_bbbtree.power_union(Sets, Set)' is true iff `Set' is the union
    % of all the sets in `Sets'
    %
:- pred set_bbbtree.power_union(set_bbbtree(set_bbbtree(T))::in,
    set_bbbtree(T)::out) is det.

:- func set_bbbtree.power_union(set_bbbtree(set_bbbtree(T))) = set_bbbtree(T).

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

:- func set_bbbtree.intersect(set_bbbtree(T), set_bbbtree(T)) = set_bbbtree(T).

    % `set_bbbtree.power_intersect(Sets, Set) is true iff `Set' is the
    % intersection of the sets in `Sets'.
    %
:- pred set_bbbtree.power_intersect(set_bbbtree(set_bbbtree(T))::in,
    set_bbbtree(T)::out) is det.

:- func set_bbbtree.power_intersect(set_bbbtree(set_bbbtree(T)))
    = set_bbbtree(T).

    % `set_bbbtree.intersect_list(Sets) = Set is true iff `Set' is the
    % intersection of the sets in `Sets'.
    %
:- func set_bbbtree.intersect_list(list(set_bbbtree(T))) = set_bbbtree(T).

    % `set_bbtree.difference(SetA, SetB, Set)' is true iff `Set' is the
    %  set containing all the elements of `SetA' except those that
    % occur in `SetB'.
    %
:- pred set_bbbtree.difference(set_bbbtree(T)::in, set_bbbtree(T)::in,
    set_bbbtree(T)::out) is det.

:- func set_bbbtree.difference(set_bbbtree(T), set_bbbtree(T))
    = set_bbbtree(T).

    % `set_bbbtree.subset(SetA, SetB)' is true iff all the elements of
    % `SetA' are also elements of `SetB'.
    %
:- pred set_bbbtree.subset(set_bbbtree(T)::in, set_bbbtree(T)::in) is semidet.

    % `set_bbbtree.superset(SetA, SetB)' is true iff all the elements of
    % `SetB' are also elements of `SetA'.
    %
:- pred set_bbbtree.superset(set_bbbtree(T)::in, set_bbbtree(T)::in)
    is semidet.

:- func set_bbbtree.fold(func(T1, T2) = T2, set_bbbtree(T1), T2) = T2.
:- pred set_bbbtree.fold(pred(T1, T2, T2), set_bbbtree(T1), T2, T2).
:- mode set_bbbtree.fold(pred(in, in, out) is det, in, in, out) is det.
:- mode set_bbbtree.fold(pred(in, mdi, muo) is det, in, mdi, muo) is det.
:- mode set_bbbtree.fold(pred(in, di, uo) is det, in, di, uo) is det.
:- mode set_bbbtree.fold(pred(in, in, out) is semidet, in, in, out)
    is semidet.
:- mode set_bbbtree.fold(pred(in, mdi, muo) is semidet, in, mdi, muo)
    is semidet.
:- mode set_bbbtree.fold(pred(in, di, uo) is semidet, in, di, uo)
    is semidet.

:- pred set_bbbtree.fold2(pred(T1, T2, T2, T3, T3), set_bbbtree(T1),
    T2, T2, T3, T3).
:- mode set_bbbtree.fold2(pred(in, in, out, in, out) is det, in,
    in, out, in, out) is det.
:- mode set_bbbtree.fold2(pred(in, in, out, mdi, muo) is det, in,
    in, out, mdi, muo) is det.
:- mode set_bbbtree.fold2(pred(in, in, out, di, uo) is det, in,
    in, out, di, uo) is det.
:- mode set_bbbtree.fold2(pred(in, in, out, in, out) is semidet, in,
    in, out, in, out) is semidet.
:- mode set_bbbtree.fold2(pred(in, in, out, mdi, muo) is semidet, in,
    in, out, mdi, muo) is semidet.
:- mode set_bbbtree.fold2(pred(in, in, out, di, uo) is semidet, in,
    in, out, di, uo) is semidet.

:- pred set_bbbtree.fold3(pred(T1, T2, T2, T3, T3, T4, T4),
    set_bbbtree(T1), T2, T2, T3, T3, T4, T4).
:- mode set_bbbtree.fold3(pred(in, in, out, in, out, in, out) is det, in,
    in, out, in, out, in, out) is det.
:- mode set_bbbtree.fold3(pred(in, in, out, in, out, mdi, muo) is det, in,
    in, out, in, out, mdi, muo) is det.
:- mode set_bbbtree.fold3(pred(in, in, out, in, out, di, uo) is det, in,
    in, out, in, out, di, uo) is det.
:- mode set_bbbtree.fold3(pred(in, in, out, in, out, in, out) is semidet, in,
    in, out, in, out, in, out) is semidet.
:- mode set_bbbtree.fold3(pred(in, in, out, in, out, mdi, muo) is semidet, in,
    in, out, in, out, mdi, muo) is semidet.
:- mode set_bbbtree.fold3(pred(in, in, out, in, out, di, uo) is semidet, in,
    in, out, in, out, di, uo) is semidet.

:- pred set_bbbtree.fold4(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5),
    set_bbbtree(T1), T2, T2, T3, T3, T4, T4, T5, T5).
:- mode set_bbbtree.fold4(
    pred(in, in, out, in, out, in, out, in, out) is det, in,
    in, out, in, out, in, out, in, out) is det.
:- mode set_bbbtree.fold4(
    pred(in, in, out, in, out, in, out, mdi, muo) is det, in,
    in, out, in, out, in, out, mdi, muo) is det.
:- mode set_bbbtree.fold4(
    pred(in, in, out, in, out, in, out, di, uo) is det, in,
    in, out, in, out, in, out, di, uo) is det.
:- mode set_bbbtree.fold4(
    pred(in, in, out, in, out, in, out, in, out) is semidet, in,
    in, out, in, out, in, out, in, out) is semidet.
:- mode set_bbbtree.fold4(
    pred(in, in, out, in, out, in, out, mdi, muo) is semidet, in,
    in, out, in, out, in, out, mdi, muo) is semidet.
:- mode set_bbbtree.fold4(
    pred(in, in, out, in, out, in, out, di, uo) is semidet, in,
    in, out, in, out, in, out, di, uo) is semidet.

:- pred set_bbbtree.fold5(
    pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6),
    set_bbbtree(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6).
:- mode set_bbbtree.fold5(
    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 set_bbbtree.fold5(
    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 set_bbbtree.fold5(
    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 set_bbbtree.fold5(
    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 set_bbbtree.fold5(
    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 set_bbbtree.fold5(
    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.

:- pred set_bbbtree.fold6(
    pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6, T7, T7),
    set_bbbtree(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6, T7, T7).
:- mode set_bbbtree.fold6(
    pred(in, in, out, in, out, in, out, in, out, in, out, in, out) is det,
    in, in, out, in, out, in, out, in, out, in, out, in, out) is det.
:- mode set_bbbtree.fold6(
    pred(in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is det,
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is det.
:- mode set_bbbtree.fold6(
    pred(in, in, out, in, out, in, out, in, out, in, out, di, uo) is det,
    in, in, out, in, out, in, out, in, out, in, out, di, uo) is det.
:- mode set_bbbtree.fold6(
    pred(in, in, out, in, out, in, out, in, out, in, out, in, out) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, in, out) is semidet.
:- mode set_bbbtree.fold6(
    pred(in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, mdi, muo) is semidet.
:- mode set_bbbtree.fold6(
    pred(in, in, out, in, out, in, out, in, out, in, out, di, uo) is semidet,
    in, in, out, in, out, in, out, in, out, in, out, 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), set_bbbtree(T)::in)
    is semidet.

:- func set_bbbtree.map(func(T1) = T2, set_bbbtree(T1)) = set_bbbtree(T2).

:- func set_bbbtree.filter_map(func(T1) = T2, set_bbbtree(T1))
    = set_bbbtree(T2).
:- mode set_bbbtree.filter_map(func(in) = out is semidet, in) = out is det.

    % set_bbbtree.filter(Pred, Items, Trues):
    % Return the set of items for which Pred succeeds.
    %
:- pred set_bbbtree.filter(pred(T)::in(pred(in) is semidet),
    set_bbbtree(T)::in, set_bbbtree(T)::out) is det.

    % set_bbbtree.filter(Pred, Items, Trues, Falses):
    % Return the set of items for which Pred succeeds,
    % and the set for which it fails.
    %
:- pred set_bbbtree.filter(pred(T)::in(pred(in) is semidet),
    set_bbbtree(T)::in, set_bbbtree(T)::out, set_bbbtree(T)::out) is det.

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


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