suggested optimization for range()

[lsemprini]

When I was writing find_ge() and find_gt() (see #34) I noticed that range() is essentially a copy of forEach() with a terminating case at the end of the range.

That is, range() will iterate all nodes from the start of the dataset to the low key.

This seems like more work than range() needs to do. range() could avoid going down a node.left if node.key is already large enough that all the nodes in the left sub-branch are guaranteed to have keys less than low

See #34 for some suggested code that could also be used in range()

Here I will take a stab at applying the same logic to range() but I haven't tested this range()...

  /**
   * Walk key range from `low` to `high` inclusive. 
   * Stops if `fn` returns a true value.
   * Walk starts (first callback) at first node >= `low`.
   * Walk ends (no callback) at first node > `high`.
   * If tree was created with !noDuplicates and tree contains 
   * more than one node with the `low` or `high`,
   * range() stops/starts at the first such node.
   * @param{Key}    low
   * @param{Key}    high
   * @param{Function} fn
   * @param{*?}     ctx
   * @return {SplayTree}
   */
  AVLTree.prototype.range = function range (low, high, fn, ctx) {
      var this$1 = this;

    var Q = [];
    var compare = this._comparator;
    var node = this._root, cmp;

    while (Q.length !== 0 || node) {
      if (node) {
        Q.push(node);
// CHANGED CODE STARTS HERE
        /* if ( this._noDuplicates) node.key >  node.left subtree nodes
         * if (!this._noDuplicates) node.key >= node.left subtree nodes
         */
        cmp = compare(node.key, low);
        if (this._noDuplicates && cmp <= 0)
          /* node.key <= low, so node.left subtree
           * cannot contain the node we want to start at.
           * if node.key === low, we can still skip node.left
           * because tree contains no duplicates.
           */
          node = null;
        else if (!this._noDuplicates && cmp < 0)
          /* node.key < low, so node.left subtree
           * cannot contain the node we want to start at.
           * if node.key === low, we must still examine node.left
           * because tree might contain duplicates and we
           * must start at first node matching low.
           */
          node = null;
        else
// CHANGED CODE ENDS HERE
          node = node.left;
      } else {
        node = Q.pop();
        cmp = compare(node.key, high);
        if (cmp > 0) {
          break;
        } else if (compare(node.key, low) >= 0) {
          if (fn.call(ctx, node)) { return this$1; } // stop if smth is returned
        }
        node = node.right;
      }
    }
    return this;
  };

[paulocoghi]

Would be interesting to see this improvement applied