OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   RE: [xml-dev] Document order calculation

[ Lists Home | Date Index | Thread Index ]

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

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

Michael Kay

> -----Original Message-----
> From: Elliotte Harold [mailto:elharo@metalab.unc.edu] 
> Sent: 27 February 2005 20:49
> To: XML Developers List
> Subject: [xml-dev] 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@metalab.unc.edu
> 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>


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS