Tree Building
Rebuild a forum’s tree of posts from unordered records of an id and a parent id, rejecting records that do not form a tree.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: tree_building.nomi
//# Builds a tree of posts from records of ids and parent ids.
/// One post as it is stored: its id and its parent's id. The root's parent
/// is itself.
pub struct Record
id: Int
parent: Int
end
/// A post and its replies, ordered by id.
pub struct Node
id: Int
children: List<Node> = []
end
/// Why the records do not make a tree.
pub enum Error
RootHasParent
InvalidRecord
end
impl Display for Error
fn to_string(error: Error) -> String
case error
.RootHasParent -> "node parent_id should be smaller than its record_id"
.InvalidRecord -> "record id is invalid or out of order"
end
end
end
/// The tree of `records`, in any order, or `None` for no records. The ids
/// must be 0 to one less than the number of records, each once; the root,
/// 0, is its own parent, and every other record's parent has a lower id.
pub fn build_tree(records: List<Record>) -> Result<Maybe<Node>, Error>
sorted = Iter.sort_by(records, .id)
ids_in_order =
sorted
|> Iter.with_index()
|> Iter.all_match(fn (index, record) -> record.id == index)
if not ids_in_order then return Err(.InvalidRecord)
case sorted
[] ->
Ok(None)
[root, ..] when root.parent != 0 ->
Err(.RootHasParent)
[_root, ..rest] when Iter.any_match(rest, fn record -> record.parent >= record.id) ->
Err(.InvalidRecord)
[_root, ..rest] ->
Ok(Some(node(0, Iter.group_by(rest, .parent))))
end
end
/// The node `id` with its replies, from each parent's child records in id
/// order.
fn node(id: Int, children: Map<Int, List<Record>>) -> Node
replies = Map.get(children, id) |> Maybe.with_default([])
{id:, children: replies |> Iter.map(&node(&1.id, children)) |> Iter.to_list()}
end
// FILE: tree_building_test.nomi
import tree_building.{self, Node, Record}
/// A node with no replies.
fn leaf(id: Int) -> Node
{id:}
end
test "build tree"
cases: List<(String, List<Record>, Maybe<Node>)> = [
("empty list", [], None),
("single record", [{id: 0, parent: 0}], Some(leaf(0))),
(
"three records in order",
[{id: 0, parent: 0}, {id: 1, parent: 0}, {id: 2, parent: 0}],
Some({id: 0, children: [leaf(1), leaf(2)]}),
),
(
"three records in reverse order",
[{id: 2, parent: 0}, {id: 1, parent: 0}, {id: 0, parent: 0}],
Some({id: 0, children: [leaf(1), leaf(2)]}),
),
(
"more than two children",
[{id: 0, parent: 0}, {id: 1, parent: 0}, {id: 2, parent: 0}, {id: 3, parent: 0}],
Some({id: 0, children: [leaf(1), leaf(2), leaf(3)]}),
),
(
"binary tree",
[
{id: 5, parent: 1},
{id: 3, parent: 2},
{id: 2, parent: 0},
{id: 4, parent: 1},
{id: 1, parent: 0},
{id: 0, parent: 0},
{id: 6, parent: 2},
],
Some({
id: 0,
children: [
{id: 1, children: [leaf(4), leaf(5)]},
{id: 2, children: [leaf(3), leaf(6)]},
],
}),
),
(
"unbalanced tree",
[
{id: 5, parent: 2},
{id: 3, parent: 2},
{id: 2, parent: 0},
{id: 4, parent: 1},
{id: 1, parent: 0},
{id: 0, parent: 0},
{id: 6, parent: 2},
],
Some({
id: 0,
children: [
{id: 1, children: [leaf(4)]},
{id: 2, children: [leaf(3), leaf(5), leaf(6)]},
],
}),
),
]
subtests cases, (description, records, expected), description
assert tree_building.build_tree(records) == Ok(expected)
end
end
test "invalid records"
cases: List<(String, List<Record>, String)> = [
(
"one root node and has parent",
[{id: 0, parent: 1}],
"node parent_id should be smaller than its record_id",
),
(
"root node has parent",
[{id: 0, parent: 1}, {id: 1, parent: 0}],
"node parent_id should be smaller than its record_id",
),
(
"no root node",
[{id: 1, parent: 0}, {id: 2, parent: 0}],
"record id is invalid or out of order",
),
(
"duplicate node",
[{id: 0, parent: 0}, {id: 1, parent: 0}, {id: 1, parent: 0}],
"record id is invalid or out of order",
),
(
"duplicate root",
[{id: 0, parent: 0}, {id: 0, parent: 0}],
"record id is invalid or out of order",
),
(
"non-continuous",
[{id: 2, parent: 0}, {id: 4, parent: 2}, {id: 1, parent: 0}, {id: 0, parent: 0}],
"record id is invalid or out of order",
),
(
"cycle directly",
[
{id: 5, parent: 2},
{id: 3, parent: 2},
{id: 2, parent: 2},
{id: 4, parent: 1},
{id: 1, parent: 0},
{id: 0, parent: 0},
{id: 6, parent: 3},
],
"record id is invalid or out of order",
),
(
"cycle indirectly",
[
{id: 5, parent: 2},
{id: 3, parent: 2},
{id: 2, parent: 6},
{id: 4, parent: 1},
{id: 1, parent: 0},
{id: 0, parent: 0},
{id: 6, parent: 3},
],
"record id is invalid or out of order",
),
(
"higher id parent of lower id",
[{id: 0, parent: 0}, {id: 2, parent: 0}, {id: 1, parent: 2}],
"record id is invalid or out of order",
),
]
subtests cases, (description, records, message), description
assert Err(error) = tree_building.build_tree(records)
assert "${error}" == message
end
endok build tree (7 cases)
ok invalid records (9 cases)
test result: ok. 16 passed, 0 failed
How it’s written
Section titled “How it’s written”- The exercise is a refactoring of slow code that each track supplies; there is no slow version here, only the tree built directly.
RecordandNodeare structs.Node’schildrendefaults to[], so a leaf is{id:}, and the tests compare whole trees with==, which compares a struct field by field with noderive Equatable.build_treereturnsResult<Maybe<Node>, Error>: no records isOk(None), the canonical empty answer, not an error.Errorhas two variants for the canonical two messages, given by itsDisplay.- The records are sorted by id once. They are valid ids exactly when the sorted record at each index has that index as its id, which
Iter.with_indexandIter.all_matchcheck in one pass; that catches a missing root, a duplicate and a gap alike. - The canonical data splits the remaining rules oddly, and the solution follows it: a root whose parent is not 0 is the “parent_id should be smaller” error, but any other record whose parent is not lower than its id, a cycle included, is “record id is invalid or out of order”. These are three arms of one
caseon the sorted list, two withwhenguards. - Once every parent is lower than its child, the records cannot form a cycle, so the tree is built by
Iter.group_byon the parent, which keeps each parent’s children in id order, and a recursivenodefrom the root. - The valid and invalid cases are two
subteststables. The invalid table asserts each error’s message, which is what the canonical data gives.leafkeeps the expected trees short.