The problem with Keirons layout code (with respect to large input files) is that it works top-down on the LM tree and thus require the creating of the complete LM tree for the page sequence. To better fit within SAX event model the layout process should also be event driven, triggered f.ex by the endBlock() and character() events. That means that the traversing of the FOTree cannot be easily done using recursive decend. Instead the main loop over the FO tree could use a non-recusive tree treverse like this:
public Element traverse(Node q, Node end, int mode) { while (q != end) { switch (mode) { case FIRST: // First time in the node. preorder(q); if (q.hasChildNodes()) { q = q.getFirstChild(); break; } mode = NEXT; // fallthrough case NEXT: // All children are handled. postorder(q);
// Add the node to its parent. if (q.getParentNode() != null) { child(q.getParentNode(), q); } // fallthrough case RESTART: // Attempt to move vertically to next sibling.
horizontally?
if (q.getNextSibling() != null) { q = q.getNextSibling(); mode = FIRST; break; } // No sibling found, move to the parent to // do postorder. q = q.getParentNode(); mode = NEXT; } } return null; }
...
The loop can be stopped when we temporary run out of FO tree nodes and restarted again when new nodes has been added. I suppose that the FO tree can then be viewed as a stream of FO nodes.
[Peter]
I suppose so. And I suppose that making layout event-driven would better fit in with the SAX event model. It just doesn't make sense from the point of view of layout which is basically a top-down process.
By top-down, do you mean the visiting order of the nodes in the tree? Or the structure of the code that does the layout? Like this:
process(Node n) {
preorder(n)
for (each child in n) {
process(child)
child(n, child);
}
postorder(n);
}The traverse() code does the exact same as the process() code. The differences are:
- All people immediately recoqnize process(). - process() can use local variables to store state.
A major drawback of process() is that is darn hard to suspend processing and then restart it. Our current getNextBreakPoss() code is a nice example of just how hard it is.
regards, finn
