XOM API for Processing XML with Java

[Wolfgang Hoschek <whoschek AT lbl.gov>]

Turns out I hit the SEND button too fast :-)

I was thinking on terms of a read-only XPath model. But the patch 
doesn't work for subsequent tree insertions/removals because the 
positions of all other siblings would need to updated as well, which is 
way too expensive. Intuitively, a HashMap{Node,int} would be too 
expensive as well :-(

Anyway, please ignore the patch...
Wolfgang.

On Jan 25, 2005, at 11:19 AM, Wolfgang Hoschek wrote:

> To be considered when you get round to think about "building XOM for 
> speed":
>
> Here is a patch reducing ParentNode.indexOf(Node child) from linear to 
> constant time.
> Among other things, this can be used to speed up XPath operations such 
> as sibling related axis navigations, document order checking and 
> sorting (when using an effective compareOrder(A,B) algorithm that 
> simulataneously walks towards the root from both nodes A and B to be 
> compared for document order).
>
> Memory consumption is increased by adding a "parentPosition" integer 
> to each Node.
> (In practise it would be sufficient to have the integer variable only 
> stored in Element nodes, but for simplicity i'm omitting this 
> variation).
>
> The way it works is by updating the variable on insertion and reading 
> it on indexOf. (There's actually no need to update it on removal 
> because indexOf checks whether the child to be found has the right 
> parent.)
>
> Node.java:
>
>     private ParentNode parent = null;
>     int parentPosition = -1; // WH
>
> ParentNode.java:
>
>     final void fastInsertChild(Node child, int position) {
>         if (children == null) children = new ArrayList(1);
>         if (position == children.size())
>                    children.add(child);
>         else
>                    children.add(position, child);
> //        children.add(position, child);
>         child.setParent(this);
>         child.parentPosition = position; // WH
>     }
>
>     public int indexOf(Node child) {
>
>         if (children == null) return -1;
>         if (child.getParent() != this) return -1;
>         // if (child.isNamespace()) return -1; // ??? Not sure
>         return child.parentPosition; // WH
> //        return children.indexOf(child);
>     }
>
> Saxon/Nux have equivalent sibling position functionality in the 
> NodeWrapper class but if such functionality would be available 
> directly from the underlying XOM tree it would be even better.
>
> [I have some more patches for XOMHandler and NonVerifyingXOMHandler 
> that simultaneously improve memory consumption and performance when 
> used in conjuntion with the stringified Text patch, but that's a story 
> for later.]
>
>
> -----------------------------------------------------------------------
> Wolfgang Hoschek                  |   email: whoschek AT lbl.gov
> Distributed Systems Department    |   phone: (415)-533-7610
> Berkeley Laboratory               |   http://dsd.lbl.gov/~hoschek/
> -----------------------------------------------------------------------
>
> _______________________________________________
> XOM-interest mailing list
> XOM-interest AT lists.ibiblio.org
> http://lists.ibiblio.org/mailman/listinfo/xom-interest