Recursive Data Structures

8. Recursive operations on pairs of quadtrees

We can use multirec to superimpose one quadtree on top of another: Our function will take a pair of quadtrees, using destructuring to extract one called left and the other called right:

const superimposeQuadTrees = multirec({
  indivisible: ({ left, right }) => isString(left),
  value: ({ left, right }) => right ==='⚫️'
                              ? right
                              : left,
  divide: ({ left, right }) => [
      { left: left.ul, right: right.ul },
      { left: left.ur, right: right.ur },
      { left: left.lr, right: right.lr },
      { left: left.ll, right: right.ll }
    ],
  combine: ([ul, ur, lr, ll]) => ({  ul, ur, lr, ll })
});

quadTreeToArray(
  superimposeQuadTrees({
    left: arrayToQuadTree(canvas),
    right: arrayToQuadTree(glider)
  })
)
  //=>
    ([
      ['⚪️', '⚪️', '⚪️', '⚪️'],
      ['⚪️', '⚫️', '⚪️', '⚪️'],
      ['⚫️', '⚪️', '⚪️', '⚫️'],
      ['⚫️', '⚫️', '⚫️', '⚫️']
    ])

Again, this feels like faffing about just so we can be recursive. But we are in position to do something interesting!