JavaScript: how to filter deep JSON objects

Question

I have an array of deep JSON objects that look like similarly to this:

var hierarchy = [
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 1",
        "children": [
          {"id": 1, "title": "name 1"},
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      },
      {"title": "subcategory 2",
        "children": [
          {"id": 1, "title": "name 4"}
        ]
      }
    ]
  },
  {
    "title": "category 2",
    "children": [etc. - shortened for brevity]
  }
];

So basically it is a hierarchy - there are categories which can have subcategories which contain objects with some IDs and names. I also have an array of IDs that are related to the deepest hierarchy level (objects with no children) and I need to filter this set of objects in such a way that only (sub)categories that contain defined objects remain.

So for example if I had an array containing two IDs:

var IDs = [2, 3];

the result would be:

var hierarchy = [
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 1",
        "children": [
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      }
    ]
  }
];

i.e. the whole, the whole 'category 2' object removed, the whole 'subcategory 2' removed, object with ID '1' removed.

The problem is that the depth of those objects is variable and unknown - some objects have no children, some have children that also have children etc., any subcategory can can itself have a subcategory and I basically need to find object with no children that have defined IDs and keep the whole path to each of them.

Thank you.

I'd strongly recommend Underscore (or Lodash) for this - it'll make your life a lot easier — Bojangles
– Bojangles, Commented Oct 20, 2013 at 22:48
@Bojangles - Underscore is great, but how exactly is it going to help me with this specific problem? I might be missing something but I don't see any underscore method which does this. Thank you. — keepsea
– keepsea, Commented Oct 21, 2013 at 8:10
Sorry, I was on my phone and didn't read the question properly. I saw lots of complex object iteration instantly thought of underscore — Bojangles
– Bojangles, Commented Oct 21, 2013 at 8:48

Mike Edwards · Accepted Answer · 2013-10-21 17:52:24Z

6

Basically, perform a depth first traversal of your tree invoking a callback function on each node. If that node is a leaf node and it's ID appears in your list then clone the branch that leads to that leaf, but don't re-clone any part of the branch that was already cloned.

Once you have constructed the partial and filtered copy of your tree you need to cleanup the original. I mutated the original tree in the process for book-keeping purposes - tracking which branches had already been cloned.

Edit: modified code to filter list of trees instead of just a single tree

var currentPath = [];

function depthFirstTraversal(o, fn) {
    currentPath.push(o);
    if(o.children) {
        for(var i = 0, len = o.children.length; i < len; i++) {
            depthFirstTraversal(o.children[i], fn);
        }
    }
    fn.call(null, o, currentPath);
    currentPath.pop();
}

function shallowCopy(o) {
    var result = {};
    for(var k in o) {
        if(o.hasOwnProperty(k)) {
            result[k] = o[k];
        }
    }
    return result;
}

function copyNode(node) {
    var n = shallowCopy(node);
    if(n.children) { n.children = []; }
    return n;
}

function filterTree(root, ids) {
    root.copied = copyNode(root); // create a copy of root
    var filteredResult = root.copied;

    depthFirstTraversal(root, function(node, branch) {
        // if this is a leaf node _and_ we are looking for its ID
        if( !node.children && ids.indexOf(node.id) !== -1 ) {
            // use the path that the depthFirstTraversal hands us that
            // leads to this leaf.  copy any part of this branch that
            // hasn't been copied, at minimum that will be this leaf
            for(var i = 0, len = branch.length; i < len; i++) {
                if(branch[i].copied) { continue; } // already copied

                branch[i].copied = copyNode(branch[i]);
                // now attach the copy to the new 'parellel' tree we are building
                branch[i-1].copied.children.push(branch[i].copied);
            }
        }
    });

    depthFirstTraversal(root, function(node, branch) {
        delete node.copied; // cleanup the mutation of the original tree
    });

    return filteredResult;
}

function filterTreeList(list, ids) {
    var filteredList = [];
    for(var i = 0, len = list.length; i < len; i++) {
        filteredList.push( filterTree(list[i], ids) );
    }
    return filteredList;
}

var hierarchy = [ /* your data here */ ];
var ids = [1,3];

var filtered = filterTreeList(hierarchy, ids);

edited Oct 21, 2013 at 17:52

answered Oct 20, 2013 at 23:07

Mike Edwards

3,77120 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

keepsea Over a year ago

Thank you Mike, but I am not sure I get how this is supposed to work. Especially that part where you create root.copied - root is supposed to be the top level of the data hierarchy, which is an array with multiple objects that have children in them, right? I am probably missing something.

Mike Edwards Over a year ago

Reviewing your code again I see that you are processing a list of trees, while my code processes a single tree. Wrapping the code in a for loop to traverse the list should do it. See my edit above.

Yuri Gor · Accepted Answer · 2019-03-07 22:52:45Z

1

You can use filterDeep method from deepdash extension for lodash:

var obj = [{/* get Vijay Jagdale's source object as example */}];
var idList = [2, 3];
var found = _.filterDeep(
  obj,
  function(value) {
    return _.indexOf(idList, value.id) !== -1;
  },
  { tree: true }
);

filtrate object will be:

[ { title: 'category 1',
    children:
     [ { title: 'subcategory 11',
         children:
          [ { id: 2, title: 'name 2' },
            { id: 3, title: 'name 3' } ] } ] },
  { title: 'category 2',
    children:
     [ { title: 'subcategory 21',
         children: [ { id: 3, title: 'name cat2sub1id3' } ] } ] } ]

Here is the full working test for your use case

edited Mar 7, 2019 at 22:52

answered Jan 15, 2019 at 18:01

Yuri Gor

1,4931 gold badge15 silver badges28 bronze badges

Comments

Vijay Jagdale · Accepted Answer · 2015-11-23 21:34:30Z

Although this is an old question I will add my 2 cents. The solution requires a straightforward iteration through the loops, subloops etc. and then compare IDs and build the resultant object. I have pure-javascript and jQuery solution. While the pure javascript works for the example above, I would recommend the jQuery solution, because it is more generic, and does a "deep copy" of the objects, in case you have large and complex objects you won't run into bugs.

function jsFilter(idList){
  var rsltHierarchy=[];
  for (var i=0;i<hierarchy.length;i++) {
    var currCatg=hierarchy[i];
    var filtCatg={"title":currCatg.title, "children":[]};
    for (var j=0;j<currCatg.children.length;j++) {
  	var currSub=currCatg.children[j];
  	var filtSub={"title":currSub.title, "children":[]}
  	for(var k=0; k<currSub.children.length;k++){
  		if(idList.indexOf(currSub.children[k].id)!==-1)
  		   filtSub.children.push({"id":currSub.children[k].id, "title":currSub.children[k].title});
  	}
  	if(filtSub.children.length>0)
  		filtCatg.children.push(filtSub);
    }
    if(filtCatg.children.length>0)
  	rsltHierarchy.push(filtCatg);
  }
  return rsltHierarchy;
}

function jqFilter(idList){
  var rsltHierarchy=[];
  $.each(hierarchy, function(index,currCatg){
      var filtCatg=$.extend(true, {}, currCatg);
      filtCatg.children=[];
  	$.each(currCatg.children, function(index,currSub){
        var filtSub=$.extend(true, {}, currSub);
  	  filtSub.children=[];
  	  $.each(currSub.children, function(index,currSubChild){
  		if(idList.indexOf(currSubChild.id)!==-1)
  		  filtSub.children.push($.extend(true, {}, currSubChild));
        });
  	  if(filtSub.children.length>0)
  		filtCatg.children.push(filtSub);
      });
      if(filtCatg.children.length>0)
  	  rsltHierarchy.push(filtCatg);
  });
  return rsltHierarchy;
}

//Now test the functions...
var hierarchy = eval("("+document.getElementById("inp").value+")");
var IDs = eval("("+document.getElementById("txtBoxIds").value+")");

document.getElementById("oupJS").value=JSON.stringify(jsFilter(IDs));
$(function() {
   $("#oupJQ").text(JSON.stringify(jqFilter(IDs)));
});

#inp,#oupJS,#oupJQ {width:400px;height:100px;display:block;clear:all}
#inp{height:200px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.11.1/jquery.min.js"></script>

ID List: <Input id="txtBoxIds" type="text" value="[2, 3]">

<p>Input:
<textarea id="inp">[
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 11",
        "children": [
          {"id": 1, "title": "name 1"},
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      },
      {"title": "subcategory 12",
        "children": [
          {"id": 1, "title": "name 4"}
        ]
      }
    ]
  },
  {
    "title": "category 2",
    "children": [
      {"title": "subcategory 21",
        "children": [
          {"id": 3, "title": "name cat2sub1id3"},
          {"id": 5, "title": "name cat2sub1id5"}
        ]
      },
      {"title": "subcategory 22",
        "children": [
          {"id": 6, "title": "name cat2sub2id6"},
          {"id": 7, "title": "name cat2sub2id7"}
        ]
      }
    ]
  }
]</textarea>

<p>Pure-Javascript solution results:
<textarea id="oupJS"></textarea>

<p>jQuery solution results:
<textarea id="oupJQ"></textarea>

vincent · Accepted Answer · 2021-01-11 19:38:10Z

I'd not reinvent the wheel. We use object-scan for most of our data processing now and it solves your question nicely. Here is how

// const objectScan = require('object-scan');

const filter = (input, ids) => {
  objectScan(['**[*]'], {
    filterFn: ({ value, parent, property }) => {
      if (
        ('id' in value && !ids.includes(value.id))
        || ('children' in value && value.children.length === 0)
      ) {
        parent.splice(property, 1);
      }
    }
  })(input);
};

const hierarchy = [ { title: 'category 1', children: [ { title: 'subcategory 1', children: [ { id: 1, title: 'name 1' }, { id: 2, title: 'name 2' }, { id: 3, title: 'name 3' } ] }, { title: 'subcategory 2', children: [ { id: 1, title: 'name 4' } ] } ] }, { title: 'category 2', children: [] } ];

filter(hierarchy, [2, 3]);

console.log(hierarchy);
// => [ { title: 'category 1', children: [ { title: 'subcategory 1', children: [ { id: 2, title: 'name 2' }, { id: 3, title: 'name 3' } ] } ] } ]

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

<script src="https://bundle.run/[email protected]"></script>

Disclaimer: I'm the author of object-scan

Collectives™ on Stack Overflow

JavaScript: how to filter deep JSON objects

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related