mcs/class/referencesource/System.Xml/System/Xml/XPath/Internal/SortQuery.cs

   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
  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         }
  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
  36         public override void Reset() { count = 0; }
  37
  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
  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
  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
  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
  92         internal void AddSort(Query evalQuery, IComparer comparer) {
  93             this.comparer.AddSort(evalQuery, comparer);
  94         }
  95
  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
 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
 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
 140         public XPathSortComparer(int size) {
 141             if (size <= 0) size = minSize;
 142             this.expressions   = new Query[   size];
 143             this.comparers     = new IComparer[size];
 144         }
 145         public XPathSortComparer() : this (minSize) {}
 146
 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
 176         public Query Expression(int i) {
 177             return this.expressions[i];
 178         }
 179
 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
 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