binary_trees.lox

class $Tree {
  $init($item, $depth) {
    this.$item = $item;
    this.$depth = $depth;
    if ($depth > 0) {
      var $item2 = $item + $item;
      $depth = $depth - 1;
      this.$left = $Tree($item2 - 1, $depth);
      this.$right = $Tree($item2, $depth);
    } else {
      this.$left = nil;
      this.$right = nil;
    }
  }

  $check() {
    if (this.$left == nil) {
      return this.$item;
    }

    return this.$item + this.$left.$check() - this.$right.$check();
  }
}

var $minDepth = 4;
var $maxDepth = 14;
var $stretchDepth = $maxDepth + 1;

var $start = $clock();

print "stretch tree of depth:";
print $stretchDepth;
print "check:";
print $Tree(0, $stretchDepth).$check();

var $longLivedTree = $Tree(0, $maxDepth);

// iterations = 2 ** maxDepth
var $iterations = 1;
var $d = 0;
while ($d < $maxDepth) {
  $iterations = $iterations * 2;
  $d = $d + 1;
}

var $depth = $minDepth;
while ($depth < $stretchDepth) {
  var $check = 0;
  var $i = 1;
  while ($i <= $iterations) {
    $check = $check + $Tree($i, $depth).$check() + $Tree(-$i, $depth).$check();
    $i = $i + 1;
  }

  print "num trees:";
  print $iterations * 2;
  print "depth:";
  print $depth;
  print "check:";
  print $check;

  $iterations = $iterations / 4;
  $depth = $depth + 2;
}

print "long lived tree of depth:";
print $maxDepth;
print "check:";
print $longLivedTree.$check();
print "elapsed:";
print $clock() - $start;