Converts an array of items with ids and parent ids to a nested tree in a performant O(n) way. Runs in browsers and Node.js.
Home Page: https://www.npmjs.com/package/performant-array-to-tree
![dependabot[bot] avatar](https://avatars.githubusercontent.com/in/29110?v=4 "dependabot[bot]")
change
lookup[itemId] = {
...item,
[conf.childrenField]: lookup[itemId][conf.childrenField],
};to:
lookup[itemId] = Object.assign(item, {
[conf.childrenField]: lookup[itemId][conf.childrenField]
})Hi there,
I've tried to use this library for constructing a tree on a application I'm developing and while it has the awesome feature of using nested id and parentId properties I've noticed a potential bug on it.
The data that I'm getting from an API has the following structure:
var performantArrayToTree = require("performant-array-to-tree");
const data = [
{
id: 1,
title: "Some title",
parent: null
},
{
id: 125,
title: "Some title 2",
parent: {
id: 1,
},
},
];
console.log(performantArrayToTree.arrayToTree(data, {
parentId: 'parent.id',
}));
Expected result:
[
{
data: { id: 1, title: "Some title", parent: null },
children: [
{
data: { id: 125, title: "Some title 2", parent: null },
children: [],
}
]
}
]
Result I've gotten:
TypeError: Cannot read property 'parentId' of null
My guess is that the problem is in the following function:
function getNestedProperty(item: Item, nestedProperty: string) {
return nestedProperty.split(".").reduce((o, i) => o[i], item);
}
Since it's accessing the object o which in my case is null with the key of i it will throw an exception. A potential fix is to check if o is null or undefined and if it is the reduce function should return null as well.
function getNestedProperty(item: Item, nestedProperty: string) {
return nestedProperty.split(".").reduce((o, i) => (o === null || o === undefined) ? null : o[i], item);
}
const tree = arrayToTree(arr, {
transform: ['id', 'key1'],
// transform: item => { return { id: item.id, key1: item.key1 } },
});Currently your implementation places all of the data from the nodes inside a "data" field. Have you considered instead using the spread syntax to maintain the structure of the data being put into trees and simply placing the new children array alongside them? I don't know what kind of performance overhead this would entail just wondering if this was a conscious choice.
Using ".key" as id does not work.
My guess is that the code references the element as item.id and not item[id].
Since ".key" contains a dot it needs to be accessed with item[".key"].
I do not know Typescript but I think this is as an example of accessing with .id compared to [id]:
When there are multiple parents (at the same highest level) with multiple children, the result is [] empty.
const data = [
{
"Id": "51eba4ed-d724-48f6-9627-16704ef56b7a",
"LastModified": "2022-04-20T14:46:58Z",
"Title": "Navigation",
"Description": "",
"UrlName": "navigation",
"Name": "navigation",
"Synonyms": "",
"TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
"Ordinal": -11,
"FullUrl": "/navigation",
"ParentId": "00000000-0000-0000-0000-000000000000",
"Provider": "OpenAccessDataProvider"
},
{
"Id": "718c5b9b-b0fd-4c84-96da-36566104efa8",
"LastModified": "2022-04-20T13:23:49Z",
"Title": "Video Type",
"Description": "",
"UrlName": "video-type",
"Name": "video-type",
"Synonyms": "",
"TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
"Ordinal": -7,
"FullUrl": "/video-type",
"ParentId": "00000000-0000-0000-0000-000000000000",
"Provider": "OpenAccessDataProvider"
},
{
"Id": "3c59b053-38bd-46e3-8927-42d6320142a8",
"LastModified": "2022-04-20T14:45:59Z",
"Title": "Vimeo",
"Description": "",
"UrlName": "vimeo",
"Name": "vimeo",
"Synonyms": "",
"TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
"Ordinal": -9,
"FullUrl": "/video-type/vimeo",
"ParentId": "718c5b9b-b0fd-4c84-96da-36566104efa8",
"Provider": "OpenAccessDataProvider"
},
{
"Id": "4f2a80e5-6712-4c92-a174-66b6f8786752",
"LastModified": "2022-04-05T16:13:54Z",
"Title": "In-vehicle Applications",
"Description": "",
"UrlName": "in-vehicle-applications",
"Name": "in-vehicle-applicationseaa47100-39da-44f5-9e49-2820a25fd977",
"Synonyms": "",
"TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
"Ordinal": -5,
"FullUrl": "/navigation/apps/in-vehicle-applications",
"ParentId": "3b2d0dff-808a-4c38-8a49-f11fd032fc5e",
"Provider": "OpenAccessDataProvider"
},
{
"Id": "3610dbd5-4be8-415c-9d6b-94ac87f06976",
"LastModified": "2022-04-05T16:14:21Z",
"Title": "Mobile Applications",
"Description": "",
"UrlName": "mobile-applications",
"Name": "mobile-applications100b5984-8b91-4a53-b603-82bbd27ae62e",
"Synonyms": "",
"TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
"Ordinal": -6,
"FullUrl": "/navigation/apps/mobile-applications",
"ParentId": "3b2d0dff-808a-4c38-8a49-f11fd032fc5e",
"Provider": "OpenAccessDataProvider"
},
{
"Id": "7d1a5c07-1b9d-421f-9902-a741c97df2fe",
"LastModified": "2022-04-20T14:45:32Z",
"Title": "YouTube",
"Description": "",
"UrlName": "youtube",
"Name": "youtube",
"Synonyms": "",
"TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
"Ordinal": -8,
"FullUrl": "/video-type/youtube",
"ParentId": "718c5b9b-b0fd-4c84-96da-36566104efa8",
"Provider": "OpenAccessDataProvider"
},
{
"Id": "6af37344-49df-4af3-99d3-ad90356f5264",
"LastModified": "2022-04-20T14:46:33Z",
"Title": "Brightcove",
"Description": "",
"UrlName": "brightcove",
"Name": "brightcove",
"Synonyms": "",
"TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
"Ordinal": -10,
"FullUrl": "/video-type/brightcove",
"ParentId": "718c5b9b-b0fd-4c84-96da-36566104efa8",
"Provider": "OpenAccessDataProvider"
},
{
"Id": "3b2d0dff-808a-4c38-8a49-f11fd032fc5e",
"LastModified": "2022-04-20T14:47:16Z",
"Title": "Apps",
"Description": "",
"UrlName": "apps",
"Name": "appsbeb61f16-48a0-4368-acc6-b34aa7c1804e",
"Synonyms": "",
"TaxonomyId": "e5cd6d69-1543-427b-ad62-688a99f5e7d4",
"Ordinal": -4,
"FullUrl": "/navigation/apps",
"ParentId": "51eba4ed-d724-48f6-9627-16704ef56b7a",
"Provider": "OpenAccessDataProvider"
}
];
const result = arrayToTree(data, {
id: "Id",
parentId: "ParentId",
rootParentIds: {
"00000000-0000-0000-0000-000000000000": true,
},
}
console.log(result);
// output
// [] length 0
Line coverage only decreased in build folder, not in source code, but the current remapping configuration does not account for that. Reason is that TypeScript's _assign stub is only used partly.
Is there a way to return specific child nodes in tree structure?
It would be great to add an option to add a list of parent ids, so that the element gets duplicated and added to the respective parents objects.
First, thank you @philipstanislaus for building this nice and helpful tool!
I ran in some issues while trying to use it on a project, which I could track down to these points:
parentId is undefined.parentId is 0.Looking at the code, I saw, that you expect IDs to be strings. My project uses Integers with parentId: 0 for Root-Items. So no surprise it didn’t work out.
Would you mind:
undefined (= nonexisting) and 0 (Int) as values of parentId in addition to null?I would submit a PR, but I’m not used programming in TypeScript. :) Thank you in advance.
Add an option emptyChildren, so we can change the default empty children value. It may be like
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, emptyChildren: node => null }
);Which produces:
[
{
id: "4",
parentId: null,
custom: "abc",
children: [{ id: "31", parentId: "4", custom: "12", children: null }],
},
{
id: "418",
parentId: null,
custom: "ü",
children: [
{ id: "1941", parentId: "418", custom: "de", children: null },
{ id: "1", parentId: "418", custom: "ZZZz", children: null },
],
},
];
Sometime we can do more things:
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, emptyChildren: node => { node.isLeaf=true; return null; } }
);Which produces:
[
{
id: "4",
parentId: null,
custom: "abc",
children: [{ id: "31", parentId: "4", custom: "12", children: null, isLeaf: true }],
},
{
id: "418",
parentId: null,
custom: "ü",
children: [
{ id: "1941", parentId: "418", custom: "de", children: null, isLeaf: true },
{ id: "1", parentId: "418", custom: "ZZZz", children: null, isLeaf: true },
],
},
];
Hi,
I noticed a problem that is problematic when parentId is 0. That happened when I was pulling categories from WooCommerce.
Example Object
[
{
id: 17,
name: 'child 1',
slug: 'child-1',
parent: 16,
description: '',
display: 'default',
image: null,
menu_order: 0,
count: 0,
_links: { self: [Array], collection: [Array], up: [Array] }
},
{
id: 18,
name: 'child 1 1',
slug: 'child-1-1',
parent: 17,
description: '',
display: 'default',
image: null,
menu_order: 0,
count: 0,
_links: { self: [Array], collection: [Array], up: [Array] }
},
{
id: 16,
name: 'Parent Catgory',
slug: 'parent-catgory',
parent: 0,
description: 'parent category',
display: 'default',
image: null,
menu_order: 0,
count: 0,
_links: { self: [Array], collection: [Array] }
},
{
id: 15,
name: 'Uncategorized',
slug: 'uncategorized',
parent: 0,
description: '',
display: 'default',
image: null,
menu_order: 0,
count: 1,
_links: { self: [Array], collection: [Array] }
}
]
Regards
Consider a tree with 4 elements like this:
{
"id": "root",
"parent_id": null,
"bar": "bar",
"children": [
{
"id": "2",
"parent_id": "root",
"foo": "bar",
"children": []
},
{
"id": "1",
"parent_id": "root",
"foo": "bar",
"children": [
{
"id": "1-1",
"parent_id": "1",
"foo": "bar",
"children": []
}
]
}
]
}As you may see there is multi level nesting in this tree.
When I break this tree into individual elements and try to build it with option throwIfOrphans: true it will throw. It should not, because there are actually no orphans.
This issue comes from the order of items in the array passed into the arrayToTree function.
To reproduce:
const tree = arrayToTree(
[
{ id: '2', parent_id: 'root', foo: 'bar' },
{ id: '1-1', parent_id: '1', foo: 'bar' },
{ id: '1', parent_id: 'root', foo: 'bar' },
{ id: 'root', parent_id: null, bar: 'bar' },
],
{
id: 'id',
parentId: 'parent_id',
childrenField: 'children',
dataField: null,
throwIfOrphans: true,
},
);Results:
Error: The items array contains orphans that point to the following parentIds: [1]. These parentIds do not exist in the items array. Hint: prevent orphans to result in an error by passing the following option: { throwIfOrphans: false }Now when you change the order of elements in the array it will not throw:
const tree = arrayToTree(
[
{ id: '2', parent_id: 'root', foo: 'bar' },
{ id: '1', parent_id: 'root', foo: 'bar' },
{ id: '1-1', parent_id: '1', foo: 'bar' },
{ id: 'root', parent_id: null, bar: 'bar' },
],
{
id: 'id',
parentId: 'parent_id',
childrenField: 'children',
dataField: null,
throwIfOrphans: true,
},
);Meaning that the input array order matters. The error is misleading in this particular case.
var performantArrayToTree = require("performant-array-to-tree")
console.log(performantArrayToTree.arrayToTree([
{ num: "4", ref: "31", custom: "abc" },
{ num: "31", ref: "4", custom: "12" },
],
{ id: "num", parentId: "ref", childrenField: "nodes", throwIfOrphans: true }
));
// result = []
version: 1.9.1
Actually, I don't have a strong opinion on the expected result from this situation. But it seems strange that the lib silently cut an array. Probably it should be an error?
Hi !
I am new to JavaScript Tree data structure, so sorry if my question is irrelevant,
I wanted to know if you plan usual tree and node method (search for a node, add a child, delete a node...), as describe on the following link for eg ?
https://code.tutsplus.com/articles/data-structures-with-javascript-tree--cms-23393
As far as I undestood I didnt see any other array to tree npm module which embeds such features, and as your script seems more efficient, it could bice to have these !
Thanks for listening :)
Somewhat related to #11 .
We have a project in which id's are represented as string. We run into problems when parentId === "" (the items are ignored/the tree is not building). We can solve the issue by replacing all empty strings by null, but this is a bit cumbersome.
Would it be possible to support empty strings in addition to null, undefined and 0?
We also noticed that there is no output (warnings/errors) in the console when tree building fails. This could help identify problems early on and would be nice to have :)
May I know how do you handle the situation where an item has parentId (i.e. it is not null) that does not match the id of any other items in the array, and therefore the item itself should be considered a root element?
Thanks for your helpful package.
data property always returns type any.
I think it would be very useful if we could pass type with Generics.
Here's my data structure:
const array = [
{ data: { id: 'id1', parent: 'idparent' , otherdata...} },
{ data: { id: 'id2', parent: 'id1' , otherdata...} },
{ data: { id: 'id3', parent: 'id1' , otherdata...} }
]
id and parentId are nested inside data in my case, and I'd bet it is not uncommon.
Would you amend your code this way to make this scenario work?
Add this:
const getItemNestedProperty = (item: Item, nestedProperty: string): string => {
return nestedProperty.split('.').reduce((o, i) => o[i], item)
}
Replace
const itemId = item[conf.id]
const parentId = item[conf.parentId]
with:
const itemId = getItemNestedProperty(item, conf.id)
const parentId = getItemNestedProperty(item, conf.parentId)
Thanks!
In most cases, our tree list contains a row whose parentId field is one of null / undefined / '', but if the tree list is a subset of original tree list, chances are that the transform result is not right, no matter the throwIfOrphans option is set to true or false
example:
import { arrayToTree } from 'performant-array-to-tree'
const list = [
{ id: "aaa", parentId: "notexist" },
{ id: "bbb", parentId: "aaa" },
{ id: "ccc", parentId: "bbb" },
{ id: "ddd", parentId: "bbb" },
];
const result = arrayToTree(list, {
dataField: null,
});
console.log(JSON.stringify(result, null, 2)); // the output is []If we add an option named rootParentId, items whose parentId equals rootParentId will be treat as a root item.
The above code's output should be like this
const result = arrayToTree(list, {
dataField: null,
rootParentId: "notexist",
});[
{
"id": "aaa",
"parentId": "notexist",
"children": [
{
"id": "bbb",
"parentId": "aaa",
"children": [
{
"id": "ccc",
"parentId": "bbb",
"children": []
},
{
"id": "ddd",
"parentId": "bbb",
"children": []
}
]
}
]
}
]Add rootParentId into option, then replace
if (parentId === null || parentId === undefined || parentId === '') {
rootItems.push(TreeItem)
}with
if (parentId === null || parentId === undefined || parentId === '' || parentId === conf.rootParentId) {
// is a root item
rootItems.push(TreeItem)
}Of course we can also make rootParentId an array, the initial value is [null, undefined, ''] and will later be merged with user defined rootParentIds
Is there a way to include a back reference to the parent from each nested child.
We had very similar ideas, but it was a bit complicated at the time.
google translate
https://github.com/zhengxs2018/common-algorithm/blob/master/src/tree.ts
Now i refactor，Removed a lot of useless logic, more lightweight。
google translate
https://github.com/zhengxs2018/js.tree/blob/main/src/transform/toTree.ts
Maybe we can refer to each other.
google translate
const ROOT_ID = '__ROOT__'
function toTree(data, options = {}) {
const root = _.defaultTo(options.root, ROOT_ID)
const idKey = _.defaultTo(options.idKey, 'id')
const parentKey = _.defaultTo(options.parentKey, 'parentId')
const childrenKey = _.defaultTo(options.childrenKey, 'children')
const transform = _.defaultTo(options.transform, (x) => x)
const nodes = {}
let i = data.length
while (i--) {
const row = data[i]
// 获取节点ID
const id = row[idKey]
// id 必须存在
assert(!_.isNil(id), `id is required, in ${i}.`)
// 数据结构转换
const node = transform(row)
// 支持过滤掉某些数据
if (_.isNil(node)) continue
// 获取子级元素
const children = nodes[id]
if (children) {
node[childrenKey] = children
} else {
nodes[id] = node[childrenKey] = []
}
// 获取上级节点ID
const parentId = _.defaultTo(row[parentKey], ROOT_ID)
// 获取同级元素
const siblings = nodes[parentId]
if (siblings) {
siblings.push(node)
} else {
nodes[parentId] = [node]
}
}
return exporter(nodes, root)
}
function exporter(nodes, root) {
if (typeof root === 'function') {
return root(nodes) || []
}
return nodes[_.defaultTo(root, ROOT_ID)] || []
}
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.