binarytree.hh

<?hh
ini_set('memory_limit','2048M');
$start = microtime(true);
/* The Computer Language Benchmarks Game
   http://benchmarksgame.alioth.debian.org/

   contributed by Peter Baltruschat
   modified by Levi Cameron
   modified by Craig Russell
*/

class Tree {
   public num $i = 0;
   public ?Tree $l = null;
   public ?Tree $r = null;

   public function __construct(num $item, num $depth) {
      $this->i = $item;
      if ($depth) {
         $this->l = new Tree($item * 2 - 1, --$depth);
         $this->r = new Tree($item * 2, $depth);
      }
   }

   public function check(): num {
      return $this->i
         + ($this->l !== null ? ($this->l->l === null ? $this->l->check() : $this->l->i) : 0)
         - ($this->r !== null ? ($this->r->l === null ? $this->r->check() : $this->r->i) : 0);
   }
}

function main(int $argc, array<string> $argv) : void {
   $minDepth = 4;

   $n = $argc == 2 ? (int) $argv[1] : 1;
   $maxDepth = $minDepth + 2 > $n ? $minDepth + 2 : $n;
   $stretchDepth = $maxDepth + 1;

   $stretch = new Tree(0, $stretchDepth);
   printf("stretch tree of depth %d\t check: %d\n", $stretchDepth, $stretch->check());
   unset($stretch);

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

   $iterations = 1 << $maxDepth;
   do
   {
      $check = 0;
      for($i = 1; $i <= $iterations; ++$i)
      {
         $check += (new Tree($i, $minDepth))->check()
            + (new Tree(-$i, $minDepth))->check();
      }

      printf("%d\t trees of depth %d\t check: %d\n",
         $iterations<<1, $minDepth, $check);

      $minDepth += 2;
      $iterations >>= 2;
   }
   while($minDepth <= $maxDepth);

   printf("long lived tree of depth %d\t check: %d\n",
         $iterations<<1, $minDepth, $check);

      $minDepth += 2;
      $iterations >>= 2;
   }
   while($minDepth <= $maxDepth);

   printf("long lived tree of depth %d\t check: %d\n",
      $maxDepth, $longLivedTree->check());
}

main($argc, $argv);
$time_elapsed_us = microtime(true) - $start;
printf($time_elapsed_us);