let inline private left (i: int) : int = 2 * (i + 1) - 1
let inline private right (i: int) : int = 2 * (i + 1)
-// TODO: measure performance with a struct.
-type private Node<'k, 'v> = { mutable key: 'k; value : 'v } with
+[<Struct>]
+type private Node<'k, 'v> =
+ val mutable key: 'k
+ val value: 'v
+ new (k, v) = { key = k; value = v }
override this.ToString () = sprintf "%A -> %A" this.key this.value
type Heap<'k, 'v> (kComparer : IComparer<'k>) =
a.[max] <- tmp
heapUp max
+ // Check the integrity of the heap, use for debug only.
let rec checkIntegrity (i: int) : bool =
let l, r = left i, right i
-
let leftIntegrity =
if l < a.Count
then
(this :> IEnumerable<'k * 'v>).GetEnumerator() :> System.Collections.IEnumerator
member this.Next () : 'k * 'v =
- let { key = key; value = value } = a.[0]
+ let node = a.[0]
a.[0] <- a.[a.Count - 1]
a.RemoveAt(a.Count - 1)
heapUp 0
- key, value
+ node.key, node.value
member this.RemoveNext () =
a.[0] <- a.[a.Count - 1]
heapUp 0
member this.Add (key: 'k) (value: 'v) =
- a.Add({ key = key; value = value })
+ a.Add(Node(key, value))
let mutable i = a.Count - 1
while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do