This is mercury_library.info, produced by makeinfo version 4.11 from
library.texi_pp.

INFO-DIR-SECTION The Mercury Programming Language
START-INFO-DIR-ENTRY
* Mercury Library: (mercury_library).  The Mercury Library Reference Manual.
END-INFO-DIR-ENTRY

   This file documents the Mercury standard library, version 11.07.

   Copyright (C) 1995-1997,1999-2011 The University of Melbourne.

   Permission is granted to make and distribute verbatim copies of this
manual provided the copyright notice and this permission notice are
preserved on all copies.

   Permission is granted to copy and distribute modified versions of
this manual under the conditions for verbatim copying, provided also
that the entire resulting derived work is distributed under the terms
of a permission notice identical to this one.

   Permission is granted to copy and distribute translations of this
manual into another language, under the above conditions for modified
versions.


File: mercury_library.info,  Node: rbtree,  Next: relation,  Prev: rational,  Up: Top

56 rbtree
*********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 1995-2000, 2003-2007, 2011 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: rbtree.m.
     % Main author: petdr.
     % Stability: medium.
     %
     % Contains an implementation of red black trees.
     %
     % *** Exit conditions of main predicates ***
     % insert:
     %   fails if key already in tree.
     % update:
     %   changes value of key already in tree.  fails if key doesn't exist.
     % transform_value:
     %   looks up an existing value in the tree, applies a transformation to the
     %   value and then updates the value.  fails if the key doesn't exist.
     % set:
     %   inserts or updates. Never fails.
     %
     % insert_duplicate:
     %   inserts duplicate keys into the tree, never fails.  Search doesn't
     %   yet support looking for duplicates.
     %
     % delete:
     %   deletes a node from the tree if it exists.
     % remove:
     %   fails if node to remove doesn't exist in the tree.
     %
     % lookup:
     %   Aborts program if key looked up doesn't exist.
     % search:
     %   Fails if key looked up doesn't exist.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module rbtree.
     :- interface.

     :- import_module assoc_list.
     :- import_module list.

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

     :- type rbtree(Key, Value).

         % Initialise the data structure.
         %
     :- func rbtree.init = rbtree(K, V).
     :- pred rbtree.init(rbtree(K, V)::uo) is det.

         % Initialise an rbtree containing the given key-value pair.
         %
     :- func rbtree.singleton(K, V) = rbtree(K, V).

         % Check whether a tree is empty.
         %
     :- pred rbtree.is_empty(rbtree(K, V)::in) is semidet.

         % Inserts a new key-value pair into the tree.
         % Fails if key already in the tree.
         %
     :- pred rbtree.insert(K::in, V::in, rbtree(K, V)::in, rbtree(K, V)::out)
         is semidet.

         % Updates the value associated with a key.
         % Fails if the key does not exist.
         %
     :- pred rbtree.update(K::in, V::in, rbtree(K, V)::in, rbtree(K, V)::out)
         is semidet.

         % Update the value at the given key by applying the supplied
         % transformation to it.  Fails if the key is not found.  This is faster
         % than first searching for the value and then updating it.
         %
     :- pred rbtree.transform_value(pred(V, V)::in(pred(in, out) is det), K::in,
         rbtree(K, V)::in, rbtree(K, V)::out) is semidet.

         % Sets a value regardless of whether key exists or not.
         %
     :- func rbtree.set(rbtree(K, V), K, V) = rbtree(K, V).
     :- pred rbtree.set(K::in, V::in, rbtree(K, V)::in, rbtree(K, V)::out) is det.

         % Insert a duplicate key into the tree.
         %
     :- func rbtree.insert_duplicate(rbtree(K, V), K, V) = rbtree(K, V).
     :- pred rbtree.insert_duplicate(K::in, V::in,
         rbtree(K, V)::in, rbtree(K, V)::out) is det.

     :- pred rbtree.member(rbtree(K, V)::in, K::out, V::out) is nondet.

         % Search for a key-value pair using the key.
         % Fails if the key does not exist.
         %
     :- pred rbtree.search(rbtree(K, V)::in, K::in, V::out) is semidet.

         % Lookup the value associated with a key.
         % Throws an exception if the key does not exist.
         %
     :- func rbtree.lookup(rbtree(K, V), K) = V.
     :- pred rbtree.lookup(rbtree(K, V)::in, K::in, V::out) is det.

         % Search for a key-value pair using the key.  If there is no entry
         % for the given key, returns the pair for the next lower key instead.
         % Fails if there is no key with the given or lower value.
         %
     :- pred rbtree.lower_bound_search(rbtree(K, V)::in, K::in, K::out, V::out)
         is semidet.

         % Search for a key-value pair using the key.  If there is no entry
         % for the given key, returns the pair for the next lower key instead.
         % Throws an exception if there is no key with the given or lower value.
         %
     :- pred rbtree.lower_bound_lookup(rbtree(K, V)::in, K::in, K::out, V::out)
         is det.

         % Search for a key-value pair using the key.  If there is no entry
         % for the given key, returns the pair for the next higher key instead.
         % Fails if there is no key with the given or higher value.
         %
     :- pred rbtree.upper_bound_search(rbtree(K, V)::in, K::in, K::out, V::out)
         is semidet.

         % Search for a key-value pair using the key.  If there is no entry
         % for the given key, returns the pair for the next higher key instead.
         % Throws an exception if there is no key with the given or higher value.
         %
     :- pred rbtree.upper_bound_lookup(rbtree(K, V)::in, K::in, K::out, V::out)
         is det.

         % Delete the key-value pair associated with a key.
         % Does nothing if the key does not exist.
         %
     :- func rbtree.delete(rbtree(K, V), K) = rbtree(K, V).
     :- pred rbtree.delete(K::in, rbtree(K, V)::in, rbtree(K, V)::out) is det.

         % Remove the key-value pair associated with a key.
         % Fails if the key does not exist.
         %
     :- pred rbtree.remove(K::in, V::out, rbtree(K, V)::in, rbtree(K, V)::out)
         is semidet.

         % Deletes the node with the minimum key from the tree,
         % and returns the key and value fields.
         %
     :- pred rbtree.remove_smallest(K::out, V::out,
         rbtree(K, V)::in, rbtree(K, V)::out) is semidet.

         % Deletes the node with the maximum key from the tree,
         % and returns the key and value fields.
         %
     :- pred rbtree.remove_largest(K::out, V::out,
         rbtree(K, V)::in, rbtree(K, V)::out) is semidet.

         % Returns an in-order list of all the keys in the rbtree.
         %
     :- func rbtree.keys(rbtree(K, V)) = list(K).
     :- pred rbtree.keys(rbtree(K, V)::in, list(K)::out) is det.

         % Returns a list of values such that the keys associated with the
         % values are in-order.
         %
     :- func rbtree.values(rbtree(K, V)) = list(V).
     :- pred rbtree.values(rbtree(K, V)::in, list(V)::out) is det.

         % Count the number of elements in the tree.
         %
     :- func rbtree.count(rbtree(K, V)) = int.
     :- pred rbtree.count(rbtree(K, V)::in, int::out) is det.

     :- func rbtree.assoc_list_to_rbtree(assoc_list(K, V)) = rbtree(K, V).
     :- pred rbtree.assoc_list_to_rbtree(assoc_list(K, V)::in, rbtree(K, V)::out)
         is det.

     :- func rbtree.from_assoc_list(assoc_list(K, V)) = rbtree(K, V).

     :- func rbtree.rbtree_to_assoc_list(rbtree(K, V)) = assoc_list(K, V).
     :- pred rbtree.rbtree_to_assoc_list(rbtree(K, V)::in, assoc_list(K, V)::out)
         is det.

     :- func rbtree.to_assoc_list(rbtree(K, V)) = assoc_list(K, V).

     :- func rbtree.foldl(func(K, V, T) = T, rbtree(K, V), T) = T.
     :- pred rbtree.foldl(pred(K, V, T, T), rbtree(K, V), T, T).
     :- mode rbtree.foldl(pred(in, in, in, out) is det, in, in, out) is det.
     :- mode rbtree.foldl(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
     :- mode rbtree.foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
     :- mode rbtree.foldl(pred(in, in, in, out) is semidet, in, in, out)
         is semidet.
     :- mode rbtree.foldl(pred(in, in, mdi, muo) is semidet, in, mdi, muo)
         is semidet.
     :- mode rbtree.foldl(pred(in, in, di, uo) is semidet, in, di, uo)
         is semidet.

     :- pred rbtree.foldl2(pred(K, V, T, T, U, U), rbtree(K, V), T, T, U, U).
     :- mode rbtree.foldl2(pred(in, in, in, out, in, out) is det,
         in, in, out, in, out) is det.
     :- mode rbtree.foldl2(pred(in, in, in, out, mdi, muo) is det,
         in, in, out, mdi, muo) is det.
     :- mode rbtree.foldl2(pred(in, in, in, out, di, uo) is det,
         in, in, out, di, uo) is det.
     :- mode rbtree.foldl2(pred(in, in, di, uo, di, uo) is det,
         in, di, uo, di, uo) is det.
     :- mode rbtree.foldl2(pred(in, in, in, out, in, out) is semidet,
         in, in, out, in, out) is semidet.
     :- mode rbtree.foldl2(pred(in, in, in, out, mdi, muo) is semidet,
         in, in, out, mdi, muo) is semidet.
     :- mode rbtree.foldl2(pred(in, in, in, out, di, uo) is semidet,
         in, in, out, di, uo) is semidet.

     :- pred rbtree.foldl3(pred(K, V, T, T, U, U, W, W), rbtree(K, V),
         T, T, U, U, W, W).
     :- mode rbtree.foldl3(pred(in, in, in, out, in, out, in, out) is det,
         in, in, out, in, out, in, out) is det.
     :- mode rbtree.foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
         in, in, out, in, out, in, out) is semidet.
     :- mode rbtree.foldl3(pred(in, in, in, out, in, out, di, uo) is det,
         in, in, out, in, out, di, uo) is det.
     :- mode rbtree.foldl3(pred(in, in, in, out, di, uo, di, uo) is det,
         in, in, out, di, uo, di, uo) is det.
     :- mode rbtree.foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
         in, di, uo, di, uo, di, uo) is det.

     :- func rbtree.map_values(func(K, V) = W, rbtree(K, V)) = rbtree(K, W).
     :- pred rbtree.map_values(pred(K, V, W), rbtree(K, V), rbtree(K, W)).
     :- mode rbtree.map_values(pred(in, in, out) is det, in, out) is det.
     :- mode rbtree.map_values(pred(in, in, out) is semidet, in, out) is semidet.

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


File: mercury_library.info,  Node: relation,  Next: require,  Prev: rbtree,  Up: Top

57 relation
***********

     %--------------------------------------------------%
     % THIS FILE IS NO LONGER USED.
     %--------------------------------------------------%


File: mercury_library.info,  Node: require,  Next: rtree,  Prev: relation,  Up: Top

58 require
**********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 1993-1999, 2003, 2005-2006, 2010-2011 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: require.m.
     % Main author: fjh.
     % Stability: medium to high.
     %
     % This module provides features similar to <assert.h> in C.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module require.
     :- interface.

         % error(Message):
         %
         % Throw a `software_error(Message)' exception.
         % This will normally cause execution to abort with an error message.
         %
     :- pred error(string::in) is erroneous.

         % func_error(Message):
         %
         % An expression that results in a `software_error(Message)'
         % exception being thrown.
         %
     :- func func_error(string) = _ is erroneous.

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

         % sorry(Module, What):
         %
         % Call error/1 with the string
         % "Module: Sorry, not implemented: What".
         %
         % Use this for features that should be implemented (or at least could be
         % implemented).
         %
     :- func sorry(string, string) = _ is erroneous.
     :- pred sorry(string::in, string::in) is erroneous.

         % sorry(Module, Proc, What):
         %
         % Call error/1 with the string
         % "Module: Proc: Sorry, not implemented: What".
         %
         % Use this for features that should be implemented,
         % or at least could be implemented.
         %
     :- func sorry(string, string, string) = _ is erroneous.
     :- pred sorry(string::in, string::in, string::in) is erroneous.

         % unexpected(Module, Message):
         %
         % Call error/1 with the string
         % "Module: Unexpected: What".
         %
         % Use this to handle cases which are not expected to arise (i.e. bugs).
         %
     :- func unexpected(string, string) = _ is erroneous.
     :- pred unexpected(string::in, string::in) is erroneous.

         % unexpected(Module, Proc, Message):
         %
         % Call error/1 with the string
         % "Module: Proc: Unexpected: What".
         %
         % Use this to handle cases which are not expected to arise (i.e. bugs).
         %
     :- func unexpected(string, string, string) = _ is erroneous.
     :- pred unexpected(string::in, string::in, string::in) is erroneous.

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

         % require(Goal, Message):
         %
         % Call goal, and call error(Message) if Goal fails.
         % This is not as useful as you might imagine, since it requires
         % that the goal not produce any output variables. In most circumstances,
         % you should use an explicit if-then-else with a call to error/1,
         % or one of its wrappers, in the "else".
         %
     :- pred require((pred)::((pred) is semidet), string::in) is det.

         % expect(Goal, Module, Message):
         %
         % Call Goal, and call unexpected(Module, Message) if Goal fails.
         %
     :- pred expect((pred)::((pred) is semidet), string::in, string::in) is det.

         % expect(Goal, Module, Proc, Message):
         %
         % Call Goal, and call unexpected(Module, Proc, Message) if Goal fails.
         %
     :- pred expect((pred)::((pred) is semidet), string::in, string::in,
         string::in) is det.

         % expect_not(Goal, Module, Message):
         %
         % Call Goal, and call unexpected(Module, Message) if Goal succeeds.
         %
     :- pred expect_not((pred)::((pred) is semidet), string::in, string::in) is det.

         % expect_not(Goal, Module, Proc, Message):
         %
         % Call Goal, and call unexpected(Module, Proc, Message) if Goal succeeds.
         %
     :- pred expect_not((pred)::((pred) is semidet), string::in, string::in,
         string::in) is det.

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

         % report_lookup_error(Message, Key):
         %
         % Call error/1 with an error message that is appropriate for
         % the failure of a lookup operation involving the specified Key.
         % The error message will include Message and information about Key.
         %
     :- pred report_lookup_error(string::in, K::in) is erroneous.

         % report_lookup_error(Message, Key, Value):
         %
         % Call error/1 with an error message that is appropriate for
         % the failure of a lookup operation involving the specified Key and Value.
         % The error message will include Message and information about Key
         % and Value.
         %
     :- pred report_lookup_error(string::in, K::in, V::unused) is erroneous.

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


File: mercury_library.info,  Node: rtree,  Next: set_bbbtree,  Prev: require,  Up: Top

59 rtree
********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2006-2007 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: rtree.m.
     % Main author: gjd.
     % Stability: low.
     %
     % This module provides a region tree (R-tree) ADT.  A region tree associates
     % values with regions in some space, e.g. rectangles in the 2D plane, or
     % bounding spheres in 3D space.  Region trees accept spatial queries, e.g. a
     % typical usage is "find all pubs within a 2km radius".
     %
     % This module also provides the typeclass region(K) which allows the user to
     % define new regions and spaces.  Three "builtin" instances for region(K)
     % are provided: region(interval), region(box) and region(box3d)
     % corresponding to "square" regions in one, two and three dimensional spaces
     % respectively.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module rtree.
     :- interface.

     :- import_module list.

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

     :- type rtree(K, V).

     :- typeclass region(K) where [

             % Succeeds iff two regions intersect.
             %
         pred intersects(K::in, K::in) is semidet,

             % Succeeds iff the first region is contained within the second.
             %
         pred contains(K::in, K::in) is semidet,

             % Returns the "size" of a region.
             % e.g. for a two dimensional box one possible measure of "size"
             %      would be the area.
             %
         func size(K) = float,

             % Return a region that contains both input regions.
             % The region returned should be minimal region that contains
             % both input regions.
             %
         func bounding_region(K, K) = K,

             % Computes the size of the bounding region returned by
             % bounding_region/2, i.e.
             %
             % bounding_region_size(K1, K2) = size(bounding_region(K1, K2)).
             %
             % While the above definition would suffice, a more efficient
             % implementation often exists, e.g. for intervals:
             %
             % bounding_region_size(interval(X0, X1), interval(Y0, Y1)) =
             %       max(X1, Y1) - min(X0, Y0).
             %
             % This version is more efficient since it does not create a
             % temporary interval.
             %
         func bounding_region_size(K, K) = float
     ].

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

         % Initialize an empty rtree.
         %
     :- func rtree.init = (rtree(K, V)::uo) is det <= region(K).

         % Succeeds iff the given rtree is empty.
         %
     :- pred rtree.is_empty(rtree(K, V)::in) is semidet.

         % Insert a new key and corresponding value into an rtree.
         %
     :- func rtree.insert(K, V, rtree(K, V)) = rtree(K, V) <= region(K).
     :- pred rtree.insert(K::in, V::in, rtree(K, V)::in, rtree(K, V)::out)
         is det <= region(K).

         % Delete a key-value pair from an rtree.
         % Assumes that K is either the key for V, or is contained in the key
         % for V.
         %
         % Fails if the key-value pair is not in the tree.
         %
     :- pred rtree.delete(K::in, V::in, rtree(K, V)::in, rtree(K, V)::out)
         is semidet <= region(K).

         % Search for all values with keys that intersect the query key.
         %
     :- func rtree.search_intersects(rtree(K, V), K) = list(V) <= region(K).

         % Search for all values with keys that contain the query key.
         %
     :- func rtree.search_contains(rtree(K, V), K) = list(V) <= region(K).

         % search_general(KTest, VTest, T) = V.
         %
         % Search for all values V with associated keys K that satisfy
         % KTest(K) /\ VTest(V).  The search assumes that for all K1, K2
         % such that K1 contains K2, then if KTest(K2) holds we have that
         % KTest(K1) also holds.
         %
         % We have that:
         %
         %   search_intersects(T, K, Vs)
         %       <=> search_general(intersects(K), true, T, Vs)
         %
         %   search_contains(T, K, Vs)
         %       <=> search_general(contains(K), true, T, Vs)
         %
     :- func rtree.search_general(pred(K)::in(pred(in) is semidet),
         pred(V)::in(pred(in) is semidet), rtree(K, V)::in) = (list(V)::out)
         is det.

         % search_first(KTest, VTest, Max, T, V, L).
         %
         % Search for a value V with associated key K such that
         % KTest(K, _) /\ VTest(V, L) is satisfied and there does not exist a
         % V' with K' such that KTest(K', _) /\ VTest(V', L') /\ (L' < L) is
         % satisfied.  Fail if no such key-value pair exists.
         %
         % The search assumes that for all K1, K2 such that
         % K1 contains K2, then if KTest(K2, L2) holds we have that
         % KTest(K1, L1) holds with L2 >= L1.
         %
         % If there exist multiple key-value pairs that satisfy the above
         % conditions, then one of the candidates is chosen arbitrarily.
         %
     :- pred rtree.search_first(pred(K, L), pred(V, L), rtree(K, V), L, V, L).
     :- mode rtree.search_first(pred(in, out) is semidet,
         pred(in, out) is semidet, in, in, out, out) is semidet.

         % search_general_fold(KTest, VPred, T, !A).
         %
         % Apply accumulator VPred to each key-value pair K-V that satisfies
         % KTest(K).  The same assumptions for KTest from search_general apply
         % here.
         %
     :- pred rtree.search_general_fold(pred(K), pred(K, V, A, A), rtree(K, V),
         A, A).
     :- mode rtree.search_general_fold(pred(in) is semidet,
         pred(in, in, in, out) is det, in, in, out) is det.
     :- mode rtree.search_general_fold(pred(in) is semidet,
         pred(in, in, di, uo) is det, in, di, uo) is det.

         % Perform a traversal of the rtree, applying an accumulator predicate
         % for each key-value pair.
         %
     :- pred rtree.fold(pred(K, V, A, A), rtree(K, V), A, A).
     :- mode rtree.fold(pred(in, in, in, out) is det, in, in, out) is det.
     :- mode rtree.fold(pred(in, in, di, uo) is det, in, di, uo) is det.
     :- mode rtree.fold(pred(in, in, in, out) is semidet, in, in, out)
         is semidet.

         % Apply a transformation predicate to all the values in an rtree.
         %
     :- pred rtree.map_values(pred(K, V, W), rtree(K, V), rtree(K, W)).
     :- mode rtree.map_values(pred(in, in, out) is det, in, out) is det.
     :- mode rtree.map_values(pred(in, in, out) is semidet, in, out)
         is semidet.

     %--------------------------------------------------%
     %
     % Pre-defined regions
     %

         % An interval type represented as interval(Min, Max).
         %
     :- type interval
         --->    interval(float, float).

         % A 2D axis aligned box represented as box(XMin, XMax, YMin, YMax).
         %
     :- type box
         --->    box(float, float, float, float).

         % A 3D axis aligned box represented as
         % box(XMin, XMax, YMin, YMax, ZMin, ZMax).
         %
     :- type box3d
         --->    box3d(float, float, float, float, float, float).

     :- instance region(interval).
     :- instance region(box).
     :- instance region(box3d).

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


File: mercury_library.info,  Node: set_bbbtree,  Next: set_ctree234,  Prev: rtree,  Up: Top

60 set_bbbtree
**************

     %--------------------------------------------------%
     % vim: ts=4 sw=4 et ft=mercury
     %--------------------------------------------------%
     % Copyright (C) 1995-1997, 1999-2006, 2010-2011 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_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).

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

         % `set_bbbtree.empty(Set) is true iff `Set' is contains no elements.
         %
     :- pred set_bbbtree.empty(set_bbbtree(T)::in) is semidet.

         % A synonym for the above.
         %
     :- pred set_bbbtree.is_empty(set_bbbtree(T)::in) is semidet.

     :- pred set_bbbtree.non_empty(set_bbbtree(T)::in) is semidet.

         % `set_bbbtree.count(Set, Count)' is true iff `Set' has `Count' elements.
         % i.e. `Count' is the cardinality (size) of the set.
         %
     :- func set_bbbtree.count(set_bbbtree(T)) = int.
     :- pred set_bbbtree.count(set_bbbtree(T)::in, int::out) is det.

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

         % `set_bbbtree.is_member(X, Set, Result)' is true iff `X' is a member
         % of `Set'.
         %
     :- pred set_bbbtree.is_member(T::in, set_bbbtree(T)::in, bool::out) is det.

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

         % `set_bbbtree.least(Set, X)' is true iff `X' is smaller than all
         % the other members of `Set'.
         %
     :- pred set_bbbtree.least(set_bbbtree(T), T).
     :- mode set_bbbtree.least(in, out) is semidet.
     :- mode set_bbbtree.least(in, in) is semidet.

         % `set_bbbtree.largest(Set, X)' is true iff `X' is larger than all
         % the other members of `Set'.
         %
     :- pred set_bbbtree.largest(set_bbbtree(T), T).
     :- mode set_bbbtree.largest(in, out) is semidet.
     :- mode set_bbbtree.largest(in, in) is semidet.

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

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

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

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

     :- func set_bbbtree.insert(set_bbbtree(T), T) = set_bbbtree(T).

         % `set_bbbtree.insert_list(Xs, Set0, Set)' is true iff `Set' is
         % the union of `Set0' and the set containing only the members of `Xs'.
         %
     :- pred set_bbbtree.insert_list(list(T)::in,
         set_bbbtree(T)::in, set_bbbtree(T)::out) is det.

     :- func set_bbbtree.insert_list(set_bbbtree(T), list(T)) = set_bbbtree(T).

         % `set_bbbtree.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'.
         %
     :- pred set_bbbtree.delete(T, set_bbbtree(T), set_bbbtree(T)).
     :- mode set_bbbtree.delete(in, di, uo) is det.
     :- mode set_bbbtree.delete(in, in, out) is det.

     :- func set_bbbtree.delete(set_bbbtree(T), T) = set_bbbtree(T).

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

     :- func set_bbbtree.delete_list(set_bbbtree(T), list(T)) = set_bbbtree(T).

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

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

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

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

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

     :- func set_bbbtree.list_to_set(list(T)) = set_bbbtree(T).

         % A synonym for set_bbtree.list_to_set/1.
         %
     :- func set_bbbtree.from_list(list(T)) = set_bbbtree(T).

         % `set_bbbtree.sorted_list_to_set(List, Set)' is true iff `Set' is the
         % set containing only the members of `List'.
         % `List' must be sorted. O(n).
         %
     :- pred set_bbbtree.sorted_list_to_set(list(T)::in, set_bbbtree(T)::out)
         is det.

     :- func set_bbbtree.sorted_list_to_set(list(T)) = set_bbbtree(T).

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

         % `set_bbbtree.sorted_list_to_set_len(List, Set, N)' is true iff
         % `Set' is the set containing only the members of `List' and `N'
         % is the length of the list. If the length of the list is already known
         % then a noticeable speed improvement can be expected over
         % `set_bbbtree.sorted_list_to_set' as a significant cost involved
         % with `set_bbbtree.sorted_list_to_set' is the call to list.length.
         % `List' must be sorted. O(n).
         %
     :- pred set_bbbtree.sorted_list_to_set_len(list(T)::in, set_bbbtree(T)::out,
         int::in) is det.

         % `set_bbbtree.to_sorted_list(Set, List)' is true iff `List' is the
         % list of all the members of `Set', in sorted order. O(n).
         %
     :- pred set_bbbtree.to_sorted_list(set_bbbtree(T), list(T)).
     :- mode set_bbbtree.to_sorted_list(di, uo) is det.
     :- mode set_bbbtree.to_sorted_list(in, out) is det.

     :- func set_bbbtree.to_sorted_list(set_bbbtree(T)) = list(T).

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

     :- func set_bbbtree.union(set_bbbtree(T), set_bbbtree(T)) = set_bbbtree(T).

         % `set_bbbtree.union_list(Sets) = Set' is true iff `Set' is the union
         % of all the sets in `Sets'
         %
     :- func set_bbbtree.union_list(list(set_bbbtree(T))) = set_bbbtree(T).

         % `set_bbbtree.power_union(Sets, Set)' is true iff `Set' is the union
         % of all the sets in `Sets'
         %
     :- pred set_bbbtree.power_union(set_bbbtree(set_bbbtree(T))::in,
         set_bbbtree(T)::out) is det.

     :- func set_bbbtree.power_union(set_bbbtree(set_bbbtree(T))) = set_bbbtree(T).

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

     :- func set_bbbtree.intersect(set_bbbtree(T), set_bbbtree(T)) = set_bbbtree(T).

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

     :- func set_bbbtree.power_intersect(set_bbbtree(set_bbbtree(T)))
         = set_bbbtree(T).

         % `set_bbbtree.intersect_list(Sets) = Set is true iff `Set' is the
         % intersection of the sets in `Sets'.
         %
     :- func set_bbbtree.intersect_list(list(set_bbbtree(T))) = set_bbbtree(T).

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

     :- func set_bbbtree.difference(set_bbbtree(T), set_bbbtree(T))
         = set_bbbtree(T).

         % `set_bbbtree.subset(SetA, SetB)' is true iff all the elements of
         % `SetA' are also elements of `SetB'.
         %
     :- pred set_bbbtree.subset(set_bbbtree(T)::in, set_bbbtree(T)::in) is semidet.

         % `set_bbbtree.superset(SetA, SetB)' is true iff all the elements of
         % `SetB' are also elements of `SetA'.
         %
     :- pred set_bbbtree.superset(set_bbbtree(T)::in, set_bbbtree(T)::in)
         is semidet.

     :- func set_bbbtree.fold(func(T1, T2) = T2, set_bbbtree(T1), T2) = T2.
     :- pred set_bbbtree.fold(pred(T1, T2, T2), set_bbbtree(T1), T2, T2).
     :- mode set_bbbtree.fold(pred(in, in, out) is det, in, in, out) is det.
     :- mode set_bbbtree.fold(pred(in, mdi, muo) is det, in, mdi, muo) is det.
     :- mode set_bbbtree.fold(pred(in, di, uo) is det, in, di, uo) is det.
     :- mode set_bbbtree.fold(pred(in, in, out) is semidet, in, in, out)
         is semidet.
     :- mode set_bbbtree.fold(pred(in, mdi, muo) is semidet, in, mdi, muo)
         is semidet.
     :- mode set_bbbtree.fold(pred(in, di, uo) is semidet, in, di, uo)
         is semidet.

     :- pred set_bbbtree.fold2(pred(T1, T2, T2, T3, T3), set_bbbtree(T1),
         T2, T2, T3, T3).
     :- mode set_bbbtree.fold2(pred(in, in, out, in, out) is det, in,
         in, out, in, out) is det.
     :- mode set_bbbtree.fold2(pred(in, in, out, mdi, muo) is det, in,
         in, out, mdi, muo) is det.
     :- mode set_bbbtree.fold2(pred(in, in, out, di, uo) is det, in,
         in, out, di, uo) is det.
     :- mode set_bbbtree.fold2(pred(in, in, out, in, out) is semidet, in,
         in, out, in, out) is semidet.
     :- mode set_bbbtree.fold2(pred(in, in, out, mdi, muo) is semidet, in,
         in, out, mdi, muo) is semidet.
     :- mode set_bbbtree.fold2(pred(in, in, out, di, uo) is semidet, in,
         in, out, di, uo) is semidet.

     :- pred set_bbbtree.fold3(pred(T1, T2, T2, T3, T3, T4, T4),
         set_bbbtree(T1), T2, T2, T3, T3, T4, T4).
     :- mode set_bbbtree.fold3(pred(in, in, out, in, out, in, out) is det, in,
         in, out, in, out, in, out) is det.
     :- mode set_bbbtree.fold3(pred(in, in, out, in, out, mdi, muo) is det, in,
         in, out, in, out, mdi, muo) is det.
     :- mode set_bbbtree.fold3(pred(in, in, out, in, out, di, uo) is det, in,
         in, out, in, out, di, uo) is det.
     :- mode set_bbbtree.fold3(pred(in, in, out, in, out, in, out) is semidet, in,
         in, out, in, out, in, out) is semidet.
     :- mode set_bbbtree.fold3(pred(in, in, out, in, out, mdi, muo) is semidet, in,
         in, out, in, out, mdi, muo) is semidet.
     :- mode set_bbbtree.fold3(pred(in, in, out, in, out, di, uo) is semidet, in,
         in, out, in, out, di, uo) is semidet.

     :- pred set_bbbtree.fold4(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5),
         set_bbbtree(T1), T2, T2, T3, T3, T4, T4, T5, T5).
     :- mode set_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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 set_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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 set_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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_bbbtree.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.

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

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

         % set_bbbtree.filter(Pred, Items, Trues):
         % Return the set of items for which Pred succeeds.
         %
     :- pred set_bbbtree.filter(pred(T)::in(pred(in) is semidet),
         set_bbbtree(T)::in, set_bbbtree(T)::out) is det.

         % set_bbbtree.filter(Pred, Items, Trues, Falses):
         % Return the set of items for which Pred succeeds,
         % and the set for which it fails.
         %
     :- pred set_bbbtree.filter(pred(T)::in(pred(in) is semidet),
         set_bbbtree(T)::in, set_bbbtree(T)::out, set_bbbtree(T)::out) is det.

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


File: mercury_library.info,  Node: set_ctree234,  Next: set,  Prev: set_bbbtree,  Up: Top

61 set_ctree234
***************

     %--------------------------------------------------%
     % vim: ts=4 sw=4 et ft=mercury
     %--------------------------------------------------%
     % Copyright (C) 2005-2006, 2010-2011 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).

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

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

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

         % `set_ctree234.empty(Set)' is true iff `Set' is an empty set.
         %
     :- pred set_ctree234.empty(set_ctree234(_T)::in) is semidet.

     :- pred set_ctree234.is_empty(set_ctree234(_T)::in) is semidet.

     :- pred set_ctree234.non_empty(set_ctree234(T)::in) is semidet.

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

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

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

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

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

     :- func set_ctree234.from_list(list(T)) = set_ctree234(T).

         % `set_ctree234.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_ctree234.sorted_list_to_set(list(T)) = set_ctree234(T).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

     :- func set_ctree234.fold(func(T1, T2) = T2, set_ctree234(T1), T2) = T2.
     :- pred set_ctree234.fold(pred(T1, T2, T2), set_ctree234(T1), T2, T2).
     :- mode set_ctree234.fold(pred(in, in, out) is det, in, in, out) is det.
     :- mode set_ctree234.fold(pred(in, mdi, muo) is det, in, mdi, muo) is det.
     :- mode set_ctree234.fold(pred(in, di, uo) is det, in, di, uo) is det.
     :- mode set_ctree234.fold(pred(in, in, out) is semidet, in, in, out)
         is semidet.
     :- mode set_ctree234.fold(pred(in, mdi, muo) is semidet, in, mdi, muo)
         is semidet.
     :- mode set_ctree234.fold(pred(in, di, uo) is semidet, in, di, uo)
         is semidet.

     :- pred set_ctree234.fold2(pred(T1, T2, T2, T3, T3), set_ctree234(T1),
         T2, T2, T3, T3) is det.
     :- mode set_ctree234.fold2(pred(in, in, out, in, out) is det,
         in, in, out, in, out) is det.
     :- mode set_ctree234.fold2(pred(in, in, out, mdi, muo) is det,
         in, in, out, mdi, muo) is det.
     :- mode set_ctree234.fold2(pred(in, in, out, di, uo) is det,
         in, in, out, di, uo) is det.
     :- mode set_ctree234.fold2(pred(in, in, out, in, out) is semidet,
         in, in, out, in, out) is semidet.
     :- mode set_ctree234.fold2(pred(in, in, out, mdi, muo) is semidet,
         in, in, out, mdi, muo) is semidet.
     :- mode set_ctree234.fold2(pred(in, in, out, di, uo) is semidet,
         in, in, out, di, uo) is semidet.

     :- pred set_ctree234.fold3(
         pred(T1, T2, T2, T3, T3, T4, T4), set_ctree234(T1),
         T2, T2, T3, T3, T4, T4).
     :- mode set_ctree234.fold3(pred(in, in, out, in, out, in, out) is det, in,
         in, out, in, out, in, out) is det.
     :- mode set_ctree234.fold3(pred(in, in, out, in, out, mdi, muo) is det, in,
         in, out, in, out, mdi, muo) is det.
     :- mode set_ctree234.fold3(pred(in, in, out, in, out, di, uo) is det, in,
         in, out, in, out, di, uo) is det.
     :- mode set_ctree234.fold3(pred(in, in, out, in, out, in, out) is semidet, in,
         in, out, in, out, in, out) is semidet.
     :- mode set_ctree234.fold3(pred(in, in, out, in, out, mdi, muo) is semidet, in,
         in, out, in, out, mdi, muo) is semidet.
     :- mode set_ctree234.fold3(pred(in, in, out, in, out, di, uo) is semidet, in,
         in, out, in, out, di, uo) is semidet.

     :- pred set_ctree234.fold4(
         pred(T1, T2, T2, T3, T3, T4, T4, T5, T5), set_ctree234(T1),
         T2, T2, T3, T3, T4, T4, T5, T5).
     :- mode set_ctree234.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_ctree234.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_ctree234.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_ctree234.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_ctree234.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_ctree234.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_ctree234.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 set_ctree234.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_ctree234.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_ctree234.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_ctree234.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_ctree234.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_ctree234.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_ctree234.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 set_ctree234.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_ctree234.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_ctree234.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_ctree234.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_ctree234.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_ctree234.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.

         % Return the set of items for which the predicate succeeds.
         %
     :- pred set_ctree234.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 set_ctree234.filter(pred(T)::in(pred(in) is semidet),
         set_ctree234(T)::in, set_ctree234(T)::out, set_ctree234(T)::out) is det.

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

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

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

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


File: mercury_library.info,  Node: set,  Next: set_ordlist,  Prev: set_ctree234,  Up: Top

62 set
******

     %--------------------------------------------------%
     % vim: ts=4 sw=4 et ft=mercury
     %--------------------------------------------------%
     % Copyright (C) 1994-1997, 1999-2011 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.m.
     % Main authors: conway, fjh, benyi.
     % Stability: high.
     %
     % This module provides a set ADT.
     % The implementation represents sets using ordered lists.
     % This file just calls the equivalent predicates in set_ordlist.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module set.
     :- interface.

     :- import_module bool.
     :- import_module list.

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

     :- type set(T).

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

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

         % Synonyms for set.list_to_set/1.
         %
     :- func set.from_list(list(T)) = set(T).
     :- func set.set(list(T)) = set(T).

         % `set.sorted_list_to_set(List, Set)' is true iff `Set' is the set
         % containing only the members of `List'.  `List' must be sorted
         % and must not contain any duplicates.
         %
     :- pred set.sorted_list_to_set(list(T)::in, set(T)::out) is det.
     :- func set.sorted_list_to_set(list(T)) = set(T).

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

         % `set.to_sorted_list(Set, List)' is true iff `List' is the list
         % of all the members of `Set', in sorted order without any
         % duplicates.
         %
     :- pred set.to_sorted_list(set(T)::in, list(T)::out) is det.
     :- func set.to_sorted_list(set(T)) = list(T).

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

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

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

     :- pred set.empty(set(T)::in) is semidet.

     :- pred set.non_empty(set(T)::in) is semidet.

         % A synonym for set.empty/1.
         %
     :- pred set.is_empty(set(T)::in) is semidet.

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

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

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

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

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

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

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

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

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

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

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

         % `set.remove_least(Elem, Set0, Set)' is true iff
         % `Set0' is not empty, `Elem' is the smallest element in `Set0'
         % (with elements ordered using the standard ordering given
         % by compare/3), and `Set' is the set containing all the
         % elements of `Set0' except `Elem'.
         %
     :- pred set.remove_least(T::out, set(T)::in, set(T)::out) is semidet.

         % `set.union(SetA, SetB, Set)' is true iff `Set' is the union of
         % `SetA' and `SetB'.  If the sets are known to be of different
         % sizes, then for efficiency make `SetA' the larger of the two.
         % (The current implementation using sorted lists with duplicates
         % removed is not sensitive to the ordering of the input arguments,
         % but other set implementations may be, so observing this convention
         % will make it less likely that you will encounter problems if
         % the implementation is changed.)
         %
     :- func set.union(set(T), set(T)) = set(T).
     :- pred set.union(set(T)::in, set(T)::in, set(T)::out) is det.

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

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

         % `set.intersect(SetA, SetB, Set)' is true iff `Set' is the
         % intersection of `SetA' and `SetB'. If the two sets are
         % known to be unequal in size, then making SetA be the larger
         % set will usually be more efficient.
         % (The current implementation, using sorted lists with duplicates
         % removed is not sensitive to the ordering of the input arguments
         % but other set implementations may be, so observing this convention
         % will make it less likely that you will encounter problems if
         % the implementation is changed.)
         %
     :- func set.intersect(set(T), set(T)) = set(T).
     :- pred set.intersect(set(T)::in, set(T)::in, set(T)::out) is det.

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

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

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

         % `set.count(Set, Count)' is true iff `Set' has `Count' elements.
         % i.e. `Count' is the cardinality (size) of the set.
         %
     :- func set.count(set(T)) = int.
     :- pred set.count(set(T)::in, int::out) is det.

         % Support for higher order set processing.

         % map(F, S) =
         %   list_to_set(list.map(F, to_sorted_list(S))).
         %
     :- func set.map(func(T1) = T2, set(T1)) = set(T2).
     :- pred set.map(pred(T1, T2), set(T1), set(T2)).
     :- mode set.map(pred(in, out) is det, in, out) is det.
     :- mode set.map(pred(in, out) is cc_multi, in, out) is cc_multi.
     :- mode set.map(pred(in, out) is semidet, in, out) is semidet.
     :- mode set.map(pred(in, out) is multi, in, out) is multi.
     :- mode set.map(pred(in, out) is nondet, in, out) is nondet.

         % set.map_fold(P, S0, S, A0, A) :-
         %   L0 = set.to_sorted_list(S0),
         %   list.map_foldl(P, L0, L, A0, A),
         %   S = set.list_to_set(L).
         %
     :- pred set.map_fold(pred(T1, T2, T3, T3), set(T1), set(T2), T3, T3).
     :- mode set.map_fold(pred(in, out, in, out) is det, in, out, in, out) is det.
     :- mode set.map_fold(pred(in, out, mdi, muo) is det, in, out, mdi, muo) is det.
     :- mode set.map_fold(pred(in, out, di, uo) is det, in, out, di, uo) is det.
     :- mode set.map_fold(pred(in, out, in, out) is semidet, in, out,
         in, out) is semidet.
     :- mode set.map_fold(pred(in, out, mdi, muo) is semidet, in, out,
         mdi, muo) is semidet.
     :- mode set.map_fold(pred(in, out, di, uo) is semidet, in, out,
         di, uo) is semidet.

         % Return the set of items for which the given predicate succeeds.
         % set.filter(P, S) =
         %   sorted_list_to_set(list.filter(P, to_sorted_list(S))).
         %
     :- func set.filter(pred(T1), set(T1)) = set(T1).
     :- mode set.filter(pred(in) is semidet, in) = out is det.
     :- pred set.filter(pred(T1), set(T1), set(T1)).
     :- mode set.filter(pred(in) is semidet, in, out) is det.

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

         % set.filter_map(PF, S) =
         %   list_to_set(list.filter_map(PF, to_sorted_list(S))).
         %
     :- pred set.filter_map(pred(T1, T2), set(T1), set(T2)).
     :- mode set.filter_map(in(pred(in, out) is semidet), in, out) is det.
     :- func set.filter_map(func(T1) = T2, set(T1)) = set(T2).
     :- mode set.filter_map(func(in) = out is semidet, in) = out is det.

         % set.fold(F, S, A) =
         %   list.foldl(F, to_sorted_list(S), A).
         %
     :- func set.fold(func(T, A) = A, set(T), A) = A.

     :- pred set.fold(pred(T, A, A), set(T), A, A).
     :- mode set.fold(pred(in, in, out) is det, in, in, out) is det.
     :- mode set.fold(pred(in, mdi, muo) is det, in, mdi, muo) is det.
     :- mode set.fold(pred(in, di, uo) is det, in, di, uo) is det.
     :- mode set.fold(pred(in, in, out) is semidet, in, in, out) is semidet.
     :- mode set.fold(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet.
     :- mode set.fold(pred(in, di, uo) is semidet, in, di, uo) is semidet.

     :- pred set.fold2(pred(T, A, A, B, B), set(T), A, A, B, B).
     :- mode set.fold2(pred(in, in, out, in, out) is det, in,
         in, out, in, out) is det.
     :- mode set.fold2(pred(in, in, out, mdi, muo) is det, in,
         in, out, mdi, muo) is det.
     :- mode set.fold2(pred(in, in, out, di, uo) is det, in,
         in, out, di, uo) is det.
     :- mode set.fold2(pred(in, in, out, in, out) is semidet,
         in, in, out, in, out) is semidet.
     :- mode set.fold2(pred(in, in, out, mdi, muo) is semidet,
         in, in, out, mdi, muo) is semidet.
     :- mode set.fold2(pred(in, in, out, di, uo) is semidet,
         in, in, out, di, uo) is semidet.

     :- pred set.fold3(pred(T, A, A, B, B, C, C), set(T), A, A, B, B, C, C).
     :- mode set.fold3(pred(in, in, out, in, out, in, out) is det, in,
         in, out, in, out, in, out) is det.
     :- mode set.fold3(pred(in, in, out, in, out, mdi, muo) is det, in,
         in, out, in, out, mdi, muo) is det.
     :- mode set.fold3(pred(in, in, out, in, out, di, uo) is det, in,
         in, out, in, out, di, uo) is det.
     :- mode set.fold3(pred(in, in, out, in, out, in, out) is semidet, in,
         in, out, in, out, in, out) is semidet.
     :- mode set.fold3(pred(in, in, out, in, out, mdi, muo) is semidet, in,
         in, out, in, out, mdi, muo) is semidet.
     :- mode set.fold3(pred(in, in, out, in, out, di, uo) is semidet, in,
         in, out, in, out, di, uo) is semidet.

     :- pred set.fold4(pred(T, A, A, B, B, C, C, D, D), set(T), A, A, B, B,
         C, C, D, D).
     :- mode set.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.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.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.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.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.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.fold5(pred(T, A, A, B, B, C, C, D, D, E, E), set(T), A, A, B, B,
         C, C, D, D, E, E).
     :- mode set.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.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.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.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.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.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.fold6(pred(T, A, A, B, B, C, C, D, D, E, E, F, F), set(T),
         A, A, B, B, C, C, D, D, E, E, F, F).
     :- mode set.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.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.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.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.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.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.

         % set.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.divide(pred(T)::in(pred(in) is semidet), set(T)::in,
         set(T)::out, set(T)::out) is det.

         % set_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.divide_by_set(set(T)::in, set(T)::in, set(T)::out, set(T)::out)
         is det.

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


File: mercury_library.info,  Node: set_ordlist,  Next: set_tree234,  Prev: set,  Up: Top

63 set_ordlist
**************

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et
     %--------------------------------------------------%
     % Copyright (C) 1996-1997,1999-2002, 2004-2006, 2008-2011 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_ordlist.m.
     % Main authors: conway, fjh.
     % Stability: medium.
     %
     % This file contains a `set' ADT.
     % Sets are implemented here as sorted lists without duplicates.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module set_ordlist.
     :- interface.

     :- import_module bool.
     :- import_module list.

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

     :- type set_ordlist(_T).

         % `set_ordlist.init(Set)' is true iff `Set' is an empty set.
         %
     :- pred set_ordlist.init(set_ordlist(_T)::uo) is det.
     :- func set_ordlist.init = set_ordlist(T).

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

         % A synonym for set_ordlist.list_to_set/1.
         %
     :- func set_ordlist.from_list(list(T)) = set_ordlist(T).

         % `set_ordlist.sorted_list_to_set(List, Set)' is true iff `Set' is
         % the set containing only the members of `List'.  `List' must be sorted.
         %
     :- pred set_ordlist.sorted_list_to_set(list(T)::in, set_ordlist(T)::out)
         is det.
     :- func set_ordlist.sorted_list_to_set(list(T)) = set_ordlist(T).

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

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

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

     :- func set_ordlist.make_singleton_set(T) = set_ordlist(T).
     :- pred set_ordlist.is_singleton(set_ordlist(T)::in, T::out) is semidet.

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

         % `set_ordlist.empty(Set)' is true iff `Set' is an empty set.
         %
     :- pred set_ordlist.empty(set_ordlist(_T)::in) is semidet.
     :- pred set_ordlist.is_empty(set_ordlist(T)::in) is semidet.

     :- pred set_ordlist.non_empty(set_ordlist(T)::in) is semidet.
     :- pred set_ordlist.is_non_empty(set_ordlist(T)::in) is semidet.

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

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

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

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

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

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

     :- func set_ordlist.insert(set_ordlist(T), T) = set_ordlist(T).

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

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

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

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

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

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

         % `set_ordlist.union(SetA, SetB, Set)' is true iff `Set' is the union
         % of `SetA' and `SetB'. The efficiency of the union operation is
         % O(card(SetA)+card(SetB)) and is not sensitive to the argument
         % ordering.
         %
     :- pred set_ordlist.union(set_ordlist(T)::in, set_ordlist(T)::in,
         set_ordlist(T)::out) is det.
     :- func set_ordlist.union(set_ordlist(T), set_ordlist(T)) = set_ordlist(T).

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

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

         % `set_ordlist.intersect(SetA, SetB, Set)' is true iff `Set' is the
         % intersection of `SetA' and `SetB'. The efficiency of the intersection
         % operation is not influenced by the argument order.
         %
     :- pred set_ordlist.intersect(set_ordlist(T), set_ordlist(T), set_ordlist(T)).
     :- mode set_ordlist.intersect(in, in, out) is det.
     :- mode set_ordlist.intersect(in, in, in) is semidet.
     :- func set_ordlist.intersect(set_ordlist(T), set_ordlist(T))
         = set_ordlist(T).

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

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

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

         % `set_ordlist.count(Set, Count)' is true iff `Set' has
         % `Count' elements.
         %
     :- pred set_ordlist.count(set_ordlist(T)::in, int::out) is det.
     :- func set_ordlist.count(set_ordlist(T)) = int.

         % Return the set of items for which the given predicate succeeds.
         %
     :- func set_ordlist.filter(pred(T1), set_ordlist(T1)) = set_ordlist(T1).
     :- mode set_ordlist.filter(pred(in) is semidet, in) = out is det.
     :- pred set_ordlist.filter(pred(T1), set_ordlist(T1), set_ordlist(T1)).
     :- mode set_ordlist.filter(pred(in) is semidet, in, out) is det.

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

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

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

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

     :- func set_ordlist.fold(func(T1, T2) = T2, set_ordlist(T1), T2) = T2.
     :- pred set_ordlist.fold(pred(T1, T2, T2), set_ordlist(T1), T2, T2).
     :- mode set_ordlist.fold(pred(in, in, out) is det, in, in, out) is det.
     :- mode set_ordlist.fold(pred(in, mdi, muo) is det, in, mdi, muo) is det.
     :- mode set_ordlist.fold(pred(in, di, uo) is det, in, di, uo) is det.
     :- mode set_ordlist.fold(pred(in, in, out) is semidet, in, in, out)
         is semidet.
     :- mode set_ordlist.fold(pred(in, mdi, muo) is semidet, in, mdi, muo)
         is semidet.
     :- mode set_ordlist.fold(pred(in, di, uo) is semidet, in, di, uo)
         is semidet.

     :- pred set_ordlist.fold2(pred(T1, T2, T2, T3, T3), set_ordlist(T1),
         T2, T2, T3, T3).
     :- mode set_ordlist.fold2(pred(in, in, out, in, out) is det, in,
         in, out, in, out) is det.
     :- mode set_ordlist.fold2(pred(in, in, out, mdi, muo) is det, in,
         in, out, mdi, muo) is det.
     :- mode set_ordlist.fold2(pred(in, in, out, di, uo) is det, in,
         in, out, di, uo) is det.
     :- mode set_ordlist.fold2(pred(in, in, out, in, out) is semidet, in,
         in, out, in, out) is semidet.
     :- mode set_ordlist.fold2(pred(in, in, out, mdi, muo) is semidet, in,
         in, out, mdi, muo) is semidet.
     :- mode set_ordlist.fold2(pred(in, in, out, di, uo) is semidet, in,
         in, out, di, uo) is semidet.

     :- pred set_ordlist.fold3(pred(T1, T2, T2, T3, T3, T4, T4),
         set_ordlist(T1), T2, T2, T3, T3, T4, T4).
     :- mode set_ordlist.fold3(pred(in, in, out, in, out, in, out) is det, in,
         in, out, in, out, in, out) is det.
     :- mode set_ordlist.fold3(pred(in, in, out, in, out, mdi, muo) is det, in,
         in, out, in, out, mdi, muo) is det.
     :- mode set_ordlist.fold3(pred(in, in, out, in, out, di, uo) is det, in,
         in, out, in, out, di, uo) is det.
     :- mode set_ordlist.fold3(pred(in, in, out, in, out, in, out) is semidet, in,
         in, out, in, out, in, out) is semidet.
     :- mode set_ordlist.fold3(pred(in, in, out, in, out, mdi, muo) is semidet, in,
         in, out, in, out, mdi, muo) is semidet.
     :- mode set_ordlist.fold3(pred(in, in, out, in, out, di, uo) is semidet, in,
         in, out, in, out, di, uo) is semidet.

     :- pred set_ordlist.fold4(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5),
         set_ordlist(T1), T2, T2, T3, T3, T4, T4, T5, T5).
     :- mode set_ordlist.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_ordlist.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_ordlist.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_ordlist.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_ordlist.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_ordlist.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_ordlist.fold5(
         pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6),
         set_ordlist(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6).
     :- mode set_ordlist.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_ordlist.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_ordlist.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_ordlist.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_ordlist.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_ordlist.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_ordlist.fold6(pred(T, A, A, B, B, C, C, D, D, E, E, F, F),
         set_ordlist(T), A, A, B, B, C, C, D, D, E, E, F, F).
     :- mode set_ordlist.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_ordlist.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_ordlist.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_ordlist.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_ordlist.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_ordlist.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.

         % set_ordlist.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_ordlist.divide(pred(T)::in(pred(in) is semidet),
         set_ordlist(T)::in, set_ordlist(T)::out, set_ordlist(T)::out) is det.

         % set_ordlist.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 set_ordlist.divide_by_set(set_ordlist(T)::in, set_ordlist(T)::in,
         set_ordlist(T)::out, set_ordlist(T)::out) is det.

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


File: mercury_library.info,  Node: set_tree234,  Next: set_unordlist,  Prev: set_ordlist,  Up: Top

64 set_tree234
**************

     %--------------------------------------------------%
     % vim: ts=4 sw=4 et ft=mercury
     %--------------------------------------------------%
     % Copyright (C) 2005-2006, 2009-2011 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.

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

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

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

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

     :- func set_tree234.from_list(list(T)) = set_tree234(T).

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

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

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

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

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

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

         % Return the set of items for which the predicate succeeds.
         %
     :- 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.

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


File: mercury_library.info,  Node: set_unordlist,  Next: solutions,  Prev: set_tree234,  Up: Top

65 set_unordlist
****************

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et
     %--------------------------------------------------%
     % Copyright (C) 1995-1997,1999-2002, 2004-2006, 2010-2011 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_unordlist.m.
     % Main authors: conway, fjh.
     % Stability: medium.
     %
     % This file contains a `set' ADT.
     % Sets are implemented here as unsorted lists, which may contain duplicates.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module set_unordlist.
     :- interface.

     :- import_module bool.
     :- import_module list.

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

     :- type set_unordlist(_T).

         % `set_unordlist.init(Set)' is true iff `Set' is an empty set.
         %
     :- func set_unordlist.init = set_unordlist(T).
     :- pred set_unordlist.init(set_unordlist(_T)::uo) is det.

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

         % A synonym for set_unordlist.list_to_set/1.
         %
     :- func set_unordlist.from_list(list(T)) = set_unordlist(T).

         % `set_unordlist.sorted_list_to_set(List, Set)' is true iff `Set' is
         % the set containing only the members of `List'.  `List' must be sorted.
         %
     :- pred set_unordlist.sorted_list_to_set(list(T)::in, set_unordlist(T)::out)
         is det.
     :- func set_unordlist.sorted_list_to_set(list(T)) = set_unordlist(T).

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

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

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

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

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

         % `set_unordlist.empty(Set)' is true iff `Set' is an empty set.
         %
     :- pred set_unordlist.empty(set_unordlist(_T)::in) is semidet.

     :- pred set_unordlist.non_empty(set_unordlist(_T)::in) is semidet.

     :- pred set_unordlist.is_empty(set_unordlist(_T)::in) is semidet.

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

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

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

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

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

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

     :- func set_unordlist.insert(set_unordlist(T), T) = set_unordlist(T).

         % `set_unordlist.insert_list(Xs, Set0, Set)' is true iff `Set' is the
         % union of `Set0' and the set containing only the members of `Xs'.
         %
     :- pred set_unordlist.insert_list(list(T)::in,
         set_unordlist(T)::in, set_unordlist(T)::out) is det.

     :- func set_unordlist.insert_list(set_unordlist(T), list(T))
         = set_unordlist(T).

         % `set_unordlist.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'.
         %
     :- pred set_unordlist.delete(T, set_unordlist(T), set_unordlist(T)).
     :- mode set_unordlist.delete(in, di, uo) is det.
     :- mode set_unordlist.delete(in, in, out) is det.

     :- func set_unordlist.delete(set_unordlist(T), T) = set_unordlist(T).

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

     :- func set_unordlist.delete_list(set_unordlist(T), list(T))
         = set_unordlist(T).

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

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

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

         % `set_unordlist.union(SetA, SetB, Set)' is true iff `Set' is the union
         % of `SetA' and `SetB'.  If the sets are known to be of different
         % sizes, then for efficiency make `SetA' the larger of the two.
         %
     :- pred set_unordlist.union(set_unordlist(T)::in, set_unordlist(T)::in,
         set_unordlist(T)::out) is det.

     :- func set_unordlist.union(set_unordlist(T), set_unordlist(T))
         = set_unordlist(T).

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

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

     :- func set_unordlist.power_union(set_unordlist(set_unordlist(T)))
         = set_unordlist(T).

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

     :- func set_unordlist.intersect(set_unordlist(T), set_unordlist(T))
         = set_unordlist(T).

         % `set_unordlist.power_intersect(A, B)' is true iff `B' is the
         % intersection of all the sets in `A'
         %
     :- pred set_unordlist.power_intersect(set_unordlist(set_unordlist(T))::in,
         set_unordlist(T)::out) is det.

     :- func set_unordlist.power_intersect(set_unordlist(set_unordlist(T)))
         = set_unordlist(T).

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

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

     :- func set_unordlist.difference(set_unordlist(T), set_unordlist(T))
         = set_unordlist(T).

     :- func set_unordlist.count(set_unordlist(T)) = int.
     :- pred set_unordlist.count(set_unordlist(T)::in, int::out) is det.

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

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

     :- func set_unordlist.fold(func(T1, T2) = T2, set_unordlist(T1), T2) = T2.
     :- pred set_unordlist.fold(pred(T1, T2, T2), set_unordlist(T1), T2, T2).
     :- mode set_unordlist.fold(pred(in, in, out) is det, in, in, out) is det.
     :- mode set_unordlist.fold(pred(in, mdi, muo) is det, in, mdi, muo) is det.
     :- mode set_unordlist.fold(pred(in, di, uo) is det, in, di, uo) is det.
     :- mode set_unordlist.fold(pred(in, in, out) is semidet, in, in, out)
         is semidet.
     :- mode set_unordlist.fold(pred(in, mdi, muo) is semidet, in, mdi, muo)
         is semidet.
     :- mode set_unordlist.fold(pred(in, di, uo) is semidet, in, di, uo)
         is semidet.

     :- pred set_unordlist.fold2(pred(T1, T2, T2, T3, T3), set_unordlist(T1),
         T2, T2, T3, T3).
     :- mode set_unordlist.fold2(pred(in, in, out, in, out) is det, in,
         in, out, in, out) is det.
     :- mode set_unordlist.fold2(pred(in, in, out, mdi, muo) is det, in,
         in, out, mdi, muo) is det.
     :- mode set_unordlist.fold2(pred(in, in, out, di, uo) is det, in,
         in, out, di, uo) is det.
     :- mode set_unordlist.fold2(pred(in, in, out, in, out) is semidet, in,
         in, out, in, out) is semidet.
     :- mode set_unordlist.fold2(pred(in, in, out, mdi, muo) is semidet, in,
         in, out, mdi, muo) is semidet.
     :- mode set_unordlist.fold2(pred(in, in, out, di, uo) is semidet, in,
         in, out, di, uo) is semidet.

     :- pred set_unordlist.fold3(pred(T1, T2, T2, T3, T3, T4, T4),
         set_unordlist(T1), T2, T2, T3, T3, T4, T4).
     :- mode set_unordlist.fold3(pred(in, in, out, in, out, in, out) is det, in,
         in, out, in, out, in, out) is det.
     :- mode set_unordlist.fold3(pred(in, in, out, in, out, mdi, muo) is det, in,
         in, out, in, out, mdi, muo) is det.
     :- mode set_unordlist.fold3(pred(in, in, out, in, out, di, uo) is det, in,
         in, out, in, out, di, uo) is det.
     :- mode set_unordlist.fold3(pred(in, in, out, in, out, in, out) is semidet, in,
         in, out, in, out, in, out) is semidet.
     :- mode set_unordlist.fold3(pred(in, in, out, in, out, mdi, muo) is semidet, in,
         in, out, in, out, mdi, muo) is semidet.
     :- mode set_unordlist.fold3(pred(in, in, out, in, out, di, uo) is semidet, in,
         in, out, in, out, di, uo) is semidet.

     :- pred set_unordlist.fold4(pred(T1, T2, T2, T3, T3, T4, T4, T5, T5),
         set_unordlist(T1), T2, T2, T3, T3, T4, T4, T5, T5).
     :- mode set_unordlist.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_unordlist.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_unordlist.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_unordlist.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_unordlist.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_unordlist.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_unordlist.fold5(
         pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6),
         set_unordlist(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6).
     :- mode set_unordlist.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_unordlist.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_unordlist.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_unordlist.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_unordlist.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_unordlist.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_unordlist.fold6(
         pred(T1, T2, T2, T3, T3, T4, T4, T5, T5, T6, T6, T7, T7),
         set_unordlist(T1), T2, T2, T3, T3, T4, T4, T5, T5, T6, T6, T7, T7).
     :- mode set_unordlist.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_unordlist.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_unordlist.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_unordlist.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_unordlist.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_unordlist.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.

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

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

         % set_unordlist.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 set_unordlist.divide(pred(T)::in(pred(in) is semidet),
         set_unordlist(T)::in, set_unordlist(T)::out, set_unordlist(T)::out) is det.

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


File: mercury_library.info,  Node: solutions,  Next: sparse_bitset,  Prev: set_unordlist,  Up: Top

66 solutions
************

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 1994-2007 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: solutions.m.
     % Main author: fjh.
     % Stability: medium.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module solutions.
     :- interface.

     :- import_module bool.
     :- import_module list.
     :- import_module set.

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

         % solutions/2 collects all the solutions to a predicate and returns
         % them as a list in sorted order, with duplicates removed.
         % solutions_set/2 returns them as a set.  unsorted_solutions/2 returns
         % them as an unsorted list with possible duplicates; since there are
         % an infinite number of such lists, this must be called from a context
         % in which only a single solution is required.
         %
     :- pred solutions(pred(T), list(T)).
     :- mode solutions(pred(out) is multi, out(non_empty_list)) is det.
     :- mode solutions(pred(out) is nondet, out) is det.

     :- func solutions(pred(T)) = list(T).
     :- mode solutions(pred(out) is multi) = out(non_empty_list) is det.
     :- mode solutions(pred(out) is nondet) = out is det.

     :- func solutions_set(pred(T)) = set(T).
     :- mode solutions_set(pred(out) is multi) = out is det.
     :- mode solutions_set(pred(out) is nondet) = out is det.

     :- pred solutions_set(pred(T), set(T)).
     :- mode solutions_set(pred(out) is multi, out) is det.
     :- mode solutions_set(pred(out) is nondet, out) is det.

     :- pred unsorted_solutions(pred(T), list(T)).
     :- mode unsorted_solutions(pred(out) is multi, out(non_empty_list))
         is cc_multi.
     :- mode unsorted_solutions(pred(out) is nondet, out) is cc_multi.

     :- func aggregate(pred(T), func(T, U) = U, U) = U.
     :- mode aggregate(pred(out) is multi, func(in, in) = out is det, in)
         = out is det.
     :- mode aggregate(pred(out) is nondet, func(in, in) = out is det, in)
         = out is det.

         % aggregate/4 generates all the solutions to a predicate,
         % sorts them and removes duplicates, then applies an accumulator
         % predicate to each solution in turn:
         %
         % aggregate(Generator, Accumulator, Acc0, Acc) <=>
         %   solutions(Generator, Solutions),
         %   list.foldl(Accumulator, Solutions, Acc0, Acc).
         %
     :- pred aggregate(pred(T), pred(T, U, U), U, U).
     :- mode aggregate(pred(out) is multi, pred(in, in, out) is det,
         in, out) is det.
     :- mode aggregate(pred(out) is multi, pred(in, di, uo) is det,
         di, uo) is det.
     :- mode aggregate(pred(out) is nondet, pred(in, di, uo) is det,
         di, uo) is det.
     :- mode aggregate(pred(out) is nondet, pred(in, in, out) is det,
         in, out) is det.

         % aggregate2/6 generates all the solutions to a predicate,
         % sorts them and removes duplicates, then applies an accumulator
         % predicate to each solution in turn:
         %
         % aggregate2(Generator, Accumulator, AccA0, AccA, AccB0, AccB) <=>
         %   solutions(Generator, Solutions),
         %   list.foldl2(Accumulator, Solutions, AccA0, AccA, AccB0, AccB).
         %
     :- pred aggregate2(pred(T), pred(T, U, U, V, V), U, U, V, V).
     :- mode aggregate2(pred(out) is multi, pred(in, in, out, in, out) is det,
         in, out, in, out) is det.
     :- mode aggregate2(pred(out) is multi, pred(in, in, out, di, uo) is det,
         in, out, di, uo) is det.
     :- mode aggregate2(pred(out) is nondet, pred(in, in, out, di, uo) is det,
         in, out, di, uo) is det.
     :- mode aggregate2(pred(out) is nondet, pred(in, in, out, in, out) is det,
         in, out, in, out) is det.

         % unsorted_aggregate/4 generates all the solutions to a predicate
         % and applies an accumulator predicate to each solution in turn.
         % Declaratively, the specification is as follows:
         %
         % unsorted_aggregate(Generator, Accumulator, Acc0, Acc) <=>
         %   unsorted_solutions(Generator, Solutions),
         %   list.foldl(Accumulator, Solutions, Acc0, Acc).
         %
         % Operationally, however, unsorted_aggregate/4 will call the
         % Accumulator for each solution as it is obtained, rather than
         % first building a list of all the solutions.
         %
     :- pred unsorted_aggregate(pred(T), pred(T, U, U), U, U).
     :- mode unsorted_aggregate(pred(out) is multi, pred(in, in, out) is det,
         in, out) is cc_multi.
     :- mode unsorted_aggregate(pred(out) is multi, pred(in, in, out) is cc_multi,
         in, out) is cc_multi.
     :- mode unsorted_aggregate(pred(out) is multi, pred(in, di, uo) is det,
         di, uo) is cc_multi.
     :- mode unsorted_aggregate(pred(out) is multi, pred(in, di, uo) is cc_multi,
         di, uo) is cc_multi.
     :- mode unsorted_aggregate(pred(muo) is multi, pred(mdi, di, uo) is det,
         di, uo) is cc_multi.
     :- mode unsorted_aggregate(pred(out) is nondet, pred(in, di, uo) is det,
         di, uo) is cc_multi.
     :- mode unsorted_aggregate(pred(out) is nondet, pred(in, di, uo) is cc_multi,
         di, uo) is cc_multi.
     :- mode unsorted_aggregate(pred(out) is nondet, pred(in, in, out) is det,
         in, out) is cc_multi.
     :- mode unsorted_aggregate(pred(out) is nondet, pred(in, in, out) is cc_multi,
         in, out) is cc_multi.
     :- mode unsorted_aggregate(pred(muo) is nondet, pred(mdi, di, uo) is det,
         di, uo) is cc_multi.

         % unsorted_aggregate2/6 generates all the solutions to a predicate
         % and applies an accumulator predicate to each solution in turn.
         % Declaratively, the specification is as follows:
         %
         % unsorted_aggregate2(Generator, Accumulator, !Acc1, !Acc2) <=>
         %   unsorted_solutions(Generator, Solutions),
         %   list.foldl2(Accumulator, Solutions, !Acc1, !Acc2).
         %
         % Operationally, however, unsorted_aggregate2/6 will call the
         % Accumulator for each solution as it is obtained, rather than
         % first building a list of all the solutions.
         %
     :- pred unsorted_aggregate2(pred(T), pred(T, U, U, V, V), U, U, V, V).
     :- mode unsorted_aggregate2(pred(out) is multi,
         pred(in, in, out, in, out) is det, in, out, in, out) is cc_multi.
     :- mode unsorted_aggregate2(pred(out) is multi,
         pred(in, in, out, in, out) is cc_multi, in, out, in, out) is cc_multi.
     :- mode unsorted_aggregate2(pred(out) is multi,
         pred(in, in, out, di, uo) is det, in, out, di, uo) is cc_multi.
     :- mode unsorted_aggregate2(pred(out) is multi,
         pred(in, in, out, di, uo) is cc_multi, in, out, di, uo) is cc_multi.
     :- mode unsorted_aggregate2(pred(out) is nondet,
         pred(in, in, out, in, out) is det, in, out, in, out) is cc_multi.
     :- mode unsorted_aggregate2(pred(out) is nondet,
         pred(in, in, out, in, out) is cc_multi, in, out, in, out) is cc_multi.
     :- mode unsorted_aggregate2(pred(out) is nondet,
         pred(in, in, out, di, uo) is det, in, out, di, uo) is cc_multi.
     :- mode unsorted_aggregate2(pred(out) is nondet,
         pred(in, in, out, di, uo) is cc_multi, in, out, di, uo) is cc_multi.

         % This is a generalization of unsorted_aggregate which allows the
         % iteration to stop before all solutions have been found.
         % Declaratively, the specification is as follows:
         %
         %   do_while(Generator, Filter, !Acc) :-
         %       unsorted_solutions(Generator, Solutions),
         %       do_while_2(Solutions, Filter, !Acc).
         %
         %   do_while_2([], _, !Acc).
         %   do_while_2([X | Xs], Filter, !Acc) :-
         %       Filter(X, More, !Acc),
         %       ( More = yes ->
         %           do_while_2(Xs, Filter, !Acc)
         %       ;
         %           true
         %       ).
         %
         % Operationally, however, do_while/4 will call the Filter
         % predicate for each solution as it is obtained, rather than
         % first building a list of all the solutions.
         %
     :- pred do_while(pred(T), pred(T, bool, T2, T2), T2, T2).
     :- mode do_while(pred(out) is multi, pred(in, out, in, out) is det, in, out)
         is cc_multi.
     :- mode do_while(pred(out) is multi, pred(in, out, di, uo) is det, di, uo)
         is cc_multi.
     :- mode do_while(pred(out) is multi, pred(in, out, di, uo) is cc_multi, di, uo)
         is cc_multi.
     :- mode do_while(pred(out) is nondet, pred(in, out, in, out) is det, in, out)
         is cc_multi.
     :- mode do_while(pred(out) is nondet, pred(in, out, di, uo) is det, di, uo)
         is cc_multi.
     :- mode do_while(pred(out) is nondet, pred(in, out, di, uo) is cc_multi, di, uo)
         is cc_multi.

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


File: mercury_library.info,  Node: sparse_bitset,  Next: stack,  Prev: solutions,  Up: Top

67 sparse_bitset
****************

     %--------------------------------------------------%
     % vim: ts=4 sw=4 et ft=mercury
     %--------------------------------------------------%
     % Copyright (C) 2000-2007, 2011 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: sparse_bitset.m.
     % Author: stayl.
     % Stability: medium.
     %
     % This module provides an ADT for storing sets of integers.
     % If the integers stored are closely grouped, a sparse_bitset
     % is much more compact than the representation provided by set.m,
     % and the operations will be much faster.
     %
     % Efficiency notes:
     %
     % A sparse bitset is represented as a sorted list of pairs of integers.
     % For a pair `Offset - Bits', `Offset' is a multiple of `int.bits_per_int'.
     % The bits of `Bits' describe which of the elements of the range
     % `Offset' .. `Offset + bits_per_int - 1' are in the set.
     % Pairs with the same value of `Offset' are merged.
     % Pairs for which `Bits' is zero are removed.
     %
     % The values of `Offset' in the list need not be contiguous multiples
     % of `bits_per_int', hence the name _sparse_ bitset.
     %
     % A sparse_bitset is suitable for storing sets of integers which
     % can be represented using only a few `Offset - Bits' pairs.
     % In the worst case, where the integers stored are not closely
     % grouped, a sparse_bitset will take more memory than an
     % ordinary set, but the operations should not be too much slower.
     %
     % In the asymptotic complexities of the operations below,
     % `rep_size(Set)' is the number of pairs needed to represent `Set',
     % and `card(Set)' is the number of elements in `Set'.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module sparse_bitset.
     :- interface.

     :- import_module enum.
     :- import_module list.
     :- import_module term.

     :- use_module set.

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

     :- type sparse_bitset(T). % <= enum(T).

         % Return an empty set.
         %
     :- func init = sparse_bitset(T).
     :- pred init(sparse_bitset(T)::out) is det.

     :- pred empty(sparse_bitset(T)).
     :- mode empty(in) is semidet.
     :- mode empty(out) is det.

     :- pred is_empty(sparse_bitset(T)::in) is semidet.

         % `equal(SetA, SetB' is true iff `SetA' and `SetB' contain the same
         % elements. Takes O(min(rep_size(SetA), rep_size(SetB))) time.
         %
     :- pred equal(sparse_bitset(T)::in, sparse_bitset(T)::in) is semidet.

         % `list_to_set(List)' returns a set containing only the members of `List'.
         % In the worst case this will take O(length(List)^2) time and space.
         % If the elements of the list are closely grouped, it will be closer
         % to O(length(List)).
         %
     :- func list_to_set(list(T)) = sparse_bitset(T) <= enum(T).
     :- pred list_to_set(list(T)::in, sparse_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)) = sparse_bitset(T) <= enum(T).
     :- pred sorted_list_to_set(list(T)::in, sparse_bitset(T)::out)
         is det <= enum(T).

         % `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)) = sparse_bitset(T) <= enum(T).

         % `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(sparse_bitset(T)) = list(T) <= enum(T).
     :- pred to_sorted_list(sparse_bitset(T)::in, list(T)::out) is det <= 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(sparse_bitset(T)) = set.set(T) <= enum(T).

         % `make_singleton_set(Elem)' returns a set containing just the single
         % element `Elem'.
         %
     :- func make_singleton_set(T) = sparse_bitset(T) <= enum(T).

         % Note: set.m contains the reverse mode of this predicate, but it is
         % difficult to implement both modes using the representation in this
         % module.
         %
     :- pred singleton_set(sparse_bitset(T)::out, T::in) is det <= 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(sparse_bitset(T)::in, sparse_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(sparse_bitset(T)::in, sparse_bitset(T)::in) is semidet.

         % `contains(Set, X)' is true iff `X' is a member of `Set'.
         % Takes O(rep_size(Set)) time.
         %
     :- pred contains(sparse_bitset(T)::in, T::in) is semidet <= enum(T).

         % `member(X, Set)' is true iff `X' is a member of `Set'.
         % Takes O(rep_size(Set)) time.
         %
     :- pred member(T, sparse_bitset(T)) <= enum(T).
     :- mode member(in, in) is semidet.
     :- mode member(out, in) is nondet.

         % `insert(Set, X)' returns the union of `Set' and the set containing
         % only `X'. Takes O(rep_size(Set)) time and space.
         %
     :- func insert(sparse_bitset(T), T) = sparse_bitset(T) <= enum(T).
     :- pred insert(T::in, sparse_bitset(T)::in, sparse_bitset(T)::out)
         is det <= 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(sparse_bitset(T), list(T)) = sparse_bitset(T) <= enum(T).
     :- pred insert_list(list(T)::in, sparse_bitset(T)::in, sparse_bitset(T)::out)
         is det <= enum(T).

         % `delete(Set, X)' returns the difference of `Set' and the set containing
         % only `X'. Takes O(rep_size(Set)) time and space.
         %
     :- func delete(sparse_bitset(T), T) = sparse_bitset(T) <= enum(T).
     :- pred delete(T::in, sparse_bitset(T)::in, sparse_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(sparse_bitset(T), list(T)) = sparse_bitset(T) <= enum(T).
     :- pred delete_list(list(T)::in, sparse_bitset(T)::in, sparse_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(rep_size(Set)) time and space.
         %
     :- pred remove(T::in, sparse_bitset(T)::in, sparse_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, sparse_bitset(T)::in, sparse_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'.
         %
     :- func remove_leq(sparse_bitset(T), T) = sparse_bitset(T) <= enum(T).
     :- pred remove_leq(T::in, sparse_bitset(T)::in, sparse_bitset(T)::out)
         is det <= 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'.
         %
     :- func remove_gt(sparse_bitset(T), T) = sparse_bitset(T) <= enum(T).
     :- pred remove_gt(T::in, sparse_bitset(T)::in, sparse_bitset(T)::out)
         is det <= 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, sparse_bitset(T)::in, sparse_bitset(T)::out)
         is semidet <= enum(T).

         % `union(SetA, SetB)' returns the union of `SetA' and `SetB'. The
         % efficiency of the union operation is not sensitive to the argument
         % ordering. Takes O(rep_size(SetA) + rep_size(SetB)) time and space.
         %
     :- func union(sparse_bitset(T), sparse_bitset(T)) = sparse_bitset(T).
     :- pred union(sparse_bitset(T)::in, sparse_bitset(T)::in,
         sparse_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 O(rep_size(SetA) + rep_size(SetB)) time and
         % O(min(rep_size(SetA)), rep_size(SetB)) space.
         %
     :- func intersect(sparse_bitset(T), sparse_bitset(T)) = sparse_bitset(T).
     :- pred intersect(sparse_bitset(T)::in, sparse_bitset(T)::in,
         sparse_bitset(T)::out) is det.

         % `difference(SetA, SetB)' returns the set containing all the elements
         % of `SetA' except those that occur in `SetB'. Takes
         % O(rep_size(SetA) + rep_size(SetB)) time and O(rep_size(SetA)) space.
         %
     :- func difference(sparse_bitset(T), sparse_bitset(T)) = sparse_bitset(T).
     :- pred difference(sparse_bitset(T)::in, sparse_bitset(T)::in,
         sparse_bitset(T)::out) is det.

         % `count(Set)' returns the number of elements in `Set'.
         % Takes O(card(Set)) time.
         %
     :- func count(sparse_bitset(T)) = int <= enum(T).

         % `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, sparse_bitset(T), U) = U <= enum(T).

     :- pred foldl(pred(T, U, U), sparse_bitset(T), U, U) <= enum(T).
     :- mode foldl(pred(in, di, uo) is det, in, di, uo) is det.
     :- mode foldl(pred(in, in, out) is det, in, in, out) is det.
     :- mode foldl(pred(in, in, out) is semidet, in, in, out) is semidet.
     :- mode foldl(pred(in, in, out) is nondet, in, in, out) 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), sparse_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, sparse_bitset(T), U) = U <= enum(T).

     :- pred foldr(pred(T, U, U), sparse_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), sparse_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.

         % `filter(Pred, Set) = TrueSet' returns the elements of Set for which
         % Pred succeeds.
         %
     :- func filter(pred(T), sparse_bitset(T)) = sparse_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), sparse_bitset(T), sparse_bitset(T), sparse_bitset(T))
         <= enum(T).
     :- mode filter(pred(in) is semidet, in, out, out) is det.

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


File: mercury_library.info,  Node: stack,  Next: std_util,  Prev: sparse_bitset,  Up: Top

68 stack
********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 1994-1995, 1997-1999, 2005-2006, 2011 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: stack.m.
     % Main author: fjh.
     % Stability: high.
     %
     % This file contains a `stack' ADT.
     % Stacks are implemented here using lists.
     %
     %--------------------------------------------------%

     :- module stack.
     :- interface.
     :- import_module list.

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

     :- type stack(T).

     	% `stack.init(Stack)' is true iff `Stack' is an empty stack.
     	%
     :- pred stack.init(stack(T)::out) is det.
     :- func stack.init = stack(T).

     	% `stack.is_empty(Stack)' is true iff `Stack' is an empty stack.
     	%
     :- pred stack.is_empty(stack(T)::in) is semidet.

     	% `stack.is_full(Stack)' is intended to be true iff `Stack'
     	% is a stack whose capacity is exhausted.  This implementation
     	% allows arbitrary-sized stacks, so stack.is_full always fails.
     	%
     :- pred stack.is_full(stack(T)::in) is semidet.

     	% `stack.push(Stack0, Elem, Stack)' is true iff `Stack' is
     	% the stack which results from pushing `Elem' onto the top
     	% of `Stack0'.
     	%
     :- pred stack.push(stack(T)::in, T::in, stack(T)::out) is det.
     :- func stack.push(stack(T), T) = stack(T).

     	% `stack.push_list(Stack0, Elems, Stack)' is true iff `Stack'
     	% is the stack which results from pushing the elements of the
     	% list `Elems' onto the top of `Stack0'.
     	%
     :- pred stack.push_list(stack(T)::in, list(T)::in, stack(T)::out) is det.
     :- func stack.push_list(stack(T), list(T)) = stack(T).

     	% `stack.top(Stack, Elem)' is true iff `Stack' is a non-empty
     	% stack whose top element is `Elem'.
     	%
     :- pred stack.top(stack(T)::in, T::out) is semidet.

     	% `stack.det_top' is like `stack.top' except that it will
     	% call error/1 rather than failing if given an empty stack.
     	%
     :- pred stack.det_top(stack(T)::in, T::out) is det.
     :- func stack.det_top(stack(T)) = T.

         % Obsolete synonyms for the above.
         %
     :- pragma obsolete(stack.top_det/2).
     :- pred stack.top_det(stack(T)::in, T::out) is det.
     :- pragma obsolete(stack.top_det/1).
     :- func stack.top_det(stack(T)) = T.

     	% `stack.pop(Stack0, Elem, Stack)' is true iff `Stack0' is
     	% a non-empty stack whose top element is `Elem', and `Stack'
     	% the stack which results from popping `Elem' off `Stack0'.
     	%
     :- pred stack.pop(stack(T)::in, T::out, stack(T)::out) is semidet.

     	% `stack.det_pop' is like `stack.pop' except that it will
     	% call error/1 rather than failing if given an empty stack.
     	%
     :- pred stack.det_pop(stack(T)::in, T::out, stack(T)::out) is det.
     :- pragma obsolete(stack.pop_det/3).
     :- pred stack.pop_det(stack(T)::in, T::out, stack(T)::out) is det.

     	% `stack.depth(Stack, Depth)' is true iff `Stack' is a stack
     	% containing `Depth' elements.
     	%
     :- pred stack.depth(stack(T)::in, int::out) is det.
     :- func stack.depth(stack(T)) = int.

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


File: mercury_library.info,  Node: std_util,  Next: store,  Prev: stack,  Up: Top

69 std_util
***********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 1994-2006, 2008 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: std_util.m.
     % Main author: fjh.
     % Stability: high.
     %
     % This file contains higher-order programming constructs and other
     % useful standard utilities.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module std_util.
     :- interface.

     :- import_module maybe.

     %--------------------------------------------------%
     %
     % General purpose higher-order programming constructs
     %

         % compose(F, G, X) = F(G(X))
         %
         % Function composition.
         % XXX It would be nice to have infix `o' or somesuch for this.
         %
     :- func compose(func(T2) = T3, func(T1) = T2, T1) = T3.

         % converse(F, X, Y) = F(Y, X).
         %
     :- func converse(func(T1, T2) = T3, T2, T1) = T3.

         % pow(F, N, X) = F^N(X)
         %
         % Function exponentiation.
         %
     :- func pow(func(T) = T, int, T) = T.

         % The identity function.
         %
     :- func id(T) = T.

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

         % maybe_pred(Pred, X, Y) takes a closure Pred which transforms an
         % input semideterministically. If calling the closure with the input
         % X succeeds, Y is bound to `yes(Z)' where Z is the output of the
         % call, or to `no' if the call fails.
         %
     :- pred maybe_pred(pred(T1, T2), T1, maybe(T2)).
     :- mode maybe_pred(pred(in, out) is semidet, in, out) is det.

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

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

         % isnt(Pred, X) <=> not Pred(X)
         %
         % This is useful in higher order programming, e.g.
         %   Odds  = list.filter(odd, Xs)
         %   Evens = list.filter(isnt(odd), Xs)
         %
     :- pred isnt(pred(T)::in(pred(in) is semidet), T::in) is semidet.

         % negate(Pred) <=> not Pred
         %
         % This is useful in higher order programming, e.g.
         %   expect(negate(Pred), ...)
         %
     :- pred negate((pred)::in((pred) is semidet)) is semidet.

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


File: mercury_library.info,  Node: store,  Next: stream,  Prev: std_util,  Up: Top

70 store
********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 1994-1997, 2000-2008, 2010-2011 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: store.m.
     % Main author: fjh.
     % Stability: low.
     %
     % This file provides facilities for manipulating mutable stores.
     % A store can be considered a mapping from abstract keys to their values.
     % A store holds a set of nodes, each of which may contain a value of any
     % type.
     %
     % Stores may be used to implement cyclic data structures such as circular
     % linked lists, etc.
     %
     % Stores can have two different sorts of keys:
     % mutable variables (mutvars) and references (refs).
     % The difference between mutvars and refs is that mutvars can only be updated
     % atomically, whereas it is possible to update individual fields of a
     % reference one at a time (presuming the reference refers to a structured
     % term).
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module store.
     :- interface.

     :- import_module io.

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

         % Stores and keys are indexed by a type S of typeclass store(S) that
         % is used to distinguish between different stores.  By using an
         % existential type declaration for store.new (see below), we use the
         % type system to ensure at compile time that you never attempt to use
         % a key from one store to access a different store.
         %
     :- typeclass store(T) where [].
     :- type store(S).

     :- instance store(io.state).
     :- instance store(store(S)).

         % Initialize a new store.
         %
     :- some [S] pred store.init(store(S)::uo) is det.

         % A synonym for the above.
         %
     :- pragma obsolete(store.new/1).
     :- some [S] pred store.new(store(S)::uo) is det.

     %--------------------------------------------------%
     %
     % Mutvars
     %

         % generic_mutvar(T, S):
         % A mutable variable holding a value of type T in store S.
         %
     :- type generic_mutvar(T, S).
     :- type io_mutvar(T) == generic_mutvar(T, io.state).
     :- type store_mutvar(T, S) == generic_mutvar(T, store(S)).

         % Create a new mutable variable, initialized with the specified value.
         %
     :- pred store.new_mutvar(T::in, generic_mutvar(T, S)::out, S::di, S::uo)
         is det <= store(S).

         % copy_mutvar(OldMutvar, NewMutvar, S0, S) is equivalent to the sequence
         %   get_mutvar(OldMutvar, Value, S0, S1),
         %   new_mutvar(NewMutvar, Value, S1, S )
         %
     :- pred store.copy_mutvar(generic_mutvar(T, S)::in, generic_mutvar(T, S)::out,
         S::di, S::uo) is det <= store(S).

         % Lookup the value stored in a given mutable variable.
         %
     :- pred store.get_mutvar(generic_mutvar(T, S)::in, T::out,
         S::di, S::uo) is det <= store(S).

         % Replace the value stored in a given mutable variable.
         %
     :- pred store.set_mutvar(generic_mutvar(T, S)::in, T::in,
         S::di, S::uo) is det <= store(S).

         % new_cyclic_mutvar(Func, Mutvar):
         %
         % Create a new mutable variable, whose value is initialized
         % with the value returned from the specified function `Func'.
         % The argument passed to the function is the mutvar itself,
         % whose value has not yet been initialized (this is safe
         % because the function does not get passed the store, so
         % it can't examine the uninitialized value).
         %
         % This predicate is useful for creating self-referential values
         % such as circular linked lists.
         % For example:
         %
         %   :- type clist(T, S) ---> node(T, mutvar(clist(T, S))).
         %
         %   :- pred init_cl(T::in, clist(T, S)::out,
         %       store(S)::di, store(S)::uo) is det.
         %
         %   init_cl(X, CList, !Store) :-
         %       store.new_cyclic_mutvar(func(CL) = node(X, CL), CList,
         %       !Store).
         %
     :- pred store.new_cyclic_mutvar((func(generic_mutvar(T, S)) = T)::in,
         generic_mutvar(T, S)::out, S::di, S::uo) is det <= store(S).

     %--------------------------------------------------%
     %
     % References
     %

         % generic_ref(T, S):
         %
         % A reference to value of type T in store S.
         %
     :- type generic_ref(T, S).
     :- type io_ref(T, S) == generic_ref(T, io.state).
     :- type store_ref(T, S) == generic_ref(T, store(S)).

         % new_ref(Val, Ref):
         %   /* In C: Ref = malloc(...); *Ref = Val; */
         %
         % Given a value of any type `T', insert a copy of the term
         % into the store and return a new reference to that term.
         % (This does not actually perform a copy, it just returns a view
         % of the representation of that value.
         % It does however allocate one cell to hold the reference;
         % you can use new_arg_ref to avoid that.)
         %
     :- pred store.new_ref(T::di, generic_ref(T, S)::out,
         S::di, S::uo) is det <= store(S).

         % ref_functor(Ref, Functor, Arity):
         %
         % Given a reference to a term, return the functor and arity
         % of that term.
         %
     :- pred store.ref_functor(generic_ref(T, S)::in, string::out, int::out,
         S::di, S::uo) is det <= store(S).

         % arg_ref(Ref, ArgNum, ArgRef):
         %   /* Pseudo-C code: ArgRef = &Ref[ArgNum]; */
         %
         % Given a reference to a term, return a reference to
         % the specified argument (field) of that term
         % (argument numbers start from zero).
         % It is an error if the argument number is out of range,
         % or if the argument reference has the wrong type.
         %
     :- pred store.arg_ref(generic_ref(T, S)::in, int::in,
         generic_ref(ArgT, S)::out, S::di, S::uo) is det <= store(S).

         % new_arg_ref(Val, ArgNum, ArgRef):
         %   /* Pseudo-C code: ArgRef = &Val[ArgNum]; */
         %
         % Equivalent to `new_ref(Val, Ref), arg_ref(Ref, ArgNum, ArgRef)',
         % except that it is more efficient.
         % It is an error if the argument number is out of range,
         % or if the argument reference has the wrong type.
         %
     :- pred store.new_arg_ref(T::di, int::in, generic_ref(ArgT, S)::out,
         S::di, S::uo) is det <= store(S).

         % set_ref(Ref, ValueRef):
         %   /* Pseudo-C code: *Ref = *ValueRef; */
         %
         % Given a reference to a term (Ref),
         % a reference to another term (ValueRef),
         % update the store so that the term referred to by Ref
         % is replaced with the term referenced by ValueRef.
         %
     :- pred store.set_ref(generic_ref(T, S)::in, generic_ref(T, S)::in,
         S::di, S::uo) is det <= store(S).

         % set_ref_value(Ref, Value):
         %   /* Pseudo-C code: *Ref = Value; */
         %
         % Given a reference to a term (Ref), and a value (Value),
         % update the store so that the term referred to by Ref
         % is replaced with Value.
         %
     :- pred store.set_ref_value(generic_ref(T, S)::in, T::di,
         S::di, S::uo) is det <= store(S).

         % Given a reference to a term, return that term.
         % Note that this requires making a copy, so this pred may
         % be inefficient if used to return large terms; it
         % is most efficient with atomic terms.
         % XXX current implementation buggy (does shallow copy)
         %
     :- pred store.copy_ref_value(generic_ref(T, S)::in, T::uo,
         S::di, S::uo) is det <= store(S).

         % Same as above, but without making a copy. Destroys the store.
         %
     :- pred store.extract_ref_value(S::di, generic_ref(T, S)::in, T::out)
         is det <= store(S).

     %--------------------------------------------------%
     %
     % Nasty performance hacks
     %
     % WARNING: use of these procedures is dangerous!
     % Use them only as a last resort, only if performance is critical, and only if
     % profiling shows that using the safe versions is a bottleneck.
     %
     % These procedures may vanish in some future version of Mercury.

         % `unsafe_arg_ref' is the same as `arg_ref',
         % and `unsafe_new_arg_ref' is the same as `new_arg_ref'
         % except that they doesn't check for errors,
         % and they don't work for `no_tag' types (types with
         % exactly one functor which has exactly one argument),
         % and they don't work for types with >4 functors.
         % If the argument number is out of range,
         % or if the argument reference has the wrong type,
         % or if the argument is a `no_tag' type,
         % then the behaviour is undefined, and probably harmful.

     :- pred store.unsafe_arg_ref(generic_ref(T, S)::in, int::in,
         generic_ref(ArgT, S)::out, S::di, S::uo) is det <= store(S).

     :- pred store.unsafe_new_arg_ref(T::di, int::in, generic_ref(ArgT, S)::out,
         S::di, S::uo) is det <= store(S).

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


File: mercury_library.info,  Node: stream,  Next: stream.string_writer,  Prev: store,  Up: Top

71 stream
*********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et
     %--------------------------------------------------%
     % Copyright (C) 2006-2007, 2010 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: stream.m.
     % Authors: juliensf, maclarty.
     % Stability: low
     %
     % This module provides a family of typeclasses for defining streams
     % in Mercury.  It also provides some generic predicates that operate
     % on instances of these typeclasses.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module stream.
     :- interface.

     :- import_module bool.
     :- import_module char.
     :- import_module list.

     :- include_module string_writer.

     %--------------------------------------------------%
     %
     % Types used by streams.
     %

     :- type stream.name == string.

     :- type stream.result(Error)
         --->    ok
         ;       eof
         ;       error(Error).

     :- type stream.result(T, Error)
         --->    ok(T)
         ;       eof
         ;       error(Error).

     :- type stream.res(Error)
         --->    ok
         ;       error(Error).

     :- type stream.res(T, Error)
         --->    ok(T)
         ;       error(Error).

         % stream.maybe_partial_res is used when it is possible to return
         % a partial result when an error occurs.
         %
     :- type stream.maybe_partial_res(T, Error)
         --->    ok(T)
         ;       error(T, Error).

     %--------------------------------------------------%
     %
     % Stream errors.
     %

     :- typeclass stream.error(Error) where
     [

         % Convert a stream error into a human-readable format.
         % e.g. for use in error messages.
         %
         func error_message(Error) = string
     ].

     %--------------------------------------------------%
     %
     % Streams.
     %

         % A stream consists of a handle type and a state type.
         % The state type is threaded through, and destructively updated by,
         % the stream operations.
         %
     :- typeclass stream.stream(Stream, State) <= (Stream -> State) where
     [
             % Returns a descriptive name for the stream.
             % Intended for use in error messages.
             %
             pred name(Stream::in, stream.name::out, State::di, State::uo) is det
     ].

     %--------------------------------------------------%
     %
     % Input streams.
     %

         % An input stream is a source of data.
         %
     :- typeclass stream.input(Stream, State) <= stream(Stream, State) where [].

         % A reader stream is a subclass of specific input stream that can be
         % used to read data of a specific type from that input stream.
         % A single input stream can support multiple reader subclasses.
         %
     :- typeclass stream.reader(Stream, Unit, State, Error)
         <= (stream.input(Stream, State), stream.error(Error),
             (Stream, Unit -> Error)) where
     [
         % Get the next unit from the given stream.
         %
         % The get operation should block until the next unit is available,
         % or the end of the stream or an error is detected.
         %
         % If a call to get/4 returns `eof', all further calls to get/4 or
         % bulk_get/9 for that stream return `eof'.  If a call to get/4
         % returns `error(...)', all further calls to get/4 or bulk_get/4 for
         % that stream return an error, although not necessarily the same one.
         %
         % XXX We should provide an interface to allow the user to reset the
         % error status to try again if an error is transient.
         %
         pred get(Stream::in, stream.result(Unit, Error)::out,
             State::di, State::uo) is det
     ].

         % A bulk_reader stream is a subclass of specific input stream that can
         % be used to read multiple items of data of a specific type from that
         % input stream into a specified container.  For example, binary input
         % streams may be able to efficiently read bytes into a bitmap.
         % A single input stream can support multiple bulk_reader subclasses.
         %
     :- typeclass stream.bulk_reader(Stream, Index, Store, State, Error)
         <= (stream.input(Stream, State), stream.error(Error),
             (Stream, Index, Store -> Error)) where
     [
         % bulk_get(Stream, Index, NumItems, !Store, NumItemsRead, Result, !State).
         %
         % Read at most NumItems items into the given Store starting at the
         % given index, returning the number of items read.
         %
         % If the read succeeds, Result is `ok' and NumItemsRead equals NumItems.
         %
         % On end-of-stream, bulk_get/9 puts as many items as it can into !Store.
         % NumItemsRead is less than NumItems, and Result is `ok'.
         %
         % If an error is detected, bulk_get/9 puts as many items as it can into
         % !Store.  NumItemsRead is less than NumItems, and Result is `error(Err)'.
         %
         % Blocks until NumItems items are available or the end of the stream
         % is reached or an error is detected.
         %
         % Throws an exception if Index given is out of range or NumItems units
         % starting at Index will not fit in !Store.
         %
         % If a call to bulk_get/4 returns less than NumItems items, all further
         % calls to get/4 or bulk_get/4 for that stream return no items.  If a
         % call to bulk_get/9 returns `error(...)', all further calls to get/4
         % or bulk_get/9 for that stream return an error, although not necessarily
         % the same one.
         %
         pred bulk_get(Stream::in, Index::in, int::in,
             Store::bulk_get_di, Store::bulk_get_uo,
             int::out, stream.res(Error)::out, State::di, State::uo) is det
     ].

         % XXX These should be di and uo, but with the current state of the mode
         % system an unsafe_promise_unique call would be required at each call
         % to bulk_get.
     :- mode bulk_get_di == in.
     :- mode bulk_get_uo == out.

     %--------------------------------------------------%
     %
     % Output streams.
     %

         % An output stream is a destination for data.
         % Note that unlike input streams, output streams do not include
         % an explicit error type.  They should handle errors by throwing
         % exceptions.
         %
     :- typeclass stream.output(Stream, State)
         <= stream(Stream, State) where
     [
         % For buffered output streams completely write out any data in the
         % buffer.  For unbuffered streams this operation is a no-op.
         %
         pred flush(Stream::in, State::di, State::uo) is det
     ].

         % A writer stream is a subclass of specific output stream that can be
         % used to write data of a specific type to that output stream.
         % A single output stream can support multiple writer subclasses.
         %
     :- typeclass stream.writer(Stream, Unit, State)
         <= stream.output(Stream, State) where
     [
         % Write the next unit to the given stream.
         % Blocks if the whole unit can't be written to the stream at the time
         % of the call (for example because a buffer is full).
         %
         pred put(Stream::in, Unit::in, State::di, State::uo) is det
     ].

     %--------------------------------------------------%
     %
     % Duplex streams.
     %

         % A duplex stream is a stream that can act as both a source
         % and destination of data, i.e. it is a both an input and
         % an output stream.
         %
     :- typeclass stream.duplex(Stream, State)
         <= (stream.input(Stream, State), stream.output(Stream, State))
             where [].

     %--------------------------------------------------%
     %
     % Putback streams.
     %

         % A putback stream is an input stream that allows data to be
         % pushed back onto the stream.  As with reader subclasses it is
         % possible to define multiple putback subclasses for a
         % single input stream.
         %
     :- typeclass stream.putback(Stream, Unit, State, Error)
         <= stream.reader(Stream, Unit, State, Error) where
     [
         % Un-gets a unit from the specified input stream.
         % Only one unit of putback is guaranteed to be successful.
         %
         pred unget(Stream::in, Unit::in, State::di, State::uo) is det
     ].

         % As above but guarantees that an unlimited number of units may
         % be pushed back onto the stream.
         %
     :- typeclass stream.unbounded_putback(Stream, Unit, State, Error)
         <= stream.putback(Stream, Unit, State, Error) where [].

     %--------------------------------------------------%
     %
     % Seekable streams.
     %

         % stream.whence denotes the base for a seek operation.
         %   set - seek relative to the start of the file
         %   cur - seek relative to the current position in the file
         %   end - seek relative to the end of the file.
         %
     :- type stream.whence
         --->    set
         ;       cur
         ;       end.

     :- typeclass stream.seekable(Stream, State) <= stream(Stream, State)
         where
     [
         % Seek to an offset relative to whence on the specified stream.
         % The offset is measured in bytes.
         %
         pred seek(Stream::in, stream.whence::in, int::in, State::di, State::uo)
             is det
     ].

     %--------------------------------------------------%
     %
     % Line oriented streams.
     %

         % A line oriented stream is a stream that keeps track of line numbers.
         %
     :- typeclass stream.line_oriented(Stream, State) <= stream(Stream, State)
         where
     [
         % Get the current line number for the specified stream.
         %
         pred get_line(Stream::in, int::out, State::di, State::uo) is det,

         % Set the current line number of the specified stream.
         %
         pred set_line(Stream::in, int::in,  State::di, State::uo) is det
     ].

     %--------------------------------------------------%
     %
     % Generic folds over input streams.
     %

         % Applies the given closure to each Unit read from the input stream
         % in turn, until eof or error.
         %
     :- pred stream.input_stream_fold(Stream, pred(Unit, T, T), T,
         stream.maybe_partial_res(T, Error), State, State)
         <= stream.reader(Stream, Unit, State, Error).
     :- mode stream.input_stream_fold(in, in(pred(in, in, out) is det),
         in, out, di, uo) is det.
     :- mode stream.input_stream_fold(in, in(pred(in, in, out) is cc_multi),
         in, out, di, uo) is cc_multi.

         % Applies the given closure to each Unit read from the input stream
         % in turn, until eof or error.
         %
     :- pred stream.input_stream_fold_state(Stream, pred(Unit, State, State),
         stream.res(Error), State, State)
         <= stream.reader(Stream, Unit, State, Error).
     :- mode stream.input_stream_fold_state(in, in(pred(in, di, uo) is det),
         out, di, uo) is det.
     :- mode stream.input_stream_fold_state(in, in(pred(in, di, uo) is cc_multi),
         out, di, uo) is cc_multi.

         % Applies the given closure to each Unit read from the input stream
         % in turn, until eof or error.
         %
     :- pred stream.input_stream_fold2_state(Stream,
         pred(Unit, T, T, State, State), T, stream.maybe_partial_res(T, Error),
         State, State) <= stream.reader(Stream, Unit, State, Error).
     :- mode stream.input_stream_fold2_state(in,
         in(pred(in, in, out, di, uo) is det),
         in, out, di, uo) is det.
     :- mode stream.input_stream_fold2_state(in,
         in(pred(in, in, out, di, uo) is cc_multi),
         in, out, di, uo) is cc_multi.

         % Applies the given closure to each Unit read from the input stream
         % in turn, until eof or error, or the closure returns `no' as its
         % second argument.
         %
     :- pred stream.input_stream_fold2_state_maybe_stop(Stream,
         pred(Unit, bool, T, T, State, State),
         T, stream.maybe_partial_res(T, Error), State, State)
         <= stream.reader(Stream, Unit, State, Error).
     :- mode stream.input_stream_fold2_state_maybe_stop(in,
         in(pred(in, out, in, out, di, uo) is det), in, out, di, uo) is det.
     :- mode stream.input_stream_fold2_state_maybe_stop(in,
         in(pred(in, out, in, out, di, uo) is cc_multi), in, out, di, uo)
         is cc_multi.

     %--------------------------------------------------%
     %
     % Misc. operations on input streams.
     %

         % Discard all the whitespace from the specified stream.
         %
     :- pred stream.ignore_whitespace(Stream::in, stream.result(Error)::out,
         State::di, State::uo)
         is det <= stream.putback(Stream, char, State, Error).

     %--------------------------------------------------%
     %
     % Misc. operations on output streams.
     %

         % put_list(Stream, Write, Sep, List, !State).
         %
         % Write all the elements List to Stream separated by Sep.
         %
     :- pred put_list(Stream, pred(Stream, T, State, State),
         pred(Stream, State, State), list(T), State, State)
         <= stream.output(Stream, State).
     :- mode put_list(in, pred(in, in, di, uo) is det, pred(in, di, uo) is det,
         in, di, uo) is det.
     :- mode put_list(in, pred(in, in, di, uo) is cc_multi,
         pred(in, di, uo) is cc_multi, in, di, uo) is cc_multi.
     :- mode put_list(in, pred(in, in, di, uo) is cc_multi,
         pred(in, di, uo) is det, in, di, uo) is cc_multi.

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


File: mercury_library.info,  Node: stream.string_writer,  Next: string.builder,  Prev: stream,  Up: Top

72 stream.string_writer
***********************

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et
     %--------------------------------------------------%
     % Copyright (C) 2006-2007, 2011 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: stream.string_writer.m.
     % Authors: trd, fjh, stayl
     %
     % Predicates to write to streams that accept strings.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module stream.string_writer.
     :- interface.

     :- import_module char.
     :- import_module deconstruct.
     :- import_module io.
     :- import_module list.
     :- import_module string.
     :- import_module univ.

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

     :- pred put_int(Stream::in, int::in, State::di, State::uo) is det
         <= stream.writer(Stream, string, State).

     :- pred put_float(Stream::in, float::in, State::di, State::uo) is det
         <= stream.writer(Stream, string, State).

     :- pred put_char(Stream::in, char::in, State::di, State::uo) is det
         <= stream.writer(Stream, string, State).

         % A version of io.format that works for arbitrary string writers.
         %
     :- pred format(Stream::in, string::in, list(string.poly_type)::in,
         State::di, State::uo) is det <= stream.writer(Stream, string, State).

     :- pred nl(Stream::in, State::di, State::uo) is det
         <= stream.writer(Stream, string, State).

         % print/3 writes its argument to the standard output stream.
         % print/4 writes its second argument to the output stream specified
         % in its first argument. In all cases, the argument to output can be
         % of any type. It is output in a format that is intended to be human
         % readable.
         %
         % If the argument is just a single string or character, it will be printed
         % out exactly as is (unquoted). If the argument is of type univ, then
         % it will print out the value stored in the univ, but not the type.
         %
         % print/5 is the same as print/4 except that it allows the caller
         % to specify how non-canonical types should be handled. print/3 and
         % print/4 implicitly specify `canonicalize' as the method for handling
         % non-canonical types. This means that for higher-order types, or types
         % with user-defined equality axioms, or types defined using the foreign
         % language interface (i.e. pragma foreign_type), the text output will
         % only describe the type that is being printed, not the value.
         %
         % print_cc/3 is the same as print/3 except that it specifies
         % `include_details_cc' rather than `canonicalize'. This means that it will
         % print the details of non-canonical types. However, it has determinism
         % `cc_multi'.
         %
         % Note that even if `include_details_cc' is specified, some implementations
         % may not be able to print all the details for higher-order types or types
         % defined using the foreign language interface.
         %
     :- pred print(Stream::in, T::in, State::di, State::uo) is det
         <= (stream.writer(Stream, string, State),
         stream.writer(Stream, char, State)).

     :- pred print(Stream, deconstruct.noncanon_handling, T, State, State)
         <= (stream.writer(Stream, string, State),
         stream.writer(Stream, char, State)).
     :- mode print(in, in(do_not_allow), in, di, uo) is det.
     :- mode print(in, in(canonicalize), in, di, uo) is det.
     :- mode print(in, in(include_details_cc), in, di, uo) is cc_multi.
     :- mode print(in, in, in, di, uo) is cc_multi.

     :- pred print_cc(Stream::in, T::in, State::di, State::uo) is cc_multi
         <= (stream.writer(Stream, string, State),
         stream.writer(Stream, char, State)).

         % write/4 writes its second argument to the output stream specified
         % in its first argument. In all cases, the argument to output may be
         % of any type. The argument is written in a format that is intended to
         % be valid Mercury syntax whenever possible.
         %
         % Strings and characters are always printed out in quotes, using backslash
         % escapes if necessary. For higher-order types, or for types defined
         % using the foreign language interface (pragma foreign_code), the text
         % output will only describe the type that is being printed, not the value,
         % and the result may not be parsable by `read'. For the types
         % containing existential quantifiers, the type `type_desc' and closure
         % types, the result may not be parsable by `read', either. But in all
         % other cases the format used is standard Mercury syntax, and if you append
         % a period and newline (".\n"), then the results can be read in again
         % using `read'.
         %
         % write/5 is the same as write/4 except that it allows the caller
         % to specify how non-canonical types should be handled. write_cc/4
         % is the same as write/4 except that it specifies `include_details_cc'
         % rather than `canonicalize'.
         %
     :- pred write(Stream::in, T::in, State::di, State::uo) is det
         <= (stream.writer(Stream, string, State),
         stream.writer(Stream, char, State)).

     :- pred write(Stream, deconstruct.noncanon_handling, T, State, State) is det
         <= (stream.writer(Stream, string, State),
         stream.writer(Stream, char, State)).
     :- mode write(in, in(do_not_allow), in, di, uo) is det.
     :- mode write(in, in(canonicalize), in, di, uo) is det.
     :- mode write(in, in(include_details_cc), in, di, uo) is cc_multi.
     :- mode write(in, in, in, di, uo) is cc_multi.

     :- pred write_cc(Stream::in, T::in, State::di, State::uo) is cc_multi
         <= (stream.writer(Stream, string, State),
         stream.writer(Stream, char, State)).

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


File: mercury_library.info,  Node: string.builder,  Next: string,  Prev: stream.string_writer,  Up: Top

73 string.builder
*****************

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et
     %--------------------------------------------------%
     % Copyright (C) 2006-2007 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: string.builder.m.
     % Main author: maclarty.
     %
     % This module implements a string builder stream.  It can be used to
     % build up a string using string or character writers.
     %
     % To build up a string using this module, you first construct an initial
     % string builder state by calling the init function.  You can then use
     % any instances of stream.writer that write strings or characters to update the
     % string builder state, using string.builder.handle as the stream argument.
     % Once you've finished writing to the string builder you can get the final
     % string by calling string.builder.to_string/1.
     %
     % For example:
     %
     %     State0 = string.builder.init,
     %     stream.string_writer.put_int(string.builder.handle, 5, State0, State),
     %     Str = string.builder.to_string(State),  % Str = "5".
     %
     %--------------------------------------------------%

     :- module string.builder.
     :- interface.

     :- import_module char.
     :- import_module stream.

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

     :- type handle
         --->    handle.

     :- type state.

     :- func init = (string.builder.state::uo) is det.

     :- instance stream.stream(string.builder.handle, string.builder.state).

     :- instance stream.output(string.builder.handle, string.builder.state).

     :- instance stream.writer(string.builder.handle, string, string.builder.state).
     :- instance stream.writer(string.builder.handle, char, string.builder.state).

     :- func to_string(string.builder.state::di) = (string::uo) is det.

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


File: mercury_library.info,  Node: string,  Next: svarray,  Prev: string.builder,  Up: Top

74 string
*********

     %--------------------------------------------------%
     % vim: ts=4 sw=4 et ft=mercury
     %--------------------------------------------------%
     % Copyright (C) 1993-2011 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: string.m.
     % Main authors: fjh, petdr.
     % Stability: medium to high.
     %
     % This modules provides basic string handling facilities.
     %
     % Unexpected null characters embedded in the middle of strings can be a source
     % of security vulnerabilities, so the Mercury library predicates and functions
     % which create strings from (lists of) characters throw an exception if a null
     % character is detected.  Programmers must not create strings that might
     % contain null characters using the foreign language interface.
     %
     % When Mercury is compiled to C, strings are UTF-8 encoded, using a null
     % character as the string terminator.  A single code point requires one to four
     % bytes (code units) to encode.
     %
     % When Mercury is compiled to Java, strings are represented as Java `String's.
     % When Mercury is compiled to C# code, strings are represented as
     % `System.String's.  In both cases, strings are UTF-16 encoded.  A single code
     % point requires one or two 16-bit integers (code units) to encode.
     %
     % Whe Mercury is compiled to Erlang, strings are represented as Erlang
     % binaries using UTF-8 encoding.
     %
     % The builtin comparison operation on strings is also implementation dependent.
     % In the current implementation, when Mercury is compiled to C, string
     % comparison is implemented using C's strcmp() function.  When Mercury
     % is compiled to Java, string comparison is implemented using Java's
     % String.compareTo() method.  When Mercury is compiled to C#, string comparison
     % is implemented using C#'s System.String.CompareOrdinal() method.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module string.
     :- interface.

     :- include_module builder.

     :- import_module assoc_list.
     :- import_module char.
     :- import_module deconstruct.
     :- import_module list.
     :- import_module maybe.
     :- import_module ops.
     :- import_module pretty_printer.

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

         % This type is used for defining stream typeclass instances where the raw
         % string type would be ambiguous. A line is:
         %
         % - a possibly empty sequence of non-newline characters terminated by a
         %   newline character; or
         % - a non-empty sequence of non-newline characters terminated by the end
         %   of the file.
         %
     :- type line
         --->    line(string).

         % This type is used for defining stream typeclass instances where the raw
         % string type would be ambiguous. A text file is a possibly empty sequence
         % of characters terminated by the end of file.
         %
     :- type text_file
         --->    text_file(string).

         % Determine the length of a string, in code units.
         % An empty string has length zero.
         %
         % NOTE: code points (characters) are encoded using one or more code units,
         % i.e. bytes for UTF-8; 16-bit integers for UTF-16.
         %
     :- func string.length(string::in) = (int::uo) is det.
     :- pred string.length(string, int).
     :- mode string.length(in, uo) is det.
     :- mode string.length(ui, uo) is det.

         % Synonyms for string.length.
         %
     :- func string.count_code_units(string) = int.
     :- pred string.count_code_units(string::in, int::out) is det.

         % Determine the number of code points in a string.
         %
     :- func string.count_codepoints(string) = int.
     :- pred string.count_codepoints(string::in, int::out) is det.

         % Determine the number of code units required to represent a string
         % in UTF-8 encoding.
         %
     :- func string.count_utf8_code_units(string) = int.

         % string.codepoint_offset(String, CodePointCount, CodePointOffset):
         % Equivalent to `string.codepoint_offset(String, 0, CodePointCount,
         % CodePointOffset)'.
         %
     :- pred string.codepoint_offset(string::in, int::in, int::out) is semidet.

         % string.codepoint_offset(String, StartOffset, CodePointCount,
         %   CodePointOffset):
         %
         % Return the offset into `String' where, starting from `StartOffset',
         % `CodePointCount' code points are skipped.  Fails if either `StartOffset'
         % or `CodePointOffset' are out of range.
         %
     :- pred string.codepoint_offset(string::in, int::in, int::in, int::out)
         is semidet.

         % Append two strings together.
         %
     :- func string.append(string::in, string::in) = (string::uo) is det.

     :- pred string.append(string, string, string).
     :- mode string.append(in, in, in) is semidet.  % implied
     :- mode string.append(in, uo, in) is semidet.
     :- mode string.append(in, in, uo) is det.
     :- mode string.append(out, out, in) is multi.
     % The following mode is semidet in the sense that it doesn't succeed more
     % than once - but it does create a choice-point, which means it's inefficient
     % and that the compiler can't deduce that it is semidet.
     % Use string.remove_suffix instead.
     % :- mode string.append(out, in, in) is semidet.

         % S1 ++ S2 = S :- string.append(S1, S2, S).
         %
         % Nicer syntax.
     :- func string ++ string = string.
     :- mode in ++ in = uo is det.

         % string.remove_suffix(String, Suffix, Prefix):
         % The same as string.append(Prefix, Suffix, String) except that
         % this is semidet whereas string.append(out, in, in) is nondet.
         %
     :- pred string.remove_suffix(string::in, string::in, string::out) is semidet.

         % string.det_remove_suffix(String, Suffix) returns the same value
         % as string.remove_suffix, except it aborts if String does not end
         % with Suffix.
         %
     :- func string.det_remove_suffix(string, string) = string.

         % An obsolete synonym for the above.
         %
     :- pragma obsolete(string.remove_suffix_det/2).
     :- func string.remove_suffix_det(string, string) = string.

         % string.remove_suffix_if_present(Suffix, String) returns `String' minus
         % `Suffix' if `String' ends with `Suffix', `String' otherwise.
         %
     :- func string.remove_suffix_if_present(string, string) = string.

         % string.remove_prefix(Prefix, String, Suffix):
         % This is a synonym for string.append(Prefix, Suffix, String) but with
         % the arguments in a more convenient order for use with higher-order code.
         %
     :- pred string.remove_prefix(string::in, string::in, string::out) is semidet.

         % string.remove_prefix_if_present(Prefix, String) = Suffix returns `String'
         % minus `Prefix' if `String' begins with `Prefix', `String' otherwise.
         %
     :- func string.remove_prefix_if_present(string, string) = string.

         % string.prefix(String, Prefix) is true iff Prefix is a prefix of String.
         % Same as string.append(Prefix, _, String).
         %
     :- pred string.prefix(string, string).
     :- mode string.prefix(in, in) is semidet.
     :- mode string.prefix(in, out) is multi.

         % string.suffix(String, Suffix) is true iff Suffix is a suffix of String.
         % Same as string.append(_, Suffix, String).
         %
     :- pred string.suffix(string, string).
     :- mode string.suffix(in, in) is semidet.
     :- mode string.suffix(in, out) is multi.

         % string.string(X): Returns a canonicalized string representation
         % of the value X using the standard Mercury operators.
         %
     :- func string.string(T) = string.

         % As above, but using the supplied table of operators.
         %
     :- func string.string_ops(ops.table, T) = string.

         % string.string_ops_noncanon(NonCanon, OpsTable, X, String)
         %
         % As above, but the caller specifies what behaviour should occur for
         % non-canonical terms (i.e. terms where multiple representations
         % may compare as equal):
         %
         % - `do_not_allow' will throw an exception if (any subterm of) the argument
         %    is not canonical;
         % - `canonicalize' will substitute a string indicating the presence
         %    of a non-canonical subterm;
         % - `include_details_cc' will show the structure of any non-canonical
         %   subterms, but can only be called from a committed choice context.
         %
     :- pred string.string_ops_noncanon(noncanon_handling, ops.table, T, string).
     :- mode string.string_ops_noncanon(in(do_not_allow), in, in, out) is det.
     :- mode string.string_ops_noncanon(in(canonicalize), in, in, out) is det.
     :- mode string.string_ops_noncanon(in(include_details_cc), in, in, out)
         is cc_multi.
     :- mode string.string_ops_noncanon(in, in, in, out) is cc_multi.

         % string.char_to_string(Char, String).
         % Converts a character (code point) to a string or vice versa.
         %
     :- func string.char_to_string(char::in) = (string::uo) is det.
     :- pred string.char_to_string(char, string).
     :- mode string.char_to_string(in, uo) is det.
     :- mode string.char_to_string(out, in) is semidet.

         % A synonym for string.char_to_string/1.
         %
     :- func string.from_char(char::in) = (string::uo) is det.

         % Convert an integer to a string.
         %
     :- func string.int_to_string(int::in) = (string::uo) is det.
     :- pred string.int_to_string(int::in, string::uo) is det.

         % A synonym for string.int_to_string/1.
         %
     :- func string.from_int(int::in) = (string::uo) is det.

         % Convert an integer to a string with commas as thousand separators.
         %
     :- func string.int_to_string_thousands(int::in) = (string::uo) is det.

         % string.int_to_base_string(Int, Base, String):
         % Convert an integer to a string in a given Base.
         % An exception is thrown if Base is not between 2 and 36.
         %
     :- func string.int_to_base_string(int::in, int::in) = (string::uo) is det.
     :- pred string.int_to_base_string(int::in, int::in, string::uo) is det.

         % string.int_to_base_string_group(Int, Base, GroupLength, Separator,
         %   String):
         % Convert an integer to a string in a given Base (between 2 and 36)
         % and insert Separator between every GroupLength digits.
         % If GroupLength is less than one then no separators will appear in the
         % output.  An exception is thrown if Base is not between 2 and 36.
         % Useful for formatting numbers like "1,300,000".
         %
     :- func string.int_to_base_string_group(int, int, int, string) = string.
     :- mode string.int_to_base_string_group(in, in, in, in) = uo is det.

         % Convert a float to a string.
         % In the current implementation the resulting float will be in the form
         % that it was printed using the format string "%#.<prec>g".
         % <prec> will be in the range p to (p+2)
         % where p = floor(mantissa_digits * log2(base_radix) / log2(10)).
         % The precision chosen from this range will be such to allow a successful
         % decimal -> binary conversion of the float.
         %
     :- func string.float_to_string(float::in) = (string::uo) is det.
     :- pred string.float_to_string(float::in, string::uo) is det.

         % A synonym for string.float_to_string/1.
         %
     :- func string.from_float(float::in) = (string::uo) is det.

         % Convert a c_pointer to a string.  The format is "c_pointer(0xXXXX)"
         % where XXXX is the hexadecimal representation of the pointer.
         %
     :- func string.c_pointer_to_string(c_pointer::in) = (string::uo) is det.
     :- pred string.c_pointer_to_string(c_pointer::in, string::uo) is det.

         % A synonym for string.c_pointer_to_string/1.
         %
     :- func string.from_c_pointer(c_pointer::in) = (string::uo) is det.

         % string.first_char(String, Char, Rest) is true iff Char is the first
         % character (code point) of String, and Rest is the remainder.
         %
         % WARNING: string.first_char makes a copy of Rest because the garbage
         % collector doesn't handle references into the middle of an object,
         % at least not the way we use it. Repeated use of string.first_char
         % to iterate over a string will result in very poor performance.
         % Use string.foldl or string.to_char_list instead.
         %
     :- pred string.first_char(string, char, string).
     :- mode string.first_char(in, in, in) is semidet.  % implied
     :- mode string.first_char(in, uo, in) is semidet.  % implied
     :- mode string.first_char(in, in, uo) is semidet.  % implied
     :- mode string.first_char(in, uo, uo) is semidet.
     :- mode string.first_char(uo, in, in) is det.

         % string.replace(String0, Search, Replace, String):
         % string.replace replaces the first occurrence of Search in String0
         % with Replace to give String. It fails if Search does not occur
         % in String0.
         %
     :- pred string.replace(string::in, string::in, string::in, string::uo)
         is semidet.

         % string.replace_all(String0, Search, Replace, String):
         % string.replace_all replaces any occurrences of Search in String0
         % with Replace to give String.
         %
     :- func string.replace_all(string::in, string::in, string::in) = (string::uo)
         is det.
     :- pred string.replace_all(string::in, string::in, string::in, string::uo)
         is det.

         % Converts a string to lowercase.
         % Note that this only converts unaccented Latin letters.
         %
     :- func string.to_lower(string::in) = (string::uo) is det.
     :- pred string.to_lower(string, string).
     :- mode string.to_lower(in, uo) is det.
     :- mode string.to_lower(in, in) is semidet.        % implied

         % Converts a string to uppercase.
         % Note that this only converts unaccented Latin letters.
         %
     :- func string.to_upper(string::in) = (string::uo) is det.
     :- pred string.to_upper(string, string).
     :- mode string.to_upper(in, uo) is det.
     :- mode string.to_upper(in, in) is semidet.        % implied

         % Convert the first character (if any) of a string to uppercase.
         % Note that this only converts unaccented Latin letters.
         %
     :- func string.capitalize_first(string) = string.
     :- pred string.capitalize_first(string::in, string::out) is det.

         % Convert the first character (if any) of a string to lowercase.
         % Note that this only converts unaccented Latin letters.
         %
     :- func string.uncapitalize_first(string) = string.
     :- pred string.uncapitalize_first(string::in, string::out) is det.

         % Convert the string to a list of characters (code points).
         % Throws an exception if the list of characters contains a null character.
         %
         % NOTE: in future the same treatment may be afforded surrogate code points.
         %
     :- func string.to_char_list(string) = list(char).
     :- pred string.to_char_list(string, list(char)).
     :- mode string.to_char_list(in, out) is det.
     :- mode string.to_char_list(uo, in) is det.

         % Convert a list of characters (code points) to a string.
         % Throws an exception if the list of characters contains a null character.
         %
         % NOTE: in future the same treatment may be afforded surrogate code points.
         %
     :- func string.from_char_list(list(char)::in) = (string::uo) is det.
     :- pred string.from_char_list(list(char), string).
     :- mode string.from_char_list(in, uo) is det.
     :- mode string.from_char_list(out, in) is det.

         % As above, but fail instead of throwing an exception if the
         % list contains a null character.
         %
         % NOTE: in future the same treatment may be afforded surrogate code points.
         %
     :- pred string.semidet_from_char_list(list(char)::in, string::uo) is semidet.

         % Same as string.from_char_list, except that it reverses the order
         % of the characters.
         % Throws an exception if the list of characters contains a null character.
         %
         % NOTE: in future the same treatment may be afforded surrogate code points.
         %
     :- func string.from_rev_char_list(list(char)::in) = (string::uo) is det.
     :- pred string.from_rev_char_list(list(char)::in, string::uo) is det.

         % As above, but fail instead of throwing an exception if the
         % list contains a null character.
         %
         % NOTE: in future the same treatment may be afforded surrogate code points.
         %
     :- pred string.semidet_from_rev_char_list(list(char)::in, string::uo)
         is semidet.

         % Convert a string into a list of code units.
         %
     :- pred string.to_code_unit_list(string::in, list(int)::out) is det.

         % Convert a list of code units to a string.
         % Fails if the list does not contain a valid encoding of a string,
         % in the encoding expected by the current process.
         %
     :- pred string.from_code_unit_list(list(int)::in, string::uo) is semidet.

         % Converts a signed base 10 string to an int; throws an exception
         % if the string argument does not match the regexp [+-]?[0-9]+
         % or the number is not in the range [int.min_int+1, int.max_int].
         %
     :- func string.det_to_int(string) = int.

         % Convert a string to an int. The string must contain only digits [0-9],
         % optionally preceded by a plus or minus sign. If the string does
         % not match this syntax or the number is not in the range
         % [int.min_int+1, int.max_int], string.to_int fails.
         %
     :- pred string.to_int(string::in, int::out) is semidet.

         % Convert a string in the specified base (2-36) to an int. The string
         % must contain one or more digits in the specified base, optionally
         % preceded by a plus or minus sign. For bases > 10, digits 10 to 35
         % are represented by the letters A-Z or a-z. If the string does not match
         % this syntax or the base is 10 and the number is not in the range
         % [int.min_int, int.max_int], the predicate fails.
         %
     :- pred string.base_string_to_int(int::in, string::in, int::out) is semidet.

         % Converts a signed base N string to an int; throws an exception
         % if the string argument is not precisely an optional sign followed by
         % a non-empty string of base N digits and, if the base is 10, the number
         % is in the range [int.min_int, int.max_int].
         %
     :- func string.det_base_string_to_int(int, string) = int.

         % Convert a string to a float. Throws an exception if the string is not
         % a syntactically correct float literal.
         %
     :- func string.det_to_float(string) = float.

         % Convert a string to a float. If the string is not a syntactically correct
         % float literal, string.to_float fails.
         %
     :- pred string.to_float(string::in, float::out) is semidet.

         % True if string contains only alphabetic characters [A-Za-z].
         %
     :- pred string.is_all_alpha(string::in) is semidet.

         % True if string contains only alphabetic characters [A-Za-z] and
         % underscores.
         %
     :- pred string.is_all_alpha_or_underscore(string::in) is semidet.

         % True if string contains only alphabetic characters [A-Za-z],
         % digits [0-9], and underscores.
         %
     :- pred string.is_all_alnum_or_underscore(string::in) is semidet.

         % True if the string contains only decimal digits (0-9).
         %
     :- pred string.is_all_digits(string::in) is semidet.

         % string.all_match(TestPred, String):
         %
         % True if TestPred is true when applied to each character (code point) in
         % String or if String is the empty string.
         %
     :- pred string.all_match(pred(char)::in(pred(in) is semidet), string::in)
         is semidet.

         % string.pad_left(String0, PadChar, Width, String):
         % Insert `PadChar's at the left of `String0' until it is at least as long
         % as `Width', giving `String'.  Width is currently measured as the number
         % of code points.
         %
     :- func string.pad_left(string, char, int) = string.
     :- pred string.pad_left(string::in, char::in, int::in, string::out) is det.

         % string.pad_right(String0, PadChar, Width, String):
         % Insert `PadChar's at the right of `String0' until it is at least as long
         % as `Width', giving `String'.  Width is currently measured as the number
         % of code points.
         %
     :- func string.pad_right(string, char, int) = string.
     :- pred string.pad_right(string::in, char::in, int::in, string::out) is det.

         % string.duplicate_char(Char, Count, String):
         % Construct a string consisting of `Count' occurrences of `Char'
         % code points in sequence.
         %
     :- func string.duplicate_char(char::in, int::in) = (string::uo) is det.
     :- pred string.duplicate_char(char::in, int::in, string::uo) is det.

         % string.contains_char(String, Char):
         % Succeed if the code point `Char' occurs in `String'.
         %
     :- pred string.contains_char(string::in, char::in) is semidet.

         % string.index(String, Index, Char):
         % `Char' is the character (code point) in `String', beginning at the
         % code unit `Index'.  Fails if `Index' is out of range (negative, or
         % greater than or equal to the length of `String').
         %
         % Calls error/1 if an illegal sequence is detected.
         %
     :- pred string.index(string::in, int::in, char::uo) is semidet.

         % string.det_index(String, Index, Char):
         % `Char' is the character (code point) in `String', beginning at the
         % code unit `Index'.
         % Calls error/1 if `Index' is out of range (negative, or greater than
         % or equal to the length of `String'), or if an illegal sequence is
         % detected.
         %
     :- func string.det_index(string, int) = char.
     :- pred string.det_index(string::in, int::in, char::uo) is det.

     :- pragma obsolete(string.index_det/2).
     :- func string.index_det(string, int) = char.
     :- pragma obsolete(string.index_det/3).
     :- pred string.index_det(string::in, int::in, char::uo) is det.

         % A synonym for det_index/2:
         % String ^ elem(Index) = string.det_index(String, Index).
         %
     :- func string ^ elem(int) = char.

         % string.unsafe_index(String, Index, Char):
         % `Char' is the character (code point) in `String', beginning at the
         % code unit `Index'.
         % WARNING: behavior is UNDEFINED if `Index' is out of range
         % (negative, or greater than or equal to the length of `String').
         % This version is constant time, whereas string.det_index
         % may be linear in the length of the string. Use with care!
         %
     :- func string.unsafe_index(string, int) = char.
     :- pred string.unsafe_index(string::in, int::in, char::uo) is det.

         % A synonym for unsafe_index/2:
         % String ^ unsafe_elem(Index) = string.unsafe_index(String, Index).
         %
     :- func string ^ unsafe_elem(int) = char.

         % string.index_next(String, Index, NextIndex, Char):
         % Like `string.index'/3 but also returns the position of the code unit
         % that follows the code point beginning at `Index',
         % i.e. NextIndex = Index + num_code_units_to_encode(Char).
         %
     :- pred string.index_next(string::in, int::in, int::out, char::uo) is semidet.

         % string.unsafe_index_next(String, Index, NextIndex, Char):
         % `Char' is the character (code point) in `String', beginning at the
         % code unit `Index'. `NextIndex' is the offset following the encoding
         % of `Char'. Fails if `Index' is equal to the length of `String'.
         % WARNING: behavior is UNDEFINED if `Index' is out of range
         % (negative, or greater than the length of `String').
         %
     :- pred string.unsafe_index_next(string::in, int::in, int::out, char::uo)
         is semidet.

         % string.prev_index(String, Index, CharIndex, Char):
         % `Char' is the character (code point) in `String' immediately _before_
         % the code unit `Index'.  Fails if `Index' is out of range (non-positive,
         % or greater than the length of `String').
         %
     :- pred string.prev_index(string::in, int::in, int::out, char::uo) is semidet.

         % string.unsafe_prev_index(String, Index, CharIndex, Char):
         % `Char' is the character (code point) in `String' immediately _before_
         % the code unit `Index'. `CharIndex' is the offset of the beginning of
         % `Char'. Fails if `Index' is zero.
         % WARNING: behavior is UNDEFINED if `Index' is out of range
         % (negative, or greater than or equal to the length of `String').
         %
     :- pred string.unsafe_prev_index(string::in, int::in, int::out, char::uo)
         is semidet.

         % string.unsafe_index_code_unit(String, Index, CodeList):
         % `Code' unit is the code unit in `String' at the offset `Index'.
         % WARNING: behavior is UNDEFINED if `Index' is out of range
         % (negative, or greater than or equal to the length of `String').
         %
     :- pred string.unsafe_index_code_unit(string::in, int::in, int::out) is det.

         % string.chomp(String):
         % `String' minus any single trailing newline character.
         %
     :- func string.chomp(string) = string.

         % string.lstrip(String):
         % `String' minus any initial whitespace characters in the ASCII range.
         %
     :- func string.lstrip(string) = string.

         % string.rstrip(String):
         % `String' minus any trailing whitespace characters in the ASCII range.
         %
     :- func string.rstrip(string) = string.

         % string.strip(String):
         % `String' minus any initial and trailing whitespace characters in the
         % ASCII range.
         %
     :- func string.strip(string) = string.

         % string.lstrip_pred(Pred, String):
         % `String' minus the maximal prefix consisting entirely of characters
         % (code points) satisfying `Pred'.
         %
     :- func string.lstrip_pred(pred(char)::in(pred(in) is semidet), string::in)
         = (string::out) is det.

         % string.rstrip_pred(Pred, String):
         % `String' minus the maximal suffix consisting entirely of characters
         % (code points) satisfying `Pred'.
         %
     :- func string.rstrip_pred(pred(char)::in(pred(in) is semidet), string::in)
         = (string::out) is det.

         % string.prefix_length(Pred, String):
         % The length (in code units) of the maximal prefix of `String' consisting
         % entirely of characters (code points) satisfying Pred.
         %
     :- func string.prefix_length(pred(char)::in(pred(in) is semidet), string::in)
         = (int::out) is det.

         % string.suffix_length(Pred, String):
         % The length (in code units) of the maximal suffix of `String' consisting
         % entirely of characters (code points) satisfying Pred.
         %
     :- func string.suffix_length(pred(char)::in(pred(in) is semidet), string::in)
         = (int::out) is det.

         % string.set_char(Char, Index, String0, String):
         % `String' is `String0', with the code point beginning at code unit
         % `Index' removed and replaced by `Char'.
         % Fails if `Index' is out of range (negative, or greater than or equal to
         % the length of `String0').
         %
     :- pred string.set_char(char, int, string, string).
     :- mode string.set_char(in, in, in, out) is semidet.
     % XXX This mode is disabled because the compiler puts constant
     % strings into static data even when they might be updated.
     %:- mode string.set_char(in, in, di, uo) is semidet.

         % string.det_set_char(Char, Index, String0, String):
         % `String' is `String0', with the code point beginning at code unit
         % `Index' removed and replaced by `Char'.
         % Calls error/1 if `Index' is out of range (negative, or greater than
         % or equal to the length of `String0').
         %
     :- func string.det_set_char(char, int, string) = string.
     :- pred string.det_set_char(char, int, string, string).
     :- mode string.det_set_char(in, in, in, out) is det.
     % XXX This mode is disabled because the compiler puts constant
     % strings into static data even when they might be updated.
     %:- mode string.det_set_char(in, in, di, uo) is det.

         % Deperecated synonyms for the above.
         %
     :- pragma obsolete(string.set_char_det/3).
     :- func string.set_char_det(char, int, string) = string.
     :- pragma obsolete(string.set_char_det/4).
     :- pred string.set_char_det(char, int, string, string).
     :- mode string.set_char_det(in, in, in, out) is det.

         % string.unsafe_set_char(Char, Index, String0, String):
         % `String' is `String0', with the code point beginning at code unit
         % `Index' removed and replaced by `Char'.
         % WARNING: behavior is UNDEFINED if `Index' is out of range
         % (negative, or greater than or equal to the length of `String0').
         % This version is constant time, whereas string.det_set_char
         % may be linear in the length of the string. Use with care!
         %
     :- func string.unsafe_set_char(char, int, string) = string.
     :- mode string.unsafe_set_char(in, in, in) = out is det.
     % XXX This mode is disabled because the compiler puts constant
     % strings into static data even when they might be updated.
     %:- mode string.unsafe_set_char(in, in, di) = uo is det.
     :- pred string.unsafe_set_char(char, int, string, string).
     :- mode string.unsafe_set_char(in, in, in, out) is det.
     % XXX This mode is disabled because the compiler puts constant
     % strings into static data even when they might be updated.
     %:- mode string.unsafe_set_char(in, in, di, uo) is det.

         % string.foldl(Closure, String, !Acc):
         % `Closure' is an accumulator predicate which is to be called for each
         % character (code point) of the string `String' in turn. The initial
         % value of the accumulator is `!.Acc' and the final value is `!:Acc'.
         % (string.foldl is equivalent to
         %   string.to_char_list(String, Chars),
         %   list.foldl(Closure, Chars, !Acc)
         % but is implemented more efficiently.)
         %
     :- func string.foldl(func(char, A) = A, string, A) = A.
     :- pred string.foldl(pred(char, A, A), string, A, A).
     :- mode string.foldl(pred(in, di, uo) is det, in, di, uo) is det.
     :- mode string.foldl(pred(in, in, out) is det, in, in, out) is det.
     :- mode string.foldl(pred(in, in, out) is semidet, in, in, out) is semidet.
     :- mode string.foldl(pred(in, in, out) is nondet, in, in, out) is nondet.
     :- mode string.foldl(pred(in, in, out) is multi, in, in, out) is multi.

         % string.foldl2(Closure, String, !Acc1, !Acc2):
         % A variant of string.foldl with two accumulators.
         %
     :- pred string.foldl2(pred(char, A, A, B, B), string, A, A, B, B).
     :- mode string.foldl2(pred(in, di, uo, di, uo) is det,
         in, di, uo, di, uo) is det.
     :- mode string.foldl2(pred(in, in, out, di, uo) is det,
         in, in, out, di, uo) is det.
     :- mode string.foldl2(pred(in, in, out, in, out) is det,
         in, in, out, in, out) is det.
     :- mode string.foldl2(pred(in, in, out, in, out) is semidet,
         in, in, out, in, out) is semidet.
     :- mode string.foldl2(pred(in, in, out, in, out) is nondet,
         in, in, out, in, out) is nondet.
     :- mode string.foldl2(pred(in, in, out, in, out) is multi,
         in, in, out, in, out) is multi.

         % string.foldl_between(Closure, String, Start, End, !Acc)
         % is equivalent to string.foldl(Closure, SubString, !Acc)
         % where SubString = string.between(String, Start, End).
         %
         % `Start' and `End' are in terms of code units.
         %
     :- func string.foldl_between(func(char, A) = A, string, int, int, A) = A.
     :- pred string.foldl_between(pred(char, A, A), string, int, int, A, A).
     :- mode string.foldl_between(pred(in, in, out) is det, in, in, in,
         in, out) is det.
     :- mode string.foldl_between(pred(in, di, uo) is det, in, in, in,
         di, uo) is det.
     :- mode string.foldl_between(pred(in, in, out) is semidet, in, in, in,
         in, out) is semidet.
     :- mode string.foldl_between(pred(in, in, out) is nondet, in, in, in,
         in, out) is nondet.
     :- mode string.foldl_between(pred(in, in, out) is multi, in, in, in,
         in, out) is multi.

         % string.foldl2_between(Closure, String, Start, End, !Acc1, !Acc2)
         % A variant of string.foldl_between with two accumulators.
         %
         % `Start' and `End' are in terms of code units.
         %
     :- pred string.foldl2_between(pred(char, A, A, B, B),
         string, int, int, A, A, B, B).
     :- mode string.foldl2_between(pred(in, di, uo, di, uo) is det,
         in, in, in, di, uo, di, uo) is det.
     :- mode string.foldl2_between(pred(in, in, out, di, uo) is det,
         in, in, in, in, out, di, uo) is det.
     :- mode string.foldl2_between(pred(in, in, out, in, out) is det,
         in, in, in, in, out, in, out) is det.
     :- mode string.foldl2_between(pred(in, in, out, in, out) is semidet,
         in, in, in, in, out, in, out) is semidet.
     :- mode string.foldl2_between(pred(in, in, out, in, out) is nondet,
         in, in, in, in, out, in, out) is nondet.
     :- mode string.foldl2_between(pred(in, in, out, in, out) is multi,
         in, in, in, in, out, in, out) is multi.

         % string.foldr(Closure, String, !Acc):
         % As string.foldl/4, except that processing proceeds right-to-left.
         %
     :- func string.foldr(func(char, T) = T, string, T) = T.
     :- pred string.foldr(pred(char, T, T), string, T, T).
     :- mode string.foldr(pred(in, in, out) is det, in, in, out) is det.
     :- mode string.foldr(pred(in, di, uo) is det, in, di, uo) is det.
     :- mode string.foldr(pred(in, in, out) is semidet, in, in, out) is semidet.
     :- mode string.foldr(pred(in, in, out) is nondet, in, in, out) is nondet.
     :- mode string.foldr(pred(in, in, out) is multi, in, in, out) is multi.

         % string.foldr_between(Closure, String, Start, End, !Acc)
         % is equivalent to string.foldr(Closure, SubString, !Acc)
         % where SubString = string.between(String, Start, End).
         %
         % `Start' and `End' are in terms of code units.
         %
     :- func string.foldr_between(func(char, T) = T, string, int, int, T) = T.
     :- pred string.foldr_between(pred(char, T, T), string, int, int, T, T).
     :- mode string.foldr_between(pred(in, in, out) is det, in, in, in,
         in, out) is det.
     :- mode string.foldr_between(pred(in, di, uo) is det, in, in, in,
         di, uo) is det.
     :- mode string.foldr_between(pred(in, in, out) is semidet, in, in, in,
         in, out) is semidet.
     :- mode string.foldr_between(pred(in, in, out) is nondet, in, in, in,
         in, out) is nondet.
     :- mode string.foldr_between(pred(in, in, out) is multi, in, in, in,
         in, out) is multi.

         % string.foldl_substring(Closure, String, Start, Count, !Acc)
         % Please use string.foldl_between instead.
         %
     :- pragma obsolete(string.foldl_substring/5).
     :- pragma obsolete(string.foldl_substring/6).
     :- func string.foldl_substring(func(char, A) = A, string, int, int, A) = A.
     :- pred string.foldl_substring(pred(char, A, A), string, int, int, A, A).
     :- mode string.foldl_substring(pred(in, in, out) is det, in, in, in,
         in, out) is det.
     :- mode string.foldl_substring(pred(in, di, uo) is det, in, in, in,
         di, uo) is det.
     :- mode string.foldl_substring(pred(in, in, out) is semidet, in, in, in,
         in, out) is semidet.
     :- mode string.foldl_substring(pred(in, in, out) is nondet, in, in, in,
         in, out) is nondet.
     :- mode string.foldl_substring(pred(in, in, out) is multi, in, in, in,
         in, out) is multi.

         % string.foldl2_substring(Closure, String, Start, Count, !Acc1, !Acc2)
         % Please use string.foldl2_between instead.
         %
     :- pragma obsolete(string.foldl2_substring/8).
     :- pred string.foldl2_substring(pred(char, A, A, B, B),
         string, int, int, A, A, B, B).
     :- mode string.foldl2_substring(pred(in, di, uo, di, uo) is det,
         in, in, in, di, uo, di, uo) is det.
     :- mode string.foldl2_substring(pred(in, in, out, di, uo) is det,
         in, in, in, in, out, di, uo) is det.
     :- mode string.foldl2_substring(pred(in, in, out, in, out) is det,
         in, in, in, in, out, in, out) is det.
     :- mode string.foldl2_substring(pred(in, in, out, in, out) is semidet,
         in, in, in, in, out, in, out) is semidet.
     :- mode string.foldl2_substring(pred(in, in, out, in, out) is nondet,
         in, in, in, in, out, in, out) is nondet.
     :- mode string.foldl2_substring(pred(in, in, out, in, out) is multi,
         in, in, in, in, out, in, out) is multi.

         % string.foldr_substring(Closure, String, Start, Count, !Acc)
         % Please use string.foldr_between instead.
         %
     :- pragma obsolete(string.foldr_substring/5).
     :- pragma obsolete(string.foldr_substring/6).
     :- func string.foldr_substring(func(char, T) = T, string, int, int, T) = T.
     :- pred string.foldr_substring(pred(char, T, T), string, int, int, T, T).
     :- mode string.foldr_substring(pred(in, in, out) is det, in, in, in,
         in, out) is det.
     :- mode string.foldr_substring(pred(in, di, uo) is det, in, in, in,
         di, uo) is det.
     :- mode string.foldr_substring(pred(in, in, out) is semidet, in, in, in,
         in, out) is semidet.
     :- mode string.foldr_substring(pred(in, in, out) is nondet, in, in, in,
         in, out) is nondet.
     :- mode string.foldr_substring(pred(in, in, out) is multi, in, in, in,
         in, out) is multi.

         % string.words_separator(SepP, String) returns the list of non-empty
         % substrings of String (in first to last order) that are delimited
         % by non-empty sequences of characters (code points) matched by SepP.
         % For example,
         %
         % string.words_separator(char.is_whitespace, " the cat  sat on the  mat") =
         %   ["the", "cat", "sat", "on", "the", "mat"]
         %
         % Note the difference to string.split_at_separator.
         %
     :- func string.words_separator(pred(char), string) = list(string).
     :- mode string.words_separator(pred(in) is semidet, in) = out is det.

         % string.words(String) =
         %   string.words_separator(char.is_whitespace, String).
         %
     :- func string.words(string) = list(string).

         % string.split_at_separator(SepP, String) returns the list of
         % substrings of String (in first to last order) that are delimited
         % by characters (code points) matched by SepP. For example,
         %
         % string.split_at_separator(char.is_whitespace, " a cat  sat on the  mat")
         %   = ["", "a", "cat", "", "sat", "on", "the", "", "mat"]
         %
         % Note the difference to string.words_separator.
         %
     :- func string.split_at_separator(pred(char), string) = list(string).
     :- mode string.split_at_separator(pred(in) is semidet, in) = out is det.

         % string.split_at_char(Char, String) =
         %     string.split_at_separator(unify(Char), String)
         %
     :- func string.split_at_char(char, string) = list(string).

         % string.split_at_string(Separator, String) returns the list of substrings
         % of String that are delimited by Separator. For example,
         %
         % string.split_at_string("|||", "|||fld2|||fld3") = ["", "fld2", [fld3"]
         %
         % Always the first match of Separator is used to break the String, for
         % example: string.split_at_string("aa", "xaaayaaaz") = ["x", "ay", "az"]
         %
     :- func string.split_at_string(string, string) = list(string).

         % string.split(String, Index, LeftSubstring, RightSubstring):
         % Split a string into two substrings, at the code unit `Index'.
         % (If `Count' is out of the range [0, length of `String'], it is treated
         % as if it were the nearest end-point of that range.)
         %
     :- pred string.split(string::in, int::in, string::uo, string::uo) is det.

         % string.split_by_codepoint(String, Count, LeftSubstring, RightSubstring):
         % `LeftSubstring' is the left-most `Count' characters (code points) of
         % `String', and `RightSubstring' is the remainder of `String'.
         % (If `Count' is out of the range [0, length of `String'], it is treated
         % as if it were the nearest end-point of that range.)
         %
     :- pred string.split_by_codepoint(string::in, int::in, string::uo, string::uo)
         is det.

         % string.left(String, Count, LeftSubstring):
         % `LeftSubstring' is the left-most `Count' code _units_ of `String'.
         % (If `Count' is out of the range [0, length of `String'], it is treated
         % as if it were the nearest end-point of that range.)
         %
     :- func string.left(string::in, int::in) = (string::uo) is det.
     :- pred string.left(string::in, int::in, string::uo) is det.

         % string.left_by_codepoint(String, Count, LeftSubstring):
         % `LeftSubstring' is the left-most `Count' characters (code points) of
         % `String'.
         % (If `Count' is out of the range [0, length of `String'], it is treated
         % as if it were the nearest end-point of that range.)
         %
     :- func string.left_by_codepoint(string::in, int::in) = (string::uo) is det.
     :- pred string.left_by_codepoint(string::in, int::in, string::uo) is det.

         % string.right(String, Count, RightSubstring):
         % `RightSubstring' is the right-most `Count' code _units_ of `String'.
         % (If `Count' is out of the range [0, length of `String'], it is treated
         % as if it were the nearest end-point of that range.)
         %
     :- func string.right(string::in, int::in) = (string::uo) is det.
     :- pred string.right(string::in, int::in, string::uo) is det.

         % string.right_by_codepoint(String, Count, RightSubstring):
         % `RightSubstring' is the right-most `Count' characters (code points) of
         % `String'.
         % (If `Count' is out of the range [0, length of `String'], it is treated
         % as if it were the nearest end-point of that range.)
         %
     :- func string.right_by_codepoint(string::in, int::in) = (string::uo) is det.
     :- pred string.right_by_codepoint(string::in, int::in, string::uo) is det.

         % string.between(String, Start, End, Substring):
         % `Substring' consists of the segment of `String' within the half-open
         % interval [Start, End), where `Start' and `End' are code unit offsets.
         % (If `Start' is out of the range [0, length of `String'], it is treated
         % as if it were the nearest end-point of that range.
         % If `End' is out of the range [`Start', length of `String'],
         % it is treated as if it were the nearest end-point of that range.)
         %
     :- func string.between(string::in, int::in, int::in) = (string::uo) is det.
     :- pred string.between(string::in, int::in, int::in, string::uo) is det.

         % string.substring(String, Start, Count, Substring):
         % Please use string.between instead.
         %
     :- pragma obsolete(string.substring/3).
     :- pragma obsolete(string.substring/4).
     :- func string.substring(string::in, int::in, int::in) = (string::uo) is det.
     :- pred string.substring(string::in, int::in, int::in, string::uo) is det.

         % string.between_codepoints(String, Start, End, Substring):
         % `Substring' is the part of `String' between the code point positions
         % `Start' and `End'.
         % (If `Start' is out of the range [0, length of `String'], it is treated
         % as if it were the nearest end-point of that range.
         % If `End' is out of the range [`Start', length of `String'],
         % it is treated as if it were the nearest end-point of that range.)
         %
     :- func string.between_codepoints(string::in, int::in, int::in)
         = (string::uo) is det.
     :- pred string.between_codepoints(string::in, int::in, int::in, string::uo)
         is det.

         % string.unsafe_between(String, Start, End, Substring):
         % `Substring' consists of the segment of `String' within the half-open
         % interval [Start, End), where `Start' and `End' are code unit offsets.
         % WARNING: if `Start' is out of the range [0, length of `String'] or
         % `End' is out of the range [`Start', length of `String']
         % then the behaviour is UNDEFINED. Use with care!
         % This version takes time proportional to the length of the substring,
         % whereas string.substring may take time proportional to the length
         % of the whole string.
         %
     :- func string.unsafe_between(string::in, int::in, int::in) = (string::uo)
         is det.
     :- pred string.unsafe_between(string::in, int::in, int::in, string::uo)
         is det.

         % string.unsafe_substring(String, Start, Count, Substring):
         % Please use string.unsafe_between instead.
         %
     :- pragma obsolete(string.unsafe_substring/3).
     :- pragma obsolete(string.unsafe_substring/4).
     :- func string.unsafe_substring(string::in, int::in, int::in) = (string::uo)
         is det.
     :- pred string.unsafe_substring(string::in, int::in, int::in, string::uo)
         is det.

         % Append a list of strings together.
         %
     :- func string.append_list(list(string)::in) = (string::uo) is det.
     :- pred string.append_list(list(string)::in, string::uo) is det.

         % string.join_list(Separator, Strings) = JoinedString:
         % Appends together the strings in Strings, putting Separator between
         % adjacent strings. If Strings is the empty list, returns the empty string.
         %
     :- func string.join_list(string::in, list(string)::in) = (string::uo) is det.

         % Compute a hash value for a string.
         %
     :- func string.hash(string) = int.
     :- pred string.hash(string::in, int::out) is det.

         % Two other hash functions for strings.
     :- func string.hash2(string) = int.
     :- func string.hash3(string) = int.

         % string.sub_string_search(String, SubString, Index).
         % `Index' is the code unit position in `String' where the first
         % occurrence of `SubString' begins. Indices start at zero, so if
         % `SubString' is a prefix of `String', this will return Index = 0.
         %
     :- pred string.sub_string_search(string::in, string::in, int::out) is semidet.

         % string.sub_string_search_start(String, SubString, BeginAt, Index).
         % `Index' is the code unit position in `String' where the first
         % occurrence of `SubString' occurs such that 'Index' is greater than or
         % equal to `BeginAt'.  Indices start at zero.
         %
     :- pred string.sub_string_search_start(string::in, string::in, int::in,
         int::out)
         is semidet.

         % A function similar to sprintf() in C.
         %
         % For example,
         %   string.format("%s %i %c %f\n",
         %       [s("Square-root of"), i(2), c('='), f(1.41)], String)
         % will return
         %   String = "Square-root of 2 = 1.41\n".
         %
         % The following options available in C are supported: flags [0+-# ],
         % a field width (or *), and a precision (could be a ".*").
         %
         % Valid conversion character types are {dioxXucsfeEgGp%}. %n is not
         % supported. string.format will not return the length of the string.
         %
         % conv  var     output form.        effect of '#'.
         % char. type.
         %
         % d     int     signed integer
         % i     int     signed integer
         % o     int     signed octal        with '0' prefix
         % x,X   int     signed hex          with '0x', '0X' prefix
         % u     int     unsigned integer
         % c     char    character
         % s     string  string
         % f     float   rational number     with '.', if precision 0
         % e,E   float   [-]m.dddddE+-xx     with '.', if precision 0
         % g,G   float   either e or f       with trailing zeros.
         % p     int     integer
         %
         % An option of zero will cause any padding to be zeros rather than spaces.
         % A '-' will cause the output to be left-justified in its % 'space'.
         % (With a `-', the default is for fields to be right-justified.)
         % A '+' forces a sign to be printed. This is not sensible for string
         % and character output. A ' ' causes a space to be printed before a thing
         % if there is no sign there. The other option is the '#', which modifies
         % the output string's format. These options are normally put directly
         % after the '%'.
         %
         % Notes:
         %
         % %#.0e, %#.0E now prints a '.' before the 'e'.
         %
         % Asking for more precision than a float actually has will result in
         % potentially misleading output.
         %
         % Numbers are now rounded by precision value, not truncated as previously.
         %
         % The implementation uses the sprintf() function in C grades, so the actual
         % output will depend on the C standard library.
         %
     :- func string.format(string, list(string.poly_type)) = string.
     :- pred string.format(string::in, list(string.poly_type)::in, string::out)
         is det.

     :- type string.poly_type
         --->    f(float)
         ;       i(int)
         ;       s(string)
         ;       c(char).

         % format_table(Columns, Separator) = Table
         % format_table/2 takes a list of columns and a column separator and returns
         % a formatted table, where each field in each column has been aligned
         % and fields are separated with Separator. A newline character is inserted
         % between each row. If the columns are not all the same length then
         % an exception is thrown. Lengths are currently measured in terms of code
         % points.
         %
         % For example:
         %
         % format_table([right(["a", "bb", "ccc"]), left(["1", "22", "333"])],
         %   " * ")
         % would return the table:
         %   a * 1
         %  bb * 22
         % ccc * 333
         %
     :- func string.format_table(list(justified_column), string) = string.

         % format_table_max(Columns, Separator) does the same job as format_table,
         % but allows the caller to associate an maximum width with each column.
         %
     :- func string.format_table_max(assoc_list(justified_column, maybe(int)),
         string) = string.

     :- type justified_column
         --->    left(list(string))
         ;       right(list(string)).

         % word_wrap(Str, N) = Wrapped.
         % Wrapped is Str with newlines inserted between words (separated by ASCII
         % space characters) so that at most N code points appear on a line and each
         % line contains as many whole words as possible. If any one word exceeds N
         % code point in length then it will be broken over two (or more) lines.
         % Sequences of whitespace characters are replaced by a single space.
         %
     :- func string.word_wrap(string, int) = string.

         % word_wrap_separator(Str, N, WordSeparator) = Wrapped.
         % word_wrap_separator/3 is like word_wrap/2, except that words that
         % need to be broken up over multiple lines have WordSeparator inserted
         % between each piece. If the length of WordSeparator is greater than
         % or equal to N code points, then no separator is used.
         %
     :- func string.word_wrap_separator(string, int, string) = string.

         % Convert a string to a pretty_printer.doc for formatting.
         %
     :- func string.string_to_doc(string) = pretty_printer.doc.

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


File: mercury_library.info,  Node: svarray,  Next: svbag,  Prev: string,  Up: Top

75 svarray
**********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2004-2007, 2011 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: svarray.m
     %
     % This file provides an interface to the 'array' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the array module; the only difference is the order
     % of the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svarray.
     :- interface.

     :- import_module array.

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

         % svarray.set sets the nth element of an array, and returns the
         % resulting array (good opportunity for destructive update ;-).
         % Throws an exception if the index is out of bounds.
         %
     :- pragma obsolete(svarray.set/4).
     :- pred svarray.set(int::in, T::in, array(T)::array_di, array(T)::array_uo)
         is det.

         % svarray.semidet_set sets the nth element of an array,
         % and returns the resulting array.
         % It fails if the index is out of bounds.
         %
     :- pragma obsolete(svarray.semidet_set/4).
     :- pred svarray.semidet_set(int::in, T::in,
         array(T)::array_di, array(T)::array_uo) is semidet.

         % svarray.slow_set sets the nth element of an array,
         % and returns the resulting array.  The initial array is not
         % required to be unique, so the implementation may not be able to use
         % destructive update.
         % It is an error if the index is out of bounds.
         %
     :- pragma obsolete(svarray.slow_set/4).
     :- pred svarray.slow_set(int, T, array(T), array(T)).
     %:- mode svarray.slow_set(in, in, array_ui, array_uo) is det.
     :- mode svarray.slow_set(in, in, in, array_uo) is det.

         % svarray.semidet_slow_set sets the nth element of an array,
         % and returns the resulting array.  The initial array is not
         % required to be unique, so the implementation may not be able to use
         % destructive update.
         % It fails if the index is out of bounds.
         %
     :- pragma obsolete(svarray.semidet_slow_set/4).
     :- pred svarray.semidet_slow_set(int, T, array(T), array(T)).
     %:- mode svarray.semidet_slow_set(in, in, array_ui, array_uo) is semidet.
     :- mode svarray.semidet_slow_set(in, in, in, array_uo) is semidet.

         % svarray.resize(Size, Init, Array0, Array):
         % The array is expanded or shrunk to make it fit
         % the new size `Size'.  Any new entries are filled
         % with `Init'.
         %
     :- pragma obsolete(svarray.resize/4).
     :- pred svarray.resize(int::in, T::in, array(T)::array_di, array(T)::array_uo)
         is det.

         % svarray.shrink(Size, Array0, Array):
         % The array is shrunk to make it fit the new size `Size'.
         % Throws an exception if `Size' is larger than the size of `Array0'.
         %
     :- pragma obsolete(svarray.shrink/3).
     :- pred svarray.shrink(int::in, array(T)::array_di, array(T)::array_uo)
         is det.

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


File: mercury_library.info,  Node: svbag,  Next: svbimap,  Prev: svarray,  Up: Top

76 svbag
********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2004-2006, 2011 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: svbag.m
     %
     % This file provides an interface to the 'bag' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the bag module; the only difference is the order of the
     % arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svbag.
     :- interface.

     :- import_module bag.
     :- import_module list.
     :- import_module set.

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

         % Insert a particular value in a bag.
         %
     :- pragma obsolete(svbag.insert/3).
     :- pred svbag.insert(T::in, bag(T)::in, bag(T)::out) is det.

         % Insert a list of values into a bag.
         %
     :- pragma obsolete(svbag.insert_list/3).
     :- pred svbag.insert_list(list(T)::in, bag(T)::in, bag(T)::out) is det.

         % Insert a set of values into a bag.
         %
     :- pragma obsolete(svbag.insert_set/3).
     :- pred svbag.insert_set(set(T)::in, bag(T)::in, bag(T)::out) is det.

         % Remove one occurrence of a particular value from a bag.
         % Fail if the item does not exist in the bag.
         %
     :- pragma obsolete(svbag.remove/3).
     :- pred svbag.remove(T::in, bag(T)::in, bag(T)::out) is semidet.

         % Remove one occurrence of a particular value from a bag.
         % Abort if the item does not exist in the bag.
         %
     :- pragma obsolete(svbag.det_remove/3).
     :- pred svbag.det_remove(T::in, bag(T)::in, bag(T)::out) is det.

         % Remove a list of values from a bag.  Duplicates are removed
         % from the bag the appropriate number of times.  Fail if any
         % of the items in the list do not exist in the bag.
         %
         % This call is logically equivalent to:
         %
         %   svbag.remove_list(RemoveList, Bag0, Bag) :-
         %       bag.from_list(RemoveList, RemoveBag),
         %       bag.is_subbag(RemoveBag, Bag0),
         %       svbag.subtract(RemoveBag, Bag0, Bag).
         %
     :- pragma obsolete(svbag.remove_list/3).
     :- pred svbag.remove_list(list(T)::in, bag(T)::in, bag(T)::out) is semidet.

         % Remove a list of values from a bag.  Duplicates are removed
         % from the bag the appropriate number of times.  Abort if any
         % of the items in the list do not exist in the bag.
         %
     :- pragma obsolete(svbag.det_remove_list/3).
     :- pred svbag.det_remove_list(list(T)::in, bag(T)::in, bag(T)::out) is det.

         % Remove a set of values from a bag. Each value is removed once.
         % Fail if any of the items in the set do not exist in the bag.
         %
     :- pragma obsolete(svbag.remove_set/3).
     :- pred svbag.remove_set(set(T)::in, bag(T)::in, bag(T)::out) is semidet.

         % Remove a set of values from a bag. Each value is removed once.
         % Abort if any of the items in the set do not exist in the bag.
         %
     :- pragma obsolete(svbag.det_remove_set/3).
     :- pred svbag.det_remove_set(set(T)::in, bag(T)::in, bag(T)::out) is det.

         % Delete one occurrence of a particular value from a bag.
         % If the key is not present, leave the bag unchanged.
         %
     :- pragma obsolete(svbag.delete/3).
     :- pred svbag.delete(T::in, bag(T)::in, bag(T)::out) is det.

         % Remove all occurrences of a particular value from a bag.
         % Fail if the item does not exist in the bag.
         %
     :- pragma obsolete(svbag.remove_all/3).
     :- pred svbag.remove_all(T::in, bag(T)::in, bag(T)::out) is semidet.

         % Delete all occurrences of a particular value from a bag.
         %
     :- pragma obsolete(svbag.delete_all/3).
     :- pred svbag.delete_all(T::in, bag(T)::in, bag(T)::out) is det.

         % svbag.subtract(Bag0, SubBag, Bag):
         %
         % Subtracts SubBag from Bag0 to produce Bag.
         % Each element in SubBag is removed from Bag0 to produce Bag.
         % If an element exists in SubBag, but not in Bag, then that
         % element is not removed.
         % e.g. svbag.subtract({1, 1, 2, 2, 3 }, {1, 1, 2, 3, 3, 3}, {2}).
         %
     :- pragma obsolete(svbag.subtract/3).
     :- pred svbag.subtract(bag(T)::in, bag(T)::in, bag(T)::out) is det.

         % Fails if the bag is empty.
         %
     :- pragma obsolete(svbag.remove_smallest/3).
     :- pred svbag.remove_smallest(T::out, bag(T)::in, bag(T)::out) is semidet.

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


File: mercury_library.info,  Node: svbimap,  Next: sveqvclass,  Prev: svbag,  Up: Top

77 svbimap
**********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2004-2006, 2011 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: svbimap.m.
     %
     % This file provides an interface to the 'bimap' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the bimap module; the only difference is the order
     % of the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svbimap.
     :- interface.

     :- import_module bimap.

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

     :- pragma obsolete(svbimap.insert/4).
     :- pred svbimap.insert(K::in, V::in, bimap(K, V)::in, bimap(K, V)::out)
         is semidet.

     :- pragma obsolete(svbimap.det_insert/4).
     :- pred svbimap.det_insert(K::in, V::in, bimap(K, V)::in, bimap(K, V)::out)
         is det.

     :- pragma obsolete(svbimap.set/4).
     :- pred svbimap.set(K::in, V::in, bimap(K, V)::in, bimap(K, V)::out) is det.

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


File: mercury_library.info,  Node: sveqvclass,  Next: svlist,  Prev: svbimap,  Up: Top

78 sveqvclass
*************

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2005-2006, 2011 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: sveqvclass.m.
     % Author: zs.
     % Stability: high.
     %
     % This file provides an interface to the 'eqvclass' ADT that is conducive
     % to the use of state variable notation. The predicates here do the same thing
     % as their counterparts in the eqvclass module; the only difference is the
     % order of the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module sveqvclass.
     :- interface.

     :- import_module eqvclass.

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

         % Make an element known to the equivalence class.
         % The element may already be known to the class;
         % if it isn't, it is created without any equivalence relationships.
         %
     :- pragma obsolete(sveqvclass.ensure_element/3).
     :- pred sveqvclass.ensure_element(T::in, eqvclass(T)::in, eqvclass(T)::out)
         is det.

         % Make an element known to the equivalence class.
         % The element must not already be known to the class;
         % it is created without any equivalence relationships.
         %
     :- pragma obsolete(sveqvclass.new_element/3).
     :- pred sveqvclass.new_element(T::in, eqvclass(T)::in, eqvclass(T)::out)
         is det.

         % Make two elements of the equivalence class equivalent.
         % It is ok if they already are.
         %
     :- pragma obsolete(sveqvclass.ensure_equivalence/4).
     :- pred sveqvclass.ensure_equivalence(T::in, T::in,
         eqvclass(T)::in, eqvclass(T)::out) is det.

         % Make two elements of the equivalence class equivalent.
         % It is an error if they are already equivalent.
         %
     :- pragma obsolete(sveqvclass.new_equivalence/4).
     :- pred sveqvclass.new_equivalence(T::in, T::in,
         eqvclass(T)::in, eqvclass(T)::out) is det.

         % Remove the given element and all other elements equivalent to it
         % from the given equivalence class.
         %
     :- pragma obsolete(sveqvclass.remove_equivalent_elements/3).
     :- pred sveqvclass.remove_equivalent_elements(T::in,
         eqvclass(T)::in, eqvclass(T)::out) is det.

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


File: mercury_library.info,  Node: svlist,  Next: svmap,  Prev: sveqvclass,  Up: Top

79 svlist
*********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2011 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: svlist.m.
     % Authors: fjh, conway, trd, zs, philip, warwick, ...
     % Stability: medium to high.
     %
     % This file provides an interface to the 'list' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the pqueue module; the only difference is the order
     % of the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svlist.
     :- interface.

     :- import_module list.

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

         % svlist.delete(Elem, List, Remainder):
         %
         % True iff `Elem' occurs in `List', and `Remainder' is the result of
         % deleting one occurrence of `Elem' from `List'.
         %
     :- pred svlist.delete(T, list(T), list(T)).
     :- mode svlist.delete(in, in, in) is semidet.
     :- mode svlist.delete(in, in, out) is nondet.
     :- mode svlist.delete(out, in, out) is nondet.
     :- mode svlist.delete(in, out, in) is multi.

         % svlist.delete_first(Elem, List0, List) is true iff Elem occurs in List0
         % and List is List0 with the first occurrence of Elem removed.
         %
     :- pred svlist.delete_first(T::in, list(T)::in, list(T)::out) is semidet.

         % svlist.delete_elems(Elems, List0, List) is true iff List is List0 with
         % all occurrences of all elements of Elems removed.
         %
     :- pred svlist.delete_elems(list(T)::in, list(T)::in, list(T)::out) is det.

         % svlist.replace(D, R, List0, List) is true iff List is List0
         % with an occurrence of D replaced with R.
         %
     :- pred svlist.replace(T, T, list(T), list(T)).
     :- mode svlist.replace(in, in, in, in) is semidet.
     :- mode svlist.replace(in, in, in, out) is nondet.

         % svlist.replace_first(D, R, List0, List) is true iff List is List0
         % with the first occurrence of D replaced with R.
         %
     :- pred svlist.replace_first(T::in, T::in, list(T)::in, list(T)::out)
         is semidet.

         % svlist.replace_all(D, R, List0, List) is true iff List is List0
         % with all occurrences of D replaced with R.
         %
     :- pred svlist.replace_all(T::in, T::in, list(T)::in, list(T)::out) is det.

         % svlist.det_replace_nth(N, R, List0, List) is true iff List is List0
         % with Nth element replaced with R.
         % Aborts if N < 1 or if length of List0 < N.
         % (Position numbers start from 1.)
         %
     :- pred svlist.det_replace_nth(int::in, T::in, list(T)::in, list(T)::out)
         is det.

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


File: mercury_library.info,  Node: svmap,  Next: svmulti_map,  Prev: svlist,  Up: Top

80 svmap
********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2004-2006, 2011 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: svmap.m.
     % Author: zs.
     % Stability: high.
     %
     % This file provides an interface to the 'map' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the map module; the only difference is the order of the
     % arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svmap.
     :- interface.

     :- import_module assoc_list.
     :- import_module list.
     :- import_module map.

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

         % Insert a new key and corresponding value into a map.
         % Fail if the key already exists.
         %
     :- pragma obsolete(svmap.insert/4).
     :- pred svmap.insert(K::in, V::in, map(K, V)::in, map(K, V)::out) is semidet.

         % Insert a new key and corresponding value into a map.
         % Abort if the key already exists.
         %
     :- pragma obsolete(svmap.det_insert/4).
     :- pred svmap.det_insert(K::in, V::in, map(K, V)::in, map(K, V)::out) is det.

         % Apply map.det_insert to key - value pairs from corresponding lists.
         %
     :- pragma obsolete(svmap.det_insert_from_corresponding_lists/4).
     :- pred svmap.det_insert_from_corresponding_lists(list(K)::in, list(V)::in,
         map(K, V)::in, map(K, V)::out) is det.

         % Apply map.det_insert to key - value pairs from the assoc_lists.
         %
     :- pragma obsolete(svmap.det_insert_from_assoc_list/3).
     :- pred svmap.det_insert_from_assoc_list(assoc_list(K, V)::in,
         map(K, V)::in, map(K, V)::out) is det.

         % Apply map.set to key - value pairs from corresponding lists.
         %
     :- pragma obsolete(svmap.set_from_corresponding_lists/4).
     :- pred svmap.set_from_corresponding_lists(list(K)::in, list(V)::in,
         map(K, V)::in, map(K, V)::out) is det.

     :- pragma obsolete(svmap.set_from_assoc_list/3).
     :- pred svmap.set_from_assoc_list(assoc_list(K, V)::in,
         map(K, V)::in, map(K, V)::out) is det.

         % Update the value corresponding to a given key
         % Fail if the key doesn't already exist.
         %
     :- pragma obsolete(svmap.update/4).
     :- pred svmap.update(K::in, V::in, map(K, V)::in, map(K, V)::out) is semidet.

         % Update the value corresponding to a given key
         % Abort if the key doesn't already exist.
         %
     :- pragma obsolete(svmap.det_update/4).
     :- pred svmap.det_update(K::in, V::in, map(K, V)::in, map(K, V)::out) is det.

         % Update value if the key is already present, otherwise
         % insert new key and value.
         %
     :- pragma obsolete(svmap.set/4).
     :- pred svmap.set(K::in, V::in, map(K, V)::in, map(K, V)::out) is det.

         % Delete a key-value pair from a map.
         % If the key is not present, leave the map unchanged.
         %
     :- pragma obsolete(svmap.delete/3).
     :- pred svmap.delete(K::in, map(K, V)::in, map(K, V)::out) is det.

         % Apply map.delete/3 to a list of keys.
         %
     :- pragma obsolete(svmap.delete_list/3).
     :- pred svmap.delete_list(list(K)::in, map(K, V)::in, map(K, V)::out) is det.

         % Delete a key-value pair from a map and return the value.
         % Fail if the key is not present.
         %
     :- pragma obsolete(svmap.remove/4).
     :- pred svmap.remove(K::in, V::out, map(K, V)::in, map(K, V)::out) is semidet.

         % Delete a key-value pair from a map and return the value.
         % Abort if the key is not present.
         %
     :- pragma obsolete(svmap.det_remove/4).
     :- pred svmap.det_remove(K::in, V::out, map(K, V)::in, map(K, V)::out) is det.

         % Remove the smallest item from the map, fail if
         % the map is empty.
         %
     :- pragma obsolete(svmap.remove_smallest/4).
     :- pred svmap.remove_smallest(K::out, V::out, map(K, V)::in, map(K, V)::out)
         is semidet.

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

     % Everything below here is not intended to be part of the public interface,
     % and will not be included in the Mercury library reference manual.

     :- interface.

     :- import_module term. % for var/1.

     :- pragma type_spec(svmap.insert(in, in, in, out), K = var(_)).
     :- pragma type_spec(svmap.insert(in, in, in, out), K = int).

     :- pragma type_spec(svmap.det_insert(in, in, in, out), K = var(_)).
     :- pragma type_spec(svmap.det_insert(in, in, in, out), K = int).

     :- pragma type_spec(svmap.set(in, in, in, out), K = var(_)).
     :- pragma type_spec(svmap.set(in, in, in, out), K = int).

     :- pragma type_spec(svmap.update(in, in, in, out), K = var(_)).
     :- pragma type_spec(svmap.update(in, in, in, out), K = int).

     :- pragma type_spec(svmap.det_update(in, in, in, out), K = var(_)).
     :- pragma type_spec(svmap.det_update(in, in, in, out), K = int).


File: mercury_library.info,  Node: svmulti_map,  Next: svpqueue,  Prev: svmap,  Up: Top

81 svmulti_map
**************

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2005-2006, 2011 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: svmulti_map.m.
     % Author: dylan.
     % Stability: low.
     %
     % This file provides an interface to the 'multi_map' ADT that is conducive to
     % the use of state variable notation. The predicates here do the same thing as
     % their counterparts in the multi_map module; the only difference is the order
     % of the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svmulti_map.
     :- interface.

     :- import_module list.
     :- import_module multi_map.

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

         % Insert a new key and corresponding value into a multi_map.
         % Fail if the key already exists.
         %
     :- pragma obsolete(svmulti_map.insert/4).
     :- pred svmulti_map.insert(K::in, V::in,
         multi_map(K, V)::in, multi_map(K, V)::out) is semidet.

         % Insert a new key and corresponding value into a multi_map.
         % Abort if the key already exists.
         %
     :- pragma obsolete(svmulti_map.det_insert/4).
     :- pred svmulti_map.det_insert(K::in, V::in,
         multi_map(K, V)::in, multi_map(K, V)::out) is det.

         % Update (add) the value corresponding to a given key.
         % Fail if the key does not already exist.
         %
     :- pragma obsolete(svmulti_map.update/4).
     :- pred svmulti_map.update(K::in, V::in,
         multi_map(K, V)::in, multi_map(K, V)::out) is semidet.

         % Update (add) the value corresponding to a given key.
         % Abort if the key doesn't already exist.
         %
     :- pragma obsolete(svmulti_map.det_update/4).
     :- pred svmulti_map.det_update(K::in, V::in,
         multi_map(K, V)::in, multi_map(K, V)::out) is det.

         % Update (replace) the value corresponding to a given key.
         % Abort if the key does not already exist.
         %
     :- pragma obsolete(svmulti_map.det_replace/4).
     :- pred svmulti_map.det_replace(K::in, list(V)::in,
         multi_map(K, V)::in, multi_map(K, V)::out) is det.

         % Update (add) value if the key is already present, otherwise
         % insert the new key and value.
         %
     :- pragma obsolete(svmulti_map.set/4).
     :- pred svmulti_map.set(K::in, V::in,
         multi_map(K, V)::in, multi_map(K, V)::out) is det.

     :- pragma obsolete(svmulti_map.add/4).
     :- pred svmulti_map.add(K::in, V::in,
         multi_map(K, V)::in, multi_map(K, V)::out) is det.

         % Delete a key and data from a multi_map
         % If the key is not present, leave the multi_map unchanged.
         %
     :- pragma obsolete(svmulti_map.delete/3).
     :- pred svmulti_map.delete(K::in, multi_map(K, V)::in, multi_map(K, V)::out)
         is det.

         % Delete a data value from a key in a multi_map
         % If the key is not present, leave the multi_map unchanged.
         %
     :- pragma obsolete(svmulti_map.delete/4).
     :- pred svmulti_map.delete(K::in, V::in,
         multi_map(K, V)::in, multi_map(K, V)::out) is det.

         % Delete a key-value pair from a multi_map and return the value.
         % Fail if the key is not present.
         %
     :- pragma obsolete(svmulti_map.remove/4).
     :- pred svmulti_map.remove(K::in, list(V)::out,
         multi_map(K, V)::in, multi_map(K, V)::out) is semidet.

         % Delete a key-value pair from a multi_map and return the value.
         % Abort if the key is not present.
         %
     :- pragma obsolete(svmulti_map.det_remove/4).
     :- pred svmulti_map.det_remove(K::in, list(V)::out,
         multi_map(K, V)::in, multi_map(K, V)::out) is det.

         % Remove the smallest item from the multi_map, fail if
         % the multi_map is empty.
         %
     :- pragma obsolete(svmulti_map.remove_smallest/4).
     :- pred svmulti_map.remove_smallest(K::out, list(V)::out,
         multi_map(K, V)::in, multi_map(K, V)::out) is semidet.

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


File: mercury_library.info,  Node: svpqueue,  Next: svqueue,  Prev: svmulti_map,  Up: Top

82 svpqueue
***********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2011 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: svpqueue.m.
     % Main author: conway.
     % Stability: high.
     %
     % This file provides an interface to the 'pqueue' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the pqueue module; the only difference is the order
     % of the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svpqueue.
     :- interface.

     :- import_module pqueue.

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

         % Insert a value V with key K into a priority queue
         % and return the new priority queue.
         %
     :- pred svpqueue.insert(K::in, V::in, pqueue(K, V)::in, pqueue(K, V)::out)
         is det.

         % Remove the smallest item from the priority queue.
         % Fails if the priority queue is empty.
         %
     :- pred svpqueue.remove(K::out, V::out, pqueue(K, V)::in, pqueue(K, V)::out)
         is semidet.

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


File: mercury_library.info,  Node: svqueue,  Next: svrelation,  Prev: svpqueue,  Up: Top

83 svqueue
**********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2004-2006, 2011 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: svqueue.m.
     % Author: zs.
     % Stability: high.
     %
     % This file provides an interface to the 'queue' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the queue module; the only difference is the order
     % of the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svqueue.
     :- interface.

     :- import_module list.
     :- import_module queue.

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

         % `svqueue.put(Elem, Queue0, Queue)' is true iff `Queue' is
         % the queue which results from appending `Elem' onto the end
         % of `Queue0'.
         %
     :- pragma obsolete(svqueue.put/3).
     :- pred svqueue.put(T::in, queue(T)::in, queue(T)::out) is det.

         % `svqueue.put_list(Elems, Queue0, Queue)' is true iff `Queue'
         % is the queue which results from inserting the items in the
         % list `Elems' into `Queue0'.
         %
     :- pragma obsolete(svqueue.put_list/3).
     :- pred svqueue.put_list(list(T)::in, queue(T)::in, queue(T)::out) is det.

         % `svqueue.get(Elem, Queue0, Queue)' is true iff `Queue0' is
         % a non-empty queue whose first element is `Elem', and `Queue'
         % the queue which results from removing that element from
         % the front of `Queue0'.
         %
     :- pragma obsolete(svqueue.get/3).
     :- pred svqueue.get(T::out, queue(T)::in, queue(T)::out) is semidet.

         % `svqueue.delete_all(Elem, Queue0, Queue)' is true iff `Queue' is
         % the same queue as `Queue0' with all occurences of `Elem' removed
         % from it.
         %
     :- pragma obsolete(svqueue.delete_all/3).
     :- pred svqueue.delete_all(T::in, queue(T)::in, queue(T)::out) is det.

         % `svqueue.put_on_front(Elem, Queue0, Queue)' pushes `Elem' on to
         % the front of `Queue0', giving `Queue'.
         %
     :- pragma obsolete(svqueue.put_on_front/3).
     :- pred svqueue.put_on_front(T::in, queue(T)::in, queue(T)::out) is det.

         % `svqueue.put_list_on_front(Queue0, Elems, Queue)' pushes `Elems'
         % on to the front of `Queue0', giving `Queue' (the Nth member
         % of `Elems' becomes the Nth member from the front of `Queue').
         %
     :- pragma obsolete(svqueue.put_list_on_front/3).
     :- pred svqueue.put_list_on_front(list(T)::in, queue(T)::in, queue(T)::out)
         is det.

         % `queue.get_from_back(Elem, Queue0, Queue)' removes `Elem' from
         % the back of `Queue0', giving `Queue'.
         %
     :- pragma obsolete(svqueue.get_from_back/3).
     :- pred svqueue.get_from_back(T::out, queue(T)::in, queue(T)::out) is semidet.

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


File: mercury_library.info,  Node: svrelation,  Next: svset,  Prev: svqueue,  Up: Top

84 svrelation
*************

     %--------------------------------------------------%
     % THIS FILE IS NO LONGER USED.
     %--------------------------------------------------%


File: mercury_library.info,  Node: svset,  Next: svstack,  Prev: svrelation,  Up: Top

85 svset
********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2004-2006, 2011 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.m.
     % Authors: zs.
     % Stability: high.
     %
     % This file provides an interface to the 'set' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the set module; the only difference is the order of
     % the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svset.
     :- interface.

     :- import_module list.
     :- import_module set.

         % `svset.insert(X, Set0, Set)' is true iff `Set' is the union of
         % `Set0' and the set containing only `X'.
         %
     :- pragma obsolete(svset.insert/3).
     :- pred svset.insert(T::in, set(T)::in, set(T)::out) is det.

         % `svset.insert_list(Xs, Set0, Set)' is true iff `Set' is the union of
         % `Set0' and the set containing only the members of `Xs'.
         %
     :- pragma obsolete(svset.insert_list/3).
     :- pred svset.insert_list(list(T)::in, set(T)::in, set(T)::out) is det.

         % `svset.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'.
         %
     :- pragma obsolete(svset.delete/3).
     :- pred svset.delete(T::in, set(T)::in, set(T)::out) is det.

         % `svset.delete_list(Xs, Set0, Set)' is true iff `Set' is the relative
         % complement of `Set0' and the set containing only the members of
         % `Xs'.
         %
     :- pragma obsolete(svset.delete_list/3).
     :- pred svset.delete_list(list(T)::in, set(T)::in, set(T)::out) is det.

         % `svset.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'.
         %
     :- pragma obsolete(svset.remove/3).
     :- pred svset.remove(T::in, set(T)::in, set(T)::out) is semidet.

         % `svset.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'.
         %
     :- pragma obsolete(svset.remove_list/3).
     :- pred svset.remove_list(list(T)::in, set(T)::in, set(T)::out) is semidet.

         % `svset.remove_least(Elem, Set0, Set)' is true iff
         % `Set0' is not empty, `Elem' is the smallest element in `Set0'
         % (with elements ordered using the standard ordering given
         % by compare/3), and `Set' is the set containing all the
         % elements of `Set0' except `Elem'.
         %
     :- pragma obsolete(svset.remove_least/3).
     :- pred svset.remove_least(T::out, set(T)::in, set(T)::out) is semidet.

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


File: mercury_library.info,  Node: svstack,  Next: svvarset,  Prev: svset,  Up: Top

86 svstack
**********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2011 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: stack.m.
     % Main author: fjh.
     % Stability: high.
     %
     % This file provides an interface to the 'stack' ADT that is conducive to the
     % use of state variable notation. The predicates here do the same thing as
     % their counterparts in the stack module; the only difference is the order of
     % the arguments.
     %
     %--------------------------------------------------%

     :- module svstack.
     :- interface.

     :- import_module list.
     :- import_module stack.

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

         % `svstack.push(Elem, Stack0, Stack)' is true iff `Stack' is
         % the stack which results from pushing `Elem' onto the top
         % of `Stack0'.
         %
     :- pred svstack.push(T::in, stack(T)::in, stack(T)::out) is det.

         % `svstack.push_list(Elems, Stack0, Stack)' is true iff `Stack'
         % is the stack which results from pushing the elements of the
         % list `Elems' onto the top of `Stack0'.
         %
     :- pred svstack.push_list(list(T)::in, stack(T)::in, stack(T)::out) is det.

         % `svstack.pop(Elem, Stack0, Stack)' is true iff `Stack0' is
         % a non-empty stack whose top element is `Elem', and `Stack'
         % the stack which results from popping `Elem' off `Stack0'.
         %
     :- pred svstack.pop(T::out, stack(T)::in, stack(T)::out) is semidet.

         % `svstack.det_pop' is like `svstack.pop' except that it will
         % call error/1 rather than failing if given an empty stack.
         %
     :- pred svstack.det_pop(T::out, stack(T)::in, stack(T)::out) is det.

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


File: mercury_library.info,  Node: svvarset,  Next: table_statistics,  Prev: svstack,  Up: Top

87 svvarset
***********

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2005-2006, 2011 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: svvarset.m.
     % Author: fjh.
     % Stability: low.
     %
     % This file provides an interface to the 'varset' ADT that is conducive to the
     % user of state variable notation.  The predicates here do the same thing as
     % their counterparts in the varset module; the only difference is the order of
     % the arguments.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module svvarset.
     :- interface.

     :- import_module list.
     :- import_module maybe.
     :- import_module set.
     :- import_module term.
     :- import_module varset.

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

         % Create a new variable.
         %
     :- pragma obsolete(svvarset.new_var/3).
     :- pred svvarset.new_var(var(T)::out, varset(T)::in, varset(T)::out) is det.

         % Create a new named variable.
         %
     :- pragma obsolete(svvarset.new_named_var/4).
     :- pred svvarset.new_named_var(string::in, var(T)::out,
         varset(T)::in, varset(T)::out) is det.

         % Create a new variable, and maybe give it a name.
         %
     :- pragma obsolete(svvarset.new_maybe_named_var/4).
     :- pred svvarset.new_maybe_named_var(maybe(string)::in, var(T)::out,
         varset(T)::in, varset(T)::out) is det.

         % Create a new named variable with a unique (w.r.t. the
         % varset) number appended to the name.
         %
     :- pragma obsolete(svvarset.new_uniquely_named_var/4).
     :- pred svvarset.new_uniquely_named_var(string::in, var(T)::out,
         varset(T)::in, varset(T)::out) is det.

         % Create multiple new variables.
         %
     :- pragma obsolete(svvarset.new_vars/4).
     :- pred svvarset.new_vars(int::in, list(var(T))::out, varset(T)::in,
         varset(T)::out) is det.

         % Delete the name and value for a variable.
         %
     :- pragma obsolete(svvarset.delete_var/3).
     :- pred svvarset.delete_var(var(T)::in, varset(T)::in, varset(T)::out) is det.

         % Delete the names and values for a list of variables.
         %
     :- pragma obsolete(svvarset.delete_vars/3).
     :- pred svvarset.delete_vars(list(var(T))::in, varset(T)::in, varset(T)::out)
         is det.

         % Set the name of a variable.
         %
     :- pragma obsolete(svvarset.name_var/4).
     :- pred svvarset.name_var(var(T)::in, string::in, varset(T)::in,
         varset(T)::out) is det.

         % Bind a value to a variable.
         % This will overwrite any existing binding.
         %
     :- pragma obsolete(svvarset.bind_var/4).
     :- pred svvarset.bind_var(var(T)::in, term(T)::in, varset(T)::in,
         varset(T)::out) is det.

         % Bind a set of terms to a set of variables.
         %
     :- pragma obsolete(svvarset.bind_vars/3).
     :- pred svvarset.bind_vars(substitution(T)::in, varset(T)::in, varset(T)::out)
         is det.

         % Given a varset and a set of variables, remove the names
         % and values of any other variables stored in the varset.
         %
     :- pragma obsolete(svvarset.select/3).
     :- pred svvarset.select(set(var(T))::in, varset(T)::in, varset(T)::out) is det.

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


File: mercury_library.info,  Node: table_statistics,  Next: term_io,  Prev: svvarset,  Up: Top

88 table_statistics
*******************

     %--------------------------------------------------%
     % vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
     %--------------------------------------------------%
     % Copyright (C) 2007 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: table_statistics.m.
     % Author: zs.
     % Stability: low.
     %
     % This file is automatically imported, as if via `use_module', into every
     % module that contains a `pragma memo' that asks the compiler to create
     % a predicate for returning statistics about the memo table. It defines
     % the data structure that this predicate will return, and some operations
     % on this data structure.
     %
     %--------------------------------------------------%
     %--------------------------------------------------%

     :- module table_statistics.
     :- interface.

     :- import_module io.
     :- import_module list.
     :- import_module maybe.

     :- type proc_table_statistics
         --->    proc_table_statistics(
                     call_table_stats            :: table_stats_curr_prev,
                     maybe_answer_table_stats    :: maybe(table_stats_curr_prev)
                 ).

     :- type table_stats_curr_prev
         --->    table_stats_curr_prev(
                     current_stats               :: table_stats,
                     stats_at_last_call          :: table_stats
                 ).

     :- type table_stats
         --->    table_stats(
                     num_lookups                 :: int,
                     num_lookups_is_dupl         :: int,
                     step_statistics             :: list(table_step_stats)
                 ).

         % The definition of this type be an enum whose implementation matches
         % the type MR_TableTrieStep in runtime/mercury_tabling.h. It should also
         % be kept in sync with the type table_trie_step in hlds_pred.m.
         %
     :- type table_step_kind
         --->    table_step_dummy
         ;       table_step_int
         ;       table_step_char
         ;       table_step_string
         ;       table_step_float
         ;       table_step_enum
         ;       table_step_foreign_enum
         ;       table_step_general
         ;       table_step_general_addr
         ;       table_step_general_poly
         ;       table_step_general_poly_addr
         ;       table_step_typeinfo
         ;       table_step_typeclassinfo
         ;       table_step_promise_implied.

     :- type table_step_stats
         --->    table_step_stats(
                     table_step_var_name                 :: string,
                     table_step_num_lookups              :: int,
                     table_step_num_lookups_is_dupl      :: int,
                     table_step_detail                   :: table_step_stat_details
                 ).

     :- type table_step_stat_details
         --->    step_stats_none
         ;       step_stats_start(
                     start_num_node_allocs               :: int,
                     start_num_node_bytes                :: int
                 )
         ;       step_stats_enum(
                     enum_num_node_allocs                :: int,
                     enum_num_node_bytes                 :: int
                 )
         ;       step_stats_hash(
                     hash_num_table_allocs               :: int,
                     hash_num_table_bytes                :: int,
                     hash_num_link_chunk_allocs          :: int,
                     hash_num_link_chunk_bytes           :: int,
                     hash_num_num_key_compares_not_dupl  :: int,
                     hash_num_num_key_compares_dupl      :: int,
                     hash_num_resizes                    :: int,
                     hash_resizes_num_old_entries        :: int,
                     hash_resizes_num_new_entries        :: int
                 )
         ;       step_stats_du(
                     du_num_node_allocs                  :: int,
                     du_num_node_bytes                   :: int,
                     du_num_arg_lookups                  :: int,
                     du_num_exist_lookups                :: int,

                     du_enum_num_node_allocs             :: int,
                     du_enum_num_node_bytes              :: int,

                     du_hash_num_table_allocs            :: int,
                     du_hash_num_table_bytes             :: int,
                     du_hash_num_link_chunk_allocs       :: int,
                     du_hash_num_link_chunk_bytes        :: int,
                     du_hash_num_num_key_compares_not_dupl :: int,
                     du_hash_num_num_key_compares_dupl   :: int,
                     du_hash_num_resizes                 :: int,
                     du_hash_resizes_num_old_entries     :: int,
                     du_hash_resizes_num_new_entries     :: int
                 )
         ;       step_stats_poly(
                     poly_du_num_node_allocs             :: int,
                     poly_du_num_node_bytes              :: int,
                     poly_du_num_arg_lookups             :: int,
                     poly_du_num_exist_lookups           :: int,

                     poly_enum_num_node_allocs           :: int,
                     poly_enum_num_node_bytes            :: int,

                     poly_hash_num_table_allocs          :: int,
                     poly_hash_num_table_bytes           :: int,
                     poly_hash_num_link_chunk_allocs     :: int,
                     poly_hash_num_link_chunk_bytes      :: int,
                     poly_hash_num_num_key_compares_not_dupl :: int,
                     poly_hash_num_num_key_compares_dupl :: int,
                     poly_hash_num_resizes               :: int,
                     poly_hash_resizes_num_old_entries   :: int,
                     poly_hash_resizes_num_new_entries   :: int
                 ).

     :- func table_stats_difference(table_stats, table_stats) = table_stats.

     :- pred write_table_stats(table_stats::in, io::di, io::uo) is det.

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

