nestify.js

/**
 * Iterates over elements until pos of one elements decrease
 * or end of iterator is reached. Iterating over iter changes
 * that iterator on caller side.
 * 
 * @param object i    Last output of iter.next() with first element
 * @param object iter Array iterator to next elements
 * 
 * @return array Tuple of current subtree and last iter.next() object
 *               that break the loop.
 */
function nestifyImpl(i, iter) {
  var output = [];
  var prevVal = i.value; // treat first element as previous element
  while (!i.done) {
    var val = i.value;
    if (val.pos === prevVal.pos) {
      output.push(val);
      prevVal = val;
      i = iter.next();
    } else if (val.pos > prevVal.pos) {
      // start new subtree
      var [children, i] = nestifyImpl(i, iter);
      // here i is the next appropriate element
      // and iter is pointing to next elements along the list
      prevVal.children = children;
    } else {
      break;
    }
  }
  return [output, i];
}

/**
 * @param array input Array of elements
 */
function nestify(input) {
  var iter = input[Symbol.iterator]();
  var [output] = nestifyImpl(
    iter.next(), // first element
    iter // next elements
  );
  return output;
}