Commits

Anonymous committed 624ef71

Submit cf-0.2 release.

Comments (0)

Files changed (6)

+(*---------------------------------------------------------------------------*
+  IMPLEMENTATION  cf_heap.ml
+
+  Copyright (c) 2004, 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. 
+ *---------------------------------------------------------------------------*)
+
+module type T = sig
+    type t
+
+    module Element: sig type t end
+    
+    val nil: t
+    val empty: t -> bool
+    val size: t -> int
+    val head: t -> Element.t
+    val tail: t -> t
+    val pop: t -> (Element.t * t) option
+    val put: Element.t -> t -> t
+    val merge: t -> t -> t
+    val iterate: (Element.t -> unit) -> t -> unit
+    val predicate: (Element.t -> bool) -> t -> bool
+    val fold: ('b -> Element.t -> 'b) -> 'b -> t -> 'b
+    val filter: (Element.t -> bool) -> t -> t
+    val partition: (Element.t -> bool) -> t -> t * t
+    val of_seq: Element.t Cf_seq.t -> t
+    val of_list: Element.t list -> t
+    val to_seq: t -> Element.t Cf_seq.t
+    val to_seq2: t -> (Element.t * t) Cf_seq.t
+end
+
+(*--- End of File [ cf_heap.ml ] ---*)
+(*---------------------------------------------------------------------------*
+  INTERFACE  cf_heap.mli
+
+  Copyright (c) 2004, 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 heap implementations. *)
+
+(** {6 Module Type} *)
+
+(**
+    This module defines the common interface to functional heaps in the {!Cf}
+    library.
+*)
+module type T = sig
+    
+    (** The heap type *)
+    type t
+
+    (** A module defining the type of the element.  Some heap implementations
+        may define more functions in this module for disambiguating elements
+        from one another.
+    *)
+    module Element: sig type t end
+    
+    (** The empty heap. *)
+    val nil: t
+    
+    (** Use [empty h] to test whether the heap [h] is empty. *)
+    val empty: t -> bool
+    
+    (** Use [size h] to count the number of elements in the heap [h].  Runs
+        in O(n) time and O(log N) space.
+    *)
+    val size: t -> int
+    
+    (** Use [head h] to obtain the element on the top of the heap [h].  Raises
+        [Not_found] if the heap is empty.
+    *)
+    val head: t -> Element.t
+    
+    (** Use [tail h] to obtain the heap produced by discarding the element on
+        the top of heap [h].  If [h] is the empty heap, then the empty heap is
+        returned.
+    *)
+    val tail: t -> t
+    
+    (** Use [pop h] to obtain the head and the tail of a heap [h] in one
+        operation.  Returns [None] if the [h] is empty.
+    *)
+    val pop: t -> (Element.t * t) option
+    
+    (** Use [put e h] to obtain a new heap that is the result of inserting
+        the element [e] into the heap [h].
+    *)
+    val put: Element.t -> t -> t
+    
+    (** Use [merge h1 h2] to obtain a new heap that is the result of merging
+        all the elements of [h1] and [h2] into a single heap.
+    *)
+    val merge: t -> t -> t
+
+    (** Use [iterate f h] to apply [f] to every element in the heap [h] in an
+        arbitrary order (not top to bottom).  Runs in O(n) time and O(1) space.
+    *)
+    val iterate: (Element.t -> unit) -> t -> unit
+    
+    (** Use [predicate f h] to test whether all the elements in heap [h]
+        satisfy the predicate function [f].  Runs in O(n) time (with a short
+        cut when an element is found to fail the predicate) and O(1) space.
+        Visits the elements in the heap in arbitrary order (not top to bottom).
+    *)
+    val predicate: (Element.t -> bool) -> t -> bool
+    
+    (** Use [fold f s h] to produce the result of folding a value [s] into
+        the elements of heap [h] with the folding function [f] in an arbitrary
+        order (not top to bottom).  Runs in O(n) time and O(1) space.
+    *)
+    val fold: ('b -> Element.t -> 'b) -> 'b -> t -> 'b
+    
+    (** Use [filter f h] to apply [f] to each element in the heap [h] in an
+        arbitrary order (not to top bottom), and produce a new heap that
+        contains only those elements for which [f pair] returned [true].
+    *)
+    val filter: (Element.t -> bool) -> t -> t
+    
+    (** Use [partition f h] to obtain a pair of new heaps that are the result
+        of applying the partitioning function [f] to each element in the heap
+        [h] in an arbitrary order (not top to bottom).  The first heap returned
+        will contain all the elements for which [f pair] returned true, and the
+        second heap will return all the remaining elements.
+    *)
+    val partition: (Element.t -> bool) -> t -> t * t
+
+    (** Use [of_seq z] to construct a heap from a sequence of elements.
+        Evaluates the whole sequence.  Runs in O(n) time and O(1) space.
+    *)
+    val of_seq: Element.t Cf_seq.t -> t
+    
+    (** Use [of_list s] to construct a heap from a list of elements.  Runs in
+        O(n) time and O(1) space.
+    *)
+    val of_list: Element.t list -> t
+    
+    (** Use [to_seq h] to produce a sequence of elements in top to bottom order
+        from the heap [h].
+    *)
+    val to_seq: t -> Element.t Cf_seq.t
+    
+    (** Use [to_seq2 h] to produce a sequence of elements from the heap [h]
+        where the first element of each pair is a key-value pair obtained from
+        the head of the heap, and the second element of the pair is the
+        corresponding tail of the heap.
+    *)
+    val to_seq2: t -> (Element.t * t) Cf_seq.t
+end
+
+(*--- End of File [ cf_heap.mli ] ---*)
+(*---------------------------------------------------------------------------*
+  IMPLEMENTATION  cf_map.ml
+
+  Copyright (c) 2004, 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. 
+ *---------------------------------------------------------------------------*)
+
+module type T = sig    
+    type +'a t    
+
+    module Key: sig type t end
+        
+    val nil: 'a t
+    val empty: 'a t -> bool
+    val size: 'a t -> int
+    
+    val min: 'a t -> (Key.t * 'a)    
+    val max: 'a t -> (Key.t * 'a)
+    
+    val search: Key.t -> 'a t -> 'a
+    val member: Key.t -> 'a t -> bool
+
+    val insert: (Key.t * 'a) -> 'a t -> 'a t * 'a option
+    val replace: (Key.t * 'a) -> 'a t -> 'a t
+    val modify: Key.t -> ('a -> 'a) -> 'a t -> 'a t
+    val extract: Key.t -> 'a t -> 'a * 'a t
+    val delete: Key.t -> 'a t -> 'a t
+    
+    val of_seq: (Key.t * 'a) Cf_seq.t -> 'a t
+    val of_list: (Key.t * 'a) list -> 'a t
+
+    val to_seq_incr: 'a t -> (Key.t * 'a) Cf_seq.t
+    val to_seq_decr: 'a t -> (Key.t * 'a) Cf_seq.t
+    val to_list_incr: 'a t -> (Key.t * 'a) list
+    val to_list_decr: 'a t -> (Key.t * 'a) list
+
+    val nearest_decr: Key.t -> 'a t -> (Key.t * 'a) Cf_seq.t
+    val nearest_incr: Key.t -> 'a t -> (Key.t * 'a) Cf_seq.t
+
+    val iterate: ((Key.t * 'a) -> unit) -> 'a t -> unit
+    val predicate: ((Key.t * 'a) -> bool) -> 'a t -> bool
+    val fold: ('b -> (Key.t * 'a) -> 'b) -> 'b -> 'a t -> 'b
+    val filter: ((Key.t * 'a) -> bool) -> 'a t -> 'a t
+    val map: ((Key.t * 'a) -> 'b) -> 'a t -> 'b t
+    val optmap: ((Key.t * 'a) -> 'b option) -> 'a t -> 'b t
+    val partition: ((Key.t * 'a) -> bool) -> 'a t -> 'a t * 'a t
+end
+
+(*--- End of File [ cf_map.ml ] ---*)
+(*---------------------------------------------------------------------------*
+  INTERFACE  cf_map.mli
+
+  Copyright (c) 2004, 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 associative array implementations (with functional
+    enhancements over the {!Map} module in the standard library).
+*)
+
+(** {6 Overview}
+    
+    This module defines the common interface to the various implementations of
+    functional associative arrays in the {!Cf} library.
+*)
+
+module type T = sig    
+    (** The tree type. *)
+    type +'a t
+    
+    (** A module defining the type of the key.  Some map implementations may
+        define more functions in this module for disambiguating keys from one
+        another.
+    *)
+    module Key: sig type t end
+            
+    (** The empty tree. *)
+    val nil: 'a t
+    
+    (** Use [empty m] to test whether the tree [m] is empty. *)
+    val empty: 'a t -> bool
+    
+    (** Use [size m] to count the number of elements in the tree [m]. *)
+    val size: 'a t -> int
+    
+    (** Use [min m] to obtain the key-value pair with the ordinally minimum key
+        in the tree [m].  Raises [Not_found] if the tree is empty.
+    *)
+    val min: 'a t -> (Key.t * 'a)
+    
+    (** Use [max m] to obtain the key-value pair with the ordinally maximum key
+        in the tree [m].  Raises [Not_found] if the tree is empty.
+    *)
+    val max: 'a t -> (Key.t * 'a)
+    
+    (** Use [search k m] to obtain the value associated with the key [k] in the
+        tree [m].  Raise [Not_found] if the tree does not contain the key.
+    *)
+    val search: Key.t -> 'a t -> 'a
+    
+    (** Use [member k m] to test whether the tree [m] contains the key [k]. *)
+    val member: Key.t -> 'a t -> bool
+
+    (** Use [insert p m] to insert the key-value pair [p] into the tree [m],
+        producing a new tree with the inserted element and, if the key [k] is
+        already present in [m], the value replaced by the insertion.
+    *)
+    val insert: (Key.t * 'a) -> 'a t -> 'a t * 'a option
+    
+    (** Use [replace p m] to obtain a new tree produced by inserting the
+        key-value pair [p] into the tree [m], replacing any existing pair
+        associated to the same key.
+    *)
+    val replace: (Key.t * 'a) -> 'a t -> 'a t
+    
+    (** Use [modify k f m] to obtain a new tree produced by replacing the value
+        in the tree [m] associated with the key [k] with the result of applying
+        it to the continuation function [f].  Raises [Not_found] if the tree
+        does not contain the key.
+    *)
+    val modify: Key.t -> ('a -> 'a) -> 'a t -> 'a t
+    
+    (** Use [extract k m] to obtain the value associated with the key [k] in
+        the tree [m] and a new tree with the key deleted from the tree.  Raises
+        [Not_found] if the tree does not contain the key.
+    *)
+    val extract: Key.t -> 'a t -> 'a * 'a t
+    
+    (** Use [delete k m] to obtain a new tree produced by deleting the key [k]
+        from the tree [m].  If the tree does not contain the key, then the
+        function simply returns its argument.
+    *)
+    val delete: Key.t -> 'a t -> 'a t
+    
+    (** Use [of_seq z] to compose a tree by evaluating the entire sequence of
+        key-value pairs [z] and inserting them in order into a new tree.
+    *)
+    val of_seq: (Key.t * 'a) Cf_seq.t -> 'a t
+    
+    (** Use [of_list s] to compose a tree by iterating the list of key-value
+        pairs [s] and inserting them in order into a new tree.
+    *)
+    val of_list: (Key.t * 'a) list -> 'a t
+
+    (** Use [to_seq_incr m] to obtain a sequence of the key-value pairs in the
+        tree [m] in order of increasing ordinality.
+    *)
+    val to_seq_incr: 'a t -> (Key.t * 'a) Cf_seq.t
+
+    (** Use [to_seq_decr m] to obtain a sequence of the key-value pairs in the
+        tree [m] in order of descreasing ordinality.
+    *)
+    val to_seq_decr: 'a t -> (Key.t * 'a) Cf_seq.t
+
+    (** Use [to_list_incr m] to obtain a sequence of the key-value pairs in the
+        tree [m] in order of increasing ordinality.
+    *)
+    val to_list_incr: 'a t -> (Key.t * 'a) list
+
+    (** Use [to_list_decr m] to obtain a sequence of the key-value pairs in the
+        tree [m] in order of descreasing ordinality.
+    *)
+    val to_list_decr: 'a t -> (Key.t * 'a) list
+
+    (** Use [nearest_decr k m] to obtain the key-value pair ordinally less than
+        or equal to the key [k] in the map [m].  Raises [Not_found] if the map
+        is empty or all the keys are ordinally greater.
+    *)
+    val nearest_decr: Key.t -> 'a t -> (Key.t * 'a) Cf_seq.t
+    
+    (** Use [nearest_incr k m] to obtain the key-value pair ordinally greater
+        than or equal to the key [k] in the map [m].  Raises [Not_found] if the
+        map is empty or all the keys are ordinally less.
+    *)
+    val nearest_incr: Key.t -> 'a t -> (Key.t * 'a) Cf_seq.t
+    
+    (** Use [iterate f m] to apply the function [f] to each key-value pair in
+        the tree [m] in an arbitrary order (not increasing or decreasing).
+    *)
+    val iterate: ((Key.t * 'a) -> unit) -> 'a t -> unit
+    
+    (** Use [predicate f m] to test whether all the key-value pairs in the tree
+        [m] satisfy the predicate function [f].  The nodes of the tree are
+        visited in an arbitrary order (not increasing or decreasing).
+    *)
+    val predicate: ((Key.t * 'a) -> bool) -> 'a t -> bool
+
+    (** Use [fold f s m] to fold the every key-value pair in the tree [m] into
+        the state [s] with the folding function [f], visiting the elements in
+        an arbitrary order (not increasing or decreasing).  Runs in O(log N)
+        space, i.e. not tail-recursive.
+    *)
+    val fold: ('b -> (Key.t * 'a) -> 'b) -> 'b -> 'a t -> 'b
+    
+    (** Use [filter f m] to obtain a new tree comprised of all the key-value
+        pairs in the tree [m] that satisfy the filtering function [f].  The
+        elements in [m] are visited in arbitrary order (not increasing or
+        decreasing).  Runs in O(log N) space, i.e. not tail-recursive.
+    *)
+    val filter: ((Key.t * 'a) -> bool) -> 'a t -> 'a t
+    
+    (** Use [map f m] to obtain a new tree produced by applying the mapping
+        function [f] to the key and the value of each key-value pair in the
+        tree [m] and associating the resulting value to the key in the new
+        tree.  Elements in the tree are visited in arbitrary order (not
+        increasing or descreasing.  Runs in O(log N) space, i.e. not
+        tail-recursive.
+    *)
+    val map: ((Key.t * 'a) -> 'b) -> 'a t -> 'b t
+    
+    (** Use [optmap f m] to obtain a new tree produced by applying the mapping
+        function [f] to the key and the value of each key-value pair in the
+        tree [m] and associating the resulting value to the key in the new
+        tree.  If the function [f] returns [None] then no value for that key
+        will be present in the new tree.  Elements in the tree are visited in
+        arbitrary order (not increasing or descreasing.  Runs in O(log N)
+        space, i.e. not tail-recursive.
+    *)
+    val optmap: ((Key.t * 'a) -> 'b option) -> 'a t -> 'b t
+    
+    (** Use [partition f m] to obtain a pair of new trees produced by applying
+        the partitioning function [f] to all the elements in the tree [m] in an
+        arbitrary order (not increasing or descreasing).  The first tree will
+        contain all the elements for which [f] returns [true], and the second
+        tree will have all the elements for which [f] returns [false].  Runs in
+        O(log N) space, i.e. not tail-recursive.
+    *)
+    val partition: ((Key.t * 'a) -> bool) -> 'a t -> 'a t * 'a t
+end
+
+(*--- End of File [ cf_map.mli ] ---*)
     val compare: t -> t -> int
 end
 
-module type KV_Pair_T = sig
-    module Key: Total_T
-    type 'a t = Key.t * 'a
-end
-
-module KV_Pair(Key: Total_T) = struct
-    module Key = Key
-    type 'a t = Key.t * 'a
-end
-
 module Int_order = struct
     type t = int
     let compare a b = a - b

cf/cf_ordered.mli

     val compare: t -> t -> int
 end
 
-(** An key-value ordered pair, as defined by the [KV_Pair(Key: Total_T)]
-    functor, in which the first element is the key and the second element is
-    the value.
-*)
-module type KV_Pair_T = sig
-
-    (** The module used as the argument of the [KV_Pair(Key: Total_T)]
-        functor used to compose modules of this type.
-    *)
-    module Key: Total_T
-    
-    (** An ordered pair, whose first element is ordered using the ordering
-        function defined in the [Key] module.
-    *)
-    type 'a t = Key.t * 'a
-end
-
-(** A functor to define a key-value pair. *)
-module KV_Pair(Key: Total_T): KV_Pair_T with module Key = Key
-
-(** The order of integers *)
+(** The order of integers. *)
 module Int_order: Total_T with type t = int
 
 (*--- End of File [ cf_ordered.mli ] ---*)
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.