Smart span algorithm for table cells

A summary of the current iteration of the smart headers algorithm for 
associating table cells with heading cells. The essential idea is that 
headings only apply down/across the table as long as there are no other 
heading with the same colspan/rowspan. The following is a summary of the 
code at [1]; it probably contains mistakes. The writing style is very 
inconsistent, for which I apologize :)

In slightly more detail, the latest iteration of the algorithm is:

The basic algorithm for assigning headers to a cell is:

1. Run the algorithm to extract table headers from a headers attribute
  (n.b. controversial; could be replaced by the same algorithm applied
  to aria-describedby). If this returns any headers let those be the
  headers for the cell and abort these steps.

  2. For each heading in the table that has had cell associated to it by
  the smart span algorithm (below), add that heading as a heading for
  the cell.

The algorithm to extract table headers from a headers attribute is (in
outline):

1. If the cell has no headers attribute, there are no headers, abort
these steps

2. Otherwise, let headers be the list of headers

3. Split the cell's headers attribute on whitespace. For each token in
the resulting list, perform the equivalent of getElementById(token) on
the subtree rooted at the cell's closest ancestor <table> element. If
this returns a <td> or <th> element add that element to
headers. Otherwise ignore the token.

4. Return the list of headers

The smart span algorithm associates a header with a set of data cells. 
It is:

1. Let header be the table heading for which the associated cells are
to be determined. Let cells be the list of data cells to which that
heading applies.

2. If header has a scope attribute and it's value, when transformed to
lowercase, is in the set ("row", "col", "rowgroup", "colgroup") then
let scope be that lowercased value. Otherwise let scope be auto.

3. * If the value of scope is "auto", let cells be the concatenation
of the values produced by running the get cells from axis algorithm
with the axis set initially to row and then to column, and with the
skip heading only axis flag set to true

* Otherwise if the value of scope is "row", let cells be the value of
the get cells from axis algorithm with the axis set to row and the
skip heading only axis flag set to false

* Otherwise if the value of scope is "col", let cells be the value of
the get cells from axis algorithm with the axis set to column and the
skip heading only axis flag set to false

* Otherwise if scope is rowgroup run the get cells from group
   algorithm for the rowgroup containing header (determining which
   group this is is left as an exercise to the reader)

* Otherwise if scope is colgroup run the get cells from group
   algorithm for the colgroups containing header (determining which
   group(s) these are is left as an exercise to the reader)

The get cells from axis algorithm is:

1 Let header be the heading for which the algorithm is being run,
cell_list be the list of cells with which header is associated, axis
be the axis ("row" or "col") over which the algorithm is being run and
skip heading only axis flags be a boolean indicating whether to
skip axes containing only heading cells

2 let span be the number of rows spanned by header on axis

3 for each row or column spanned by header on axis:

     3.1 If skip heading only axes is set and all the cells on the
     current row/column are headings, return an empty cell_list and
     abort these steps

     3.2 let data_found be false

     3.3 let current_cell be the cell immediately adjacent to the header
     on the current row/column

     3.4 If current_cell is a heading:

        3.4.1 If current_cell's span across the current axis is equal to
     span and data_cell_found is True then go to step 4


        3.4.2 Otherwise, if current_cell's span across the current axis
     is greater than or equal to span add current_cell to cell_list

     3.5 Otherwise current_cell is a data cell. Add current_cell to
     cell_list and set data_cell_found to be true

4 Return cell_list
 


Notes: This does not associate a cell that overlaps with the header
cell.  It is not clear that the handling of groups of headers in the
middle of the table is sophisticated enough; however we deal with
simple cases where the headers match those at the beginning of the
axis


The get cells from group algorithm is:

let header be the header for which associated data cells are being
determined, let cell list be the list of headers associated with the cell.
1. For each cell in the group:
   1.1 If cell is anchored at a slot such that cell_x >= header_x and cell_y
 >= header_y then append cell to cell list
2. Return cell list

[1] 
http://code.google.com/p/html5/source/browse/trunk/tables/lib/headers/smartheaders.py

-- 
"Mixed up signals
Bullet train
People snuffed out in the brutal rain"
--Conner Oberst

Received on Monday, 10 March 2008 22:20:01 UTC