From bf160df1254f650f9d541ee7a8f0ab62e3c8ac16 Mon Sep 17 00:00:00 2001
From: "arseny.kapoulkine"
 <arseny.kapoulkine@99668b35-9821-0410-8761-19e4c4f06640>
Date: Mon, 19 Jan 2009 11:18:34 +0000
Subject: XPath: Fixed document order comparator (wrong attributes comparison
 in case of added ones, buggy LCA determination)

git-svn-id: http://pugixml.googlecode.com/svn/trunk@109 99668b35-9821-0410-8761-19e4c4f06640
---
 src/pugixpath.cpp | 76 +++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 51 insertions(+), 25 deletions(-)

diff --git a/src/pugixpath.cpp b/src/pugixpath.cpp
index 310cac6..857b695 100644
--- a/src/pugixpath.cpp
+++ b/src/pugixpath.cpp
@@ -125,6 +125,45 @@ namespace
 		}
 	}
 	
+	unsigned int node_height(xml_node n)
+	{
+	    unsigned int result = 0;
+	    
+	    while (n)
+	    {
+	        ++result;
+	        n = n.parent();
+	    }
+	    
+	    return result;
+	}
+	
+	// precondition: node_height of ln is <= node_height of rn, ln != rn
+	bool node_is_before(xml_node ln, unsigned int lh, xml_node rn, unsigned int rh)
+	{
+	    assert(lh <= rh);
+	    
+	    while (lh < rh)
+	    {
+	        --rh;
+	        rn = rn.parent();
+	    }
+	    
+	    if (ln == rn) return true;
+	    
+	    while (ln.parent() != rn.parent())
+	    {
+	        ln = ln.parent();
+	        rn = rn.parent();
+	    }
+	    
+        for (; ln; ln = ln.next_sibling())
+            if (ln == rn)
+                return true;
+                
+        return false;
+    }
+    
 	struct document_order_comparator
 	{
 		bool operator()(const xpath_node& lhs, const xpath_node& rhs) const
@@ -139,7 +178,14 @@ namespace
 
 			if (lhs.attribute() && rhs.attribute())
 			{
-				if (lhs.parent() == rhs.parent()) return lhs.attribute() < rhs.attribute();
+				if (lhs.parent() == rhs.parent())
+				{
+				    for (xml_attribute a = lhs.attribute(); a; a = a.next_attribute())
+				        if (a == rhs.attribute())
+				            return true;
+				    
+				    return false;
+				}
 				
 				ln = lhs.parent();
 				rn = rhs.parent();
@@ -158,31 +204,11 @@ namespace
 			}
 
 			if (ln == rn) return false;
-				
-			xml_node lp = ln, rp = rn;
-				
-			while (lp != rp)
-			{
-				ln = lp;
-				lp = lp.parent();
-					
-				if (lp != rp)
-				{
-					rn = rp;
-					rp = rp.parent();
-				}
-			}
-				
-			if (!lp) // no common parent - ???
-				return false;
-			else // lp is parent, ln & rn are distinct siblings
-			{
-				for (; ln; ln = ln.next_sibling())
-					if (ln == rn)
-						return true;
 			
-				return false;
-			}
+			unsigned int lh = node_height(ln);
+			unsigned int rh = node_height(rn);
+			
+			return (lh <= rh) ? node_is_before(ln, lh, rn, rh) : !node_is_before(rn, rh, ln, lh);
 		}
 	};
 
-- 
cgit v1.2.3