Tree datastructures

Tree datastructures
You are encouraged to solve this task according to the task description, using any language you may know.

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.

11l

Translation of: Nim

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) -> N
      @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’))

Output:

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

C++

#include <iomanip>
#include <iostream>
#include <list>
#include <string>
#include <vector>
#include <utility>
#include <vector>

class nest_tree;

bool operator==(const nest_tree&, const nest_tree&);

class nest_tree {
public:
    explicit nest_tree(const std::string& name) : name_(name) {}
    nest_tree& add_child(const std::string& name) {
        children_.emplace_back(name);
        return children_.back();
    }
    void print(std::ostream& out) const {
        print(out, 0);
    }
    const std::string& name() const {
        return name_;
    }
    const std::list<nest_tree>& children() const {
        return children_;
    }
    bool equals(const nest_tree& n) const {
        return name_ == n.name_ && children_ == n.children_;
    }
private:
    void print(std::ostream& out, int level) const {
        std::string indent(level * 4, ' ');
        out << indent << name_ << '\n';
        for (const nest_tree& child : children_)
            child.print(out, level + 1);
    }
    std::string name_;
    std::list<nest_tree> children_;
};

bool operator==(const nest_tree& a, const nest_tree& b) {
    return a.equals(b);
}

class indent_tree {
public:
    explicit indent_tree(const nest_tree& n) {
        items_.emplace_back(0, n.name());
        from_nest(n, 0);
    }
    void print(std::ostream& out) const {
        for (const auto& item : items_)
            std::cout << item.first << ' ' << item.second << '\n';
    }
    nest_tree to_nest() const {
        nest_tree n(items_[0].second);
        to_nest_(n, 1, 0);
        return n;
    }
private:
    void from_nest(const nest_tree& n, int level) {
        for (const nest_tree& child : n.children()) {
            items_.emplace_back(level + 1, child.name());
            from_nest(child, level + 1);
        }
    }
    size_t to_nest_(nest_tree& n, size_t pos, int level) const {
        while (pos < items_.size() && items_[pos].first == level + 1) {
            nest_tree& child = n.add_child(items_[pos].second);
            pos = to_nest_(child, pos + 1, level + 1);
        }
        return pos;
    }
    std::vector<std::pair<int, std::string>> items_;
};

int main() {
    nest_tree n("RosettaCode");
    auto& child1 = n.add_child("rocks");
    auto& child2 = n.add_child("mocks");
    child1.add_child("code");
    child1.add_child("comparison");
    child1.add_child("wiki");
    child2.add_child("trolling");
    
    std::cout << "Initial nest format:\n";
    n.print(std::cout);
    
    indent_tree i(n);
    std::cout << "\nIndent format:\n";
    i.print(std::cout);
    
    nest_tree n2(i.to_nest());
    std::cout << "\nFinal nest format:\n";
    n2.print(std::cout);

    std::cout << "\nAre initial and final nest formats equal? "
        << std::boolalpha << n.equals(n2) << '\n';
    
    return 0;
}

Output:

Initial nest format:
RosettaCode
    rocks
        code
        comparison
        wiki
    mocks
        trolling

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

Final nest format:
RosettaCode
    rocks
        code
        comparison
        wiki
    mocks
        trolling

Are initial and final nest formats equal? true

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", []nNode{{"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)
}

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

Haskell

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.

{-# LANGUAGE FlexibleInstances       #-}
{-# LANGUAGE MultiParamTypeClasses   #-}
{-# LANGUAGE UndecidableSuperClasses #-}
{-# LANGUAGE TypeApplications        #-}

import Data.List (span)

-- A nested tree structure. 
-- Using `Maybe` allows encoding several zero-level items
-- or irregular lists (see test example)
data Nest a = Nest (Maybe a) [Nest a]
  deriving Eq

instance Show a => Show (Nest a) where
  show (Nest (Just a) []) = show a
  show (Nest (Just a) s) = show a ++ show s
  show (Nest Nothing []) = "\"\""
  show (Nest Nothing s) = "\"\"" ++ show s

-- An indented tree structure.
type Indent a = [(Int, a)]

-- class for isomorphic types
class Iso b a => Iso a b where
  from :: a -> b

-- A bijection from nested form to indent form
instance Iso (Nest a) (Indent a) where
  from = go (-1)
    where
      go n (Nest a t) =
        case a of
          Just a -> (n, a) : foldMap (go (n + 1)) t 
          Nothing -> foldMap (go (n + 1)) t

-- A bijection from indent form to nested form
instance Iso (Indent a) (Nest a) where
  from = revNest . foldl add (Nest Nothing [])
    where
      add t (d,x) = go 0 t
        where
          go n (Nest a s) =
            case compare n d of
              EQ -> Nest a $ Nest (Just x) [] : s
              LT -> case s of
                      h:t -> Nest a $ go (n+1) h : t
                      [] -> go n $ Nest a [Nest Nothing []]
              GT -> go (n-1) $ Nest Nothing [Nest a s]

      revNest (Nest a s) = Nest a (reverse $ revNest <$> s)  

-- A bijection from indent form to a string
instance Iso (Indent String) String where
  from = unlines . map process
    where
      process (d, s) = replicate (4*d) ' ' ++ s

-- A bijection from a string to indent form
instance Iso String (Indent String) where
  from = map process . lines
    where
      process s = let (i, a) = span (== ' ') s
                  in (length i `div` 4, a)

-- A bijection from nest form to a string via indent form
instance Iso (Nest String) String where
  from = from @(Indent String) . from

-- A bijection from a string to nest form via indent form
instance Iso String (Nest String) where
  from = from @(Indent String) . from

Testing:

test = unlines
  [ "RosettaCode"
  , "    rocks"
  , "        code"
  , "        comparison"
  , "        wiki"
  , "    mocks"
  , "        trolling"
  , "Some lists"
  , "            may"
  , "        be"
  , "    irregular"  ]

itest :: Indent String
itest = from test 

ttest :: Nest String
ttest = from test

λ> mapM_ print itest
(0,"RosettaCode")
(1,"rocks")
(2,"code")
(2,"comparison")
(2,"wiki")
(1,"mocks")
(2,"trolling")
(0,"Some lists")
(3,"may")
(2,"be")
(1,"irregular")

λ> ttest
""["RosettaCode"["rocks"["code","comparison","wiki"],"mocks"["trolling"]],
"Some lists"[""[""["may"],"be"],"irregular"]]

λ> putStr $ from (from test :: Indent String)
RosettaCode
    rocks
        code
        comparison
        wiki
    mocks
        trolling
Some lists
            may
        be
    irregular

λ> putStr $ from (from test :: Nest String)
RosettaCode
    rocks
        code
        comparison
        wiki
    mocks
        trolling
Some lists
            may
        be
    irregular

λ> test == from (from test :: Nest String)
True

λ> test == from (from test :: Indent String)
True

λ> itest == from (from itest :: String)
True

λ> itest == from (from itest :: Nest String)
True

λ> ttest == from (from ttest :: String)
True

λ> ttest == from (from ttest :: Indent String)
True

And less satisfyingly and instructively – just relying a little passively on the existing Data.Tree, we might also write something like:

import Data.Bifunctor (bimap, first)
import Data.Char (isSpace)
import Data.List (find)
import Data.Tree (Forest, Tree (..), drawTree)

-------- MAPPINGS BETWEEN INDENTED LINES AND TREES -------

forestFromNestLevels :: [(Int, String)] -> Forest String
forestFromNestLevels = go
  where
    go [] = []
    go ((n, v) : xs) =
      uncurry (:) $
        bimap (Node v . go) go (span ((n <) . fst) xs)

indentLevelsFromLines :: [String] -> [(Int, String)]
indentLevelsFromLines xs =
  let pairs = first length . span isSpace <$> xs
      indentUnit = maybe 1 fst (find ((0 <) . fst) pairs)
   in first (`div` indentUnit) <$> pairs

outlineFromForest ::
  (String -> String -> String) ->
  String ->
  Forest String ->
  String
outlineFromForest showRoot tabString forest =
  let go indent node =
        showRoot indent (rootLabel node) :
        (subForest node >>= go ((<>) tabString indent))
   in unlines $ forest >>= go ""

-------------------------- TESTS -------------------------
main :: IO ()
main = do
  putStrLn "Tree representation parsed directly:\n"
  putStrLn $ drawTree $ Node "" nativeForest

  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

  putStrLn "Indented text from trees:\n"
  putStrLn $ outlineFromForest (<>) "    " trees

test :: [String]
test =
  [ "RosettaCode",
    "    rocks",
    "        code",
    "        comparison",
    "        wiki",
    "    mocks",
    "        trolling",
    "Some lists",
    "            may",
    "        be",
    "    irregular"
  ]

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" []
      ]
  ]

Output:

Tree representation parsed directly:

|
+- 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:

|
+- RosettaCode
|  |
|  +- rocks
|  |  |
|  |  +- code
|  |  |
|  |  +- comparison
|  |  |
|  |  `- wiki
|  |
|  `- mocks
|     |
|     `- trolling
|
`- Some lists
   |
   +- may
   |
   +- be
   |
   `- irregular

Indented text from trees:

RosettaCode
    rocks
        code
        comparison
        wiki
    mocks
        trolling
Some lists
    may
    be
    irregular

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";

}

Output:

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

jq

Adapted from Wren

Works with: jq

Also works with gojq, the Go implementation of 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

Output:

As for Wren.

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))

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

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"

Output:

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

Perl

Translation of: Raku

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();

# 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);

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

Library: Phix/basics

The standard Phix sequence is perfect for handling all of these kinds of structures.

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***")})

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".

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)

Python

Just arranges the standard lists and tuples for the datastructures allowing pprint to show the different arrangement of storage.

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")

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.

#`(
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');

#`(
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.
)

# 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;
}

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
...

Wren

Translation of: Go

Library: Wren-dynamic

Library: Wren-fmt

import "./dynamic" for Struct
import "./fmt" for Fmt

var NNode = Struct.create("NNode", ["name", "children"])
var INode = Struct.create("INode", ["level", "name"])

var sw = ""

var printNest // recursive
printNest = Fn.new { |n, level|
    if (level == 0) sw = sw + "\n==Nest form==\n\n"
    sw = sw + Fmt.swrite("$0s$s\n", "  " * level, n.name)
    for (c in n.children) {
        sw = sw + ("  " * (level + 1))
        printNest.call(c, level+1)
    }
}

var toNest // recursive
toNest = Fn.new { |iNodes, start, level, n|
    if (level == 0) n.name = iNodes[0].name
    var i = start + 1
    while (i < iNodes.count) {
        if (iNodes[i].level == level + 1) {
            var c = NNode.new(iNodes[i].name, [])
            toNest.call(iNodes, i, level+1, c)
            n.children.add(c)
        } else if (iNodes[i].level <= level) return
        i = i + 1
    }
}

var printIndent = Fn.new { |iNodes|
    sw = sw + "\n==Indent form==\n\n"
    for (n in iNodes) sw = sw + Fmt.swrite("$d $s\n", n.level, n.name)
}

var toIndent // recursive
toIndent = Fn.new { |n, level, iNodes|
    iNodes.add(INode.new(level, n.name))
    for (c in n.children) toIndent.call(c, level+1, iNodes)
}

var n1 = NNode.new("RosettaCode", [])
var n2 = NNode.new("rocks", [NNode.new("code", []), NNode.new("comparison", []), NNode.new("wiki", [])])
var n3 = NNode.new("mocks", [NNode.new("trolling", [])])
n1.children.add(n2)
n1.children.add(n3)

printNest.call(n1, 0)
var s1 = sw
System.print(s1)

var iNodes = []
toIndent.call(n1, 0, iNodes)
sw = ""
printIndent.call(iNodes)
System.print(sw)

var n = NNode.new("", [])
toNest.call(iNodes, 0, 0, n)
sw = ""
printNest.call(n, 0)
var s2 = sw
System.print(s2)

System.print("\nRound trip test satisfied? %(s1 == s2)")

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

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") }

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);

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:

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();

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