Nested Sets in JavaScript

Question

I created a procedural implementation of the nested set model in JavaScript. The use case for this small library was that the front-end(presented as an MVC) needs to traverse hierarchical data from back-ends.

The library that I created satisfies the following:

• DSL-like architecture, with clear distinction between a tree and a node.
• Searching through the set for a node matching a given partial of it
• Retrieve parents for any given node
• Retrieve children for any given node
• Retrieve descendants for any particular node
• Utility methods determining "what" a node is, given it's coordinates
• A lesser distinguished way of finding siblings (parents[0] -> children = siblings)

The library is divided into two classes.

NestedSetModel is the base class and acts as a starting point for traversing the tree.

It's first function is to order the set by left values ascendantly. This is done for the presumption that descendants are always at a higher index(of the set) than parents. The second function is to create an index of all right values.

var NestedSetModel = function(model) {
 this.model = [];
 this.index = {};
 // sort the set for deterministic order
 model.sort(function(a, b)
 {
 return a.left - b.left;
 });
 var self = this;
 // create an index
 for(var index in model) {
 if (!model.hasOwnProperty(index)) {
 continue;
 }
 this.index[model[index].right] = index;
 }
 for(var entry in model) {
 if (!model.hasOwnProperty(entry)) {
 continue;
 }
 try {
 var node = new NestedSetModelNode(model[entry], model, this.index);
 this.model.push(node);
 } catch(e) {}
 }
 return this;
}
NestedSetModel.prototype.compareNodes = function(a, b, strict) {
 var strict = strict || false;
 if (a === b) {
 return true;
 }
 var keys = [
 Object.keys(a),
 Object.keys(b)
 ];
 if (strict && keys[0].length !== keys[1].length) {
 return false;
 }
 for (var i = 0; i <= keys[1].length; i++) {
 var prop = keys[1][i];
 if (a[prop] !== b[prop]) {
 return false;
 }
 }
 if (!strict) {
 return true;
 }
 for (var prop in keys[0]) {
 if (b[prop] !== undefined && a[prop] !== b[prop]) {
 return false;
 }
 if (typeof a[prop] === 'object'
 && this.compareNodes(a[prop], b[prop], true) === false) {
 return false
 }
 }
 return true;
}
NestedSetModel.prototype.find = function(partial, strict) {
 for (var key in this.model) {
 if (!this.model.hasOwnProperty(key)) {
 continue;
 } else if (this.compareNodes(this.model[key], partial, strict)) {
 return new NestedSetModelNode(this.model[key], this.model, this.index);
 }
 }
}

The second and final class is NestedSetModelNode. It contains methods related to relationships between nodes. I've omitted methods that perform rudementy calculations.

var NestedSetModelNode = function(node, model, index) {
 var self = this;
 Object.keys(node).forEach(function(prop) {
 self[prop] = node[prop];
 });
 this.model = model;
 this.index = index;
}
NestedSetModelNode.prototype.parents = function() {
 var parents = [];
 var self = this;
 this.model.map(function(node) {
 if (self.left > node.left && self.right < node.right) {
 parents.push(new NestedSetModelNode(node, self.model, self.index));
 }
 });
 return parents;
}
NestedSetModelNode.prototype.descendants = function() {
 var descendants = [];
 var num_items = Math.floor((this.right - this.left) / 2);
 for(var right in this.index) {
 if (right < this.right && right > this.left) {
 var node = this.model[this.index[right]];
 descendants.push(new NestedSetModelNode(node, this.model, this.index));
 }
 }
 return descendants;
}
NestedSetModelNode.prototype.children = function() {
 var children = [];
 var right = this.right - 1;
 while(true) {
 if (right === this.left) {
 break;
 }
 var child = this.model[this.index[right]];
 children.push(new NestedSetModelNode(child, this.model, this.index));
 right = child.left - 1;
 }
 return children.reverse();
}

Semantics aside, what improvements can I implement that will make this library more consistent and practical(performance wise) to compute client-side?

So far, I have created an index tree of right values for optimization of r - l > 1 lookups. This increases performance, as only half the amount of objects are actually traversed and compared.

Answer 1

Interesting code,

the first thing that comes to mind is that forEachand map are slower than for loops, so you might want to consider converting those statements to for loops.

the second thing is that I assume you query several times these data structures, if that is the case then the node should know who is/are the parents and who is/are the children, it does not make sense to traverse (partially) the model every time to figure that out.

Other than that

• This

  // create an index
  for(var index in model) {
   if (!model.hasOwnProperty(index)) {
   continue;
   }
   this.index[model[index].right] = index;
  }
  

  could be

  // create an index
  for(var index in model) {
   if (model.hasOwnProperty(index)) {
   this.index[model[index].right] = index;
   }
  } 
  

  by avoiding the continue statement

• This

  try {
   var node = new NestedSetModelNode(model[entry], model, this.index);
   this.model.push(node);
  } catch(e) {}
  

  intrigues me, I don't see what could go wrong with this code that you need a try/catch, even more intriguing is that you fail silently here, potentially providing wrong query results later in the game

• This part could be faster for strict comparisons:

  for (var i = 0; i <= keys[1].length; i++) {
   var prop = keys[1][i];
   if (a[prop] !== b[prop]) {
   return false;
   }
  }
  if (!strict) {
   return true;
  }
  for (var prop in keys[0]) {
   if (b[prop] !== undefined && a[prop] !== b[prop]) {
   return false;
   }
   if (typeof a[prop] === 'object'
   && this.compareNodes(a[prop], b[prop], true) === false) {
   return false
   }
  }
  

  What you do here every time you check for strict comparison is comparing b with a using != and then again comparing a with b using !==. Since you know for strict comparison that the key count is the same, this is overkill. Furthermore I have doubts on (b[prop] !== undefined && a[prop] !== b[prop]) if the value of b[prop] is undefined and the value of a[prop] is not undefined, then the comparison should be false. Furthermore I am not sure why you this.compareNodes in case of an object, if a[prop] === b[prop], then the nodes cannot be different because it is the same object (as I understand it), if you want to really compare two different objects for the same properties, then that should should be before the !== check.

  I would counter propose something like this:

  if (!strict) {
   for (var prop in keys[1]) { //I still wonder, why 1, not 0?
   if (b[prop] != a[prop]) {
   return false;
   }
   } 
  } else {
   for (var prop in keys[0]) {
   if (typeof a[prop] == 'object') {
   if( !this.compareNodes(a[prop], b[prop], true)) {
   return false;
   }
   } else if (a[prop] !== b[prop]) {
   return false;
   }
   }
  }
  //We made it thru, a and b are equal (enough)
  return true;
  

• Perhaps consider renaming NestedSetModel.prototype.find to findFirst, since it only returns the first match

• This

  var self = this;
  Object.keys(node).forEach(function(prop) {
   self[prop] = node[prop];
  });
  

  only needs self because of the forEach, from a style/performance perspective you could avoid this by going to a faster for loop.

• This

  this.model.map(function(node) {
   if (self.left > node.left && self.right < node.right) {
   parents.push(new NestedSetModelNode(node, self.model, self.index));
   }
   });
  

  utilizes map which builds an array for you, if you are not going to use the results of map, then you should use forEach, and since you are interested in speed, you should use a simple for loop.

• On the whole I dont get your data structur with left and right, I would have loved to see a small example with data

• I also don't get the difference between children and descendants unless you mean descendants also include grandchildren etc. I think you could find a better name than descendants.

• An excellent point of @Megawac, which I completely missed is that using for .. in is considered very bad practice for arrays. If you simply use the regular for loop then that will be faster because you no longer need check hasOwnProperty every single time.

• megawac: no mention of for .. in on arrays all over the place?
• David Harkness: With so much advice leaning towards performance (which was sought), store the length of arrays before traversing them in traditional for loops. However, I'd start with the more readable forEach et al and switch only after profiling reveals a problem.