Want more features on Pastebin? Sign Up, it's FREE!
Guest

Juliet

By: a guest on Aug 6th, 2010  |  syntax: OCaml  |  size: 8.01 KB  |  views: 19  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. (* Treap.fsi *)
  2. module Treap
  3.     [<Sealed>]
  4.     type Treap<'a> =
  5.         member Contains : v:'a -> bool
  6.         member Insert : v:'a -> Treap<'a>
  7.         member Remove : v:'a -> Treap<'a>
  8.         member Split : v:'a -> Treap<'a> * bool * Treap<'a>
  9.         member Count : int
  10.         member Max : 'a
  11.         member Min : 'a
  12.  
  13.     val empty : ('a -> 'a -> int) -> Treap<'a>
  14.     val toSeq : Treap<'a> -> seq<'a>
  15.     val toSeqBack : Treap<'a> -> seq<'a>
  16.  
  17. (* Treap.fs *)
  18. module Treap
  19.     open System
  20.  
  21.     type 'a treap =
  22.         | Nil of ('a -> 'a -> int) * Random
  23.         | Node of ('a -> 'a -> int) * Random * int * 'a treap * 'a * 'a treap * int
  24.         with
  25.             member this.Comparer =
  26.                 match this with
  27.                 | Nil(comparer, rnd) -> comparer
  28.                 | Node(comparer, rnd, priority, left, x, right, count) -> comparer
  29.  
  30.             member this.Rnd =
  31.                 match this with
  32.                 | Nil(comparer, rnd) -> rnd
  33.                 | Node(comparer, rnd, priority, left, x, right, count) -> rnd
  34.  
  35.             member this.Priority =
  36.                 match this with
  37.                 | Nil(comparer, rnd) -> Int32.MinValue
  38.                 | Node(comparer, rnd, priority, left, x, right, count) -> priority
  39.  
  40.             member this.Left =
  41.                 match this with
  42.                 | Nil(comparer, rnd) -> failwith "Empty treap"
  43.                 | Node(comparer, rnd, priority, left, x, right, count) -> left
  44.  
  45.             member this.Right =
  46.                 match this with
  47.                 | Nil(comparer, rnd) -> failwith "Empty treap"
  48.                 | Node(comparer, rnd, priority, left, x, right, count) -> right
  49.  
  50.             member this.Value =
  51.                 match this with
  52.                 | Nil(comparer, rnd) -> failwith "Empty treap"
  53.                 | Node(comparer, rnd, priority, left, x, right, count) -> x
  54.  
  55.             member this.Count =
  56.                 match this with
  57.                 | Nil(comparer, rnd) -> 0
  58.                 | Node(comparer, rnd, priority, left, x, right, count) -> count
  59.  
  60.             member this.Min =
  61.                 match this with
  62.                 | Nil(comparer, rnd) -> failwith "Empty treap"
  63.                 | Node(comparer, rnd, priority, Nil(comparer', rnd'), x, right, count) -> x
  64.                 | Node(comparer, rnd, priority, left, x, right, count) -> left.Min
  65.  
  66.             member this.Max =
  67.                 match this with
  68.                 | Nil(comparer, rnd) -> failwith "Empty treap"
  69.                 | Node(comparer, rnd, priority, left, x, Nil(comparer', rnd'), count) -> x
  70.                 | Node(comparer, rnd, priority, left, x, right, count) -> right.Max
  71.  
  72.             member this.IsEmpty =
  73.                 match this with
  74.                 | Nil(comparer, rnd) -> true
  75.                 | Node(comparer, rnd, priority, left, x, right, count) -> false
  76.  
  77.  
  78.  
  79.     let nil f = Nil(f, new Random())
  80.     let nextPriority (rnd : Random) = rnd.Next(Int32.MinValue, Int32.MaxValue)
  81.     let makeWithPriority (l : 'a treap, v, r : 'a treap, priority) = Node(l.Comparer, l.Rnd, priority, l, v, r, l.Count + r.Count + 1)
  82.     let make(l : 'a treap, v, r) = makeWithPriority(l, v, r, l.Rnd.Next(Int32.MinValue, Int32.MaxValue))
  83.  
  84.     (*
  85.          q      Right Rotation       p
  86.        /   \    --------------+    /   \
  87.       p     c                     a     q
  88.      / \        Left Rotation          / \
  89.     a   b       +-------------        b   c
  90.     *)
  91.  
  92.     let rotLeft = function
  93.         | Node(pcomparer, prnd, ppriority, a, p, Node(qcomparer, qrnd, qpriority, b, q, c, qcount), pcount) ->
  94.             makeWithPriority(makeWithPriority(a, p, b, ppriority), q, c, qpriority)
  95.         | node -> node
  96.  
  97.     let rotRight = function
  98.         | Node(qcomparer, qrnd, qpriority, Node(pcomparer, prnd, ppriority, a, p, b, pcount), q, c, qcount) ->
  99.             makeWithPriority(a, p, makeWithPriority(b, q, c, qpriority), ppriority)
  100.         | node -> node
  101.  
  102.     let balLeft = function
  103.         | Node(comparer, rnd, priority, l, x, r, count) as node when priority < l.Priority -> rotRight node
  104.         | node -> node
  105.  
  106.     let balRight = function
  107.         | Node(comparer, rnd, priority, l, x, r, count) as node when priority < r.Priority -> rotLeft node
  108.         | node -> node
  109.  
  110.     let rec contains v = function
  111.         | Nil(comparer, rnd) -> false
  112.         | Node(comparer, rnd, priority, left, x, right, count) ->
  113.             let compare = comparer v x
  114.             if compare < 0 then contains v left
  115.             elif compare > 0 then contains v right
  116.             else true
  117.  
  118.     let rec insert v = function
  119.         | Nil(comparer, rnd) as node -> make(node, v, node)
  120.         | Node(comparer, rnd, priority, left, x, right, count) as node ->
  121.             let compare = comparer v x
  122.             if compare < 0 then makeWithPriority(insert v left, x, right, priority) |> balLeft
  123.             elif compare > 0 then makeWithPriority(left, x, insert v right, priority) |> balRight
  124.             else node
  125.  
  126.     let rec remove v = function
  127.         | Nil(comparer, rnd) as node -> node
  128.         | Node(comparer, rnd, priority, left, x, right, count) as node ->
  129.             let compare = comparer v x
  130.             if compare < 0 then makeWithPriority(remove v left, x, right, priority)
  131.             elif compare > 0 then makeWithPriority(left, x, remove v right, priority)
  132.             else
  133.                 if not (left.IsEmpty) then
  134.                     let successor = left.Max
  135.                     let l' = remove successor left
  136.                     makeWithPriority(l', successor, right, priority)
  137.                 elif not (right.IsEmpty) then
  138.                     let successor = right.Min
  139.                     let r' = remove successor right
  140.                     makeWithPriority(left, successor, r', priority)
  141.                 else
  142.                     left // guaranteed to be nil
  143.  
  144.     let rec split v = function
  145.         | Nil(comparer, rnd) as node -> node, false, node
  146.         | Node(comparer, rnd, priority, left, x, right, count) as node ->
  147.             let compare = comparer v x
  148.             if compare < 0 then
  149.                 let left', found, r' = split v left
  150.                 let right' = makeWithPriority(r', x, right, priority)
  151.                 left', found, right'
  152.             elif compare > 0 then
  153.                 let l', found, right' = split v right
  154.                 let left' = makeWithPriority(left, x, l', priority)
  155.                 left', found, right'
  156.             else
  157.                 left, true, right
  158.  
  159.     (*
  160.     // used for debugging in fsi
  161.  
  162.     let print t =
  163.         let rec loop indent = function
  164.             | Nil(comparer, rnd) -> ()
  165.             | Node(comparer, rnd, priority, left, x, right, count) ->
  166.                 let spaces = new String(' ', indent * 4)
  167.                 loop (indent + 1) right
  168.                 printfn "%s(%s, %i)" spaces (x.ToString()) priority
  169.                 loop (indent + 1) left
  170.         loop 0 t
  171.  
  172.     let insert' v t =
  173.         let t' = insert v t
  174.         print t'
  175.         t'
  176.  
  177.     let remove' v t =
  178.         let t' = remove v t
  179.         print t'
  180.         t'
  181.  
  182.     *)
  183.  
  184.     [<Sealed>]
  185.     type Treap<'a>(t : 'a treap) =
  186.         member this.Internal = t
  187.         member this.Insert v = Treap(insert v t)
  188.         member this.Remove v = Treap(remove v t)
  189.         member this.Split v = let l, found, r = split v t in Treap(l), found, Treap(r)
  190.         member this.Contains v = contains v t
  191.         member this.Count = t.Count
  192.         member this.Min = t.Min
  193.         member this.Max = t.Max
  194.  
  195.     let empty f = Treap(nil f)
  196.  
  197.     let toSeq (t : Treap<'a>) =
  198.         let rec loop = function
  199.             | Nil(comparer, rnd) -> Seq.empty
  200.             | Node(comparer, rnd, priority, l, x, r, count) -> seq { yield! loop l; yield x; yield! loop r }
  201.         loop t.Internal
  202.  
  203.     let toSeqBack (t : Treap<'a>) =
  204.         let rec loop = function
  205.             | Nil(comparer, rnd) -> Seq.empty
  206.             | Node(comparer, rnd, priority, l, x, r, count) -> seq { yield! loop r; yield x; yield! loop l }
  207.         loop t.Internal
clone this paste RAW Paste Data