134 lines
3.9 KiB
Nim
134 lines
3.9 KiB
Nim
import strformat, strutils
|
|
|
|
|
|
####################################################################################################
|
|
# Nested representation of trees.
|
|
# The tree is simply the first node.
|
|
|
|
type
|
|
|
|
NNode*[T] = ref object
|
|
value*: T
|
|
children*: seq[NNode[T]]
|
|
|
|
|
|
proc newNNode*[T](value: T; children: varargs[NNode[T]]): NNode[T] =
|
|
## Create a node.
|
|
NNode[T](value: value, children: @children)
|
|
|
|
|
|
proc add*[T](node: NNode[T]; children: varargs[NNode[T]]) =
|
|
## Add a list of chlidren to a node.
|
|
node.children.add children
|
|
|
|
|
|
proc `$`*[T](node: NNode[T]; depth = 0): string =
|
|
## Return a string representation of a tree/node.
|
|
result = repeat(' ', 2 * depth) & $node.value & '\n'
|
|
for child in node.children:
|
|
result.add `$`(child, depth + 1)
|
|
|
|
|
|
####################################################################################################
|
|
# Indented representation of trees.
|
|
# The tree is described as the list of the nodes.
|
|
|
|
type
|
|
|
|
INode*[T] = object
|
|
value*: T
|
|
level*: Natural
|
|
|
|
ITree*[T] = seq[INode[T]]
|
|
|
|
|
|
proc initINode*[T](value: T; level: Natural): INode[T] =
|
|
## Return a new node.
|
|
INode[T](value: value, level: level)
|
|
|
|
|
|
proc initItree*[T](value: T): ITree[T] =
|
|
## Return a new tree initialized with the first node (root node).
|
|
result = @[initINode(value, 0)]
|
|
|
|
|
|
proc add*[T](tree: var ITree[T]; nodes: varargs[INode[T]]) =
|
|
## Add a list of nodes to the tree.
|
|
for node in nodes:
|
|
if node.level - tree[^1].level > 1:
|
|
raise newException(ValueError, &"wrong level {node.level} in node {node.value}.")
|
|
tree.add node
|
|
|
|
|
|
proc `$`*[T](tree: ITree[T]): string =
|
|
## Return a string representation of a tree.
|
|
for node in tree:
|
|
result.add $node.level & ' ' & $node.value & '\n'
|
|
|
|
|
|
####################################################################################################
|
|
# Conversion between nested form and indented form.
|
|
|
|
proc toIndented*[T](node: NNode[T]): Itree[T] =
|
|
## Convert a tree in nested form to a tree in indented form.
|
|
|
|
proc addNode[T](tree: var Itree[T]; node: NNode[T]; level: Natural) =
|
|
## Add a node to the tree at the given level.
|
|
tree.add initINode(node.value, level)
|
|
for child in node.children:
|
|
tree.addNode(child, level + 1)
|
|
|
|
result.addNode(node, 0)
|
|
|
|
|
|
proc toNested*[T](tree: Itree[T]): NNode[T] =
|
|
## Convert a tree in indented form to a tree in nested form.
|
|
|
|
var stack: seq[NNode[T]] # Note that stack.len is equal to the current level.
|
|
var nnode = newNNode(tree[0].value) # Root.
|
|
for i in 1..tree.high:
|
|
let inode = tree[i]
|
|
if inode.level > stack.len:
|
|
# Child.
|
|
stack.add nnode
|
|
elif inode.level == stack.len:
|
|
# Sibling.
|
|
stack[^1].children.add nnode
|
|
else:
|
|
# Branch terminated.
|
|
while inode.level < stack.len:
|
|
stack[^1].children.add nnode
|
|
nnode = stack.pop()
|
|
stack[^1].children.add nnode
|
|
|
|
nnode = newNNode(inode.value)
|
|
|
|
# Empty the stack.
|
|
while stack.len > 0:
|
|
stack[^1].children.add nnode
|
|
nnode = stack.pop()
|
|
|
|
result = nnode
|
|
|
|
|
|
#———————————————————————————————————————————————————————————————————————————————————————————————————
|
|
|
|
when isMainModule:
|
|
|
|
echo "Displaying tree built using nested structure:"
|
|
let nestedTree = newNNode("RosettaCode")
|
|
let rocks = newNNode("rocks")
|
|
rocks.add newNNode("code"), newNNode("comparison"), newNNode("wiki")
|
|
let mocks = newNNode("mocks", newNNode("trolling"))
|
|
nestedTree.add rocks, mocks
|
|
echo nestedTree
|
|
|
|
echo "Displaying tree converted to indented structure:"
|
|
let indentedTree = nestedTree.toIndented
|
|
echo indentedTree
|
|
|
|
echo "Displaying tree converted back to nested structure:"
|
|
echo indentedTree.toNested
|
|
|
|
echo "Are they equal? ", if $nestedTree == $indentedTree.toNested: "yes" else: "no"
|