#
sub ins {
   my $s = shift ;
   my $at = shift ;
   my $c = shift ;
   my $r = $s ;
   substr($r, $at, 0) = $c ;
   return $r ;
}
sub del {
   my $s = shift ;
   my $at = shift ;
   my $r = $s ;
   substr($r, $at, 1) = '' ;
   return $r ;
}
my $teststr = 'abcdefghijklmnopqrstuvwxyz' ;
sub doit {
   my $cmd = shift ;
   my $str = shift ;
   my $r = $str ;
   if ($cmd->[0] eq 'D') {
      substr($r, $cmd->[1], 1) = '' ;
   } else {
      substr($r, $cmd->[1], 0) = $cmd->[2] ;
   }
   return $r ;
}
sub testme {
   my $a1 = shift ;
   my $a2 = shift ;
   my $a3 = shift ;
   my $a4 = shift ;
   my $t1 = doit($a2, doit($a1, $teststr)) ;
   my $t2 = doit($a4, doit($a3, $teststr)) ;
   if ($t1 ne $t2) {
      print "Doing @{$a1} @{$a2} gives $t1\n" ;
      print "Doing @{$a3} @{$a4} gives $t2\n" ;
      die "Mismatch" ;
   }
}
#   I a x; I b y:
#      a >= b:  I b y; I a+1 x
#      a < b:   I b-1 y; I a x
testme(['I', 10, 'A'], ['I', 5, 'B'], ['I', 5, 'B'], ['I', 11, 'A']) ;
testme(['I', 5, 'A'], ['I', 5, 'B'], ['I', 5, 'B'], ['I', 6, 'A']) ;
testme(['I', 5, 'A'], ['I', 10, 'B'], ['I', 9, 'B'], ['I', 5, 'A']) ;
#   D a; D b:
#      a <= b:   D b+1; D a
#      a > b:   D b; D a-1
testme(['D', 5], ['D', 10], ['D', 11], ['D', 5]) ;
testme(['D', 5], ['D', 5], ['D', 6], ['D', 5]) ;
testme(['D', 10], ['D', 5], ['D', 5], ['D', 9]) ;
#   I a x; D b:
#      a == b:  (no swap)
#      a < b:  D b-1; I a x
#      a > b:  D b; I a-1 x
testme(['I', 5, 'A'], ['D', 10], ['D', 9], ['I', 5, 'A']) ;
testme(['I', 10, 'A'], ['D', 5], ['D', 5], ['I', 9, 'A']) ;
#   D a; I b x:
#      a < b:   I b+1 x; D a
#      a >= b:  I b x; D a+1
testme(['D', 5], ['I', 10, 'A'], ['I', 11, 'A'], ['D', 5]) ;
testme(['D', 5], ['I', 5, 'A'], ['I', 5, 'A'], ['D', 6]) ;
testme(['D', 10], ['I', 5, 'A'], ['I', 5, 'A'], ['D', 11]) ;
#
#   Okay now generate a random editing sequence.
#
my @e = () ;
my $n = shift || 10 ;
my $m = shift || 1000 ;
my $bad = shift ; # add 'bad' if you want us to modify the program
#my $mm = 1 + $m + $n ;
#print "$mm\n" ;
for ($i=0; $i<$n; $i++) {
   my $ind = 1 + int rand $m ;
   if (int rand 2) {
      push @e, ['D', $ind] ;
   } else {
      $ch = chr(ord('A')+int rand 26) ;
      push @e, ['I', $ind, $ch] ;
   }
}
for (@e) {
   print "@{$_}\n" ;
}
print "E\n" ;
my $t1 = $teststr ;
if ($m <= 10000 && !$bad) {
   $t1 .= $t1 while length($t1) <= 10 * $m ;
   $a1 = $t1 ;
   $a1 = doit($_, $a1) for @e ;
}
@oe = @e ;
for ($i=0; $i<1000 && $i < 20 * $n; $i++) {
   my $j = int rand (@e-1) ;
   if (0 == int rand (5 * $n)) { # sporadically insert a matching pair
      my $ind = 1 + int rand $m ;
      splice(@e, $j, 0, ['I', $ind, chr(ord('A')+int rand 26)], ['D', $ind]) ;
      next ;
   }
   my $k = $j + 1 ;
   $jcmd = $e[$j][0] ;
   $kcmd = $e[$k][0] ;
   $jind = $e[$j][1] ;
   $kind = $e[$k][1] ;
   if ($jcmd eq 'I' && $kcmd eq 'D' && $jind == $kind) {
      # cannot swap these but we *can* kill them
      if (int rand 2) {
         splice(@e, $j, 2) ;
      }
      next ;
   }
   $t = $e[$j] ;
   $e[$j] = $e[$k] ;
   $e[$k] = $t ;
   if ($jcmd eq 'I') {
      if ($kcmd eq 'I') {
         if ($jind >= $kind) {
            $e[$k][1]++ ;
         } else {
            $e[$j][1]-- ;
         }
      } else {
         if ($jind >= $kind) {
            $e[$k][1]-- ;
         } else {
            $e[$j][1]-- ;
         }
      }
   } else {
      if ($kcmd eq 'I') {
         if ($jind < $kind) {
            $e[$j][1]++ ;
         } else {
            $e[$k][1]++ ;
         }
      } else {
         if ($jind <= $kind) {
            $e[$j][1]++ ;
         } else {
            $e[$k][1]-- ;
         }
      }
   }
}
if ($bad) {
   $e[int rand @e][1] += -1 + 2 * int rand 2 ;
}
for (@e) {
   print "@{$_}\n" ;
}
print "E\n" ;
if ($m <= 10000 && !$bad) {
   $a2 = $t1 ;
   $a2 = doit($_, $a2) for @e ;
   die "Bad result [$a1] [$a2]" if $a1 ne $a2 ;
}