1. camlspotter
  2. spotlib

Commits

camlspotter  committed b158229

updates

  • Participants
  • Parent commits b76d273
  • Branches default

Comments (0)

Files changed (7)

File lib/OMakefile

View file
    xprintf
    xsys
    xset
+   xint64
    phantom
    weaktbl
    hashset

File lib/spot.ml

View file
 end
 
 module Set = Xset
+
+module Int64 = struct
+  include Int64
+  include Xint64
+end

File lib/xint64.ml

View file
+open Int64
+
+let ( + ) = add
+let ( - ) = sub
+let ( * ) = mul
+let ( / ) = div
+let (mod) =rem

File lib/xlist.ml

View file
   | [] -> []
   | [y] -> [y]
   | y::ys -> y::x::intersperse x ys
+
+let rec last = function
+  | [] -> failwith "Xlist.last"
+  | [x] -> x
+  | _::xs -> last xs
+

File lib/xlist.mli

View file
   *)
 
 val intersperse : 'a -> 'a list -> 'a list
+
+val last : 'a list -> 'a
+  (** raises Failure when the argument is [].
+      [last [1;2;3] = 3]
+  *)

File lib/xset.ml

View file
   val one : elt -> t (** singleton *)
   val unions : t list -> t
   val to_list : t -> elt list (** elements *)
+
+  val middle : t -> elt option (** find the middle element in [t] *)
+  val find : elt -> t -> elt option (** find the "same" element as [elt] in [t] *)
 end
 
 module Make(O : OrderedType) = struct
   let one = singleton
   let unions = List.fold_left union empty
   let to_list = elements
+
+  let middle t =
+    if is_empty t then None
+    else
+      let found = ref None in
+      try
+	ignore (filter (fun elt -> 
+	  found := Some elt;
+	  raise Exit) t);
+	assert false
+      with
+      | Exit -> !found
+
+  let rec find elt t =
+    match middle t with
+    | None -> None
+    | Some elt' ->
+	match O.compare elt elt' with 
+	| 0 -> Some elt'
+	| -1 ->
+	    let l, present, _ = split elt' t in
+	    assert present;
+	    find elt l
+	| 1 -> 
+	    let _, present, r = split elt' t in
+	    assert present;
+	    find elt r
+	| _ -> assert false
 end
 

File lib/xset.mli

View file
   val one : elt -> t (** singleton *)
   val unions : t list -> t
   val to_list : t -> elt list (** elements *)
+
+  val middle : t -> elt option (** find the middle element in [t] *)
+  val find : elt -> t -> elt option (** find the "same" element as [elt] in [t] *)
 end
 
 module Make(O : Set.OrderedType) : S