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 [<Struct>]
  10 type private Node<'k, 'v> =
  11     val mutable key: 'k
  12     val value: 'v
  13     new (k, v) = { key = k; value = v }
  14     override this.ToString () = sprintf "%A -> %A" this.key this.value
  15
  16 type Heap<'k, 'v> (kComparer : IComparer<'k>) =
  17     let a = List<Node<'k, 'v>>()
  18
  19     let rec heapUp (i: int) =
  20         let l, r = left i, right i
  21
  22         // Is the left child greater than the parent?
  23         let mutable max = if l < a.Count && kComparer.Compare(a.[l].key, a.[i].key) > 0 then l else i
  24
  25         // Is the right child greater than the parent and the left child?
  26         if r < a.Count && kComparer.Compare(a.[r].key, a.[max].key) > 0
  27         then
  28             max <- r
  29
  30         // If a child is greater than the parent.
  31         if max <> i
  32         then
  33             let tmp = a.[i]
  34             a.[i] <- a.[max]
  35             a.[max] <- tmp
  36             heapUp max
  37
  38     // Check the integrity of the heap, use for debug only.
  39     let rec checkIntegrity (i: int) : bool =
  40         let l, r = left i, right i
  41         let leftIntegrity =
  42             if l < a.Count
  43             then
  44                 if kComparer.Compare(a.[l].key, a.[i].key) > 0
  45                 then false
  46                 else checkIntegrity l
  47             else
  48                 true
  49         let rightIntegrity =
  50             if r < a.Count
  51             then
  52                 if kComparer.Compare(a.[r].key, a.[i].key) > 0
  53                 then false
  54                 else checkIntegrity r
  55             else
  56                 true
  57         leftIntegrity && rightIntegrity
  58
  59     interface IEnumerable<'k * 'v> with
  60         member this.GetEnumerator () : IEnumerator<'k * 'v> =
  61             (seq { for e in a -> e.key, e.value }).GetEnumerator()
  62
  63     interface System.Collections.IEnumerable with
  64         member this.GetEnumerator () : System.Collections.IEnumerator =
  65             (this :> IEnumerable<'k * 'v>).GetEnumerator() :> System.Collections.IEnumerator
  66
  67     member this.Next () : 'k * 'v =
  68         let node = a.[0]
  69         a.[0] <- a.[a.Count - 1]
  70         a.RemoveAt(a.Count - 1)
  71         heapUp 0
  72         node.key, node.value
  73
  74     member this.RemoveNext () =
  75         a.[0] <- a.[a.Count - 1]
  76         a.RemoveAt(a.Count - 1)
  77         heapUp 0
  78
  79     member this.Add (key: 'k) (value: 'v) =
  80         a.Add(Node(key, value))
  81
  82         let mutable i = a.Count - 1
  83         while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do
  84             let tmp = a.[parent i]
  85             a.[parent i] <- a.[i]
  86             a.[i] <- tmp
  87             i <- parent i
  88
  89     member this.IsEmpty = a.Count = 0
  90     member this.Count = a.Count
  91
  92     member this.Max : 'k * 'v =
  93         let max = a.[0]
  94         max.key, max.value
  95
  96     member this.Clear () = a.Clear()
  97
  98