tree-module.js

// 根据 https://www.zhihu.com/question/391388615/answer/1193135808 中的代码重构，
// 以对应所 fork 的工业聚版本

// 和工业聚版本的主要区别：
// - OO 范式而不是 FP 范式（其实像知乎原版那样不用 class 写成 makeTree 函数也是可以的，这里
//   主要是响应工业聚的号召，更「class」一些。但因为是 JS 而不是 TS 写的，就没有再加额外的
//   interface 或 abstract class 了。）
// - Tree 没有弄成 immutable 的。要弄成 immutable 也不是不行，但 OO 范式下处理这类数据结构，
//   通常不会特意弄成 immutable 的，而是在必要的时候提供 clone 方法。
// - 简易起见，没有对 root 节点做额外处理（实际上似乎也不应该做原本格式的数据必然只有一个
//   {parent:null} 的假设，知乎原题也没有这个假设），所以 Tree1 会比工业聚版本多一层节点。

function Tree({createNode, appendChild}) {
  return class {
    constructor(items = []) {
      this._nodes = new Map()
      this.append(...items)
    }
    get root() {
      return this._nodes.get(null)
    }
    append(...items) {
      for (const item of items) {
        const parentNode = getOrCreate(this._nodes, item.parent, createNode)
        const childNode = getOrCreate(this._nodes, item.id, createNode)
        appendChild(parentNode, childNode, item)
      }
    }
  }
}

const Tree0 = Tree({
  createNode() {
    return {}
  },
  appendChild(parentNode, childNode, {id}) {
    parentNode[id] = childNode
  },
})

const Tree1 = Tree({
  createNode(name) {
    return { parent: null, name, children: [] }
  },
  appendChild(parentNode, childNode, {parent}) {
    parentNode.children.push(childNode)
    childNode.parent = parent
  },
})

function getOrCreate(map, key, initializer) {
  if (map.has(key)) return map.get(key)
  const v = initializer(key)
  map.set(key, v)
  return v
}

const categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' },
];

const test = (Tree, name = '') => {
  const tree = new Tree(categories);

  console.log(name, 'tree0', JSON.stringify(tree.root, null, 2));

  tree.append({ id: 'husky', parent: 'dogs' });

  console.log(name, 'tree1', JSON.stringify(tree.root, null, 2));
};

test(Tree0, 'TreeModule0');
console.log('-------------------------------------------')
test(Tree1, 'TreeModule1');

tree-module.ts

// 不用高阶函数，只用传统OOP风格的版本

type Item = { id: string, parent: string | null }

interface Tree<TreeNode> {
  readonly root: TreeNode | null
  append(...items: ReadonlyArray<Item>): void
}

abstract class AbstractTree<TreeNode> implements Tree<TreeNode> {
  private _nodes: Map<string | null, TreeNode> = new Map()
  protected abstract _createNode(name: string | null): TreeNode
  protected abstract _appendChild(parentNode: TreeNode, childNode: TreeNode, item: Item): void
  
  constructor(items: ReadonlyArray<Item>) {
    this.append(...items)
  }
  get root() {
    return this._nodes.get(null) ?? null
  }
  append(...items: ReadonlyArray<Item>) {
    for (const item of items) {
      const parentNode = getOrCreate(this._nodes, item.parent, this._createNode)
      const childNode = getOrCreate(this._nodes, item.id, this._createNode)
      this._appendChild(parentNode, childNode, item)
    }    
  }
}

type TreeNode0 = {
  [childName: string]: TreeNode0
}
class Tree0 extends AbstractTree<TreeNode0> {
  _createNode() {
    return {}
  }
  _appendChild(parentNode: TreeNode0, childNode: TreeNode0, {id}: Item) {
    parentNode[id] = childNode
  }
}

type TreeNode1 = {
  name: string
  parent: string | null
  children: Array<TreeNode1>
}
class Tree1 extends AbstractTree<TreeNode1> {
  _createNode(name: string) {
    return {parent: null, name, children: [] as Array<TreeNode1> }
  }
  _appendChild(parentNode: TreeNode1, childNode: TreeNode1, {parent}: Item) {
    parentNode.children.push(childNode)
    childNode.parent = parent
  }
}

function getOrCreate<K, V>(map: Map<K, V>, key: K, initializer: (key: K) => V) {
  if (map.has(key)) return map.get(key)!
  const v = initializer(key)
  map.set(key, v)
  return v
}


const categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' },
];

function test(Tree: { new (items: ReadonlyArray<Item>): Tree<any> }, name = '') {
  const tree = new Tree(categories);

  console.log(name, 'tree0', '<pre>' + JSON.stringify(tree.root, null, 2) + '</pre>');

  tree.append({ id: 'husky', parent: 'dogs' });

  console.log(name, 'tree1', '<pre>' + JSON.stringify(tree.root, null, 2) + '</pre>');
};

test(Tree0, 'TreeModule0');
console.log('-------------------------------------------')
test(Tree1, 'TreeModule1');

remove class and new

function Tree({ createNode, appendChild }) {
  return (items = []) => {
    let nodes = new Map();

    let append = (...items) => {
      for (const item of items) {
        const parentNode = getOrCreate(nodes, item.parent, createNode);
        const childNode = getOrCreate(nodes, item.id, createNode);
        appendChild(parentNode, childNode, item);
      }
    };

    append(...items);

    return {
      get root() {
        return nodes.get(null);
      },
      append,
    };
  };
}

const Tree0 = Tree({
  createNode() {
    return {};
  },
  appendChild(parentNode, childNode, { id }) {
    parentNode[id] = childNode;
  },
});

const Tree1 = Tree({
  createNode(name) {
    return { parent: null, name, children: [] };
  },
  appendChild(parentNode, childNode, { parent }) {
    parentNode.children.push(childNode);
    childNode.parent = parent;
  },
});

function getOrCreate(map, key, initializer) {
  if (map.has(key)) return map.get(key);
  const v = initializer(key);
  map.set(key, v);
  return v;
}

const categories = [
  { id: 'animals', parent: null },
  { id: 'mammals', parent: 'animals' },
  { id: 'cats', parent: 'mammals' },
  { id: 'dogs', parent: 'mammals' },
  { id: 'chihuahua', parent: 'dogs' },
  { id: 'labrador', parent: 'dogs' },
  { id: 'persian', parent: 'cats' },
  { id: 'siamese', parent: 'cats' },
];

const test = (Tree, name = '') => {
  const tree = Tree(categories);

  console.log(name, 'tree0', JSON.stringify(tree.root, null, 2));

  tree.append({ id: 'husky', parent: 'dogs' });

  console.log(name, 'tree1', JSON.stringify(tree.root, null, 2));
};

test(Tree0, 'TreeModule0');
console.log('-------------------------------------------');
test(Tree1, 'TreeModule1');