chiark - git - mdw - mLib/blob - struct/t/da-gtest.py

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