| 1 | #! /usr/bin/python |
| 2 | ### -*-python-*- |
| 3 | ### |
| 4 | ### Generate input script and expected output for dynamic array testing. |
| 5 | |
| 6 | import sys as SYS |
| 7 | import random as R |
| 8 | |
| 9 | if SYS.version_info >= (3,): xrange = range |
| 10 | |
| 11 | ###-------------------------------------------------------------------------- |
| 12 | ### Command-line parsing. |
| 13 | |
| 14 | SYS.argv[0:1] = [] |
| 15 | def arg(default = None): |
| 16 | if len(SYS.argv): |
| 17 | r = SYS.argv[0] |
| 18 | SYS.argv[0:1] = [] |
| 19 | return r |
| 20 | else: |
| 21 | return default |
| 22 | |
| 23 | R.seed(None) |
| 24 | SEED = int(arg(str(R.randrange(0, 1 << 32))), 0) |
| 25 | R.seed(SEED) |
| 26 | |
| 27 | LINES = int(arg(1000)) |
| 28 | |
| 29 | ###-------------------------------------------------------------------------- |
| 30 | ### Initialization. |
| 31 | |
| 32 | SERIAL = 1 |
| 33 | ARRAY = [] |
| 34 | |
| 35 | SCRIPT = open('da.script', 'w') |
| 36 | WIN = open('expout', 'w') |
| 37 | |
| 38 | ###-------------------------------------------------------------------------- |
| 39 | ### Utility functions. |
| 40 | |
| 41 | OPS = [] |
| 42 | def op(weight): |
| 43 | """ |
| 44 | Operation decorator. Add the following function to the operations table, |
| 45 | with the given probability WEIGHT. This works as follows: if TOTAL is the |
| 46 | total of all the WEIGHTs, then this operation has a probability of |
| 47 | WEIGHT/TOTAL of being selected. |
| 48 | """ |
| 49 | def _(cls): |
| 50 | OPS.append((weight, cls)) |
| 51 | return cls |
| 52 | return _ |
| 53 | |
| 54 | def serial(): |
| 55 | """Return the next number in a simple sequence.""" |
| 56 | global SERIAL |
| 57 | SERIAL += 1 |
| 58 | return SERIAL - 1 |
| 59 | |
| 60 | def mkseq(): |
| 61 | """Return a short list of stuff to be added to the array.""" |
| 62 | seq = [serial()] |
| 63 | while R.randrange(0, 4) < 3: seq.append(serial()) |
| 64 | return seq |
| 65 | |
| 66 | def mkseqlen(): |
| 67 | """Return a length of stuff to be removed from the array.""" |
| 68 | n = 1 |
| 69 | while R.randrange(0, 4) < 3: n += 1 |
| 70 | return n |
| 71 | |
| 72 | ###-------------------------------------------------------------------------- |
| 73 | ### The actual operations. |
| 74 | |
| 75 | @op(20) |
| 76 | def op_push(): |
| 77 | n = serial() |
| 78 | SCRIPT.write('push %d\n' % n) |
| 79 | ARRAY.append(n) |
| 80 | @op(20) |
| 81 | def op_pop(): |
| 82 | SCRIPT.write('pop\n') |
| 83 | if not ARRAY: |
| 84 | WIN.write('*UFLOW*\n') |
| 85 | else: |
| 86 | n, = ARRAY[-1:] |
| 87 | ARRAY[-1:] = [] |
| 88 | WIN.write('%d\n' % n) |
| 89 | @op(20) |
| 90 | def op_unshift(): |
| 91 | n = serial() |
| 92 | SCRIPT.write('unshift %d\n' % n) |
| 93 | ARRAY[0:0] = [n] |
| 94 | @op(20) |
| 95 | def op_shift(): |
| 96 | SCRIPT.write('shift\n') |
| 97 | if not ARRAY: |
| 98 | WIN.write('*UFLOW*\n') |
| 99 | else: |
| 100 | n = ARRAY[0] |
| 101 | ARRAY[0:1] = [] |
| 102 | WIN.write('%d\n' % n) |
| 103 | |
| 104 | @op(10) |
| 105 | def op_insert(): |
| 106 | stuff = mkseq() |
| 107 | SCRIPT.write('insert ' + ' '.join(['%d' % i for i in stuff]) + '\n') |
| 108 | ARRAY[0:0] = stuff |
| 109 | @op(10) |
| 110 | def op_append(): |
| 111 | global ARRAY # += is a binding occurrence |
| 112 | stuff = mkseq() |
| 113 | SCRIPT.write('append ' + ' '.join(['%d' % i for i in stuff]) + '\n') |
| 114 | ARRAY += stuff |
| 115 | |
| 116 | @op(20) |
| 117 | def op_delete(): |
| 118 | if len(ARRAY) < LINES/10: return |
| 119 | n = mkseqlen() |
| 120 | SCRIPT.write('delete %d\n' % n) |
| 121 | if n > len(ARRAY): WIN.write('*UFLOW*\n') |
| 122 | else: ARRAY[0:n] = [] |
| 123 | @op(20) |
| 124 | def op_reduce(): |
| 125 | if len(ARRAY) < LINES/10: return |
| 126 | n = mkseqlen() |
| 127 | SCRIPT.write('reduce %d\n' % n) |
| 128 | if n > len(ARRAY): WIN.write('*UFLOW*\n') |
| 129 | else: ARRAY[-n:] = [] |
| 130 | |
| 131 | def mkindex(): |
| 132 | if not ARRAY: ix = 0 |
| 133 | else: ix = R.randrange(0, len(ARRAY)) |
| 134 | while R.randrange(0, 2) < 1: ix += 1 |
| 135 | return ix |
| 136 | |
| 137 | @op(20) |
| 138 | def op_set(): |
| 139 | global ARRAY # += is a binding occurrence |
| 140 | ix, x = mkindex(), serial() |
| 141 | SCRIPT.write('set %d %d\n' % (ix, x)) |
| 142 | if ix >= len(ARRAY): ARRAY += [-1] * (ix - len(ARRAY) + 1) |
| 143 | ARRAY[ix] = x |
| 144 | @op(20) |
| 145 | def op_get(): |
| 146 | ix = mkindex() |
| 147 | SCRIPT.write('get %d\n' % ix) |
| 148 | if ix >= len(ARRAY): WIN.write('*RANGE*\n') |
| 149 | else: WIN.write('%d\n' % ARRAY[ix]) |
| 150 | |
| 151 | @op(10) |
| 152 | def op_first(): |
| 153 | SCRIPT.write('first\n') |
| 154 | if len(ARRAY): WIN.write('%d\n' % ARRAY[0]) |
| 155 | else: WIN.write('*RANGE*\n') |
| 156 | @op(10) |
| 157 | def op_last(): |
| 158 | SCRIPT.write('last\n') |
| 159 | if len(ARRAY): WIN.write('%d\n' % ARRAY[-1]) |
| 160 | else: WIN.write('*RANGE*\n') |
| 161 | |
| 162 | @op(1) |
| 163 | def op_show(): |
| 164 | SCRIPT.write('show\n') |
| 165 | if not ARRAY: WIN.write('*EMPTY*\n') |
| 166 | else: WIN.write(' '.join(['%d' % i for i in ARRAY]) + '\n') |
| 167 | |
| 168 | ###-------------------------------------------------------------------------- |
| 169 | ### Generate the output. |
| 170 | |
| 171 | OPTAB = [] |
| 172 | for p, func in OPS: |
| 173 | OPTAB += [func] * p |
| 174 | for i in xrange(LINES): |
| 175 | OPTAB[R.randrange(0, len(OPTAB))]() |
| 176 | op_show() |
| 177 | |
| 178 | SCRIPT.close() |
| 179 | WIN.close() |
| 180 | open('da.seed', 'w').write('da-gtest seed = %08x\n' % SEED) |
| 181 | |
| 182 | ###----- That's all, folks -------------------------------------------------- |