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 "%O -> %O" 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 then
  31             max <- r
  32
  33         // If a child is greater than the parent.
  34         if max <> i then
  35             let tmp = a.[i]
  36             a.[i] <- a.[max]
  37             a.[max] <- tmp
  38             heapUp max
  39
  40     // Check the integrity of the heap, use for debug only.
  41     let rec checkIntegrity (i : int) : bool =
  42         let l, r = left i, right i
  43         let leftIntegrity =
  44             if l < a.Count then
  45                 if kComparer.Compare (a.[l].key, a.[i].key) > 0 then false else checkIntegrity l
  46             else
  47                 true
  48         let rightIntegrity =
  49             if r < a.Count then
  50                 if kComparer.Compare (a.[r].key, a.[i].key) > 0 then false else checkIntegrity r
  51             else
  52                 true
  53         leftIntegrity && rightIntegrity
  54
  55     interface IEnumerable<'k * 'v> with
  56         member this.GetEnumerator () : IEnumerator<'k * 'v> =
  57             (seq { for e in a -> e.key, e.value }).GetEnumerator ()
  58
  59     interface System.Collections.IEnumerable with
  60         member this.GetEnumerator () : System.Collections.IEnumerator =
  61             (this :> IEnumerable<'k * 'v>).GetEnumerator () :> System.Collections.IEnumerator
  62
  63     member this.Next () : 'k * 'v =
  64         let node = a.[0]
  65         a.[0] <- a.[a.Count - 1]
  66         a.RemoveAt (a.Count - 1)
  67         heapUp 0
  68         node.key, node.value
  69
  70     member this.RemoveNext () =
  71         a.[0] <- a.[a.Count - 1]
  72         a.RemoveAt (a.Count - 1)
  73         heapUp 0
  74
  75     member this.Add (key : 'k) (value : 'v) =
  76         a.Add (Node (key, value))
  77
  78         let mutable i = a.Count - 1
  79         while i > 0 && kComparer.Compare (a.[parent i].key, a.[i].key) < 0 do
  80             let tmp = a.[parent i]
  81             a.[parent i] <- a.[i]
  82             a.[i] <- tmp
  83             i <- parent i
  84
  85     member this.IsEmpty = a.Count = 0
  86     member this.Count = a.Count
  87
  88     member this.Max : 'k * 'v =
  89         let max = a.[0]
  90         max.key, max.value
  91
  92     member this.Clear () = a.Clear ()