§1  PICT  INTRODUCTION 1

1. Introduction. This is the first file of a program to play with pictures as defined in [Zel], in an ‘X Windows’ environment. This part is written by Marc van Leeuwen, and the graphic part will be created by James Faux. Although the author has quite some experience with literate programming to date (Jan 19 1994), this is the first time he writes a substential literate program from scratch, so it is interesting to see if and how this affects the style of programming.

2. Here is the global order in which things will be presented to the compiler. Externally visible functions will be declared in the remaining sections of the unnamed module, and will therefore follow the material listed here. #include #include #include #define local static

format local static

⟨ Local typedef delarations 70 ⟩

⟨ Local function definitions 16 ⟩

3. For externally visible types and objects, a declaration will appear in the header file , which will be written by this program unit. ⟨ 3 ⟩ ≡ #include /∗ take care of things like size t ∗/

⟨ General macros and typedef declarations 4 ⟩

⟨ Prototypes of externally visible functions 5 ⟩

4. Here are some definitions that can be used in all files. The type bool and the constants true and false can be used to suggest a distinction between the logical and the integer domain. The macro fatal can be called to make an emergency exit, while uttering some dying words. The macros new and new array provide a way to allocate memory that is type-safe and also guarantees that ⊙ will not be returned; instead fatal will be called if memory is exhausted. ⟨ General macros and typedef declarations 4 ⟩ ≡

typedef signed char bool; /∗ signed for in case we do “Boolean arithmetic” ∗/ #define true (bool)1 #define false (bool)0 #define fatal (mess ) fprintf (stderr , ␣ , mess ), exit (1) #define new (type) (type∗)checked alloc(sizeof (type)) #define new array (type, size) (type∗)checked alloc((size) ∗ sizeof (type))

See also sections 7, 36, and 45. This code is used in section 3.

5. For new and new array we use a function checked alloc that is a wrapper around malloc. ⟨ Prototypes of externally visible functions 5 ⟩ ≡

void ∗checked alloc (size t); /∗ will not return ⊙ ∗/

See also sections 8, 10, 12, 14, 17, 20, 22, 24, 27, 34, 37, 40, 46, 48, 52, 56, 60, 68, 71, 74, 78, 82, 87, 91, and 93. This code is used in section 3.

6.

void ∗checked alloc (size t amount )

{ void ∗p ⇐ malloc(amount ); if (p = ⊙) fatal ( ␣ ); return p;

2  SKEW DIAGRAMS  PICT §7

} 7. Skew diagrams. The first basic type of mathematical objects to be handled is that of skew diagrams. A skew diagram is defined to be a finite subset of Z×Z that is convex with respect to the natural ordering ‘≤’. A skew diagram will be represented by listing its rows. Each row is represented by a pointer r to a structure of type row, where r = ⊙ if the row is empty, and otherwise r→start < r→end and the row occupies column numbers j with r→start ≤ j < r→end . A skew diagram is represented by a pointer d to a structure of type diagram, where d = ⊙ if the diagram is empty, and otherwise the non-empty rows of the diagram have row number i with d→top ≤ i < d→bottom and can be found as d→r[i − d→top], for which the macro diag row (d, i) is provided. There may be empty rows in this range, but not at either end, i.e., when d ≠ ⊙ we are guaranteed to have diag row (d, d→top) ≠ ⊙ and diag row (d, d→bottom − 1) ≠ ⊙. Futhermore the definition of pictures implies that if d→r[i] ≠ ⊙∧d→r[i+1] ≠ ⊙ then d→r[i+1]→start ≤ d→r[i]→start and d→r[i + 1]→end ≤ d→r[i]→end , and that if k < l < m with d→r[l] = ⊙ while d→r[k] ≠ ⊙ ∧ d→r[m] ≠ ⊙ then d→r[m]→end ≤ d→r[k]→start . To accommodate growing and shrinking of pictures, an extra field size indicates that d→r[i] is a valid memory reference (although possibly with an undefined value) for 0 ≤ i < d→size; naturally we have size ≥ d→bottom − d→top. ⟨ General macros and typedef declarations 4 ⟩ +≡

typedef struct { int start , end ; } row, ∗row p;

typedef struct { int top, bottom; unsigned int size; row p ∗r; } diagram, ∗diag p; #define diag row (d, i) (d)→r[(i) − (d)→top]

8. The function abs diag computes the number of squares of a skew digram. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

int abs diag (diag p d);

9.

int abs diag (diag p d)

{ int i, n ⇐ 0; row p r; if (d = ⊙) return 0; for (i ⇐ 0; i < d→bottom − d→top; ^{++}i)

if ((r ⇐ d→r[i]) ≠ ⊙) n +⇐ r→end − r→start ; return n;

}

10. The following function tests whether a square (i, j) occurs in a skew diagram d. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

bool inside (diag p d, int i, int j);

11.

bool inside (diag p d, int i, int j)

{ if (d ≠ ⊙ ∧ d→top ≤ i ∧ i < d→bottom)

{ row p r ⇐ diag row (d, i); return r ≠ ⊙ ∧ r→start ≤ j ∧ j < r→end ; } else return false;

§12  PICT  SKEW DIAGRAMS 3

} 12. Here is a slightly more complicated function that determines whether a square (i, j) is a “corner” of d, i.e., if it is inside p and moreover p will remain a skew diagram if (i, j) is removed. It has an extra parameter direction which if positive requires in addition that p is a maximal element of d with respect to ‘≤’, if negative that it is a minimal element, and if zero allows either or both to be the case. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

bool corner (diag p d, int i, int j, int direction);

13.

bool corner (diag p d, int i, int j, int direction)

{ if (d ≠ ⊙ ∧ d→top ≤ i ∧ i < d→bottom)

{ row p r ⇐ diag row (d, i);

return r ≠ ⊙ ∧ (direction ≥ 0 ∧ j = r→end − 1 ∧ ¬inside(d, i + 1, j)

∨ direction ≤ 0 ∧ j = r→start ∧ ¬inside(d, i − 1, j));

}

else return false; }

14. A square (i, j) is a “cocorner” of a skew diagram d if there is a skew diagram d′ with (i, j) as corner and d = d′ \ {(i, j)} (the only candidate for this is of course d′ = d ∪ {(i, j)}). The function cocorner tests this, with a similar interpretation of the parameter direction as corner . ⟨ Prototypes of externally visible functions 5 ⟩ +≡

bool cocorner (diag p d, int i, int j, int direction);

15. For (i, j) to be a cocorner of d in the positive direction it is required that (i, j) nor any square larger than it in the natural ordering are element of d, and that the squares (i − 1, j) and (i, j − 1) each either are element of d or no square less than it is an element of d. The test whether a quadrant (in positive or negative direction) is void of squares from d will be handled by an auxiliary function empty quad ; for the condition that a square either lies inside d or a whole quadrant with it as corner lies outside d, a macro neighbour is used. The (direct) calls of empty quad in cocorner cannot be pulled in front of the tests of direction (in the form empty quad (d, i, j, direction)) because in case direction = 0 we must ensure that the calls of empty quad and neighbour return true for a pair of opposite directions. #define neighbour (d, i, j, direction) (inside(d, i, j) ∨ empty quad (d, i, j, direction))

bool cocorner (diag p d, int i, int j, int direction)

{ return d = ⊙∨direction ≥ 0∧empty quad (d, i, j, 1)∧neighbour (d, i−1, j, −1)∧neighbour (d, i, j−1, −1)

∨ direction ≤ 0 ∧ empty quad (d, i, j, −1) ∧ neighbour (d, i + 1, j, 1) ∧ neighbour (d, i, j + 1, 1); } 16. The function empty quad is never called with direction = 0. It starts with splitting off the cases where no squares of d lie in a row that meets the requested quadrant. Otherwise it looks for the non-empty row closest to row i that meets the quadrant (which must be present because the first and last rows of a skew diagram may not be ⊙), and tests its last or first square (according as the direction is positive or negative) for lying in the quadrant: if any squares lie in the quadrant, this square must be one of them. ⟨ Local function definitions 16 ⟩ ≡

local bool empty quad (diag p d, int i, int j, int direction) { if (d = ⊙ ∨ direction > 0 ∧ i ≥ d→bottom ∨ direction < 0 ∧ i < d→top) return true;

if (direction > 0)

{ int k ⇐ i − d→top; if (k < 0) k ⇐ 0; else while (d→r[k] = ⊙) ^{++}k; return d→r[k]→end ≤ j;

}

else

{ int k ⇐ i − d→top; if (i ≥ d→bottom) k ⇐ d→bottom − d→top − 1; else while (d→r[k] = ⊙) ^{−}k; return d→r[k]→start > j;

} }

This code is used in section 2.

17. Skew diagrams are not shared; we may need to duplicate or delete them. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

diag p dup diag (diag p d); void del diag (diag p d);

18.

diag p dup diag (diag p d) { if (d = ⊙) return ⊙;

{ int i; diag p result ⇐ new (diagram); result →top ⇐ d→top; result →bottom ⇐ d→bottom; result →r ⇐ new array (row p, result →size ⇐ d→size); for (i ⇐ 0; i < d→bottom − d→top; ^{++}i) if (d→r[i] = ⊙) result →r[i] ⇐ ⊙; else ∗(result →r[i] ⇐ new (row)) ⇐ ∗d→r[i];

return result ; }

}

19.

void del diag (diag p d) { if (d ≠ ⊙)

{ int i;

for (i ⇐ 0; i < d→bottom − d→top; ^{++}i)

if (d→r[i] ≠ ⊙) free(d→r[i]); free(d→r); free(d);

} } 20. Here is one more trivial routine that translates a diagram over a vector (i, j). ⟨ Prototypes of externally visible functions 5 ⟩ +≡

void shift diag (diag p ∗p, int i, int j);

21.

void shift diag (diag p ∗p, int i, int j) { diag p d ⇐ ∗p;

if (d ≠ ⊙) { row p r; d→top +⇐ i; d→bottom +⇐ i;

for (i ⇐ 0; i < d→bottom − d→top; ^{++}i)

if ((r ⇐ d→r[i]) ≠ ⊙) r→start +⇐ j, r→end +⇐ j; }

}

22. On some occasions when modifying a skew diagram we may have created rows with start ≥ end , and also have emptied one or both of the extreme rows of the diagram (either by making start ≥ end or by making the row ⊙), and we need to normalise the diagram to a form that can be safely passed to other functions. Although we could make the necessary modifications each time separately, it is much easier and safer to call a catch-all cleanup function; this function is called normalise diag . ⟨ Prototypes of externally visible functions 5 ⟩ +≡

diag p normalise diag (diag p ∗p);

23.

diag p normalise diag (diag p ∗p) { int i, first nonempty , last nonempty ; bool empty ⇐ true; row p r; diag p d ⇐ ∗p;

if (d = ⊙) return ⊙; for (i ⇐ 0; i < d→bottom − d→top; ^{++}i)

if ((r ⇐ d→r[i]) ≠ ⊙)

if (r→start ≥ r→end ) free(r), d→r[i] ⇐ ⊙;

else

{ if (empty ) first nonempty ⇐ i, empty ⇐ false;

last nonempty ⇐ i; }

if (empty ) return free(d), ∗p ⇐ ⊙; d→bottom ⇐ d→top + last nonempty + 1; if (first nonempty > 0) { d→top +⇐ first nonempty ;

for (i ⇐ first nonempty ; i ≤ last nonempty ; ^{++}i) d→r[i − first nonempty ] ⇐ d→r[i]; } return d;

} 24. There are two important geometric symmetries of the set of skew diagrams: central reflection in the origin and transposition (reflection in the main diagonal). The former is trivial to implement, and can in done in situ. As a convention we shall pass diagram arguments that may be modified by functions in the form of a pointer to diag p; this is only necessary if changes of value to and from ⊙ are possible (unlike in minus diag for instance), but is a good reminder of the destructive nature of the call in any case. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

diag p minus diag (diag p ∗p); diag p transpose diag (diag p d);

25. In fact the origin is taken to lie at the upper left hand corner of square (0, 0), rather than in its center, so that a diagram with only this sqaure is transformed into one with a square at (−1, −1).

diag p minus diag (diag p ∗p) { if (∗p = ⊙) return ⊙;

{ diag p d ⇐ ∗p; int t, i, n ⇐ d→bottom − d→top; row p r; t ⇐ d→top, d→top ⇐ −d→bottom, d→bottom ⇐ −t; for (i ⇐ 0; i < n/2; ^{++}i) r ⇐ d→r[n − 1 − i], d→r[n − 1 − i] ⇐ d→r[i], d→r[i] ⇐ r; for (i ⇐ 0; i < n; ^{++}i)

if ((r ⇐ d→r[i]) ≠ ⊙) t ⇐ r→start , r→start ⇐ −r→end , r→end ⇐ −t; return d;

} }

26. Transposition takes a little more work.

diag p transpose diag (diag p d) { if (d = ⊙) return ⊙;

{ int s, e, i, top ⇐ diag row (d, d→bottom − 1)→start , bottom ⇐ d→r[0]→end ; diag p result ⇐ new (diagram); result →top ⇐ top, result →bottom ⇐ bottom; result →r ⇐ new array (row p, result →size ⇐ bottom − top); s ⇐ e ⇐ bottom; for (i ⇐ d→top; i ≤ d→bottom; ^{++}i) { row p r ⇐ i < d→bottom ? diag row (d, i) : ⊙;

if (r = ⊙ ∨ s > r→end )

{ while (e > s) diag row (result ,^{−}e)→end ⇐ i; if (r = ⊙) continue; e ⇐ r→end ; do diag row (result ,^{−}s) ⇐ ⊙; while (s > e);

}

while (s > r→start ) (diag row (result ,^{−}s) ⇐ new (row))→start ⇐ i; while (e > r→end ) diag row (result ,^{−}e)→end ⇐ i;

} return result ;

} } 27. Now let’s be more constructive and define a function that builds up a skew diagram. Since skew diagrams are defined by a closure condition, it is natural to build them by closure from a given set of squares. The basic step then is to compute from an existing (possibly empty) skew diagram d and a square (i, j) a new diagram that is its closure. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

void close diagram (diag p ∗p, int i, int j);

28. Although close diagram is not algorithmically complicated, it is not an easy function to write since it must take care of a lot of possible cases. Our basic strategy is to first ensure that the diagram has a row i, then accommodate any points greater than (i, j), then points smaller than (i, j) and finally (if neither were found) to add the point (i, j) itself. The first two cases are mutually exclusive since if there are already points greater and smaller than (i, j), then the point itself was already inside d; however, in case row i was originally empty we may have to investigate both possibilities. The points added in these cases form a (inverted) Young diagram with (i, j) as its origin, and can be best constructed from the far end, by working back towards row i. Although adding empty rows to accommodate row i my have temporarily invalidated the property that the extreme rows of d are not empty, the conditions guarding a search for greater and smaller points ensure that no final empty row occurs in the direction of the search.

void close diagram (diag p ∗p, int i, int j)

{ if (∗p = ⊙) ⟨ Make ∗p point to a new diagram with a single square (i, j) 29 ⟩ else { diag p d ⇐ ∗p; row p r, ∗R;

if (i < d→top ∨ i ≥ d→bottom) ⟨ Add null rows to d so that in contains row i 32 ⟩

if ((r ⇐ diag row (d, i)) = ⊙ ? i ≠ d→bottom − 1 : j < r→start )

⟨ Find first row below i with start ≤ j and work back, making all intermediate rows start at j 30 ⟩ if ((r ⇐ diag row (d, i)) = ⊙ ? i ≠ d→top : j ≥ r→end ) ⟨ Find first row above i with end > j and

work back, making all intermediate rows end at j + 1 31 ⟩ if (diag row (d, i) = ⊙) r ⇐ diag row (d, i) ⇐ new (row), r→start ⇐ j, r→end ⇐ j + 1;

} }

29. To avoid too frequent future resizing, we allocate 8 rows for a starting diagram. ⟨ Make ∗p point to a new diagram with a single square (i, j) 29 ⟩ ≡

{ diag p d ⇐ ∗p ⇐ new (diagram); d→r ⇐ new array (row p, d→size ⇐ 8), d→top ⇐ i, d→bottom ⇐ i + 1; d→r[0] ⇐ new (row), d→r[0]→start ⇐ j, d→r[0]→end ⇐ j + 1;

}

This code is used in section 28.

30. The search stops either because we find a square that in not greater than (i, j), or because we reach the bottom of d; in the former case we may have in fact gone a bit too far and encounter a number of rows on the way back that remain empty. In either case it is the end of the last row we did see that determines the end of any newly created rows. When we enter this module, we have r = diag row (d, i); this fact is used when i + 1 = d→bottom. ⟨ Find first row below i with start ≤ j and work back, making all intermediate rows start at j 30 ⟩ ≡

{ for (R ⇐ &diag row (d, i + 1); R < &diag row (d, d→bottom) ∧ ((r ⇐ ∗R) = ⊙ ∨ r→start > j); ) ^{++}R;

{ int e ⇐ r→end ; /∗ if R = &diag row (d, d→bottom) then r = R[−1] ≠ ⊙ ∗/

while (^{−}R ≥ &diag row (d, i))
if (∗R ≠ ⊙) (r ⇐ ∗R)→start ⇐ j, e ⇐ r→end ;
else if (j < e) (r ⇐ ∗R ⇐ new (row))→start ⇐ j, r→end ⇐ e;

} }

This code is used in section 28.

31. Although this module is similar to the previous one, there are some subtle differences in order to avoid assigning &d→r[−1] to R, as this value is not guaranteed to exist. Therefore, in the first loop, R is sometimes a step behind compared to the code above, and in particular if we hit the top of d, the row pointed to by R may need to be adjusted. When we enter this module, we have r = diag row (d, i); this fact is used when i = d→top. ⟨ Find first row above i with end > j and work back, making all intermediate rows end at j + 1 31 ⟩ ≡

{ for (R ⇐ &diag row (d, i); R > &d→r[0] ∧ ((r ⇐ ∗^{−}R) = ⊙ ∨ r→end ≤ j); ) { }

{ int s ⇐ r→start ; /∗ if R = &d→r[0] then r = ∗R ≠ ⊙ ∗/

if (r→end ≤ j) r→end ⇐ j + 1; /∗ in case R = &d→r[0], adjust r→end ∗/
while (^{++}R ≤ &diag row (d, i))
if ((r ⇐ ∗R) ≠ ⊙) r→end ⇐ j + 1, s ⇐ r→start ;
else if (s ≤ j) (r ⇐ ∗R ⇐ new (row))→end ⇐ j + 1, r→start ⇐ s;

} }

This code is used in section 28.

32. In this module we either have i < d→top or i ≥ d→bottom. These cases have to be distinguished so often that it might be easier to write them out separately. ⟨ Add null rows to d so that in contains row i 32 ⟩ ≡

{ unsigned int size ⇐ i < d→top ? d→bottom − i : i + 1 − d→top, k ⇐ size;

if (size > d→size) ⟨ Replace array d→r by one with at least size elements, and adapt bounds and

contents so that diag row (d, i) = ⊙ 33 ⟩ else if (i ≥ d→bottom) { do d→r[^{−}k] ⇐ ⊙; while (k > d→bottom − d→top);

d→bottom ⇐ i + 1; } else { do ^{−}k, d→r[k] ⇐ diag row (d, i + k); while (k > d→top − i); /∗ unsigned ∗/

do d→r[^{−}k] ⇐ ⊙; while (k > 0);

d→top ⇐ i; }

}

This code is used in section 28.

33. When the array d→r must grow we oversize it by approximately the golden ratio (which has no particular significance). Since the skew diagrams are intended for graphical display, we ignore the possibility of integer overflow of d→size. ⟨ Replace array d→r by one with at least size elements, and adapt bounds and contents so that

diag row (d, i) = ⊙ 33 ⟩ ≡ { row p ∗rr ⇐ new array (row p, d→size ⇐ 13 ∗ size/8), ∗copy ;

if (i < d→top) copy ⇐ &(rr [d→top − i]), k ⇐ d→bottom − d→top, d→top ⇐ i; else { copy ⇐ &rr [0]; /∗ k = size = i + 1 − d→top ∗/

do copy [^{−}k] ⇐ ⊙; while (k > d→bottom − d→top); d→bottom ⇐ i + 1;

} while (k^{−} > 0) copy [k] ⇐ d→r[k]; /∗ k is unsigned ∗/ while (copy > rr ) ∗^{−}copy ⇐ ⊙; /∗ clear any new rows at top ∗/ free(d→r), d→r ⇐ rr ;

}

This code is used in section 32.

34. Here is a simpler routine that removes a sqaure from a diagram, and any further sqaure to make the result a skew diagram. This can be done in two ways, either removing all squares larger or smaller than it; therefore the function has an extra direction parameter. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

diag p remove square (diag p ∗p, int i, int j, int direction);

35.

diag p remove square (diag p ∗p, int i, int j, int direction) { diag p d ⇐ ∗p;

if (¬inside(d, i, j)) return d; { row p r ⇐ diag row (d, i);

if (direction > 0)

do r→end ⇐ j; while (^{++}i < d→bottom ∧ (r ⇐ diag row (d, i)) ≠ ⊙ ∧ r→end > j); else

do r→start ⇐ j + 1; while (^{−}i ≥ d→top ∧ (r ⇐ diag row (d, i)) ≠ ⊙ ∧ r→start ≤ j); } return normalise diag (p);

10  PICTURES  PICT §36

} 36. Pictures. We now come to the central objects for this software, namely pictures. A picture f represents a bijection between two skew diagrams, and it does so basically by tabulating the images of each of the points in the domain. We do not choose the most compact representation of pictures possible, but rather incorporate some information that is useful in many places, although it could be deduced from the remaining information. For instance, we must clearly record the skew diagram that is the domain of the bijection, but it is useful to also explicitly record the skew diagram that is the image of the bijection. Similarly, given the image diagram, it would be sufficient to record just the row or just the column coordinates of the individual images; however, we record both. On the other hand, since the list of row-images of f runs parallel to the list of rows of f→domain, there is no need to replicate f→domain→top and f→domain→bottom; however a size field for the picture and for each individual row image is provided (since we shall use diagram funtions to manipulate f→domain and f→image, we cannot assume that f→domain→size is always identical to f→size, although both must accomodate the same number of actual rows). The field f→r[i].size need only be defined if f→r[i].p ≠ ⊙. ⟨ General macros and typedef declarations 4 ⟩ +≡

typedef struct { int i, j; } point;

typedef struct { unsigned int size; point ∗p; } row image;

typedef struct { diag p domain, image; row image ∗r; unsigned int size; } picture, ∗pict p; #define pict row (f, i) (f)→r[(i) − (f)→domain→top].p #define pict point (f, i, j) pict row (f, i)[(j) − diag row ((f)→domain, i)→start ]

37. Like for diagrams we need some utility routines ⟨ Prototypes of externally visible functions 5 ⟩ +≡

pict p dup pict (pict p d);

void del pict (pict p f);

38.

pict p dup pict (pict p f)

{ if (f = ⊙) return ⊙;

{ int i; pict p result ⇐ new (picture); result →domain ⇐ dup diag (f→domain); result →image ⇐ dup diag (f→image); result →r ⇐ new array (row image, result →size ⇐ f→size); for (i ⇐ 0; i < f→domain→bottom − f→domain→top; ^{++}i)

if (f→r[i].p = ⊙) result →r[i].p ⇐ ⊙;

else

{ int j, n ⇐ f→domain→r[i]→end − f→domain→r[i]→start ; point ∗p ⇐ result →r[i].p ⇐ new array (point, result →r[i].size ⇐ f→r[i].size), ∗q ⇐ f→r[i].p; for (j ⇐ 0; j < n; ^{++}j) p[j] ⇐ q[j];

} return result ;

§39  PICT  PICTURES 11

} } 39. Although normally non-empty pictures nave non-null domain and image, we allow for ⊙ in these positions in del pict ; for instance del pict might well be called because some operation has just made domain = ⊙ (see shrink pict ).

void del pict (pict p f)

{ if (f ≠ ⊙)

{ if (f→domain ≠ ⊙)

{ int i, n ⇐ f→domain→bottom − f→domain→top; for (i ⇐ 0; i < n; ^{++}i) if (f→r[i].p ≠ ⊙) free(f→r[i].p); free(f→domain);

}

if (f→image ≠ ⊙) free(f→image);

free(f→r); free(f); }

}

40. There are quite a few conditions that a picture must satisfy. Although we should use only functions that preserve these properties, it is good to have a function that tests the sanity of a picture, both for testing purposes and because it gives us the opportunity to explicitly state all conditions. Because one of the most important conditions to check is bijectivity, it is convenient to combine this testing function with one that computes the inverse of a picture; if just a check of a picture f is desired, one can call del pict (inverse pict (f)). ⟨ Prototypes of externally visible functions 5 ⟩ +≡

pict p inverse pict (pict p f);

41. #define pict error (mess , i, j) (fprintf (stderr , mess , i, j), exit (1))

pict p inverse pict (pict p f)

{ pict p inv ; if (f = ⊙) return ⊙; if (abs diag (f→domain) ≠ abs diag (f→image))

pict error ( ␣ ␣ ␣ ␣ ␣ ␣ , abs diag (f→domain),

abs diag (f→image)); ⟨ Prepare inv for use 42 ⟩ ⟨ Insert the points of f→domain at the proper place into inv , meanwhile checking that the picture

conditions are satisfied 43 ⟩ return inv ;

}

42. For inv we mainly reuse the ingredients of f, but sharing is avoided. We put inv →domain ⇐ ⊙ initially, and will transform this into its final value (a copy of f→image) during the insertion process. We allocate the rows slightly oversized to accommodate small future changes more easily. ⟨ Prepare inv for use 42 ⟩ ≡

{ int i; row p r; inv ⇐ new (picture); inv →domain ⇐ ⊙; inv →image ⇐ dup diag (f→domain); inv →r ⇐ new array (row image, inv →size ⇐ f→image→size); for (i ⇐ 0; i < f→image→bottom − f→image→top; ^{++}i) inv →r[i].p ⇐

(r ⇐ f→image→r[i]) = ⊙ ? ⊙ : new array (point, inv →r[i].size ⇐ r→end − r→start + 2);

}

This code is used in section 41.

43. The order of insertion used is by rows from bottom to top, where each row is traversed from left to right. Since this (total) ordering extends the partial ordering ‘≤_{↙}’ defined by (i, j) ≤_{↙} (i′, j′) ⟺ i ≥ i′ ∧ j ≤ j′, it follows from the theory of pictures that the image of each initial set of points should be an order ideal of the full image in the natural ordering, and hence a skew diagram. Therefore we maintain in the skew diagram inv →domain the image of the points treated so far; it will be equal to f→image at the end because we will test that all images lie in f→image but not (yet) in inv →domain, and we already checked that f→domain and f→image have equally many squares. Note that inv →r has been initialised according to f→image while inv →domain is still under construction, hence we cannot use pict row or pict point for inv , e.g., by saying img ⇐ &pict point (inv , i, j): that would use the not yet correct values in inv →domain rather than those in f→image. Therefore we instead compute the required offsets “by hand”. ⟨ Insert the points of f→domain at the proper place into inv , meanwhile checking that the picture

conditions are satisfied 43 ⟩ ≡ { int i, j; row p r;

for (i ⇐ f→domain→bottom − 1; i ≥ f→domain→top; ^{−}i)

if ((r ⇐ diag row (f→domain, i)) ≠ ⊙) for (j ⇐ r→start ; j < r→end ; ^{++}j) { point x ⇐ pict row (f, i)[j − r→start ], ∗img ;

int k ⇐ x.i − f→image→top, l ⇐ x.j − f→image→r[k]→start ; /∗ offsets ∗/ ⟨ Test validity of the image x of (i, j) 44 ⟩ img ⇐ &inv →r[k].p[l], img →i ⇐ i, img →j ⇐ j; close diagram(&inv →domain, x.i, x.j); /∗ this adds a single point ∗/

} }

This code is used in section 41.

44. Three conditions are tested. First the image x of (i, j) must of course lie in the stated image f→image. The second and third tests correspond to the requirements that f^{−1} and f be morphisms of partial ordered sets from the natural ordering to ‘≤_{↙}’. For f^{−1} we in fact replace ‘≤_{↙}’ by the total ordering in which we traverse the points of f→domain (this apparent weakening of the condition makes no difference when the picture as a whole is considered), and do the check by verifying that the inverse image under f^{−1} of each order ideal for this ordering is an order ideal for the natural ordering. The inverse image under f^{−1} is of course just the image under f, and the condition conveniently reduces to the fact that each next image should be an outer cocorner of the diagram inv →domain constructed so far. For f the morphism check follows more directly from the definition. It will be sufficient to perform the check for pairs of points that are adjacent, so we compare the image x of (i, j) with the image of (i, j − 1) and of (i + 1, j), whenever one or both of these points lie inside f→domain; we should have f(i, j − 1) ≤_{↙} x and x ≤_{↙} f(i + 1, j). Since we already checked that x is an outer cocorner of inv →domain, which contains both f(i, j − 1) and f(i + 1, j), it will be sufficient to check the first coordinate in the former and the second coordinate in the latter case. ⟨ Test validity of the image x of (i, j) 44 ⟩ ≡

if (¬inside(f→image, x.i, x.j)) pict error ( ␣ ␣ ␣ , x.i, x.j); if (¬cocorner (inv →domain, x.i, x.j, 1))

pict error ( ␣ ␣ ␣ ␣ ␣ , x.i, x.j); if (j > r→start ∧ x.i > pict row (f, i)[j − 1 − r→start ].i

∨ inside(f→domain, i + 1, j) ∧ x.j > pict point (f, i + 1, j).j)

pict error (  ␣       ␣         ␣        ␣  ␣  , x.i, x.j);

This code is used in section 43.

45. Next we consider the functions that can be used to to enter a picture. The user must enter a number of images of points before a complete picture is defined, but the event-driven nature of the user interface more or less forces us to take an incremental approach, where a single function call handles only one user input, so that control can return to the main event loop. This means that we shall need a data structure to represent a partially entered picture. The domain of the picture to be constructed will be fixed beforehand, and the images of the points of the picture will be considered in the same order as in inverse pict ; they will be submitted to the same tests as in that function, so that illegal images can be ruled out immediately. Altogether an incomplete picture will be characterised by a pict p f together with a pair of coordinates (i,

j) that indicate the point whose image is next to be entered; there is also a Boolean field complete which is set to true when all images have been entered. The component f differs from ordinary pictures in that abs (f→domain) may exceed abs (f→image), because the former is fixed beforehand while the latter grows while images are entered. Also f→r and all its individual row images are fully allocated, but only the images of points up to (i, j) have been defined and included in f→image.

⟨ General macros and typedef declarations 4 ⟩ +≡ typedef struct { pict p f; int i, j; bool complete; } part pict;

46. The first function is setup new pict , which builds an empty partial picture from its domain.

⟨ Prototypes of externally visible functions 5 ⟩ +≡ void setup new pict (part pict ∗p, diag p d);

47. If d = ⊙ the picture is immediately complete (and equal to ⊙); otherwise a full picture is allocated, and the fields p→i and p→j are set to the leftmost square in the bottom row.

void setup new pict (part pict ∗p, diag p d)

{ p→complete ⇐ d = ⊙; if (p→complete) p→f ⇐ ⊙; else { int i; row p r; pict p f ⇐ p→f ⇐ new (picture);

f→domain ⇐ d; f→image ⇐ ⊙; f→r ⇐ new array (row image, f→size ⇐ d→size); for (i ⇐ 0; i < d→bottom − d→top; ^{++}i)

f→r[i].p ⇐ (r ⇐ d→r[i]) = ⊙ ? ⊙ : new array (point, f→r[i].size ⇐ r→end − r→start + 2);

p→i ⇐ d→bottom − 1; p→j ⇐ diag row (d, p→i)→start ; }

} 48. When the user provides a new image, a call to add image will attempt to incorporate it into a partial picture. This may fail however for mathematical reasons, and in such a case add image returns a positive number indicating the reason of failure and no change is made. If add image returns 0, the image has been accepted and incorporated, and the current point is advanced, unless the last image has been reached in which case p→complete is set. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

int add image (part pict ∗p, int i, int j);

49. When add image is called we should have p→complete = false, and we may therefore assume that p→f ≠ ⊙ and diag row (p→f→domain, p→i) ≠ ⊙.

int add image (part pict ∗p, int i, int j)

{ diag p d ⇐ p→f→domain; row p r ⇐ diag row (d, p→i); point ∗loc ⇐ &p→f→r[p→i − d→top].p[p→j − r→start ]; ⟨ Test validity of the image (i, j); if incorrect, return error code 50 ⟩ loc→i ⇐ i; loc→j ⇐ j; close diagram(&p→f→image, i, j); /∗ adds one point ∗/ ⟨ Move to next position (p→i, p→j) or set p→complete 51 ⟩ return 0;

}

50. These tests are similar to those in inverse pict but there is no a priori range to which images are confined. There is always at least one possibility to enter a valid point here. ⟨ Test validity of the image (i, j); if incorrect, return error code 50 ⟩ ≡

if (¬cocorner (p→f→image, i, j, 1)) return 1;

if (p→j > r→start ∧ i > loc[−1].i) return 2;

if (inside(d, p→i + 1, p→j) ∧ j > pict point (p→f, p→i + 1, p→j).j) return 3;

This code is used in section 49.

51. Moving to the next position may involve skipping of empty lines. If we hit the end of the diagram, the value of (p→i, p→j) is irrelevant. ⟨ Move to next position (p→i, p→j) or set p→complete 51 ⟩ ≡

if (^{++}p→j = r→end )

{ if (p→i = d→top) p→complete ⇐ true; else { do ^{−}p→i; while ((r ⇐ diag row (d, p→i)) = ⊙);

p→j ⇐ r→start ; }

}

This code is used in section 49.

52. The user may also decide to cancel the last image, in which case a call to delete image is made. Its only parameter is a reference p to a partial picture, and it returns true while clearing p→complete unless the picture was already empty and there was nothing to cancel. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

bool delete image (part pict ∗p);

53. It is legal to call delete image when p→complete holds, in which case the coordinate pair (p→i, p→j) will be set to the last square of the domain instead of backing it up.

bool delete image (part pict ∗p)

{ if (p→f = ⊙) return false; if (p→complete) p→i ⇐ p→f→domain→top, p→j ⇐ p→f→domain→r[0]→end − 1; else ⟨ Move to previous position (p→i, p→j); if none exists return false 54 ⟩ { point ∗loc ⇐ &pict point (p→f, p→i, p→j);

remove square(&p→f→image, loc→i, loc→j, 1); /∗ removes one point ∗/ } p→complete ⇐ false; return true;

}

54. The easiest way to see if there is a previous point is to examine p→f→image; this also avoids modifying (p→i, p→j) in case there is no previous point. Once this case is eliminated, no further precautions are needed to ensure termination of the search for a position. ⟨ Move to previous position (p→i, p→j); if none exists return false 54 ⟩ ≡

{ if (p→f→image = ⊙) return false;

{ diag p d ⇐ p→f→domain; row p r ⇐ diag row (d, p→i);

if (^{−}p→j < r→start )
{ do ^{++}p→i; while ((r ⇐ diag row (d, p→i)) = ⊙);
p→j ⇐ r→end − 1;
}

} }

This code is used in section 53.

16  SIMPLE ALGORITHMS FOR PICTURES: REFLECTIONS AND GLISSEMENT  PICT §55

55. Simple algorithms for pictures: reflections and glissement. Once we have pictures available, there are several algorithms that may be applied to them to produce other pictures. We have already seen inverse pict that interchanges domain and image, there are similar symmetry operators that affect a combination of central symmetry and transposition on the domain and image diagrams. Then there are Schützenberger’s glissements, which can be applied either at the domain or the image diagram, and either in the inward or the outward direction. Any picture can be decomposed into a pair of pictures with a common Young diagram as its domain (or image) and vice verso by means of the generalised Robinson-Schensted algorithm. Finally we can use Schützenberger’s algorithm to change a picture with a Young diagram as domain to one with the same image but the corresponding anti-Young diagram (central reflection) as domain. In this chapter we consider the simpler of these algorithms, in which we include glissement, although existence of this algorithm for pictures is mathematically not the most obvious, nor was it discovered early.

56. We start with the symmetry operations. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

pict p minus pict (pict p ∗p); pict p transpose pict (pict p f);

57. Reflecting the diagrams for minus pict can be done using minus diag ; the entries themselves need to be reflected and negated separately. Recall that negating means mapping x ↦ −1 − x.

pict p minus pict (pict p ∗p)

{ if (∗p = ⊙) return ⊙;

{ pict p f ⇐ ∗p; diag p d; int i, j, n, m; point ∗r; d ⇐ minus diag (&f→domain); minus diag (&f→image); n ⇐ d→bottom − d→top; for (i ⇐ 0; i < n/2; ^{++}i) { row image ri ⇐ f→r[n − 1 − i]; f→r[n − 1 − i] ⇐ f→r[i]; f→r[i] ⇐ ri ; } for (i ⇐ 0; i < n; ^{++}i) if ((r ⇐ f→r[i].p) ≠ ⊙)

for (j ⇐ 0, m ⇐ d→r[i]→end − 1 − d→r[i]→start ; j ≤ m/2; ^{++}j)
{ point x ⇐ r[m − j];
r[m − j].i ⇐ −1 − r[j].i, r[m − j].j ⇐ −1 − r[j].j; r[j].i ⇐ −1 − x.i, r[j].j ⇐ −1 − x.j;
}

return f; }

}

58. Transposition is similar, but we create a fresh picture. The image of the pictures suffers negation as well as transposition, in order to retain the picture property.

pict p transpose pict (pict p f)

{ if (f = ⊙) return ⊙;

{ int i; diag p d; row p r; pict p result ⇐ new (picture); result →domain ⇐ d ⇐ transpose diag (f→domain); result →image ⇐ transpose diag (f→image), minus diag (&result →image); result →r ⇐ new array (row image, result →size ⇐ d→size); for (i ⇐ d→top; i < d→bottom; ^{++}i)

if ((r ⇐ diag row (d, i)) = ⊙) pict row (result , i) ⇐ ⊙;

else ⟨ Allocate row i of result and assign anti-transposed images of column i of f to it 59 ⟩ return result ;

§59  PICT  SIMPLE ALGORITHMS FOR PICTURES: REFLECTIONS AND GLISSEMENT 17

} } 59. ⟨ Allocate row i of result and assign anti-transposed images of column i of f to it 59 ⟩ ≡

{ int j; row image ∗ri ⇐ &result →r[i − d→top]; ri →p ⇐ new array (point, ri →size ⇐ r→end − r→start + 2); for (j ⇐ r→start ; j < r→end ; ^{++}j) { point ∗p ⇐ &ri →p[j − r→start ], x ⇐ pict point (f, j, i);

p→i ⇐ −1 − x.j; p→j ⇐ −1 − x.i; }

}

This code is used in section 58.

60. Before we define glissement, we need a pair of auxiliary functions to temporarily add a square to the set for which images are recorded, and to remove one afterwards. The function grow pict is called to extend a picture by a square, which should be cocorner, and whose image is initially undefined, and shrink pict is used to remove a square (possibly a different one) afterwards. The parameter dir indicates whether it is an outer or an inner cocorner. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

void grow pict (pict p ∗p, int i, int j, int dir );

61. Normally grow pict has two tasks to perform: adapting f→domain (there is no change to f→image) and adapting the arrays of row images; it must also take care of creating the picture structure itself if it was previously empty. The first task can be performed by calling close diagram, the others have to be done explicitly.

void grow pict (pict p ∗p, int i, int j, int dir )

{ if (∗p = ⊙) ⟨ Make ∗p to a refer to a newly created picture with empty fields 62 ⟩ else if (¬cocorner ((∗p)→domain, i, j, dir )) fatal ( ␣ ␣ ); { pict p f ⇐ ∗p;

close diagram(&f→domain, i, j); /∗ adds one point ∗/ ⟨ Extend f so as to make pict point (f, i, j) a valid reference 63 ⟩

} }

62. Setting f→domain ⇐ ⊙ suffices to provide close diagram with a legal starting point, but we should make f→r ≠ ⊙. ⟨ Make ∗p to a refer to a newly created picture with empty fields 62 ⟩ ≡

{ pict p f ⇐ ∗p ⇐ new (picture);

f→domain ⇐ f→image ⇐ ⊙; f→r ⇐ new array (row image, f→size ⇐ 6); }

This code is used in section 61.

63. We may have to add a new row of images, and certainly have to extend row i with a new image. ⟨ Extend f so as to make pict point (f, i, j) a valid reference 63 ⟩ ≡

{ int k; row image ∗r; diag p d ⇐ f→domain; ⟨ If diag row (d, i) has been newly created, reserve a slot in f→r, and set pict row (f, i) ⇐ ⊙ 64 ⟩ r ⇐ &f→r[i − d→top]; if (r→p = ⊙) r→p ⇐ new array (point, r→size ⇐ 4); else ⟨ Reserve a slot for pict point (f, i, j) in the array r→p 66 ⟩

}

This code is used in section 61.

64. The row diag row (d, i) was newly created if it is the first or the last row row, and has length 1. If it was the first row, the other rows have to be shifted down to reflect the change in f→domain→top. ⟨ If diag row (d, i) has been newly created, reserve a slot in f→r, and set pict row (f, i) ⇐ ⊙ 64 ⟩ ≡

if ((i = d→top ∨ i = d→bottom − 1) ∧ diag row (d, i)→end − diag row (d, i)→start = 1)

{ int a ⇐ 1; if (i = d→top) while (d→r[a] = ⊙) ^{++}a; else while (diag row (d, d→bottom − 1 − a) = ⊙) ^{++}a; ⟨ Make sure that f→r can accommodate at least a more rows 65 ⟩ if (i = d→top) /∗ then shift entries of f→r a places down ∗/

for (k ⇐ d→bottom − 1 − a − d→top; k ≥ 0; ^{−}k) f→r[k + a] ⇐ f→r[k]; pict row (f, i) ⇐ ⊙;

}

This code is used in section 63.

65. ⟨ Make sure that f→r can accommodate at least a more rows 65 ⟩ ≡

{ if (f→size < d→bottom − d→top)

{ row image ∗r ⇐ new array (row image, f→size +⇐ a); for (k ⇐ 0; k < d→bottom − d→top − 1; ^{++}k) r[k] ⇐ f→r[k]; /∗ copy array ∗/ free(f→r); f→r ⇐ r;

} }

This code is used in section 64.

66. Like in section 64, we must not only allocate memory if necessary, but also compensate for any changes that close diagram has made to diag row (d, i)→start ; this is the case after adding an inner cocorner, i.e., if dir < 0. ⟨ Reserve a slot for pict point (f, i, j) in the array r→p 66 ⟩ ≡

{ row di ⇐ ∗diag row (d, i); ⟨ Make sure that r→p can accommodate at least one more point 67 ⟩ if (dir < 0) /∗ then shift entries of r→p one place to the right ∗/ for (k ⇐ di .end − 1 − di .start ; k > 0; ^{−}k) r→p[k] ⇐ r→p[k − 1];

}

This code is used in section 63.

67. ⟨ Make sure that r→p can accommodate at least one more point 67 ⟩ ≡

{ if (r→size < di .end − di .start )

{ point ∗p ⇐ new array (point, r→size ⇐ di .end − di .start + 4); for (k ⇐ 0; k < di .end − 1 − di .start ; ^{++}k) p[k] ⇐ r→p[k]; free(r→p); r→p ⇐ p;

} }

This code is used in section 66.

68. The function shrink pict is called to remove a square from a picture, which should be corner whose image is no longer of interest. The parameter dir indicates whether it is an outer or an inner corner. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

void shrink pict (pict p ∗p, int i, int j, int dir );

69. Unlike grow pict , we do not have to worry about allocation of sufficient memeory in shrink picture, so the function is shorter; we do however have to take care of shifting rows or entries back when the first one has disappeared.

void shrink pict (pict p ∗p, int i, int j, int dir )

{ if (∗p = ⊙ ∨ ¬corner ((∗p)→domain, i, j, dir )) fatal ( ␣ ␣ );

{ pict p f ⇐ ∗p; remove square(&f→domain, i, j, dir ); /∗ removes one point ∗/ if (f→domain = ⊙) { del pict (f); ∗p ⇐ ⊙; return; } { int k; diag p d ⇐ f→domain;

if (i < d→top) for (k ⇐ 0; k < d→bottom − d→top; ^{++}k) f→r[k] ⇐ f→r[k + d→top − i]; else if (i < d→bottom)

if (diag row (d, i) = ⊙) { point ∗∗p ⇐ &f→r[i − d→top].p; free(∗p); ∗p ⇐ ⊙; } else if (dir < 0) { row p r ⇐ diag row (f→domain, i); point ∗p ⇐ pict row (f, i); for (k ⇐ 0; k < r→end − r→start ; ^{++}k) p[k] ⇐ p[k + 1];

}

}

} }

70. We shall often need to classify the relative position of two points according to the compass. #define sign(n) ((n) < 0 ? −1 : (n) > 0) #define rel pos (x, y) ((compass) (3 ∗ sign(x.i − y.i) + sign(x.j − y.j))) ⟨ Local typedef delarations 70 ⟩ ≡

typedef enum { Nw ⇐ −4, N ⇐ −3, Ne ⇐ −2, W ⇐ −1, E ⇐ 1, Sw ⇐ 2, S ⇐ 3, Se ⇐ 4

} compass;

This code is used in section 2.

71. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

void glissement (pict p ∗p, int i, int j);

72. We do nothing if (i, j) is neither inner nor outer cocorner, or if it is both. A bit of Boolean arithmetic is useful to establish the condition and the corresponding direction.

void glissement (pict p ∗p, int i, int j)

{ pict p f ⇐ ∗p; if (f ≠ ⊙) { diag p d ⇐ f→domain; int dir ⇐ (int) cocorner (d, i, j, −1) − (int) cocorner (d, i, j, 1);

if (dir = 0) return;

grow pict (p, i, j, −dir ); ⟨ Perform glissement into (i, j) on d 73 ⟩ shrink pict (p, i, j, dir );

} } 73. The basic algorithm for glissement is really quite simple. First we look if both neighbours in the direction dir are present. i.e., to the right and below respectively to the left and above. If one of them is absent, moving the other one is the only possibility (since (i, j) is a non-isolated cocorner, the neighbours cannot both be absent). If both are present we need a comparison of the images, and although if all is well comparing just one coordinate would would suffice, we determine the exact compass direction so that erroneous situations can be detected. Given the relative position of (i, j + 1) and (i + 1, j) (for the case dir = 1), the picture condition implies that the relative position of the images should lie in { Ne, E, Se, S, Sw }, but the fundamental lemma that underlies the definition of glissement for pictures says that the case Se, which would mean the images are incomparable by ‘≤_{↙}’, will not occur; in the other cases we move the square whose image compares less under ‘≤_{↙}’. ⟨ Perform glissement into (i, j) on d 73 ⟩ ≡

{ point ∗loc ⇐ &pict point (f, i, j), ∗new loc; bool horizontal ; /∗ whether the next move will be a horizontal one ∗/ do { if (¬inside(d, i + dir , j)) horizontal ⇐ true;

else if (¬inside(d, i, j + dir )) horizontal ⇐ false;

else

{ point h ⇐ pict point (f, i, j + dir ), v ⇐ pict point (f, i + dir , j); switch (dir ∗ rel pos (h, v)) { case Ne: case E: horizontal ⇐ false; break; case Sw : case S: horizontal ⇐ true; break;

case Se: fatal (  ␣      ␣  ␣  );
default: fatal (  ␣       ␣  ␣  );

} } if (horizontal ) j +⇐ dir ; else i +⇐ dir ; /∗ select square to move ∗/ new loc ⇐ &pict point (f, i, j); ∗loc ⇐ ∗new loc; loc ⇐ new loc; /∗ slide it ∗/

} while (¬corner (d, i, j, dir )); }

This code is used in section 72.

74. It can be useful to perform a sequence of glissements at once. The function multi glissement is like glissement , but the point (i_{0}, j_{0}) need not be a cocorner of the diagram in this case. If there are any points of (∗f)→domain that are greater respectively smaller than (i_{0}, j_{0}) in the natural ordering, then glissement will be repeatedly be applied to cocorners in that direction, until (i_{0}, j_{0}) has become a point of (∗f)→domain. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

void multi glissement (pict p ∗p, int i_{0}, int j_{0});

75. In its outline, multi glissement is somewhat similar to close diagram.

void multi glissement (pict p ∗p, int i_{0}, int j_{0})

{ if (∗p ≠ ⊙)

{ diag p d ⇐ (∗p)→domain; row p r;

if (i_{0} < d→top ∨ i_{0} < d→bottom ∧ ((r ⇐ diag row (d, i_{0})) = ⊙ ∨ r→start > j_{0}))

⟨ Move to first row below i_{0} with start ≤ j_{0} and work back, applying glissements by rows from

right to left, ending in column j_{0} 76 ⟩ if (i_{0} ≥ d→bottom ∨ i_{0} ≥ d→top ∧ ((r ⇐ diag row (d, i_{0})) = ⊙ ∨ r→end ≤ j_{0}))

⟨ Move to first row above i_{0} with end > j_{0} and work back, applying glissements by rows from left

to right, ending in column j_{0} 77 ⟩

} } 76. Like in the corresponding module of close diagram, we use the fact that when the search below stops, r is defined and not ⊙, possibly due to the assignment in the parent module. We set s to the start of the current row if it is non-empty, and otherwise to the end of the last non-empty row encountered. ⟨ Move to first row below i_{0} with start ≤ j_{0} and work back, applying glissements by rows from right to left,

ending in column j_{0} 76 ⟩ ≡ { int i ⇐ i_{0} < d→top ? d→top − 1 : i_{0};

do ^{++}i; while (i < d→bottom ∧ ((r ⇐ diag row (d, i)) = ⊙ ∨ r→start > j_{0})); { int j, s ⇐ r→start , e ⇐ r→end ;

while (^{−}i ≥ i_{0}) { if (i ≥ d→top ∧ (r ⇐ diag row (d, i)) ≠ ⊙) s ⇐ r→start , e ⇐ r→end ; else s ⇐ e;

for (j ⇐ s − 1; j ≥ j_{0}; ^{−}j) glissement (p, i, j); }

} }

This code is used in section 75.

77. And the opposite direction is of course quite similar. ⟨ Move to first row above i_{0} with end > j_{0} and work back, applying glissements by rows from left to right,

ending in column j_{0} 77 ⟩ ≡ { int i ⇐ i_{0} > d→bottom ? d→bottom : i_{0};

do ^{−}i; while (i ≥ d→top ∧ ((r ⇐ diag row (d, i)) = ⊙ ∨ r→end ≤ j_{0})); { int j, s ⇐ r→start , e ⇐ r→end ;

while (^{++}i ≤ i_{0}) { if (i < d→bottom ∧ (r ⇐ diag row (d, i)) ≠ ⊙) s ⇐ r→start , e ⇐ r→end ; else e ⇐ s;

for (j ⇐ e; j ≤ j_{0}; ^{++}j) glissement (p, i, j); }

} }

This code is used in section 75.

22  THE GENERALISED ROBINSON-SCHENSTED ALGORITHM  PICT §78

78. The generalised Robinson-Schensted algorithm. In this chapter we implement the generalisations given in [Zel] of the Robinson-Schensted algorithm, in both directions. We first consider the “insertion” direction, which in the traditional case amounts to computing a pair of Young tableaux from a permutation. The function RS tableau takes a reference f to a picture as argument, where ∗f is an arbitrary picture that will be modified into a picture with the same domain but a Young diagram λ as image; RS tableau returns a picture with domain λ and as image the original image of ∗f. In the traditional case ∗f is a permutation initially, and the inverse picture of the value it is transformed into is usually called Q (i.e., it is transformed into the “lattice permutation” corresponding to Q), while the return value is what is usually called P. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

pict p RS tableau (pict p ∗f);

79. We traverse (∗f)→domain by rows from bottom to top, as in inverse pict . The organisation of this function is quite similar to that of the traditional Robinson-Schensted algorithm.

pict p RS tableau (pict p ∗f)

{ pict p P ⇐ ⊙; if (∗f ≠ ⊙) { diag p d ⇐ (∗f)→domain; row p r; int i, j;

for (i ⇐ d→bottom − 1; i ≥ d→top; ^{−}i)
if ((r ⇐ diag row (d, i)) ≠ ⊙)

for (j ⇐ r→start ; j < r→end ; ^{++}j) { point p ⇐ pict point (∗f, i, j), q;

⟨ Insert p into the tableau P, assigning to q the square by which it’s shape is extended 80 ⟩ pict point (∗f, i, j) ⇐ q;

} P →image ⇐ (∗f)→image; (∗f)→image ⇐ dup diag (P →domain);

}

return P; }

80. Since in this module we are not dealing with the picture ∗f that is passed to RS tableau, there is no harm done in redeclaring i, j, d, and r for a diffferent use relative to the picture P. Since P →domain→top = 0 whenever P ≠ ⊙, and then also diag row (P →domain, i)→start = 0 for 0 ≤ i < P →domain→bottom, we can use expressions like P →r[i].p[j] directly instead of pict point (P, i, j). ⟨ Insert p into the tableau P, assigning to q the square by which it’s shape is extended 80 ⟩ ≡

{ int i, j; if (P = ⊙) i ⇐ j ⇐ 0; else { diag p d ⇐ P →domain; row p r ⇐ d→r[0];

i ⇐ 0; j ⇐ r→end ; /∗ start at end of top row ∗/

do

{ ⟨ Decrease j to proper location for p, then either break if the square is empty, or swap p with its

contents 81 ⟩ if (^{++}i = d→bottom) { j ⇐ 0; break; } /∗ extend P by a new row ∗/ if (j > (r ⇐ d→r[i])→end ) j ⇐ r→end ; /∗ snap leftwards to end of row ∗/

} while (true); } grow pict (&P, i, j, 1); P →r[i].p[j] ⇐ p; /∗ extend P by (i, j), and fill the new square ∗/ q.i ⇐ i; q.j ⇐ j;

}

This code is used in section 79.

§81  PICT  THE GENERALISED ROBINSON-SCHENSTED ALGORITHM 23

81. We search each row from the current column backwards, intil stopped by an image x with x ≤_{↙} p, or by the vertical axis. Like in glissement , we are extra prudent and perform a full test on the relative position of x with respect to p, rather than just testing one coordinate which should be sufficient. For this test we cannot use a switch statement, since we must be able to break from the loop containing it (oof!). ⟨ Decrease j to proper location for p, then either break if the square is empty, or swap p with its

contents 81 ⟩ ≡ { while (j > 0)

{ point x ⇐ P →r[i].p[j − 1]; compass c ⇐ rel pos (x, p); if (c = Ne ∨ c = N) ^{−}j; /∗ p ≤_{↙} x, so it is safe to move back ∗/ else if (c = W ∨ c = Sw ) break; /∗ smaller entry ahead: stop ∗/

else if (c = Nw ) fatal (  ␣      ␣  ␣  );
else fatal (  ␣       ␣  ␣  );

}

if (j = r→end ) break; /∗ no entries displaced, row is extended ∗/ { point t ⇐ P →r[i].p[j]; P →r[i].p[j] ⇐ p; p ⇐ t; } /∗ bump down ∗/

}

This code is used in section 80.

82. Next we consider the Robinson-Schensted algorithm in the opposite direction, which in the traditional case is computing a permutation from a pair of Young tableaux. The function RS permutation takes a picture f and a reference g to a picture as arguments, where (unless f = ∗g = ⊙) f→domain and (∗g)→image should be the same Young diagram (meaning that their sets of squares should contain (0, 0) as minimum in the natural ordering). The picture ∗g is transformed into a general picture with f→domain as domain; the picture f will be destroyed by RS permutation (since it is altered and eventually made empty during the computation). For any picture f the net effect of RS permutation(RS tableau(&f), &f) should be nihil (the second argument to RS permutation refers to f as modified by RS tableau). Since the function may fail if improper arguments are supplied, it returns a boolean value telling whether it succeeded; if not then the call did not make any changes. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

bool RS permutation (pict p f, pict p ∗g);

83. We must copy f→image into ∗g before f is deleted in the last step of the extraction process; f→image itself is cleared to prevent destruction of (∗g)→image when f is deleted.

bool RS permutation (pict p f, pict p ∗g)

{ if (f ≠ ⊙ ∧ ∗g ≠ ⊙)

{ diag p d ⇐ (∗g)→domain; row p r; int i, j; ⟨ Check that f→domain and (∗g)→image are equal Young diagrams; if not return false 86 ⟩ del diag ((∗g)→image); (∗g)→image ⇐ f→image; f→image ⇐ ⊙; for (i ⇐ d→top; i < d→bottom; ^{++}i) if ((r ⇐ diag row (d, i)) ≠ ⊙)

for (j ⇐ r→end − 1; j ≥ r→start ; ^{−}j)

{ point p, q ⇐ pict point (∗g, i, j); ⟨ Evacuate q from the tableau f, assigning to p the image extracted from it 84 ⟩ pict point (∗g, i, j) ⇐ p;

} return true;

}

else return f = ∗g; /∗ i.e., whether f = ∗g = ⊙ ∗/ } 84. Extracting is a bit simpler than inserting, since fewer boundary conditions have to be considered: the process can stop only because the horizontal axis is reached, and the proper entry to swap p with can always be found inside the existing tableau. Like in RS tableau, we redeclare i, j, d, and r, and we can use f→r[i].p[j] as a more direct way specifying pict point (f, i, j). The fact that we recompute d ⇐ f→domain every time we enter this module reflects the fact that it is a different diagram each time; we do not depend on the fact that the pointer value is the same each time due to the fact that shrink pict never changes the pointer to the domain of its first argument. The last call of shrink pict however does remove f altogether; the dangling value of d this causes does no harm since in this case i = 0 and the body of the while loop is not executed. ⟨ Evacuate q from the tableau f, assigning to p the image extracted from it 84 ⟩ ≡

{ int i ⇐ q.i, j ⇐ q.j; diag p d ⇐ f→domain; p ⇐ f→r[i].p[j]; shrink pict (&f, i, j, 1); while (^{−}i ≥ 0) { row p r ⇐ d→r[i];

⟨ Increase j to proper location, and then swap p with f→r[i].p[j] 85 ⟩ }

}

This code is used in section 83.

85. ⟨ Increase j to proper location, and then swap p with f→r[i].p[j] 85 ⟩ ≡

{ while (j < r→end − 1)

{ point x ⇐ f→r[i].p[j + 1]; compass c ⇐ rel pos (x, p); if (c = Sw ∨ c = S) ^{++}j; /∗ x ≤_{↙} p, so it is safe to move on ∗/ else if (c = E ∨ c = Ne) break; /∗ larger entry ahead: stop ∗/

else if (c = Se) fatal (  ␣      ␣  ␣  );
else fatal (  ␣       ␣  ␣  );

}

{ point t ⇐ f→r[i].p[j]; f→r[i].p[j] ⇐ p; p ⇐ t; } /∗ bump ∗/ }

This code is used in section 84.

86. When we arrive at this module, we know that f and ∗g are non-empty pictures. Once we have established that the first and last rows start in column 0 (and hence all rows), the possibility of empty rows is also excluded. ⟨ Check that f→domain and (∗g)→image are equal Young diagrams; if not return false 86 ⟩ ≡

{ diag p d ⇐ f→domain, e ⇐ (∗g)→image; if (d→top ≠ 0 ∨ e→top ≠ 0 ∨ d→bottom ≠ e→bottom) return false; { int i, l ⇐ d→bottom − 1;

if (d→r[0]→start ≠ 0 ∨ e→r[0]→start ≠ 0 ∨ d→r[l]→start ≠ 0 ∨ e→r[l]→start ≠ 0) return false; for (i ⇐ 0; i ≤ l; ^{++}i)

if (d→r[i]→end ≠ e→r[i]→end ) return false;

} }

This code is used in section 83.

§87  PICT  THE SCHÜTZENBERGER ALGORITHM FOR PICTURES 25

87. The Schützenberger algorithm for pictures. In this chapter we define the generalisation of the Schützenberger (evacuation) algorithm to pictures, and some applications that involve a combination with the Robinson-Schensted algorithms. The main function here is Schützenberger dualise that takes as argument a reference to a picture whose domain is a Young diagram, and transforms it to a picture with the same domain but with negated image. Like RS permutation, we return as a boolean value whether a proper argument was supplied and the function was therefore actually performed.

format Schutz dualise TEX (Schützenberger dualise) ⟨ Prototypes of externally visible functions 5 ⟩ +≡

bool Schützenberger dualise (pict p ∗f);

88. We could implement this function using multi glissement in combination with the functions minus pict and shift diag , which would be the natural way to define the procedure for pictures in the sense that pictures are treated as tableaux with entries in a partially ordered set. However, we implement the function in a way similar to the traditional formulation using a deflation (or evacuation) procedure, to which end we must artificially consider the entries as totally ordered; the particular total ordering chosen should have no effect provided the choice is made consistently. This alternative approach has the advantage that it provides an independent check of the validity of the theory and glissement .

bool Schützenberger dualise (pict p ∗f)

{ if (∗f ≠ ⊙)

{ diag p d ⇐ dup diag ((∗f)→domain); /∗ duplicate since d will be destroyed ∗/ ⟨ Check that d is a Young diagram; if not, return false 90 ⟩ do { int i ⇐ 0, j ⇐ 0; point p ⇐ (∗f)→r[i].p[j];

⟨ Repeatedly slide an image into the empty square (i, j), until it is a corner of d 89 ⟩ p.i ⇐ −1 − p.i, p.j ⇐ −1 − p.j; (∗f)→r[i].p[j] ⇐ p; remove square(&d, i, j, 1);

} while (d ≠ ⊙);

minus diag (&(∗f)→image); } return true;

}

89. This module is similar to one of glissement , but we must handle the possibility that we are finished without doing any sliding (this situation arises at the final deflation step). Also, rather than using ‘≤_{↙}’ for comparing images, we use a total ordering extending it. To demonstrate the fact that any such ordering may be chosen, we choose the unusual ordering that first compares by the “diagonal numbers” j − i, and if those are the same, it considers the image with the largest value for i to be greater. ⟨ Repeatedly slide an image into the empty square (i, j), until it is a corner of d 89 ⟩ ≡

{ point ∗loc ⇐ &(∗f)→r[i].p[j], ∗new loc; bool horizontal ; /∗ whether the next move will be a horizontal one ∗/ while (¬corner (d, i, j, 1)) { if (¬inside(d, i + 1, j)) horizontal ⇐ true;

else if (¬inside(d, i, j + 1)) horizontal ⇐ false;

else

{ point h ⇐ (∗f)→r[i].p[j + 1], v ⇐ (∗f)→r[i + 1].p[j];

horizontal ⇐ h.j − h.i ≠ v.j − v.i ? h.j − h.i < v.j − v.i : h.i < v.i; } if (horizontal ) ^{++}j; else ^{++}i; /∗ select square to move ∗/ new loc ⇐ &(∗f)→r[i].p[j]; ∗loc ⇐ ∗new loc; loc ⇐ new loc; /∗ slide it ∗/

} }

This code is used in section 88.

26  THE SCHÜTZENBERGER ALGORITHM FOR PICTURES  PICT §90

90. When we come here we know that d ≠ ⊙. ⟨ Check that d is a Young diagram; if not, return false 90 ⟩ ≡

{ if (d→top ≠ 0 ∨ d→r[0]→start ≠ 0 ∨ d→r[d→bottom − 1]→start ≠ 0) return false; }

This code is used in section 88.

91. Here is a way to apply this algorithm to obtain from a picture f: χ → ψ a picture χ → −ψ. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

void negate image (pict p ∗f);

92.

void negate image (pict p ∗f) { pict p P ⇐ RS tableau(f);

if (¬Schützenberger dualise(&P))

fprintf (stderr , ␣ ␣ ␣ ␣ ); else if (¬RS permutation(P, f))

fprintf (stderr , ␣ ␣ ␣ ␣ ); }

93. And here is a way to apply this algorithm to obtain from a picture f: χ → ψ a picture χ^{t} → ψ^{t}. ⟨ Prototypes of externally visible functions 5 ⟩ +≡

void transpose both (pict p ∗f);

94.

void transpose both (pict p ∗f) { pict p g ⇐ (negate image(f), transpose pict (∗f));

del pict (∗f), ∗f ⇐ g; }

§95  PICT  REFERENCES AND INDEX 27

95. References and Index.

[FG] S. Fomin and C. Greene, “A Littlewood-Richardson Miscellany”, Europ. J. Combinatorics 14, (1993), 191–212.

[JP] G. D. James and M. H. Peel, “Specht series for skew representations of symmetric groups”, Journal of Algebra 56, (1979), 343–364.

[Zel] A. V. Zelevinsky, “A Generalisation of the Littlewood-Richardson Rule and the Robinson-Schensted-Knuth Correspondence”, Journal of Algebra 69, (1981), 82–94.

a: \underline{64}. abs : 45. abs diag : \underline{8}, \underline{9}, 41. add image: \underline{48}, \underline{49}. amount : \underline{6}. bool: \underline{4}, 10, 11, 12, 13, 14, 15, 16, 23, 45, 52,

53, 73, 82, 83, 87, 88, 89. Boolean arithmetic: 4, 72. bottom: \underline{7}, 9, 11, 13, 16, 18, 19, 21, 23, 25, \underline{26}, 28,

29, 30, 32, 33, 35, 36, 38, 39, 42, 43, 47, 57, 58, 64, 65, 69, 75, 76, 77, 79, 80, 83, 86, 90.

c: \underline{81}, \underline{85}. checked alloc: 4, \underline{5}, \underline{6}. close diagram: \underline{27}, \underline{28}, 43, 49, 61, 62, 66, 75, 76. cocorner : \underline{14}, \underline{15}, 44, 50, 61, 72. compass: \underline{70}, 81, 85. complete: \underline{45}, 47, 48, 49, 51, 52, 53. copy : \underline{33}. corner : \underline{12}, \underline{13}, 14, 69, 73, 89. d: \underline{8}, \underline{9}, \underline{10}, \underline{11}, \underline{12}, \underline{13}, \underline{14}, \underline{15}, \underline{16}, \underline{17}, \underline{18}, \underline{19}, \underline{21},

\underline{23}, \underline{24}, \underline{25}, \underline{26}, \underline{28}, \underline{29}, \underline{35}, \underline{37}, \underline{46}, \underline{47}, \underline{49}, \underline{54}, \underline{57}, \underline{58}, \underline{63}, \underline{69}, \underline{72}, \underline{75}, \underline{79}, \underline{80}, \underline{83}, \underline{84}, \underline{86}, \underline{88}.

del diag : \underline{17}, \underline{19}, 83. del pict : \underline{37}, \underline{39}, 40, 69, 94. delete image: \underline{52}, \underline{53}. di : \underline{66}, 67. diag p: \underline{7}, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17,

18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 34, 35, 36, 46, 47, 49, 54, 57, 58, 63, 69, 72, 75, 79, 80, 83, 84, 86, 88.

diag row : 7, 11, 13, 26, 28, 30, 31, 32, 35, 36, 43, 47, 49, 51, 54, 58, 64, 66, 69, 75, 76, 77, 79, 80, 83.

diagram: \underline{7}, 18, 26, 29. dir : \underline{60}, \underline{61}, 66, \underline{68}, \underline{69}, \underline{72}, 73. direction: \underline{12}, \underline{13}, \underline{14}, \underline{15}, \underline{16}, \underline{34}, \underline{35}. domain: \underline{36}, 38, 39, 41, 42, 43, 44, 45, 47, 49,

53, 54, 57, 58, 61, 62, 63, 64, 69, 72, 74, 75, 79, 80, 82, 83, 84, 86, 88.

dup diag : \underline{17}, \underline{18}, 38, 42, 79, 88. dup pict : \underline{37}, \underline{38}. E: \underline{70}. e: \underline{26}, \underline{30}, \underline{76}, \underline{77}, \underline{86}. empty : \underline{23}. empty quad : 15, \underline{16}. end : \underline{7}, 9, 11, 13, 16, 21, 22, 23, 25, 26, 28, 29, 30,

31, 35, 38, 42, 43, 47, 51, 53, 54, 57, 59, 64, 66, 67, 69, 75, 76, 77, 79, 80, 81, 83, 85, 86.

exit : 4, 41. f: \underline{37}, \underline{38}, \underline{39}, \underline{40}, \underline{41}, \underline{45}, \underline{47}, \underline{56}, \underline{57}, \underline{58}, \underline{61}, \underline{62}, \underline{69},

\underline{72}, \underline{78}, \underline{79}, \underline{82}, \underline{83}, \underline{87}, \underline{88}, \underline{91}, \underline{92}, \underline{93}, \underline{94}. false: 4, 11, 13, 23, 49, 53, 54, 73, 86, 89, 90. fatal : 4, 6, 61, 69, 73, 81, 85. first nonempty : \underline{23}. fprintf : 4, 41, 92. free: 19, 23, 33, 39, 65, 67, 69. g: \underline{82}, \underline{83}, \underline{94}. glissement : \underline{71}, \underline{72}, 74, 76, 77, 81, 88, 89. grow pict : \underline{60}, \underline{61}, 69, 72, 80. h: \underline{73}, \underline{89}. horizontal : \underline{73}, \underline{89}. i: \underline{9}, \underline{10}, \underline{11}, \underline{12}, \underline{13}, \underline{14}, \underline{15}, \underline{16}, \underline{18}, \underline{19}, \underline{20}, \underline{21}, \underline{23},

\underline{25}, \underline{26}, \underline{27}, \underline{28}, \underline{34}, \underline{35}, \underline{36}, \underline{38}, \underline{39}, \underline{42}, \underline{43}, \underline{45}, \underline{47}, \underline{48}, \underline{49}, \underline{57}, \underline{58}, \underline{60}, \underline{61}, \underline{68}, \underline{69}, \underline{71}, \underline{72}, \underline{76}, \underline{77}, \underline{79}, \underline{80}, \underline{83}, \underline{84}, \underline{86}, \underline{88}.

image: \underline{36}, 38, 39, 41, 42, 43, 44, 45, 47, 49, 50,

53, 54, 57, 58, 61, 62, 79, 82, 83, 86, 88. img : \underline{43}. inside: \underline{10}, \underline{11}, 13, 15, 35, 44, 50, 73, 89. inv : \underline{41}, 42, 43, 44. inverse pict : \underline{40}, \underline{41}, 45, 50, 55, 79. i_{0}: \underline{74}, \underline{75}, 76, 77. j: \underline{10}, \underline{11}, \underline{12}, \underline{13}, \underline{14}, \underline{15}, \underline{16}, \underline{20}, \underline{21}, \underline{27}, \underline{28}, \underline{34}, \underline{35},

\underline{36}, \underline{38}, \underline{43}, \underline{45}, \underline{48}, \underline{49}, \underline{57}, \underline{59}, \underline{60}, \underline{61}, \underline{68}, \underline{69}, \underline{71}, \underline{72}, \underline{76}, \underline{77}, \underline{79}, \underline{80}, \underline{83}, \underline{84}, \underline{88}.

j_{0}: \underline{74}, \underline{75}, 76, 77. k: \underline{16}, \underline{32}, \underline{43}, \underline{63}, \underline{69}. l: \underline{43}, \underline{86}. last nonempty : \underline{23}. loc: \underline{49}, 50, \underline{53}, \underline{73}, \underline{89}. local: \underline{2}. m: \underline{57}. malloc: 5, 6. mess : 4, 41. minus diag : \underline{24}, \underline{25}, 57, 58, 88. minus pict : \underline{56}, \underline{57}, 88. multi glissement : \underline{74}, \underline{75}, 88. N: \underline{70}. n: \underline{9}, \underline{25}, \underline{38}, \underline{39}, \underline{57}. Ne: \underline{70}, 73, 81, 85.

28  REFERENCES AND INDEX  PICT §95

negate image: \underline{91}, \underline{92}, 94. neighbour : \underline{15}. new : 4, 5, 18, 26, 28, 29, 30, 31, 38, 42, 47, 58, 62. new array : 4, 5, 18, 26, 29, 33, 38, 42, 47, 58,

59, 62, 63, 65, 67. new loc: \underline{73}, \underline{89}. normalise diag : \underline{22}, \underline{23}, 35. Nw : \underline{70}, 81. P: \underline{79}, \underline{92}. p: \underline{6}, \underline{20}, \underline{21}, \underline{22}, \underline{23}, \underline{24}, \underline{25}, \underline{27}, \underline{28}, \underline{34}, \underline{35}, \underline{36}, \underline{38},

\underline{46}, \underline{47}, \underline{48}, \underline{49}, \underline{52}, \underline{53}, \underline{56}, \underline{57}, \underline{59}, \underline{60}, \underline{61}, \underline{67}, \underline{68}, \underline{69}, \underline{71}, \underline{72}, \underline{74}, \underline{75}, \underline{79}, \underline{83}, \underline{88}.

part pict: \underline{45}, 46, 47, 48, 49, 52, 53. pict error : \underline{41}, 44. pict p: \underline{36}, 37, 38, 39, 40, 41, 45, 47, 56, 57, 58,

60, 61, 62, 68, 69, 71, 72, 74, 75, 78, 79, 82, 83, 87, 88, 91, 92, 93, 94.

pict point : 36, 43, 44, 50, 53, 59, 73, 79, 80, 83, 84. pict row : 36, 43, 44, 58, 64, 69. picture: \underline{36}, 38, 42, 47, 58, 61, 62. point: \underline{36}, 38, 42, 43, 47, 49, 53, 57, 59, 63, 67,

69, 73, 79, 81, 83, 85, 88, 89. q: \underline{38}, \underline{79}, \underline{83}. R: \underline{28}. r: \underline{7}, \underline{9}, \underline{11}, \underline{13}, \underline{21}, \underline{23}, \underline{25}, \underline{26}, \underline{28}, \underline{35}, \underline{36}, \underline{42}, \underline{43},

\underline{47}, \underline{49}, \underline{54}, \underline{57}, \underline{58}, \underline{63}, \underline{65}, \underline{69}, \underline{75}, \underline{79}, \underline{80}, \underline{83}, \underline{84}. rel pos : \underline{70}, 73, 81, 85. remove square: \underline{34}, \underline{35}, 53, 69, 88. result : \underline{18}, \underline{26}, \underline{38}, \underline{58}, 59. ri : \underline{57}, \underline{59}. row: \underline{7}, 18, 26, 28, 29, 30, 31, 66. row image: \underline{36}, 38, 42, 47, 57, 58, 59, 62, 63, 65. row p: \underline{7}, 9, 11, 13, 18, 21, 23, 25, 26, 28, 29, 33,

35, 42, 43, 47, 49, 54, 58, 69, 75, 79, 80, 83, 84. rr : \underline{33}. RS permutation: \underline{82}, \underline{83}, 87, 92. RS tableau: \underline{78}, \underline{79}, 80, 82, 84, 92. S: \underline{70}. s: \underline{26}, \underline{31}, \underline{76}, \underline{77}. Schützenberger dualise: \underline{87}, \underline{88}, 92. Se: \underline{70}, 73, 85. setup new pict : \underline{46}, \underline{47}. shift diag : \underline{20}, \underline{21}, 88. shrink pict : 39, 60, \underline{68}, \underline{69}, 72, 84. shrink picture: 69. sign: \underline{70}. size: 4, \underline{7}, 18, 26, 29, \underline{32}, 33, \underline{36}, 38, 42, 47, 58,

59, 62, 63, 65, 67. size t: 3, 5, 6. start : \underline{7}, 9, 11, 13, 16, 21, 22, 23, 25, 26, 28, 29, 30,

31, 35, 36, 38, 42, 43, 44, 47, 49, 50, 51, 54, 57, 59, 64, 66, 67, 69, 75, 76, 77, 79, 80, 83, 86, 90. stderr : 4, 41, 92. Sw : \underline{70}, 73, 81, 85. t: \underline{25}, \underline{81}, \underline{85}. top: \underline{7}, 9, 11, 13, 16, 18, 19, 21, 23, 25, \underline{26}, 28, 29, 31, 32, 33, 35, 36, 38, 39, 42, 43, 47, 49, 51, 53, 57, 58, 59, 63, 64, 65, 69, 75, 76, 77, 79, 80, 83, 86, 90. transpose both: \underline{93}, \underline{94}. transpose diag : \underline{24}, \underline{26}, 58. transpose pict : \underline{56}, \underline{58}, 94. true: 4, 15, 16, 23, 45, 51, 52, 53, 73, 80, 83, 88, 89. type: 4. v: \underline{73}, \underline{89}. W: \underline{70}. x: \underline{43}, \underline{57}, \underline{59}, \underline{81}, \underline{85}.

PICT NAMES OF THE MODULES 29

⟨ Add null rows to d so that in contains row i 32 ⟩ Used in section 28. ⟨ Allocate row i of result and assign anti-transposed images of column i of f to it 59 ⟩ Used in section 58. ⟨ Check that d is a Young diagram; if not, return false 90 ⟩ Used in section 88. ⟨ Check that f→domain and (∗g)→image are equal Young diagrams; if not return false 86 ⟩ Used in

section 83.

⟨ Decrease j to proper location for p, then either break if the square is empty, or swap p with its contents 81 ⟩

Used in section 80.

⟨ Evacuate q from the tableau f, assigning to p the image extracted from it 84 ⟩ Used in section 83. ⟨ Extend f so as to make pict point (f, i, j) a valid reference 63 ⟩ Used in section 61. ⟨ Find first row above i with end > j and work back, making all intermediate rows end at j + 1 31 ⟩ Used

in section 28.

⟨ Find first row below i with start ≤ j and work back, making all intermediate rows start at j 30 ⟩ Used in

section 28.

⟨ General macros and typedef declarations 4, 7, 36, 45 ⟩ Used in section 3. ⟨ If diag row (d, i) has been newly created, reserve a slot in f→r, and set pict row (f, i) ⇐ ⊙ 64 ⟩ Used in

section 63.

⟨ Increase j to proper location, and then swap p with f→r[i].p[j] 85 ⟩ Used in section 84. ⟨ Insert the points of f→domain at the proper place into inv , meanwhile checking that the picture conditions

are satisfied 43 ⟩ Used in section 41.

⟨ Insert p into the tableau P, assigning to q the square by which it’s shape is extended 80 ⟩ Used in section 79. ⟨ Local function definitions 16 ⟩ Used in section 2. ⟨ Local typedef delarations 70 ⟩ Used in section 2. ⟨ Make sure that f→r can accommodate at least a more rows 65 ⟩ Used in section 64. ⟨ Make sure that r→p can accommodate at least one more point 67 ⟩ Used in section 66. ⟨ Make ∗p point to a new diagram with a single square (i, j) 29 ⟩ Used in section 28. ⟨ Make ∗p to a refer to a newly created picture with empty fields 62 ⟩ Used in section 61. ⟨ Move to first row above i_{0} with end > j_{0} and work back, applying glissements by rows from left to right,

ending in column j_{0} 77 ⟩ Used in section 75.

⟨ Move to first row below i_{0} with start ≤ j_{0} and work back, applying glissements by rows from right to left,

ending in column j_{0} 76 ⟩ Used in section 75.

⟨ Move to next position (p→i, p→j) or set p→complete 51 ⟩ Used in section 49. ⟨ Move to previous position (p→i, p→j); if none exists return false 54 ⟩ Used in section 53. ⟨ Perform glissement into (i, j) on d 73 ⟩ Used in section 72.

⟨ Prepare inv for use 42 ⟩ Used in section 41. ⟨ Prototypes of externally visible functions 5, 8, 10, 12, 14, 17, 20, 22, 24, 27, 34, 37, 40, 46, 48, 52, 56, 60, 68, 71, 74,

78, 82, 87, 91, 93 ⟩ Used in section 3.

⟨ Repeatedly slide an image into the empty square (i, j), until it is a corner of d 89 ⟩ Used in section 88. ⟨ Replace array d→r by one with at least size elements, and adapt bounds and contents so that diag row (d,

i) = ⊙ 33 ⟩ Used in section 32.

⟨ Reserve a slot for pict point (f, i, j) in the array r→p 66 ⟩ Used in section 63. ⟨ Test validity of the image (i, j); if incorrect, return error code 50 ⟩ Used in section 49. ⟨ Test validity of the image x of (i, j) 44 ⟩ Used in section 43. ⟨ 3 ⟩

PICT

Section Page

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 Skew diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Pictures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 10 Simple algorithms for pictures: reflections and glissement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 16 The generalised Robinson-Schensted algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 22 The Schützenberger algorithm for pictures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 25 References and Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 27