Skip to content

Instantly share code, notes, and snippets.

@Lucifier129

Lucifier129/tree-module.js

Created May 1, 2020 13:50
Show Gist options
  • Save Lucifier129/14a7fa78259f32face8fe24eb4e9c4d1 to your computer and use it in GitHub Desktop.
Save Lucifier129/14a7fa78259f32face8fe24eb4e9c4d1 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
tree-module.js
const createTreeModule = (operations) => {
const append = (tree, node) => {
if (operations.matchChild(tree, node)) {
return operations.appendChild(tree, node);
}
return operations.map(tree, (child) => {
return append(child, node);
});
};
const fromList = (list) => {
return list.reduce((tree, item) => {
return append(tree, operations.itemToNode(item));
}, operations.createRoot());
};
return {
...operations,
fromList,
append,
};
};
const TreeModule0 = createTreeModule({
createRoot: () => {
return {};
},
itemToNode: (item) => {
return item;
},
map: (node, f) => {
let newNode = {};
for (let key in node) {
newNode[key] = f(node[key]);
}
return newNode;
},
matchChild: (tree, node) => {
if (node.parent === null) return true;
return tree.hasOwnProperty(node.parent);
},
appendChild: (tree, node) => {
if (node.parent === null) {
return {
...tree,
[node.id]: {},
};
}
return {
...tree,
[node.parent]: {
...tree[node.parent],
[node.id]: {},
},
};
},
});
const TreeModule1 = createTreeModule({
createRoot: () => {
return {
parent: null,
name: '',
children: [],
};
},
itemToNode: (item) => {
return {
parent: item.parent,
name: item.id,
children: [],
};
},
map: (node, f) => {
return {
...node,
children: node.children.map(f),
};
},
matchChild: (tree, node) => {
if (node.parent === null) return true;
return node.parent === tree.name;
},
appendChild: (tree, node) => {
if (node.parent === null) return node;
return {
...tree,
children: [...tree.children, node],
};
},
});
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 = (TreeModule, name = '') => {
const tree0 = TreeModule.fromList(categories);
console.log(name, 'tree0', JSON.stringify(tree0, null, 2));
const tree1 = TreeModule.append(
tree0,
TreeModule.itemToNode({ id: 'husky', parent: 'dogs' })
);
console.log(name, 'tree1', JSON.stringify(tree1, null, 2));
};
test(TreeModule0, 'TreeModule0');
console.log('-------------------------------------------')
test(TreeModule1, 'TreeModule1');
@Lucifier129
Copy link
Author

Lucifier129 commented May 2, 2020 •
edited
Loading

OO style

class AbstractTree {
  constructor(id = null) {
    this.id = id;
    this.children = [];
  }
  create(...args) {
    return new this.constructor(...args);
  }
  isRoot() {
    return this.id === null;
  }
  getArgsFromItem() {
    throw new Error(`getArgsFromItem is not implemented`);
  }
  matchItem() {
    throw new Error(`matchItem is not implemented`);
  }
  appendNode(node) {
    this.children.push(node);
  }
  append(...items) {
    let unmatchItems = [];

    for (let i = 0; i < items.length; i++) {
      let item = items[i];
      if (this.matchItem(item)) {
        let args = this.getArgsFromItem(item);
        this.appendNode(this.create(...args));
      } else {
        unmatchItems.push(item);
      }
    }

    for (let i = 0; i < this.children.length; i++) {
      if (unmatchItems.length === 0) break;
      unmatchItems = this.children[i].append(...unmatchItems);
    }

    return unmatchItems;
  }
}

class CategoryTree extends AbstractTree {
  matchItem(item) {
    return item.parent === this.id;
  }
  getArgsFromItem(item) {
    return [item.id];
  }
}

class Tree0 extends CategoryTree {
  toJSON() {
    let json = {};

    for (let i = 0; i < this.children.length; i++) {
      Object.assign(json, this.children[i].toJSON());
    }

    if (this.isRoot()) return json;

    return {
      [this.id]: json,
    };
  }
}

class Tree1 extends CategoryTree {
  toJSON() {
    let children = [];

    for (let i = 0; i < this.children.length; i++) {
      children.push({
        parent: this.id,
        ...this.children[i].toJSON(),
      });
    }

    return {
      id: this.id,
      children,
    };
  }
}

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 = (Tree0, name = '') => {
  const tree = new Tree0();

  tree.append(...categories);

  console.log(name, JSON.stringify(tree.toJSON(), null, 2));

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

  console.log(name, JSON.stringify(tree.toJSON(), null, 2));
};

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

@Lucifier129
Copy link
Author

codata style

const Tree = (value, ...children) => (visitor) => {
  return visitor.walk(value, ...children);
};

const mapTree = (tree, f) => (visitor) => {
  return tree({
    walk: (value, ...children) => {
      let mappedChildren = children.map((child) => mapTree(child, f));
      return visitor.walk(f(value), ...mappedChildren);
    },
  });
};

const foldTree = (tree, f, initValue) => {
  return tree({
    walk: (value, ...children) => {
      let accValue = children.reduce(
        (value, child) => foldTree(child, f, value),
        initValue
      );
      return f(accValue, value);
    },
  });
};

const countTree = (tree) => {
  return foldTree(tree, (sum, _) => sum + 1, 0);
};

const toJSON = (tree) =>
  tree({
    walk: (value, ...children) => {
      return {
        value,
        children: children.map(toJSON),
      };
    },
  });

const toCategoryTree = (list = [], value = null) => {
  let children = list
    .filter((item) => item.parent === value)
    .map((item) => toCategoryTree(list, item.id));
  return Tree(value, ...children);
};

const appendToCategoryTree = (tree, item) => {
  return tree({
    walk: (value, ...children) => {
      if (item.parent === value) {
        return Tree(value, ...children, Tree(item.id));
      } else {
        return Tree(
          value,
          ...children.map((child) => appendToCategoryTree(child, item))
        );
      }
    },
  });
};

const toInlineJSON = (tree) => {
  return tree({
    walk: (value, ...children) => {
      let json = children.reduce((json, child) => {
        return {
          ...json,
          ...toInlineJSON(child),
        };
      }, {});
      if (value === null) return json;
      return {
        [value]: json,
      };
    },
  });
};

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' },
];

let tree0 = Tree(0, Tree(1), Tree(2, Tree(3), Tree(4)));

let tree1 = mapTree(tree0, (value) => `count: ${value}`);

let categoryTree0 = toCategoryTree(categories);
let categoryTree1 = appendToCategoryTree(categoryTree0, {
  id: 'husky',
  parent: 'dogs',
});

console.log('tree0', JSON.stringify(toJSON(tree0), null, 2));
console.log('tree1', JSON.stringify(toJSON(tree1), null, 2));
console.log('count', countTree(tree0));

console.log(
  'categoryTree0-json',
  JSON.stringify(toJSON(categoryTree0), null, 2)
);

console.log(
  'categoryTree1-json',
  JSON.stringify(toJSON(categoryTree1), null, 2)
);

console.log(
  'categoryTree0-inline-json',
  JSON.stringify(toInlineJSON(categoryTree0), null, 2)
);

console.log(
  'categoryTree1-inline-json',
  JSON.stringify(toInlineJSON(categoryTree1), null, 2)
);

console.log('categoryTree0-count', countTree(categoryTree0));
console.log('categoryTree1-count', countTree(categoryTree1));

@Lucifier129
Copy link
Author

codata in typescript

interface TreeVisitor<T, TT> {
  walk: (value: T, ...children: Tree<T>[]) => TT;
}

interface Tree<T> {
  <TT>(visitor: TreeVisitor<T, TT>): TT;
}

const Tree = <T>(value: T, ...children: Tree<T>[]): Tree<T> => {
  return (visitor) => {
    return visitor.walk(value, ...children);
  };
};
const mapTree = <T, TT>(tree: Tree<T>, f: (a: T) => TT): Tree<TT> => {
  return (visitor) => {
    return tree({
      walk: (value, ...children) => {
        let mappedChildren = children.map((child) => mapTree(child, f));
        return visitor.walk(f(value), ...mappedChildren);
      },
    });
  };
};

const foldTree = <T, A>(tree: Tree<T>, f: (A, T) => A, initValue: A): A => {
  return tree({
    walk: (value, ...children) => {
      let accValue = children.reduce(
        (value, child) => foldTree(child, f, value),
        initValue
      );
      return f(accValue, value);
    },
  });
};

const countTree = <T>(tree: Tree<T>): number => {
  return foldTree(tree, (sum, _) => sum + 1, 0);
};

type TreeJSON<T> = {
  value: T;
  children: TreeJSON<T>[];
};

const toJSON = <T>(tree: Tree<T>): TreeJSON<T> =>
  tree({
    walk: (value, ...children) => {
      return {
        value,
        children: children.map(toJSON),
      };
    },
  });

type Category = {
  id: string;
  parent: string | null;
};

type Categories = Category[];

type CategoryTree = Tree<string | null>;

const toCategoryTree = (list: Categories = [], value = null): CategoryTree => {
  let children = list
    .filter((item) => item.parent === value)
    .map((item) => toCategoryTree(list, item.id));
  return Tree(value, ...children);
};

const appendToCategoryTree = (
  tree: CategoryTree,
  item: Category
): CategoryTree => {
  return tree({
    walk: (value, ...children) => {
      if (item.parent === value) {
        return Tree(value, ...children, Tree(item.id));
      } else {
        return Tree(
          value,
          ...children.map((child) => appendToCategoryTree(child, item))
        );
      }
    },
  });
};

type InlineJSON = {
  [key: string]: InlineJSON | {};
};

const toInlineJSON = (tree: CategoryTree): InlineJSON => {
  return tree({
    walk: (value, ...children) => {
      let json = children.reduce((json, child) => {
        return {
          ...json,
          ...toInlineJSON(child),
        };
      }, {});
      if (value === null) return json;
      return {
        [value]: json,
      };
    },
  });
};

const categories: 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' },
];

let tree0 = Tree(0, Tree(1), Tree(2, Tree(3), Tree(4)));

let tree1 = mapTree(tree0, (value) => `count: ${value}`);

let categoryTree0 = toCategoryTree(categories);
let categoryTree1 = appendToCategoryTree(categoryTree0, {
  id: 'husky',
  parent: 'dogs',
});

console.log('tree0', JSON.stringify(toJSON(tree0), null, 2));
console.log('tree1', JSON.stringify(toJSON(tree1), null, 2));
console.log('count', countTree(tree0));

console.log(
  'categoryTree0-json',
  JSON.stringify(toJSON(categoryTree0), null, 2)
);

console.log(
  'categoryTree1-json',
  JSON.stringify(toJSON(categoryTree1), null, 2)
);

console.log(
  'categoryTree0-inline-json',
  JSON.stringify(toInlineJSON(categoryTree0), null, 2)
);

console.log(
  'categoryTree1-inline-json',
  JSON.stringify(toInlineJSON(categoryTree1), null, 2)
);

console.log('categoryTree0-count', countTree(categoryTree0));
console.log('categoryTree1-count', countTree(categoryTree1));

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