// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.

using System;
using System.Diagnostics;
using System.Globalization;

namespace System.Xml.Xsl.Runtime
{
    /// <summary>
    /// Base internal class for all sort keys.
    /// Inherits from IComparable, so that Array.Sort can perform comparison.
    /// </summary>
    internal abstract class XmlSortKey : IComparable
    {
        private int _priority;           // Original input ordering used to ensure that sort is stable
        private XmlSortKey? _nextKey;     // Next sort key if there are multiple keys (null otherwise)

        /// <summary>
        /// Get or set this key's index, relative to other keys involved in a sort.  This priority will
        /// break ties.  If the priority is not set, then the sort will not be stable.
        /// </summary>
        public int Priority
        {
            //get { return this.priority; }
            set
            {
                // All linked keys have same priority
                XmlSortKey? key = this;

                while (key != null)
                {
                    key._priority = value;
                    key = key._nextKey;
                }
            }
        }

        /// <summary>
        /// Sometimes a key is composed of multiple parts.  For example: (LastName, FirstName).  Multi-part
        /// keys are linked together in a list.  This method recursively adds a new key part to the end of the list.
        /// Returns the first (primary) key in the list.
        /// </summary>
        public XmlSortKey AddSortKey(XmlSortKey sortKey)
        {
            if (_nextKey != null)
            {
                // Add to end of list--this is not it
                _nextKey.AddSortKey(sortKey);
            }
            else
            {
                // This is the end of the list
                _nextKey = sortKey;
            }

            return this;
        }

        /// <summary>
        /// When two keys are compared and found to be equal, the tie must be broken.  If there is a secondary key,
        /// then use that to break the tie.  Otherwise, use the input ordering to break the tie.  Since every key
        /// has a unique index, this is guaranteed to always break the tie.
        /// </summary>
        protected int BreakSortingTie(XmlSortKey that)
        {
            if (_nextKey != null)
            {
                // There are multiple keys, so break tie using next key
                Debug.Assert(_nextKey != null && that._nextKey != null);
                return _nextKey.CompareTo(that._nextKey);
            }

            Debug.Assert(_priority != that._priority);
            return (_priority < that._priority) ? -1 : 1;
        }

        /// <summary>
        /// Compare a non-empty key (this) to an empty key (obj).  The empty sequence always sorts either before all
        /// other values, or after all other values.
        /// </summary>
        protected int CompareToEmpty(object? obj)
        {
            XmlEmptySortKey? that = obj as XmlEmptySortKey;
            Debug.Assert(that != null && !(this is XmlEmptySortKey));
            return that.IsEmptyGreatest ? -1 : 1;
        }

        /// <summary>
        /// Base internal class is abstract and doesn't actually implement CompareTo; derived classes must do this.
        /// </summary>
        public abstract int CompareTo(object? that);
    }


    /// <summary>
    /// Sort key for the empty sequence.  Empty sequence always compares sorts either before all other values,
    /// or after all other values.
    /// </summary>
    internal sealed class XmlEmptySortKey : XmlSortKey
    {
        private readonly bool _isEmptyGreatest;

        public XmlEmptySortKey(XmlCollation collation)
        {
            // Greatest, Ascending: isEmptyGreatest = true
            // Greatest, Descending: isEmptyGreatest = false
            // Least, Ascending: isEmptyGreatest = false
            // Least, Descending: isEmptyGreatest = true
            _isEmptyGreatest = collation.EmptyGreatest != collation.DescendingOrder;
        }

        public bool IsEmptyGreatest
        {
            get { return _isEmptyGreatest; }
        }

        public override int CompareTo(object? obj)
        {
            XmlEmptySortKey? that = obj as XmlEmptySortKey;

            if (that == null)
            {
                // Empty compared to non-empty
                Debug.Assert(obj is XmlSortKey);
                return -(obj as XmlSortKey)!.CompareTo(this);
            }

            // Empty compared to empty
            return BreakSortingTie(that);
        }
    }


    /// <summary>
    /// Sort key for xs:decimal values.
    /// </summary>
    internal sealed class XmlDecimalSortKey : XmlSortKey
    {
        private readonly decimal _decVal;

        public XmlDecimalSortKey(decimal value, XmlCollation collation)
        {
            // Invert decimal if sorting in descending order
            _decVal = collation.DescendingOrder ? -value : value;
        }

        public override int CompareTo(object? obj)
        {
            XmlDecimalSortKey? that = obj as XmlDecimalSortKey;
            int cmp;

            if (that == null)
                return CompareToEmpty(obj);

            cmp = decimal.Compare(_decVal, that._decVal);
            if (cmp == 0)
                return BreakSortingTie(that);

            return cmp;
        }
    }


    /// <summary>
    /// Sort key for xs:integer values.
    /// </summary>
    internal class XmlIntegerSortKey : XmlSortKey
    {
        private readonly long _longVal;

        public XmlIntegerSortKey(long value, XmlCollation collation)
        {
            // Invert long if sorting in descending order
            _longVal = collation.DescendingOrder ? ~value : value;
        }

        public override int CompareTo(object? obj)
        {
            XmlIntegerSortKey? that = obj as XmlIntegerSortKey;

            if (that == null)
                return CompareToEmpty(obj);

            if (_longVal == that._longVal)
                return BreakSortingTie(that);

            return (_longVal < that._longVal) ? -1 : 1;
        }
    }


    /// <summary>
    /// Sort key for xs:int values.
    /// </summary>
    internal sealed class XmlIntSortKey : XmlSortKey
    {
        private readonly int _intVal;

        public XmlIntSortKey(int value, XmlCollation collation)
        {
            // Invert integer if sorting in descending order
            _intVal = collation.DescendingOrder ? ~value : value;
        }

        public override int CompareTo(object? obj)
        {
            XmlIntSortKey? that = obj as XmlIntSortKey;

            if (that == null)
                return CompareToEmpty(obj);

            if (_intVal == that._intVal)
                return BreakSortingTie(that);

            return (_intVal < that._intVal) ? -1 : 1;
        }
    }

    /// <summary>
    /// Sort key for xs:string values.  Strings are sorted according to a byte-wise sort key calculated by caller.
    /// </summary>
    internal sealed class XmlStringSortKey : XmlSortKey
    {
        private readonly SortKey? _sortKey;
        private readonly byte[]? _sortKeyBytes;
        private readonly bool _descendingOrder;

        public XmlStringSortKey(SortKey sortKey, bool descendingOrder)
        {
            _sortKey = sortKey;
            _descendingOrder = descendingOrder;
        }

        public XmlStringSortKey(byte[] sortKey, bool descendingOrder)
        {
            _sortKeyBytes = sortKey;
            _descendingOrder = descendingOrder;
        }

        public override int CompareTo(object? obj)
        {
            XmlStringSortKey? that = obj as XmlStringSortKey;
            int idx, cntCmp, result;

            if (that == null)
                return CompareToEmpty(obj);

            // Compare either using SortKey.Compare or byte arrays
            if (_sortKey != null)
            {
                Debug.Assert(that._sortKey != null, "Both keys must have non-null sortKey field");
                result = SortKey.Compare(_sortKey, that._sortKey);
            }
            else
            {
                Debug.Assert(_sortKeyBytes != null && that._sortKeyBytes != null, "Both keys must have non-null sortKeyBytes field");

                cntCmp = (_sortKeyBytes.Length < that._sortKeyBytes.Length) ? _sortKeyBytes.Length : that._sortKeyBytes.Length;
                for (idx = 0; idx < cntCmp; idx++)
                {
                    if (_sortKeyBytes[idx] < that._sortKeyBytes[idx])
                    {
                        result = -1;
                        goto Done;
                    }

                    if (_sortKeyBytes[idx] > that._sortKeyBytes[idx])
                    {
                        result = 1;
                        goto Done;
                    }
                }

                // So far, keys are equal, so now test length of each key
                if (_sortKeyBytes.Length < that._sortKeyBytes.Length)
                    result = -1;
                else if (_sortKeyBytes.Length > that._sortKeyBytes.Length)
                    result = 1;
                else
                    result = 0;
            }

        Done:
            // Use document order to break sorting tie
            if (result == 0)
                return BreakSortingTie(that);

            return _descendingOrder ? -result : result;
        }
    }

    /// <summary>
    /// Sort key for Double values.
    /// </summary>
    internal sealed class XmlDoubleSortKey : XmlSortKey
    {
        private readonly double _dblVal;
        private readonly bool _isNaN;

        public XmlDoubleSortKey(double value, XmlCollation collation)
        {
            if (double.IsNaN(value))
            {
                // Treat NaN as if it were the empty sequence
                _isNaN = true;

                // Greatest, Ascending: isEmptyGreatest = true
                // Greatest, Descending: isEmptyGreatest = false
                // Least, Ascending: isEmptyGreatest = false
                // Least, Descending: isEmptyGreatest = true
                _dblVal = (collation.EmptyGreatest != collation.DescendingOrder) ? double.PositiveInfinity : double.NegativeInfinity;
            }
            else
            {
                _dblVal = collation.DescendingOrder ? -value : value;
            }
        }

        public override int CompareTo(object? obj)
        {
            XmlDoubleSortKey? that = obj as XmlDoubleSortKey;

            if (that == null)
            {
                // Compare to empty sequence
                if (_isNaN)
                    return BreakSortingTie((obj as XmlSortKey)!);

                return CompareToEmpty(obj);
            }

            if (_dblVal == that._dblVal)
            {
                if (_isNaN)
                {
                    // NaN sorts equal to NaN
                    if (that._isNaN)
                        return BreakSortingTie(that);

                    // NaN sorts before or after all non-NaN values
                    Debug.Assert(_dblVal == double.NegativeInfinity || _dblVal == double.PositiveInfinity);
                    return (_dblVal == double.NegativeInfinity) ? -1 : 1;
                }
                else if (that._isNaN)
                {
                    // NaN sorts before or after all non-NaN values
                    Debug.Assert(that._dblVal == double.NegativeInfinity || that._dblVal == double.PositiveInfinity);
                    return (that._dblVal == double.NegativeInfinity) ? 1 : -1;
                }

                return BreakSortingTie(that);
            }

            return (_dblVal < that._dblVal) ? -1 : 1;
        }
    }


    /// <summary>
    /// Sort key for DateTime values (just convert DateTime to ticks and use Long sort key).
    /// </summary>
    internal sealed class XmlDateTimeSortKey : XmlIntegerSortKey
    {
        public XmlDateTimeSortKey(DateTime value, XmlCollation collation) : base(value.Ticks, collation)
        {
        }
    }
}