(*   
     Author: Mateusz Wykurz
     email: wykurz@gmail.com

     This code is based on work of Markus Mottl

     Copyright (C) 1999, 2000, 2001  Markus Mottl
     email:  markus@oefai.at
     www:    http://www.oefai.at/~markus

     Original source code in SML from:

     Purely Functional Data Structures
     Chris Okasaki
     Cambridge University Press, 1998
     Copyright (c) 1998 Cambridge University Press

     This source code is free software; you can redistribute it and/or
     modify it without any restrictions. It is distributed in the hope
     that it will be useful, but WITHOUT ANY WARRANTY.
*)

module BstFunctor (Element : Set.ORDERED) :
  (Set.SET with type elem = Element.elem) =
struct
  type elem = Element.elem
  type tree = E | T of tree * elem * tree
  type set = tree

  let empty() = E

  let rec member s x =
    match s with
      | E -> false
      | T (a, y, b) ->
          if Element.lt x y then member a x
          else if Element.lt y x then member b x
          else true

  let rec insert s x =
    match s with
        E -> T (E, x, E)
      | T (a, y, b) as s ->
          if Element.lt x y then T (insert a x, y, b)
          else if Element.lt y x then T (a, y, insert b x)
          else s

  let rec attach_left att t =
    match t with
        E -> att
      | T (a, x, b) ->
          T (attach_left att a, x, b)

  exception Set_is_empty

  let rec remove s x =
    match s with
      | E -> raise Set_is_empty
      | T (a, y, b) ->
          if Element.lt x y then T (remove a x, y, b)
          else if Element.lt y x then T (a, y, remove b x)
          else attach_left a b
end