File: winforms\Managed\System\WinForms\StringSorter.cs
Project: ndp\fx\src\System.Windows.Forms.csproj (System.Windows.Forms)
//------------------------------------------------------------------------------
// <copyright file="StringSorter.cs" company="Microsoft">
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>                                                                
//------------------------------------------------------------------------------
 
namespace System.Windows.Forms {
    
    using System.Threading;
    using System.ComponentModel;
    using System.Diagnostics;
    using System;
    using System.Globalization;
 
    /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter"]/*' />
    /// <internalonly/>
    /// <devdoc>
    ///    <para>
    ///       This class provides methods to perform locale based comparison of strings
    ///       and sorting of arrays.
    ///    </para>
    /// </devdoc>
    internal sealed class StringSorter
    {
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.IgnoreCase"]/*' />
        /// <devdoc>
        ///     Ignore case when comparing two strings. When this flag is specified in
        ///     calls to compare() and sort(), two strings are considered equal if they
        ///     differ only in casing.
        /// </devdoc>
        public const int IgnoreCase = 0x00000001;
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.IgnoreKanaType"]/*' />
        /// <devdoc>
        ///     Do not differentiate between Hiragana and Katakana characters. When this
        ///     flag is specified in calls to compare() and sort(), corresponding
        ///     Hiragana and Katakana characters compare as equal.
        /// </devdoc>
        public const int IgnoreKanaType = 0x00010000;
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.IgnoreNonSpace"]/*' />
        /// <devdoc>
        ///     Ignore nonspacing marks (accents, diacritics, and vowel marks). When
        ///     this flag is specified in calls to compare() and sort(), strings compare
        ///     as equal if they differ only in how characters are accented.
        /// </devdoc>
        public const int IgnoreNonSpace = 0x00000002;
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.IgnoreSymbols"]/*' />
        /// <devdoc>
        ///     Ignore symbols. When this flag is specified in calls to compare() and
        ///     sort(), strings compare as equal if they differ only in what symbol
        ///     characters they contain.
        /// </devdoc>
        public const int IgnoreSymbols = 0x00000004;
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.IgnoreWidth"]/*' />
        /// <devdoc>
        ///     Ignore character widths. When this flag is specified in calls to
        ///     compare() and sort(), string comparisons do not differentiate between a
        ///     single-ubyte character and the same character as a double-ubyte character.
        /// </devdoc>
        public const int IgnoreWidth = 0x00020000;
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.StringSort"]/*' />
        /// <devdoc>
        ///     Treat punctuation the same as symbols. Typically, strings are compared
        ///     using what is called a "word sort" technique. In a word sort, all
        ///     punctuation marks and other nonalphanumeric characters, except for the
        ///     hyphen and the apostrophe, come before any alphanumeric character. The
        ///     hyphen and the apostrophe are treated differently than the other
        ///     nonalphanumeric symbols, in order to ensure that words such as "coop"
        ///     and "co-op" stay together within a sorted list. If the STRINGSORT flag
        ///     is specified, strings are compared using what is called a "string sort"
        ///     technique. In a string sort, the hyphen and apostrophe are treated just
        ///     like any other nonalphanumeric symbols: they come before the
        ///     alphanumeric symbols.
        /// </devdoc>
        public const int StringSort = 0x00001000;
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Descending"]/*' />
        /// <devdoc>
        ///     Descending sort. When this flag is specified in a call to sort(), the
        ///     strings are sorted in descending order. This flag should not be used in
        ///     calls to compare().
        /// </devdoc>
        public const int Descending = unchecked((int)0x80000000);
 
        private const int CompareOptions = IgnoreCase | IgnoreKanaType |
            IgnoreNonSpace | IgnoreSymbols | IgnoreWidth | StringSort;
 
        private string[] keys;
        private object[] items;
        private int lcid;
        private int options;
        private bool descending;
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.StringSorter"]/*' />
        /// <devdoc>
        ///     Constructs a StringSorter. Instances are created by the sort() routines,
        ///     but never by the user.
        /// </devdoc>
        private StringSorter(CultureInfo culture, string[] keys, object[] items, int options) {
            if (keys == null) {
                if (items is string[]) {
                    keys = (string[])items;
                    items = null;
                }
                else {
                    keys = new string[items.Length];
                    for (int i = 0; i < items.Length; i++) {
                        object item = items[i];
                        if (item != null) keys[i] = item.ToString();
                    }
                }
            }
            this.keys = keys;
            this.items = items;
            this.lcid = culture == null? SafeNativeMethods.GetThreadLocale(): culture.LCID;
            this.options = options & CompareOptions;
            this.descending = (options & Descending) != 0;
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.ArrayLength"]/*' />
        /// <devdoc>
        /// </devdoc>
        /// <internalonly/>
        internal static int ArrayLength(object[] array) {
            if (array == null)
                return 0;
            else
                return array.Length;
        }
        
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Compare"]/*' />
        /// <devdoc>
        ///     Compares two strings using the default locale and no additional string
        ///     comparison flags.
        /// </devdoc>
        public static int Compare(string s1, string s2) {
            return Compare(SafeNativeMethods.GetThreadLocale(), s1, s2, 0);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Compare1"]/*' />
        /// <devdoc>
        ///     Compares two strings using the default locale with the given set of
        ///     string comparison flags.
        /// </devdoc>
        public static int Compare(string s1, string s2, int options) {
            return Compare(SafeNativeMethods.GetThreadLocale(), s1, s2, options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Compare2"]/*' />
        /// <devdoc>
        ///     Compares two strings using a given locale and a given set of comparison
        ///     flags. If the two strings are of different lengths, they are compared up
        ///     to the length of the shortest one. If they are equal to that point, then
        ///     the return value will indicate that the longer string is greater. Notice
        ///     that if the return value is 0, the two strings are "equal" in the
        ///     collation sense, though not necessarily identical.
        ///     A <embedcode term='null'/> string always sorts before a non-null string. Two
        /// <embedcode term='null'/> strings are considered equal.
        ///     The <paramref name='options'/> parameter is a combination of zero or more of
        ///     the following flags: <code>IGNORECASE</code>, <code>IGNOREKANATYPE</code>,
        /// <code>IGNORENONSPACE</code>, <code>IGNORESYMBOLS</code>,
        /// <code>IGNOREWIDTH</code>, and <code>STRINGSORT</code>.
        /// </devdoc>
        public static int Compare(CultureInfo culture, string s1, string s2, int options) {
            return Compare(culture.LCID, s1, s2, options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Compare3"]/*' />
        /// <devdoc>
        /// </devdoc>
        /// <internalonly/>
        private static int Compare(int lcid, string s1, string s2, int options) {
            if (s1 == null) return s2 == null? 0: -1;
            if (s2 == null) return 1;
            return String.Compare(s1, s2, false, CultureInfo.CurrentCulture);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.CompareKeys"]/*' />
        /// <devdoc>
        /// </devdoc>
        /// <internalonly/>
        private int CompareKeys(string s1, string s2) {
            int result = Compare(lcid, s1, s2, options);
            return descending? -result: result;
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.QuickSort"]/*' />
        /// <devdoc>
        ///     Implementation of Quicksort algorithm. Within the outer <code>do</code>
        ///     loop, the method recurses on the shorter side and loops on the longer
        ///     side. This bounds the recursive depth by log2(n) in the worst case.
        ///     Otherwise, worst case recursive depth would be n.
        /// </devdoc>
        /// <internalonly/>
        private void QuickSort(int left, int right) {
            do {
                int i = left;
                int j = right;
                string s = keys[(i + j) >> 1];
                do {
                    while (CompareKeys(keys[i], s) < 0) i++;
                    while (CompareKeys(s, keys[j]) < 0) j--;
                    if (i > j) break;
                    if (i < j) {
                        string key = keys[i];
                        keys[i] = keys[j];
                        keys[j] = key;
                        if (items != null) {
                            object item = items[i];
                            items[i] = items[j];
                            items[j] = item;
                        }
                    }
                    i++;
                    j--;
                } while (i <= j);
                if (j - left <= right - i) {
                    if (left < j) QuickSort(left, j);
                    left = i;
                }
                else {
                    if (i < right) QuickSort(i, right);
                    right = j;
                }
            } while (left < right);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort"]/*' />
        /// <devdoc>
        ///     Sorts an object array based on the string representation of the
        ///     elements. If the <code>items</code> parameter is not a string array, the
        /// <code>toString</code> method of each of the elements is called to
        ///     produce the string representation. The objects are then sorted by their
        ///     string representations using the default locale.
        /// </devdoc>
        public static void Sort(object[] items) {
            Sort(null, null, items, 0, ArrayLength(items), 0);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort1"]/*' />
        /// <devdoc>
        ///     Sorts a range in an object array based on the string representation of
        ///     the elements. If the <code>items</code> parameter is not a string array,
        ///     the <code>toString</code> method of each of the elements is called to
        ///     produce the string representation. The objects are then sorted by their
        ///     string representations using the default locale.
        /// </devdoc>
        public static void Sort(object[] items, int index, int count) {
            Sort(null, null, items, index, count, 0);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort2"]/*' />
        /// <devdoc>
        ///     Sorts a string array and an object array based on the elements of the
        ///     string array. The arrays are sorted using the default locale.
        /// </devdoc>
        public static void Sort(string[] keys, object[] items) {
            Sort(null, keys, items, 0, ArrayLength(items), 0);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort3"]/*' />
        /// <devdoc>
        ///     Sorts a range in a string array and a range in an object array based on
        ///     the elements of the string array. The arrays are sorted using the
        ///     default locale.
        /// </devdoc>
        public static void Sort(string[] keys, object[] items, int index, int count) {
            Sort(null, keys, items, index, count, 0);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort4"]/*' />
        /// <devdoc>
        ///     Sorts an object array based on the string representation of the
        ///     elements. If the <code>items</code> parameter is not a string array, the
        /// <code>toString</code> method of each of the elements is called to
        ///     produce the string representation. The objects are then sorted by their
        ///     string representations using the default locale and the given sorting
        ///     options.
        /// </devdoc>
        public static void Sort(object[] items, int options) {
            Sort(null, null, items, 0, ArrayLength(items), options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort5"]/*' />
        /// <devdoc>
        ///     Sorts a range in an object array based on the string representation of
        ///     the elements. If the <code>items</code> parameter is not a string array,
        ///     the <code>toString</code> method of each of the elements is called to
        ///     produce the string representation. The objects are then sorted by their
        ///     string representations using the default locale and the given sorting
        ///     options.
        /// </devdoc>
        public static void Sort(object[] items, int index, int count, int options) {
            Sort(null, null, items, index, count, options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort6"]/*' />
        /// <devdoc>
        ///     Sorts a string array and an object array based on the elements of the
        ///     string array. The arrays are sorted using the default locale and the
        ///     given sorting options.
        /// </devdoc>
        public static void Sort(string[] keys, object[] items, int options) {
            Sort(null, keys, items, 0, ArrayLength(items), options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort7"]/*' />
        /// <devdoc>
        ///     Sorts a range in a string array and a range in an object array based on
        ///     the elements of the string array. The arrays are sorted using the
        ///     default locale and the given sorting options.
        /// </devdoc>
        public static void Sort(string[] keys, object[] items, int index, int count, int options) {
            Sort(null, keys, items, index, count, options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort8"]/*' />
        /// <devdoc>
        ///     Sorts an object array based on the string representation of the
        ///     elements. If the <code>items</code> parameter is not a string array, the
        /// <code>toString</code> method of each of the elements is called to
        ///     produce the string representation. The objects are then sorted by their
        ///     string representations using the given locale and the given sorting
        ///     options.
        /// </devdoc>
        public static void Sort(CultureInfo culture, object[] items, int options) {
            Sort(culture, null, items, 0, ArrayLength(items), options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort9"]/*' />
        /// <devdoc>
        ///     Sorts a range in an object array based on the string representation of
        ///     the elements. If the <code>items</code> parameter is not a string array,
        ///     the <code>toString</code> method of each of the elements is called to
        ///     produce the string representation. The objects are then sorted by their
        ///     string representations using the given locale and the given sorting
        ///     options.
        /// </devdoc>
        public static void Sort(CultureInfo culture, object[] items, int index, int count, int options) {
            Sort(culture, null, items, index, count, options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort10"]/*' />
        /// <devdoc>
        ///     Sorts a string array and an object array based on the elements of the
        ///     string array. The arrays are sorted using the given locale and the
        ///     given sorting options.
        /// </devdoc>
        public static void Sort(CultureInfo culture, string[] keys, object[] items, int options) {
            Sort(culture, keys, items, 0, ArrayLength(items), options);
        }
 
        /// <include file='doc\StringSorter.uex' path='docs/doc[@for="StringSorter.Sort11"]/*' />
        /// <devdoc>
        ///     Sorts a range in a string array and a range in an object array based on
        ///     the elements of the string array. Elements in the <code>keys</code>
        ///     array specify the sort keys for corresponding elements in the
        /// <code>items</code> array. The range of elements given by the
        /// <code>index</code> and <code>count</code> parameters is sorted in both
        ///     arrays according to the given locale and sorting options.
        ///     If the <code>keys</code> parameter is <code>null</code>, the sort keys
        ///     are instead computed by calling the <code>toString</code> method of each
        ///     element in the <code>items</code> array.
        /// <code>null</code> keys always sort before a non-null keys.
        ///     The <code>options</code> parameter is a combination of zero or more of
        ///     the following flags: <code>IGNORECASE</code>, <code>IGNOREKANATYPE</code>,
        /// <code>IGNORENONSPACE</code>, <code>IGNORESYMBOLS</code>,
        /// <code>IGNOREWIDTH</code>, <code>STRINGSORT</code>, and
        /// <code>DESCENDING</code>.
        /// </devdoc>
        public static void Sort(CultureInfo culture, string[] keys, object[] items, int index, int count, int options) {
            // keys and items have to be the same length
            //
            if ((items == null)
                || ((keys != null) && (keys.Length != items.Length)))
                throw new ArgumentException(SR.GetString(SR.ArraysNotSameSize,
                                                                   "keys",
                                                                   "items"));
            if (count > 1) {
                StringSorter sorter = new StringSorter(culture, keys, items, options);
                sorter.QuickSort(index, index + count - 1);
            }
        }
    }
}