%--------------------------------------------------%
% vim: ts=4 sw=4 et ft=mercury
%--------------------------------------------------%
% Copyright (C) 1995-1997, 1999-2006, 2010-2012 The University of Melbourne.
% Copyright (C) 2014-2015, 2018 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% 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).

%--------------------------------------------------%
%
% Initial creation of sets.
%

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

    % `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).

%--------------------------------------------------%
%
% Emptiness and singleton-ness tests.
%

    % `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.
:- pragma obsolete(pred(empty/1), [is_empty/1]).

    % `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.
:- pragma obsolete(pred(non_empty/1), [is_non_empty/1]).

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

%--------------------------------------------------%
%
% Membership tests.
%

    % `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.

%--------------------------------------------------%
%
% Insertions and deletions.
%

    % `insert(X, Set0, Set)' is true iff `Set' is the union of
    % `Set0' and the set containing only `X'.
    %
:- func insert(set_bbbtree(T), T) = set_bbbtree(T).
:- pred insert(T, set_bbbtree(T), set_bbbtree(T)).
:- mode insert(di, di, uo) is det.
:- mode insert(in, in, 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_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'.
    %
:- func insert_list(set_bbbtree(T), list(T)) = set_bbbtree(T).
:- pred insert_list(list(T)::in,
    set_bbbtree(T)::in, set_bbbtree(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(set_bbbtree(T), T) = set_bbbtree(T).
:- pred delete(T, set_bbbtree(T), set_bbbtree(T)).
:- mode delete(in, di, uo) is det.
:- mode delete(in, in, 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(set_bbbtree(T), list(T)) = set_bbbtree(T).
:- pred delete_list(list(T)::in,
    set_bbbtree(T)::in, set_bbbtree(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'.
    %
    % The det_remove version throws an exception instead of failing.
    %
:- pred remove(T::in, set_bbbtree(T)::in, set_bbbtree(T)::out) is semidet.
:- pred det_remove(T::in, set_bbbtree(T)::in, set_bbbtree(T)::out) is det.

    % `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'.
    %
    % The det_remove_list version throws an exception instead of failing.
    %
:- pred remove_list(list(T)::in,
    set_bbbtree(T)::in, set_bbbtree(T)::out) is semidet.
:- pred det_remove_list(list(T)::in,
    set_bbbtree(T)::in, set_bbbtree(T)::out) is det.

    % `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.

%--------------------------------------------------%
%
% Comparisons between sets.
%

    % `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.

    % `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.

%--------------------------------------------------%
%
% Operations on two or more sets.
%

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

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

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

    % `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).

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

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

%--------------------------------------------------%
%
% Converting lists to sets.
%

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

    % 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 in ascending order, and must not contain
    % any duplicates. O(n).
    %
    % The sorted_list_to_set_len version allows the caller to provide
    % the length of List, which avoids the cost of computing it again.
    % This version will throw an exception if the length is incorrect.
    %
:- func sorted_list_to_set(list(T)) = set_bbbtree(T).
:- pred sorted_list_to_set(list(T)::in, set_bbbtree(T)::out) is det.
:- pred sorted_list_to_set_len(list(T)::in, set_bbbtree(T)::out,
    int::in) is det.

    % `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_bbbtree(T).
:- pred rev_sorted_list_to_set(list(T)::in, set_bbbtree(T)::out) is det.
:- pred rev_sorted_list_to_set_len(list(T)::in, set_bbbtree(T)::out,
    int::in) is det.

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

%--------------------------------------------------%
%
% Converting sets to lists.
%

    % `to_sorted_list(Set, List)' is true iff `List' is the
    % list of all the members of `Set', in sorted order. O(n).
    %
:- func to_sorted_list(set_bbbtree(T)) = list(T).
:- 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.

%--------------------------------------------------%
%
% Counting.
%

    % `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.

%--------------------------------------------------%
%
% Standard higher order functions on collections.
%

    % 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.

    % 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.

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

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

:- 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.

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