Tree datastructures: Difference between revisions
m (Withdrew the examples which use other sample outlines. I don't feel comfortable reproducing jokes about mocking and trolling.) |
(→{{header|Go}}: Changed 'golfing' to 'trolling'. Also round trip test now programmatic rather than just visual.) |
||
Line 45: | Line 45: | ||
import ( |
import ( |
||
"fmt" |
"fmt" |
||
"io" |
|||
"os" |
|||
"strings" |
"strings" |
||
) |
) |
||
Line 58: | Line 60: | ||
} |
} |
||
func printNest(n nNode, level int) { |
func printNest(n nNode, level int, w io.Writer) { |
||
if level == 0 { |
if level == 0 { |
||
fmt. |
fmt.Fprintln(w, "\n==Nest form==\n") |
||
} |
} |
||
fmt. |
fmt.Fprintf(w, "%s%s\n", strings.Repeat(" ", level), n.name) |
||
for _, c := range n.children { |
for _, c := range n.children { |
||
fmt. |
fmt.Fprintf(w, "%s", strings.Repeat(" ", level+1)) |
||
printNest(c, level+1) |
printNest(c, level+1, w) |
||
} |
} |
||
} |
} |
||
Line 84: | Line 86: | ||
} |
} |
||
func printIndent(iNodes []iNode) { |
func printIndent(iNodes []iNode, w io.Writer) { |
||
fmt. |
fmt.Fprintln(w, "\n==Indent form==\n") |
||
for _, n := range iNodes { |
for _, n := range iNodes { |
||
fmt. |
fmt.Fprintf(w, "%d %s\n", n.level, n.name) |
||
} |
} |
||
} |
} |
||
Line 101: | Line 103: | ||
n1 := nNode{"RosettaCode", nil} |
n1 := nNode{"RosettaCode", nil} |
||
n2 := nNode{"rocks", []nNode{{"code", nil}, {"comparison", nil}, {"wiki", nil}}} |
n2 := nNode{"rocks", []nNode{{"code", nil}, {"comparison", nil}, {"wiki", nil}}} |
||
n3 := nNode{"mocks", []nNode{{" |
n3 := nNode{"mocks", []nNode{{"trolling", nil}}} |
||
n1.children = append(n1.children, n2, n3) |
n1.children = append(n1.children, n2, n3) |
||
⚫ | |||
var sb strings.Builder |
|||
⚫ | |||
s1 := sb.String() |
|||
fmt.Print(s1) |
|||
var iNodes []iNode |
var iNodes []iNode |
||
toIndent(n1, 0, &iNodes) |
toIndent(n1, 0, &iNodes) |
||
printIndent(iNodes) |
printIndent(iNodes, os.Stdout) |
||
var n nNode |
var n nNode |
||
toNest(iNodes, 0, 0, &n) |
toNest(iNodes, 0, 0, &n) |
||
sb.Reset() |
|||
printNest(n, 0, &sb) |
|||
s2 := sb.String() |
|||
fmt.Print(s2) |
|||
fmt.Println("\nRound trip test satisfied? ", s1 == s2) |
|||
}</lang> |
}</lang> |
||
Line 122: | Line 135: | ||
wiki |
wiki |
||
mocks |
mocks |
||
trolling |
|||
==Indent form== |
==Indent form== |
||
Line 132: | Line 145: | ||
2 wiki |
2 wiki |
||
1 mocks |
1 mocks |
||
2 trolling |
|||
2 golfing |
|||
==Nest form== |
==Nest form== |
||
Line 142: | Line 155: | ||
wiki |
wiki |
||
mocks |
mocks |
||
trolling |
|||
⚫ | |||
Round trip test satisfied? true |
|||
⚫ | |||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 09:32, 18 October 2019
The following shows a tree of data with nesting denoted by visual levels of indentation:
RosettaCode rocks code comparison wiki mocks trolling
A common datastructure for trees is to define node structures having a name and a, (possibly empty), list of child nodes. The nesting of nodes captures the indentation of the tree. Lets call this the nest form.
# E.g. if child nodes are surrounded by brackets # and separated by commas then: RosettaCode(rocks(code, ...), ...) # But only an _example_
Another datastructure for trees is to construct from the root an ordered list of the nodes level of indentation and the name of that node. The indentation for the root node is zero; node 'rocks is indented by one level from the left, and so on. Lets call this the indent form.
0 RosettaCode 1 rocks 2 code ...
- Task
- Create/use a nest datastructure format and textual representation for arbitrary trees.
- Create/use an indent datastructure format and textual representation for arbitrary trees.
- Create methods/classes/proceedures/routines etc to:
- Change from a nest tree datastructure to an indent one.
- Change from an indent tree datastructure to a nest one
- Use the above to encode the example at the start into the nest format, and show it.
- transform the initial nest format to indent format and show it.
- transform the indent format to final nest format and show it.
- Compare initial and final nest formats which should be the same.
- Note
- It's all about showing aspects of the contrasting datastructures as they hold the tree.
- Comparing nested datastructures is secondary - saving formatted output as a string then a string compare would suffice for this task, if its easier.
- The word "trolling" is substituted for the original, less appropriate, "golfing" in the tree above as golfing can be friendly fun! (just not for RC examples). Please update language examples appropriately.
Show all output on this page.
Go
<lang go>package main
import (
"fmt" "io" "os" "strings"
)
type nNode struct {
name string children []nNode
}
type iNode struct {
level int name string
}
func printNest(n nNode, level int, w io.Writer) {
if level == 0 { fmt.Fprintln(w, "\n==Nest form==\n") } fmt.Fprintf(w, "%s%s\n", strings.Repeat(" ", level), n.name) for _, c := range n.children { fmt.Fprintf(w, "%s", strings.Repeat(" ", level+1)) printNest(c, level+1, w) }
}
func toNest(iNodes []iNode, start, level int, n *nNode) {
if level == 0 { n.name = iNodes[0].name } for i := start + 1; i < len(iNodes); i++ { if iNodes[i].level == level+1 { c := nNode{iNodes[i].name, nil} toNest(iNodes, i, level+1, &c) n.children = append(n.children, c) } else if iNodes[i].level <= level { return } }
}
func printIndent(iNodes []iNode, w io.Writer) {
fmt.Fprintln(w, "\n==Indent form==\n") for _, n := range iNodes { fmt.Fprintf(w, "%d %s\n", n.level, n.name) }
}
func toIndent(n nNode, level int, iNodes *[]iNode) {
*iNodes = append(*iNodes, iNode{level, n.name}) for _, c := range n.children { toIndent(c, level+1, iNodes) }
}
func main() {
n1 := nNode{"RosettaCode", nil} n2 := nNode{"rocks", []nNode{{"code", nil}, {"comparison", nil}, {"wiki", nil}}} n3 := nNode{"mocks", []nNodeTemplate:"trolling", nil} n1.children = append(n1.children, n2, n3)
var sb strings.Builder printNest(n1, 0, &sb) s1 := sb.String() fmt.Print(s1)
var iNodes []iNode toIndent(n1, 0, &iNodes) printIndent(iNodes, os.Stdout)
var n nNode toNest(iNodes, 0, 0, &n) sb.Reset() printNest(n, 0, &sb) s2 := sb.String() fmt.Print(s2)
fmt.Println("\nRound trip test satisfied? ", s1 == s2)
}</lang>
- Output:
==Nest form== RosettaCode rocks code comparison wiki mocks trolling ==Indent form== 0 RosettaCode 1 rocks 2 code 2 comparison 2 wiki 1 mocks 2 trolling ==Nest form== RosettaCode rocks code comparison wiki mocks trolling Round trip test satisfied? true
Python
Just arranges the standard lists and tuples for the datastructures allowing pprint to show the different arrangement of storage.
<lang python>from pprint import pprint as pp
def to_indent(node, depth=0, flat=None):
if flat is None: flat = [] if node: flat.append((depth, node[0])) for child in node[1]: to_indent(child, depth + 1, flat) return flat
def to_nest(lst, depth=0, level=None):
if level is None: level = [] while lst: d, name = lst[0] if d == depth: children = [] level.append((name, children)) lst.pop(0) elif d > depth: # down to_nest(lst, d, children) elif d < depth: # up return return level[0] if level else None
if __name__ == '__main__':
print('Start Nest format:') nest = ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]), ('mocks', [('trolling', [])])]) pp(nest, width=25)
print('\n... To Indent format:') as_ind = to_indent(nest) pp(as_ind, width=25)
print('\n... To Nest format:') as_nest = to_nest(as_ind) pp(as_nest, width=25)
if nest != as_nest: print("Whoops round-trip issues")</lang>
- Output:
Start Nest format: ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]), ('mocks', [('trolling', [])])]) ... To Indent format: [(0, 'RosettaCode'), (1, 'rocks'), (2, 'code'), (2, 'comparison'), (2, 'wiki'), (1, 'mocks'), (2, 'trolling')] ... To Nest format: ('RosettaCode', [('rocks', [('code', []), ('comparison', []), ('wiki', [])]), ('mocks', [('trolling', [])])])