X-Git-Url: http://git.euphorik.ch/?p=master-thesis.git;a=blobdiff_plain;f=Parasitemia%2FParasitemia%2FHeap.fs;h=82298e2fae46034915a55c2ba5e50f8b5586b611;hp=39c6a4be5f882fe9bfbc68b93d5b4ff899c67d79;hb=d0c85068bb98a7999ed994f02669befa70edd5f9;hpb=dcf3645b3426991237567e90bab9806a9c111cd1

diff --git a/Parasitemia/Parasitemia/Heap.fs b/Parasitemia/Parasitemia/Heap.fs
index 39c6a4b..82298e2 100644
--- a/Parasitemia/Parasitemia/Heap.fs
+++ b/Parasitemia/Parasitemia/Heap.fs
@@ -6,19 +6,25 @@ 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)
 
-type private Node<'k, 'v> = { key: 'k; value : 'v } with
+// TODO: measure performance with a struct.
+type private Node<'k, 'v> = { mutable key: 'k; value : 'v } with
     override this.ToString () = sprintf "%A -> %A" this.key this.value
 
-type Heap<'k, 'v when 'k : comparison> () =
+type Heap<'k, 'v> (kComparer : IComparer<'k>) =
     let a = List<Node<'k, 'v>>()
 
     let rec heapUp (i: int) =
         let l, r = left i, right i
-        let mutable max = if l < a.Count && a.[l].key > a.[i].key then l else i
-        if r < a.Count && a.[r].key > a.[max].key
+
+        // Is the left child greater than the parent?
+        let mutable max = if l < a.Count && kComparer.Compare(a.[l].key, a.[i].key) > 0 then l else i
+
+        // Is the right child greater than the parent and the left child?
+        if r < a.Count && kComparer.Compare(a.[r].key, a.[max].key) > 0
         then
             max <- r
 
+        // If a child is greater than the parent.
         if max <> i
         then
             let tmp = a.[i]
@@ -26,17 +32,64 @@ type Heap<'k, 'v when 'k : comparison> () =
             a.[max] <- tmp
             heapUp max
 
+    let rec checkIntegrity (i: int) : bool =
+        let l, r = left i, right i
+
+        let leftIntegrity =
+            if l < a.Count
+            then
+                if kComparer.Compare(a.[l].key, a.[i].key) > 0
+                then false
+                else checkIntegrity l
+            else
+                true
+        let rightIntegrity =
+            if r < a.Count
+            then
+                if kComparer.Compare(a.[r].key, a.[i].key) > 0
+                then false
+                else checkIntegrity r
+            else
+                true
+        leftIntegrity && rightIntegrity
+
+    interface IEnumerable<'k * 'v> with
+        member this.GetEnumerator () : IEnumerator<'k * 'v> =
+            (seq { for e in a -> e.key, e.value }).GetEnumerator()
+
+    interface System.Collections.IEnumerable with
+        member this.GetEnumerator () : System.Collections.IEnumerator =
+            (this :> IEnumerable<'k * 'v>).GetEnumerator() :> System.Collections.IEnumerator
+
     member this.Next () : 'k * 'v =
-        let { key = key; value = value} = a.[0]
-        a.RemoveAt(0)
+        let { key = key; value = value } = a.[0]
+        a.[0] <- a.[a.Count - 1]
+        a.RemoveAt(a.Count - 1)
+        heapUp 0
         key, value
 
-    member this.Add (key: 'k) (value: 'v) =
-        a.Insert(0, { key = key; value = value})
+    member this.RemoveNext () =
+        a.[0] <- a.[a.Count - 1]
+        a.RemoveAt(a.Count - 1)
         heapUp 0
 
+    member this.Add (key: 'k) (value: 'v) =
+        a.Add({ key = key; value = value })
+
+        let mutable i = a.Count - 1
+        while i > 0 && kComparer.Compare(a.[parent i].key, a.[i].key) < 0 do
+            let tmp = a.[parent i]
+            a.[parent i] <- a.[i]
+            a.[i] <- tmp
+            i <- parent i
+
     member this.IsEmpty = a.Count = 0
-    member this.Max : 'k = a.[0].key
+    member this.Count = a.Count
+
+    member this.Max : 'k * 'v =
+        let max = a.[0]
+        max.key, max.value
+
     member this.Clear () = a.Clear()