Here is a sketch in Scala. Whatever your language is, you first have to represent the tree-like data structure somehow:
sealed trait NestedArray
case class Leaf(arr: Array[Int]) extends NestedArray {
override def toString = arr.mkString("[", ",", "]")
}
case class Node(children: Array[NestedArray]) extends NestedArray {
override def toString =
children
.flatMap(_.toString.split("\n"))
.map(" " + _)
.mkString("[\n", "\n", "\n]")
}
object NestedArray {
def apply(ints: Int*) = Leaf(ints.toArray)
def apply(cs: NestedArray*) = Node(cs.toArray)
}
The only important part is the differentiation between the leaf nodes that hold arrays of integers, and the inner nodes that hold their child-nodes in arrays. The toString methods and extra constructors are not that important, it's mostly just for the little demo below.
Now you essentially want to build an encoder-decoder, where the encode part simply flattens everything, and decode part takes another nested array as argument, and reshapes a flat array into the shape of the nested array. The flattening is very simple:
def encode(a: NestedArray): Array[Int] = a match {
case Leaf(arr) => arr
case Node(cs) => cs flatMap encode
}
The restoring of the structure isn't all that difficult either. I've decided to keep the track of the position in the array by passing around an explicit int-index:
def decode(
shape: NestedArray,
flatArr: Array[Int]
): NestedArray = {
def recHelper(
startIdx: Int,
subshape: NestedArray
): (Int, NestedArray) = subshape match {
case Leaf(a) => {
val n = a.size
val subArray = Array.ofDim[Int](n)
System.arraycopy(flatArr, startIdx, subArray, 0, n)
(startIdx + n, Leaf(subArray))
}
case Node(cs) => {
var idx = startIdx
val childNodes = for (c <- cs) yield {
val (i, a) = recHelper(idx, c)
idx = i
a
}
(idx, Node(childNodes))
}
}
recHelper(0, shape)._2
}
Your example:
val original = NestedArray(
NestedArray(NestedArray(1, 2), NestedArray(3, 4), NestedArray(5, 6)),
NestedArray(NestedArray(7, 8, 9, 10))
)
println(original)
Here is what it looks like as ASCII-tree:
[
[
[1,2]
[3,4]
[5,6]
]
[
[7,8,9,10]
]
]
Now reconstruct a tree of same shape from a different array:
val flatArr = Array(1, 2, 3, 4, 12515, 25125, 12512, 8, 9, 10)
val reconstructed = decode(original, flatArr)
println(reconstructed)
this gives you:
[
[
[1,2]
[3,4]
[12515,25125]
]
[
[12512,8,9,10]
]
]
I hope that should be more or less comprehensible for anyone who does some functional programming in a not-too-remote descendant of ML.
