mcs/class/referencesource/System.Data.SqlXml/System/Xml/Xsl/Runtime/XmlSortKey.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="XmlSortKey.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 // <owner current="true" primary="true">Microsoft</owner>
   6 //------------------------------------------------------------------------------
   7 using System;
   8 using System.Diagnostics;
   9 using System.Globalization;
  10
  11 namespace System.Xml.Xsl.Runtime {
  12
  13     /// <summary>
  14     /// Base internal class for all sort keys.
  15     /// Inherits from IComparable, so that Array.Sort can perform comparison.
  16     /// </summary>
  17     internal abstract class XmlSortKey : IComparable {
  18         private int priority;           // Original input ordering used to ensure that sort is stable
  19         private XmlSortKey nextKey;     // Next sort key if there are multiple keys (null otherwise)
  20
  21         /// <summary>
  22         /// Get or set this key's index, relative to other keys involved in a sort.  This priority will
  23         /// break ties.  If the priority is not set, then the sort will not be stable.
  24         /// </summary>
  25         public int Priority {
  26             //get { return this.priority; }
  27             set {
  28                 // All linked keys have same priority
  29                 XmlSortKey key = this;
  30
  31                 while (key != null) {
  32                     key.priority = value;
  33                     key = key.nextKey;
  34                 }
  35             }
  36         }
  37
  38         /// <summary>
  39         /// Sometimes a key is composed of multiple parts.  For example: (LastName, FirstName).  Multi-part
  40         /// keys are linked together in a list.  This method recursively adds a new key part to the end of the list.
  41         /// Returns the first (primary) key in the list.
  42         /// </summary>
  43         public XmlSortKey AddSortKey(XmlSortKey sortKey) {
  44             if (this.nextKey != null) {
  45                 // Add to end of list--this is not it
  46                 this.nextKey.AddSortKey(sortKey);
  47             }
  48             else {
  49                 // This is the end of the list
  50                 this.nextKey = sortKey;
  51             }
  52
  53             return this;
  54         }
  55
  56         /// <summary>
  57         /// When two keys are compared and found to be equal, the tie must be broken.  If there is a secondary key,
  58         /// then use that to break the tie.  Otherwise, use the input ordering to break the tie.  Since every key
  59         /// has a unique index, this is guaranteed to always break the tie.
  60         /// </summary>
  61         protected int BreakSortingTie(XmlSortKey that) {
  62             if (this.nextKey != null) {
  63                 // There are multiple keys, so break tie using next key
  64                 Debug.Assert(this.nextKey != null && that.nextKey != null);
  65                 return this.nextKey.CompareTo(that.nextKey);
  66             }
  67
  68             Debug.Assert(this.priority != that.priority);
  69             return (this.priority < that.priority) ? -1 : 1;
  70         }
  71
  72         /// <summary>
  73         /// Compare a non-empty key (this) to an empty key (obj).  The empty sequence always sorts either before all
  74         /// other values, or after all other values.
  75         /// </summary>
  76         protected int CompareToEmpty(object obj) {
  77             XmlEmptySortKey that = obj as XmlEmptySortKey;
  78             Debug.Assert(that != null && !(this is XmlEmptySortKey));
  79             return that.IsEmptyGreatest ? -1 : 1;
  80         }
  81
  82         /// <summary>
  83         /// Base internal class is abstract and doesn't actually implement CompareTo; derived classes must do this.
  84         /// </summary>
  85         public abstract int CompareTo(object that);
  86     }
  87
  88
  89     /// <summary>
  90     /// Sort key for the empty sequence.  Empty sequence always compares sorts either before all other values,
  91     /// or after all other values.
  92     /// </summary>
  93     internal class XmlEmptySortKey : XmlSortKey {
  94         private bool isEmptyGreatest;
  95
  96         public XmlEmptySortKey(XmlCollation collation) {
  97             // Greatest, Ascending: isEmptyGreatest = true
  98             // Greatest, Descending: isEmptyGreatest = false
  99             // Least, Ascending: isEmptyGreatest = false
 100             // Least, Descending: isEmptyGreatest = true
 101             this.isEmptyGreatest = collation.EmptyGreatest != collation.DescendingOrder;
 102         }
 103
 104         public bool IsEmptyGreatest {
 105             get { return this.isEmptyGreatest; }
 106         }
 107
 108         public override int CompareTo(object obj) {
 109             XmlEmptySortKey that = obj as XmlEmptySortKey;
 110
 111             if (that == null) {
 112                 // Empty compared to non-empty
 113                 Debug.Assert(obj is XmlSortKey);
 114                 return -(obj as XmlSortKey).CompareTo(this);
 115             }
 116
 117             // Empty compared to empty
 118             return BreakSortingTie(that);
 119         }
 120     }
 121
 122
 123     /// <summary>
 124     /// Sort key for xs:decimal values.
 125     /// </summary>
 126     internal class XmlDecimalSortKey : XmlSortKey {
 127         private decimal decVal;
 128
 129         public XmlDecimalSortKey(decimal value, XmlCollation collation) {
 130             // Invert decimal if sorting in descending order
 131             this.decVal = collation.DescendingOrder ? -value : value;
 132         }
 133
 134         public override int CompareTo(object obj) {
 135             XmlDecimalSortKey that = obj as XmlDecimalSortKey;
 136             int cmp;
 137
 138             if (that == null)
 139                 return CompareToEmpty(obj);
 140
 141             cmp = Decimal.Compare(this.decVal, that.decVal);
 142             if (cmp == 0)
 143                 return BreakSortingTie(that);
 144
 145             return cmp;
 146         }
 147     }
 148
 149
 150     /// <summary>
 151     /// Sort key for xs:integer values.
 152     /// </summary>
 153     internal class XmlIntegerSortKey : XmlSortKey {
 154         private long longVal;
 155
 156         public XmlIntegerSortKey(long value, XmlCollation collation) {
 157             // Invert long if sorting in descending order
 158             this.longVal = collation.DescendingOrder ? ~value : value;
 159         }
 160
 161         public override int CompareTo(object obj) {
 162             XmlIntegerSortKey that = obj as XmlIntegerSortKey;
 163
 164             if (that == null)
 165                 return CompareToEmpty(obj);
 166
 167             if (this.longVal == that.longVal)
 168                 return BreakSortingTie(that);
 169
 170             return (this.longVal < that.longVal) ? -1 : 1;
 171         }
 172     }
 173
 174
 175     /// <summary>
 176     /// Sort key for xs:int values.
 177     /// </summary>
 178     internal class XmlIntSortKey : XmlSortKey {
 179         private int intVal;
 180
 181         public XmlIntSortKey(int value, XmlCollation collation) {
 182             // Invert integer if sorting in descending order
 183             this.intVal = collation.DescendingOrder ? ~value : value;
 184         }
 185
 186         public override int CompareTo(object obj) {
 187             XmlIntSortKey that = obj as XmlIntSortKey;
 188
 189             if (that == null)
 190                 return CompareToEmpty(obj);
 191
 192             if (this.intVal == that.intVal)
 193                 return BreakSortingTie(that);
 194
 195             return (this.intVal < that.intVal) ? -1 : 1;
 196         }
 197     }
 198
 199
 200     /// <summary>
 201     /// Sort key for xs:string values.  Strings are sorted according to a byte-wise sort key calculated by caller.
 202     /// </summary>
 203     internal class XmlStringSortKey : XmlSortKey {
 204         private SortKey sortKey;
 205         private byte[] sortKeyBytes;
 206         private bool descendingOrder;
 207
 208         public XmlStringSortKey(SortKey sortKey, bool descendingOrder) {
 209             this.sortKey = sortKey;
 210             this.descendingOrder = descendingOrder;
 211         }
 212
 213         public XmlStringSortKey(byte[] sortKey, bool descendingOrder) {
 214             this.sortKeyBytes = sortKey;
 215             this.descendingOrder = descendingOrder;
 216         }
 217
 218         public override int CompareTo(object obj) {
 219             XmlStringSortKey that = obj as XmlStringSortKey;
 220             int idx, cntCmp, result;
 221
 222             if (that == null)
 223                 return CompareToEmpty(obj);
 224
 225             // Compare either using SortKey.Compare or byte arrays
 226             if (this.sortKey != null) {
 227                 Debug.Assert(that.sortKey != null, "Both keys must have non-null sortKey field");
 228                 result = SortKey.Compare(this.sortKey, that.sortKey);
 229             }
 230             else {
 231                 Debug.Assert(this.sortKeyBytes != null && that.sortKeyBytes != null, "Both keys must have non-null sortKeyBytes field");
 232
 233                 cntCmp = (this.sortKeyBytes.Length < that.sortKeyBytes.Length) ? this.sortKeyBytes.Length : that.sortKeyBytes.Length;
 234                 for (idx = 0; idx < cntCmp; idx++) {
 235                     if (this.sortKeyBytes[idx] < that.sortKeyBytes[idx]) {
 236                         result = -1;
 237                         goto Done;
 238                     }
 239
 240                     if (this.sortKeyBytes[idx] > that.sortKeyBytes[idx]) {
 241                         result = 1;
 242                         goto Done;
 243                     }
 244                 }
 245
 246                 // So far, keys are equal, so now test length of each key
 247                 if (this.sortKeyBytes.Length < that.sortKeyBytes.Length)
 248                     result = -1;
 249                 else if (this.sortKeyBytes.Length > that.sortKeyBytes.Length)
 250                     result = 1;
 251                 else
 252                     result = 0;
 253             }
 254
 255         Done:
 256             // Use document order to break sorting tie
 257             if (result == 0)
 258                 return BreakSortingTie(that);
 259
 260             return this.descendingOrder ? -result : result;
 261         }
 262     }
 263
 264
 265     /// <summary>
 266     /// Sort key for Double values.
 267     /// </summary>
 268     internal class XmlDoubleSortKey : XmlSortKey {
 269         private double dblVal;
 270         private bool isNaN;
 271
 272         public XmlDoubleSortKey(double value, XmlCollation collation) {
 273             if (Double.IsNaN(value)) {
 274                 // Treat NaN as if it were the empty sequence
 275                 this.isNaN = true;
 276
 277                 // Greatest, Ascending: isEmptyGreatest = true
 278                 // Greatest, Descending: isEmptyGreatest = false
 279                 // Least, Ascending: isEmptyGreatest = false
 280                 // Least, Descending: isEmptyGreatest = true
 281                 this.dblVal = (collation.EmptyGreatest != collation.DescendingOrder) ? Double.PositiveInfinity : Double.NegativeInfinity;
 282             }
 283             else {
 284                 this.dblVal = collation.DescendingOrder ? -value : value;
 285             }
 286         }
 287
 288         public override int CompareTo(object obj) {
 289             XmlDoubleSortKey that = obj as XmlDoubleSortKey;
 290
 291             if (that == null) {
 292                 // Compare to empty sequence
 293                 if (this.isNaN)
 294                     return BreakSortingTie(obj as XmlSortKey);
 295
 296                 return CompareToEmpty(obj);
 297             }
 298
 299             if (this.dblVal == that.dblVal) {
 300                 if (this.isNaN) {
 301                     // NaN sorts equal to NaN
 302                     if (that.isNaN)
 303                         return BreakSortingTie(that);
 304
 305                     // NaN sorts before or after all non-NaN values
 306                     Debug.Assert(this.dblVal == Double.NegativeInfinity || this.dblVal == Double.PositiveInfinity);
 307                     return (this.dblVal == Double.NegativeInfinity) ? -1 : 1;
 308                 }
 309                 else if (that.isNaN) {
 310                     // NaN sorts before or after all non-NaN values
 311                     Debug.Assert(that.dblVal == Double.NegativeInfinity || that.dblVal == Double.PositiveInfinity);
 312                     return (that.dblVal == Double.NegativeInfinity) ? 1 : -1;
 313                 }
 314
 315                 return BreakSortingTie(that);
 316             }
 317
 318             return (this.dblVal < that.dblVal) ? -1 : 1;
 319         }
 320     }
 321
 322
 323     /// <summary>
 324     /// Sort key for DateTime values (just convert DateTime to ticks and use Long sort key).
 325     /// </summary>
 326     internal class XmlDateTimeSortKey : XmlIntegerSortKey {
 327         public XmlDateTimeSortKey(DateTime value, XmlCollation collation) : base(value.Ticks, collation) {
 328         }
 329     }
 330 }