Nonconformist Propaganda Machine

    performant-array-to-tree
    TypeScript icon, indicating that this package has built-in type declarations

    1.9.1 • Public • Published

    Performant array to tree

    npm version minified size CircleCI codecov Dependency Status devDependency Status typings included npm license

    Converts an array of items with ids and parent ids to a nested tree in a performant way (time complexity O(n)). Runs in browsers and node.

    Why another package

    Other packages have stricter assumptions or are not as performant, as they often use nested loops or recursion. For example:

    o-unflatten requires the input to be ordered such that parent nodes always come before their children. un-flatten-tree uses 2 nested loops (time complexity O(n^2)).

    This implementation does not require any order of items in the input array and focuses on runtime performance. It is the fastest amongst 4 different packages, you can find the benchmarks here. It uses an index and a single loop (time complexity O(n)). It was inspired by this discussion on StackOverflow.

    Installation

    yarn add performant-array-to-tree

    or if using npm

    npm install --save performant-array-to-tree

    Usage

    const tree = arrayToTree([
      { id: "4", parentId: null, custom: "abc" },
      { id: "31", parentId: "4", custom: "12" },
      { id: "1941", parentId: "418", custom: "de" },
      { id: "1", parentId: "418", custom: "ZZZz" },
      { id: "418", parentId: null, custom: "ü" },
    ]);

    Which results in the following array:

    [
      {
        data: { id: "4", parentId: null, custom: "abc" },
        children: [
          { data: { id: "31", parentId: "4", custom: "12" }, children: [] },
        ],
      },
      {
        data: { id: "418", parentId: null, custom: "ü" },
        children: [
          { data: { id: "1941", parentId: "418", custom: "de" }, children: [] },
          { data: { id: "1", parentId: "418", custom: "ZZZz" }, children: [] },
        ],
      },
    ];

    Configuration

    You can provide a second argument to arrayToTree with configuration options. Right now, you can set the following:

    • id: key of the id field of the item. Also works with nested properties (e. g. "nested.parentId"). Default: "id".
    • parentId: key of the parent's id field of the item. Also works with nested properties (e. g. "nested.parentId"). Default: "parentId".
    • nestedIds: option to enable/disable nested ids. Default: true.
    • childrenField: key which will contain all child nodes of the parent node. Default: "children"
    • dataField: key which will contain all properties/data of the original items. Set to null if you don't want a container. Default: "data"
    • throwIfOrphans: option to throw an error if the array of items contains one or more items that have no parents in the array. This option has a small runtime penalty, so it's disabled by default. When enabled, the function will throw an error containing the parentIds that were not found in the items array. When disabled, the function will just ignore orphans and not add them to the tree. Default: false
    • rootParentIds: object with parent ids as keys and true as values that should be considered the top or root elements of the tree. This is useful when your tree is a subset of full tree, which means there is no item whose parent id is one of undefined, null or ''. The array you pass in will be replace the default value. undefined and null are always considered to be rootParentIds. For more details, see #23. Default: {'': true}

    Example:

    const tree = arrayToTree(
      [
        { num: "4", ref: null, custom: "abc" },
        { num: "31", ref: "4", custom: "12" },
        { num: "1941", ref: "418", custom: "de" },
        { num: "1", ref: "418", custom: "ZZZz" },
        { num: "418", ref: null, custom: "ü" },
      ],
      { id: "num", parentId: "ref", childrenField: "nodes" }
    );

    Which produces:

    [
      {
        data: { num: "4", ref: null, custom: "abc" },
        nodes: [{ data: { num: "31", ref: "4", custom: "12" }, nodes: [] }],
      },
      {
        data: { num: "418", ref: null, custom: "ü" },
        nodes: [
          { data: { num: "1941", ref: "418", custom: "de" }, nodes: [] },
          { data: { num: "1", ref: "418", custom: "ZZZz" }, nodes: [] },
        ],
      },
    ];

    Example with no data field:

    const tree = arrayToTree(
      [
        { id: "4", parentId: null, custom: "abc" },
        { id: "31", parentId: "4", custom: "12" },
        { id: "1941", parentId: "418", custom: "de" },
        { id: "1", parentId: "418", custom: "ZZZz" },
        { id: "418", parentId: null, custom: "ü" },
      ],
      { dataField: null }
    );

    Which produces:

    [
      {
        id: "4",
        parentId: null,
        custom: "abc",
        children: [{ id: "31", parentId: "4", custom: "12", children: [] }],
      },
      {
        id: "418",
        parentId: null,
        custom: "ü",
        children: [
          { id: "1941", parentId: "418", custom: "de", children: [] },
          { id: "1", parentId: "418", custom: "ZZZz", children: [] },
        ],
      },
    ];

    Example with nested id/parentId properties:

    const tree = arrayToTree(
      [
        { num: { id: "4" }, parent: { parentId: null }, custom: "abc" },
        { num: { id: "31" }, parent: { parentId: "4" }, custom: "12" },
      ],
      { id: "num.id", parentId: "parent.parentId" }
    );

    Which produces:

    [
      {
        data: { num: { id: "4" }, parent: { parentId: null }, custom: "abc" },
        children: [
          {
            data: { num: { id: "31" }, parent: { parentId: "4" }, custom: "12" },
            children: [],
          },
        ],
      },
    ];

    TypeScript

    This project includes types, just import the module as usual:

    import { arrayToTree } from "performant-array-to-tree";
    
    const tree = arrayToTree(array);

    Development

    yarn version to create a new version npm login npm publish --access public to publish it to npm

    Install

    npm i performant-array-to-tree

    DownloadsWeekly Downloads

    5,484

    Version

    1.9.1

    License

    MIT

    Unpacked Size

    58.9 kB

    Total Files

    9

    Last publish

    Collaborators

    • avatar