(*---------------------------------------------------------------------------*
  INTERFACE  cf_set.mli

  Copyright (c) 2004-2006, James H. Woodyatt
  All rights reserved.

  Redistribution and use in source and binary forms, with or without
  modification, are permitted provided that the following conditions
  are met:

    Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.

    Redistributions in binary form must reproduce the above copyright
    notice, this list of conditions and the following disclaimer in
    the documentation and/or other materials provided with the
    distribution

  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  OF THE POSSIBILITY OF SUCH DAMAGE. 
 *---------------------------------------------------------------------------*)

(** A module type for functional set implementations (with enhancements over
    the {!Set} module in the standard library).
*)

(** {6 Overview}

    This module defines the common interface to the various implementations of
    functional sets in the {!Cf} library.
*)

module type T = sig
    
    (** The set type *)
    type t

    (** A module defining the type of the element.  Some set implementations
        may define more functions in this module for disambiguating keys from
        one another.
    *)
    module Element: sig type t end
    
    (** The empty set. *)
    val nil: t
    
    (** Use [empty s] to test whether the set [s] is the empty set. *)
    val empty: t -> bool
    
    (** Use [size s] to compute the size of the set [s]. *)
    val size: t -> int
    
    (** Use [member e s] to test whether the element [e] is a member of the set
        [s].
    *)
    val member: Element.t -> t -> bool
    
    (** Use [singleton e] to compose a new set containing only the element [e].
    *)
    val singleton: Element.t -> t
    
    (** Use [min s] to return the ordinally least element in the set [s].
        Raises [Not_found] if the set is empty.
    *)
    val min: t -> Element.t
    
    (** Use [min s] to return the ordinally greatest element in the set [s].
        Raises [Not_found] if the set is empty.
    *)
    val max: t -> Element.t
    
    (** Use [put e s] to obtain a new set produced by inserting the element [e]
        into the set [s].  If [s] already contains a member ordinally equal to
        [e] then it is replaced by [e] in the set returned.
    *)
    val put: Element.t -> t -> t
    
    (** Use [clear e s] to obtain a new set produced by deleting the element
        in the set [s] ordinally equal to the element [e].  If there is no such
        element in the set, then the set is returned unchanged.
    *)
    val clear: Element.t -> t -> t
    
    (** Use [union s1 s2] to obtain a new set from the union of the sets [s1]
        and [s2].  Elements of the new set belonging to the intersection are
        copied from [s2].
    *)
    val union: t -> t -> t
    
    (** Use [diff s1 s2] to obtain a new set from the difference of the sets
        [s1] and [s2].
    *)
    val diff: t -> t -> t
    
    (** Use [interset s1 s2] to obtain a new set from the intersection of the
        sets [s1] and [s2].  All the elements in the new set are copied from
        [s2].
    *)
    val intersect: t -> t -> t
    
    (** Use [compare s1 s2] to compare the sequence of elements in the set
        [s1] and the sequence of elements in the set [s2] in order of
        increasing ordinality.  Two sets are ordinally equal if the sequences
        of their elements are ordinally equal.
    *)
    val compare: t -> t -> int
    
    (** Use [subset s1 s2] to test whether the set [s1] is a subset of [s2]. *)
    val subset: t -> t -> bool
    
    (** Use [of_list s] to iterate a list of elements and compose a new set by
        inserting them in order.
    *)
    val of_list: Element.t list -> t
    
    (** Use [of_list_incr s] to compose the set with elements in the ordered
        list [s].  Runs in linear time if the list [s] is known to be in
        increasing order.  Otherwise, there is an additional linear cost beyond
        [of_list s].
    *)
    val of_list_incr: Element.t list -> t
    
    (** Use [of_list_decr s] to compose the set with elements in the ordered
        list [s].  Runs in linear time if the list [s] is known to be in
        decreasing order.  Otherwise, there is an additional linear cost beyond
        [of_list s].
    *)
    val of_list_decr: Element.t list -> t
    
    (** Use [of_seq z] to evaluate a sequence of elements and compose a new set
        by inserting them in order.
    *)
    val of_seq: Element.t Cf_seq.t -> t
    
    (** Use [of_seq_incr z] to compose the set with elements in the ordered
        sequence [z].  Runs in linear time if the sequence [z] is known to be
        in increasing order.  Otherwise, there is an additional linear cost
        beyond [of_seq z].
    *)
    val of_seq_incr: Element.t Cf_seq.t -> t
    
    (** Use [of_seq_decr z] to compose the set with elements in the ordered
        sequence [z].  Runs in linear time if the sequence [z] is known to be
        in decreasing order.  Otherwise, there is an additional linear cost
        beyond [of_seq z].
    *)
    val of_seq_decr: Element.t Cf_seq.t -> t
    
    (** Use [to_list_incr s] to produce the list of elements in the set [s]
        in order of increasing ordinality.
    *)
    val to_list_incr: t -> Element.t list
    
    (** Use [to_list_decr s] to produce the list of elements in the set [s]
        in order of decreasing ordinality.
    *)
    val to_list_decr: t -> Element.t list
    
    (** Use [to_seq_incr s] to produce the sequence of elements in the set [s]
        in order of increasing ordinality.
    *)
    val to_seq_incr: t -> Element.t Cf_seq.t
    
    (** Use [to_seq_decr s] to produce the sequence of elements in the set [s]
        in order of decreasing ordinality.
    *)
    val to_seq_decr: t -> Element.t Cf_seq.t

    (** Use [nearest_decr k s] to obtain the key-value pair ordinally less than
        or equal to the key [k] in the set [s].  Raises [Not_found] if the set
        is empty or all the keys are ordinally greater.
    *)
    val nearest_decr: Element.t -> t -> Element.t Cf_seq.t
    
    (** Use [nearest_incr k s] to obtain the element ordinally greater
        than or equal to the key [k] in the set [s].  Raises [Not_found] if the
        set is empty or all the keys are ordinally less.
    *)
    val nearest_incr: Element.t -> t -> Element.t Cf_seq.t
    
    (** Use [iterate f s] to apply the iterator function [f] to every element
        in the set [s] in arbitrary order (not increasing or decreasing).
    *)
    val iterate: (Element.t -> unit) -> t -> unit
    
    (** Use [predicate f s] to test whether all the elements in the set [s]
        satisfy the predicate function [f], visiting the elements in an
        arbitrary order (not increasing or decreasing) until [f] returns
        [false] or all elements are tested.
    *)
    val predicate: (Element.t -> bool) -> t -> bool
    
    (** Use [fold f a s] to fold the elements of the set [s] into the folding
        function [f] with the initial state [a], by applying the elements in
        an arbitrary order (not increasing or decreasing).
    *)
    val fold: ('a -> Element.t -> 'a) -> 'a -> t -> 'a
    
    (** Use [filter f s] to produce a new set comprised of all the elements of
        the set [s] that satisfy the filtering function [f], applying the
        elements in an arbitrary order (not increasing or decreasing).
    *)
    val filter: (Element.t -> bool) -> t -> t
    
    (** Use [partition f s] to produce two new sets by applying the
        partitioning function [f] to every element in the set [s] in an
        arbitrary order (not increasing or decreasing).  The first set returned
        contains all the elements for which applying [f] returns [true].  The
        second set returned contains all the elements for which applying [f]
        returns [false].
    *)
    val partition: (Element.t -> bool) -> t -> t * t
end

(*--- End of File [ cf_set.mli ] ---*)