Tree datastructures: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|zkl}}: Fix code and comment: Perl 6 --> Raku)
m (→‎{{header|Raku}}: .perl -> .raku)
Line 569: Line 569:
=={{header|Raku}}==
=={{header|Raku}}==
(formerly Perl 6)
(formerly Perl 6)
{{works with|Rakudo|2019.07.1}}
{{works with|Rakudo|2020.08.1}}
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.
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.


Line 634: Line 634:


$forest ~= ']' x 1 + $last;
$forest ~= ']' x 1 + $last;
use MONKEY-SEE-NO-EVAL;
$forest.EVAL;
$forest.EVAL;
}
}
Line 640: Line 639:
my $forest = import $trees;
my $forest = import $trees;


say "\nNative data structure:\n", $forest.perl;
say "\nNative data structure:\n", $forest.raku;


{
{

Revision as of 04:17, 28 August 2020

Tree datastructures is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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
  1. Create/use a nest datastructure format and textual representation for arbitrary trees.
  2. Create/use an indent datastructure format and textual representation for arbitrary trees.
  3. Create methods/classes/proceedures/routines etc to:
    1. Change from a nest tree datastructure to an indent one.
    2. Change from an indent tree datastructure to a nest one
  4. Use the above to encode the example at the start into the nest format, and show it.
  5. transform the initial nest format to indent format and show it.
  6. transform the indent format to final nest format and show it.
  7. 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.


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

Julia

<lang julia>const nesttext = """ RosettaCode 

   rocks
       code
       comparison
       wiki
   mocks
       trolling

"""

function nesttoindent(txt) 

   ret = ""
   windent = gcd(length.([x.match for x in eachmatch(r"\s+", txt)]) .- 1)
   for lin in split(txt, "\n")
       ret *= isempty(lin) ? "\n" : isspace(lin[1]) ? 
           replace(lin, r"\s+" => (s) -> "$(length(s)÷windent)    ") * "\n" :
           "0    " * lin * "\n"
   end
   return ret, " "^windent

end

function indenttonest(txt, indenttext) 

   ret = ""
   for lin in filter(x -> length(x) > 1, split(txt, "\n"))
       (num, name) = split(lin, r"\s+", limit=2)
       indentnum = parse(Int, num)
       ret *= indentnum == 0 ? name * "\n" : indenttext^indentnum * name * "\n"
   end
   return ret

end

indenttext, itext = nesttoindent(nesttext) restorednesttext = indenttonest(indenttext, itext)

println("Original:\n", nesttext, "\n") println("Indent form:\n", indenttext, "\n") println("Back to nest form:\n", restorednesttext, "\n") println("original == restored: ", strip(nesttext) == strip(restorednesttext))

</lang>

Output:
Original:
RosettaCode
    rocks
        code
        comparison
        wiki
    mocks
        trolling


Indent form:
0    RosettaCode
1    rocks
2    code
2    comparison
2    wiki
1    mocks
2    trolling



Back to nest form:
RosettaCode
    rocks
        code
        comparison
        wiki
    mocks
        trolling


original == restored: true

Perl

Translation of: Raku

<lang perl>use strict; use warnings; use feature 'say'; use JSON; use Data::Printer;

my $trees = <<~END; 

   RosettaCode
     encourages
       code
         diversity
         comparison
     discourages
       golfing
       trolling
       emphasising execution speed
   code-golf.io
     encourages
       golfing
     discourages
       comparison
   END

my $level = ' '; sub nested_to_indent { shift =~ s#^($level*)# ($1 ? length($1)/length $level : 0) . ' ' #egmr } sub indent_to_nested { shift =~ s#^(\d+)\s*# $level x $1 #egmr }

say my $indent = nested_to_indent $trees; 

   my $nest   = indent_to_nested $indent;

use Test::More; is($trees, $nest, 'Round-trip'); done_testing();

  1. Import outline paragraph into native data structure

sub import { 

   my($trees) = @_;
   my $level = '  ';
   my $forest;
   my $last = -999;

   for my $branch (split /\n/, $trees) {
       $branch =~ m/(($level*))*/;
       my $this = $1 ? length($1)/length($level) : 0;
       $forest .= do {
           if    ($this gt $last) { '['                   . trim_and_quote($branch) }
           elsif ($this lt $last) { ']'x($last-$this).',' . trim_and_quote($branch) }
           else                   {                         trim_and_quote($branch) }
       };
       $last = $this;
   }
   sub trim_and_quote { shift =~ s/^\s*(.*\S)\s*$/"$1",/r }

   eval $forest . ']' x (1+$last);

}

my $forest = import $trees; say "Native data structure:\n" . np $forest; say "\nJSON:\n" . encode_json($forest);</lang>

Output:
RosettaCode
1 encourages
2 code
3 diversity
3 comparison
1 discourages
2 golfing
2 trolling
2 emphasising execution speed
code-golf.io
1 encourages
2 golfing
1 discourages
2 comparison

ok 1 - Round-trip
1..1

Native data structure:
\ [
    [0] "RosettaCode",
    [1] [
        [0] "encourages",
        [1] [
            [0] "code",
            [1] [
                [0] "diversity",
                [1] "comparison"
            ]
        ],
        [2] "discourages",
        [3] [
            [0] "golfing",
            [1] "trolling",
            [2] "emphasising execution speed"
        ]
    ],
    [2] "code-golf.io",
    [3] [
        [0] "encourages",
        [1] [
            [0] "golfing"
        ],
        [2] "discourages",
        [3] [
            [0] "comparison"
        ]
    ]
]

JSON:
["RosettaCode",["encourages",["code",["diversity","comparison"]],"discourages",["golfing","trolling","emphasising execution speed"]],"code-golf.io",["encourages",["golfing"],"discourages",["comparison"]]]

Phix

The standard Phix sequence is perfect for handling all of these kinds of structures. <lang Phix>function text_to_indent(string plain_text) 

   sequence lines = split(plain_text,"\n",no_empty:=true),
            parents = {}
   for i=1 to length(lines) do
       string line = trim_tail(lines[i]),
              text = trim_head(line)
       integer indent = length(line)-length(text)
       -- remove any completed parents
       while length(parents) and indent<=parents[$] do
           parents = parents[1..$-1]
       end while
       -- append potential new parent
       parents &= indent
       integer depth = length(parents)
       lines[i] = {depth,text}
   end for
   return lines

end function

function indent_to_nested(sequence indent, integer idx=1, level=1) 

   sequence res = {}
   while idx<=length(indent) do
       {integer lvl, string text} = indent[idx]
       if lvl<level then exit end if
       {sequence children,idx} = indent_to_nested(indent,idx+1,level+1)
       res = append(res,{text,children})
   end while
   return {res,idx}

end function

function nested_to_indent(sequence nested, integer level=1) 

   sequence res = {}
   for i=1 to length(nested) do
       {string text, sequence children} = nested[i]
       res = append(res,{level,text})
       res &= nested_to_indent(children,level+1)
   end for
   return res

end function

constant text = """ 

   RosettaCode
     encourages
       code
         diversity
         comparison
     discourages
       emphasising execution speed
   code-golf.io
     encourages
       golfing
     discourages
       comparison"""

sequence indent = text_to_indent(text), 

        nested = indent_to_nested(indent)[1],
        n2ichk = nested_to_indent(nested)

puts(1,"Indent form:\n") pp(indent,{pp_Nest,1}) puts(1,"\nNested form:\n") pp(nested,{pp_Nest,8}) printf(1,"\nNested to indent:%s\n",{iff(n2ichk==indent?"same":"***ERROR***")})</lang>

Output:
Indent form:
{{1, `RosettaCode`},
 {2, `encourages`},
 {3, `code`},
 {4, `diversity`},
 {4, `comparison`},
 {2, `discourages`},
 {3, `emphasising execution speed`},
 {1, `code-golf.io`},
 {2, `encourages`},
 {3, `golfing`},
 {2, `discourages`},
 {3, `comparison`}}

Nested form:
{{`RosettaCode`,
  {{`encourages`,
    {{`code`,
      {{`diversity`,
        {}},
       {`comparison`,
        {}}}}}},
   {`discourages`,
    {{`emphasising execution speed`,
      {}}}}}},
 {`code-golf.io`,
  {{`encourages`,
    {{`golfing`,
      {}}}},
   {`discourages`,
    {{`comparison`,
      {}}}}}}}

Nested to indent:same

You can also strictly enforce these structures, which is obviously useful for debugging.
Admittedly this is somewhat more tedious, but at the same time infinitely more flexible and powerful than a "plain old struct". <lang Phix>type indent_struct(object o) 

   if sequence(o) then
       for i=1 to length(o) do
           object oi = o[i]
           if not sequence(oi)
           or length(oi)!=2
           or not integer(oi[1])
           or not string(oi[2]) then
               return false
           end if
       end for
       return true
   end if
   return false

end type

type nested_struct(object o) 

   if sequence(o) then
       for i=1 to length(o) do
           object oi = o[i]
           if not sequence(oi)
           or length(oi)!=2
           or not string(oi[1])
           or not nested_struct(oi[2]) then
               return false
           end if
       end for
       return true
   end if
   return false

end type

-- and as above except: function indent_to_nested(indent_struct indent, integer idx=1, level=1) function nested_to_indent(nested_struct nested, integer level=1) -- also make the output sequences better typed: indent_struct indent = text_to_indent(text) nested_struct nested = indent_to_nested(indent)[1] indent_struct r2ichk = nested_to_indent(nested)</lang>

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', [])])])

Raku

(formerly Perl 6)

Works with: Rakudo version 2020.08.1

Code golf is a entertaining passtime, even if it isn't appropriate for this site. To a large extent, I agree with 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.

<lang perl6>#`( 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 perform string manipulations. )

my $level = ' ';

my $trees = q:to/END/; 

   RosettaCode
     encourages
       code
         diversity
         comparison
     discourages
       golfing
       trolling
       emphasising execution speed
   code-golf.io
     encourages
       golfing
     discourages
       comparison
   END

sub nested-to-indent { $^str.subst: / ^^ ($($level))* /, -> $/ { "{+$0} " }, :g } sub indent-to-nested { $^str.subst: / ^^ (\d+) \s* /, -> $/ { "{$level x +$0}" }, :g }

say $trees; say my $indent = $trees.&nested-to-indent; say my $nest = $indent.&indent-to-nested;

use Test; is($trees, $nest, 'Round-trip equals original');

  1. `(

If, on the other hand, we want perform more complex transformations; better to load it into a native data structure which will then allow us to manipulate it however we like. )

  1. Import outline paragraph into native data structure

sub import (Str $trees, $level = ' ') { 

   my $forest;
   my $last = -Inf;

   for $trees.lines -> $branch {
       $branch ~~ / ($($level))* /;
       my $this = +$0;
       $forest ~= do {
           given $this cmp $last {
               when More { "\['{esc $branch.trim}', " }
               when Same { "'{esc $branch.trim}', " }
               when Less { "{']' x $last - $this}, '{esc $branch.trim}', " }
           }
       }
       $last = $this;
   }

   sub esc { $^s.subst( /(<['\\]>)/, -> $/ { "\\$0" }, :g) }

   $forest ~= ']' x 1 + $last;
   $forest.EVAL;

}

my $forest = import $trees;

say "\nNative data structure:\n", $forest.raku;

{ 

   use JSON::Fast;
   say "\nJSON:\n", $forest.&to-json;

}

{ 

   use YAML;
   say "\nYAML:\n", $forest.&dump;

}</lang>

Output:
RosettaCode
  encourages
    code
      diversity
      comparison
  discourages
    golfing
    trolling
    emphasising execution speed
code-golf.io
  encourages
    golfing
  discourages
    comparison

0 RosettaCode
1 encourages
2 code
3 diversity
3 comparison
1 discourages
2 golfing
2 trolling
2 emphasising execution speed
0 code-golf.io
1 encourages
2 golfing
1 discourages
2 comparison

RosettaCode
  encourages
    code
      diversity
      comparison
  discourages
    golfing
    trolling
    emphasising execution speed
code-golf.io
  encourages
    golfing
  discourages
    comparison

ok 1 - Round-trip equals original

Native data structure:
$["RosettaCode", ["encourages", ["code", ["diversity", "comparison"]], "discourages", ["golfing", "trolling", "emphasising execution speed"]], "code-golf.io", ["encourages", ["golfing"], "discourages", ["comparison"]]]

JSON:
[
  "RosettaCode",
  [
    "encourages",
    [
      "code",
      [
        "diversity",
        "comparison"
      ]
    ],
    "discourages",
    [
      "golfing",
      "trolling",
      "emphasising execution speed"
    ]
  ],
  "code-golf.io",
  [
    "encourages",
    [
      "golfing"
    ],
    "discourages",
    [
      "comparison"
    ]
  ]
]

YAML:
---
- RosettaCode
- - encourages
  - - code
    - - diversity
      - comparison
  - discourages
  - - golfing
    - trolling
    - emphasising execution speed
- code-golf.io
- - encourages
  - - golfing
  - discourages
  - - comparison
...

zkl

<lang zkl>fcn nestToIndent(nestTree){ 

  fcn(out,node,level){
     out.append(List(level,node[0]));	// (n,name) or ("..",name)
     if(node.len()>1){		// (name children), (name, (tree))

level+=1; foreach child in (node[1,*]){ if(String.isType(child)) out.append(List(level,child)); else self.fcn(out,child,level) } 

     }
     out
  }(List(),nestTree,0)

} fcn nestToString(nestTree,dot="."){ 

  fcn(out,dot,node,level){
     out.writeln(dot*level,node[0]);	// (name)
     if(node.len()>1){			// (name children), (name, (tree))

level+=1; foreach child in (node[1,*]){ if(String.isType(child)) out.writeln(dot*level,child); else self.fcn(out,dot,child,level) } 

     }
     out
  }(Data(),dot,nestTree,0).text

}

fcn indentToNest(iTree,depth=0,nTree=List()){ 

  while(iTree){	// (n,name)
     d, name := iTree[0];
     if(d==depth){
        nTree.append(name);

iTree.pop(0); 

     }
     else if(d>depth){		// assume can't skip levels down

if(nTree.len()>1 and not List.isType((nm:=nTree[-1]))){ nTree[-1]=(children:=List(nm)); indentToNest(iTree,d,children); }else{ nTree.append(children:=List(name)); iTree.pop(0); indentToNest(iTree,d+1,children); } 

     }
     else break;  // d<depth
  }
  return(nTree)

} fcn indentToString(indentTree){ indentTree.apply("concat"," ").concat("\n") }</lang> <lang zkl>tree:=L("RosettaCode", 

        L("rocks","code","comparison","wiki"),

L("mocks","golfing") );

println("Nest tree internal format:\n",tree.toString(*,*)); println("Formated:\n",nestToString(tree));

indentTree:=nestToIndent(tree); println("To indent format:\n",indentToString(indentTree));

nestTree:=indentToNest(indentTree); println("\nIndent to nested format:\n",nestTree); println("Is this tree the same as what we started with? ",nestTree==tree);</lang>

Output:
Nest tree internal format:
L("RosettaCode",L("rocks","code","comparison","wiki"),L("mocks","golfing"))
Formated:
RosettaCode
.rocks
..code
..comparison
..wiki
.mocks
..golfing

To indent format:
0 RosettaCode
1 rocks
2 code
2 comparison
2 wiki
1 mocks
2 golfing

Indent to nested format:
L("RosettaCode",L("rocks","code","comparison","wiki"),L("mocks","golfing"))
Is this tree the same as what we started with? True

I'm choosing to only allow one root per tree/forest so the Raku example is coded differently: <lang zkl>rakutrees:=L( 

  L("RosettaCode",
    L("encourages",
      L("code",

"diversity","comparison")), 

    L("discourages",
      "golfing","trolling","emphasising execution speed"),
  ),
  L("code-golf.io",
    L("encourages","golfing"),
    L("discourages","comparison"),
  )

); println(rakutrees.apply(nestToString).concat()); iTrees := rakutrees.apply(nestToIndent); println(iTrees.apply(indentToString).concat("\n")); (iTrees.apply(indentToNest)==rakutrees).println();</lang>

Output:
RosettaCode
  encourages
    code
      diversity
      comparison
  discourages
    golfing
    trolling
    emphasising execution speed
code-golf.io
  encourages
    golfing
  discourages
    comparison

0 RosettaCode
1 encourages
2 code
3 diversity
3 comparison
1 discourages
2 golfing
2 trolling
2 emphasising execution speed
0 code-golf.io
1 encourages
2 golfing
1 discourages
2 comparison
True
Retrieved from "https://rosettacode.org/wiki/Tree_datastructures?oldid=294528"