src/models/tree.ts

   1 // Copyright (C) The Arvados Authors. All rights reserved.
   2 //
   3 // SPDX-License-Identifier: AGPL-3.0
   4
   5 export type Tree<T> = Record<string, TreeNode<T>>;
   6
   7 export const TREE_ROOT_ID = '';
   8
   9 export interface TreeNode<T = any> {
  10     children: string[];
  11     value: T;
  12     id: string;
  13     parent: string;
  14 }
  15
  16 export const createTree = <T>(): Tree<T> => ({});
  17
  18 export const getNode = (id: string) => <T>(tree: Tree<T>): TreeNode<T> | undefined => tree[id];
  19
  20 export const setNode = <T>(node: TreeNode<T>) => (tree: Tree<T>): Tree<T> => {
  21     const [newTree] = [tree]
  22         .map(tree => getNode(node.id)(tree) === node
  23             ? tree
  24             : { ...tree, [node.id]: node })
  25         .map(addChild(node.parent, node.id));
  26     return newTree;
  27 };
  28
  29 export const getNodeValue = (id: string) => <T>(tree: Tree<T>) => {
  30     const node = getNode(id)(tree);
  31     return node ? node.value : undefined;
  32 };
  33
  34 export const setNodeValue = (id: string) => <T>(value: T) => (tree: Tree<T>) => {
  35     const node = getNode(id)(tree);
  36     return node
  37         ? setNode(mapNodeValue(() => value)(node))(tree)
  38         : tree;
  39 };
  40
  41 export const setNodeValueWith = <T>(mapFn: (value: T) => T) => (id: string) => (tree: Tree<T>) => {
  42     const node = getNode(id)(tree);
  43     return node
  44         ? setNode(mapNodeValue(mapFn)(node))(tree)
  45         : tree;
  46 };
  47
  48 export const mapTreeValues = <T, R>(mapFn: (value: T) => R) => (tree: Tree<T>): Tree<R> =>
  49     getNodeDescendantsIds('')(tree)
  50         .map(id => getNode(id)(tree))
  51         .map(mapNodeValue(mapFn))
  52         .reduce((newTree, node) => setNode(node)(newTree), createTree<R>());
  53
  54 export const mapTree = <T, R = T>(mapFn: (node: TreeNode<T>) => TreeNode<R>) => (tree: Tree<T>): Tree<R> =>
  55     getNodeDescendantsIds('')(tree)
  56         .map(id => getNode(id)(tree))
  57         .map(mapFn)
  58         .reduce((newTree, node) => setNode(node)(newTree), createTree<R>());
  59
  60 export const getNodeAncestors = (id: string) => <T>(tree: Tree<T>) =>
  61     mapIdsToNodes(getNodeAncestorsIds(id)(tree))(tree);
  62
  63
  64 export const getNodeAncestorsIds = (id: string) => <T>(tree: Tree<T>): string[] => {
  65     const node = getNode(id)(tree);
  66     return node && node.parent
  67         ? [...getNodeAncestorsIds(node.parent)(tree), node.parent]
  68         : [];
  69 };
  70
  71 export const getNodeDescendants = (id: string, limit = Infinity) => <T>(tree: Tree<T>) =>
  72     mapIdsToNodes(getNodeDescendantsIds(id, limit)(tree))(tree);
  73
  74 export const getNodeDescendantsIds = (id: string, limit = Infinity) => <T>(tree: Tree<T>): string[] => {
  75     const node = getNode(id)(tree);
  76     const children = node ? node.children :
  77         id === TREE_ROOT_ID
  78             ? getRootNodeChildren(tree)
  79             : [];
  80
  81     return children
  82         .concat(limit < 1
  83             ? []
  84             : children
  85                 .map(id => getNodeDescendantsIds(id, limit - 1)(tree))
  86                 .reduce((nodes, nodeChildren) => [...nodes, ...nodeChildren], []));
  87 };
  88
  89 export const getNodeChildren = (id: string) => <T>(tree: Tree<T>) =>
  90     mapIdsToNodes(getNodeChildrenIds(id)(tree))(tree);
  91
  92 export const getNodeChildrenIds = (id: string) => <T>(tree: Tree<T>): string[] =>
  93     getNodeDescendantsIds(id, 0)(tree);
  94
  95 export const mapIdsToNodes = (ids: string[]) => <T>(tree: Tree<T>) =>
  96     ids.map(id => getNode(id)(tree)).filter((node): node is TreeNode<T> => node !== undefined);
  97
  98 const mapNodeValue = <T, R>(mapFn: (value: T) => R) => (node: TreeNode<T>): TreeNode<R> =>
  99     ({ ...node, value: mapFn(node.value) });
 100
 101 const getRootNodeChildren = <T>(tree: Tree<T>) =>
 102     Object
 103         .keys(tree)
 104         .filter(id => getNode(id)(tree)!.parent === TREE_ROOT_ID);
 105
 106 const addChild = (parentId: string, childId: string) => <T>(tree: Tree<T>): Tree<T> => {
 107     const node = getNode(parentId)(tree);
 108     if (node) {
 109         const children = node.children.some(id => id === childId)
 110             ? node.children
 111             : [...node.children, childId];
 112
 113         const newNode = children === node.children
 114             ? node
 115             : { ...node, children };
 116
 117         return setNode(newNode)(tree);
 118     }
 119     return tree;
 120 };