Bottom Up Search to Filter a Nested Menu Array

I have searched on here for bottom-up search examples and I understand how they are done, but I have a specific need here that I have been unable to solve.

We have a menu system that I need to create a filter for.

So for example if the menu is

- Testing
    - Test
- Something
    - Something Else
    - Test

If I filter for "Test" I want 4 nodes back and everything else pruned out. The tricky part is that it can't remove the "Something" node in this case due to it having matching children that need to be accessed.

My code works, but only for the top level items, due to the filter pass during the first recursion step removing anything that may have matching children but the parent doesn't match.

private recursiveFilter(menuItems: MenuItem[], label: string): MenuItem[] {

if (label === '') {
  this.menuItems = this.originalMenuItems;
  return this.menuItems;
} else if (!menuItems)  {
  return [];
}

return menuItems
  .filter((el) => el.label?.toLowerCase().includes(label.toLowerCase()))
  .map((el) => {

    if (!(el.items || !Array.isArray(el.items))) {
      return el;
    } else {

      const menuChildren = el.items as MenuItem[];

      if (menuChildren) {
        el.items = this.recursiveFilter(menuChildren, label);
      }

      return el;

    }
  });

}

Example of a MenuItem with nested children:

{
    "label": "Messages",
    "expanded": false,
    "items": [
        {
            "label": "Dashboard",
            "expanded": false,
            "routerLink": "/messages",
            "visible": true
        },
        {
            "label": "Voicemail",
            "expanded": false,
            "items": [
                {
                    "label": "Inbox",
                    "icon": "pi pi-fw pi-folder",
                    "routerLink": "/mailbox/inbox"
                },
                {
                    "label": "Archived",
                    "icon": "pi pi-fw pi-folder",
                    "routerLink": "/mailbox/archived"
                },
                {
                    "label": "Trash",
                    "icon": "pi pi-fw pi-folder",
                    "routerLink": "/mailbox/trash"
                }
            ]
        },
        {
            "label": "Text",
            "expanded": false,
            "items": [
                {
                    "label": "Messages",
                    "routerLink": "/sms",
                    "routerLinkActiveOptions": {
                        "exact": true
                    }
                },
                {
                    "label": "Send",
                    "routerLink": "/sms/send",
                    "routerLinkActiveOptions": {
                        "exact": true
                    }
                },
                {
                    "label": "Contacts",
                    "routerLink": "/sms/contacts"
                }
        ]
    }
]

}

Solution 1:

Do the filtering after the recursive call has identified which children to keep. If, after filtering, there still exist any child elements or the label matches, keep that parent item.

Something along the lines of:

private recursiveFilter(menuItems: MenuItem[], label: string, labelLower = label.toLowerCase()) {
    return menuItems.filter((item) => {
        if (item.items) item.items = recursiveFilter(item.items, label, labelLower);
        return item.label?.toLowerCase().includes(labelLower) || item.items?.length;
    });
}

Side-effects inside a .filter is a bit smelly, but I think it's the clearest way to approach this problem.

Live demo:

const recursiveFilter = (menuItems, label) => (
    menuItems.filter((item) => {
        if (item.items) item.items = recursiveFilter(item.items, label);
        return item.label?.toLowerCase().includes(label) || item.items?.length;
    })
);

const topItem={label:"Messages",expanded:!1,items:[{label:"Dashboard",expanded:!1,routerLink:"/messages",visible:!0},{label:"Voicemail",expanded:!1,items:[{label:"Inbox",icon:"pi pi-fw pi-folder",routerLink:"/mailbox/inbox"},{label:"Archived",icon:"pi pi-fw pi-folder",routerLink:"/mailbox/archived"},{label:"Trash",icon:"pi pi-fw pi-folder",routerLink:"/mailbox/trash"}]},{label:"Text",expanded:!1,items:[{label:"Messages",routerLink:"/sms",routerLinkActiveOptions:{exact:!0}},{label:"Send",routerLink:"/sms/send",routerLinkActiveOptions:{exact:!0}},{label:"Contacts",routerLink:"/sms/contacts"}]}]};

topItem.items = recursiveFilter(topItem.items, 'send');
console.log(topItem);

Solution 2:

I prefer separating out the recursive filtering from the specific check required. Then we can pass in a predicate function as needed. I find this simpler. So I might write it like this:

const deepFilter = (pred) => ({items = [], ...rest}) => {
  const children = items .flatMap (deepFilter (pred))
  return (children .length || pred (rest)) 
    ? [{...rest, ...(items.length ? {items: children} : {})}] 
    : []
}

const matchLabel = (text) => ({label = ''}) => 
  label .toLowerCase () .includes (text .toLowerCase())

const filterByLabel = (t) =>
  deepFilter (matchLabel (t))

const menuItem = {label: "Messages", expanded: false, items: [{label: "Dashboard", expanded: false, routerLink: "/messages", visible: true}, {label: "Voicemail", expanded: false, items: [{label: "Inbox", icon: "pi pi-fw pi-folder", routerLink: "/mailbox/inbox"}, {label: "Archived", icon: "pi pi-fw pi-folder", routerLink: "/mailbox/archived"}, {label: "Trash", icon: "pi pi-fw pi-folder", routerLink: "/mailbox/trash"}]}, {label: "Text", expanded: false, items: [{label: "Messages", routerLink: "/sms", routerLinkActiveOptions: {exact: true}}, {label: "Send", routerLink: "/sms/send", routerLinkActiveOptions: {exact: true}}, {label: "Contacts", routerLink: "/sms/contacts"}]}]}


console .log ('labels containing "send":', filterByLabel ('send') (menuItem))
console .log ('labels containing "a":', filterByLabel ('a') (menuItem))
console .log ('labels containing "foobar":', filterByLabel ('foobar') (menuItem))

.as-console-wrapper {max-height: 100% !important; top: 0}

Here, deepFilter takes a predicate function and returns a function which takes a tree with children nested as items and returns only those items matching the predicate or which have children matching the predicate. We write the matchLabel predicate which takes a search string and returns a function which tests whether the object passed to it has a label property that (case-insensitively) contains the search term. Finally, filterByLabel simply combines them, accepting a search term and returning a function which takes an item and (recursively) returns the item if it matches the term or if any of its children do.

Variations

There are some things we might want to change.

First of all, matchLabel is calling .toLowerCase on the text every time. We could avoid that with this alternative:
```
const matchLabel = (t, text = t.toLowerCase()) => ({label = ''}) => 
  label .toLowerCase () .includes (text)
```

Second, deepFilter is nice and generic... except that it hard-codes the tree structure of an items array in the function. We might want to make that more generic by making that node name a parameter. We can do so by

const deepFilter = (childName) => (pred) => ({[childName]: items = [], ...rest}) => {
  const children = items .flatMap (deepFilter (childName) (pred))
  return (children .length || pred (rest)) 
    ? [{...rest, ...(items.length ? {[childName]: children} : {})}] 
    : []
}

and then use it like this:

const filterByLabel = (t) =>
  deepFilter ('items') (matchLabel (t))

or by naming the intermediate function:

const deepFilterItemTree = deepFilter ('items')

const filterByLabel = (t) =>
  deepFilterItemTree (matchLabel (t))

Third, if we happen to have handy a compose function, we might rewrite the main function as

const filterByLabel = compose (deepFilter, matchLabel)

or if we took the second suggestion, as either of these:

const filterByLabel = compose (deepFilter ('items'), matchLabel)
// or
const filterByLabel = compose (deepFilterItemTree, matchLabel)

Bottom Up Search to Filter a Nested Menu Array

Solution 1:

Solution 2:

Variations

Related

Recent Posts