Parasitemia/ParasitemiaCore/Heap.fs

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