#!/usr/local/bin/perl 

# Jason Eisner, 11/24/96

# OT tableau shading.  Input is a LaTeX tableau that may already have
# shading.  We kill any shading and exclamation marks and fix them
# then spit the fixed tableau right back out.  Preserves spacing.
# Input should avoid tab characters.
# 
# Specifically, this script
# - automatically inserts (or moves) the exclamation points
# - changes \unsha to \shade or vice-versa where appropriate
# - inserts \hand (the pointy hand) in front of all surviving candidates
#
# The input LaTeX tableau looks like the one in sample-tableau.tex.
# Thus, a cell that might have stars in it looks like \shade{*****} if
# shaded, \unsha{**!***} if unshaded.  \shade and \unsha should be
# defined in the document as LaTeX macros.
#
# This script is especially useful if you have several tableaux that
# are rerankings of each other.  Just swap the constraint columns
# using Emacs's C-x r commands, then use C-u M-| to filter the new
# tableau through the script.

while (<>) {                 # read in all the rows and save them
   s/^( *)\\hand/$1     /;            # get rid of leading pointy hand if any
   s/\\(shade|unsha){/unknown{/g;      # all cells, whether shaded or unshaded in the input, have their shading changed to "unknown"
   s/(unknown{\**)!(\**})/$1$2 /g;     # kill all exclamation marks, adding a space after the cell to preserve alignment
   die "Aborting: Some cell in input wouldn't have had room to add ! -- no space after it.\n" if /unknown{\**}([^ ]|$)/;
   push(@rows, $_);
}


# Keep running through the tableau looking for "unknown" cells to
# process until there are no more.  On each pass we turn the unknowns
# in the next column to unshaded, and for each candidate in that
# column that gets thrown out we mark it with ! and shade the rest of
# its row.  
while (1) {
   $candidates = 0;
   foreach (@rows) {   
      if (/unknown{(\**)}/) {   # find best candidate in this column (i.e., the survivor with fewest violations)
         $minviols = $1 if ($candidates == 0) || (length($1) < length($minviols));
	 $candidates++;
      }
   } 
   $qminviols = $minviols;  $qminviols =~ s/(\W)/\\$1/g;     # version of $minviols with * (and other special chars, in principle) quoted
   last if $candidates == 0;       # all done!  no more columns
   foreach (@rows) {
      if (/unknown{(\**)}/) {     # if this candidate is still in the running, put $1 to its cell for the CURRENT column
	  s/unknown({$qminviols\*)(\**}) /\\unsha$1!$2/  if length($1) > length($minviols);   # mark it with an exclamation point, and unshade the cell
          s/unknown{/\\shade{/g  if $candidates == 1 || length($1) > length($minviols);      # if we (now) know everything we need to about the candidate, shade its remaining cells (possibly including this one)
          s/unknown{/\\unsha{/;                                                              # if candidate is still in the running, unshade the single cell that kept it there
      }
   }
}

foreach (@rows) {    # all done, print the munged rows
    s/^( ?){6}( *)/$2\\hand / unless /\\unsha{\**!\**}/;    # if this candidate never got killed, put a pointy hand right-aligned to its left (damaging spacing as little as possible)
   print;
}