ocamlspot / xset.ml

(***********************************************************************)
(*                                                                     *)
(*                            OCamlSpotter                             *)
(*                                                                     *)
(*                             Jun FURUSE                              *)
(*                                                                     *)
(*   Copyright 2008, 2009 Jun Furuse. All rights reserved.             *)
(*   This file is distributed under the terms of the GNU Library       *)
(*   General Public License, with the special exception on linking     *)
(*   described in file LICENSE.                                        *)
(*                                                                     *)
(***********************************************************************)

(* Set with binary custom search *)

module type OrderedType = Set.OrderedType

module type S = sig
  include Set.S
  val middle : t -> elt option
  val find : elt -> t -> elt option
end

module Make(Ord : OrderedType) : S with type elt = Ord.t = struct
  include Set.Make(Ord)

  (* find the middle element in [t] *)
  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

  (* find the "same" element as [elt] in [t] *)
  let rec find elt t =
    match middle t with
    | None -> None
    | Some elt' ->
	match Ord.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
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.