tree.test.ts

import {
  createTree,
  deleteFromTreeByCondition,
  findInTreeByCondition,
  flatTree,
  TreeNode,
} from 'lib/tree';

test('create tree', () => {
  const tree = [
    {
      name: 1,
      nameRu: 2,
      children: [
        {
          name: 3,
          nameRu: 4,
          children: [],
        },
      ],
    },
    {
      name: 5,
      nameRu: 6,
      children: [
        {
          name: 7,
          nameRu: 8,
          children: [],
        },
      ],
    },
  ];

  expect(createTree(tree, 'children')).toMatchInlineSnapshot(`
    Array [
      Object {
        "childrens": Array [
          Object {
            "childrens": Array [],
            "value": Object {
              "name": 3,
              "nameRu": 4,
            },
          },
        ],
        "value": Object {
          "name": 1,
          "nameRu": 2,
        },
      },
      Object {
        "childrens": Array [
          Object {
            "childrens": Array [],
            "value": Object {
              "name": 7,
              "nameRu": 8,
            },
          },
        ],
        "value": Object {
          "name": 5,
          "nameRu": 6,
        },
      },
    ]
  `);
});

test('find in tree', () => {
  const tree: TreeNode<number>[] = [
    { childrens: [], value: 1 },
    { childrens: [], value: 2 },
    { childrens: [], value: 3 },
  ];

  expect(findInTreeByCondition(tree, (node) => node === 2))
    .toMatchInlineSnapshot(`
    Object {
      "childrens": Array [],
      "value": 2,
    }
  `);
});

test('find in nest tree', () => {
  const tree = [
    {
      value: { id: '60636de67a0c59656eac9776', name: 'Check', nameRu: 'Чек' },
      childrens: [],
    },
    {
      value: { id: '606395c67a0c59656eac9780', name: 'Test', nameRu: 'Тест' },
      childrens: [
        {
          value: {
            id: '60639cf97a0c59656eac9782',
            name: 'SubCategory',
            nameRu: 'СубКатегория',
          },
          childrens: [],
        },
        {
          value: {
            id: '60639f717a0c59656eac9783',
            name: 'SubCategory2',
            nameRu: 'СубКатегория2',
          },
          childrens: [],
        },
      ],
    },
    {
      value: { id: '606399637a0c59656eac9781', name: 'g', nameRu: 'ghghghghg' },
      childrens: [],
    },
    {
      value: {
        id: '606393b67a0c59656eac977f',
        name: 'аарарар',
        nameRu: 'арар',
      },
      childrens: [],
    },
  ];

  expect(
    findInTreeByCondition(
      tree,
      (node) => node.id === '60639cf97a0c59656eac9782'
    )
  ).toMatchInlineSnapshot(`
    Object {
      "childrens": Array [],
      "value": Object {
        "id": "60639cf97a0c59656eac9782",
        "name": "SubCategory",
        "nameRu": "СубКатегория",
      },
    }
  `);
});

test('remove from tree', () => {
  const tree: TreeNode<number>[] = [
    { childrens: [], value: 1 },
    { childrens: [], value: 2 },
    { childrens: [], value: 3 },
  ];

  expect(deleteFromTreeByCondition(tree, (node) => node === 2))
    .toMatchInlineSnapshot(`
    Array [
      Object {
        "childrens": Array [],
        "value": 1,
      },
      Object {
        "childrens": Array [],
        "value": 3,
      },
    ]
  `);
});

test('remove from nest tree', () => {
  const tree: TreeNode<number> = {
    childrens: [{ childrens: [{ childrens: [], value: 3 }], value: 2 }],
    value: 1,
  };
  expect(deleteFromTreeByCondition(tree, (node) => node === 3))
    .toMatchInlineSnapshot(`
    Object {
      "childrens": Array [
        Object {
          "childrens": Array [],
          "value": 2,
        },
      ],
      "value": 1,
    }
  `);
});

test('flat tree', () => {
  const tree: TreeNode<number>[] = [
    {
      childrens: [{ childrens: [{ childrens: [], value: 3 }], value: 2 }],
      value: 1,
    },
    {
      childrens: [{ childrens: [{ childrens: [], value: 6 }], value: 5 }],
      value: 4,
    },
  ];
  expect(flatTree(tree)).toMatchInlineSnapshot(`
    Array [
      1,
      2,
      3,
      4,
      5,
      6,
    ]
  `);
});

tree.ts

export type TreeNode<T> = {
  value: T;
  childrens: TreeNode<T>[];
};

export const createTree = <T, P extends keyof T>(
  root: T[] | T,
  childPropertyName: P
): TreeNode<Omit<T, P>>[] => {
  const arrayedTree = Array.isArray(root) ? root : [root];

  const tree: TreeNode<Omit<T, P>>[] = [];
  for (const node of arrayedTree) {
    const nodeChilds = (node[childPropertyName] as unknown) as T[];

    let childrens: TreeNode<Omit<T, P>>[] = [];

    if (nodeChilds.length > 0) {
      childrens = createTree(nodeChilds, childPropertyName);
    }

    const keys = Object.keys(node).filter((key) => key !== childPropertyName);

    const value: Omit<T, P> = {} as Omit<T, P>;

    for (const key of keys) {
      // @ts-ignore
      value[key] = node[key];
    }
    tree.push({
      value,
      childrens,
    });
  }
  return tree;
};

export const findInTreeByCondition = <T>(
  root: TreeNode<T>[] | TreeNode<T>,
  condition: (node: T) => boolean
): TreeNode<T> | null => {
  const arrayedTree = Array.isArray(root) ? root : [root];

  let foundedNode: TreeNode<T> | null = null;
  for (const node of arrayedTree) {
    if (condition(node.value)) {
      foundedNode = node;
      break;
    }
    foundedNode = findInTreeByCondition(node.childrens, condition);
    if (foundedNode) break;
  }

  return foundedNode;
};

/* export const moveChildren = <T, P extends keyof T>(
  root: TreeNode<T>[] | TreeNode<T>,
  property: P,
  from: T[P],
  to: T[P]
) => {
  const arrayedTree = Array.isArray(root) ? root : [root];

  let foundedNode: TreeNode<T> | null = null;
  let moveToNode: TreeNode<T> | null = null;

  for (const node of arrayedTree) {
    if (!foundedNode) {
      if (node.value[property] === from) {
        foundedNode = node;
      } else {
        foundedNode = findInTreeByCondition(
          node.childrens,
          (value) => value[property] === from
        );
        node.childrens = node.childrens.filter((node) => node !== foundedNode);
      }
    }

    if (!moveToNode) {
      if (node.value[property] === to) {
        moveToNode = node;
      } else {
        moveToNode = findInTreeByCondition(
          node.childrens,
          (value) => value[property] === to
        );
      }
    }

    if (foundedNode && moveToNode) {
      moveToNode?.childrens.push(foundedNode);
    }
  }

  return Array.isArray(root) ? [...root] : { ...root };
}; */

export function deleteFromTreeByCondition<T>(
  root: TreeNode<T>,
  condition: (node: T) => boolean
): TreeNode<T>;
export function deleteFromTreeByCondition<T>(
  root: TreeNode<T>[],
  condition: (node: T) => boolean
): TreeNode<T>[];

export function deleteFromTreeByCondition<T>(
  root: TreeNode<T>[] | TreeNode<T>,
  condition: (node: T) => boolean
): TreeNode<T>[] | TreeNode<T> {
  const arrayedTree = Array.isArray(root) ? root : [root];

  for (let i = 0; i < arrayedTree.length; i += 1) {
    if (condition(arrayedTree[i].value)) {
      arrayedTree.splice(i, 1);
    } else {
      deleteFromTreeByCondition(arrayedTree[i].childrens, condition);
    }
  }

  return Array.isArray(root) ? [...root] : { ...root };
}

export const flatTree = <T>(root: TreeNode<T>[] | TreeNode<T>): T[] => {
  const arrayedTree = Array.isArray(root) ? root : [root];

  return arrayedTree
    .map((node) => {
      const nodes = [node.value];
      if (node.childrens.length > 0) {
        nodes.push(...flatTree(node.childrens));
      }
      return nodes;
    })
    .flat();
};