Rosetta Code

Tree datastructures: Difference between revisions

Page Discussion

Tree datastructures (view source)

Revision as of 18:12, 12 May 2024

14,108 bytes added ,  11 days ago
PascalABC.NET solution added before Perl
(→‎{{header|Haskell}}: Added a less instructive variant, using the pre-cooked Data.Tree)
(PascalABC.NET solution added before Perl)
(12 intermediate revisions by 7 users not shown)
Line 38:
 
Show all output on this page.
 
=={{header|11l}}==
{{trans|Nim}}
 
<syntaxhighlight lang="11l">T NNode
String value
[NNode] children
 
F (value)
.value = value
 
F add(node)
.children.append(node)
 
F.const to_str(depth) -> String
V result = (‘ ’ * depth)‘’(.value)"\n"
L(child) .children
result ‘’= child.to_str(depth + 1)
R result
 
F String()
R .to_str(0)
 
T INode
String value
Int level
F (value, level)
.value = value
.level = level
 
F to_indented(node)
[INode] result
F add_node(NNode node, Int level) -> Void
@result.append(INode(node.value, level))
L(child) node.children
@add_node(child, level + 1)
add_node(node, 0)
R result
 
F to_nested(tree)
[NNode] stack
V nnode = NNode(tree[0].value)
L(i) 1 .< tree.len
V inode = tree[i]
I inode.level > stack.len
stack.append(nnode)
E I inode.level == stack.len
stack.last.children.append(nnode)
E
L inode.level < stack.len
stack.last.children.append(nnode)
nnode = stack.pop()
stack.last.children.append(nnode)
nnode = NNode(inode.value)
 
L stack.len > 0
stack.last.children.append(nnode)
nnode = stack.pop()
 
R nnode
 
print(‘Displaying tree built using nested structure:’)
V nestedTree = NNode(‘RosettaCode’)
V rocks = NNode(‘rocks’)
rocks.add(NNode(‘code’))
rocks.add(NNode(‘comparison’))
rocks.add(NNode(‘wiki’))
V mocks = NNode(‘mocks’)
mocks.add(NNode(‘trolling’))
nestedTree.add(rocks)
nestedTree.add(mocks)
print(nestedTree)
 
print(‘Displaying tree converted to indented structure:’)
V indentedTree = to_indented(nestedTree)
L(node) indentedTree
print((node.level)‘ ’(node.value))
print()
 
print(‘Displaying tree converted back to nested structure:’)
print(to_nested(indentedTree))
 
print(‘Are they equal? ’(I String(nestedTree) == String(to_nested(indentedTree)) {‘yes’} E ‘no’))</syntaxhighlight>
 
{{out}}
<pre>
Displaying tree built using nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
Displaying tree converted to indented structure:
0 RosettaCode
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
Displaying tree converted back to nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
Are they equal? yes
</pre>
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
#include <list>
Line 142 ⟶ 257:
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 177 ⟶ 292:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 259 ⟶ 374:
 
fmt.Println("\nRound trip test satisfied? ", s1 == s2)
}</langsyntaxhighlight>
 
{{out}}
Line 299 ⟶ 414:
The task is all about the isomorphism between different representations of a nested list structure. Therefore the solution is given in terms of the isomorphisms.
 
<langsyntaxhighlight lang="haskell">{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE UndecidableSuperClasses #-}
Line 369 ⟶ 484:
-- A bijection from a string to nest form via indent form
instance Iso String (Nest String) where
from = from @(Indent String) . from</langsyntaxhighlight>
 
Testing:
<langsyntaxhighlight lang="haskell">test = unlines
[ "RosettaCode"
, " rocks"
Line 389 ⟶ 504:
 
ttest :: Nest String
ttest = from test</langsyntaxhighlight>
 
<pre>λ> mapM_ print itest
Line 453 ⟶ 568:
 
 
And less satisfyingly and instructively – just relying a little passively on the existing Data.Tree,
we might also write something like:
 
<langsyntaxhighlight lang="haskell">import Data.Bifunctor (bimap, first)
import Data.Char (isSpace)
import Data.List (find)
Line 463 ⟶ 578:
-------- MAPPINGS BETWEEN INDENTED LINES AND TREES -------
 
forestFromNestLevels :: [(Int, aString)] -> Forest aString
forestFromNestLevels = go
where
Line 478 ⟶ 593:
 
outlineFromForest ::
(String -> aString -> String) ->
String ->
Forest aString ->
String
outlineFromForest showRoot tabString forest =
Line 489 ⟶ 604:
 
-------------------------- TESTS -------------------------
 
main :: IO ()
main = do
putStrLn "TreesTree fromrepresentation indentedparsed textdirectly:\n"
putStrLn $ drawTree $ Node "" nativeForest
let trees =
 
forestFromNestLevels $
let levelPairs = indentLevelsFromLines test
putStrLn "\n[(Level, Text)] list from lines:\n"
mapM_ print levelPairs
 
putStrLn "\n\nTrees from indented text:\n"
let trees = forestFromNestLevels levelPairs
putStrLn $ drawTree $ Node "" trees
 
Line 514 ⟶ 633:
" be",
" irregular"
]</lang>
 
nativeForest :: Forest String
nativeForest =
[ Node
"RosettaCode"
[ Node
"rocks"
[ Node "code" [],
Node "comparison" [],
Node "wiki" []
],
Node
"mocks"
[Node "trolling" []]
],
Node
"Some lists"
[ Node "may" [],
Node "be" [],
Node "irregular" []
]
]</syntaxhighlight>
{{Out}}
<pre>TreesTree fromrepresentation indentedparsed textdirectly:
 
|
+- RosettaCode
| |
| +- rocks
| | |
| | +- code
| | |
| | +- comparison
| | |
| | `- wiki
| |
| `- mocks
| |
| `- trolling
|
`- Some lists
|
+- may
|
+- be
|
`- irregular
 
 
[(Level, Text)] list from lines:
 
(0,"RosettaCode")
(1,"rocks")
(2,"code")
(2,"comparison")
(2,"wiki")
(1,"mocks")
(2,"trolling")
(0,"Some lists")
(3,"may")
(2,"be")
(1,"irregular")
 
 
Trees from indented text:
 
|
Line 554 ⟶ 736:
be
irregular</pre>
 
=={{header|Java}}==
<syntaxhighlight lang="java">
public class TreeDatastructures {
 
public static void main(String[] args) {
String initialNested = """
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
""";
System.out.println(initialNested);
String indented = nestedToIndented(initialNested);
System.out.println(indented);
String finalNested = indentedToNested(indented);
System.out.println(finalNested);
 
final boolean equal = ( initialNested.compareTo(finalNested) == 0 );
System.out.println("initialNested = finalNested ? " + equal);
}
private static String nestedToIndented(String nested) {
StringBuilder result = new StringBuilder();
for ( String line : nested.split(LINE_END) ) {
int index = 0;
while ( line.charAt(index) == '.' ) {
index += 1;
}
result.append(String.valueOf(index / 4) + " " + line.substring(index) + LINE_END);
}
return result.toString();
}
 
private static String indentedToNested(String indented) {
StringBuilder result = new StringBuilder();
for ( String line : indented.split(LINE_END) ) {
final int index = line.indexOf(' ');
final int level = Integer.valueOf(line.substring(0, index));
for ( int i = 0; i < level; i++ ) {
result.append("....");
}
result.append(line.substring(index + 1) + LINE_END);
}
return result.toString();
}
private static final String LINE_END = "\n";
 
}
</syntaxhighlight>
{{ out }}
<pre>
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
 
0 Rosetta Code
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
 
initialNested = finalNested ? true
</pre>
 
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
{{works with|jq}}
'''Also works with gojq, the Go implementation of jq'''
 
<syntaxhighlight lang="jq">
# node of a nested representation
def NNode($name; $children): {$name, $children};
 
# node of an indented representation:
def INode($level; $name): {$level, $name};
 
# Output: string representation of an NNode structure
def printNest:
. as $nested
# input: string so far
| def printNest($n; $level):
if ($level == 0) then "\n==Nest form==\n\n" else . end
| reduce ($n.children[], null) as $c ( . + "\((" " * $level) // "")\($n.name)\n";
if $c == null then .
else . + (" " * ($level + 1)) | printNest($c; $level + 1)
end );
printNest($nested; 0);
 
# input: an INode structure
# output: the corresponding NNode structure
def toNest:
. as $in
| def toNest($iNodes; start; level):
{ i: (start + 1),
n: (if (level == 0) then .name = $iNodes[0].name else . end)
}
| until ( (.i >= ($iNodes|length)) or .done;
if ($iNodes[.i].level == level + 1)
then .i as $i
| (NNode($iNodes[$i].name; []) | toNest($iNodes; $i; level+1)) as $c
| .n.children += [$c]
else if ($iNodes[.i].level <= level) then .done = true else . end
end
| .i += 1 )
| .n ;
NNode(""; []) | toNest($in; 0; 0);
 
# Output: string representation of an INode structure
def printIndent:
"\n==Indent form==\n\n"
+ reduce .[] as $n ("";
. + "\($n.level) \($n.name)\n") ;
 
# output: representation using INode
def toIndent:
def toIndent($n; level):
. + [INode(level; $n.name)]
+ reduce $n.children[] as $c ([];
toIndent($c; level+1) );
. as $in
| [] | toIndent($in; 0);
 
 
### Example
 
def n: NNode(""; []);
def n1: NNode("RosettaCode"; []);
def n2: NNode("rocks"; [NNode("code"; []), NNode("comparison"; []), NNode("wiki"; [])] );
def n3: NNode("mocks"; [NNode("trolling"; [])]);
 
def n123:
n1
| .children += [n2]
| .children += [n3];
 
### The task
def nested:
n123
| printNest ;
 
def indented:
n123
| toIndent
| printIndent;
 
def roundtrip:
n123
| toIndent
| toNest
| printNest;
 
def task:
nested as $nested
| roundtrip as $roundtrip
| $nested, indented, $roundtrip,
"\nRound trip test satisfied? \($nested == $roundtrip)" ;
 
task
</syntaxhighlight>
{{output}}
As for [[#Wren|Wren]].
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">const nesttext = """
RosettaCode
rocks
Line 594 ⟶ 963:
println("Back to nest form:\n", restorednesttext, "\n")
println("original == restored: ", strip(nesttext) == strip(restorednesttext))
</langsyntaxhighlight>{{out}}
<pre>
Original:
Line 629 ⟶ 998:
original == restored: true
</pre>
 
=={{header|Nim}}==
 
<syntaxhighlight lang="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"</syntaxhighlight>
 
{{out}}
<pre>Displaying tree built using nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
Displaying tree converted to indented structure:
0 RosettaCode
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
Displaying tree converted back to nested structure:
RosettaCode
rocks
code
comparison
wiki
mocks
trolling
 
Are they equal? yes</pre>
 
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
{$zerobasedstrings}
function NestedToIndented(nested: string): string;
begin
var lst := new List<string>;
foreach var line in Regex.Split(nested,NewLine) do
begin
var ind := Regex.Match(line,'[^\.]').Index;
lst.Add($'{ind div 4} {line[ind:]}');
end;
Result := lst.JoinToString(NewLine);
end;
 
function IndentedToNested(indented: string): string;
begin
var lst := new List<string>;
foreach var line in Regex.Split(indented,NewLine) do
begin
var ind := line.IndexOf(' ');
var level := line[:ind].ToInteger;
lst.Add((level*4) * '.' + line[ind+1:]);
end;
Result := lst.JoinToString(NewLine);
end;
 
begin
var initialNested := '''
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
''';
Writeln(initialNested,NewLine);
var indented := NestedToIndented(initialNested);
Writeln(indented,NewLine);
var nested := IndentedToNested(indented);
Writeln(nested,NewLine);
Writeln($'Initial = Restored: {initialNested = nested}');
end.
</syntaxhighlight>
{{ out }}
<pre>
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
 
0 Rosetta Code
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 trolling
 
Rosetta Code
....rocks
........code
........comparison
........wiki
....mocks
........trolling
 
Initial = Restored: True
</pre>
 
 
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use feature 'say';
Line 690 ⟶ 1,299:
my $forest = import $trees;
say "Native data structure:\n" . np $forest;
say "\nJSON:\n" . encode_json($forest);</langsyntaxhighlight>
{{out}}
<pre>RosettaCode
Line 748 ⟶ 1,357:
{{libheader|Phix/basics}}
The standard Phix sequence is perfect for handling all of these kinds of structures.
<!--<langsyntaxhighlight Phixlang="phix">-->
<span style="color: #008080;">function</span> <span style="color: #000000;">text_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">plain_text</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lines</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plain_text</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">no_empty</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">),</span>
Line 812 ⟶ 1,421:
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nested</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nNested to indent:%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n2ichk</span><span style="color: #0000FF;">==</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"same"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"***ERROR***"</span><span style="color: #0000FF;">)})</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 852 ⟶ 1,461:
You can also strictly enforce these structures, which is obviously useful for debugging.<br>
Admittedly this is somewhat more tedious, but at the same time infinitely more flexible and powerful than a "plain old struct".
<!--<langsyntaxhighlight Phixlang="phix">-->
<span style="color: #008080;">type</span> <span style="color: #000000;">indent_struct</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">o</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">o</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
Line 892 ⟶ 1,501:
<span style="color: #000000;">nested_struct</span> <span style="color: #000000;">nested</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">indent_to_nested</span><span style="color: #0000FF;">(</span><span style="color: #000000;">indent</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">indent_struct</span> <span style="color: #000000;">r2ichk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nested_to_indent</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nested</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
 
=={{header|Python}}==
Just arranges the standard lists and tuples for the datastructures allowing pprint to show the different arrangement of storage.
 
<langsyntaxhighlight lang="python">from pprint import pprint as pp
 
def to_indent(node, depth=0, flat=None):
Line 938 ⟶ 1,547:
 
if nest != as_nest:
print("Whoops round-trip issues")</langsyntaxhighlight>
 
{{out}}
Line 973 ⟶ 1,582:
Code golf is a entertaining passtime, even if it isn't appropriate for this site. To a large extent, I agree with [[User:Hout|Hout]], I am not really on board with mocking anybody, especially espousing it as an official RosettaCode position. So, feel free to mark this incorrect.
 
<syntaxhighlight lang="raku" perl6line>#`(
Sort of vague as to what we are trying to accomplish here. If we are just
trying to transform from one format to another, probably easiest to just
Line 1,050 ⟶ 1,659:
use YAML;
say "\nYAML:\n", $forest.&dump;
}</langsyntaxhighlight>
{{out}}
<pre>RosettaCode
Line 1,156 ⟶ 1,765:
{{libheader|Wren-dynamic}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./dynamic" for Struct
import "./fmt" for Fmt
 
var NNode = Struct.create("NNode", ["name", "children"])
Line 1,222 ⟶ 1,831:
System.print(s2)
 
System.print("\nRound trip test satisfied? %(s1 == s2)")</langsyntaxhighlight>
 
{{out}}
Line 1,263 ⟶ 1,872:
 
=={{header|zkl}}==
<langsyntaxhighlight lang="zkl">fcn nestToIndent(nestTree){
fcn(out,node,level){
out.append(List(level,node[0])); // (n,name) or ("..",name)
Line 1,311 ⟶ 1,920:
return(nTree)
}
fcn indentToString(indentTree){ indentTree.apply("concat"," ").concat("\n") }</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">tree:=L("RosettaCode",
L("rocks","code","comparison","wiki"),
L("mocks","golfing") );
Line 1,324 ⟶ 1,933:
nestTree:=indentToNest(indentTree);
println("\nIndent to nested format:\n",nestTree);
println("Is this tree the same as what we started with? ",nestTree==tree);</langsyntaxhighlight>
{{out}}
<pre>
Line 1,352 ⟶ 1,961:
</pre>
I'm choosing to only allow one root per tree/forest so the Raku example is coded differently:
<langsyntaxhighlight lang="zkl">rakutrees:=L(
L("RosettaCode",
L("encourages",
Line 1,368 ⟶ 1,977:
iTrees := rakutrees.apply(nestToIndent);
println(iTrees.apply(indentToString).concat("\n"));
(iTrees.apply(indentToNest)==rakutrees).println();</langsyntaxhighlight>
{{out}}
<pre style="height:40ex">
Miks1965
26

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/294535...364434"