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 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 --------------------------------------------------