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