On Jan 14, 2007, at 22:51, J.Pietschmann wrote:
Andreas L Delmelle wrote:
Based on Jörgs statistics, I'd say that the number of children
will most likely never reach the level where using direct index-
based access (ArrayList) has its benefits over traversing a tree
of references (LinkedList).
There may be FOs, specifically fo:flow and fo:table-body, which may
have hundreds of children in real documents.
If the FOs use access functions for the children, even for adding,
each FO can implement a mechanism which suites its purposes best. In
particular, page masters and tables can store the regions in typed
fields, FOs which don't have children can get rid of the field
completely.
This happens already for some FOs. Tables for instance, override
addChildNode() and store only bodies as their 'child nodes'. The
header and footer have separate typed fields, the columns end up in a
separate standard List. Behavior for markers is another example, they
too end up in a separate collection (map).
I've already been experimenting locally with removing the List
member, and replacing it with pointers to the neighbors. As I re-
implemented FObj.addChildNode(), it occurred to me that FOs with a
possibly larger amount of children would need to traverse the entire
list to append child nodes to the end. For a handful of children,
this costs virtually nothing, but as the list gets bigger... Could
easily be solved though for the applicable FOs, by keeping a
reference to the last added child, and giving it an addSibling() method.
I'm not sure whether the layout engine places any restrictions on the
access to FO children. Is it possible that access is not random?
FTM, there are only a handful of places in the code where the
childNodes list is accessed using an index.
The only way it can be accessed by classes outside the fo package is
through FObj.getChildNodes(), and that method returns a ListIterator,
not the list itself. The LMs only need access to these iterators
while creating their childLMs, which is done in forward sequential
order, i.e.
for (Iterator i = AbstractLM.fobjIter; i.hasNext();) { ... }
[Note: these are ArrayLists we're talking about. Iterators are far
from the best approach with lists implementing RandomAccess. Not that
this matters much if the lists are small...]
This fobjIter is created in the constructor of the LM. IIC, this
means that there is currently no way to, for example, instantiate the
FlowLM as soon as the first endBlock() event occurs, and keep
extending the flow's list of child nodes in a different thread. The
FlowLM's fobjIter will then throw a ConcurrentModificationException().
In the structure I'm currently playing with, it would be possible to
construct an iterator over an FObj whose child nodes are not all
known, move to the last node in the list, put the iterator in a stack
(or keep a reference as an instance member), continue adding nodes in
another thread, return, and continue iterating (a call to next() will
then return the first node that was added after the iterator was
paused).
That would be mighty dangerous if the access to the nodes was not so
predictable, but as it stands now, this could turn out to be a
benefit, if documented properly.
Removal from and addition to the tail of the list are never a
problem. The iterator will simply keep following the following-
sibling reference until it is null.
The head of the list might become a problem if one needs a decent
implementation of nextIndex() and previousIndex(). If we never really
need the index, then the fact that a child was added at a previous
position will simply make the iterator go back a few steps further
than where it started.
Cheers,
Andreas
