One type of table that occurs in practice is a completely unstructured collection of entries. A table containing a collection of photographs illustrating several aspects of a topic, in which the precise order of the photographs is unspecified, might require a formatting system to arrange the pictures to occupy the minimal space on a page. This can be formalized as RANDOM PACK, the problem of laying out an unordered set of rectangular table entries T = {ti} with entry ti having height hý(ti) and width wý(ti), so that the resulting table is bounded by the page width and has a minimum depth (to be more precise, the RANDOM PACK problem asks whether the table can be laid out to fit on a page of depth k). In laying out the table, whitespace may be left within the table boundary where entries do not abut exactly.

THEOREM 1. RANDOM PACK is NP-complete.

Proof. The proof follows from a reduction of the PARTITION problem, known to be NP-complete [Garey&Johnson, NP], to RANDOM PACK. Consider a table of rectangular entries, each with widths exactly one-half the page width but with arbitrary heights that sum to 2k. The best possible table arrangement would be two columns of exactly the same height (in this case k). This arrangement requires partitioning the entries into two subsets whose total height (the sum of the heights of its entries) is k. Thus, we are given a set of entries, T = {ti} with heights hý(ti) such that S hý(ti) = 2k, and we wish to find two subsets of T, S and S` = T—S, such that S hý(si) = S hý(s`j) = k. This is precisely the PARTITION problem. There, we are given a set of integers and are asked to partition them into two disjoint sets whose sum is the same. Given any instance of the PARTITION problem, we construct an instance of RANDOM PACK by specifying a set of rectangular table entries of width one-half the page and heights equal to the integers in the set to be partitioned. The original PARTITION problem has a solution if and only if the constructed RANDOM PACK table entries can be laid out with equally balanced column depths. This completes the reduction and the proof. ®

In fact, we can say more than this. Theorem 1 shows only that RANDOM PACK (and thus the general table layout problem) is NP-complete and hence almost certainly intractable. The PARTITION problem is known to have a dynamic programming algorithm that is polynomial time in the size of the set if there is a bound on the magnitude of the integers (the coefficients in the polynomial may be exponential in this magnitude) [Garey&Johnson, NP, page 90]. In formatting tables, the table entries are bounded by the page size, and thus the PARTITION problems that would be produced by the reduction in Theorem 1 would all have polynomial time algorithms. If the BIN PACKING problem is used instead of PARTITION we can in fact show that the table formatting problem is even more difficult than indicated by the the result of Theorem 1. BIN PACKING [Garey&Johnson, NP] is a problem which has no polynomial time algorithm unless P=NP, regardless of the magnitude of the numbers used in describing the problem (it is in the class of strongly NP-complete problems).

THEOREM 2. RANDOM PACK is strongly NP-complete.

Proof. We again perform a reduction from a problem known to be difficult. Consider a table of rectangular entries with integer widths less than the page width but with uniform heights. The table layout algorithm must minimize the number of rows required for the table in order to optimize space. This requires partitioning a set of table entries T={ti} having widths wý(ti) into k rows R1, R2, ..., Rk. This partitioning is an instance of the BIN PACKING problem, known to be strongly NP-complete. The proof follows that for Theorem 1. ®

We realize that RANDOM PACK does not produce very interesting or aesthetically pleasing tables. Few tables contain unordered entries (although the example given before, a collection of related but unordered photographs, is such a table). Even when a table is an unordered set of entries, the mix and match jumble produced by RANDOM PACK is not typical of the row and column structure usually employed for such tables. The juxtaposition of different sizes and shapes for the various entries does not lend itself to a readable table. An aesthetically pleasing table exhibits a design discipline for organizing the table entries that avoids unexpected relationships due to the random positioning of table entries. We are thus led from this general problem to introduce restrictions that make the problem more realistic and also more tractable for formatting, especially for interactive work.

There are two approaches to dealing with the general table formatting problem: accept an approximate solution to the optimal table layout or restrict the table formatting problem so that efficient optimal algorithms exist. Approximation algorithms for the TWO-DIMENSIONAL BIN PACKING problem, and hence for the RANDOM PACK problem, are known [Coffman, 2D Packing]. These approximations use polynomial time algorithms to produce layouts within 5/4 of the optimal space [Baker, 5/4 Algorithm]. The Up-Down (UD) algorithm presented by Baker et al. is known to have a bound UD(L) on the packing height for any list L of rectangles with height at most H as follows:

However, the table layouts produced by these algorithms are still unaesthetic, with a chaotic arrangement of small entries among the crevices between larger ones, as shown in the example layout of Figure 5-1 adapted from Figure 2 in Baker et al. [Baker, Packings].

Restricting the table arrangement leads to more aesthetic table layouts and to algorithms with polynomial running time. Introducing a row structure to the table by placing horizontal rules between the rows is the first restriction we consider. Once a rule is introduced into the table, it must extend all the way to the right of the table. These rules form the stub of the table (typical of financial tables) and hence this restricted table formatting problem will be called STUB PACK. Figure 5-2 contains an example of a STUB PACK table layout.

STUB PACK can be formalized as a set of unordered table entries T = {ti} with height hý(ti) and width wý(ti) that are to be placed into an arrangement bounded by the page width and having minimum depth. Each entry in the final layout is separated from the entry below it by a line (typographic rule) that defines a row of the table.

A polynomial time algorithm exists to solve the STUB PACK problem within 1.7 of the optimal space [Coffman, 2D Packing, Theorem 2]. The First-Fit Decreasing-Height (FFDH) algorithm described by Coffman et al. is shown to have a bound on the packing height of

While STUB PACK has a polynomial time algorithm, it still does not lay out the ordered tables normally encountered in practice. The row and column grid structure that occurs in tables imposes an ordering of table entries specified by the table designer, who has taken into account a number of aesthetic considerations. Restricting tables to be ordered in advance by the designer reduces the complexity of the table formatting problem (at the expense of possibly requiring greater space). An algorithm which performs table layout given the arrangement is what we need to achieve the aesthetics we desire.

The GRID PACK problem is to lay out a given set of table entries, each with a width and a height, where all of the entries are assigned to lie between particular row and column grid coordinates within the table. The layout is entirely determined once the physical (page) coordinates of the grid lines are known. These are determined by the width and height of the entries.

THEOREM 3: GRID PACK requires linear time.

Proof: The requirement is to determine the position of the grid lines. This can be done by a two pass algorithm that examines all of the table entries in turn. The first pass determines the relative width and depth of each row and column (horizontal and vertical pairs of grid lines) by ensuring that the relative width of the column is greater than the width of any entry in that column and that the relative depth of the row is greater than the height of any entry in that row. The absolute page coordinates of the row and column grid lines are then determined by accumulating relative widths and depths for consecutive grid lines. The second pass over the entries determines the page coordinates of each entry from the row and column grid coordinates. ®

The GRID PACK algorithm is similar to the one used by the tbl table formatter. Additional alignment possibilities may be incorporated into the GRID PACK problem through suitable extensions. As stated here, it does not handle spanned column headings or aligning table entries on decimal points. The remainder of this chapter will discuss the practical issues of table formatting, including a document structure and grid system for representing table layouts and an interactive algorithm for formatting these tables.

For formatting purposes, a table object in the extensible document structure can be thought of as a box and two procedures for laying out and rendering its content. The box concept is similar to the boxes used in eqn and TEX but with additional information required for alignment of table entries. The procedure concept is similar to the artist procedures used to render data structures graphically [Myers, Incense] or animate graphical objects [Kahn&Hewitt, Actors].

A table entry is abstractly represented by a box with four offsets (left, right, up, and down) from an origin implied by the content. This origin is the starting point for the rendering procedure that displays the content of the table entry. Four offsets, rather than simply a width and a height, permit alignment in both the horizontal and vertical directions simultaneously. Other schemes like eqn and TEX that represent boxes with fewer parameters provide less-functional alignment primitives. To align the table entry with other entries an alignment point is computed within the box depending on the typographic alignment style, as shown in Figure 5-4.

The layout procedure is given the arrangement and content of the table entries and determines their sizes and positions. A table's arrangement is explicitly determined by its creator when the table entries are collected in the document. This is analogous to the ordering of paragraphs in a document as it is created by an author.

The rendering procedure is given the positions of the table entries, as computed by the layout procedure, and produces the human-readable form of the table by recursively rendering the content of the table entries at each position. The rendering procedure relies on a device-independent graphics package that can produce a screen display or a file-based printer description of the table. This device-independent capability permits WYSIWYG interaction with table objects in their actual positions, subject to differences in device resolution. The separation of the layout and rendering steps permits the rapid redisplay of the table without recomputing the layout when the view of a table is moved or scrolled.

The document structure extensions for tables must capture the arrangement of the table entries as well as their content. Tables are two-dimensional, and in this respect are similar to mathematical notation in the microscopic sense, and to page layout in the macroscopic sense. However, tables are significantly unlike paragraphs of text, wherein text flows from one line to the next and there are few positioning relationships between text elements. It is precisely the positioning and alignment relationships between table entries that must be included in the table document model.

One might begin with the obvious row and column structure of the table. Many document formatting systems have chosen one of these as the dominant structure and expressed the table arrangement in terms of it, leaving the other structure implicit. For example, rows are the dominant structural element for tables in tbl. This choice appears natural since all the column entries of a row can be entered on the same input line, and the UNIX philosophy treats streams of characters as the unifying data structure.

This row dominance makes column operations more difficult. Adding a new row is simple; one adds a new input line to the source file. Adding a new column is tedious; each input line must have a new column entry inserted in the appropriate place, although special editors could help here. Another asymmetry between rows and columns in tbl concerns how one specifies spanned headings. A spanned column heading must be specified as a sequence of s layout codes for each column spanned, whereas a spanned row heading may be specified either by a ^ layout code for each row spanned or by a special formatting code \^ as the table entry content for each spanned row entry. The treatment of rows and columns in interactive table formatting should be symmetric to reduce the cognitive burden and to avoid errors.

A hierarchical structure suggests itself from the subdivision of rows and columns in tables. Figure 5-5 illustrates a table with its row and column subdivisions and the hierarchical data structure based on the columns. A column heading that spans several entries becomes a subtree root for those columns. Multiway branches are for spanned headings, single branches are for table entries. A dual hierarchy would be expected for the row structure. Such a dual hierarchical scheme was unsuccessfully attempted in a previous table formatting prototype [Beach, CS740 project]. The implementation was complex and the data structures were difficult to coordinate. Many of the algorithms had to be duplicated for the row and column cases. The crucial realization was that not all table designs can be represented as hierarchical tree structures. In particular, the table in Figure 5-5 does not have a hierarchical row structure because heading D has two row parents, C and G. A more general underlying structure is required. This is the topic of the next subsection.

When they exist, the dual row and column hierarchies do provide powerful interactive selections of parts of tables. This selection hierarchy notion is similar to a text selection hierarchy which enables one to select a character and extend the selection through various levels of structure from a character to a word, sentence, paragraph, section, and ultimately the entire document. Starting from a selected table entry, one can extend the selection to include all entries in the containing row or column by traversing either the row or column hierarchy. Successive extensions of the selection would include containing rows or columns until the entire table is selected. While a hierarchical table representation was

A more general representation of table arrangements must simultaneously satisfy several goals: it must exist within a hierarchical document model, it must embed arbitrary table entry objects, and it must describe the arrangement and positioning relationships of the table entries. The hierarchical document model cannot be used directly because tables are not always hierarchical, for example, the box head in Figure 5-5 is nonhierarchical. The insight applied here is that one need provide the data structure for tables explicitly in the document model. Instead, the table arrangement can be described indirectly in terms of a grid coordinate system with table entries having associated grid coordinates. This permits a table object to be represented by a collection of arbitrary table entry objects and the table arrangement to be specified by the grid labelling. The entries may be listed in any order since the labelling will determine the table layout.

The proposed grid coordinate scheme expresses the table topology. This in turn determines the arrangement of table entries between the grid lines, and thus determines which table entries are neighbors and which entries share the same boundaries. Grid modules between grid lines may be nonuniformly spaced to permit both narrow and wide entries. Each table entry is surrounded by four grid lines, one each on its left, right, top and bottom sides. A row is bounded by two horizontal grid lines, and a column by two vertical grid lines in a symmetric fashion. Entries in the same row will share the same pair of horizontal grid lines, similarly for entries in the same column. A spanned column heading will cross several grid lines and is bounded by the left grid line of the leftmost spanned entry and by the right grid line of the rightmost spanned entry. An arbitrarily complex arrangement of table entries can be specified by listing the four grid lines for each table entry. Figure 5-6 contains a table with the grid coordinate system overlaid as light grey lines.

Typographic rules and decorations can be superimposed on the grid boundaries. In this case, the grid boundary has a nonzero width equal to the thickest rule that runs along that grid line. Note that both horizontal and vertical rules are treated symmetrically.

The table layout geometry, that is, the actual position of each grid boundary and each table entry, is computed from both the table topology and the dimensions of the table entry contents. A mathematical linear inequality constraint solver permits general alignment relationships to be expressed, such as the equal column widths shown in Figure 5-6. The independent variables in the inequality constraints are the positions of the grid lines and the alignment points of table entries. An incremental constraint solver that can accept new or changed constraints permits interactive modification of the table arrangement.

Similar grids have been used in the graphic arts since grid systems were first developed by designers in Switzerland shortly after World War II. The principle behind a grid system is an objective attitude to the presentation of the subject material and to the uniformity in the layout of all pages. Grids institute a disciplined approach to design and layout, limiting the number of choices to provide regularity and order in potentially chaotic situations.

Several graphic designers have written about grid systems in books including Muller-Brockman's Grid Systems in Graphic Design [Muller-Brockman, Grid Systems], Hurlburt's The Grid [Hurlburt, The Grid], and Williamson's Methods of Book Design [Williamson, Book Design]. Some computer composition systems have incorporated grid systems. One early example was Tilbrook's NEWSWHOLE [Tilbrook], a prototype system for interactive newspaper page layout. Hurlburt [Hurlburt, The Grid] describes the modular design and sense of proportion induced by a grid design. Several proportions, such as the Golden Ratio, square, and 2 rectangle, are commonly used as the basis for grid designs. Letter form design is also often constructed to conform to a grid design [Goines, Constructed Alphabet].

Unlike the orthodox grid formed by uniformly spaced horizontal and vertical lines to produce square modules, the typographic grid is more casual with lines introduced to specify margins on the page, column measures, and alignment guides. Common grid lines are the headline, the first line of text on a page, the first line of a chapter title, the first line of text within a chapter, the last text line on a page, and the footline. Figure 5-7 shows the grid design for the pages of this thesis.

The interactive newspaper pagination system NEWSWHOLE [Tilbrook] is an example of the application of grid systems for layout and formatting. The grid lines in that system were active; they could be stretched and moved across the page at the user's command. There was a simple constraint satisfaction to ensure that there were always an integral number of grids across the section of the page and that the grids were equal width. The NEWSWHOLE prototype had only limited text composition capabilities, and it did not attempt a WYSIWYG presentation of the entire page (mainly due to display resolution, which will always be a problem). The same idea can be used here to do interactive tabular composition and is discussed in Chapter 6.

The document style mechanism must also be extended to incorporate additional table formatting attributes and to apply those attributes to table entries. The additional tabular style attributes include various alignment specifications (decimal or character alignment, top or bottom baseline alignment, centered top or bottom baseline alignment), various rule parameters (rule thickness and color), and various bearoff distances (the whitespace between table entries and the grid lines).

Applying style attributes to table entries is harder than for text or illustrations because the attributes may come from several nonhierarchical sources. Figure 5-8 illustrates some of the possible interactions among style attributes applied to parts of a table. The whole table may have a general formatting style. Rows or columns may have particular style rules for the entries within those rows or columns. Each table entry may have additional local formatting attributes applied that override the other specifications.

Because tables have both a row and a column structure that in turn has nested subrows and subcolumns, there may be several row or column style rules applicable for a given table entry. The nested containment of a table entry within a row and/or a column can determine an appropriate search path for applying style rules. The rendering algorithm first applies the style attributes specified in the style rule for the entire table. It then applies attributes for each containing row or column that successively contains the table entry, down to the attributes for the given table entry. When style rules do not specify values for all the possible style attributes, values are inherited from previous style rules along the search path. Style rules may be specified for both a row and a column containing the given table entry, in which case it is necessary to disambiguate the row or column preference. The solution taken here is to provide a Boolean

Alignment relationships between table entries are controlled by the alignment points of the table entry objects. These relationships are generalizations of the mark and lineup alignment specifications for equations in eqn. Formatting style attributes determine the alignment point based on the typographic treatment of the table entry. Centered alignment places the alignment point in the middle of the object box by dividing the sum of the appropriate pair of dimensions by two. Flush left, right, top or bottom alignment places the alignment point at the appropriate edge of the box. Aligning on a character within the table entry sets the alignment point to be the origin (which may be chosen from one of several alignment options) of that particular character. Figure 5-9 illustrates two columns of character-aligned table entries, the first aligned on decimal points (including the implied decimal point at the end of a numerical string), and the second aligned on a multiplication sign.

The positioning of odd-sized table entries requires additional information, especially for text entries that are folded into multiple lines or for entries with varying heights like mathematical expressions. The top row in Figure 5-10, which has been horizontally aligned on the center of each table entry, demonstrates the disjointed result when baselines of folded entries do not align across the column. Simple horizontal alignment attributes such as flush top, flush bottom, or center do not take into consideration the internal structure of a table entry. Additional alignment choices are needed to align on the baselines within a text table entry, such as align on the top or bottom baseline. Text entries with an even number of baselines have two middle baselines for centering, thus requiring two choices to center on either the top-middle or bottom-middle baseline. The bottom row of Figure 5-10 demonstrates the range of alignment choices available for aligning baselines within table entries.

Establishing the alignment point on baselines within a table entry implies that the document object must understand all these alignment choices. The simpler alignment attributes, such as flush top or bottom, could be computed from the representation of an object and its four offsets (except for decimal or character alignment). Some table entry objects have little similarity to text objects, yet the alignment attributes must apply to all objects in a uniform way. The technique used in the prototype is to extend the representation of a table entry to include an optional list of baseline origins. Should the list be absent, the default baseline is chosen to pass through the origin of the object. Alignment attributes that concern themselves with content, such as decimal alignment, are left as the responsibility of the table entry object. Some objects may choose to ignore text alignment attributes. For example, a scanned illustration object contains no characters, so it could safely ignore those attributes.

Another alignment attribute deals with the excess whitespace in the wide columns in Figure 5-11. In this example, the table entries in each column are aligned on decimal points. The last two columns need further specification: how should the excess whitespace induced by the very long column heading be treated? This additional specification determines how the vertically aligned set of column entries are positioned within the column. The choices are centered, flush left, or flush right. Currently, the table formatting prototype does not support this positioning specification, but a more complete implementation is planned and described in Chapter 6. In tbl, numeric entries that are aligned on decimal points are centered within the column after they are aligned on decimal points; there is no control provided over the distribution of the excess whitespace.

Textual table entries may be more complex than just simple phrases or numbers. Some entries may be paragraphs with long lines of text broken into pieces short enough to fit within the column boundaries. Yet the layout algorithm attempts to determine the width of the column boundaries from the widest line in the broken paragraph. Thus the line-breaking algorithm depends on the column width and the column width depends on the width of lines folded by the line-breaking algorithm. How does one exit from this circular dependency?

In existing table formatters, such as tbl, the only technique for dealing with this problem is to require the table designer to supply an explicit column width attribute. In fact, this is an easy way to specify equal-width columns, since no matter what the content of the entry, all such designated column entries are forced to be the specified width. Unfortunately, fixing the column width often results in an unaesthetic table. Short justified lines induce more hyphenation and larger spaces between words, making the entries more difficult to read. Unjustified lines are easier to read but extra whitespace accumulates at the end of lines creating the illusion of unevenly spaced columns.

A better strategy would be for the formatter to accept the line length as only a `hint' for folding the text to approximately that length. The actual bounding box of the composed text could be returned by the object layout procedure or determined by a scan of the formatted object. With the bounding box, a folded table entry can be treated uniformly as any other entry. A feature of this strategy is that a column of folded entries is only as wide as necessary without excess whitespace.

The problem of determining an aesthetically pleasing column width for a column of entries with widely varying widths or for a table that exceeds the page measure is a very hard problem and is not solved here. Some directions for determining optimum column widths for folded table entries and for balancing whitespace are outlined in Chapter 6.

An external storage representation is normally concerned with compactness and ease of conversion between external and internal representations. However, because the prototype relies on the Tioga document structure, the external representation of a table must be a textual description of the table. This representation is editable by the Tioga text editor. While this is an advantage for testing the prototype, it is expected that an interactive user interface will be built to permit most editing actions without resorting to editing the textual representation directly. We believe, however, that the textual description is useful for debugging, for document interchange, and for possibly fine tuning table structures.

A table is represented as a subtree of nodes in a Tioga document hierarchy. The root node of the table subtree has an ArtworkClass property (described in Chapter 3) of Table to distinguish the subtree as being a table object (as distinct from text or illustrations). This Table property is recognized by the table formatting prototype which interprets the contents of the subtree as a collection of table entries. The table entries themselves may contain an object of any document object class since the object layout and rendering procedures understand the content of the object. This object-oriented design permits arbitrary recursion within document content at any time.

The table representation is converted into the internal data structure whenever a table is edited in a WYSIWYG fashion or formatted. After manipulating the internal data structure (perhaps changing the table topology or the content of some table entries) the internal data structure is converted back into a Tioga document subtree. The new subtree is spliced into the original document to replace the previous table representation.

Only topological information is represented in the table description. Table entries are described by the grid coordinates that they occupy. Typographic rules are described by the grid lines along which they run. The table previously shown as Figure 5-6 has been annotated with grid coordinate values in Figure 5-12. Horizontal and vertical grid lines are each numbered beginning at 0 and incrementing for each successive grid line. A column or row is contained within two grid lines (not necessarily two consecutive grid lines). Thus the column containing the heading ``Spanned over Four Columns'' is contained within vertical grid lines 1 and 5. Two typographic rules are shown along vertical grid line 1 and along horizontal grid line 3. The table in Figure 5-12 will be used both to illustrate the external table representation (in Figure 5-13) and the internal data structure (in Figure 5-15).

A table is described in general terms by the contents of the root node of its table subtree. In Figure 5-13, the table is formatted on a 6 by 6 grid (for 5 rows and 5 columns). A grid overlay 3-points thick in a light gray color (hue 0, saturation 0, brightness 0.7) is superimposed on the table to make the grid coordinate system visible. (This grid overlay would not appear on printed tables, except for expository purposes, although the grid overlay serves as a useful target for interactively manipulating the grid topology.) The direct descendants of the table root node within the document describe the table structure and table entries in more detail. There are four things to describe: constraints on the grid coordinate layout, boxes containing table entries, typographic rules, and background shaded areas.

The internal data structure for representing tables must meet several criteria. It must represent the arrangement of table entries in both the horizontal and vertical directions. It must support row and column selections and a selection hierarchy within containing rows and columns. It must also permit fast algorithms suitable for interactive table editing operations and for conversion to/from an external form.

The data structure chosen for the table formatting prototype was the corner stitching data structure employed by Ousterhout [Ousterhout, Corner Stitching] for his VLSI layout tools. An implementation by Shand [Shand, CornerStitching] which runs in the Cedar environment was modified and extended for the prototype.

The corner stitching data structure tesselates the plane with rectangular tiles. Each tile is connected to its neighbors by four compass-point links and each tile references its associated data. The corner stitching implementation uses special border tiles surrounding the tesselation to simplify the algorithms. Figure 5-14 illustrates a prototypical tile and a fragment of the tesselation showing how several tiles are connected together.

To use the corner stitching data structure there must be a geometric coordinate system. The table topology specified by the grid structure has no geometric information, only the presence or absence of table entries and their relative positioning. Grid boundaries between table entries must have nonzero width, even in the table topology, since provision must be made for typographic rules. Therefore the corner stitching coordinate system has distinct coordinate values for table entries within the grid lines and for typographic rules along the grid lines. The topology is highlighted in the table prototype by representing table entries as unit squares and grid lines as lines with unit widths. (Some additional separation between grid lines and table entries is provided in the prototype to help distinguish between adjacent tiles. Thus the table grid coordinates are in fact multiplied by four to create corner stitching coordinate values.) The coordinate mapping is indicated in Figure 5-15, which presents the corner stitched data structure for the table in Figure 5-6.

The external description of the table is parsed to create the internal data structure. The internal table description is held in a table object record, which remembers the table document subtree. Later, an updated external table description is spliced into the subtree after edits. The table object record also points to the grid tesselation of table entries and there are fields for the grid positions and table origin that will be computed later by the table layout algorithm. The auxiliary constraints provided by the table designer are contained in a linked list.

The corner stitching data structure tesselates the plane with tiles. An initial tesselation contains a single tile that serves as a universe. A tile object contains four pointers for the major compass-points, a tesselation coordinate value, and a generic pointer to its associated data. (In Cedar, a generic pointer permits a data structure to be used in several different applications without the algorithm knowing the type of the data. The application is responsible for providing the pointer value and for later asserting the type of the pointer whenever the pointer is dereferenced to access the data fields.) New tiles are added by splitting the universal tile to maintain a ``maximal East-West strip'' property, which can be seen in Figures 5-14 and 5-15.

The table formatting prototype creates a table entry record for each corner stitched tile. The table entry contains the grid coordinates and the kind of table object. A box table entry points to the document object that will appear in the table, and retains the box dimensions, origin, and alignment point computed by the layout algorithms. Typographic rules and background table entries have no content. The style attributes are remembered as a list of attribute-value pairs.

The corner stitching data structure is inherently planar, whereas some tables may involve overlapping table entries or rules. There are three things that may overlap: table entries that are ``pasted over'' other entries, rules that intersect with other rules, and backgrounds that underlay part or all of the table. The positions of all these overlapping elements can be expressed in terms of grid boundaries, so no additional layout information is necessary or generated by overlapped entries.

Backgrounds can be easily handled because there are generally few of them (often only one per table) and their size depends on and does not influence the table layout. It is sufficient to maintain a list of background rectangles to be shaded in the table object, so the rendering algorithm can traverse the list and paint the shaded background before rendering the rules and table entries.

Overlapping rules within tables are more interesting and more common. Rules intersect when a horizontal rule and a vertical rule meet. Even if the rules are of equal thicknesses, the end points of the rules must be adjusted to ensure that they avoid a notched corner, such as the leftmost examples in Figure 5-16. Additional complications arise when two rules of different colors or textures intersect. Then one of the rules dominates and the other rule should have its endpoint adjusted to avoid penetrating the first, as shown by the middle examples in Figure 5-16. The prototype implementation only handles rules with square ends but an extension capability is available to add other intersection types.

The fragmentation of corner stitched tiles, when a tile is about to penetrate an existing tile, provides the opportunity to capture the notion of intersecting rules explicitly. For example, the capability for rounded corners (as shown at the bottom right in Figure 5-16), or for placing special ornaments at the intersection of two rules can be specified at the intersection tile. The intersections between double or multiple rules can be treated in various ways. This technique for capturing the intersections between rules permits a general mechanism for specifying style attributes that apply to typographic rules and border patterns.

Overlapping table entries might be handled by maintaining an overlap order when they intersect. Table entry tiles in the grid data structure presently reference a single table entry. For overlapping entries, the tiles would have to maintain the list of overlapped table entries in overlap priority order. The rendering algorithm could then be modified to render the list of overlapped entries from back to front using the Painter's algorithm. These extensions for overlapping table entries have not been implemented in the prototype.

The main algorithms presented in this section are the table layout and table rendering algorithms. The table layout algorithm takes a table arrangement and produces the positions of the grid lines and table entries. The table rendering algorithm is responsible for creating a printable or displayable version of the table given the positions and content of the table. These two algorithms require an enumeration algorithm to act on all of the table entries in the internal table data structure. Interactive manipulation of tables requires a hit-testing algorithm, which resolves the table entry that is being pointed at on the screen, and dynamic restructuring algorithms to insert and delete parts of a table.

Examples of constraint systems in computer graphics provided the motivation for this technique. Sutherland's Sketchpad [Sutherland, Sketchpad] was a seminal interactive graphics system that relied on constraint satisfaction to position graphical elements. Borning's implementation of Thinglab [Borning, Thinglab] demonstrated the use of constraints in several problem domains. The document layout and document content examples in his report were of particular interest. The layout example [Borning, Thinglab, p29] showed a paragraph surrounded by a rectangle precisely large enough to hold the paragraph. When the width of the rectangle or content of the paragraph was changed, the rectangle's height was adjusted accordingly.

Several other graphics systems used constraints to position things. JUNO [Nelson, Juno] and ideal [van Wyk, ideal] both use nonlinear constraints to determine the position of graphical objects. pic [Kernighan, pic] labels the corners of boxes and position objects relative to those labellings. The graphical debugger Incense [Myers, Incense] contained a heuristic for positioning nested objects in a data structure by dividing the available space in two. The ability of these systems to position parts of an illustration relative to one another was very attractive and analogous to the layout of table entries relative to one another.

Linear inequalities are sufficient to describe the positioning relationships between table entries, such as making a column wide enough for an entry, or making a row heading tall enough to span several rows. Restricting the constraints to linear inequalities prevents expressing area relationships, but it is more common to express such relationships by establishing a ratio among the sides of the rectangle which can be described by linear inequalities. All the distances in a table can be expressed as rectilinear (horizontal or vertical) distances. Thus addition, subtraction and scalar multiplication are the only operations needed to express the table positioning relationships.

Using inequalities introduces the notion of slack variables that turn the inequality into an equality for the constraint solver. These slack variables capture the extra room left over for the table entry to fit the grid lines. Smaller table entries have greater slack than larger entries, and one or more table entries will have zero slack. The slack variables are helpful in determining whether the constraint system must be recomputed when editing a table. A table entry with slack may grow or shrink without requiring the constraint system to be recomputed, while a table entry with zero slack that changes size will always require recomputing the grid lines.

The linear inequality solver due to Nelson [Nelson, Program Verification] used in the table formatting prototype has an useful property for implementing an undo facility in an interactive table editor. The constraint tableau maintains a stack of `dead' tableau columns which permits a previous state of the tableau to be recomputed quickly. Changes to the table that modify table layout constraints may be quickly undone through this mechanism without recomputing the entire solution of the constraint system.

Solving a system of linear inequalities is equivalent to the LINEAR PROGRAMMING problem, which is known to be solvable in polynomial time [Khachiyan, LP]. A table arrangement without centered table entries can be described by a system of linear inequalities using only two variables per inequality, as described in the next section. This particular LINEAR INEQUALITY problem for two variables can be solved in O(n3) worst case time [Aspvall&Shiloach, Linear Inequalities], where n is the number of constraints. Algorithms for solving more general systems of linear inequalities based on the Simplex method have O(n3) expected time behavior [Dantzig, LP]. A version of the Simplex algorithm due to Nelson [Nelson, Program Verification] was implemented in the table formatting prototype.

The table layout algorithm introduced in Section 5.4.4 depends on a linear inequality constraint solver to compute the positions of the grid and table entries. This section discusses the linear inequalities actually used to describe the table arrangement.

Consider a particular table entry represented as a box k. This table entry is positioned within a pair of horizontal grid lines and a pair of vertical grid lines as shown in Figure 5-17. The alignment point of the box is to be aligned with other boxes that share the same pair of grid lines. Label the four grid lines surrounding the box as leftGridk, rightGridk, topGridk, bottomGridk. Label the offsets from the alignment point to the edge of the box as distances leftOffsetk, rightOffsetk, topOffsetk and bottomOffsetk (these offsets are fixed by the content and can be determined before table layout). The position of the alignment point within box k will be (Xk, Yk).

The vertical grid lines represent column boundaries and their positions are designated by the variables Ci. The horizontal grid lines represent row boundaries and their positions are designated by the variables Rj. Boxes within the pair of grid lines left and right that are vertically aligned will be positioned at the variable Vleft,right, while boxes horizontally aligned within the row between grid lines top and bottom will be positioned at Htop,bottom. All variables are restricted to positive values.

The objective function for the constraint solver will be to minimize the width and depth of the table. For a table with m rows and n columns, the objective function would be

The table layout the relationships among grid lines and alignment points can be described by inequality constraints. The first set of constraints (1) ensure that all of the grid lines are in the expected order and that the alignment line is within the column. One set of constraints is required for each pair of grid lines, left and right, that contain a table entry. (Column constraints are used in the examples that follow; row constraints are similar.)

A constraint to ensure that the grid lines are sufficiently far apart to contain the width of a table entry is generated for each table box k:

In practice, these two sets of constraints are not generated explicitly since they are subsumed by the alignment constraints below.

The alignment constraints vary with the type of alignment requested. Aligning a table box flush left in the column without regard to any other box in

Similarly, aligning a table box flush right in the column without regard to any other box switches the equality and inequality constraints from those in (3L):

Centering a table box within the column may involve one of two centering concepts. The first forces the box alignment point to be equidistant between the column grid lines:

The second centering concept positions the box to balance the excess whitespace surrounding the box. The excess whitespace is the width of the column (CrightGridk — CleftGridk) less the width of the box (leftOffsetk + rightOffsetk):

Note that up until now none of these alignment constraints involved aligning a set of boxes with each other, only positioning the box within the column. To align several boxes, we need to force the alignment point within a box to be equal to the position of the alignment line within that column. Thus, for each box k in the set, generate an equality constraint:

The positioning constraints for each box aligned within a set are simpler because they only require that the box fit within the column:

However, these constraints are not sufficient to force the set of boxes to be flush left, flush right, or centered within the column. This must be accomplished by guiding the constraint solver to a particular desired solution. For example, to force the set of aligned boxes flush left, the objective function to be minimized by the constraint solver must be augmented with a term for the left distance:

Centering the alignment line for a set of boxes within a column may be accomplished in two ways. The first simply positions the alignment line equidistant between the column grid lines and does not involve an additional term in the objective function:

These linear constraints can be generated automatically for a table from the information kept in the grid data structure. A small expression language for constraint inequalities is provided in the prototype for the table designer to describe additional constraints for special effects. For instance, to create two columns of equal-width, say the column between grid lines left and right and the column between left` and right`, the following equality constraint is added to the table specification:

The constraint scheme just outlined suffers from rapid growth in the problem size as the tables grow larger. Several strategies can greatly reduce the number of constraints generated.

The first strategy eliminates redundant variables whenever they appear as aliases of other variables. For example, the box position Xk is often an alias for VleftGridk,rightGridk when they are set equal and therefore Xk can be eliminated.

In many table layouts, a simplifying assumption may be made to solve the row and column constraints separately. Treating the two sets of constraints independently reduces the number of constraints and the size of the corresponding constraint tableau. It is worth assessing the necessity of this assumption and the situations in which it is violated.

The independence assumption does not hold when one wants to create grid designs with modules that are square or have specific aspect ratios. A square module results from constraining the row height to equal the column width. Obviously, in this situation the sets of row and column constraints are not independent. The assumption is also not true when trying to distribute whitespace within a table, for example, by folding wide horizontally-oriented table entries to trade off more vertical depth for less horizontal width. In this situation, decreasing the column width increases the row height and the constraints are again not independent.

The independence assumption can be tested automatically by examining the variables in each constraint. Constraints that mix row and column variables, such as one specifying that a row height equals a column width, are interdependent and must be solved simultaneously. Constraints that do not mix variables are independent and can be solved separately as smaller problems. The prototype currently assumes that the row and column constraints are independent, but one could easily check the explicitly supplied constraints for violations of this assumption and thus determine automatically whether to solve the table layout constraints independently or not.

What is the cost of solving interdependent row and column constraints? When the two sets are combined into a single constraint system the problem size is doubled. Since the constraint solver takes O(n3) time on average, the combined constraint layout would require about four times as much as the sum of the two smaller independent computations.

A reduction in the number of constraints can also be achieved by observing the structure of the constraint inequalities. The constraints that determine the grid positions surrounding a particular table entry are all similar:

A further optimization in the linear constraint solver can be made based on the observation that most of the constraint inequalities have only two variable terms. Thus, sparse matrix techniques might reduce the space requirements of the solver at the expense of more overhead in the constraint solver. The prototype implementation uses a conventional matrix structure for the constraint tableau.

The complete table layout algorithm including the constraint solver can now be presented. The algorithm requires the grid data structure for the table arrangement and the contents of all of its table entries. The first step in the algorithm ensures that the dimensions of all of the table entries are known. These dimensions are provided by invoking the particular layout algorithm for each table entry object. In the event that a table entry contains another subtable, then the layout algorithm would be invoked on that subtable first. The dimension information for each table entry is cached in the table entry object since the box dimensions are used twice when the row and column constraints are independent.