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