examples/shootout/binarytrees.pir

   1 #!./parrot -R cgp
   2 # Copyright (C) 2005-2009, Parrot Foundation.
   3 # $Id$
   4 #
   5 # binarytrees.pir N         (N = 16 for shootout)
   6 # by Joshua Isom, modified by Leopold Toetsch
   7 # modified by karl : default value of N=10 to match shootout output
   8
   9 .sub itemcheck
  10         .param pmc node
  11         $I0 = exists node[0]
  12         unless $I0 goto final
  13         .local pmc tmp
  14         tmp = node[0]
  15         unless_null tmp, else
  16         $I0 = node[2]
  17         .return($I0)
  18 else:
  19         # tmp = node[0]
  20         $I0 = itemcheck(tmp)
  21         tmp = node[1]
  22         $I1 = itemcheck(tmp)
  23         $I0 -= $I1
  24         $I1 = node[2]
  25         $I0 += $I1
  26 final:
  27         .return($I0)
  28 .end
  29
  30 .sub bottomuptree
  31         .param int item
  32         .param int dep
  33         .local pmc left, right, tree
  34         .local int item2
  35         unless dep > 0 goto else
  36         item2 = item * 2
  37         $I0 = item2 - 1
  38         dec dep
  39         left = bottomuptree($I0, dep)
  40         right = bottomuptree(item2, dep)
  41         goto endif
  42 else:
  43         null left
  44         null right
  45 endif:
  46         tree = new 'FixedPMCArray'
  47         tree = 3
  48         tree[0] = left
  49         tree[1] = right
  50         tree[2] = item
  51         .return(tree)
  52 .end
  53
  54 .sub main :main
  55         .param pmc argv
  56         .local int argc
  57         .local int N, dep, mindepth, maxdepth, stretchdepth
  58         .local pmc stretchtree, longlivedtree, tmptree
  59
  60         argc = elements argv
  61         N = 10
  62         if argc == 1 goto default
  63         $S0 = argv[1]
  64         N = $S0
  65 default:
  66         mindepth = 4
  67         unless N < 6 goto else
  68         maxdepth = mindepth + 2
  69         goto endif
  70 else:
  71         maxdepth = N
  72 endif:
  73         stretchdepth = maxdepth + 1
  74         $I0 = 0
  75         stretchtree = bottomuptree($I0, stretchdepth)
  76         $I0 = itemcheck(stretchtree)
  77
  78         print "stretch tree of depth "
  79         print stretchdepth
  80         print "\t check: "
  81         print $I0
  82         print "\n"
  83
  84         null stretchtree
  85         $I0 = 0
  86         longlivedtree = bottomuptree($I0, maxdepth)
  87
  88         dep = mindepth
  89 beginfor_1:
  90
  91         .local int i, iterations, check
  92
  93         $N0 = maxdepth - dep
  94         $N0 += mindepth
  95         $N1 = 2
  96         $N2 = pow $N1, $N0
  97         iterations = $N2
  98
  99         check = 0
 100
 101         i = 1
 102         beginfor_2:
 103        noop
 104
 105                         tmptree = bottomuptree(i, dep)
 106                         $I0 = itemcheck(tmptree)
 107                         check += $I0
 108                         $I0 = 0 - i
 109                         tmptree = bottomuptree($I0, dep)
 110                         $I0 = itemcheck(tmptree)
 111                         check += $I0
 112
 113         inc i
 114         if i <= iterations goto beginfor_2
 115         $I0 = iterations * 2
 116         print $I0
 117         print "\t trees of depth "
 118         print dep
 119         print "\t check: "
 120         print check
 121         print "\n"
 122
 123
 124         dep += 2
 125         if dep <= maxdepth goto beginfor_1
 126
 127         $I0 = itemcheck(longlivedtree)
 128         print "long lived tree of depth "
 129         print maxdepth
 130         print "\t check: "
 131         print $I0
 132         print "\n"
 133
 134 .end
 135
 136 # Local Variables:
 137 #   mode: pir
 138 #   fill-column: 100
 139 # End:
 140 # vim: expandtab shiftwidth=4 ft=pir: