32887a230b6cf5cdbde185dde5f441e13661e3f7
1
module ParasitemiaCore.Heap
3 open System.Collections.Generic
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)
10 type private Node<'k, 'v
> =
13 new (k
, v
) = { key = k
; value = v
}
14 override this.ToString () = sprintf
"%A -> %A" this.key this.value
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.
20 type Heap<'k, 'v
> (kComparer
: IComparer<'k>) =
21 let a = List<Node<'k
, 'v>>()
23 let rec heapUp (i: int) =
24 let l, r = left i, right i
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
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
34 // If a child is greater than the parent.
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
48 if kComparer.Compare(a.[l].key, a.[i].key) > 0
56 if kComparer.Compare(a.[r].key, a.[i].key) > 0
61 leftIntegrity && rightIntegrity
63 interface IEnumerable<'k
* 'v> with
64 member this.GetEnumerator () : IEnumerator<'k
* 'v> =
65 (seq { for e in a -> e.key, e.value }).GetEnumerator()
67 interface System.Collections.IEnumerable with
68 member this.GetEnumerator () : System.Collections.IEnumerator =
69 (this :> IEnumerable<'k
* 'v>).GetEnumerator() :> System.Collections.IEnumerator
71 member this.Next () : 'k
* 'v =
73 a.[0] <- a.[a.Count - 1]
74 a.RemoveAt(a.Count - 1)
78 member this.RemoveNext () =
79 a.[0] <- a.[a.Count - 1]
80 a.RemoveAt(a.Count - 1)
83 member this.Add (key: 'k
) (value: 'v) =
84 a.Add(Node(key, value))
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]
93 member this.IsEmpty = a.Count = 0
94 member this.Count = a.Count
96 member this.Max : 'k
* 'v =
100 member this.Clear () = a.Clear()