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