Javascript Iterators and Generators: Dream Comes True

This article will present two ways to iterate over trees thanks to iterators and generators.


Context

Used to program with iterators and generators in Python or Ruby, tired of Javascript loops, I thought it was time to dive in the next generation of Javascript.

We'll handle trees implemented with a children relationship between nodes.

We'll code an ES6 iterator to iterate depth-first our trees, then an ES7 generator.

Setup

We need to install Node.js then babel:

$ node -v
v2.2.1  
$ npm install -g babel
$ npm install moment

Create our first tree

First, we need a simple program to generate a tree:

import moment from 'moment';

const MAX_NODES = 1000;  
const MAX_CHILD = 7;  
const MAX_DEPTH = 10;

class Node{  
  constructor({id, title} = {}){
    this.id = id;
    this.title = title;
  }

  isLeaf(){
    return !((this.children || []).length);
  }

  count(){
    if(this.isLeaf()) return 1;
    return this.children.reduce( (sum, n) => sum + n.count(), 1); 
  }
};


function getRandomInt(min, max) {  
  return Math.floor(Math.random() * (max - min)) + min;
}

function makeTree(maxNodes, maxChild, maxDepth){  
  let root = new Node({id: 0, title: 'root'});

  function makeNodes(nodes, depth, nbNodes){
    let node = nodes[0];
    if(!node) return;
    if(depth <= maxDepth && nbNodes <= maxNodes){
      var nbChildren = Math.min(maxNodes - nbNodes, getRandomInt(depth == 0 ? 1 : 0,maxChild));
      node.children = Array.from(new Array(nbChildren), () => new Node({id:++nbNodes, title: `node${nbNodes}`}));
    }
    makeNodes(nodes.slice(1).concat(node.children), depth, nbNodes);
  }
  makeNodes([root], 0, 1);
  return root;
}

let t0 = moment()  
  , tree = makeTree(MAX_NODES, MAX_CHILD, MAX_DEPTH)
  , t1 = moment() - t0;

console.log(`Generated a tree made of ${tree.count()} nodes in ${t1} ms`);

Nothing special here, makeNodes is a very naive recursive function that tries to build a tree breadth first to balance it.

Iterate over the tree with an iterator

Update the previous Node class with following code:

 // (1)
 // a node is an iterable

  [Symbol.iterator](){
    return this.nodes();
  }

  // depth-first iterator over subtree including this 
  nodes(){
    let done = {} // already crossed nodes
      , node 
      , remainingNodes = [this]; // array to store remaining nodes to handle

    // pass depth-first through the tree til a leaf or an already crossed node is found  
    function iterate(nodes){ 
      let child = nodes[0]; // handle first node
      if(!child) return [null, []]; // This is the end
      if(child.isLeaf() || done[child.id]) return [child, nodes.slice(1)];
      nodes.splice(0, 0, ...child.children); // depth-first
      done[child.id] = true; // mark node as already crossed
      return iterate(nodes); 
    }

    // iterator
    return {
      [Symbol.iterator](){ return this }, // an iterator is iterable
      next(){ // (2)
        [node, remainingNodes] =  iterate(remainingNodes);
        if(node)return {value: node};
        else return {done: true}; // the end ...
      }
    }
  }
  • (1): Node's instances are iterable, Node#nodes() returns an iterator
  • (2): next is defined inside a closure where remainingNodes stores all nodes already seen. Each time iterate meets a leaf or an already crossed node, next will return a node and remainingNodes stores node to explore next.

Iterate over the tree with a generator

Replace upper code by:

  [Symbol.iterator](){
    return this.nodes();
  }

  *nodes(){
    if(this.isLeaf()) return yield this;
    for(let node of this.children) yield *node.nodes();
    yield this;
  }

Fun and obvious, isn't it ?

For sure! But, beyond this beautiful code snippet, iterate over a tree made of 10000 nodes takes arround 500ms with the generator and only 15ms with the iterator (with babel 5.5.6). So beware, Babel is a fantastic tool that must be used carefully before projecting us into the next javascript world !