[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