npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

fast-tree-builder

v1.0.0-alpha.2

Published

Efficiently construct highly customizable bi-directional tree structures from iterable data.

Downloads

52

Readme

fast-tree-builder

Build Status Coverage Status npms.io (quality) Maintenance

fast-tree-builder is an npm package that allows you to efficiently build trees from iterable data structures. With its optimized algorithm, strong TypeScript typings, and customizable node structure, it provides a reliable solution for organizing and manipulating hierarchical data.

Prerequisites

  • You have a list of items,
  • where each item is identifiable by a unique value,
  • and the items are connected via a parent OR a childred relation.

Features

  • Efficient Tree Building: The package utilizes an optimized algorithm to construct trees efficiently in O(n) time, while maintaining good performance.

  • Bi-Directional Tree Traversal: Traverse the built tree in both directions, enabling easy navigation between parent and child nodes.

  • Robust TypeScript Type Definitions: Leverage type safety through extensive TypeScript type definitions. The package includes precise type annotations to improve code reliability and developer workflow.

  • Fully Customizable Node Structure: Tailor the structure of the nodes in the built tree to meet your specific requirements. You have the freedom to define data, parent, and children key names according to your application's needs. To avoid circular references, parent links can be turned off which helps generating JSON data.

  • Works on Any Iterable Data: Designed to handle arrays, sets, and other iterable data structures efficiently, ensuring broad applicability.

  • No Sorting Required: The algorithm does not require your input data to be sorted, saving you preprocessing time and effort.

  • Flexible Key and Parent Key Types: You can use any JavaScript value for identifying items. Relations checked with strict (childKey === parentKey) comparison.

  • Multiple Root Nodes: Can efficiently construct trees with multiple root nodes, accommodating scenarios that necessitate distinct, separate tree structures within the same dataset.

  • Map of Nodes: Beside the root nodes you can retrieve a Map object containing the nodes of the built tree, enabling easy entry on any point of the tree.

  • Support for Parent Key Validation: Enables you to validate parent keys while building the tree. When a node missing its parent, an error will be thrown.

  • Support for Tree Validation: Ensures the recieved data structure is an acyclic graph.

Installation

To install fast-tree-builder, use npm:

npm install fast-tree-builder

or

yarn add fast-tree-builder

Usage

Here are some examples showcasing the usage of fast-tree-builder and their expected outputs:

Example 1: Basic Tree Building

import buildTree from 'fast-tree-builder';
// OR
const { default: buildTree } = require('fast-tree-builder');

const items = [
  { id: 1, parent: null, name: 'Root 1' },
  { id: 2, parent: null, name: 'Root 2' },
  { id: 3, parent: 1, name: 'Child 1.1' },
  { id: 4, parent: 1, name: 'Child 1.2' },
  { id: 5, parent: 2, name: 'Child 2.1' },
];

const { roots, nodes } = buildTree(items, {
  // the input items:
  key: 'id',
  parentKey: 'parent',
  // the built node:
  nodeDataKey: 'data',
  nodeParentKey: 'parent',
  nodeChildrenKey: 'children',
});

console.log(roots[0].data.name);
// Expected output: Root 1

console.log(roots[0].children[1].data.name);
// Expected output: Child 1.2

console.log(roots[0].children[1].parent.data.name);
// Expected output: Root 1

console.log(roots);
// Expected output: [
//   { data: { id: 1, parent: null, name: 'Root 1' }, children: [
//     { data: { id: 3, parent: 1, name: 'Child 1.1' }, parent: { ... } },
//     { data: { id: 4, parent: 1, name: 'Child 1.2' }, parent: { ... } }
//   ] },
//   { data: { id: 2, parent: null, name: 'Root 2' }, children: [
//     { data: { id: 5, parent: 2, name: 'Child 2.1' }, parent: { ... } }
//   ] }
// ]

console.log(nodes);
// Expected output: Map {
//   1 => { data: { id: 1, parent: null, name: 'Root 1' }, children: [
//     { data: { id: 3, parent: 1, name: 'Child 1.1' }, parent: { ... } },
//     { data: { id: 4, parent: 1, name: 'Child 1.2' }, parent: { ... } }
//   ] },
//   2 => { data: { id: 2, parent: null, name: 'Root 2' }, children: [
//     { data: { id: 5, parent: 2, name: 'Child 2.1' }, parent: { ... } }
//   ] },
//   3 => { data: { id: 3, parent: 1, name: 'Child 1.1' }, parent: { ... } },
//   4 => { data: { id: 4, parent: 1, name: 'Child 1.2' }, parent: { ... } },
//   5 => { data: { id: 5, parent: 2, name: 'Child 2.1' }, parent: { ... } }
// }

Example 2: Build tree by children

import buildTree from 'fast-tree-builder';

const items = [
  { id: 1, children: [3, 4], name: 'Root 1' },
  { id: 2, children: [5], name: 'Root 2' },
  { id: 3, name: 'Child 1.1' },
  { id: 4, name: 'Child 1.2' },
  { id: 5, name: 'Child 2.1' },
];

const { roots, nodes } = buildTree(items, {
  mode: 'children'
});

Produces the same output as Example 1.

Example 3: Customized Node Structure

import buildTree from 'fast-tree-builder';

const items = [
  { key: { n: 1 }, parentKey: null, name: 'Root 1' },
  { key: { n: 2 }, parentKey: null, name: 'Root 2' },
  { key: { n: 3 }, parentKey: { n: 1 }, name: 'Child 1.1' },
  { key: { n: 4 }, parentKey: { n: 1 }, name: 'Child 1.2' },
  { key: { n: 5 }, parentKey: { n: 2 }, name: 'Child 2.1' },
];

const { roots, nodes } = buildTree(items, {
  key(item) { return item.key?.n; },
  parentKey(item) { return item.parentKey?.n; },
  nodeDataKey: false, // merge item data into node
  nodeParentKey: 'up',
  nodeChildrenKey: 'down',
  mapNodeData(item) { return { title: item.name }; },
});

console.log(roots[0].title);
// Expected output: Root 1

console.log(roots[0].down[1].title);
// Expected output: Child 1.2

console.log(roots[0].down[1].up.title);
// Expected output: Root 1

console.log(roots);
// Expected output: [
//   { title: 'Root 1', down: [
//     { title: 'Child 1.1', up: { ... } },
//     { title: 'Child 1.2', up: { ... } }
//   ] },
//   { title: 'Root 2', down: [
//     { title: 'Child 2.1', up: { ... } }
//   ] }
// ]

console.log(nodes);
// Expected output: Map {
//   1 => { title: 'Root 1', down: [
//     { title: 'Child 1.1', up: { ... } },
//     { title: 'Child 1.2', up: { ... } }
//   ] },
//   2 => { title: 'Root 2', down: [
//     { title: 'Child 2.1', up: { ... } }
//   ] },
//   3 => { title: 'Child 1.1', up: { ... } },
//   4 => { title: 'Child 1.2', up: { ... } },
//   5 => { title: 'Child 2.1', up: { ... } }
// }

Example 4: Crazy ideas

import buildTree from 'fast-tree-builder';

const items = [
  '0001Root 1',
  '0002Root 2',
  '0103Child 1.1',
  '0104Child 1.2',
  '0205Child 2.1',
];

const { roots, nodes } = buildTree(items, {
  key(item) { return item.substring(2, 4); },
  parentKey(item) { return item.substring(0, 2); },
  mapNodeData(item) { return { name: item.substring(4) }; },
  nodeDataKey: false, // merge item data into node
});

console.log(roots[0].name);
// Expected output: Root 1

console.log(roots[0].children[1].name);
// Expected output: Child 1.2

console.log(roots);
// Expected output: [
//   { name: 'Root 1', children: [
//     { name: 'Child 1.1', parent: { ... } },
//     { name: 'Child 1.2', parent: { ... } }
//   ] },
//   { name: 'Root 2', children: [
//     { name: 'Child 2.1', parent: { ... } }
//   ] }
// ]

Documentation

buildTree(items: Iterable<T>, options: BuildTreeOptions): TreeResult<T>

Builds a tree from the given iterable items using the specified options.

Parameters

  • items: An iterable data structure containing the items to build the tree from.
  • options: An object specifying the build options. It has the following properties:
    • mode: (Optional) Defines the item connection method. children means an item defines its children in a list, and connects that way; parent means an item defines its parent, and connects to it that way. Defaults to parent.
      • key: (Optional) The key used to identify items. It can be a string, number, symbol, or a function that extracts the key from an item. Defaults to 'id'.
      • parentKey: (Optional) The key used to identify the parent of each item. It can be a string, number, symbol, or a function that extracts the parent key from an item. Defaults to 'parent'.
      • nodeDataKey: (Optional) The key used to store the item's data in each node. It can be a string, number, symbol, or false if the data should be merged directly into the node. Defaults to 'data'.
      • nodeParentKey: (Optional) The key used to store the parent node in each node. It can be a string, number, symbol, or false if the parent node should not be included. Defaults to 'parent'.
      • nodeChildrenKey: (Optional) The key used to store the children nodes in each node. It can be a string, number, symbol. Defaults to 'children'.
      • mapNodeData: (Optional) A function that maps an item to its corresponding node data. It allows transforming the item before assigning it to the node. Defaults to undefined.
      • validRootKeys: (Optional) An iterable containing key values that can be accepted as root nodes. If provided, any item with a key not present in this iterable will cause an error to be thrown. Defaults to undefined.
    • validRootParentKeys: (Optional) Only available when mode is set to parent. An iterable containing key values that can be accepted the parent field values of root nodes. If provided, any root node with a parent key not present in this iterable will cause an error to be thrown. Defaults to undefined.
    • validateTree: (Optional) A boolean flag that determines whether to validate the resulting data structure. If the structure is a cyclic graph, an Error will be thrown. Requires additional O(n) time to compute. Defaults to false.

Returns

An object with the following properties:

  • roots: An array of the root nodes of the built tree.
  • nodes: A Map object containing all nodes of the built tree, with keys corresponding to their identifiers.

Throws Error when:

  • A duplicate identifier is recieved,
  • or validRootKeys is set and an invalid key is recieved,
  • or validRootParentKeys is set and an invalid parent key is recieved,
  • or validateTree is set to true and a cyclic graph is the result.

Comparison with other tree building libraries

The package aims to be feature complete and highly customizable, which usually opposes with performance. There are other packages that may be more performant but lacks features that I really needed in my daily coding. In standard scenarios this package should perform more than enough and nearly as good as other packages.

For scenarios where performance is critical, consider implementing a tailored, optimized algorithm. It could be as simple as:

const roots = [];
const nodes = new Map();
for (const item of items) {
  let node = nodes.get(item.id);
  if (!node) {
    node = {};
    nodes.set(item.id, node);
  }
  node.data = item; // Or Object.assign(node, item);
  if (item.parentId) {
    let parent = nodes.get(item.parentId);
    if (!parent) {
      parent = {};
      nodes.set(item.parentId, parent);
    }
    if (!parent.children) parent.children = [];
    parent.children.push(node);
    node.parent = parent;
  } else {
    roots.push(node);
  }
}

Contributions

Contributions to fast-tree-builder are welcome! If you have any bug reports, feature requests, or improvements, please open an issue on the GitHub repository.

License

fast-tree-builder is licensed under the MIT License.