-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathBaseline.fs
45 lines (38 loc) · 1.69 KB
/
Baseline.fs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
module TreeBuildingBaseline
open TreeBuildingTypes
let buildTree records =
let records' = List.sortBy (fun x -> x.RecordId) records
if List.isEmpty records' then failwith "Empty input"
else
let root = records'.[0]
if (root.ParentId = 0 |> not) then
failwith "Root node is invalid"
else
if (root.RecordId = 0 |> not) then failwith "Root node is invalid"
else
let mutable prev = -1
let mutable leafs = []
for r in records' do
if (r.RecordId <> 0 && (r.ParentId > r.RecordId || r.ParentId = r.RecordId)) then
failwith "Nodes with invalid parents"
else
if r.RecordId <> prev + 1 then
failwith "Non-continuous list"
else
prev <- r.RecordId
if (r.RecordId = 0) then
leafs <- (-1, r.RecordId) :: leafs
else
leafs <- (r.ParentId, r.RecordId) :: leafs
leafs <- List.rev leafs
let root = leafs.[0]
let grouped = leafs |> List.groupBy fst |> List.map (fun (x, y) -> (x, List.map snd y))
let parens = List.map fst grouped
let map = grouped |> Map.ofSeq
let rec helper key =
if Map.containsKey key map then
Branch (key, List.map (fun i -> helper i) (Map.find key map))
else
Leaf key
let root = helper 0
root