54545

Recursive depth function on an array

<h3>Question</h3>

I have an array of objects like this input, and I want to nest some objects inside another objects (based if their parentId is the parents' forumId),

I got the function working but up to 1 depth, how can I get it working for n depth? Any idea or optimizations are appreciated!

EDIT: After pointing out, the input isn't necessarily ordered.

<pre class="lang-js prettyprint-override">const input = [ { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true, }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true, }, { forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true, }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true, }, ]; function processInput(forumInput) { const topLevelForums = forumInput.filter(function (forum) { return forum.parentId === null; }); let output = topLevelForums; forumInput.forEach(function (forum) { if (forum.parentId !== null) { const forumParentId = forum.parentId; output.forEach(function (parentForum, idx) { if (parentForum.forumId === forumParentId) { if (!output[idx].hasOwnProperty("subForums")) { output[idx].subForums = []; } parentForum.subForums.push(forum); } }); } }); return output; }

This is the expected output:

[ { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true, subForums: [ { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true, }, { forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true, subForums: [ { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true, }, ], }, ], }, ]

This is the current output:

[ { forumDescription: "", forumDisplay: true, forumId: 1, forumLocked: false, forumName: "Main", parentId: null, subForums: [ { forumDescription: "Announcements & Projects posted here", forumDisplay: true, forumId: 2, forumLocked: false, forumName: "Announcements", parentId: 1, }, { forumDescription: "General forum, talk whatever you want here", forumDisplay: true, forumId: 3, forumLocked: false, forumName: "General", parentId: 1, }, ], }, ]
<h3>Answer1:</h3>

A wonderful opportunity to learn about mutual recursion. The input can be in any order -

<pre class="snippet-code-js lang-js prettyprint-override">function makeIndex (items, indexer) { const append = (r, k, v) => r.set(k, (r.get(k) || []).concat([ v ])) return items.reduce ( (r, i) => append(r, indexer(i), i) , new Map ) } function makeTree (index, root = null) { const many = (all = []) => all.map(one) const one = (forum = {}) => ( { ...forum , subforums: many(index.get(forum.forumId)) } ) return many(index.get(root)) } const input = [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newcomers here",forumLocked:false,forumDisplay:true}] const result = makeTree(makeIndex(input, forum => forum.parentId)) console.log(JSON.stringify(result, null, 2)) [ { "forumId": 1, "parentId": null, "forumName": "Main", "forumDescription": "", "forumLocked": false, "forumDisplay": true, "subforums": [ { "forumId": 2, "parentId": 1, "forumName": "Announcements", "forumDescription": "Announcements & Projects posted here", "forumLocked": false, "forumDisplay": true, "subforums": [] }, { "forumId": 3, "parentId": 1, "forumName": "General", "forumDescription": "General forum, talk whatever you want here", "forumLocked": false, "forumDisplay": true, "subforums": [ { "forumId": 4, "parentId": 3, "forumName": "Introduction", "forumDescription": "A warming introduction for newcomers here", "forumLocked": false, "forumDisplay": true, "subforums": [] } ] } ] } ] <hr />

make it modular

Above makeIndex is written in a way that it can index any array of datum, but makeTree makes assumptions like ...forum, subforums, and forum.forumId. When we think about our code in modules, we are forced to draw lines of separation and consequently our programs become untangled.

Below, input is defined in main and so we keep all knowledge about input here -

<pre class="lang-js prettyprint-override">// main.js import { tree } from './tree' const input = [{forumId:1,parentId:null,forumName:"Main",forumDescription:"",forumLocked:false,forumDisplay:true},{forumId:2,parentId:1,forumName:"Announcements",forumDescription:"Announcements & Projects posted here",forumLocked:false,forumDisplay:true},{forumId:3,parentId:1,forumName:"General",forumDescription:"General forum, talk whatever you want here",forumLocked:false,forumDisplay:true},{forumId:4,parentId:3,forumName:"Introduction",forumDescription:"A warming introduction for newcomers here",forumLocked:false,forumDisplay:true}] const result = tree ( input // <- array of nodes , forum => forum.parentId // <- foreign key , (forum, subforums) => // <- node reconstructor function ({ ...forum, subforums: subforums(forum.forumId) }) // <- primary key ) console.log(JSON.stringify(result, null, 2))

When I make a tree, I don't want to have to think about making an index first. In our original program, how was I supposed to know a tree needed an index? Let's let the tree module worry about that -

<pre class="lang-js prettyprint-override">// tree.js import { index } from './index' const empty = {} function tree (all, indexer, maker, root = null) { const cache = index(all, indexer) const many = (all = []) => all.map(x => one(x)) // zero knowledge of forum object shape const one = (single) => maker(single, next => many(cache.get(next))) return many(cache.get(root)) } export { empty, tree } // <-- public interface

We could have written the index function directly in the tree module but the behavior we want is not specific to trees. Writing a separate index module makes more sense -

<pre class="lang-js prettyprint-override">// index.js const empty = _ => new Map const update = (r, k, t) => r.set(k, t(r.get(k))) const append = (r, k, v) => update(r, k, (all = []) => [...all, v]) const index = (all = [], indexer) => all.reduce ( (r, v) => append(r, indexer(v), v) // zero knowledge of v shape , empty() ) export { empty, index, append } // <-- public interface

Writing modules helps you think about your code in meaningful parts and promotes a high degree of code reusability.


<h3>Answer2:</h3>

Since parents might be after the children in the input, I think I'd approach it by building a Map of forums by ID, then adding the children to them:

function processInput(forumInput) { // Get a map of forums by ID const forumsById = new Map(); for (const forum of forumInput) { forumsById.set(forum.forumId, forum); } // Add child forums to their parents for (const forum of forumInput) { const {parentId} = forum; if (parentId !== null) { const parent = forumsById.get(forum.parentId); parent.subForums = parent.subForums || []; // Or you could use `?? []` now parent.subForums.push(forum); } } // Return the parents array return [...forumsById.values()].filter(({parentId}) => parentId === null); }

Live Example:

<pre class="snippet-code-js lang-js prettyprint-override">const input = [ { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true, }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true, }, { forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true, }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true, }, ]; function processInput(forumInput) { // Get a map of forums by ID const forumsById = new Map(); for (const forum of forumInput) { forumsById.set(forum.forumId, forum); } // Add child forums to their parents for (const forum of forumInput) { const {parentId} = forum; if (parentId !== null) { const parent = forumsById.get(forum.parentId); parent.subForums = parent.subForums || []; // Or you could use `?? []` now parent.subForums.push(forum); } } // Return the parents array return [...forumsById.values()].filter(({parentId}) => parentId === null); } console.log(processInput(input)); <pre class="snippet-code-css lang-css prettyprint-override">.as-console-wrapper { max-height: 100% !important; }

Note that the above will throw an error if a forum claims to be in a parent forum that isn't in the input.


<h3>Answer3:</h3>

I think the systematic approach is 1. create a map of id to object 2. create a map of parent -> children 3. add all the parent to the results 4. recursively add children (subforums)

const input = [ { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true, }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true, }, { forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true, }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true, }, ]; const mapIdToForums = input.reduce((acc, cur) => { acc[cur.forumId] = cur; return acc; }, {}); const mapForumsToSubForums = input.reduce((acc, cur) => { parentId = cur.parentId || ""; // no parent acc[parentId] = acc[parentId] || []; acc[parentId].push(cur); return acc; }, {}); const addChildren = (parent) => { var children = mapForumsToSubForums[parent.forumId]; if (children) { parent.subForums = children children.forEach(c => addChildren(c)); } }; results = mapForumsToSubForums[""]; results.forEach(p => addChildren(p)); console.log(results);
<h3>Answer4:</h3>

You could take an object which takes all relation from an object with child to parent and parent to childand get the nodes which have no parent.

This approach works for any depth, unsorted data and uses only a single loop.

<pre class="snippet-code-js lang-js prettyprint-override">const input = [{ forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true }, { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }], tree = function(data, root) { var t = {}; data.forEach(o => { Object.assign(t[o.forumId] = t[o.forumId] || {}, o); t[o.parentId] = t[o.parentId] || {}; t[o.parentId].subForums = t[o.parentId].subForums || []; t[o.parentId].subForums.push(t[o.forumId]); }); return t[root].subForums; }(input, null); console.log(tree); <pre class="snippet-code-css lang-css prettyprint-override">.as-console-wrapper { max-height: 100% !important; top: 0; }
<h3>Answer5:</h3>

As some other answers, I would use a Map to key nodes by their forumId, and then populate the children inside the corresponding values:

<pre class="snippet-code-js lang-js prettyprint-override">let input = [{ forumId: 3, parentId: 1, forumName: "General", forumDescription: "General forum, talk whatever you want here", forumLocked: false, forumDisplay: true }, { forumId: 2, parentId: 1, forumName: "Announcements", forumDescription: "Announcements & Projects posted here", forumLocked: false, forumDisplay: true }, { forumId: 4, parentId: 3, forumName: "Introduction", forumDescription: "A warming introduction for newcomers here", forumLocked: false, forumDisplay: true }, { forumId: 1, parentId: null, forumName: "Main", forumDescription: "", forumLocked: false, forumDisplay: true }]; let root = {}; let map = new Map(input.map(o => [o.forumId, ({...o})])) map.forEach(o => (p => p.subForms = (p.subForms || []).concat(o))(map.get(o.parentId) || root)); let result = root.subForms; console.log(result);

来源:https://stackoverflow.com/questions/62137572/recursive-depth-function-on-an-array

Recommend

  • I need a specific example of how to define a local parameter in the primary constructor of an immuta
  • Position a that stays at the bottom
  • Is it possible to add Function.caller support to Rhino?
  • Hashing a range
  • Transpiler and compiler
  • Should I declare system call functions in C?
  • Implementing generic java interface adds additional method [duplicate]
  • iOS: Customise UITextField's inputView size
  • Apache with c# classes
  • Is Azure TopicClient threadsafe?
  • Reload reCaptcha after ajaxComplete
  • Firebase App named '[DEFAULT]' already exists (app/duplicate-app)
  • Reversibly encode two large integers of different bit lengths into one integer
  • Setting Development Environment to Production locally in Angular project template with ASP.NET Core
  • multi column sorting of datagrid view:
  • Update existing embedded chart in powerpoint using excel vba
  • Server page based on weightage
  • Read Bluetooth RSSI on Windows 7/Vista/XP
  • Bootstrap Datepicker : Changing start date to tomorrow
  • Can't access web service when connected to the network :: HTTP 407
  • How to use SerialPort class more reliably
  • Faces Servlet not parsing .xhtml pages in jsf 2. running on tomcat 7
  • How to convert days into months using datetime in Python3?
  • Javascript inside HTML import not affecting imported HTML
  • Year over Year Stats from a Crossfilter Dataset
  • Runtime complexity of getting the length of a string in different representations
  • Calculate time from document
  • How to turn off notice reporting in xampp?
  • Debug `Unexpected end of JSON input Error` on content script
  • Apple Mach-O Linker error (“duplicate symbol”)
  • Angular 4: Responsive Grid List
  • Sql - ON DUPLICATE KEY UPDATE
  • Angular FormGroup won't update it's value immediately after patchValue or setValue
  • PHP Permalinks.. how to change?
  • media foundation H264 decoder not working properly
  • Running R's aov() mixed effects model from Python using rpy2
  • Creating random wired topology for given arbitrary number of nodes on NS2
  • Access to a Matlab gui from the web
  • Time Complexity of Fibonacci Algorithm [duplicate]
  • XSLT Transformation to validate rules in XML document