Higher-level tree operations

One extremely useful aspect of tree-based development is that we can define higher-level operations on trees that solve general problems.

In the previous step, we combined several trees backed by different data representations into a single tree with several branches.

In some cases, it’s useful to merge two or more trees together to create a single tree. Let’s solve that general problem by creating a higher-level tree that merges multiple trees together.

MergeTree class

We’ll start creating a MergeTree class whose constructor accepts multiple trees.

/* src/merge/MergeTree.js */

export default class MergeTree {
  constructor(...trees) {
    this.trees = trees;
  }

  async keys() {
    /* TODO */
  }

  async get(key) {
    /* TODO */
  }
}

The keys will return all the keys in all of the supplied trees. We can use a Set to de-duplicate the keys.

  async keys() {
    const keys = new Set();
    for (const tree of this.trees) {
      for await (const key of tree) {
        keys.add(key);
      }
    }
    return keys;
  }

The get method looks in each of the trees in turn, returning the first defined value from any of the trees.

  async get(key) {
    const subtrees = [];
    for (const tree of this.trees) {
      const value = await tree.get(key);

      const isAsyncDictionary =
        typeof value?.get === "function" &&
        typeof value?.keys === "function";

      if (value !== undefined) {
        if (isAsyncDictionary) {
          subtrees.push(value);
        } else {
          return value;
        }
      }
    }

    return subtrees.length === 0
      ? undefined
      : subtrees.length === 1
      ? subtrees[0]
      : new this.constructor(...subtrees);
  }

We also take care to handle the case where multiple trees define async subtrees for the same key. In that case, we collect the subtrees and wrap them in a new MergeTree instance. This implements a deep merge operation.

Use MergeTree to define the site

We can update our site tree to use this new higher-level MergeTree operation.

/* src/merge/SiteTree.js */

We apply our indexPages transform to give the merged tree index pages.

The site is now the deep merge of all three trees: