4
\$\begingroup\$

I recently had cause to write some code which would take an object like

const obj = {
      a: 1,
      c: {
            d: 1,
            e: 1
      }
};

Which we regard as a rooted labelled tree, I then want the rooted labelled subtrees, e.g. in this example

{ c: { e: 1, d: 1 }, a: 1 }
{ c: { e: 1, d: 1 } }
{ c: { e: 1 }, a: 1 }
{ c: { e: 1 } }
{ c: { d: 1 }, a: 1 }
{ c: { d: 1 } }
{ c: {}, a: 1 }
{ c: {} }
{ a: 1 }
{}

It was important to me that the function be a generator function, and that I avoid making any deep copies of the initial object.

So I wrote the following

function* generateRootedSubtreesOfObject(tree) {
      const children = Object.keys(tree);

      if (children.length === 0) {
            yield tree;
            return;
      }

      const firstChild = children[0];
      const firstSubtree = tree[firstChild];

      const isLeaf =
            typeof firstSubtree !== "object" || Array.isArray(firstSubtree);

      delete tree[firstChild];

      for (const remainingSubtree of generateRootedSubtreesOfObject(tree)) {
            const elSubtrees = isLeaf
                  ? [firstSubtree]
                  : generateRootedSubtreesOfObject(firstSubtree);

            for (const firstChildSubtree of elSubtrees) {
                  remainingSubtree[firstChild] = firstChildSubtree;
                  yield remainingSubtree;
                  delete remainingSubtree[firstChild];
            }
            yield remainingSubtree;
      }
      tree[firstChild] = firstSubtree;
}

Which works as desired, but is extremely cryptic in my opinion. The idea is simple enough, go to the first child of the root, find the rooted subtrees with this as the root, and combine this in all the possible ways with the rooted subtrees once you detach this child. But the current implementation I think is too subtle.

How could this be improved?

Re error handling, please assume (it is true in my case) that the caller of this function will know it is appropriate to call.

\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.