[
Lists Home |
Date Index |
Thread Index
]
One implementation is easy, just as proof of concept, but is not likely to
be optimal. If it's your own flavor of DOM to which XPath processing is
applied, and the DOM can be assumed to be read-only, each node can be
constructed to carry its index in document order, allowing a trivial sort
after nodes were found by the Xpath processor, using the DOM implementation
secret sauce. You could relax the read-only assumption at the cost of a
major renumbering each time the DOM was modified.
I think the following is a germ of another scheme by which each node carries
the number of descendants it has. To compute the document order index of a
node, you do something like this (too little time to nail down the details):
let sum =0
for ancestor = self to root by getParent(ancestor) do
sum = sum + 1 // each ancestor, including self, counts 1
// each preceding sibling contributes itself and all its
descendants
for all preceding siblings of ancestor do
sum = sum + 1 + descendant-node-count(sibling)
This is slower for finding the doc order index of a node, but faster for
recomputing indexes when modifying the DOM. Any change of the DOM tree gets
propagated in an obvious way to the descendant-node-counts of the ancestors
up to the root, but the other nodes don't have to be changed.
Jeff
----- Original Message -----
From: "bob mcwhirter" <bob@werken.com>
To: "Jeni Tennison" <jeni@jenitennison.com>
Cc: <xml-dev@lists.xml.org>
Sent: Wednesday, July 17, 2002 4:21 PM
Subject: Re: [xml-dev] Quick Xpath
>
> Howsabout given:
>
> (//foo | //bar)[4]
>
> Would that be the 4th occurrence of either foo or bar, in document
> order? That's just an implementational nightmare.
|
