Dealing with complex objects in JavaScript with walk.js

Let’s imagine we have a complex object such as a person’s social network, represented (via JSON) like so:

{
"name": "Jim",
"age": 21,
"friends": [
{
"name": "Sara",
"age": 23,
"friends":[
{
"name": "Bob",
"age": 45,
"friends":[
// and so on...
]
}
]
},
{
"name": "George",
"age": 22,
"friends":[
// and so on...
]
}
]
}

There are plenty of reasonable operations we may want to run on such a structure, such as:

  1. Calculating the average age of all people in the network
  2. Adding a “hometown” property to each person
  3. Ranking the network by the count of their friends

Writing a single loop wouldn’t cut it, since we don’t know how deep the tree goes. Below I’ll outline a simple tree traversal algorithm for “walking” the tree, and present a framework for conditionally executing custom operations as we go.

Walking the tree

At its heart, traversing the tree is as simple as stepping through each property. If the property is an object, step through its properties. If the property is an array, iterate over the array and step through each of its items. Pseudocode for that looks something like this (grossly simplifying):

function traverse(key, value){
if value == Array:
for item in value:
traverse(key, item)
else if value == Object:
for key2, prop2 in value:
traverse(key2, prop2)
else:
//property is a simple type (string, number)

There are some other attributes we want to know as we traverse the tree. With respect to any given property, we may want to know:

  • If it’s an object, whether the current property is a “root” or not. This is determined by the absence of a parent object.
  • What type each object is (such as “car,” “person,” etc.) This can be determined by defining what types match what keys. For example, “friends” in the example above matches to a type of “person.”
  • What type of container the current property is, and what type of container it is contained by. “Friends” from above is an array and is contained within an object of type “person.”

If we can annotate each node with that data, the three operations outlined above aren’t too difficult:

  1. Calculating the average age of all people in the network: traverse the tree and find all unique instances of type “person,” add their age to the running sum. At the end, divide by the total count of people.
  2. Adding a “hometown” property to each person: traverse the tree and anytime a “person” object is found, look up their hometown in some external data source via a property on that person object (such as name or SSN.) Add the result to the current object.
  3. Ranking the network by the count of their friends: traverse the tree and find all instances of an array of type “person,” defined by a key of “friends,” that exists within a “person” object. Calculate the length of that array, and use that to rank members across the network.

Tree traversal with walk.js

After dealing with this problem at work, I decided to write a small library to help me accomplish these operations seamlessly. The result is walk.js, a small, specialized library for handling object traversal.

The premise is to provide hooks into the traversal process through callback functions. Before and after each property is read/traversed, custom functionality can be run based on whether certain filters are met. Examples of such filters are:

  • Object types, or “classes” (car, person, building)
  • Container types (array, object)
  • Keys (“friends”, “age”)

To see this in action, let’s show how we may run each of the three operations from above with walk.js:

  1. Calculating the average age of all people in the network

Woo, that was easy. I ran this on some test data, the output looks like this:

Person Deanne Malone is 38 years old.
Person Cooper Collins is 37 years old.
Person Delia Conley is 33 years old.
Person Allen Clements is 30 years old.
Person Bridgett Lara is 39 years old.
Person Miles Miller is 26 years old.
Person Hayden Howell is 34 years old.
Person Conley Slater is 39 years old.
Person Natalie Stein is 38 years old.
Person Jessica Nguyen is 29 years old.
Person Velez Cantu is 22 years old.
Person Grace Spears is 20 years old.
Average age of 12 people is 32.083333333333333

2. Adding a “hometown” property to each person

Example output:

Person Peck Burgess is from San Francisco
Person Huff Pennington is from San Francisco
Person Sexton Sims is from Chicago
Person Ortega Richard is from New York
Person Koch Acosta is from Miami
Person Harrell Serrano is from Austin
Person Cooper Collins is from New York
Person Mendez Forbes is from New York
Person Reyes Black is from New York

3. Ranking the network by the count of their friends

Example output:

Friend-count ranking:
1. Miles Miller — 14
2. Bridgett Lara — 13
3. Natalie Stein — 13
4. Allen Clements — 12
5. Velez Cantu — 12
6. Deanne Malone — 11
7. Jessica Nguyen — 11
8. Delia Conley — 10
9. Grace Spears — 10
10. Hayden Howell — 9
11. Conley Slater — 7
12. Cooper Collins — 6

Conclusion

I hope you find this library as useful as I’ve found it so far. Walk.js is freely available on GitHub, where you can read more about its functionality: https://github.com/tckerrpl/walk.

Feel free to use it as you please and leave comments/suggestions!

Note: this post was written using the 0.0.1 release.

Show your support

Clapping shows how much you appreciated Tom Kerr’s story.