Creating deep filter by input value

I have an array of objects

[
  {
    id: "95c3-1e74-48c7-ec7e",
    name: "model.yaml",
    type: "file",
    path: "model/model.yaml",
  },
  {
    id: "115c-d112-5ce5-a7e8",
    name: "storage-complextypes.yaml",
    type: "file",
    path: "model/storage-complextypes.yaml",
  },
  {
    id: "9f51-93b5-4160-0237",
    name: "storage-simpletypes.yaml",
    type: "file",
    path: "model/storage-simpletypes.yaml",
  },
  {
    id: "05a0-d4fb-d461-9697",
    name: "newfolder",
    type: "directory",
    path: "model/newfolder",
    children: [
      {
        id: "e8e5-f0c8-6664-96e1",
        name: "newname",
        type: "file",
        path: "model/newfolder/newname",
      },
    ],
  },
];

The purpose is to get an array if only some of the objects name characters are matching , so it's checking similarity on each input occurence. Below, is what I want to see as a result if "newn" is typed.

[
      {
        id: "e8e5-f0c8-6664-96e1",
        name: "newname",
        type: "file",
        path: "model/newfolder/newname",
      },
    ]

Thats what I have for now.

const findItem = function(array, name) {
  return array.flatMap((item) => item.children).some((data) => data.name.includes(name)) || null;
}

5 answers

  • answered 2021-05-05 11:18 georg

    I'd do it in two steps: flatten and then find:

    data = [
        {name: "model.yaml",},
        {name: "storage-simpletypes.yaml",},
        {name: "newfolder",
            children: [
                {
                    name: "newname",
                    children: [
                        {name: "newname2", path: 'hi there'},
                    ],
                },
            ],
        },
    ];
    
    let flatten = d => (d || []).flatMap(e => [e, ...flatten(e.children)])
    
    console.log(...flatten(data).filter(e => e.name.startsWith('newn')))

  • answered 2021-05-05 11:24 Nithish

    There are multiple ways in achieving the expected output. Here I'm using Array.reduce.

    const data = [{id:"95c3-1e74-48c7-ec7e",name:"model.yaml",type:"file",path:"model/model.yaml",},{id:"115c-d112-5ce5-a7e8",name:"storage-complextypes.yaml",type:"file",path:"model/storage-complextypes.yaml",},{id:"9f51-93b5-4160-0237",name:"storage-simpletypes.yaml",type:"file",path:"model/storage-simpletypes.yaml",},{id:"05a0-d4fb-d461-9697",name:"newfolder",type:"directory",path:"model/newfolder",children:[{id:"e8e5-f0c8-6664-96e1",name:"newname",type:"file",path:"model/newfolder/newname",}]}];
    
    const getFilteredData = (data, name) => {
      const addIfMatching = (res, obj, name) => {
        if (obj.name.includes(name)) {
          res.push(obj);
        }
      }
    
      return data.reduce((res, obj) => {
        const { children, ...rest } = obj;
        addIfMatching(res, rest, name);
        if (children) {
          children.forEach(child => {
            addIfMatching(res, child, name)
          })
        }
        return res;
      }, [])
    }
    
    console.log("names having `newn`");
    console.log(getFilteredData(data, "newn"));
    
    console.log("-------------")
    console.log("names having `new`");
    console.log(getFilteredData(data, "new"));
    .as-console-wrapper {
      max-height: 100% !important;
    }

    Note: I have considered only one sub level of the parent object. i.e., only one level of children in the top level object.

  • answered 2021-05-05 13:43 Scott Sauyet

    Update: the various versions of flatFilter have been updated with a suggestion from user @Thankyou.

    I would probably start with a generic function to do a deep filtering into a flat list, one that works with an arbitrary predicate, something like this:

    const flatFilter = (pred) => (xs = []) =>
      xs .flatMap (x => (pred (x) ? [x] : []) .concat (flatFilter (pred) (x.children)))
    

    Then we could use it to build your search function on the path nodes:

    const searchPath = (target) => 
      flatFilter (({path = ''}) => path .includes (target))
    

    and we would call it like this:

    searchPath ('newn') (input)
    

    So overall, it might look like this:

    const flatFilter = (pred) => (xs = []) =>
      xs .flatMap (x => (pred (x) ? [x] : []) .concat (flatFilter (pred) (x.children)))
    
    const searchPath = (target) => 
      flatFilter (({path = ''}) => path .includes (target))
    
    const input = [{id: "95c3-1e74-48c7-ec7e", name: "model.yaml", type: "file", path: "model/model.yaml"}, {id: "115c-d112-5ce5-a7e8", name: "storage-complextypes.yaml", type: "file", path: "model/storage-complextypes.yaml"}, {id: "9f51-93b5-4160-0237", name: "storage-simpletypes.yaml", type: "file", path: "model/storage-simpletypes.yaml"}, {id: "05a0-d4fb-d461-9697", name: "newfolder", type: "directory", path: "model/newfolder", children: [{id: "e8e5-f0c8-6664-96e1", name: "newname", type: "file", path: "model/newfolder/newname"}]}]
    
    console .log ('newn:', searchPath ('newn') (input))
    console .log ('type:', searchPath ('type') (input))
    .as-console-wrapper {max-height: 100% !important; top: 0}

    If you preferred your main function to be called like searchPath (input, 'newn'), it would be a minor change, still using the same base function:

    const searchPath = (xs, target) => 
      flatFilter ('children') (({path = ''}) => path .includes (target)) (xs)
    

    And if we wanted to make this more generic, so that the name of the descendent node (here 'children' is configurable, it's just one more parameter:

    const flatFilter = (prop) => (pred) => (xs = []) =>
      xs.flatMap (x => (pred (x) ? [x] : []).concat (flatFilter (prop) (pred) (x.children)))
    

    And our main function would now look like this:

    const searchPath = (xs, target) => 
      flatFilter ('children') (({path = ''}) => path .includes (target)) (xs)
    

    Finally, the above does a depth-first traversal. If we wanted a breadth-first traversal, it's only slightly more complex. Here's one version:

    const flatFilter = (pred) => (xs = []) => 
      xs .length == 0 
        ? [] 
        : xs .flatMap (x => pred (x) ? [x] : [])
             .concat (flatFilter (pred) (xs .flatMap (({children = []}) => children)))
    

    And here's one that abstracts 'children':

    const flatFilter = (prop) => (pred) => (xs = []) => 
      xs .length == 0 
        ? [] 
        : xs .flatMap (x => pred (x) ? [x] : [])
             .concat (flatFilter (prop) (pred) (xs .flatMap (({[prop]: c = []}) => c)))
    

    I think quite often, reaching for a more generic version of what we're trying to do actually ends up simplifying an approach. Here, by separating the predicate we apply from the tree traversal, we can both simplify our custom function and have available a reusable function for other parts of our app or other apps.

  • answered 2021-05-05 14:35 Thank you

    generic

    I will suggest a generic approach, find, that works on any input and any level of nesting. It accepts a target of any type, t, and a querying function, query -

    function* find (t, query)
    { if (query(t)) yield {path: [], value: t}
      switch (t?.constructor)
      { case Array:
        case Object:
          for (const [k, v] of Object.entries(t))
            for (const {path, value} of find(v, query))
              yield {path: [k, ...path], value}
      }
    }
    

    find is a higher-order function that works similarly to Array.prototype.find -

    Array.from(find(data, t => /newn/.test(t)))
    

    find yields {path, value} results -

    path value
    ["3", "children", "0", "name"] "newname"
    ["3", "children", "0", "path"] "model/newfolder/newname"

    Where the path can be used to lookup the value -

    data["3"]["children"]["0"]["name"]  // => "newname"
    data["3"]["children"]["0"]["path"]  // => "model/newfolder/newname"
    

    specialize

    find is a higher-order function, enabling the caller (you!) to modify its output by modifying the querying function. Below we write a matchProperty to accept a regular expression, re, and an input o. If o is an Object and one of its properties matches the expression, we return true to signal that find should include this result -

    const matchProperty = re => o =>
      o?.constructor === Object
        && Object.keys(o).some(k => re.test(o[k]))
        
    Array.from(find(data, matchProperty(/newn/)))
    
    path value
    ["3", "children", "0"] {id:"e8e5-f0c8-6664-96e1",name:"newname",type:"file", path":"model/newfolder/newname"}

    You can be as specific or creative with these queries as you'd like. Instead of matching any property, we could write a more focused match -

    const hasFileType = type => o =>
      o?.name?.endsWith(`.${type}`)
    
    Array.from(find(data, hasFileType("yaml")))
    
    path value
    ["0"] {"id":"95c3-1e74-48c7-ec7e","name":"model.yaml","type":"file","path":"model/model.yaml"}
    ["1"] {"id":"115c-d112-5ce5-a7e8","name":"storage-complextypes.yaml","type":"file","path":"model/storage-complextypes.yaml"}
    ["2"] {"id":"9f51-93b5-4160-0237","name":"storage-simpletypes.yaml","type":"file","path":"model/storage-simpletypes.yaml"}

    Or maybe instead of finding all results, you only wish to find the first result -

    function find1 (t, f)
    { for (const r of find(t, f))
        return r
    }
    
    find1(data, hasFileType("yaml"))
    
    path value
    ["0"] {"id":"95c3-1e74-48c7-ec7e","name":"model.yaml","type":"file","path":"model/model.yaml"}

    demo

    Run the program below to verify the results in your own browser -

    function* find (t, query)
    { if (query(t)) yield {path: [], value: t}
      switch (t?.constructor)
      { case Array:
        case Object:
          for (const [k, v] of Object.entries(t))
            for (const {path, value} of find(v, query))
              yield {path: [k, ...path], value}
      }
    }
    
    const matchProperty = re => o =>
      o?.constructor === Object
        && Object.keys(o).some(k => re.test(o[k]))
    
    const hasFileType = type => o =>
      o?.name?.endsWith("." + type)
    
    const data =
      [{id: "95c3-1e74-48c7-ec7e",name: "model.yaml",type: "file",path: "model/model.yaml"},{id: "115c-d112-5ce5-a7e8",name: "storage-complextypes.yaml",type: "file",path: "model/storage-complextypes.yaml"},{id: "9f51-93b5-4160-0237",name: "storage-simpletypes.yaml",type: "file",path: "model/storage-simpletypes.yaml"},{id: "05a0-d4fb-d461-9697",name: "newfolder",type: "directory",path: "model/newfolder",children: [{id: "e8e5-f0c8-6664-96e1",name: "newname",type: "file",path: "model/newfolder/newname"}]}]
      
    console.log(Array.from(find(data, t => /newn/.test(t))))        
    console.log(Array.from(find(data, matchProperty(/newn/))))
    console.log(Array.from(find(data, hasFileType("yaml"))))
    .as-console-wrapper {max-height: 100% !important; top: 0}

    refinements

    Currently find casts all path segments to strings. Per Scott's comment, we might wish to maintain numeric values of array indices. This can be done by treating arrays as different from objects. This definition also uses generator delegation, yield *, to simplify nested for loops -

    function* find (t, query, path = [])
    { if (query(t)) yield {path, value: t}
      switch (t?.constructor)
      { case Array:
          for (const [k, v] of t.entries())
            yield *find(v, query, [...path, k])
          break
        case Object:
          for (const [k, v] of Object.entries(t))
            yield *find(v, query, [...path, k])
          break
      }
    }
    
    Array.from(find(data, t => /newn/.test(t)))
    
    path value
    [3, "children", 0, "name"] "newname"
    [3, "children", 0, "path"] "model/newfolder/newname"
    data[3]["children"][0]["name"]  // => "newname"
    data[3]["children"][0]["path"]  // => "model/newfolder/newname"
    

    iter

    You might dislike introducing find1 but I only did that to simplify the original answer. In reality this is a generic function to work on any iterable. I typically have an iter module which contains the functions for working with iterables, such as the result of a generator like find -

    // iter.js
    
    const iter = t =>
      t?.[Symbol.iterator]()
    
    function first (t)
    { for (const v of t)
        return v
    }
    
    function toArray (t)
    { const r = []
      for (const v of t)
        r.push(v)
      return r
    }
    
    export { iter, first, toArray }
    

    Having a separate module gives you a barrier of abstraction where you are free to make changes as you see fit. It makes it easier to test things and keeps us from repeating this functionality every time we need it somewhere else in our program. We can import iter wherever it is needed -

    // main.js
    
    import { toArray, first } from "./iter.js"
    
    const data = ...
    
    function* find (...) { ... }
    
    toArray(find(data, t => /newn/.test(t)))
    
    path value
    [3, "children", 0, "name"] "newname"
    [3, "children", 0, "path"] "model/newfolder/newname"
    first(find(data, t => /newn/.test(t)))
    
    path value
    [3, "children", 0, "name"] "newname"

    If you prefer to work in a more object-oriented way, we can write a simple class Iterator that wraps our plain functions -

    // iter.js (continued)
    
    // ...
    
    class Iterator
    { constructor(t) { this.t = iter(t) }
      first() { return first(this.t) }
      toArray() { return toArray(this.t) }
    }
    
    export default Iterator
    

    You now have a dual-purpose module that can be used in functional style or object-oriented style -

    // main.js
    
    import Iterator from "./iter.js"
    
    const data = ...
    
    function* find (...) { ... }
    
    new Iterator(find(data, t => /newn/.test(t))).toArray()
    
    path value
    [3, "children", 0, "name"] "newname"
    [3, "children", 0, "path"] "model/newfolder/newname"
    new Iterator(find(data, t => /newn/.test(t))).first()
    
    path value
    [3, "children", 0, "name"] "newname"

  • answered 2021-05-05 14:59 vincent

    Here is an iterative solution using object-scan. Adds a dependency, but you might find it more legible and maintainable. E.g. searching within multiple fields would be very easy.

    // const objectScan = require('object-scan');
    
    const myData = [{ id: '95c3-1e74-48c7-ec7e', name: 'model.yaml', type: 'file', path: 'model/model.yaml' }, { id: '115c-d112-5ce5-a7e8', name: 'storage-complextypes.yaml', type: 'file', path: 'model/storage-complextypes.yaml' }, { id: '9f51-93b5-4160-0237', name: 'storage-simpletypes.yaml', type: 'file', path: 'model/storage-simpletypes.yaml' }, { id: '05a0-d4fb-d461-9697', name: 'newfolder', type: 'directory', path: 'model/newfolder', children: [{ id: 'e8e5-f0c8-6664-96e1', name: 'newname', type: 'file', path: 'model/newfolder/newname' }] }];
    
    const find = objectScan(['**(^children$).name'], {
      useArraySelector: false,
      rtn: 'parent',
      filterFn: ({ value, context }) => value.includes(context)
    });
    
    console.log(find(myData, 'newn'));
    /* => [ {
      id: 'e8e5-f0c8-6664-96e1',
      name: 'newname',
      type: 'file',
      path: 'model/newfolder/newname'
    } ] */
    .as-console-wrapper {max-height: 100% !important; top: 0}
    <script src="https://bundle.run/object-scan@14.3.0"></script>

    Disclaimer: I'm the author of object-scan