Home > Software engineering >  Removing items from a nested array with unknown depth
Removing items from a nested array with unknown depth

Time:06-04

I am trying to remove items from a nested array based on an array of correct matches.

Three requirements apply:

  1. The depth of the array is unknown. Items can have nested children.
  2. Only items without children should be removed
  3. The items should be removed if they are not in the matching array

I have build a function to recursively get to the deepest level and filter the items based on the $match array.

This is what my code looks like so far:

import * as lodash from "https://cdn.skypack.dev/[email protected]";

let filterRecursively = (arr, match) => {
  // Recursively go to the deepest array we can find
  arr.forEach(el => {
      arr = el.children ? filterRecursively(el.children, match) : arr
  });

  // If we are at the deepest level we filter the items ...
  if (arr[0] && arr[0].children === undefined) {
    return _.filter(arr, (item) => {
        return match.includes(item.name)
    })
  } else { // ... if not we just return the array as-is
    return arr
  }
}

let arr = [
  {
    'name': 'John',
    'children': [
      {
        'name': 'John',
        'children': [
          { 'name': 'John' },
          { 'name': 'Jane' },
          { 'name': 'Joe' }
        ]
      }]
  }, {
    'name': 'Jeff',
    'children': [
      {
        'name': 'Joe',
        'children': [
          { 'name': 'Jill' },
          { 'name': 'Jeff' },
          { 'name': 'Joe' }
        ]
      }]
  }];

let match = ['John', 'Joe'];
let result = filterRecursively(arr, match);

console.log(result);

// Expected result:
 [
   {
     'name': 'John',
     'children': [
       {
         'name': 'John',
         'children': [
           { 'name': 'John' },
           { 'name': 'Joe' }
         ]
       }]
   }, {
     'name': 'Jeff',
     'children': [
       {
         'name': 'Joe',
         'children': [
           { 'name': 'Joe' }
         ]
       }]
   }];
// Current output
[
    {
        "name": "Joe"
    }
]

See the Codepen

CodePudding user response:

let filterRecursively = (arr, match) => {
  // Recursively go to the deepest array we can find
  return arr
    .map((el) =>
      el.children
        ? { ...el, children: filterRecursively(el.children, match) }
        : el
    )
    .filter((el) => el.children || match.includes(el.name));
};

I have updated filterRecursively.

      let filterRecursively = (arr, match) => {
      // Recursively go to the deepest array we can find
      return arr
        .map((el) =>
          el.children
            ? { ...el, children: filterRecursively(el.children, match) }
            : el
        )
        .filter((el) => el.children || match.includes(el.name));
    };
    
    let arr = [
      {
        name: "John",
        children: [
          {
            name: "John",
            children: [{ name: "John" }, { name: "Jane" }, { name: "Joe" }],
          },
        ],
      },
      {
        name: "Jeff",
        children: [
          {
            name: "Joe",
            children: [{ name: "Jill" }, { name: "Jeff" }, { name: "Joe" }],
          },
        ],
      },
    ];
    
    let match = ["John", "Joe"];
    let result = filterRecursively(arr, match);
    
    console.log(JSON.stringify(result));
    
    // Expected result:
    // [
    //   {
    //     'name': 'John',
    //     'children': [
    //       {
    //         'name': 'John',
    //         'children': [
    //           { 'name': 'John' },
    //           { 'name': 'Joe' }
    //         ]
    //       }]
    //   }, {
    //     'name': 'Jeff',
    //     'children': [
    //       {
    //         'name': 'Joe',
    //         'children': [
    //           { 'name': 'Joe' }
    //         ]
    //       }]
    //   }];

CodePudding user response:

Because the forEach basically "skips" layers without returning anything, you end up with just your first and deepest result.

I also think your function is a bit more complicated because it starts with an array, rather than a sort of ROOT node.

Here's an alternative that (I think) meets your requirements:

let childlessMatch = (node, match) => {
  // If it's at the deepest level, check against match
  if (node.children === undefined) {
    return match.includes(node.name) ? [node] : [];
  }
  
  // If not, calculate the next child layer first
  const newChildren = node.children.flatMap(c => childlessMatch(c, match));

  // With the children calculated, we can prune based on whether there
  // are any children left to show
  if (newChildren.length === 0) return [];
  
  return [{
    ...node,
    children: newChildren
  }]
} 

In a runnable snippet:

let childlessMatch = (node, match) => {
  if (node.children === undefined) {
    return match.includes(node.name) ? [node] : [];
  }
  
  const newChildren = node.children.flatMap(c => childlessMatch(c, match));
  if (newChildren.length === 0) return [];
  
  return {
    ...node,
    children: newChildren
  }
}

let arr = [
  {
    'name': 'John',
    'children': [
      {
        'name': 'John',
        'children': [
          { 'name': 'John' },
          { 'name': 'Jane' },
          { 'name': 'Joe' }
        ]
      }]
  }, {
    'name': 'Jeff',
    'children': [
      {
        'name': 'Joe',
        'children': [
          { 'name': 'Jill' },
          { 'name': 'Jeff' },
          { 'name': 'Joe' }
        ]
      }]
  }];

let match = ['John', 'Joe'];
let result = childlessMatch({ children: arr }, match).children;

console.log(result);

CodePudding user response:

I think it's better to separate out a generic node filtering technique that handles children appropriately from the code that checks the names. Here filterNodes accepts a predicate that says whether the node should be included (without worrying about children). It then does the child handling bit.

We write our main function by just passing a predicate that tests whether the name is on the allowed list.

Together, it looks like this:

const filterNodes = (pred) => (nodes) => 
  nodes .flatMap (
    (node, _, __, 
     kids = filterNodes (pred) (node .children || [])
    ) => pred (node) || node .children ?.length > 0 
      ? [{...node, ... (kids .length ? {children: kids} : {})}] 
      : []
  )

const removeUnmatchedNames = (names) =>
  filterNodes (({name}) => names .includes (name))


const arr = [{name: "John", children: [{name: "John", children: [{name: "John"}, {name: "Jane"}, {name: "Joe"}]}]}, {name: "Jeff", children: [{name: "Joe", children: [{name: "Jill"}, {name: "Jeff"}, {name: "Joe"}]}]}]

console .log (removeUnmatchedNames (['John', 'Joe']) (arr))
.as-console-wrapper {max-height: 100% !important; top: 0}

  • Related