1 //------------------------------------------------------------------------------ 2 // <copyright file="SortQuery.cs" company="Microsoft"> 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // </copyright> 5 // <owner current="true" primary="true">Microsoft</owner> 6 //------------------------------------------------------------------------------ 7 8 namespace MS.Internal.Xml.XPath { 9 using System; 10 using System.Xml; 11 using System.Xml.XPath; 12 using System.Xml.Xsl; 13 using System.Diagnostics; 14 using System.Collections; 15 using System.Collections.Generic; 16 17 internal sealed class SortQuery : Query { 18 private List<SortKey> results; 19 private XPathSortComparer comparer; 20 private Query qyInput; 21 SortQuery(Query qyInput)22 public SortQuery(Query qyInput) { 23 Debug.Assert(qyInput != null, "Sort Query needs an input query tree to work on"); 24 this.results = new List<SortKey>(); 25 this.comparer = new XPathSortComparer(); 26 this.qyInput = qyInput; 27 count = 0; 28 } SortQuery(SortQuery other)29 private SortQuery(SortQuery other) : base(other) { 30 this.results = new List<SortKey>(other.results); 31 this.comparer = other.comparer.Clone(); 32 this.qyInput = Clone(other.qyInput); 33 count = 0; 34 } 35 Reset()36 public override void Reset() { count = 0; } 37 SetXsltContext(XsltContext xsltContext)38 public override void SetXsltContext(XsltContext xsltContext) { 39 qyInput.SetXsltContext(xsltContext); 40 if ( 41 qyInput.StaticType != XPathResultType.NodeSet && 42 qyInput.StaticType != XPathResultType.Any 43 ) { 44 throw XPathException.Create(Res.Xp_NodeSetExpected); 45 } 46 } 47 BuildResultsList()48 private void BuildResultsList() { 49 Int32 numSorts = this.comparer.NumSorts; 50 51 Debug.Assert(numSorts > 0, "Why was the sort query created?"); 52 53 XPathNavigator eNext; 54 while ((eNext = qyInput.Advance()) != null) { 55 SortKey key = new SortKey(numSorts, /*originalPosition:*/this.results.Count, eNext.Clone()); 56 57 for (Int32 j = 0; j < numSorts; j++) { 58 key[j] = this.comparer.Expression(j).Evaluate(qyInput); 59 } 60 61 results.Add(key); 62 } 63 results.Sort(this.comparer); 64 } 65 Evaluate(XPathNodeIterator context)66 public override object Evaluate(XPathNodeIterator context) { 67 qyInput.Evaluate(context); 68 this.results.Clear(); 69 BuildResultsList(); 70 count = 0; 71 return this; 72 } 73 Advance()74 public override XPathNavigator Advance() { 75 Debug.Assert(0 <= count && count <= results.Count); 76 if (count < this.results.Count) { 77 return this.results[count++].Node; 78 } 79 return null; 80 } 81 82 public override XPathNavigator Current { 83 get { 84 Debug.Assert(0 <= count && count <= results.Count); 85 if (count == 0) { 86 return null; 87 } 88 return results[count - 1].Node; 89 } 90 } 91 AddSort(Query evalQuery, IComparer comparer)92 internal void AddSort(Query evalQuery, IComparer comparer) { 93 this.comparer.AddSort(evalQuery, comparer); 94 } 95 Clone()96 public override XPathNodeIterator Clone() { return new SortQuery(this); } 97 98 public override XPathResultType StaticType { get { return XPathResultType.NodeSet; } } 99 public override int CurrentPosition { get { return count; } } 100 public override int Count { get { return results.Count; } } 101 public override QueryProps Properties { get { return QueryProps.Cached | QueryProps.Position | QueryProps.Count; } } 102 PrintQuery(XmlWriter w)103 public override void PrintQuery(XmlWriter w) { 104 w.WriteStartElement(this.GetType().Name); 105 qyInput.PrintQuery(w); 106 w.WriteElementString("XPathSortComparer", "... PrintTree() not implemented ..."); 107 w.WriteEndElement(); 108 } 109 } // class SortQuery 110 111 internal sealed class SortKey { 112 private Int32 numKeys; 113 private object[] keys; 114 private int originalPosition; 115 private XPathNavigator node; 116 SortKey(int numKeys, int originalPosition, XPathNavigator node)117 public SortKey(int numKeys, int originalPosition, XPathNavigator node) { 118 this.numKeys = numKeys; 119 this.keys = new object[numKeys]; 120 this.originalPosition = originalPosition; 121 this.node = node; 122 } 123 124 public object this[int index] { 125 get { return this.keys[index]; } 126 set { this.keys[index] = value; } 127 } 128 129 public int NumKeys { get { return this.numKeys; } } 130 public int OriginalPosition { get { return this.originalPosition; } } 131 public XPathNavigator Node { get { return this.node; } } 132 } // class SortKey 133 134 internal sealed class XPathSortComparer : IComparer<SortKey> { 135 private const int minSize = 3; 136 private Query[] expressions; 137 private IComparer[] comparers; 138 private int numSorts; 139 XPathSortComparer(int size)140 public XPathSortComparer(int size) { 141 if (size <= 0) size = minSize; 142 this.expressions = new Query[ size]; 143 this.comparers = new IComparer[size]; 144 } XPathSortComparer()145 public XPathSortComparer() : this (minSize) {} 146 AddSort(Query evalQuery, IComparer comparer)147 public void AddSort(Query evalQuery, IComparer comparer) { 148 Debug.Assert(this.expressions.Length == this.comparers.Length); 149 Debug.Assert(0 < this.expressions.Length); 150 Debug.Assert(0 <= numSorts && numSorts <= this.expressions.Length); 151 // Ajust array sizes if needed. 152 if (numSorts == this.expressions.Length) { 153 Query[] newExpressions = new Query[ numSorts * 2]; 154 IComparer[] newComparers = new IComparer[numSorts * 2]; 155 for (int i = 0; i < numSorts; i ++) { 156 newExpressions[i] = this.expressions[i]; 157 newComparers [i] = this.comparers[i]; 158 } 159 this.expressions = newExpressions; 160 this.comparers = newComparers; 161 } 162 Debug.Assert(numSorts < this.expressions.Length); 163 164 // Fixup expression to handle node-set return type: 165 if (evalQuery.StaticType == XPathResultType.NodeSet || evalQuery.StaticType == XPathResultType.Any) { 166 evalQuery = new StringFunctions(Function.FunctionType.FuncString, new Query[] { evalQuery }); 167 } 168 169 this.expressions[numSorts] = evalQuery; 170 this.comparers[ numSorts] = comparer; 171 numSorts ++; 172 } 173 174 public int NumSorts { get { return numSorts; } } 175 Expression(int i)176 public Query Expression(int i) { 177 return this.expressions[i]; 178 } 179 Compare(SortKey x, SortKey y)180 int IComparer<SortKey>.Compare(SortKey x, SortKey y) { 181 Debug.Assert(x != null && y != null, "Oops!! what happened?"); 182 int result = 0; 183 for (int i = 0; i < x.NumKeys; i++) { 184 result = this.comparers[i].Compare(x[i], y[i]); 185 if (result != 0) { 186 return result; 187 } 188 } 189 190 // if after all comparisions, the two sort keys are still equal, preserve the doc order 191 return x.OriginalPosition - y.OriginalPosition; 192 } 193 Clone()194 internal XPathSortComparer Clone() { 195 XPathSortComparer clone = new XPathSortComparer(this.numSorts); 196 197 for (int i = 0; i < this.numSorts; i ++) { 198 clone.comparers[i] = this.comparers[i]; 199 clone.expressions[i] = (Query)this.expressions[i].Clone(); // Expressions should be cloned because Query should be cloned 200 } 201 clone.numSorts = this.numSorts; 202 return clone; 203 } 204 } // class XPathSortComparer 205 } // namespace 206