1. james woodyatt
  2. oni

Commits

jhwoodyatt  committed b897b1f

Add of_list_incr, of_list_decr, of_seq_incr and of_seq_decr functions.

  • Participants
  • Parent commits eb6e12f
  • Branches default

Comments (0)

Files changed (5)

File cf/cf_map.ml

View file
  • Ignore whitespace
     val extract: Key.t -> 'a t -> 'a * 'a t
     val delete: Key.t -> 'a t -> 'a t
     
+    val of_list: (Key.t * 'a) list -> 'a t
+    val of_list_incr: (Key.t * 'a) list -> 'a t
+    val of_list_decr: (Key.t * 'a) list -> 'a t
     val of_seq: (Key.t * 'a) Cf_seq.t -> 'a t
-    val of_list: (Key.t * 'a) list -> 'a t
+    val of_seq_incr: (Key.t * 'a) Cf_seq.t -> 'a t
+    val of_seq_decr: (Key.t * 'a) Cf_seq.t -> 'a t
 
+    val to_list_incr: 'a t -> (Key.t * 'a) list
+    val to_list_decr: 'a t -> (Key.t * 'a) list
     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

File cf/cf_map.mli

View file
  • Ignore whitespace
     *)
     val delete: Key.t -> 'a 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 [of_list_incr s] to compose a tree with the key-value pairs in the
+        ordered list [s].  Runs in linear time if the keys in the list [s] are
+        known to be in increasing order.  Otherwise, there is an additional
+        linear cost beyond [of_list s].
+    *)
+    val of_list_incr: (Key.t * 'a) list -> 'a t
+    
+    (** Use [of_list_decr s] to compose a tree with the key-value pairs in the
+        ordered list [s].  Runs in linear time if the keys in the list [s] are
+        known to be in decreasing order.  Otherwise, there is an additional
+        linear cost beyond [of_list s].
+    *)
+    val of_list_decr: (Key.t * 'a) list -> '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.
+    (** Use [of_seq_incr z] to compose a tree with the key-value pairs in the
+        ordered sequence [z].  Runs in linear time if the keys in the sequence
+        [z] are known to be in increasing order.  Otherwise, there is an
+        additional linear cost beyond [of_seq z].
     *)
-    val of_list: (Key.t * 'a) list -> 'a t
+    val of_seq_incr: (Key.t * 'a) Cf_seq.t -> 'a t
+    
+    (** Use [of_seq_decr z] to compose a tree with the key-value pairs in the
+        ordered sequence [z].  Runs in linear time if the keys in the sequence
+        [z] are known to be in decreasing order.  Otherwise, there is an
+        additional linear cost beyond [of_seq z].
+    *)
+    val of_seq_decr: (Key.t * 'a) Cf_seq.t -> 'a 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 [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_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.

File cf/cf_rbtree.ml

View file
  • Ignore whitespace
         with
         | Not_found ->
             u
+
+    let rec of_list_aux_ acc = function
+        | hd :: tl -> of_list_aux_ (replace hd acc) tl
+        | [] -> acc
     
-    let of_list =
-        let rec loop acc = function
-            | hd :: tl -> loop (replace hd acc) tl
-            | [] -> acc
+    let of_list s = of_list_aux_ nil s
+    
+    let rec of_seq_aux_ acc seq =
+        match Lazy.force seq with
+        | Cf_seq.P (hd, tl) -> of_seq_aux_ (replace hd acc) tl
+        | Cf_seq.Z -> acc
+    
+    let of_seq z = of_seq_aux_ nil z
+    
+    type 'a digit_t =
+        | Y of 'a node_t * 'a
+        | X of 'a node_t * 'a * 'a node_t * 'a
+
+    let rec accum_incr_ n x = function
+        | [] -> [ Y (n, x) ]
+        | Y (m, y) :: t -> X (m, y, n, x) :: t
+        | X (m, y, p, z) :: t -> Y (n, x) :: (accum_incr_ (B (y, m, p)) z t)
+
+    let rec accum_decr_ n x = function
+        | [] -> [ Y (n, x) ]
+        | Y (m, y) :: t -> X (n, x, m, y) :: t
+        | X (p, z, m, y) :: t -> Y (n, x) :: (accum_decr_ (B (y, p, m)) z t)
+    
+    let rec final_incr_ acc = function
+        | [] -> acc
+        | Y (m, y) :: t -> final_incr_ (B (y, m, acc)) t
+        | X (m, y, p, z) :: t -> final_incr_ (B (y, m, R (z, p, acc))) t
+    
+    let rec final_decr_ acc = function
+        | [] -> acc
+        | Y (m, y) :: t -> final_decr_ (B (y, acc, m)) t
+        | X (p, z, m, y) :: t -> final_decr_ (B (y, R (z, acc, p), m)) t
+
+    let of_list_incr =
+        let rec loop last acc = function
+            | hd :: tl -> 
+                if N.compare last hd > 0 then
+                    of_list_aux_ (replace hd (final_incr_ Z acc)) tl
+                else
+                    loop hd (accum_incr_ Z hd acc) tl
+            | [] ->
+                final_incr_ Z acc
+        in
+        function
+        | [] -> Z
+        | hd :: tl -> loop hd [ Y (Z, hd) ] tl
+
+    let of_list_decr =
+        let rec loop last acc = function
+            | hd :: tl -> 
+                if N.compare last hd < 0 then
+                    of_list_aux_ (replace hd (final_decr_ Z acc)) tl
+                else
+                    loop hd (accum_decr_ Z hd acc) tl
+            | [] ->
+                final_incr_ Z acc
+        in
+        function
+        | [] -> Z
+        | hd :: tl -> loop hd [ Y (Z, hd) ] tl
+
+    let of_seq_incr =
+        let rec loop last acc z =
+            match Lazy.force z with
+            | Cf_seq.P (hd, tl) -> 
+                if N.compare last hd > 0 then
+                    of_seq_aux_ (replace hd (final_incr_ Z acc)) tl
+                else
+                    loop hd (accum_incr_ Z hd acc) tl
+            | Cf_seq.Z ->
+                final_incr_ Z acc
         in
         fun z ->
-            loop nil z
+            match Lazy.force z with
+            | Cf_seq.Z -> Z
+            | Cf_seq.P (hd, tl) -> loop hd [ Y (Z, hd) ] tl
+
+    let of_seq_decr =
+        let rec loop last acc z =
+            match Lazy.force z with
+            | Cf_seq.P (hd, tl) -> 
+                if N.compare last hd < 0 then
+                    of_seq_aux_ (replace hd (final_decr_ Z acc)) tl
+                else
+                    loop hd (accum_decr_ Z hd acc) tl
+            | Cf_seq.Z ->
+                final_decr_ Z acc
+        in
+        fun z ->
+            match Lazy.force z with
+            | Cf_seq.Z -> Z
+            | Cf_seq.P (hd, tl) -> loop hd [ Y (Z, hd) ] tl
     
-    let of_seq =
-        let rec loop acc seq =
-            match Lazy.force seq with
-            | Cf_seq.P (hd, tl) -> loop (replace hd acc) tl
-            | Cf_seq.Z -> acc
-        in
-        fun seq ->
-            loop nil seq
-
     type 'a stack_t = ('a * 'a node_t) list
     
     let rec stack_min_ i = function

File cf/cf_set.ml

View file
  • Ignore whitespace
     val compare: t -> t -> int
     val subset: t -> t -> bool
     
+    val of_list: Element.t list -> t
+    val of_list_incr: Element.t list -> t
+    val of_list_decr: Element.t list -> t
+    
     val of_seq: Element.t Cf_seq.t -> t
-    val of_list: Element.t list -> t
-    
+    val of_seq_incr: Element.t Cf_seq.t -> t
+    val of_seq_decr: Element.t Cf_seq.t -> t
+
+    val to_list_incr: t -> Element.t list
+    val to_list_decr: t -> Element.t list
+
     val to_seq_incr: t -> Element.t Cf_seq.t
     val to_seq_decr: t -> Element.t Cf_seq.t
     
-    val to_list_incr: t -> Element.t list
-    val to_list_decr: t -> Element.t list
-
     val nearest_decr: Element.t -> t -> Element.t Cf_seq.t
     val nearest_incr: Element.t -> t -> Element.t Cf_seq.t
     

File cf/cf_set.mli

View file
  • Ignore whitespace
     (** 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_list s] to iterate a list of elements and compose a new set by
-        inserting them in order.
+    (** 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_list: Element.t list -> t
+    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.
         in order of decreasing ordinality.
     *)
     val to_seq_decr: t -> Element.t Cf_seq.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 [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