examples/shootout/binarytrees.pir

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