Skip to content

Instantly share code, notes, and snippets.

@hax
Forked from Lucifier129/tree-module.js
Last active May 3, 2020 06:19
Show Gist options
  • Save hax/9ca59fef3e57a33295a755ada60ef465 to your computer and use it in GitHub Desktop.
Save hax/9ca59fef3e57a33295a755ada60ef465 to your computer and use it in GitHub Desktop.
// 根据 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');
// 不用高阶函数,只用传统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');
@Lucifier129
Copy link

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');

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment