The Labs \ Source Viewer \ SSCLI \ System.Xml.Xsl.Runtime \ XmlSortKey

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

Developer Fusion