Cleaning, micro-optimizations.

[master-thesis.git] / Parasitemia / Parasitemia / Heap.fs

diff --git a/Parasitemia/Parasitemia/Heap.fs b/Parasitemia/Parasitemia/Heap.fs
index 82298e2..3d0879e 100644 (file)
--- a/Parasitemia/Parasitemia/Heap.fs
+++ b/Parasitemia/Parasitemia/Heap.fs
@@ -6,8 +6,11 @@ let inline private parent (i: int) : int = (i - 1) / 2
 let inline private left (i: int) : int = 2 * (i + 1) - 1
 let inline private right (i: int) : int = 2 * (i + 1)
 
 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>) =
     override this.ToString () = sprintf "%A -> %A" this.key this.value
 
 type Heap<'k, 'v> (kComparer : IComparer<'k>) =


@@ -32,9 +35,9 @@ type Heap<'k, 'v> (kComparer : IComparer<'k>) =
             a.[max] <- tmp
             heapUp max
 
             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 rec checkIntegrity (i: int) : bool =
         let l, r = left i, right i

-

         let leftIntegrity =
             if l < a.Count
             then
         let leftIntegrity =
             if l < a.Count
             then


@@ -62,11 +65,11 @@ type Heap<'k, 'v> (kComparer : IComparer<'k>) =
             (this :> IEnumerable<'k * 'v>).GetEnumerator() :> System.Collections.IEnumerator
 
     member this.Next () : 'k * 'v =
             (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
         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]
 
     member this.RemoveNext () =
         a.[0] <- a.[a.Count - 1]


@@ -74,7 +77,7 @@ type Heap<'k, 'v> (kComparer : IComparer<'k>) =
         heapUp 0
 
     member this.Add (key: 'k) (value: 'v) =
         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
 
         let mutable i = a.Count - 1
         while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do