# Tree from nesting levels

*is a*

**Tree from nesting levels****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.

Given a flat list of integers greater than zero, representing object nesting
levels, e.g. `[1, 2, 4]`

,
generate a tree formed from nested lists of those nesting level integers where:

- Every int appears, in order, at its depth of nesting.
- If the next level int is greater than the previous then it appears in a sub-list of the list containing the previous item

The generated tree datastructure should ideally be in a languages nested list format that can be used for further calculations rather than something just calculated for printing.

An input of `[1, 2, 4]`

should produce the equivalent of: `[1, [2, [[4]]]]`

where 1 is at depth1, 2 is two deep and 4 is nested 4 deep.

`[1, 2, 4, 2, 2, 1]`

should produce `[1, [2, [[4]], 2, 2], 1]`

.

All the nesting integers are in the same order but at the correct nesting
levels.

Similarly `[3, 1, 3, 1]`

should generate `[[[3]], 1, [[3]], 1]`

- Task

Generate and show here the results for the following inputs:

`[]`

`[1, 2, 4]`

`[3, 1, 3, 1]`

`[1, 2, 3, 1]`

`[3, 2, 1, 3]`

`[3, 3, 3, 1, 1, 3, 3, 3]`

## Julia

<lang julia>function makenested(list)

isempty(list) && return list nesting = 0 str = "" for n in list if n > nesting str *= "["^(n - nesting) nesting = n elseif n < nesting str *= "]"^(nesting - n) * ", " nesting = n end str *= "$n, " end str *= "]"^nesting replace(str, s"\, \]" => "]") return eval(Meta.parse(str))

end

for test in [[], [1, 2, 4], [3, 1, 3, 1], [1, 2, 3, 1], [3, 2, 1, 3], [3, 3, 3, 1, 1, 3, 3, 3]]

result = "$test => $(makenested(test))" println(replace(result, "Any" => ""))

end

</lang>- Output:

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

## Phix

I was thinking along the same lines but admit I had a little peek at the (recursive) python solution.. <lang Phix>constant tests = {{},

{1, 2, 4},

-- {1, 2, 4, 2, 2, 1}, -- (fine too)

{3, 1, 3, 1}, {1, 2, 3, 1}, {3, 2, 1, 3}, {3, 3, 3, 1, 1, 3, 3, 3}}

function test(sequence s, integer level=1, idx=1)

sequence res = {}, part while idx<=length(s) do switch compare(s[idx],level) do case +1: {idx,part} = test(s,level+1,idx) res = append(res,part) case 0: res &= s[idx] case -1: idx -=1 exit end switch idx += 1 end while return iff(level=1?res:{idx,res})

end function

for i=1 to length(tests) do

sequence ti = tests[i], res = test(ti), rpp = ppf(res,{pp_Nest,3,pp_Indent,4}) printf(1,"%v nests to %v\n or %s\n",{ti,res,rpp})

end for</lang>

- Output:

{} nests to {} or {} {1,2,4} nests to {1,{2,{{4}}}} or {1, {2, {{4}}}} {3,1,3,1} nests to {{{3}},1,{{3}},1} or {{{3}}, 1, {{3}}, 1} {1,2,3,1} nests to {1,{2,{3}},1} or {1, {2, {3}}, 1} {3,2,1,3} nests to {{{3},2},1,{{3}}} or {{{3}, 2}, 1, {{3}}} {3,3,3,1,1,3,3,3} nests to {{{3,3,3}},1,1,{{3,3,3}}} or {{{3, 3, 3}}, 1, 1, {{3, 3, 3}}}

## Python

### Python: Recursive

<lang python>def to_tree(x, index=0, depth=1):

so_far = [] while index < len(x): this = x[index] if this == depth: so_far.append(this) elif this > depth: index, deeper = to_tree(x, index, depth + 1) so_far.append(deeper) else: # this < depth: index -=1 break index += 1 return (index, so_far) if depth > 1 else so_far

if __name__ == "__main__":

from pprint import pformat

def pnest(nest:list, width: int=9) -> str: text = pformat(nest, width=width).replace('\n', '\n ') print(f" OR {text}\n")

exercises = [ [], [1, 2, 4], [3, 1, 3, 1], [1, 2, 3, 1], [3, 2, 1, 3], [3, 3, 3, 1, 1, 3, 3, 3], ] for flat in exercises: nest = to_tree(flat) print(f"{flat} NESTS TO: {nest}") pnest(nest)</lang>

- Output:

[] NESTS TO: [] OR [] [1, 2, 4] NESTS TO: [1, [2, [[4]]]] OR [1, [2, [[4]]]] [3, 1, 3, 1] NESTS TO: [[[3]], 1, [[3]], 1] OR [[[3]], 1, [[3]], 1] [1, 2, 3, 1] NESTS TO: [1, [2, [3]], 1] OR [1, [2, [3]], 1] [3, 2, 1, 3] NESTS TO: [[[3], 2], 1, [[3]]] OR [[[3], 2], 1, [[3]]] [3, 3, 3, 1, 1, 3, 3, 3] NESTS TO: [[[3, 3, 3]], 1, 1, [[3, 3, 3]]] OR [[[3, 3, 3]], 1, 1, [[3, 3, 3]]]

### Python: Iterative

<lang python>def to_tree(x: list) -> list:

nested = [] stack = [nested] for this in x: while this != len(stack): if this > len(stack): innermost = [] # new level stack[-1].append(innermost) # nest it stack.append(innermost) # push it else: # this < stack: stack.pop(-1) stack[-1].append(this)

return nested

</lang>

- Output:

Using the same main block it produces the same output as the recursive case above.