Tree from nesting levels: Difference between revisions
Added C#
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added C#) |
||
| (8 intermediate revisions by 6 users not shown) | |||
Line 695:
[3, 3, 3, 1, 1, 3, 3, 3] Nests to:
[[[3, 3, 3]], 1, 1, [[3, 3, 3]]]
</pre>
=={{header|C sharp|C#}}==
{{works with|C sharp|12}}
<syntaxhighlight lang="csharp">public static class TreeFromNestingLevels
{
public static void Main()
{
List<int[]> tests = [[], [1,2,4], [3,1,3,1], [1,2,3,1], [3,2,1,3], [3,3,3,1,1,3,3,3]];
Console.WriteLine($"{"Input",24} -> {"Nested",-32} -> Round-trip");
foreach (var test in tests) {
var tree = BuildTree(test);
string input = $"[{string.Join(", ", test)}]";
string roundTrip = $"[{string.Join(", ", tree.ToList())}]";
Console.WriteLine($"{input,24} -> {tree,-32} -> {roundTrip}");
}
}
private static Tree BuildTree(int[] levels)
{
Tree root = new(0);
Tree current = root;
foreach (int level in levels) {
while (current.Level > level) current = current.Parent;
current = current.Parent.Add(level);
}
return root;
}
private class Tree
{
public int Level { get; }
public Tree Parent { get; }
private readonly List<Tree> children = [];
public Tree(int level, Tree? parent = null)
{
Level = level;
Parent = parent ?? this;
}
public Tree Add(int level)
{
if (Level == level) return this;
Tree tree = new(Level + 1, this);
children.Add(tree);
return tree.Add(level);
}
public override string ToString() => children.Count == 0
? (Level == 0 ? "[]" : $"{Level}")
: $"[{string.Join(", ", children.Select(c => c.ToString()))}]";
public List<int> ToList()
{
List<int> list = [];
ToList(this, list);
return list;
}
private static void ToList(Tree tree, List<int> list)
{
if (tree.children.Count == 0) {
if (tree.Level > 0) list.Add(tree.Level);
} else {
foreach (Tree child in tree.children) {
ToList(child, list);
}
}
}
}
}</syntaxhighlight>
{{out}}
<pre>
Input -> Nested -> Round-trip
[] -> [] -> []
[1, 2, 4] -> [1, [2, [[4]]]] -> [1, 2, 4]
[3, 1, 3, 1] -> [[[3]], 1, [[3]], 1] -> [3, 1, 3, 1]
[1, 2, 3, 1] -> [1, [2, [3]], 1] -> [1, 2, 3, 1]
[3, 2, 1, 3] -> [[[3], 2], 1, [[3]]] -> [3, 2, 1, 3]
[3, 3, 3, 1, 1, 3, 3, 3] -> [[[3, 3, 3]], 1, 1, [[3, 3, 3]]] -> [3, 3, 3, 1, 1, 3, 3, 3]</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
const TreeData1: array [0..0] of integer = (0);
const TreeData2: array [0..2] of integer = (1, 2, 4);
const TreeData3: array [0..3] of integer = (3, 1, 3, 1);
const TreeData4: array [0..3] of integer = (1, 2, 3, 1);
const TreeData5: array [0..3] of integer = (3, 2, 1, 3);
const TreeData6: array [0..7] of integer = (3, 3, 3, 1, 1, 3, 3, 3);
function GetDataString(Data: array of integer): string;
var I: integer;
begin
Result:='[';
for I:=0 to High(Data) do
begin
if I<>0 then Result:=Result+', ';
Result:=Result+IntToStr(Data[I]);
end;
Result:=Result+']';
end;
function GetNestingLevel(Data: array of integer): string;
var Level,Level2: integer;
var I,J,HLen: integer;
begin
Level:=0;
Result:='';
for I:=0 to High(Data) do
begin
Level2:=Data[I];
if Level2>Level then for J:=Level to Level2-1 do Result:=Result+'['
else if Level2<Level then
begin
for J:=Level-1 downto Level2 do Result:=Result+']';
Result:=Result+', ';
end
else if Level2=0 then
begin
Result:='[]';
break;
end
else Result:=Result+', ';
Result:=Result+IntToStr(Level2);
Level:=Level2;
if (I<High(Data)) and (Level<Data[I+1]) then Result:=Result+', ';
end;
for J:=Level downto 1 do Result:=Result+']';
end;
procedure ShowNestData(Memo: TMemo; Data: array of integer);
begin
Memo.Lines.Add(GetDataString(Data)+' Nests to: ');
Memo.Lines.Add(GetNestingLevel(Data));
Memo.Lines.Add('');
end;
procedure ShowNestingLevels(Memo: TMemo);
var S: string;
begin
ShowNestData(Memo,TreeData1);
ShowNestData(Memo,TreeData2);
ShowNestData(Memo,TreeData3);
ShowNestData(Memo,TreeData4);
ShowNestData(Memo,TreeData5);
ShowNestData(Memo,TreeData6);
end;
</syntaxhighlight>
{{out}}
<pre>
[0] Nests to:
[]
[1, 2, 4] Nests to:
[1, [2, [[4]]]]
[3, 1, 3, 1] Nests to:
[[[3]], 1, [[3]], 1]
[1, 2, 3, 1] Nests to:
[1, [2, [3]], 1]
[3, 2, 1, 3] Nests to:
[[[3], 2], 1, [[3]]]
[3, 3, 3, 1, 1, 3, 3, 3] Nests to:
[[[3, 3, 3]], 1, 1, [[3, 3, 3]]]
Elapsed Time: 21.513 ms.
</pre>
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Tree_from_nesting_levels}}
'''Solution'''
[[File:Fōrmulæ - Tree from nesting levels 01.png]]
'''Test cases'''
[[File:Fōrmulæ - Tree from nesting levels 02.png]]
[[File:Fōrmulæ - Tree from nesting levels 03.png]]
Notice that in Fōrmulæ an array of arrays (of the same cardinality each) is automatically shown as a matrix.
[[File:Fōrmulæ - Tree from nesting levels 04.png]]
[[File:Fōrmulæ - Tree from nesting levels 05.png]]
[[File:Fōrmulæ - Tree from nesting levels 06.png]]
[[File:Fōrmulæ - Tree from nesting levels 07.png]]
[[File:Fōrmulæ - Tree from nesting levels 08.png]]
[[File:Fōrmulæ - Tree from nesting levels 09.png]]
[[File:Fōrmulæ - Tree from nesting levels 10.png]]
[[File:Fōrmulæ - Tree from nesting levels 11.png]]
[[File:Fōrmulæ - Tree from nesting levels 12.png]]
[[File:Fōrmulæ - Tree from nesting levels 13.png]]
'''Other test cases'''
Cases generated with random numbers:
[[File:Fōrmulæ - Tree from nesting levels 14.png]]
[[File:Fōrmulæ - Tree from nesting levels 15.png]]
=={{header|FreeBASIC}}==
<syntaxhighlight lang="vb">Sub ShowTree(List() As Integer)
Dim As Integer I, NestLevel = 0
For I = 0 To Ubound(List)
While List(I) < NestLevel
Print "]";
NestLevel -= 1
Wend
If List(I) = 0 Then
Print
Elseif I <> Lbound(List) Then Print ", ";
End If
While List(I) > NestLevel
Print "[";
NestLevel += 1
Wend
If NestLevel <> 0 Then Print NestLevel;
Next I
End Sub
Dim As Integer list(0 To ...) = {0}
ShowTree(list())
Dim As Integer list0(0 To ...) = {1, 2, 4, 0}
ShowTree(list0())
Dim As Integer list1(0 To ...) = {3, 1, 3, 1, 0}
ShowTree(list1())
Dim As Integer list2(0 To ...) = {1, 2, 3, 1, 0}
ShowTree(list2())
Dim As Integer list3(0 To ...) = {3, 2, 1, 3, 0}
ShowTree(list3())
Dim As Integer list4(0 To ...) = {3, 3, 3, 1, 1, 3, 3, 3, 0}
ShowTree(list4())
Dim As Integer list5(0 To ...) = {1, 2, 4, 2, 2, 1, 0}
ShowTree(list5())
Sleep</syntaxhighlight>
{{out}}
<pre> 'Note that [0] displays nothing.
[ 1, [ 2, [[ 4]]]]
[[[ 3]], 1, [[ 3]], 1]
[ 1, [ 2, [ 3]], 1]
[[[ 3], 2], 1, [[ 3]]]
[[[ 3, 3, 3]], 1, 1, [[ 3, 3, 3]]]
[ 1, [ 2, [[ 4]], 2, 2], 1]</pre>
=={{header|Go}}==
Line 1,163 ⟶ 1,430:
│└─────┴─┴─────┴─┘│ │ │
└─────────────────┴─┴─────┘</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public final class TreeNestingLevels {
public static void main(String[] args) {
List<List<Integer>> lists = List.of(
Arrays.asList(),
Arrays.asList( 1, 2, 4 ),
Arrays.asList( 3, 1, 3, 1 ),
Arrays.asList( 1, 2, 3, 1 ),
Arrays.asList( 3, 2, 1, 3 ),
Arrays.asList( 3, 3, 3, 1, 1, 3, 3, 3 )
);
for ( List<Integer> list : lists ) {
List<Object> tree = createTree(list);
System.out.println(list + " --> " + tree);
}
}
private static List<Object> createTree(List<Integer> list) {
return makeTree(list, 0, 1);
}
private static List<Object> makeTree(List<Integer> list, int index, int depth) {
List<Object> tree = new ArrayList<Object>();
int current;
while ( index < list.size() && depth <= ( current = list.get(index) ) ) {
if ( depth == current ) {
tree.add(current);
index += 1;
} else {
tree.add(makeTree(list, index, depth + 1));
final int position = list.subList(index, list.size()).indexOf(depth);
index += ( position == -1 ) ? list.size() : position;
}
}
return tree;
}
}
</syntaxhighlight>
{{ out }}
<pre>
[] --> []
[1, 2, 4] --> [1, [2, [[4]]]]
[3, 1, 3, 1] --> [[[3]], 1, [[3]], 1]
[1, 2, 3, 1] --> [1, [2, [3]], 1]
[3, 2, 1, 3] --> [[[3], 2], 1, [[3]]]
[3, 3, 3, 1, 1, 3, 3, 3] --> [[[3, 3, 3]], 1, 1, [[3, 3, 3]]]
</pre>
=={{header|Julia}}==
Line 2,275 ⟶ 2,602:
{{libheader|Wren-seq}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var toTree = Fn.new { |list|
Line 2,322 ⟶ 2,649:
===Recursive===
{{trans|Python}}
<syntaxhighlight lang="
var toTree // recursive
Line 2,361 ⟶ 2,688:
<pre>
Same as iterative version.
</pre>
=={{header|XPL0}}==
A sentinel 0 is used to terminate the input arrays because XPL0 does not have built-in lists.
Note that [0] displays nothing.
<syntaxhighlight lang "XPL0">proc ShowTree(List);
int List, NestLevel, I;
[NestLevel:= 0;
for I:= 0 to -1>>1 do
[while List(I) < NestLevel do
[ChOut(0, ^]); NestLevel:= NestLevel-1];
if List(I) = 0 then [CrLf(0); return];
if I # 0 then Text(0, ", ");
while List(I) > NestLevel do
[ChOut(0, ^[); NestLevel:= NestLevel+1];
IntOut(0, NestLevel);
];
];
[ShowTree([0]);
ShowTree([1, 2, 4, 0]);
ShowTree([3, 1, 3, 1, 0]);
ShowTree([1, 2, 3, 1, 0]);
ShowTree([3, 2, 1, 3, 0]);
ShowTree([3, 3, 3, 1, 1, 3, 3, 3, 0]);
ShowTree([1, 2, 4, 2, 2, 1, 0]);
]</syntaxhighlight>
{{out}}
<pre>
[1, [2, [[4]]]]
[[[3]], 1, [[3]], 1]
[1, [2, [3]], 1]
[[[3], 2], 1, [[3]]]
[[[3, 3, 3]], 1, 1, [[3, 3, 3]]]
[1, [2, [[4]], 2, 2], 1]
</pre>
| |||