View difference between Paste ID: j0aV3DJQ and

-
+(* Treap.fsi *)
 module Treap
     [<Sealed>]
     type Treap<'a> =
         member Contains : v:'a -> bool
         member Insert : v:'a -> Treap<'a>
         member Remove : v:'a -> Treap<'a>
         member Split : v:'a -> Treap<'a> * bool * Treap<'a>
         member Count : int
         member Max : 'a
         member Min : 'a
 
     val empty : ('a -> 'a -> int) -> Treap<'a>
     val toSeq : Treap<'a> -> seq<'a>
     val toSeqBack : Treap<'a> -> seq<'a>
 
 (* Treap.fs *)
 module Treap
     open System
 
     type 'a treap =
         | Nil of ('a -> 'a -> int) * Random
         | Node of ('a -> 'a -> int) * Random * int * 'a treap * 'a * 'a treap * int
         with
             member this.Comparer =
                 match this with
                 | Nil(comparer, rnd) -> comparer
                 | Node(comparer, rnd, priority, left, x, right, count) -> comparer
 
             member this.Rnd =
                 match this with
                 | Nil(comparer, rnd) -> rnd
                 | Node(comparer, rnd, priority, left, x, right, count) -> rnd
 
             member this.Priority =
                 match this with
                 | Nil(comparer, rnd) -> Int32.MinValue
                 | Node(comparer, rnd, priority, left, x, right, count) -> priority
 
             member this.Left =
                 match this with
                 | Nil(comparer, rnd) -> failwith "Empty treap"
                 | Node(comparer, rnd, priority, left, x, right, count) -> left
 
             member this.Right =
                 match this with
                 | Nil(comparer, rnd) -> failwith "Empty treap"
                 | Node(comparer, rnd, priority, left, x, right, count) -> right
 
             member this.Value =
                 match this with
                 | Nil(comparer, rnd) -> failwith "Empty treap"
                 | Node(comparer, rnd, priority, left, x, right, count) -> x
 
             member this.Count =
                 match this with
                 | Nil(comparer, rnd) -> 0
                 | Node(comparer, rnd, priority, left, x, right, count) -> count
 
             member this.Min =
                 match this with
                 | Nil(comparer, rnd) -> failwith "Empty treap"
                 | Node(comparer, rnd, priority, Nil(comparer', rnd'), x, right, count) -> x
                 | Node(comparer, rnd, priority, left, x, right, count) -> left.Min
 
             member this.Max =
                 match this with
                 | Nil(comparer, rnd) -> failwith "Empty treap"
                 | Node(comparer, rnd, priority, left, x, Nil(comparer', rnd'), count) -> x
                 | Node(comparer, rnd, priority, left, x, right, count) -> right.Max
 
             member this.IsEmpty =
                 match this with
                 | Nil(comparer, rnd) -> true
                 | Node(comparer, rnd, priority, left, x, right, count) -> false
 
 
 
     let nil f = Nil(f, new Random())
     let nextPriority (rnd : Random) = rnd.Next(Int32.MinValue, Int32.MaxValue)
     let makeWithPriority (l : 'a treap, v, r : 'a treap, priority) = Node(l.Comparer, l.Rnd, priority, l, v, r, l.Count + r.Count + 1)
     let make(l : 'a treap, v, r) = makeWithPriority(l, v, r, l.Rnd.Next(Int32.MinValue, Int32.MaxValue))
 
     (*
          q      Right Rotation       p
        /   \    --------------+    /   \
       p     c                     a     q
      / \        Left Rotation          / \
     a   b       +-------------        b   c
     *)
 
     let rotLeft = function
         | Node(pcomparer, prnd, ppriority, a, p, Node(qcomparer, qrnd, qpriority, b, q, c, qcount), pcount) ->
             makeWithPriority(makeWithPriority(a, p, b, ppriority), q, c, qpriority)
         | node -> node
 
     let rotRight = function
         | Node(qcomparer, qrnd, qpriority, Node(pcomparer, prnd, ppriority, a, p, b, pcount), q, c, qcount) ->
             makeWithPriority(a, p, makeWithPriority(b, q, c, qpriority), ppriority)
         | node -> node
 
     let balLeft = function
         | Node(comparer, rnd, priority, l, x, r, count) as node when priority < l.Priority -> rotRight node
         | node -> node
 
     let balRight = function
         | Node(comparer, rnd, priority, l, x, r, count) as node when priority < r.Priority -> rotLeft node
         | node -> node
 
     let rec contains v = function
         | Nil(comparer, rnd) -> false
         | Node(comparer, rnd, priority, left, x, right, count) ->
             let compare = comparer v x
             if compare < 0 then contains v left
             elif compare > 0 then contains v right
             else true
 
     let rec insert v = function
         | Nil(comparer, rnd) as node -> make(node, v, node)
         | Node(comparer, rnd, priority, left, x, right, count) as node ->
             let compare = comparer v x
             if compare < 0 then makeWithPriority(insert v left, x, right, priority) |> balLeft
             elif compare > 0 then makeWithPriority(left, x, insert v right, priority) |> balRight
             else node
 
     let rec remove v = function
         | Nil(comparer, rnd) as node -> node
         | Node(comparer, rnd, priority, left, x, right, count) as node ->
             let compare = comparer v x
             if compare < 0 then makeWithPriority(remove v left, x, right, priority)
             elif compare > 0 then makeWithPriority(left, x, remove v right, priority)
             else
                 if not (left.IsEmpty) then
                     let successor = left.Max
                     let l' = remove successor left
                     makeWithPriority(l', successor, right, priority)
                 elif not (right.IsEmpty) then
                     let successor = right.Min
                     let r' = remove successor right
                     makeWithPriority(left, successor, r', priority)
                 else
                     left // guaranteed to be nil
 
     let rec split v = function
         | Nil(comparer, rnd) as node -> node, false, node
         | Node(comparer, rnd, priority, left, x, right, count) as node ->
             let compare = comparer v x
             if compare < 0 then
                 let left', found, r' = split v left
                 let right' = makeWithPriority(r', x, right, priority)
                 left', found, right'
             elif compare > 0 then
                 let l', found, right' = split v right
                 let left' = makeWithPriority(left, x, l', priority)
                 left', found, right'
             else
                 left, true, right
 
     (*
     // used for debugging in fsi
 
     let print t =
         let rec loop indent = function
             | Nil(comparer, rnd) -> ()
             | Node(comparer, rnd, priority, left, x, right, count) ->
                 let spaces = new String(' ', indent * 4)
                 loop (indent + 1) right
                 printfn "%s(%s, %i)" spaces (x.ToString()) priority
                 loop (indent + 1) left
         loop 0 t
 
     let insert' v t =
         let t' = insert v t
         print t'
         t'
 
     let remove' v t =
         let t' = remove v t
         print t'
         t'
 
     *)
 
     [<Sealed>]
     type Treap<'a>(t : 'a treap) =
         member this.Internal = t
         member this.Insert v = Treap(insert v t)
         member this.Remove v = Treap(remove v t)
         member this.Split v = let l, found, r = split v t in Treap(l), found, Treap(r)
         member this.Contains v = contains v t
         member this.Count = t.Count
         member this.Min = t.Min
         member this.Max = t.Max
 
     let empty f = Treap(nil f)
 
     let toSeq (t : Treap<'a>) =
         let rec loop = function
             | Nil(comparer, rnd) -> Seq.empty
             | Node(comparer, rnd, priority, l, x, r, count) -> seq { yield! loop l; yield x; yield! loop r }
         loop t.Internal
 
     let toSeqBack (t : Treap<'a>) =
         let rec loop = function
             | Nil(comparer, rnd) -> Seq.empty
             | Node(comparer, rnd, priority, l, x, r, count) -> seq { yield! loop r; yield x; yield! loop l }
         loop t.Internal