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


61 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).

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

    % `empty(Set)' is true iff `Set' is an empty set.
    % `is_empty' is a synonym for `empty'.
    %
:- pred empty(set_bbbtree(T)::in) is semidet.
:- pred is_empty(set_bbbtree(T)::in) is semidet.

    % `non_empty(Set)' is true iff `Set' is not an empty set.
    % `is_non_empty' is a synonym for `non_empty'.
    %
:- pred non_empty(set_bbbtree(T)::in) is semidet.
:- pred is_non_empty(set_bbbtree(T)::in) is semidet.

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

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

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

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

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

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

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

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

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

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

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

:- func insert(set_bbbtree(T), T) = set_bbbtree(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,
    set_bbbtree(T)::in, set_bbbtree(T)::out) is semidet.

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

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

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

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

:- func delete_list(set_bbbtree(T), list(T)) = set_bbbtree(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, set_bbbtree(T)::in, set_bbbtree(T)::out)
    is semidet.

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

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

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

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

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

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

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

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

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

    % `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
    % `sorted_list_to_set' as a significant cost involved
    % with `sorted_list_to_set' is the call to list.length.
    % `List' must be sorted. O(n).
    %
:- pred sorted_list_to_set_len(list(T)::in, set_bbbtree(T)::out,
    int::in) is det.

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

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

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

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

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

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

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

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

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

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

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

    % `intersect_list(Sets) = Set is true iff `Set' is the
    % intersection of the sets in `Sets'.
    %
:- func 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 difference(set_bbbtree(T)::in, set_bbbtree(T)::in,
    set_bbbtree(T)::out) is det.

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

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

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

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

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

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

:- pred fold4(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5),
    set_bbbtree(T1), T2, T2, T3, T3, T4, T4, T5, T5).
:- mode 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 map(func(T1) = T2, set_bbbtree(T1)) = set_bbbtree(T2).

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

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

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

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


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