[Mono-devel-list] Sorting in XPath

Ben Maurer bmaurer at users.sourceforge.net
Mon Jun 23 20:14:59 EDT 2003


Hello all,

I have implemented sorting in XPath. I am attaching the patch that adds
support for the AddSort (...) methods. It also contains NUnit tests.

I would appreciate a review for this patch.

-- Ben 
-------------- next part --------------
? Test/System.Xml.XPath/tmp
Index: System.Xml.XPath/ChangeLog
===================================================================
RCS file: /cvs/public/mcs/class/System.XML/System.Xml.XPath/ChangeLog,v
retrieving revision 1.34
diff -u -r1.34 ChangeLog
--- System.Xml.XPath/ChangeLog	28 Apr 2003 21:00:33 -0000	1.34
+++ System.Xml.XPath/ChangeLog	24 Jun 2003 00:23:17 -0000
@@ -1,3 +1,7 @@
+2003-06-23  Ben Maurer <bmaurer at users.sourceforge.net>
+	
+	* Expression.cs: Added support for sorts.
+
 2003-04-28  Piers Haken  <piersh at friskit.com>
 
 	* Parser.jay, Tokenizer.cs: more compliant lexical parsing of ambiguous tokens
Index: System.Xml.XPath/Expression.cs
===================================================================
RCS file: /cvs/public/mcs/class/System.XML/System.Xml.XPath/Expression.cs,v
retrieving revision 1.10
diff -u -r1.10 Expression.cs
--- System.Xml.XPath/Expression.cs	7 Apr 2003 10:55:13 -0000	1.10
+++ System.Xml.XPath/Expression.cs	24 Jun 2003 00:23:17 -0000
@@ -9,9 +9,11 @@
 using System;
 using System.IO;
 using System.Collections;
+using System.Globalization;
 using System.Xml;
 using System.Xml.XPath;
 using System.Xml.Xsl;
+using Mono.Xml.XPath;
 
 namespace System.Xml.XPath
 {
@@ -46,17 +48,40 @@
 		internal XmlNamespaceManager NamespaceManager { get { return _nsm; } }
 		public override String Expression { get { return _expr.ToString (); }}
 		public override XPathResultType ReturnType { get { return _expr.ReturnType; }}
-		[MonoTODO]
-		public override void AddSort (Object obj, IComparer cmp)
+		
+		public override void AddSort (object query, IComparer cmp)
 		{
-			throw new NotImplementedException ();
+			Expression e = ExpFromObj (query);
+			if (!(this._expr is ExprSort))
+				this._expr = new ExprSort (this._expr);
+			
+			((ExprSort)this._expr).AddSort (e, cmp);
+		
 		}
-		[MonoTODO]
-		public override void AddSort(object obj, XmlSortOrder sortOrder, XmlCaseOrder caseOrder, string str, XmlDataType type)
+		
+		public override void AddSort(object query, XmlSortOrder sortOrder, XmlCaseOrder caseOrder, string lang, XmlDataType type)
 		{
-			throw new NotImplementedException ();
+			Expression e = ExpFromObj (query);
+			if (!(this._expr is ExprSort))
+				this._expr = new ExprSort (this._expr);
+			
+			((ExprSort)this._expr).AddSort (e, sortOrder, caseOrder, lang, type);
 		}
+		
+		static Expression ExpFromObj (object query)
+		{
+			if (query is CompiledExpression) return ((CompiledExpression)query)._expr;
+			if (query is String) return Compile ((string)query);
 
+			throw new XPathException ("Invalid query object");
+		}
+		static Expression Compile (string xpath)
+		{
+			Tokenizer tokenizer = new Tokenizer (xpath);
+			XPathParser parser = new XPathParser ();
+			return (Expression)parser.yyparseSafe (tokenizer);
+		}
+		
 		public object Evaluate (BaseIterator iter)
 		{
 			try
@@ -1054,6 +1079,212 @@
 				}
 			}
 			return func.Invoke (context, rgArgs, iter.Current);
+		}
+	}
+	
+	internal class ExprSort : NodeSet
+	{
+		Expression exp;
+		
+		ArrayList sortExpressions;
+		ArrayList comparers;
+			
+		public ExprSort (Expression exp) {
+			this.exp = exp;
+			sortExpressions = new ArrayList ();
+			comparers = new ArrayList ();
+		}
+			
+		public void AddSort (Expression query, IComparer cmp)
+		{
+			if (query.ReturnType == XPathResultType.NodeSet)
+				query = new ExprFunctionCall ("string", new FunctionArguments (query, null));
+				
+			sortExpressions.Add (query);
+			comparers.Add (cmp);
+		}
+		
+		public void AddSort (Expression query, XmlSortOrder sortOrder, XmlCaseOrder caseOrder, string lang, XmlDataType type)
+		{
+			CultureInfo cinfo;
+			
+			if (lang == null || lang == String.Empty)
+				cinfo = System.Threading.Thread.CurrentThread.CurrentCulture;
+			else
+				cinfo = new CultureInfo(lang);
+			
+			AddSort (query, new XPathComparer (sortOrder, caseOrder, cinfo, type));
+		}
+			
+		public override String ToString () { return "sort " + exp.ToString ();}
+		public override object Evaluate (BaseIterator iter)
+		{
+			BaseIterator baseItr = exp.EvaluateNodeSet (iter);
+			int numSorts = sortExpressions.Count;
+			SortedList results = new SortedList (new MultiSortComparer (comparers));
+			
+			while (baseItr.MoveNext ()) {
+
+				MultiSortKey key = new MultiSortKey (numSorts);
+
+				for (int i = 0; i < numSorts; i++) {
+					Expression e = (Expression)sortExpressions [i];
+					key.Parts [i] = e.Evaluate (baseItr);
+				}
+				
+				results.Add (key, baseItr.Current.Clone ());
+			}
+			
+			return new SortIterator (iter, results);
+		}
+		
+		
+		class SortIterator : BaseIterator
+		{
+			SortedList nodes;
+			int pos = -1;
+	
+			public SortIterator (BaseIterator iter, SortedList nodes) : base (iter)
+			{
+				this.nodes = nodes;
+			}
+	
+			private SortIterator (SortIterator other) : base (other)
+			{
+				this.nodes = (SortedList) other.nodes.Clone ();
+				pos = other.pos;
+			}
+			public override XPathNodeIterator Clone () { return new SortIterator (this); }
+	
+			public override bool MoveNext ()
+			{
+				return ++pos < nodes.Count;
+			}
+			public override XPathNavigator Current
+			{
+				get {
+					return (XPathNavigator) nodes.GetByIndex (pos);
+				}
+			}
+			
+			public override int CurrentPosition { get { return pos; }}
+		}
+		
+		class XPathComparer : IComparer {
+			
+			private XmlSortOrder sortOrder;
+			private XmlCaseOrder caseOrder;
+			private CultureInfo cinfo;
+			private XmlDataType dataType;
+	
+			internal XPathComparer (XmlSortOrder sortOrder, XmlCaseOrder caseOrder, CultureInfo cinfo, XmlDataType dataType)
+			{
+				this.sortOrder = sortOrder;
+				this.caseOrder = caseOrder;
+				this.cinfo = cinfo;
+				// Is this right?
+				if (dataType != XmlDataType.Text && dataType != XmlDataType.Number)
+					throw new ArgumentException ("dataType");
+				this.dataType = dataType;
+			}
+			
+			public int Compare (object x, object y)
+			{
+				int sortMul = (sortOrder == XmlSortOrder.Ascending) ? -1 : 1;
+				switch (dataType) {
+					case XmlDataType.Text:
+						string strX = x.ToString ();
+						string strY = y.ToString ();
+						int result = String.Compare (strX, strY, true, cinfo);
+						if (result != 0 || caseOrder == XmlCaseOrder.None)
+							return (sortMul * result);
+	
+						// so, they are equal in case
+						int caseMul = (caseOrder == XmlCaseOrder.LowerFirst) ? 1 : -1;
+						return sortMul * caseMul * String.Compare (strX, strY, false, cinfo);
+	
+					case XmlDataType.Number:
+						double dblX = ToDouble (x);
+						double dblY = ToDouble (y);
+	
+						// Easy
+						if (dblX >  dblY) return  sortMul;
+						if (dblY <  dblX) return -sortMul;
+						if (dblX == dblY) return 0;
+						
+						
+						if (Double.IsNaN (dblX)) {
+							if (Double.IsNaN (dblY)) {
+								return 0;
+							}
+							// NaN > anything
+							return -sortMul;
+						}
+						// NaN > anything
+						return sortMul;
+				}
+				throw new Exception ();
+				
+			}
+			static double ToDouble (object o)
+			{
+				switch (Type.GetTypeCode(o.GetType ())) {
+				case TypeCode.String :
+					try {
+						string str = ((string)o).Trim ();
+						return Double.Parse(str, NumberStyles.AllowLeadingSign|NumberStyles.AllowDecimalPoint, NumberFormatInfo.InvariantInfo);
+					} catch {}
+					return Double.NaN;
+				case TypeCode.Double :
+					return (double)o;
+				case TypeCode.Boolean :
+					return (bool)o ? 1.0 : 0.0;
+				default :
+						return Convert.ToDouble (o, NumberFormatInfo.InvariantInfo); 
+				}
+			}
+
+		}
+		
+		class MultiSortComparer : IComparer {
+			ArrayList cmpArray;
+	
+			internal MultiSortComparer (ArrayList cmpArray)
+			{
+				this.cmpArray = cmpArray;
+			}
+	
+			int IComparer.Compare (object x, object y)
+			{			
+				return Compare ((MultiSortKey)x, (MultiSortKey)y);
+			}
+	
+			public int Compare (MultiSortKey x, MultiSortKey y)
+			{
+				int i = 0;
+				
+				foreach (IComparer cmp in cmpArray) {
+					
+					int result = cmp.Compare (x.Parts [i], y.Parts [i]);
+					if (result != 0) return result;
+					i++;
+				}
+	
+				// Preserve document order
+				return 1;
+			}
+		}
+		
+		class MultiSortKey {
+			
+			object [] parts;
+	
+			public MultiSortKey (int n)
+			{
+				parts = new object [n];
+			}
+		
+			public object [] Parts { get { return parts; } }
 		}
 	}
 }
Index: Test/System.Xml.XPath/ChangeLog
===================================================================
RCS file: /cvs/public/mcs/class/System.XML/Test/System.Xml.XPath/ChangeLog,v
retrieving revision 1.4
diff -u -r1.4 ChangeLog
--- Test/System.Xml.XPath/ChangeLog	1 Jun 2003 05:58:05 -0000	1.4
+++ Test/System.Xml.XPath/ChangeLog	24 Jun 2003 00:23:17 -0000
@@ -1,3 +1,7 @@
+2003-06-23  Ben Maurer <bmaurer at users.sourceforge.net>
+
+	* XPathNavigatorTests.cs: Added tests for sorting.
+
 2003-06-01  Atsushi Enomoto <ginga at kit.hi-ho.ne.jp>
 
 	* XPathNavigatorTests.cs : added DocumentWithProcessingInstruction().
Index: Test/System.Xml.XPath/XPathNavigatorTests.cs
===================================================================
RCS file: /cvs/public/mcs/class/System.XML/Test/System.Xml.XPath/XPathNavigatorTests.cs,v
retrieving revision 1.4
diff -u -r1.4 XPathNavigatorTests.cs
--- Test/System.Xml.XPath/XPathNavigatorTests.cs	1 Jun 2003 05:58:05 -0000	1.4
+++ Test/System.Xml.XPath/XPathNavigatorTests.cs	24 Jun 2003 00:23:17 -0000
@@ -204,5 +204,80 @@
 			XPathNodeIterator iter = navigator.SelectChildren (XPathNodeType.Element);
 			AssertEquals (0, iter.Count);
 		}
+		[Test]
+		public void TestSort ()
+		{
+			// This is from MSDN
+			document.LoadXml (@"
+<?xml version='1.0'?>
+<bookstore xmlns:bk='urn:samples'>
+  <book genre='novel' publicationdate='1997' bk:ISBN='1-861001-57-8' id='1'>
+    <title>Pride And Prejudice</title>
+    <author>
+      <first-name>Jane</first-name>
+      <last-name>Austen</last-name>
+    </author>
+    <price>24.95</price>
+  </book>
+  <book genre='novel' publicationdate='1992' bk:ISBN='1-861002-30-1' id='2'>
+    <title>The Handmaid's Tale</title>
+    <author>
+      <first-name>Margaret</first-name>
+      <last-name>Atwood</last-name>
+    </author>
+    <price>29.95</price>
+  </book>
+  <book genre='novel' publicationdate='1991' bk:ISBN='1-861001-57-6' id='3'>
+    <title>Emma</title>
+    <author>
+      <first-name>jane</first-name>
+      <last-name>Austen</last-name>
+    </author>
+    <price>19.95</price>
+  </book>
+  <book genre='novel' publicationdate='1982' bk:ISBN='1-861001-45-3' id='4'>
+    <title>Sense and Sensibility</title>
+    <author>
+      <first-name>Jane</first-name>
+      <last-name>Austen</last-name>
+    </author>
+    <price>19.95</price>
+  </book>
+</bookstore>
+			");
+			navigator = document.CreateNavigator ();
+			
+			XPathExpression expr; 
+			XPathNodeIterator iterator;
+			
+			expr = navigator.Compile ("descendant::book[author/last-name='Austen']");
+			expr.AddSort ("price", XmlSortOrder.Ascending, XmlCaseOrder.None, "", XmlDataType.Number);
+			AssertItrVals ("a", navigator.Select(expr), 3, 4, 1);
+			
+			expr = navigator.Compile ("descendant::book[author/last-name='Austen']");
+			expr.AddSort ("price", XmlSortOrder.Descending, XmlCaseOrder.None, "", XmlDataType.Number);
+			AssertItrVals ("b", navigator.Select(expr), 1, 3, 4);
+			
+			expr = navigator.Compile ("descendant::book[author/last-name='Austen']");
+			expr.AddSort ("title", XmlSortOrder.Descending, XmlCaseOrder.None, "", XmlDataType.Text);
+			AssertItrVals ("c", navigator.Select(expr), 3, 1, 4);
+			
+			expr = navigator.Compile ("descendant::book[author/last-name='Austen']");
+			expr.AddSort ("title", XmlSortOrder.Ascending, XmlCaseOrder.None, "", XmlDataType.Text);
+			AssertItrVals ("d", navigator.Select(expr), 4, 1, 3);
+			
+						
+			expr = navigator.Compile ("descendant::book[author/last-name='Austen']");
+			expr.AddSort ("author/first-name", XmlSortOrder.Ascending, XmlCaseOrder.LowerFirst, "", XmlDataType.Text);
+			AssertItrVals ("e", navigator.Select(expr), 1, 4, 3);
+		}
+		
+		static void AssertItrVals (string s, XPathNodeIterator itr, params int [] v) {
+			for (int i = 0; i < v.Length; i++) {
+				AssertEquals (s, true, itr.MoveNext ());
+				AssertEquals (s, v [i], int.Parse(itr.Current.GetAttribute ("id", "")));
+			}
+			AssertEquals (s, false, itr.MoveNext ());
+		}
 	}
 }


More information about the Mono-devel-list mailing list