Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- (* 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement