OpenEuphoria

Binary Trees

Binary Trees Euphoria

-- The Computer Language Shootout Benchmarks 
--  http://shootout.alioth.debian.org/ 
--  
--  Converted to Euphoria by Jason Gade 
--  run: exu binary-trees.ex [N=0] 
 
without warning 
without type_check 
 
include std/get.e  
 
constant LEFT =  1, 
         RIGHT = 2, 
         ITEM =  3 
          
constant NULL = {}  
 
 
 
function ItemCheck(sequence tree) 
 
    if equal(tree[LEFT], NULL) then  
        return tree[ITEM] 
    else  
        return tree[ITEM] + ItemCheck(tree[LEFT]) - ItemCheck(tree[RIGHT]) 
 
    end if 
 
end function -- ItemCheck 
 
 
 
function BottomUpTree(atom item, integer depth) 
 
    if depth > 0 then 
        return {BottomUpTree(2 * item - 1, depth - 1),  
                BottomUpTree(2 * item, depth - 1), 
                item} 
    else 
        return {NULL, NULL, item} 
     
    end if 
end function -- BottomUpTree 
 
 
 
procedure main(sequence argv) 
 
    atom iterations, check 
    integer minDepth, maxDepth, stretchDepth 
    sequence stretchTree, longLivedTree, tempTree 
    object N 
     
    if length(argv) >= 3 then 
        N = value(argv[3]) 
        N = N[2] 
    else 
        N = 0 
    end if 
 
    minDepth = 4 
 
    if (minDepth + 2) > N then 
        maxDepth = minDepth + 2 
    else 
        maxDepth = N 
    end if 
 
    stretchDepth = maxDepth + 1 
 
    stretchTree = BottomUpTree(0, stretchDepth) 
    printf(1, "stretch tree of depth %d\t  check: %d\n", 
              {stretchDepth, 
              ItemCheck(stretchTree)}) 
 
    stretchTree = {}  
 
    longLivedTree = BottomUpTree(0, maxDepth) 
 
    for depth = minDepth to maxDepth by 2 do 
 
       iterations = power(2, maxDepth - depth + minDepth) 
 
       check = 0 
 
       for i = 1 to iterations do 
 
           tempTree = BottomUpTree(i, depth) 
           check += ItemCheck(tempTree) 
           tempTree = {} 
 
           tempTree = BottomUpTree(-i, depth) 
           check += ItemCheck(tempTree) 
           tempTree = {} 
 
       end for -- i 
 
        printf(1, "%d\t  trees of depth %d\t  check: %d\n", 
                  {iterations * 2, depth, check }) 
 
    end for -- depth 
 
    printf(1, "long lived tree of depth %d\t  check: %d\n", 
              {maxDepth, ItemCheck(longLivedTree)}) 
 
end procedure -- main 
 
 
main(command_line()) 

Binary Trees Python

# The Computer Language Benchmarks Game 
# http://shootout.alioth.debian.org/ 
# 
# contributed by Antoine Pitrou 
# modified by Dominique Wahli 
# modified by Heinrich Acker 
 
import sys 
 
def make_tree(item, depth): 
    if not depth: return item, None, None 
    item2 = item + item 
    depth -= 1 
    return item, make_tree(item2 - 1, depth), make_tree(item2, depth) 
 
def check_tree((item, left, right)): 
    if not left: return item 
    return item + check_tree(left) - check_tree(right) 
 
min_depth = 4 
max_depth = max(min_depth + 2, int(sys.argv[1])) 
stretch_depth = max_depth + 1 
 
print "stretch tree of depth %d\t check:" % stretch_depth, check_tree(make_tree(0, stretch_depth)) 
 
long_lived_tree = make_tree(0, max_depth) 
 
iterations = 2**max_depth 
for depth in xrange(min_depth, stretch_depth, 2): 
 
    check = 0 
    for i in xrange(1, iterations + 1): 
        check += check_tree(make_tree(i, depth)) + check_tree(make_tree(-i, depth)) 
 
    print "%d\t trees of depth %d\t check:" % (iterations * 2, depth), check 
    iterations /= 4 
 
print "long lived tree of depth %d\t check:" % max_depth, check_tree(long_lived_tree) 
	 

Binary Trees Perl

# The Computer Language Benchmarks Game 
# http://shootout.alioth.debian.org/ 
#  
# contributed by Emanuele Zeppieri 
 
sub bottomup_tree { 
    my ($value, $depth) = @_; 
    return $value unless $depth; 
    my $value2 = $value * 2; $depth--; 
    [ bottomup_tree($value2-1, $depth), bottomup_tree($value2, $depth), $value ] 
} 
 
sub check_tree { 
    my ($left, $right, $value) = @{ $_[0] }; 
    $value + ( 
        ref $left ? check_tree($left) - check_tree($right) : $left - $right 
    ) 
} 
 
my $max_depth = shift @ARGV; 
my $min_depth = 4; 
 
$max_depth = $min_depth + 2 if $min_depth + 2 > $max_depth; 
 
my $stretch_depth = $max_depth + 1; 
my $stretch_tree = bottomup_tree(0, $stretch_depth); 
print "stretch tree of depth $stretch_depth\t check: ", 
    check_tree($stretch_tree), "\n"; 
undef $stretch_tree; 
 
my $longlived_tree = bottomup_tree(0, $max_depth); 
 
for ( my $depth = $min_depth; $depth <= $max_depth; $depth += 2 ) { 
    my $iterations = 2 << $max_depth - $depth + $min_depth - 1; 
    my $check = 0; 
     
    foreach (1..$iterations) { 
        $check += check_tree( bottomup_tree(0, $depth) ); 
        $check += check_tree( bottomup_tree(0, $depth) ) 
    } 
     
    print 2*$iterations, "\t trees of depth $depth\t check: ", $check, "\n" 
} 
 
print "long lived tree of depth $max_depth\t check: ", 
    check_tree($longlived_tree), "\n"