Sha256: beb0439cabf44c4b5c54fe224aa3e59952a4b3c408f504a22d61dd073bf15006
Contents?: true
Size: 1.61 KB
Versions: 38
Compression:
Stored size: 1.61 KB
Contents
module TreeBuilding
type Record = { RecordId: int; ParentId: int }
type Tree =
| Branch of int * Tree list
| Leaf of int
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 = -1 |> 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.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
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
Version data entries
38 entries across 38 versions & 1 rubygems