Rosetta Code

Tree datastructures: Difference between revisions

Page Discussion

Tree datastructures (view source)

Revision as of 18:12, 12 May 2024

6,225 bytes added ,  1 month ago
PascalABC.NET solution added before Perl
(Added 11l)
(PascalABC.NET solution added before Perl)
(5 intermediate revisions by 5 users not shown)
Line 42:
{{trans|Nim}}
 
<langsyntaxhighlight lang="11l">T NNode
String value
[NNode] children
Line 70:
F to_indented(node)
[INode] result
F add_node(NNode node, Int level) -> NVoid
@result.append(INode(node.value, level))
L(child) node.children
Line 120:
print(to_nested(indentedTree))
 
print(‘Are they equal? ’(I String(nestedTree) == String(to_nested(indentedTree)) {‘yes’} E ‘no’))</langsyntaxhighlight>
 
{{out}}
Line 155:
 
=={{header|C++}}==
<langsyntaxhighlight lang="cpp">#include <iomanip>
#include <iostream>
#include <list>
Line 257:
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 292:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 374:
 
fmt.Println("\nRound trip test satisfied? ", s1 == s2)
}</langsyntaxhighlight>
 
{{out}}
Line 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 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 504:
 
ttest :: Nest String
ttest = from test</langsyntaxhighlight>
 
<pre>λ> mapM_ print itest
Line 571:
we might also write something like:
 
<langsyntaxhighlight lang="haskell">import Data.Bifunctor (bimap, first)
import Data.Char (isSpace)
import Data.List (find)
Line 655:
Node "irregular" []
]
]</langsyntaxhighlight>
{{Out}}
<pre>Tree representation parsed directly:
Line 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 776 ⟶ 963:
println("Back to nest form:\n", restorednesttext, "\n")
println("original == restored: ", strip(nesttext) == strip(restorednesttext))
</langsyntaxhighlight>{{out}}
<pre>
Original:
Line 814 ⟶ 1,001:
=={{header|Nim}}==
 
<langsyntaxhighlight Nimlang="nim">import strformat, strutils
 
 
Line 946 ⟶ 1,133:
echo indentedTree.toNested
 
echo "Are they equal? ", if $nestedTree == $indentedTree.toNested: "yes" else: "no"</langsyntaxhighlight>
 
{{out}}
Line 977 ⟶ 1,164:
 
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 1,038 ⟶ 1,299:
my $forest = import $trees;
say "Native data structure:\n" . np $forest;
say "\nJSON:\n" . encode_json($forest);</langsyntaxhighlight>
{{out}}
<pre>RosettaCode
Line 1,096 ⟶ 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 1,160 ⟶ 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 1,200 ⟶ 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 1,240 ⟶ 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 1,286 ⟶ 1,547:
 
if nest != as_nest:
print("Whoops round-trip issues")</langsyntaxhighlight>
 
{{out}}
Line 1,321 ⟶ 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,398 ⟶ 1,659:
use YAML;
say "\nYAML:\n", $forest.&dump;
}</langsyntaxhighlight>
{{out}}
<pre>RosettaCode
Line 1,504 ⟶ 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,570 ⟶ 1,831:
System.print(s2)
 
System.print("\nRound trip test satisfied? %(s1 == s2)")</langsyntaxhighlight>
 
{{out}}
Line 1,611 ⟶ 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,659 ⟶ 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,672 ⟶ 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,700 ⟶ 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,716 ⟶ 1,977:
iTrees := rakutrees.apply(nestToIndent);
println(iTrees.apply(indentToString).concat("\n"));
(iTrees.apply(indentToNest)==rakutrees).println();</langsyntaxhighlight>
{{out}}
<pre style="height:40ex">
Miks1965
170

edits

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