[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

RE: Document order calculation

• To: "'Elliotte Harold'" <elharo@m...>, "'XML Developers List'" <xml-dev@l...>
• Subject: RE: Document order calculation
• From: "Michael Kay" <mike@s...>
• Date: Sun, 27 Feb 2005 23:39:38 -0000
• In-reply-to: <4222323E.7000801@m...>
• Thread-index: AcUdDfyfWxLVJ44PT4mJsFY3nHxIEQAFj56A

Where Saxon does this on external models such as DOM, JDOM, or XOM, the
algorithm is:

calculate the depth of each node

find the ancestor of the deeper node whose depth is the same as that of the
shallower node

if this is the same node, we're done (the deeper node comes later)

if the two nodes have the same parent, compare their sibling position

otherwise find the parent of each of the two nodes and recurse

Comparing sibling position depends on the implementation. Some trees give
you the sibling position directly. If you have to walk siblings to count how
many there are, then you can look for the other node while you do so,
assuming that testing two nodes for identity is cheap. You have to make a
guess which node to start from and whether to walk backwards or forwards -
it will only make a difference if there is a non-random pattern to the
comparisons being done (it's quite possible that the first node in the pair
being compared is much more likely to be the first in document order, for
example).

There are complications, of course, for attribute and namespace nodes.

Michael Kay
http://www.saxonica.com/

> -----Original Message-----
> From: Elliotte Harold [mailto:elharo@m...] 
> Sent: 27 February 2005 20:49
> To: XML Developers List
> Subject:  Document order calculation
> 
> I'm wondering if anyone knows an efficient algorithm for 
> comparing two 
> nodes for document order? I'm looking for something better 
> than simply 
> walking the tree from beginning to end and seeing which node appears 
> first. Assumptions are:
> 
> 1. XPath 1.0 data model or rough equivalent
> 
> 2. Usual navigation operations like getParent(), getChild(), 
> etc. such 
> as might be found in XSLT 1, DOM Level 2, JDOM, XOM, etc. 
> (i.e. I don't 
> want to rely on the extensions to do exactly this in XPath 2/XSLT 
> 2/XQuery and in DOM Level 3)
> 
> -- 
> Elliotte Rusty Harold  elharo@m...
> XML in a Nutshell 3rd Edition Just Published!
> http://www.cafeconleche.org/books/xian3/
> http://www.amazon.com/exec/obidos/ISBN=0596007647/cafeaulaitA/
> ref=nosim
> 
> 
> -----------------------------------------------------------------
> The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> initiative of OASIS <http://www.oasis-open.org>
> 
> The list archives are at http://lists.xml.org/archives/xml-dev/
> 
> To subscribe or unsubscribe from this list use the subscription
> manager: <http://www.oasis-open.org/mlmanage/index.php>
> 
> 

• References:
  • Document order calculation
    • From: Elliotte Harold <elharo@m...>

• Prev by Date: Re: Document order calculation
• Next by Date: Re: Quiz: XML flexibility
• Previous by thread: Re: Document order calculation
• Index(es):
  • Date
  • Thread