xsl-list
[Top] [All Lists]

RE: Omnimark vs. XSL (Saxon) Challenge

2004-03-18 08:27:24
Thank you very much for your ideas. I fear they are not easily applicable, 
because I have to keep the width of some cells, so I cannot easily discard 
processed rows. But I'll keep this in mind for other table related tasks.

What I am going for is to stop processing as soon as I have a valid column 
width for every column. In this case the processing time depends mainly on the 
structure of any given table, but especially with long tables it may shorten 
the processing time dramatically.

- Michael Müller-Hillebrand

On 17.03.2004 (16:13 Uhr +0000), Michael Kay wrote:

I think it's quite hard to come up with an algorithm here that isn't
quadratic. The best I can come up with as that you process the cells by row
and then column in a single recursive sequence, passing as a parameter a map
of which positions in the final table are already occupied. Expressing this
map as an RTF will require copying it at each stage, which will give you
quadratic performance; so try expressing it as a character string, which can
be copied at close to constant cost. (The fastest implementation of my
knight's tour turned out to be the one that represented the board as a
character string). I think the map can be as simple as a zero for a vacant
position, a one for an occupied position, and a delimiter for the end of
each row (you can discard rows once they have been processed). The algorithm
for processing each cell is then to find the map for the current row (which
is the first row in the map if you drop rows as you go) and look for the
first sequence of n vacant positions where n is the colspan; then create a
new map in which you mark these positions and any previous positions in the
row as occupied, together with corresponding positions in subsequent rows
within the range of the cell's rowspan, and then move on to the next cell. I
think this algorithm will be very close to linear.

Michael Kay

-- 
_____________________________________________________________
Dipl.-Ing. Michael Müller-Hillebrand
                                     
"Mehr Effizienz für Wissensarbeiter" --> http://cap-studio.de

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list