# Recursive Data Structures

## 6. Separation of concerns

But back to our code. All we've done so far is moved the "faffing about" out of our code and we're doing it by hand. That's bad: we don't want to retrain our eyes to read quadtrees instead of flat arrays, and we don't want to sit at a computer all day manually translating quadtrees to flat arrays and back.

If only we could write some code to do it for us… Some recursive code…

Here's a function that recursively turns a two-dimensional array into a quadtree:

const isOneByOneArray = (something) =>
Array.isArray(something) && something.length === 1 &&
Array.isArray(something[0]) && something[0].length === 1;

const contentsOfOneByOneArray = (array) => array[0][0];

const regionsToQuadTree = ([ul, ur, lr, ll]) =>
({ ul, ur, lr, ll });

indivisible: isOneByOneArray,
value: contentsOfOneByOneArray,
divide: divideSquareIntoRegions,
});

['⚪️', '⚪️', '⚪️', '⚪️'],
['⚪️', '⚫️', '⚪️', '⚪️'],
['⚫️', '⚪️', '⚪️', '⚪️'],
['⚫️', '⚫️', '⚫️', '⚪️']
])
//=>
({
ul:  { ul: "⚪️", ur: "⚪️", lr: "⚫️", ll: "⚪️" },
ur:  { ul: "⚪️", ur: "⚪️", lr: "⚪️", ll: "⚪️" },
lr:  { ul: "⚪️", ur: "⚪️", lr: "⚪️", ll: "⚫️" },
ll:  { ul: "⚫️", ur: "⚪️", lr: "⚫️", ll: "⚫️" }
})

Naturally, we can also write a function to convert quadtrees back into two-dimensional arrays again:

const isSmallestActualSquare = (square) => isString(square.ul);

const asTwoDimensionalArray = ({ ul, ur, lr, ll }) =>
[[ul, ur], [ll, lr]];

const regions = ({ ul, ur, lr, ll }) =>
[ul, ur, lr, ll];

const combineFlatArrays = ([upperLeft, upperRight, lowerRight, lowerLeft]) => {
const upperHalf = [...zipWith(concat, upperLeft, upperRight)];
const lowerHalf = [...zipWith(concat, lowerLeft, lowerRight)];

return concat(upperHalf, lowerHalf);
}

indivisible: isSmallestActualSquare,
value: asTwoDimensionalArray,
divide: regions,
combine: combineFlatArrays
});

['⚪️', '⚪️', '⚪️', '⚪️'],
['⚪️', '⚫️', '⚪️', '⚪️'],
['⚫️', '⚪️', '⚪️', '⚪️'],
['⚫️', '⚫️', '⚫️', '⚪️']
])
)
//=>
([
["⚪️", "⚪️", "⚪️", "⚪️"],
["⚪️", "⚫️", "⚪️", "⚪️"],
["⚫️", "⚪️", "⚪️", "⚪️"],
["⚫️", "⚫️", "⚫️", "⚪️"]
])

And thus, we can take a two-dimensional array, turn it into a quadtree, rotate the quadtree, and convert it back to a two-dimensional array again:

quadTreeToArray(
['⚪️', '⚪️', '⚪️', '⚪️'],
['⚪️', '⚫️', '⚪️', '⚪️'],
['⚫️', '⚪️', '⚪️', '⚪️'],
['⚫️', '⚫️', '⚫️', '⚪️']
])
)
)
//=>
([
["⚫️", "⚫️", "⚪️", "⚪️"],
["⚫️", "⚪️", "⚫️", "⚪️"],
["⚫️", "⚪️", "⚪️", "⚪️"],
["⚪️", "⚪️", "⚪️", "⚪️"]
])