// A vec-based container for a tree structure.
//
// `TreeIndex` values start at 1; index 0 is a dummy node so that `Array`'s
// default `get` behavior works without subtracting one everywhere.
///|
/// A node in the tree.
priv struct Node[T] {
mut child : Int32?
mut next : Int32?
item : T
}
///|
/// A tree abstraction, intended for fast building as a preorder traversal.
struct Tree[T] {
nodes : Array[Node[T]]
spine : Array[Int32] // indices of nodes on path to current node
mut cur : Int32?
}
///|
fn[T : Default] tree_with_capacity(_cap : Int32) -> Tree[T] {
let nodes : Array[Node[T]] = Array::make(1, {
child: None,
next: None,
item: T::default(),
})
{ nodes, spine: [], cur: None, }
}
///|
/// Returns the index of the element currently in focus.
fn[T] Tree::cur(self : Tree[T]) -> Int32? {
self.cur
}
///|
/// Append one item to the current position in the tree.
fn[T] Tree::append(self : Tree[T], item : T) -> Int32 {
let ix = self.create_node(item)
if self.cur is Some(cur) {
self.nodes[cur].next = Some(ix)
} else if self.spine.last() is Some(parent) {
self.nodes[parent].child = Some(ix)
}
self.cur = Some(ix)
ix
}
///|
/// Create an isolated node.
fn[T] Tree::create_node(self : Tree[T], item : T) -> Int32 {
let this = self.nodes.length()
self.nodes.push({ child: None, next: None, item, })
this
}
///|
/// Push down one level, so that new items become children of the current node.
/// The new focus index is returned.
fn[T] Tree::push(self : Tree[T]) -> Int32 {
let cur_ix = self.cur.unwrap()
self.spine.push(cur_ix)
self.cur = self.nodes[cur_ix].child
cur_ix
}
///|
/// Pop back up a level.
fn[T] Tree::pop(self : Tree[T]) -> Int32? {
let ix = self.spine.pop()
self.cur = ix
ix
}
///|
/// Remove the last node, as `pop` but removing it.
fn[T] Tree::remove_node(self : Tree[T]) -> Int32? {
let ix = self.spine.pop()
self.cur = ix
guard ix is Some(i) else { return ix }
if self.nodes.length() > 0 {
ignore(self.nodes.pop())
self.nodes[i].child = None
}
ix
}
///|
/// Look at the parent node.
fn[T] Tree::peek_up(self : Tree[T]) -> Int32? {
self.spine.last()
}
///|
/// Look at grandparent node.
fn[T] Tree::peek_grandparent(self : Tree[T]) -> Int32? {
guard self.spine.length() >= 2 else { None }
Some(self.spine[self.spine.length() - 2])
}
///|
/// Returns true when there are no nodes other than the root node in the tree.
fn[T] Tree::is_empty(self : Tree[T]) -> Bool {
self.nodes.length() <= 1
}
///|
/// Returns the length of the spine.
fn[T] Tree::spine_len(self : Tree[T]) -> Int32 {
self.spine.length()
}
///|
/// Resets the focus to the first node added to the tree, if it exists.
fn[T] Tree::reset(self : Tree[T]) -> Unit {
self.cur = if self.is_empty() { None } else { Some(1) }
self.spine.clear()
}
///|
/// Iterates the spine from a root node up to, but not including, the current node.
fn[T] Tree::walk_spine(self : Tree[T]) -> Array[Int32] {
self.spine.copy()
}
///|
/// Moves focus to the next sibling of the given node.
fn[T] Tree::next_sibling(self : Tree[T], cur_ix : Int32) -> Int32? {
self.cur = self.nodes[cur_ix].next
self.cur
}
///|
fn[T] Tree::truncate_to_parent(self : Tree[T], child_ix : Int32) -> Unit {
let next = self.nodes[child_ix].next
self.nodes[child_ix].next = None
if self.cur is Some(cur) {
self.nodes[cur].next = next
} else if self.spine.last() is Some(parent) {
self.nodes[parent].child = next
}
if next is Some(_) {
self.cur = next
}
}
///|
fn Tree::append_text(self : Tree[Item], start : Int32, end : Int32) -> Unit {
if end > start {
if self.cur() is Some(ix) {
let merges = self.nodes[ix].item.body is Text &&
self.nodes[ix].item.end == start
if merges {
self.nodes[ix].item.end = end
return
}
}
ignore(self.append(Item::{ start, end, body: Text, }))
}
}
///|
/// Returns true if the current node is inside a table.
fn Tree::is_in_table(self : Tree[Item]) -> Bool {
let spine = self.spine.copy()
for idx in 0..