performant-array-to-tree - npm Package Compare versions

Comparing version 1.9.2 to 1.10.0

build/arrayToTree.d.ts

@@ -22,1 +22,8 @@ export interface Item {
 export declare function arrayToTree(items: Item[], config?: Partial<Config>): TreeItem[];
+/**
+ * Returns the number of nodes in a tree in a recursive way
+ * @param tree An array of nodes (tree items), each having a field `childrenField` that contains an array of nodes
+ * @param childrenField Name of the property that contains the array of child nodes
+ * @returns Number of nodes in the tree
+ */
+export declare function countNodes(tree: TreeItem[], childrenField: string): number;

build/arrayToTree.js

@@ -14,3 +14,3 @@ "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.arrayToTree = void 0;
+exports.countNodes = exports.arrayToTree = void 0;
 var defaultConfig = {
@@ -38,3 +38,3 @@ id: "id",
     // this is an opt-in property, since it has a slight runtime overhead
-    var orphanIds = config.throwIfOrphans
+    var orphanIds = conf.throwIfOrphans
         ? new Set()
@@ -103,2 +103,6 @@ : null;
     }
+    if (conf.throwIfOrphans &&
+        countNodes(rootItems, conf.childrenField) < Object.keys(lookup).length) {
+        throw new Error("The items array contains nodes with a circular parent/child relationship.");
+    }
     return rootItems;
@@ -108,2 +112,16 @@ }
 /**
+ * Returns the number of nodes in a tree in a recursive way
+ * @param tree An array of nodes (tree items), each having a field `childrenField` that contains an array of nodes
+ * @param childrenField Name of the property that contains the array of child nodes
+ * @returns Number of nodes in the tree
+ */
+function countNodes(tree, childrenField) {
+    return tree.reduce(function (sum, n) {
+        return sum +
+            1 +
+            (n[childrenField] && countNodes(n[childrenField], childrenField));
+    }, 0);
+}
+exports.countNodes = countNodes;
+/**
  * Returns the value of a nested property inside an item
@@ -110,0 +128,0 @@ * Example: user can access 'id', or 'parentId' inside item = { nestedObject: { id: 'myId', parentId: 'myParentId' } }

build/arrayToTree.min.js

@@ -1,1 +0,1 @@
-"use strict";var __assign=this&&this.__assign||function(){return(__assign=Object.assign||function(e){for(var r,t=1,n=arguments.length;t<n;t++)for(var o in r=arguments[t])Object.prototype.hasOwnProperty.call(r,o)&&(e[o]=r[o]);return e}).apply(this,arguments)},defaultConfig=(Object.defineProperty(exports,"__esModule",{value:!0}),{id:"id",parentId:"parentId",dataField:"data",childrenField:"children",throwIfOrphans:!1,rootParentIds:{"":!(exports.arrayToTree=void 0)},nestedIds:!0});function arrayToTree(p,e){void 0===e&&(e={});for(var r,t=__assign(__assign({},defaultConfig),e),n=[],o={},a=e.throwIfOrphans?new Set:null,s=0,h=p;s<h.length;s++){var i=h[s],d=t.nestedIds?getNestedProperty(i,t.id):i[t.id],l=t.nestedIds?getNestedProperty(i,t.parentId):i[t.parentId];if(t.rootParentIds[d])throw new Error("The item array contains a node whose parentId both exists in another node and is in "+'`rootParentIds` (`itemId`: "'.concat(d,'", `rootParentIds`: ').concat(Object.keys(t.rootParentIds).map(function(e){return'"'.concat(e,'"')}).join(", "),")."));Object.prototype.hasOwnProperty.call(o,d)||(o[d]=((r={})[t.childrenField]=[],r)),a&&a.delete(d),t.dataField?o[d][t.dataField]=i:o[d]=__assign(__assign({},i),((r={})[t.childrenField]=o[d][t.childrenField],r));i=o[d];null==l||t.rootParentIds[l]?n.push(i):(Object.prototype.hasOwnProperty.call(o,l)||(o[l]=((d={})[t.childrenField]=[],d),a&&a.add(l)),o[l][t.childrenField].push(i))}if(null!=a&&a.size)throw new Error("The items array contains orphans that point to the following parentIds: "+"[".concat(Array.from(a),"]. These parentIds do not exist in the items array. Hint: prevent orphans to result ")+"in an error by passing the following option: { throwIfOrphans: false }");return n}function getNestedProperty(e,r){return r.split(".").reduce(function(e,r){return e&&e[r]},e)}exports.arrayToTree=arrayToTree;
+"use strict";var __assign=this&&this.__assign||function(){return(__assign=Object.assign||function(e){for(var r,t=1,n=arguments.length;t<n;t++)for(var o in r=arguments[t])Object.prototype.hasOwnProperty.call(r,o)&&(e[o]=r[o]);return e}).apply(this,arguments)},defaultConfig=(Object.defineProperty(exports,"__esModule",{value:!0}),{id:"id",parentId:"parentId",dataField:"data",childrenField:"children",throwIfOrphans:!1,rootParentIds:{"":!(exports.countNodes=exports.arrayToTree=void 0)},nestedIds:!0});function arrayToTree(l,e){void 0===e&&(e={});for(var r,t=__assign(__assign({},defaultConfig),e),n=[],o={},a=t.throwIfOrphans?new Set:null,s=0,h=l;s<h.length;s++){var i=h[s],d=t.nestedIds?getNestedProperty(i,t.id):i[t.id],c=t.nestedIds?getNestedProperty(i,t.parentId):i[t.parentId];if(t.rootParentIds[d])throw new Error("The item array contains a node whose parentId both exists in another node and is in "+'`rootParentIds` (`itemId`: "'.concat(d,'", `rootParentIds`: ').concat(Object.keys(t.rootParentIds).map(function(e){return'"'.concat(e,'"')}).join(", "),")."));Object.prototype.hasOwnProperty.call(o,d)||(o[d]=((r={})[t.childrenField]=[],r)),a&&a.delete(d),t.dataField?o[d][t.dataField]=i:o[d]=__assign(__assign({},i),((r={})[t.childrenField]=o[d][t.childrenField],r));i=o[d];null==c||t.rootParentIds[c]?n.push(i):(Object.prototype.hasOwnProperty.call(o,c)||(o[c]=((d={})[t.childrenField]=[],d),a&&a.add(c)),o[c][t.childrenField].push(i))}if(null!=a&&a.size)throw new Error("The items array contains orphans that point to the following parentIds: "+"[".concat(Array.from(a),"]. These parentIds do not exist in the items array. Hint: prevent orphans to result ")+"in an error by passing the following option: { throwIfOrphans: false }");if(t.throwIfOrphans&&countNodes(n,t.childrenField)<Object.keys(o).length)throw new Error("The items array contains nodes with a circular parent/child relationship.");return n}function countNodes(e,t){return e.reduce(function(e,r){return e+1+(r[t]&&countNodes(r[t],t))},0)}function getNestedProperty(e,r){return r.split(".").reduce(function(e,r){return e&&e[r]},e)}exports.arrayToTree=arrayToTree,exports.countNodes=countNodes;

build/arrayToTree.spec.js

@@ -29,2 +29,51 @@ "use strict";
     });
+    it("should work with nested objects if throwIfOrphans is set to true", function () {
+        (0, chai_1.expect)((0, arrayToTree_1.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: "ü" },
+        ], { throwIfOrphans: true })).to.deep.equal([
+            {
+                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: [] },
+                ],
+            },
+        ]);
+    });
+    it("should ignore circular parent child relations", function () {
+        (0, chai_1.expect)((0, arrayToTree_1.arrayToTree)([
+            { id: "4", parentId: "31", custom: "abc" },
+            { id: "31", parentId: "4", custom: "12" },
+        ])).to.deep.equal([]);
+        (0, chai_1.expect)((0, arrayToTree_1.arrayToTree)([
+            { id: "4", parentId: "31", custom: "abc" },
+            { id: "31", parentId: "5", custom: "12" },
+            { id: "5", parentId: "4", custom: "12" },
+        ])).to.deep.equal([]);
+    });
+    it("should throw if throwIfOrphans is enabled and circular parent child relations are encountered, see #37", function () {
+        (0, chai_1.expect)(function () {
+            return (0, arrayToTree_1.arrayToTree)([
+                { id: "4", parentId: "31", custom: "abc" },
+                { id: "31", parentId: "4", custom: "12" },
+            ], { throwIfOrphans: true });
+        }).to.throw("The items array contains nodes with a circular parent/child relationship.");
+        (0, chai_1.expect)(function () {
+            return (0, arrayToTree_1.arrayToTree)([
+                { id: "4", parentId: "31", custom: "abc" },
+                { id: "31", parentId: "5", custom: "12" },
+                { id: "5", parentId: "4", custom: "12" },
+            ], { throwIfOrphans: true });
+        }).to.throw("The items array contains nodes with a circular parent/child relationship.");
+    });
     it("should work with integer keys", function () {
@@ -504,2 +553,19 @@ (0, chai_1.expect)((0, arrayToTree_1.arrayToTree)([
 });
+describe("countNodes", function () {
+    it("should work with nested objects", function () {
+        (0, chai_1.expect)((0, arrayToTree_1.countNodes)((0, arrayToTree_1.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: "ü" },
+        ]), "children")).to.equal(5);
+    });
+    it("should work for 1 node", function () {
+        (0, chai_1.expect)((0, arrayToTree_1.countNodes)((0, arrayToTree_1.arrayToTree)([{ id: "4", parentId: null, custom: "abc" }]), "children")).to.equal(1);
+    });
+    it("should work for 0 nodes", function () {
+        (0, chai_1.expect)((0, arrayToTree_1.countNodes)((0, arrayToTree_1.arrayToTree)([]), "children")).to.equal(0);
+    });
+});
 //# sourceMappingURL=arrayToTree.spec.js.map

package.json

 {
   "name": "performant-array-to-tree",
-  "version": "1.9.2",
+  "version": "1.10.0",
   "description": "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.",
@@ -5,0 +5,0 @@ "keywords": [

README.md

@@ -67,9 +67,9 @@ # Performant array to tree
 
-- `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](https://github.com/philipstanislaus/performant-array-to-tree/issues/23). Default: `{'': true}`
+- `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 or if the array of items contains items with a circular parent/child relationship. 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, or in the case of only circular item relationships a generic error. The function will throw an error if the number of nodes in the tree is smaller than the number of nodes in the original array. When disabled, the function will just ignore orphans and circular relationships 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](https://github.com/philipstanislaus/performant-array-to-tree/issues/23). Default: `{'': true}`
 
@@ -76,0 +76,0 @@ Example:

No alert changes

Improved metrics

Total package byte prevSize

72162

increased by14.31%

Lines of code

728

increased by14.29%

No dependency changes