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


62 set_ctree234

%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 2005-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_ctree234.m.
% Author: zs.
% Stability: high.
%
% This module implements sets using 2-3-4 trees extended with element counts.
% This representation has higher constant factors for most operations than
% ordered lists, but it has much better worst-case complexity, and is likely
% to be faster for large sets. Specifically,
%
% - the cost of lookups is only logarithmic in the size of the set, not linear;
%
% - for operations that are intrinsically linear in the size of one input
%   operand or the other, the counts allow us to choose to be linear in the
%   size of the smaller set.
%
%--------------------------------------------------%
%--------------------------------------------------%

:- module set_ctree234.
:- interface.

:- import_module bool.
:- import_module list.

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

:- type set_ctree234(_T).

    % `init = Set' is true iff `Set' is an empty set.
    %
:- func init = set_ctree234(T).

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

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

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

    % `empty(Set)' is true iff `Set' is an empty set.
    % `is_empty' is a synonym for `empty'.
    %
:- pred empty(set_ctree234(_T)::in) is semidet.
:- pred is_empty(set_ctree234(_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_ctree234(T)::in) is semidet.
:- pred is_non_empty(set_ctree234(T)::in) is semidet.

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

    % `one_member(Set, X)' is true iff `X' is a member of `Set'.
    %
:- pred one_member(set_ctree234(T)::in, T::out) is nondet.

    % `is_member(Set, X, Result)' returns `Result = yes' iff
    % `X' is a member of `Set'.
    %
:- func is_member(set_ctree234(T), T) = bool.
:- pred is_member(set_ctree234(T)::in, T::in, bool::out) is det.

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

    % `list_to_set(List) = Set' is true iff `Set' is the set
    % containing only the members of `List'.
    %
    % `from_list' is a synonym for `list_to_set'.
    %
:- func list_to_set(list(T)) = set_ctree234(T).
:- func from_list(list(T)) = set_ctree234(T).

    % `sorted_list_to_set(List) = Set' is true iff `Set' is the set
    % containing only the members of `List'. `List' must be sorted
    % in ascending order.
    %
:- func sorted_list_to_set(list(T)) = set_ctree234(T).

    % `rev_sorted_list_to_set(List) = Set' is true iff `Set' is the set
    % containing only the members of `List'. `List' must be sorted
    % in descending order.
    %
:- func rev_sorted_list_to_set(list(T)) = set_ctree234(T).

    % `to_sorted_list(Set) = List' is true iff `List' is the list
    % of all the members of `Set', in sorted order.
    %
:- func to_sorted_list(set_ctree234(T)) = list(T).

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

    % `subset(SetA, SetB)' is true iff `SetA' is a subset of `SetB'.
    %
:- pred subset(set_ctree234(T)::in, set_ctree234(T)::in) is semidet.

    % `superset(SetA, SetB)' is true iff `SetA' is a superset of `SetB'.
    %
:- pred superset(set_ctree234(T)::in, set_ctree234(T)::in) is semidet.

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

    % `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_ctree234(T)::in, set_ctree234(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'.
    %
:- func insert_list(list(T), set_ctree234(T)) = set_ctree234(T).
:- pred insert_list(list(T)::in, set_ctree234(T)::in, set_ctree234(T)::out)
    is det.

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

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

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

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

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

    % `union_list(A, B)' is true iff `B' is the union of
    % all the sets in `A'
    %
:- func union_list(list(set_ctree234(T))) = set_ctree234(T).
:- pred union_list(list(set_ctree234(T))::in,
    set_ctree234(T)::out) is det.

    % `power_union(A) = B' is true iff `B' is the union of all the sets in `A'.
    %
:- func power_union(set_ctree234(set_ctree234(T))) = set_ctree234(T).
:- pred power_union(set_ctree234(set_ctree234(T))::in,
    set_ctree234(T)::out) is det.

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

    % `power_intersect(A, B)' is true iff `B' is the intersection
    % of all the sets in `A'.
    %
:- func power_intersect(set_ctree234(set_ctree234(T))) = set_ctree234(T).

    % `intersect_list(A) = B' is true iff `B' is the intersection
    % of all the sets in `A'.
    %
:- func intersect_list(list(set_ctree234(T))) = set_ctree234(T).

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

    % `count(Set, Count)' is true iff `Set' has `Count' elements.
    %
:- func count(set_ctree234(T)) = int.

:- func map(func(T1) = T2, set_ctree234(T1)) = set_ctree234(T2).
:- pred map(pred(T1, T2)::in(pred(in, out) is det),
    set_ctree234(T1)::in, set_ctree234(T2)::out) is det.

:- pred filter_map(pred(T1, T2)::in(pred(in, out) is semidet),
    set_ctree234(T1)::in, set_ctree234(T2)::out) is det.

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

:- func fold(func(T1, T2) = T2, set_ctree234(T1), T2) = T2.
:- pred fold(pred(T1, T2, T2), set_ctree234(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_ctree234(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_ctree234(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_ctree234(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_ctree234(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_ctree234(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_ctree234(T)::in) is semidet.

    % Return the set of items for which the predicate succeeds.
    %
:- pred filter(pred(T)::in(pred(in) is semidet),
    set_ctree234(T)::in, set_ctree234(T)::out) is det.

    % Return the set of items for which the predicate succeeds,
    % and the set for which it fails.
    %
:- pred filter(pred(T)::in(pred(in) is semidet),
    set_ctree234(T)::in, set_ctree234(T)::out, set_ctree234(T)::out) is det.

    % divide(Pred, Set, TruePart, FalsePart):
    % TruePart consists of those elements of Set for which Pred succeeds;
    % FalsePart consists of those elements of Set for which Pred fails.
    % NOTE: This is the same as filter/4.
    %
:- pred divide(pred(T)::in(pred(in) is semidet),
    set_ctree234(T)::in, set_ctree234(T)::out, set_ctree234(T)::out) is det.

    % 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 which are
    % not in DivideBySet.
    %
:- pred divide_by_set(set_ctree234(T)::in, set_ctree234(T)::in,
    set_ctree234(T)::out, set_ctree234(T)::out) is det.

    % intersection_and_differences(SetA, SetB, InAandB, OnlyInA, OnlyInB):
    % Given SetA and SetB, return the elements that occur in both sets,
    % and those that occur only in one or the other.
    %
:- pred intersection_and_differences(set_ctree234(T)::in, set_ctree234(T)::in,
    set_ctree234(T)::out, set_ctree234(T)::out, set_ctree234(T)::out) is det.

:- pred verify_depths(set_ctree234(T)::in, list(int)::out) is det.

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


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