kamlostuff / btrees.ml

(* pipelining *)
let ( |> ) x f = f x
let ( <| ) f x = f x
(* composition *)
let ( << ) f g x = f (g x)
let ( >> ) f g x = g (f x)
(* `right currying` *)
let flip f x y = f y x

exception Exit


module type SET =
sig
  type elem
  type set

  val empty : set
  val insert : elem -> set -> set
  val member : elem -> set -> bool
end


module type ORDERED =
sig
  type t

  val eq : t -> t -> bool
  val lt : t -> t -> bool
  val leq : t -> t -> bool
end


module UnbalancedSet = 
  functor (Element: ORDERED) ->
    struct 
      type elem = Element.t
      type tree = E | T of (tree * elem * tree)
      type set = tree
          
      let empty = E
        
      let insert x st = 
        let rec loop_none = function 
          | E -> T (E, x, E)
          | T (a, y, b) when (Element.lt x y) -> 
              let nl = loop_none a in T (nl, y, b)
          | T (a, y, b) ->
              let nr = loop_some y b in T (a, y, nr)
        and loop_some last = function 
          | E when x = last -> raise Exit
          | E -> T (E, x, E)
          | T (a, y, b) when (Element.lt x y) ->
              let nl = loop_some last a in T (nl, y, b)
          | T (a, y, b) -> 
              let nr = loop_some last b in T (a, y, nr)
        in try loop_none st with Exit -> st
                        
      let  member x collection = 
        let rec loop_none = function
          | E -> false
          | T (a, y, _) when (Element.lt x y) ->
              loop_none a
          | T (_, y, b) -> loop_some y b
        and loop_some last = function
          | E -> last = x
          | T (a, y, _) when (Element.lt x y) -> 
              loop_some last a
          | T (_, y, b) -> loop_some y b
        in loop_none
    end : SET 
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.