%--------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%--------------------------------------------------%
% Copyright (C) 2006, 2009-2012 The University of Melbourne.
% Copyright (C) 2014-2018 The Mercury team.
% This file is distributed under the terms specified in COPYING.LIB.
%--------------------------------------------------%
%
% File: tree_bitset.m.
% Author: zs, based on sparse_bitset.m by stayl.
% Stability: medium.
%
% This module provides an ADT for storing sets of non-negative integers.
% If the integers stored are closely grouped, a tree_bitset is more compact
% than the representation provided by set.m, and the operations will be much
% faster. Compared to sparse_bitset.m, the operations provided by this module
% for contains, union, intersection and difference can be expected to have
% lower asymptotic complexity (often logarithmic in the number of elements in
% the sets, rather than linear). The price for this is a representation that
% requires more memory, higher constant factors, and an additional factor
% representing the tree in the complexity of the operations that construct
% tree_bitsets. However, since the depth of the tree has a small upper bound
% for all sets of a practical size, we will fold this into the "higher
% constant factors" in the descriptions of the complexity of the individual
% operations below.
%
% All this means that using a tree_bitset in preference to a sparse_bitset
% is likely to be a good idea only when the sizes of the sets to be manipulated
% are quite big, or when worst-case performance is important.
%
% For the time being, this module can only handle items that map to nonnegative
% integers. This may change once unsigned integer operations are available.
%
%--------------------------------------------------%
:- module tree_bitset.
:- interface.
:- import_module enum.
:- import_module list.
:- import_module term.
:- use_module set.
%--------------------------------------------------%
:- type tree_bitset(T). % <= enum(T).
%--------------------------------------------------%
%
% Initial creation of sets.
%
% Return an empty set.
%
:- func init = tree_bitset(T).
% `make_singleton_set(Elem)' returns a set containing just the single
% element `Elem'.
%
:- func make_singleton_set(T) = tree_bitset(T) <= enum(T).
%--------------------------------------------------%
%
% Emptiness and singleton-ness tests.
%
:- pred empty(tree_bitset(T)).
:- mode empty(in) is semidet.
:- mode empty(out) is det.
:- pragma obsolete(pred(empty/1), [init/0, is_empty/1]).
:- pred is_empty(tree_bitset(T)::in) is semidet.
:- pred is_non_empty(tree_bitset(T)::in) is semidet.
% Is the given set a singleton, and if yes, what is the element?
%
:- pred is_singleton(tree_bitset(T)::in, T::out) is semidet <= enum(T).
%--------------------------------------------------%
%
% Membership tests.
%
% `member(X, Set)' is true iff `X' is a member of `Set'.
% Takes O(card(Set)) time for the semidet mode.
%
:- pred member(T, tree_bitset(T)) <= enum(T).
:- mode member(in, in) is semidet.
:- mode member(out, in) is nondet.
% `contains(Set, X)' is true iff `X' is a member of `Set'.
% Takes O(log(card(Set))) time.
%
:- pred contains(tree_bitset(T)::in, T::in) is semidet <= enum(T).
%--------------------------------------------------%
%
% Insertions and deletions.
%
% `insert(Set, X)' returns the union of `Set' and the set containing
% only `X'. Takes O(log(card(Set))) time and space.
%
:- func insert(tree_bitset(T), T) = tree_bitset(T) <= enum(T).
:- pred insert(T::in, tree_bitset(T)::in, tree_bitset(T)::out)
is det <= enum(T).
% `insert_new(X, Set0, Set)' returns the union of `Set' and the set
% containing only `X' is `Set0' does not contain 'X'; if it does, it fails.
% Takes O(log(card(Set))) time and space.
%
:- pred insert_new(T::in, tree_bitset(T)::in, tree_bitset(T)::out)
is semidet <= enum(T).
% `insert_list(Set, X)' returns the union of `Set' and the set containing
% only the members of `X'. Same as `union(Set, list_to_set(X))', but may be
% more efficient.
%
:- func insert_list(tree_bitset(T), list(T)) = tree_bitset(T) <= enum(T).
:- pred insert_list(list(T)::in, tree_bitset(T)::in, tree_bitset(T)::out)
is det <= enum(T).
%--------------------------------------------------%
% `delete(Set, X)' returns the difference of `Set' and the set containing
% only `X'. Takes O(card(Set)) time and space.
%
:- func delete(tree_bitset(T), T) = tree_bitset(T) <= enum(T).
:- pred delete(T::in, tree_bitset(T)::in, tree_bitset(T)::out)
is det <= enum(T).
% `delete_list(Set, X)' returns the difference of `Set' and the set
% containing only the members of `X'. Same as
% `difference(Set, list_to_set(X))', but may be more efficient.
%
:- func delete_list(tree_bitset(T), list(T)) = tree_bitset(T) <= enum(T).
:- pred delete_list(list(T)::in, tree_bitset(T)::in, tree_bitset(T)::out)
is det <= enum(T).
% `remove(X, Set0, Set)' returns in `Set' the difference of `Set0'
% and the set containing only `X', failing if `Set0' does not contain `X'.
% Takes O(log(card(Set))) time and space.
%
:- pred remove(T::in, tree_bitset(T)::in, tree_bitset(T)::out)
is semidet <= enum(T).
% `remove_list(X, Set0, Set)' returns in `Set' the difference of `Set0'
% and the set containing all the elements of `X', failing if any element
% of `X' is not in `Set0'. Same as `subset(list_to_set(X), Set0),
% difference(Set0, list_to_set(X), Set)', but may be more efficient.
%
:- pred remove_list(list(T)::in, tree_bitset(T)::in, tree_bitset(T)::out)
is semidet <= enum(T).
% `remove_leq(Set, X)' returns `Set' with all elements less than or equal
% to `X' removed. In other words, it returns the set containing all the
% elements of `Set' which are greater than `X'. Takes O(log(card(Set)))
% time and space.
%
:- func remove_leq(tree_bitset(T), T) = tree_bitset(T) <= enum(T).
% `remove_gt(Set, X)' returns `Set' with all elements greater than `X'
% removed. In other words, it returns the set containing all the elements
% of `Set' which are less than or equal to `X'. Takes O(log(card(Set)))
% time and space.
%
:- func remove_gt(tree_bitset(T), T) = tree_bitset(T) <= enum(T).
% `remove_least(Set0, X, 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'. Takes O(1) time and space.
%
:- pred remove_least(T::out, tree_bitset(T)::in, tree_bitset(T)::out)
is semidet <= enum(T).
%--------------------------------------------------%
%
% Comparisons between sets.
%
% `equal(SetA, SetB)' is true iff `SetA' and `SetB' contain the same
% elements. Takes O(min(card(SetA), card(SetB))) time.
%
:- pred equal(tree_bitset(T)::in, tree_bitset(T)::in) is semidet <= enum(T).
% `subset(Subset, Set)' is true iff `Subset' is a subset of `Set'.
% Same as `intersect(Set, Subset, Subset)', but may be more efficient.
%
:- pred subset(tree_bitset(T)::in, tree_bitset(T)::in) is semidet.
% `superset(Superset, Set)' is true iff `Superset' is a superset of `Set'.
% Same as `intersect(Superset, Set, Set)', but may be more efficient.
%
:- pred superset(tree_bitset(T)::in, tree_bitset(T)::in) is semidet.
%--------------------------------------------------%
%
% Operations on two or more sets.
%
% `union(SetA, SetB)' returns the union of `SetA' and `SetB'. The
% efficiency of the union operation is not sensitive to the argument
% ordering. Takes somewhere between O(log(card(SetA)) + log(card(SetB)))
% and O(card(SetA) + card(SetB)) time and space.
%
:- func union(tree_bitset(T), tree_bitset(T)) = tree_bitset(T).
:- pred union(tree_bitset(T)::in, tree_bitset(T)::in, tree_bitset(T)::out)
is det.
% `union_list(Sets, Set)' returns the union of all the sets in Sets.
%
:- func union_list(list(tree_bitset(T))) = tree_bitset(T).
:- pred union_list(list(tree_bitset(T))::in, tree_bitset(T)::out) is det.
% `intersect(SetA, SetB)' returns the intersection of `SetA' and `SetB'.
% The efficiency of the intersection operation is not sensitive to the
% argument ordering. Takes somewhere between
% O(log(card(SetA)) + log(card(SetB))) and O(card(SetA) + card(SetB)) time,
% and O(min(card(SetA)), card(SetB)) space.
%
:- func intersect(tree_bitset(T), tree_bitset(T)) = tree_bitset(T).
:- pred intersect(tree_bitset(T)::in, tree_bitset(T)::in, tree_bitset(T)::out)
is det.
% `intersect_list(Sets, Set)' returns the intersection of all the sets
% in Sets.
%
:- func intersect_list(list(tree_bitset(T))) = tree_bitset(T).
:- pred intersect_list(list(tree_bitset(T))::in, tree_bitset(T)::out) is det.
% `difference(SetA, SetB)' returns the set containing all the elements
% of `SetA' except those that occur in `SetB'. Takes somewhere between
% O(log(card(SetA)) + log(card(SetB))) and O(card(SetA) + card(SetB)) time,
% and O(card(SetA)) space.
%
:- func difference(tree_bitset(T), tree_bitset(T)) = tree_bitset(T).
:- pred difference(tree_bitset(T)::in, tree_bitset(T)::in, tree_bitset(T)::out)
is det.
%--------------------------------------------------%
%
% Operations that divide a set into two parts.
%
% divide(Pred, Set, InPart, OutPart):
% InPart consists of those elements of Set for which Pred succeeds;
% OutPart consists of those elements of Set for which Pred fails.
%
:- pred divide(pred(T)::in(pred(in) is semidet), tree_bitset(T)::in,
tree_bitset(T)::out, tree_bitset(T)::out) is det <= enum(T).
% 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 Set which are not in DivideBySet.
%
:- pred divide_by_set(tree_bitset(T)::in, tree_bitset(T)::in,
tree_bitset(T)::out, tree_bitset(T)::out) is det <= enum(T).
%--------------------------------------------------%
%
% Converting lists to sets.
%
% `list_to_set(List)' returns a set containing only the members of `List'.
% Takes O(length(List)) time and space.
%
:- func list_to_set(list(T)) = tree_bitset(T) <= enum(T).
:- pred list_to_set(list(T)::in, tree_bitset(T)::out) is det <= enum(T).
% `sorted_list_to_set(List)' returns a set containing only the members
% of `List'. `List' must be sorted. Takes O(length(List)) time and space.
%
:- func sorted_list_to_set(list(T)) = tree_bitset(T) <= enum(T).
:- pred sorted_list_to_set(list(T)::in, tree_bitset(T)::out) is det <= enum(T).
%--------------------------------------------------%
%
% Converting sets to lists.
%
% `to_sorted_list(Set)' returns a list containing all the members of `Set',
% in sorted order. Takes O(card(Set)) time and space.
%
:- func to_sorted_list(tree_bitset(T)) = list(T) <= enum(T).
:- pred to_sorted_list(tree_bitset(T)::in, list(T)::out) is det <= enum(T).
%--------------------------------------------------%
%
% Converting between different kinds of sets.
%
% `from_set(Set)' returns a bitset containing only the members of `Set'.
% Takes O(card(Set)) time and space.
%
:- func from_set(set.set(T)) = tree_bitset(T) <= enum(T).
% `to_sorted_list(Set)' returns a set.set containing all the members
% of `Set', in sorted order. Takes O(card(Set)) time and space.
%
:- func to_set(tree_bitset(T)) = set.set(T) <= enum(T).
%--------------------------------------------------%
%
% Counting.
%
% `count(Set)' returns the number of elements in `Set'.
% Takes O(card(Set)) time.
%
:- func count(tree_bitset(T)) = int <= enum(T).
%--------------------------------------------------%
%
% 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), tree_bitset(T)::in)
is semidet <= enum(T).
% `filter(Pred, Set) = TrueSet' returns the elements of Set for which
% Pred succeeds.
%
:- func filter(pred(T), tree_bitset(T)) = tree_bitset(T) <= enum(T).
:- mode filter(pred(in) is semidet, in) = out is det.
% `filter(Pred, Set, TrueSet, FalseSet)' returns the elements of Set
% for which Pred succeeds, and those for which it fails.
%
:- pred filter(pred(T), tree_bitset(T), tree_bitset(T), tree_bitset(T))
<= enum(T).
:- mode filter(pred(in) is semidet, in, out, out) is det.
% `foldl(Func, Set, Start)' calls Func with each element of `Set'
% (in sorted order) and an accumulator (with the initial value of `Start'),
% and returns the final value. Takes O(card(Set)) time.
%
:- func foldl(func(T, U) = U, tree_bitset(T), U) = U <= enum(T).
:- pred foldl(pred(T, U, U), tree_bitset(T), U, U) <= enum(T).
:- mode foldl(pred(in, in, out) is det, in, in, out) is det.
:- mode foldl(pred(in, mdi, muo) is det, in, mdi, muo) is det.
:- mode foldl(pred(in, di, uo) is det, in, di, uo) is det.
:- mode foldl(pred(in, in, out) is semidet, in, in, out) is semidet.
:- mode foldl(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet.
:- mode foldl(pred(in, di, uo) is semidet, in, di, uo) is semidet.
:- mode foldl(pred(in, in, out) is nondet, in, in, out) is nondet.
:- mode foldl(pred(in, mdi, muo) is nondet, in, mdi, muo) is nondet.
:- mode foldl(pred(in, di, uo) is cc_multi, in, di, uo) is cc_multi.
:- mode foldl(pred(in, in, out) is cc_multi, in, in, out) is cc_multi.
:- pred foldl2(pred(T, U, U, V, V), tree_bitset(T), U, U, V, V) <= enum(T).
:- mode foldl2(pred(in, di, uo, di, uo) is det, in, di, uo, di, uo) is det.
:- mode foldl2(pred(in, in, out, di, uo) is det, in, in, out, di, uo) is det.
:- mode foldl2(pred(in, in, out, in, out) is det, in, in, out, in, out) is det.
:- mode foldl2(pred(in, in, out, in, out) is semidet, in, in, out, in, out)
is semidet.
:- mode foldl2(pred(in, in, out, in, out) is nondet, in, in, out, in, out)
is nondet.
:- mode foldl2(pred(in, di, uo, di, uo) is cc_multi, in, di, uo, di, uo)
is cc_multi.
:- mode foldl2(pred(in, in, out, di, uo) is cc_multi, in, in, out, di, uo)
is cc_multi.
:- mode foldl2(pred(in, in, out, in, out) is cc_multi, in, in, out, in, out)
is cc_multi.
% `foldr(Func, Set, Start)' calls Func with each element of `Set'
% (in reverse sorted order) and an accumulator (with the initial value
% of `Start'), and returns the final value. Takes O(card(Set)) time.
%
:- func foldr(func(T, U) = U, tree_bitset(T), U) = U <= enum(T).
:- pred foldr(pred(T, U, U), tree_bitset(T), U, U) <= enum(T).
:- mode foldr(pred(in, di, uo) is det, in, di, uo) is det.
:- mode foldr(pred(in, in, out) is det, in, in, out) is det.
:- mode foldr(pred(in, in, out) is semidet, in, in, out) is semidet.
:- mode foldr(pred(in, in, out) is nondet, in, in, out) is nondet.
:- mode foldr(pred(in, di, uo) is cc_multi, in, di, uo) is cc_multi.
:- mode foldr(pred(in, in, out) is cc_multi, in, in, out) is cc_multi.
:- pred foldr2(pred(T, U, U, V, V), tree_bitset(T), U, U, V, V) <= enum(T).
:- mode foldr2(pred(in, di, uo, di, uo) is det, in, di, uo, di, uo) is det.
:- mode foldr2(pred(in, in, out, di, uo) is det, in, in, out, di, uo) is det.
:- mode foldr2(pred(in, in, out, in, out) is det, in, in, out, in, out) is det.
:- mode foldr2(pred(in, in, out, in, out) is semidet, in, in, out, in, out)
is semidet.
:- mode foldr2(pred(in, in, out, in, out) is nondet, in, in, out, in, out)
is nondet.
:- mode foldr2(pred(in, di, uo, di, uo) is cc_multi, in, di, uo, di, uo)
is cc_multi.
:- mode foldr2(pred(in, in, out, di, uo) is cc_multi, in, in, out, di, uo)
is cc_multi.
:- mode foldr2(pred(in, in, out, in, out) is cc_multi, in, in, out, in, out)
is cc_multi.
%--------------------------------------------------%