// priority heap implemention in F#
#load "streamdefs.fsx"
open System;
open Streamdefs

let private left i = 2*i+1
let private right i = 2*i+2
let private parent i = (i-1)/2

type Heap<'T> =
  {
     H : ResizeArray<'T>;
     lt : 'T -> 'T -> bool;  // less than operation such as (<)
  }
  static member makeheap cmp = { H = ResizeArray<'T>(); lt = cmp; }
  member private this.swapup k = 
    let (H,lt) = (this.H,this.lt)
    let mutable i = k;
    let mutable pi = parent(k)
    while i>0 && (lt H[pi] H[i]) do   // assume larger above
      let tmp = H[i]
      H[i] <- H[pi]
      H[pi] <- tmp
      i <- pi
      pi <- parent(i)
    i  // returns final position
  member private this.swapdown k =
    let (H,lt) = (this.H,this.lt)
    let mutable i = k;
    let mutable si = 0; // swap index
    while si >= 0 do
      si <- -1;
      let (lf,rt) = (left(i), right(i))
      if lf<H.Count && (lt H[i] H[lf]) then si <- lf;
      if rt<H.Count && (lt H[i] H[rt]) && (lt H[lf] H[rt]) then si <- rt
      if si>=0 then
        let tmp = H[i] in (H[i] <- H[si]; H[si] <- tmp;)
        i <- si
    // while
    i
  //// public methods
  member this.size() = this.H.Count
  member this.push x =
    this.H.Add(x)
    this.swapup (this.H.Count - 1) |> ignore
  //push      
  member this.pop() : Option<'T> =  // returns Option
    let H = this.H
    if H.Count = 0 then None
    else 
      let answer = H[0]
      H[0] <- H[H.Count-1]
      H.RemoveAt (H.Count-1)
      this.swapdown 0 |> ignore
      Some(answer)
  //pop
  member this.stream() =
    coinduction 0 (fun x -> x+1)
      |> limit (this.size())
      |> map (fun i -> this.H[i])
  member this.priority_stream() =
    fun () -> this.pop()

let h = Heap<int>.makeheap (<);
for x in [3;6;1;8;9;4] do h.push(x);

h.stream() |> foreach (printfn "%d")
h.priority_stream() |> foreach (printfn "popped %d")