Parasitemia/Parasitemia/Heap.fs

   1 module Heap
   2
   3 open System.Collections.Generic
   4
   5 let inline private parent (i: int) : int = (i - 1) / 2
   6 let inline private left (i: int) : int = 2 * (i + 1) - 1
   7 let inline private right (i: int) : int = 2 * (i + 1)
   8
   9 type private Node<'k, 'v> = { key: 'k; value : 'v } with
  10     override this.ToString () = sprintf "%A -> %A" this.key this.value
  11
  12 type Heap<'k, 'v when 'k : comparison> () =
  13     let a = List<Node<'k, 'v>>()
  14
  15     let rec heapUp (i: int) =
  16         let l, r = left i, right i
  17         let mutable max = if l < a.Count && a.[l].key > a.[i].key then l else i
  18         if r < a.Count && a.[r].key > a.[max].key
  19         then
  20             max <- r
  21         if max <> i
  22         then
  23             let tmp = a.[i]
  24             a.[i] <- a.[max]
  25             a.[max] <- tmp
  26             heapUp max
  27
  28     member this.Next () : 'k * 'v =
  29         let { key = key; value = value} = a.[0]
  30         a.RemoveAt(0)
  31         key, value
  32
  33     member this.Add (key: 'k) (value: 'v) =
  34         a.Insert(0, { key = key; value = value})
  35         heapUp 0
  36
  37     member this.IsEmpty = a.Count = 0
  38     member this.Max : 'k = a.[0].key
  39     member this.Clear () = a.Clear()
  40
  41