Recursive JavaScript function to locate an object by its UID

bob.mazzo Source

I'm having an issue returning the element which has been found in this hierarchical tree. For example, if my selected item is:

{
 "UID": 49,
 "GUID": "",
 "LocationName": "Doctor Smith's Office",

 "LocationType": {
    "UID": 2,
    "LocationTypeName": "Practice",
    "Description": "other location"
 }
}

I will match up the UID to the below array of objects.

{
  UID: 2,
  GUID: "",
  LocationName: "USA",
  ParentLocation: null,
  subs: [{
	UID: 42,
	GUID: "",
	LocationName: "New Jersey",
	Description: "",
	subs: [{
		UID: 3,
		GUID: "",
		LocationName: "Essex County",
		ParentLocation: null,
		"subs":[
			UID: 4,
			LocationName: "Newark",
			ParentLocation: 3,
			"subs": [
				{
					"UID": 49,
					"GUID": "",
					"LocationName": "Doctor Smith's Office",
													
					"LocationType": {
						"UID": 2,
						"LocationTypeName": "Practice",
						"Description": "other location"
					},                                    
					"subs": [
						{
							"HostID": 38,
							"HostName": "Ocean Host",
						}
					]
				}
			]
		]
	  }                  
	]
  }]
};

let foundItem = this.findInTreeView(this.treeviewData[0], node.selectedNode);

// find selected node in treeview nav
	// param: data - the treeview dataset
	// param: selected - the selected node to be searched for in param 'data'
	findInTreeView(data: any, selected: any )	{		
		let found;
		if (this.foundInTree(data, selected)) {			
			return data;
		}
		let elem;
		let ary = data.subs;
		for (var i=0; i < ary.length; i++) {
			elem = ary[i];
			if (this.foundInTree(elem, selected)) {		
                // *** PROBLEM: If func has return true, I want to return the 'elem' object.	
				return elem;
			}
		}
		for (var i=0; i < ary.length; i++) {
			elem = ary[i];
			if (elem.subs !== undefined) { 
				// recurse subs array
				let found = this.findInTreeView(elem, selected); 
				if (found) {
					return elem;
				}
			}
		}	
		//return elem;		
	}
  
  foundInTree(treeItem, node) {
		if (treeItem.UID === node.UID) {
			return true;			
		}
		else {
			return false;
		}
	}

javascriptrecursion

Answers

answered 2 months ago CertainPerformance #1

It would be far easier to use a recursive reduce function, like this:

const input={UID:2,GUID:"",LocationName:"USA",ParentLocation:null,subs:[{UID:42,GUID:"",LocationName:"New Jersey",Description:"",subs:[{UID:3,GUID:"",LocationName:"Essex County",ParentLocation:null,"subs":[{UID:4,LocationName:"Newark",ParentLocation:3,"subs":[{"UID":49,"GUID":"","LocationName":"Doctor Smith's Office","LocationType":{"UID":2,"LocationTypeName":"Practice","Description":"other location"},"subs":[{"HostID":38,"HostName":"Ocean Host",}]}]}]}]}]};

const findUIDObj = (uid, parent) => {
  const { UID, subs } = parent;
  if (UID === uid) {
    const { subs, ...rest } = parent;
    return rest;
  }
  if (subs) return subs.reduce((found, child) => found || findUIDObj(uid, child), null);
};
console.log(findUIDObj(49, input))

answered 2 months ago Nina Scholz #2

You could use an explicit function which searches for the wanted UID.

function find(array, UID) {
    var object;
    array.some(o => {
        if (o.UID === UID) {
            return object = o;
        }
        return object = find(o.subs, UID);
    });
    return object;
}

var object = { UID: 2, GUID: "", LocationName: "USA", ParentLocation: null, subs: [{ UID: 42, GUID: "", LocationName: "New Jersey", Description: "", subs: [{ UID: 3, GUID: "", LocationName: "Essex County", ParentLocation: null, subs: [{ UID: 4, LocationName: "Newark", ParentLocation: 3, subs: [{ UID: 49, GUID: "", LocationName: "Doctor Smith's Office", LocationType: { UID: 2, LocationTypeName: "Practice", Description: "other location" }, subs: [{ HostID: 38, HostName: "Ocean Host", }] }] }] }] }] };

console.log(find([object], 49));
.as-console-wrapper { max-height: 100% !important; top: 0; }

answered 2 months ago Scott Sauyet #3

One way to do this is to write a fairly generic version of a tree-finding function, and then configure it for your specific problem. Here we choose to test by matching on a supplied UID, we descend into children by looking at the subs property, and we convert the result by stripping out the subs property:

const searchTreeDF = (kids, test, convert, node) => test(node) // depth-first search
  ? convert(node) 
  : (kids(node) || []).reduce(
      (found, child) => found || searchTreeDF(kids, test, convert, child), 
      false
  )

const subs = node => node.subs
const matchId = (uid) => (item) => item.UID === uid
const convert = ({subs, ...rest}) => ({...rest})

const findUid = (uid, tree) => searchTreeDF(subs, matchId(uid), convert, tree)
// ...
const tree = {"GUID": "", "LocationName": "USA", "ParentLocation": null, "UID": 2, "subs": [{"Description": "", "GUID": "", "LocationName": "New Jersey", "UID": 42, "subs": [{"GUID": "", "LocationName": "Essex County", "ParentLocation": null, "UID": 3, "subs": [{"LocationName": "Newark", "ParentLocation": 3, "UID": 4, "subs": [{"GUID": "", "LocationName": "Doctor Smith's Office", "LocationType": {"Description": "other location", "LocationTypeName": "Practice", "UID": 2}, "UID": 49, "subs": [{"HostID": 38, "HostName": "Ocean Host"}]}]}]}]}]}


console.log(findUid(49, tree))

But if we didn't want to pass in the UID directly, but instead wanted to pass in an element that has its own UID property, we could write

const matchElem = (elem) => (item) => elem.UID === item.UID

and then do this:

const findUid2 = (elem, tree) => searchTreeDF(subs, matchElem(elem), convert, tree)
// ...
findUid2({UID: 49}, tree)

Or if we wanted to not convert the result, and keep the subs property, we could just supply an identity function for convert:

const findUid = (uid, tree) => searchTreeDF(subs, matchId(uid), x => x, tree)

Or we could mix and match as we please. Also note that the configuration does not have to use named functions. We could just as easily write

const findUid = (uid, tree) => searchTreeDF(
  node => node.subs || [], 
  (item) => item.UID === uid,
  ({subs, ...rest}) => ({...rest}), 
  tree
)

Generic functions are not always the right answer. But they can help separate out those things that change from the more basic algorithm we're writing. I think in this case it helps make things more maintainable.

comments powered by Disqus