# Tree from nesting levels

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

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]`

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.