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. % 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_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). % `set_tree234.init = Set' is true iff `Set' is an empty set. % :- func set_tree234.init = set_tree234(T). % `set_tree234.singleton_set(Elem, Set)' is true iff `Set' is the set % containing just the single element `Elem'. % :- pred set_tree234.singleton_set(T, set_tree234(T)). :- mode set_tree234.singleton_set(in, out) is det. :- mode set_tree234.singleton_set(out, in) is semidet. :- func set_tree234.make_singleton_set(T) = set_tree234(T). :- pred set_tree234.is_singleton(set_tree234(T)::in, T::out) is semidet. % `set_tree234.empty(Set)' is true iff `Set' is an empty set. % :- pred set_tree234.empty(set_tree234(_T)::in) is semidet. % A synonym for the above. % :- pred set_tree234.is_empty(set_tree234(_T)::in) is semidet. :- pred set_tree234.non_empty(set_tree234(T)::in) is semidet. :- pred set_tree234.is_non_empty(set_tree234(T)::in) is semidet. % `set_tree234.member(X, Set)' is true iff `X' is a member of `Set'. % :- pred set_tree234.member(T, set_tree234(T)). :- mode set_tree234.member(in, in) is semidet. :- mode set_tree234.member(out, in) is nondet. % `set_tree234.is_member(Set, X, Result)' returns % `Result = yes' iff `X' is a member of `Set'. % :- func set_tree234.is_member(set_tree234(T), T) = bool. :- pred set_tree234.is_member(set_tree234(T)::in, T::in, bool::out) is det. % `set_tree234.contains(Set, X)' is true iff `X' is a member of `Set'. % :- pred set_tree234.contains(set_tree234(T)::in, T::in) is semidet. % `set_tree234.list_to_set(List) = Set' is true iff `Set' is the set % containing only the members of `List'. % :- func set_tree234.list_to_set(list(T)) = set_tree234(T). :- pred set_tree234.list_to_set(list(T)::in, set_tree234(T)::out) is det. :- func set_tree234.from_list(list(T)) = set_tree234(T). :- pred set_tree234.from_list(list(T)::in, set_tree234(T)::out) is det. % `set_tree234.sorted_list_to_set(List) = Set' is true iff `Set' is % the set containing only the members of `List'. `List' must be sorted. % :- func set_tree234.sorted_list_to_set(list(T)) = set_tree234(T). :- pred set_tree234.sorted_list_to_set(list(T)::in, set_tree234(T)::out) is det. % `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). % `set_tree234.to_sorted_list(Set) = List' is true iff `List' is the % list of all the members of `Set', in sorted order. % :- func set_tree234.to_sorted_list(set_tree234(T)) = list(T). :- pred set_tree234.to_sorted_list(set_tree234(T)::in, list(T)::out) is det. % `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). % `set_tree234.equal(SetA, SetB)' is true iff % `SetA' and `SetB' contain the same elements. % :- pred set_tree234.equal(set_tree234(T)::in, set_tree234(T)::in) is semidet. % `set_tree234.subset(SetA, SetB)' is true iff `SetA' is a subset of % `SetB'. % :- pred set_tree234.subset(set_tree234(T)::in, set_tree234(T)::in) is semidet. % `set_tree234.superset(SetA, SetB)' is true iff `SetA' is a % superset of `SetB'. % :- pred set_tree234.superset(set_tree234(T)::in, set_tree234(T)::in) is semidet. % `set_tree234.insert(X, Set0, Set)' is true iff `Set' is the union % of `Set0' and the set containing only `X'. % :- func set_tree234.insert(T, set_tree234(T)) = set_tree234(T). :- pred set_tree234.insert(T::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `set_tree234.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 set_tree234.insert_new(T::in, set_tree234(T)::in, set_tree234(T)::out) is semidet. % `set_tree234.insert_list(Xs, Set0, Set)' is true iff `Set' is the % union of `Set0' and the set containing only the members of `Xs'. % :- func set_tree234.insert_list(list(T), set_tree234(T)) = set_tree234(T). :- pred set_tree234.insert_list(list(T)::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `set_tree234.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 set_tree234.delete(T, set_tree234(T)) = set_tree234(T). :- pred set_tree234.delete(T::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `set_tree234.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 set_tree234.delete_list(list(T), set_tree234(T)) = set_tree234(T). :- pred set_tree234.delete_list(list(T)::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `set_tree234.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 set_tree234.remove(T::in, set_tree234(T)::in, set_tree234(T)::out) is semidet. % `set_tree234.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 set_tree234.remove_list(list(T)::in, set_tree234(T)::in, set_tree234(T)::out) is semidet. % `set_tree234.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 set_tree234.remove_least(T::out, set_tree234(T)::in, set_tree234(T)::out) is semidet. % `set_tree234.union(SetA, SetB) = Set' is true iff `Set' is the union % of `SetA' and `SetB'. % :- func set_tree234.union(set_tree234(T), set_tree234(T)) = set_tree234(T). :- pred set_tree234.union(set_tree234(T)::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `set_tree234.union_list(A, B)' is true iff `B' is the union of % all the sets in `A' % :- func set_tree234.union_list(list(set_tree234(T))) = set_tree234(T). :- pred set_tree234.union_list(list(set_tree234(T))::in, set_tree234(T)::out) is det. % `set_tree234.power_union(A) = B' is true iff `B' is the union of % all the sets in `A' % :- func set_tree234.power_union(set_tree234(set_tree234(T))) = set_tree234(T). :- pred set_tree234.power_union(set_tree234(set_tree234(T))::in, set_tree234(T)::out) is det. % `set_tree234.intersect(SetA, SetB) = Set' is true iff `Set' is the % intersection of `SetA' and `SetB'. % :- func set_tree234.intersect(set_tree234(T), set_tree234(T)) = set_tree234(T). :- pred set_tree234.intersect(set_tree234(T)::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `set_tree234.power_intersect(A, B)' is true iff `B' is the % intersection of all the sets in `A'. % :- func set_tree234.power_intersect(set_tree234(set_tree234(T))) = set_tree234(T). :- pred set_tree234.power_intersect(set_tree234(set_tree234(T))::in, set_tree234(T)::out) is det. % `set_tree234.intersect_list(A, B)' is true iff `B' is the % intersection of all the sets in `A'. % :- func set_tree234.intersect_list(list(set_tree234(T))) = set_tree234(T). :- pred set_tree234.intersect_list(list(set_tree234(T))::in, set_tree234(T)::out) is det. % `set_tree234.difference(SetA, SetB, Set)' is true iff `Set' is the % set containing all the elements of `SetA' except those that % occur in `SetB'. % :- func set_tree234.difference(set_tree234(T), set_tree234(T)) = set_tree234(T). :- pred set_tree234.difference(set_tree234(T)::in, set_tree234(T)::in, set_tree234(T)::out) is det. % `set_tree234.count(Set, Count)' is true iff `Set' has % `Count' elements. % :- func set_tree234.count(set_tree234(T)) = int. :- func set_tree234.map(func(T1) = T2, set_tree234(T1)) = set_tree234(T2). :- pred set_tree234.map(pred(T1, T2)::in(pred(in, out) is det), set_tree234(T1)::in, set_tree234(T2)::out) is det. :- pred set_tree234.filter_map(pred(T1, T2)::in(pred(in, out) is semidet), set_tree234(T1)::in, set_tree234(T2)::out) is det. :- func set_tree234.filter_map(func(T1) = T2, set_tree234(T1)) = set_tree234(T2). :- mode set_tree234.filter_map(func(in) = out is semidet, in) = out is det. :- func set_tree234.fold(func(T1, T2) = T2, set_tree234(T1), T2) = T2. :- pred set_tree234.fold(pred(T1, T2, T2), set_tree234(T1), T2, T2). :- mode set_tree234.fold(pred(in, in, out) is det, in, in, out) is det. :- mode set_tree234.fold(pred(in, mdi, muo) is det, in, mdi, muo) is det. :- mode set_tree234.fold(pred(in, di, uo) is det, in, di, uo) is det. :- mode set_tree234.fold(pred(in, in, out) is semidet, in, in, out) is semidet. :- mode set_tree234.fold(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet. :- mode set_tree234.fold(pred(in, di, uo) is semidet, in, di, uo) is semidet. :- func set_tree234.foldl(func(T1, T2) = T2, set_tree234(T1), T2) = T2. :- pred set_tree234.foldl(pred(T1, T2, T2), set_tree234(T1), T2, T2). :- mode set_tree234.foldl(pred(in, in, out) is det, in, in, out) is det. :- mode set_tree234.foldl(pred(in, mdi, muo) is det, in, mdi, muo) is det. :- mode set_tree234.foldl(pred(in, di, uo) is det, in, di, uo) is det. :- mode set_tree234.foldl(pred(in, in, out) is semidet, in, in, out) is semidet. :- mode set_tree234.foldl(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet. :- mode set_tree234.foldl(pred(in, di, uo) is semidet, in, di, uo) is semidet. :- pred set_tree234.fold2(pred(T1, T2, T2, T3, T3), set_tree234(T1), T2, T2, T3, T3). :- mode set_tree234.fold2(pred(in, in, out, in, out) is det, in, in, out, in, out) is det. :- mode set_tree234.fold2(pred(in, in, out, mdi, muo) is det, in, in, out, mdi, muo) is det. :- mode set_tree234.fold2(pred(in, in, out, di, uo) is det, in, in, out, di, uo) is det. :- mode set_tree234.fold2(pred(in, in, out, in, out) is semidet, in, in, out, in, out) is semidet. :- mode set_tree234.fold2(pred(in, in, out, mdi, muo) is semidet, in, in, out, mdi, muo) is semidet. :- mode set_tree234.fold2(pred(in, in, out, di, uo) is semidet, in, in, out, di, uo) is semidet. :- pred set_tree234.foldl2(pred(T1, T2, T2, T3, T3), set_tree234(T1), T2, T2, T3, T3). :- mode set_tree234.foldl2(pred(in, in, out, in, out) is det, in, in, out, in, out) is det. :- mode set_tree234.foldl2(pred(in, in, out, mdi, muo) is det, in, in, out, mdi, muo) is det. :- mode set_tree234.foldl2(pred(in, in, out, di, uo) is det, in, in, out, di, uo) is det. :- mode set_tree234.foldl2(pred(in, in, out, in, out) is semidet, in, in, out, in, out) is semidet. :- mode set_tree234.foldl2(pred(in, in, out, mdi, muo) is semidet, in, in, out, mdi, muo) is semidet. :- mode set_tree234.foldl2(pred(in, in, out, di, uo) is semidet, in, in, out, di, uo) is semidet. :- pred set_tree234.fold3( pred(T1, T2, T2, T3, T3, T4, T4), set_tree234(T1), T2, T2, T3, T3, T4, T4). :- mode set_tree234.fold3(pred(in, in, out, in, out, in, out) is det, in, in, out, in, out, in, out) is det. :- mode set_tree234.fold3(pred(in, in, out, in, out, mdi, muo) is det, in, in, out, in, out, mdi, muo) is det. :- mode set_tree234.fold3(pred(in, in, out, in, out, di, uo) is det, in, in, out, in, out, di, uo) is det. :- mode set_tree234.fold3(pred(in, in, out, in, out, in, out) is semidet, in, in, out, in, out, in, out) is semidet. :- mode set_tree234.fold3(pred(in, in, out, in, out, mdi, muo) is semidet, in, in, out, in, out, mdi, muo) is semidet. :- mode set_tree234.fold3(pred(in, in, out, in, out, di, uo) is semidet, in, in, out, in, out, di, uo) is semidet. :- pred set_tree234.foldl3( pred(T1, T2, T2, T3, T3, T4, T4), set_tree234(T1), T2, T2, T3, T3, T4, T4). :- mode set_tree234.foldl3(pred(in, in, out, in, out, in, out) is det, in, in, out, in, out, in, out) is det. :- mode set_tree234.foldl3(pred(in, in, out, in, out, mdi, muo) is det, in, in, out, in, out, mdi, muo) is det. :- mode set_tree234.foldl3(pred(in, in, out, in, out, di, uo) is det, in, in, out, in, out, di, uo) is det. :- mode set_tree234.foldl3(pred(in, in, out, in, out, in, out) is semidet, in, in, out, in, out, in, out) is semidet. :- mode set_tree234.foldl3(pred(in, in, out, in, out, mdi, muo) is semidet, in, in, out, in, out, mdi, muo) is semidet. :- mode set_tree234.foldl3(pred(in, in, out, in, out, di, uo) is semidet, in, in, out, in, out, di, uo) is semidet. :- pred set_tree234.fold4( pred(T1, T2, T2, T3, T3, T4, T4, T5, T5), set_tree234(T1), T2, T2, T3, T3, T4, T4, T5, T5). :- mode set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.foldl4( pred(T1, T2, T2, T3, T3, T4, T4, T5, T5), set_tree234(T1), T2, T2, T3, T3, T4, T4, T5, T5). :- mode set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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 set_tree234.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. % all_true(Pred, Set) succeeds iff Pred(Element) succeeds % for all the elements of Set. % :- pred set_tree234.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 set_tree234.filter(pred(T)::in(pred(in) is semidet), set_tree234(T)::in) = (set_tree234(T)::out) is det. :- pred set_tree234.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 set_tree234.filter(pred(T)::in(pred(in) is semidet), set_tree234(T)::in, set_tree234(T)::out, set_tree234(T)::out) is det. % set_tree234.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 set_tree234.divide(pred(T)::in(pred(in) is semidet), set_tree234(T)::in, set_tree234(T)::out, set_tree234(T)::out) is det. % set_tree234.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 set_tree234.divide_by_set(set_tree234(T)::in, set_tree234(T)::in, set_tree234(T)::out, set_tree234(T)::out) is det. %--------------------------------------------------% %--------------------------------------------------%

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