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

%--------------------------------------------------% % vim: ts=4 sw=4 et ft=mercury %--------------------------------------------------% % Copyright (C) 2005-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: set_tree234.m. % Author: zs. % Stability: high. % % This module implements sets using 2-3-4 trees. % %--------------------------------------------------% %--------------------------------------------------% :- module set_tree234. :- interface. :- import_module bool. :- import_module list. :- import_module set. %--------------------------------------------------% :- type set_tree234(_T). %--------------------------------------------------% % % Initial creation of sets. % % `init = Set' is true iff `Set' is an empty set. % :- func init = set_tree234(T). % `singleton_set(Elem, Set)' is true iff `Set' is the set containing just % the single element `Elem'. % :- pred singleton_set(T, set_tree234(T)). :- mode singleton_set(in, out) is det. :- mode singleton_set(out, in) is semidet. :- func make_singleton_set(T) = set_tree234(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_tree234(_T)::in) is semidet. :- pred is_empty(set_tree234(_T)::in) is semidet. :- pragma obsolete(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_tree234(T)::in) is semidet. :- pred is_non_empty(set_tree234(T)::in) is semidet. :- pragma obsolete(non_empty/1, [is_non_empty/1]). :- pred is_singleton(set_tree234(T)::in, T::out) is semidet. %--------------------------------------------------% % % Membership tests. % % `member(X, Set)' is true iff `X' is a member of `Set'. % :- pred member(T, set_tree234(T)). :- mode member(in, in) is semidet. :- mode member(out, in) is nondet. % `is_member(Set, X, Result)' returns `Result = yes' iff % `X' is a member of `Set'. % :- func is_member(set_tree234(T), T) = bool. :- pred is_member(set_tree234(T)::in, T::in, bool::out) is det. % `contains(Set, X)' is true iff `X' is a member of `Set'. % :- pred contains(set_tree234(T)::in, T::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(T, set_tree234(T)) = set_tree234(T). :- pred insert(T::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `insert_new(X, Set0, Set)' is true iff `Set0' does not contain `X', while % `Set' is the union of `Set0' and the set containing only `X'. % :- pred insert_new(T::in, set_tree234(T)::in, set_tree234(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_tree234(T)) = set_tree234(T). :- pred insert_list(list(T)::in, set_tree234(T)::in, set_tree234(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_tree234(T)) = set_tree234(T). :- pred delete(T::in, set_tree234(T)::in, set_tree234(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_tree234(T)) = set_tree234(T). :- pred delete_list(list(T)::in, set_tree234(T)::in, set_tree234(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_tree234(T)::in, set_tree234(T)::out) is semidet. :- pred det_remove(T::in, set_tree234(T)::in, set_tree234(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_tree234(T)::in, set_tree234(T)::out) is semidet. :- pred det_remove_list(list(T)::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `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_tree234(T)::in, set_tree234(T)::out) is semidet. %--------------------------------------------------% % % Comparisons between sets. % % `equal(SetA, SetB)' is true iff `SetA' and `SetB' contain the same % elements. % :- pred equal(set_tree234(T)::in, set_tree234(T)::in) is semidet. % `subset(SetA, SetB)' is true iff `SetA' is a subset of `SetB'. % :- pred subset(set_tree234(T)::in, set_tree234(T)::in) is semidet. % `superset(SetA, SetB)' is true iff `SetA' is a superset of `SetB'. % :- pred superset(set_tree234(T)::in, set_tree234(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_tree234(T), set_tree234(T)) = set_tree234(T). :- pred union(set_tree234(T)::in, set_tree234(T)::in, set_tree234(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_tree234(T))) = set_tree234(T). :- pred union_list(list(set_tree234(T))::in, set_tree234(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_tree234(set_tree234(T))) = set_tree234(T). :- pred power_union(set_tree234(set_tree234(T))::in, set_tree234(T)::out) is det. % `intersect(SetA, SetB) = Set' is true iff `Set' is the intersection of % `SetA' and `SetB'. % :- func intersect(set_tree234(T), set_tree234(T)) = set_tree234(T). :- pred intersect(set_tree234(T)::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `intersect_list(A, B)' is true iff `B' is the intersection of all the % sets in `A'. % :- func intersect_list(list(set_tree234(T))) = set_tree234(T). :- pred intersect_list(list(set_tree234(T))::in, set_tree234(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_tree234(set_tree234(T))) = set_tree234(T). :- pred power_intersect(set_tree234(set_tree234(T))::in, set_tree234(T)::out) is det. % `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_tree234(T), set_tree234(T)) = set_tree234(T). :- pred difference(set_tree234(T)::in, set_tree234(T)::in, set_tree234(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_tree234(T)::in, set_tree234(T)::in, set_tree234(T)::out, set_tree234(T)::out, set_tree234(T)::out) is det. %--------------------------------------------------% % % Operations that divide a set into two parts. % % 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. % :- pred divide(pred(T)::in(pred(in) is semidet), set_tree234(T)::in, set_tree234(T)::out, set_tree234(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_tree234(T)::in, set_tree234(T)::in, set_tree234(T)::out, set_tree234(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'. % :- func list_to_set(list(T)) = set_tree234(T). :- pred list_to_set(list(T)::in, set_tree234(T)::out) is det. :- func from_list(list(T)) = set_tree234(T). :- pred from_list(list(T)::in, set_tree234(T)::out) is det. % `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 duplicates. % :- func sorted_list_to_set(list(T)) = set_tree234(T). :- pred sorted_list_to_set(list(T)::in, set_tree234(T)::out) 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 and must not contain duplicates. % :- func rev_sorted_list_to_set(list(T)) = set_tree234(T). :- pred rev_sorted_list_to_set(list(T)::in, set_tree234(T)::out) is det. %--------------------------------------------------% % % 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. % :- func to_sorted_list(set_tree234(T)) = list(T). :- pred to_sorted_list(set_tree234(T)::in, list(T)::out) is det. %--------------------------------------------------% % % Converting between different kinds of sets. % % `from_set(Set)' returns a set_tree234 containing only % the members of `Set'. Takes O(card(Set)) time and space. % :- func from_set(set.set(T)) = set_tree234(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(set_tree234(T)) = set.set(T). %--------------------------------------------------% % % Counting. % % `count(Set, Count)' is true iff `Set' has `Count' elements. % :- func count(set_tree234(T)) = int. %--------------------------------------------------% % % 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_tree234(T)::in) is semidet. % Return the set of items for which the predicate succeeds. % :- func filter(pred(T)::in(pred(in) is semidet), set_tree234(T)::in) = (set_tree234(T)::out) is det. :- pred filter(pred(T)::in(pred(in) is semidet), set_tree234(T)::in, set_tree234(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_tree234(T)::in, set_tree234(T)::out, set_tree234(T)::out) is det. :- func filter_map(func(T1) = T2, set_tree234(T1)) = set_tree234(T2). :- mode filter_map(func(in) = out is semidet, in) = out is det. :- pred filter_map(pred(T1, T2)::in(pred(in, out) is semidet), set_tree234(T1)::in, set_tree234(T2)::out) is det. :- func map(func(T1) = T2, set_tree234(T1)) = set_tree234(T2). :- pred map(pred(T1, T2)::in(pred(in, out) is det), set_tree234(T1)::in, set_tree234(T2)::out) is det. :- func fold(func(T1, T2) = T2, set_tree234(T1), T2) = T2. :- pred fold(pred(T1, T2, T2), set_tree234(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. :- func foldl(func(T1, T2) = T2, set_tree234(T1), T2) = T2. :- pred foldl(pred(T1, T2, T2), set_tree234(T1), T2, T2). :- 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. :- pred fold2(pred(T1, T2, T2, T3, T3), set_tree234(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 foldl2(pred(T1, T2, T2, T3, T3), set_tree234(T1), T2, T2, T3, T3). :- mode foldl2(pred(in, in, out, in, out) is det, in, in, out, in, out) is det. :- mode foldl2(pred(in, in, out, mdi, muo) is det, in, in, out, mdi, muo) 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 semidet, in, in, out, in, out) is semidet. :- mode foldl2(pred(in, in, out, mdi, muo) is semidet, in, in, out, mdi, muo) is semidet. :- mode foldl2(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_tree234(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 foldl3( pred(T1, T2, T2, T3, T3, T4, T4), set_tree234(T1), T2, T2, T3, T3, T4, T4). :- mode foldl3(pred(in, in, out, in, out, in, out) is det, in, in, out, in, out, in, out) is det. :- mode foldl3(pred(in, in, out, in, out, mdi, muo) is det, in, in, out, in, out, mdi, muo) is det. :- mode foldl3(pred(in, in, out, in, out, di, uo) is det, in, in, out, in, out, di, uo) is det. :- mode foldl3(pred(in, in, out, in, out, in, out) is semidet, in, in, out, in, out, in, out) is semidet. :- mode foldl3(pred(in, in, out, in, out, mdi, muo) is semidet, in, in, out, in, out, mdi, muo) is semidet. :- mode foldl3(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_tree234(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 foldl4( pred(T1, T2, T2, T3, T3, T4, T4, T5, T5), set_tree234(T1), T2, T2, T3, T3, T4, T4, T5, T5). :- mode foldl4(pred(in, in, out, in, out, in, out, in, out) is det, in, in, out, in, out, in, out, in, out) is det. :- mode foldl4(pred(in, in, out, in, out, in, out, mdi, muo) is det, in, in, out, in, out, in, out, mdi, muo) is det. :- mode foldl4(pred(in, in, out, in, out, in, out, di, uo) is det, in, in, out, in, out, in, out, di, uo) is det. :- mode foldl4( pred(in, in, out, in, out, in, out, in, out) is semidet, in, in, out, in, out, in, out, in, out) is semidet. :- mode foldl4( pred(in, in, out, in, out, in, out, mdi, muo) is semidet, in, in, out, in, out, in, out, mdi, muo) is semidet. :- mode foldl4( 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_tree234(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 foldl5( pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6), set_tree234(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6). :- mode foldl5( 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 foldl5( 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 foldl5( 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 foldl5( 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 foldl5( 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 foldl5( 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_tree234(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. :- pred foldl6( pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6, T7, T7), set_tree234(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6, T7, T7). :- mode foldl6( 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 foldl6( 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 foldl6( 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 foldl6( 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 foldl6( 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 foldl6( 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. %--------------------------------------------------% %--------------------------------------------------%

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