using System;
using System.Collections.Generic;
using System.Linq;

namespace Amphora.UnitTests
{
    public class SortTests : UnitTestSharp.TestFixture
    {
        /// <summary>
        /// Returns the mask of the lowest <paramref name="span"/> bits of a key.
        /// </summary>
        public static int SpanMask(int span)
        {
            if (span == 32)
            {
                return -1;
            }

            return (1 << span) - 1;
        }

        /// <summary>
        /// What an order array starts with in a test, which no position can be.
        /// </summary>
        public const int Unwritten = -7;

        /// <summary>
        /// The largest batch size that the tests of every size go up to, which is past where radix passes take over
        /// from insertion.
        /// </summary>
        public const int LargestBatchChecked = 130;

        /// <summary>
        /// Makes keys that are spread over the whole int range, and not in any order.
        /// </summary>
        public static int[] Scattered(int count)
        {
            var returnMe = new int[count];
            for (int i = 0; i < count; ++i)
            {
                returnMe[i] = unchecked((int)(i * 2654435761u));
            }

            return returnMe;
        }

        /// <summary>
        /// Makes an order array of the given length that nothing has written to.
        /// </summary>
        public static int[] UnwrittenOrder(int length)
        {
            var returnMe = new int[length];
            for (int i = 0; i < length; ++i)
            {
                returnMe[i] = Unwritten;
            }

            return returnMe;
        }

        /// <summary>
        /// Returns the positions of the first <paramref name="count"/> keys in a stable sort of them.
        /// </summary>
        public static int[] ExpectedOrder(int[] keys, int count)
        {
            return Enumerable.Range(0, count).OrderBy(i => keys[i]).ToArray();
        }

        public class RadixCrossoverTests : UnitTestSharp.TestFixture
        {
            public void EverySpan_IsAtLeastTheRadixMinimum()
            {
                for (int span = 0; span <= 32; ++span)
                {
                    CheckTrue(Sort.RadixCrossover(span) >= Sort.RadixMinimum);
                }
            }

            public void TheProbe_IsNoLongerThanTheRadixMinimum()
            {
                CheckTrue(Sort.ProbeLength <= Sort.RadixMinimum);
            }

            public void WiderKeys_NeverCrossSooner()
            {
                for (int span = 1; span <= 32; ++span)
                {
                    CheckTrue(Sort.RadixCrossover(span) >= Sort.RadixCrossover(span - 1));
                }
            }

            public void KeysThatDifferInEveryBit_CrossAtAboutAThousand()
            {
                int crossover = Sort.RadixCrossover(32);

                CheckTrue(crossover >= 900 && crossover <= 1100);
            }

            public void NegativeSpan_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.RadixCrossover(-1);
            }

            public void SpanWiderThanAKey_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.RadixCrossover(33);
            }
        }

        public class RadixPaysTests : UnitTestSharp.TestFixture
        {
            [UnitTestSharp.IgnoreTest]
            public bool Pays(int[] keys, int count)
            {
                int low;
                int high;
                bool anyNegative;

                return Sort.RadixPays(keys, count, out low, out high, out anyNegative);
            }

            public void FewerThanTheRadixMinimum_DoNotPay()
            {
                CheckFalse(Pays(RadixKeySorterTests.Scrambled(Sort.RadixMinimum - 1, 0x3), Sort.RadixMinimum - 1));
            }

            public void TheRadixMinimumOfNarrowKeys_Pay()
            {
                CheckTrue(Pays(RadixKeySorterTests.Scrambled(Sort.RadixMinimum, 0x3), Sort.RadixMinimum));
            }

            public void WideKeysBelowTheirCrossover_DoNotPay()
            {
                int count = Sort.RadixCrossover(31) - 1;

                CheckFalse(Pays(RadixKeySorterTests.Scrambled(count, 0x7FFFFFFF), count));
            }

            public void WideKeysAtTheirCrossover_Pay()
            {
                int count = Sort.RadixCrossover(31);

                CheckTrue(Pays(RadixKeySorterTests.Scrambled(count, 0x7FFFFFFF), count));
            }

            public void NarrowKeysFollowedByAWideOne_DoNotPay()
            {
                int[] keys = RadixKeySorterTests.Scrambled(200, 0xFF);
                keys[199] = 0x7FFFFFFF;

                CheckFalse(Pays(keys, 200));
            }

            public void WideKeysFollowedByNarrowOnes_DoNotPay()
            {
                int[] keys = RadixKeySorterTests.Scrambled(200, 0xFF);
                for (int i = 0; i < Sort.ProbeLength; ++i)
                {
                    keys[i] = unchecked((int)(i * 2654435761u)) & 0x7FFFFFFF;
                }

                CheckFalse(Pays(keys, 200));
            }

            public void OnlyTheFirstCountKeysAreLookedAt()
            {
                int[] keys = RadixKeySorterTests.Scrambled(300, 0xFF);
                keys[250] = 0x7FFFFFFF;

                CheckTrue(Pays(keys, 200));
            }

            public void Pays_ReportsTheBitsTheKeysDifferIn()
            {
                var keys = new int[200];
                for (int i = 0; i < keys.Length; ++i)
                {
                    keys[i] = (i % 256) << 8;
                }

                int low;
                int high;
                bool anyNegative;

                CheckTrue(Sort.RadixPays(keys, 200, out low, out high, out anyNegative));
                CheckEqual(8, low);
                CheckEqual(16, high);
                CheckFalse(anyNegative);
            }

            public void Pays_ReportsNegativeKeys()
            {
                int[] keys = RadixKeySorterTests.Scrambled(200, 0xFF);
                keys[100] = -5;

                int low;
                int high;
                bool anyNegative;

                Sort.RadixPays(keys, 200, out low, out high, out anyNegative);

                CheckTrue(anyNegative);
            }
        }

        public class IsAscendingTests : UnitTestSharp.TestFixture
        {
            public void KeysInOrder_IsTrue()
            {
                CheckTrue(Sort.IsAscending(new[] { 1, 2, 2, 5 }, 4, signed: true));
            }

            public void EqualKeys_IsTrue()
            {
                CheckTrue(Sort.IsAscending(new[] { 3, 3, 3 }, 3, signed: true));
            }

            public void OneKey_IsTrue()
            {
                CheckTrue(Sort.IsAscending(new[] { 3 }, 1, signed: true));
            }

            public void ANeighborOutOfOrder_IsFalse()
            {
                CheckFalse(Sort.IsAscending(new[] { 1, 3, 2 }, 3, signed: true));
            }

            public void OnlyTheFirstCountKeysAreLookedAt()
            {
                CheckTrue(Sort.IsAscending(new[] { 1, 2, 3, 0 }, 3, signed: true));
            }

            public void ANegativeAfterAPositive_IsFalseWhenSigned()
            {
                CheckFalse(Sort.IsAscending(new[] { 1, -1 }, 2, signed: true));
            }

            public void ANegativeAfterAPositive_IsTrueWhenUnsigned()
            {
                CheckTrue(Sort.IsAscending(new[] { 1, -1 }, 2, signed: false));
            }

            public void UnsignedKeysOutOfOrder_IsFalse()
            {
                CheckFalse(Sort.IsAscending(new[] { -1, 1 }, 2, signed: false));
            }
        }

        public class KeysTests : UnitTestSharp.TestFixture
        {
            /// <summary>
            /// Sorts the first <paramref name="count"/> keys and checks they come out in order and the rest stay put.
            /// </summary>
            [UnitTestSharp.IgnoreTest]
            public void CheckSorts(RadixKeySorter sorter, int[] keys, int count)
            {
                var expected = (int[])keys.Clone();
                Array.Sort(expected, 0, count);

                Sort.Keys(keys, count, sorter);

                CheckEqual(expected, keys);
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckSorts(int[] keys)
            {
                CheckSorts(new RadixKeySorter(), keys, keys.Length);
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckSortsUnsigned(RadixKeySorter sorter, uint[] keys, int count)
            {
                var expected = (uint[])keys.Clone();
                Array.Sort(expected, 0, count);

                Sort.Keys(keys, count, sorter);

                CheckEqual(expected, keys);
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckSortsUnsigned(uint[] keys)
            {
                CheckSortsUnsigned(new RadixKeySorter(), keys, keys.Length);
            }

            public void NoKeys_ChangesNothing()
            {
                CheckSorts(new RadixKeySorter(), new[] { 3, 1, 2 }, 0);
            }

            public void OneKey_ChangesNothing()
            {
                CheckSorts(new RadixKeySorter(), new[] { 3, 1, 2 }, 1);
            }

            public void AFewKeys_AreSorted()
            {
                CheckSorts(RadixKeySorterTests.Scrambled(10, 0xFFFF));
            }

            public void JustBelowTheAnalyzeLimit_AreSorted()
            {
                CheckSorts(RadixKeySorterTests.Scrambled(Sort.AnalyzeLimit - 1, 0xFFFF));
            }

            public void ExactlyTheAnalyzeLimit_AreSorted()
            {
                CheckSorts(RadixKeySorterTests.Scrambled(Sort.AnalyzeLimit, 0xFFFF));
            }

            public void ExactlyTheAnalyzeLimitAlreadyAscending_AreUnchanged()
            {
                CheckSorts(Enumerable.Range(0, Sort.AnalyzeLimit).ToArray());
            }

            public void EveryKeyWidthJustBelowTheCrossover_AreSorted()
            {
                for (int span = 1; span <= 32; ++span)
                {
                    CheckSorts(RadixKeySorterTests.Scrambled(Sort.RadixCrossover(span) - 1, SpanMask(span)));
                }
            }

            public void EveryKeyWidthExactlyAtTheCrossover_AreSorted()
            {
                for (int span = 1; span <= 32; ++span)
                {
                    CheckSorts(RadixKeySorterTests.Scrambled(Sort.RadixCrossover(span), SpanMask(span)));
                }
            }

            public void EveryKeyWidthJustOverTheCrossover_AreSorted()
            {
                for (int span = 1; span <= 32; ++span)
                {
                    CheckSorts(RadixKeySorterTests.Scrambled(Sort.RadixCrossover(span) + 1, SpanMask(span)));
                }
            }

            public void NarrowKeysOverTheCrossover_AreSortedWithAReusedSorter()
            {
                var sorter = new RadixKeySorter();
                foreach (int count in new[] { 100, 300, 1000, 5000, 200 })
                {
                    CheckSorts(sorter, RadixKeySorterTests.Scrambled(count, 0xFF), count);
                }
            }

            public void KeysDifferingOnlyInTheMiddleBits_AreSorted()
            {
                CheckSorts(RadixKeySorterTests.Scrambled(500, 0x0000FF00));
            }

            public void KeysDifferingOnlyInTheSignBit_AreSorted()
            {
                CheckSorts(RadixKeySorterTests.Scrambled(300, int.MinValue));
            }

            public void OnlyNegativeKeys_AreSorted()
            {
                CheckSorts(RadixKeySorterTests.Scrambled(600, 0xFFFF).Select(key => ~key).ToArray());
            }

            public void ManyKeys_AreSorted()
            {
                CheckSorts(RadixKeySorterTests.Scrambled(20000, 0x7FFFFFFF));
            }

            public void AlreadyAscending_AreUnchanged()
            {
                CheckSorts(Enumerable.Range(0, 3000).ToArray());
            }

            public void AlreadyAscendingBelowTheCrossover_AreUnchanged()
            {
                CheckSorts(Enumerable.Range(0, 500).ToArray());
            }

            public void ManyDescending_BecomeAscending()
            {
                CheckSorts(Enumerable.Range(0, 3000).Reverse().ToArray());
            }

            public void NegativeKeys_ComeFirst()
            {
                int[] keys = RadixKeySorterTests.Scrambled(3000, 0x7FFFFFFF);
                for (int i = 0; i < keys.Length; i += 3)
                {
                    keys[i] = -keys[i];
                }

                CheckSorts(keys);
            }

            public void OnlyTheFirstCount_AreSorted()
            {
                CheckSorts(new RadixKeySorter(), RadixKeySorterTests.Scrambled(4000, 0x7FFFFFFF), 3000);
            }

            public void OnlyTheFirstCountOfAFew_AreSorted()
            {
                CheckSorts(new RadixKeySorter(), new[] { 5, 4, 3, 2, 1, 0 }, 4);
            }

            public void UnsignedAFewKeys_AreSorted()
            {
                CheckSortsUnsigned(RadixKeySorterTests.Unsigned(RadixKeySorterTests.Scrambled(10, -1)));
            }

            public void UnsignedExactlyTheAnalyzeLimitAlreadyAscending_AreUnchanged()
            {
                CheckSortsUnsigned(Enumerable.Range(0, Sort.AnalyzeLimit).Select(i => (uint)i << 27).ToArray());
            }

            public void UnsignedEveryKeyWidthAroundTheCrossover_AreSorted()
            {
                for (int span = 1; span <= 32; ++span)
                {
                    foreach (int count in new[] { Sort.RadixCrossover(span) - 1, Sort.RadixCrossover(span),
                        Sort.RadixCrossover(span) + 1 })
                    {
                        CheckSortsUnsigned(RadixKeySorterTests.Unsigned(
                            RadixKeySorterTests.Scrambled(count, SpanMask(span))));
                    }
                }
            }

            public void UnsignedKeysDifferingOnlyInTheTopBit_AreSorted()
            {
                CheckSortsUnsigned(RadixKeySorterTests.Unsigned(RadixKeySorterTests.Scrambled(300, int.MinValue)));
            }

            public void UnsignedKeysDifferingOnlyInTheMiddleBits_AreSorted()
            {
                CheckSortsUnsigned(RadixKeySorterTests.Unsigned(RadixKeySorterTests.Scrambled(500, 0x0000FF00)));
            }

            public void UnsignedKeysPastTheIntRange_AreSortedAsUnsigned()
            {
                CheckSortsUnsigned(RadixKeySorterTests.Unsigned(RadixKeySorterTests.Scrambled(3000, -1))
                    .Select(key => key | 0x80000000).ToArray());
            }

            public void UnsignedAlreadyAscendingPastTheIntRange_AreUnchanged()
            {
                CheckSortsUnsigned(Enumerable.Range(0, 3000).Select(i => 0x80000000 + (uint)i * 1000).ToArray());
            }

            public void UnsignedOnlyTheFirstCount_AreSorted()
            {
                CheckSortsUnsigned(
                    new RadixKeySorter(), RadixKeySorterTests.Unsigned(RadixKeySorterTests.Scrambled(4000, -1)), 3000);
            }

            public void NullKeys_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Keys((int[])null, 0, new RadixKeySorter());
            }

            public void UnsignedNullKeys_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Keys((uint[])null, 0, new RadixKeySorter());
            }

            public void NullSorter_ThrowsEvenForAFewKeys()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Keys(new int[3], 3, null);
            }

            public void UnsignedNullSorter_ThrowsEvenForAFewKeys()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Keys(new uint[3], 3, null);
            }

            public void NegativeCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Keys(new int[3], -1, new RadixKeySorter());
            }

            public void CountBeyondTheKeys_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Keys(new int[3], 4, new RadixKeySorter());
            }

            public void UnsignedCountBeyondTheKeys_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Keys(new uint[3], 4, new RadixKeySorter());
            }

            public static readonly int[] AllocationSource = RadixKeySorterTests.Scrambled(5000, 0x7FFFFFFF);
            public static readonly int[] AllocationKeys = new int[5000];
            public static readonly RadixKeySorter AllocationSorter = Grown();

            public static RadixKeySorter Grown()
            {
                var returnMe = new RadixKeySorter();
                Array.Copy(AllocationSource, AllocationKeys, 5000);
                Sort.Keys(AllocationKeys, 5000, returnMe);
                return returnMe;
            }

            [UnitTestSharp.AllocationTest]
            public void OnceTheSorterHasGrown_AllocatesNothing()
            {
                Array.Copy(AllocationSource, AllocationKeys, 5000);
                Sort.Keys(AllocationKeys, 5000, AllocationSorter);

                CheckNoAllocations();
                CheckTrue(AllocationKeys[0] <= AllocationKeys[4999]);
            }
        }

        public class OrderTests : UnitTestSharp.TestFixture
        {
            /// <summary>
            /// Orders the first <paramref name="count"/> keys and checks the positions come out as a stable sort would
            /// give them, the keys are untouched, and the order past the count is untouched.
            /// </summary>
            [UnitTestSharp.IgnoreTest]
            public void CheckOrders(int[] keys, int count)
            {
                int[] original = (int[])keys.Clone();
                int[] order = UnwrittenOrder(keys.Length + 2);

                Sort.Order(keys, count, order);

                var expected = new List<int>(ExpectedOrder(original, count));
                for (int i = count; i < order.Length; ++i)
                {
                    expected.Add(Unwritten);
                }

                CheckEqual(expected, order.ToList());
                CheckEqual(original, keys);
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckOrders(int[] keys)
            {
                CheckOrders(keys, keys.Length);
            }

            public void NoKeys_WritesNothing()
            {
                var order = UnwrittenOrder(3);

                Sort.Order(new[] { 3, 1, 2 }, 0, order);

                CheckEqual(UnwrittenOrder(3), order);
            }

            public void OneKey_IsPositionZero()
            {
                var order = UnwrittenOrder(3);

                Sort.Order(new[] { 3, 1, 2 }, 1, order);

                CheckEqual(new[] { 0, Unwritten, Unwritten }, order);
            }

            public void AFewKeys_AreOrdered()
            {
                CheckOrders(new[] { 5, 1, 4, 2, 3 });
            }

            public void AFewKeysAlreadyAscending_AreTheIdentity()
            {
                CheckOrders(new[] { 1, 2, 2, 5, 9 });
            }

            public void AFewEqualKeys_KeepTheirOrder()
            {
                CheckOrders(new[] { 2, 1, 2, 1, 2, 1 });
            }

            public void ExactlyTheUncheckedLimit_IsOrdered()
            {
                CheckOrders(Scattered(Sort.UncheckedLimit));
            }

            public void OneMoreThanTheUncheckedLimit_IsOrdered()
            {
                CheckOrders(Scattered(Sort.UncheckedLimit + 1));
            }

            public void ExactlyTheUnrolledLimit_IsOrdered()
            {
                CheckOrders(Scattered(Sort.UnrolledLimit));
            }

            public void OneMoreThanTheUnrolledLimit_IsOrdered()
            {
                CheckOrders(Scattered(Sort.UnrolledLimit + 1));
            }

            public void TheUncheckedLimit_IsNoMoreThanTheUnrolledLimit()
            {
                CheckTrue(Sort.UncheckedLimit <= Sort.UnrolledLimit);
            }

            public void EveryBatchSizeWithEqualKeys_KeepsTheirOrder()
            {
                foreach (int distinct in new[] { 1, 2, 3, 5, 40 })
                {
                    for (int count = 2; count <= LargestBatchChecked; ++count)
                    {
                        CheckOrders(Enumerable.Range(0, count).Select(i => (i * 7 + 3) % distinct).ToArray());
                    }
                }
            }

            public void EveryBatchSizeInReverse_IsOrdered()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    CheckOrders(Enumerable.Range(0, count).Reverse().ToArray());
                }
            }

            public void EveryBatchSizeAlreadyAscending_AreTheIdentity()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    CheckOrders(Enumerable.Range(0, count).ToArray());
                }
            }

            public void EveryBatchSizeWithAnExtremeOutOfPlace_IsOrdered()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    int[] keys = Enumerable.Range(0, count).ToArray();
                    keys[count / 2] = int.MinValue;
                    keys[count - 1] = int.MaxValue;
                    keys[0] = int.MaxValue;
                    CheckOrders(keys);
                }
            }

            public void EveryBatchSizeWithNegativeKeys_IsOrdered()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    CheckOrders(Enumerable.Range(0, count).Select(i => (i * 37 % 101) - 50).ToArray());
                }
            }

            public void EveryBatchSizeScattered_IsOrdered()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    CheckOrders(Scattered(count));
                }
            }

            public void KeysThatSwapInPairsAndTriples_AreOrdered()
            {
                CheckOrders(new[] { 1, 0, 3, 2, 5, 4, 8, 6, 7, 9, 10, 11 });
            }

            public void ManyKeysAlreadyAscendingWithEqualKeys_KeepTheirOrder()
            {
                CheckOrders(Enumerable.Range(0, 30).Select(i => i / 4).ToArray());
            }

            public void AlreadyAscendingExactlyTheInsertionLimit_AreTheIdentity()
            {
                CheckOrders(Enumerable.Range(0, Sort.InsertionSortLimit).ToArray());
            }

            public void ManyKeysDescending_AreReversed()
            {
                CheckOrders(Enumerable.Range(0, 20).Reverse().ToArray());
            }

            public void DescendingWithTheFirstTwoKeysEqual_KeepsThemInOrder()
            {
                CheckOrders(Enumerable.Range(0, 20).Select(i => 30 - Math.Max(i, 1)).ToArray());
            }

            public void DescendingWithEqualKeysInTheMiddle_KeepsThemInOrder()
            {
                CheckOrders(Enumerable.Range(0, 20).Select(i => 30 - (i < 10 ? i : i - 1)).ToArray());
            }

            public void DescendingWithTheLastTwoKeysEqual_KeepsThemInOrder()
            {
                CheckOrders(Enumerable.Range(0, 20).Select(i => 30 - Math.Min(i, 18)).ToArray());
            }

            public void DescendingWithTheLastKeyOutOfPlace_IsOrdered()
            {
                int[] keys = Enumerable.Range(0, 20).Select(i => 30 - i).ToArray();
                keys[19] = 100;

                CheckOrders(keys);
            }

            public void DescendingAfterAnAscendingFirstPair_IsOrdered()
            {
                CheckOrders(new[] { 0 }.Concat(Enumerable.Range(0, 19).Select(i => 30 - i)).ToArray());
            }

            public void DescendingFromTheHighestKeyToTheLowest_IsOrdered()
            {
                long step = uint.MaxValue / 19u;

                CheckOrders(Enumerable.Range(0, 20).Select(i => (int)(int.MaxValue - i * step)).ToArray());
            }

            public void ManyEqualKeysBelowTheInsertionLimit_KeepTheirOrder()
            {
                CheckOrders(Enumerable.Range(0, 20).Select(i => i % 3).ToArray());
            }

            public void ExactlyTheInsertionLimit_IsOrdered()
            {
                CheckOrders(Scattered(Sort.InsertionSortLimit));
            }

            public void OneMoreThanTheInsertionLimit_IsOrdered()
            {
                CheckOrders(Scattered(Sort.InsertionSortLimit + 1));
            }

            public void ManyScatteredKeys_AreOrdered()
            {
                CheckOrders(Scattered(5000));
            }

            public void MoreKeysThanTheFirstPassHasBuckets_AreOrdered()
            {
                CheckOrders(Scattered(40000));
            }

            public void ManyKeysWithManyTies_KeepTheirOrder()
            {
                CheckOrders(Enumerable.Range(0, 5000).Select(i => i * 7919 % 1000).ToArray());
            }

            public void ManyKeysOfTwoValues_KeepTheirOrder()
            {
                CheckOrders(Enumerable.Range(0, 1000).Select(i => i % 2).ToArray());
            }

            public void ManyKeysThatDifferOnlyInTheLowestBit_AreOrdered()
            {
                CheckOrders(Scattered(1000).Select(key => key & 1).ToArray());
            }

            public void ManyKeysThatDifferOnlyInTheMiddleBits_AreOrdered()
            {
                CheckOrders(Scattered(3000).Select(key => key & 0x00FF0F00).ToArray());
            }

            public void ManyKeysThatShareTheirHighBits_AreOrdered()
            {
                CheckOrders(Scattered(3000).Select(key => 100000000 + (key & 0xFFFF)).ToArray());
            }

            public void ManyKeysMostlyInOneBucket_AreOrdered()
            {
                int[] keys = Scattered(5000);
                for (int i = 0; i < keys.Length; ++i)
                {
                    if (i % 10 != 0)
                    {
                        keys[i] = 5000000 + (keys[i] & 7);
                    }
                }

                CheckOrders(keys);
            }

            public void ManyKeysMostlyInOneBucketWithTies_KeepTheirOrder()
            {
                int[] keys = Scattered(5000);
                for (int i = 0; i < keys.Length; ++i)
                {
                    keys[i] = i % 10 == 0 ? keys[i] % 50 : 5000000 + (i & 1);
                }

                CheckOrders(keys);
            }

            public void ManyKeysThatAreAllNegative_AreOrdered()
            {
                CheckOrders(Scattered(500).Select(key => key | int.MinValue).ToArray());
            }

            public void ManyNegativeAndPositiveKeys_AreOrdered()
            {
                CheckOrders(Scattered(2000));
            }

            public void ManyKeysAtTheExtremes_AreOrdered()
            {
                CheckOrders(Enumerable.Range(0, 500).Select(i => i % 3 == 0 ? int.MinValue : int.MaxValue).ToArray());
            }

            public void ManyKeysThatDifferOnlyInTheSignBit_AreOrdered()
            {
                CheckOrders(Enumerable.Range(0, 300).Select(i => i % 2 == 0 ? int.MinValue : 0).ToArray());
            }

            public void ManyKeysDescendingWithTies_KeepTheirOrder()
            {
                CheckOrders(Enumerable.Range(0, 2000).Select(i => (2000 - i) / 3).ToArray());
            }

            public void ManyKeysAlreadyAscending_AreTheIdentity()
            {
                CheckOrders(Enumerable.Range(0, 1000).ToArray());
            }

            public void ManyEqualKeys_AreTheIdentity()
            {
                CheckOrders(Enumerable.Repeat(7, 1000).ToArray());
            }

            public void OnlyTheFirstCountKeys_AreOrdered()
            {
                CheckOrders(Scattered(100), 60);
            }

            public void OnlyTheFirstCountKeys_OfAFewAreOrdered()
            {
                CheckOrders(Scattered(30), 20);
            }

            public void NullKeys_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Order(null, 3, new int[3]);
            }

            public void NullOrder_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Order(new int[3], 3, null);
            }

            public void NegativeCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Order(new int[3], -1, new int[3]);
            }

            public void CountBeyondTheKeys_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Order(new int[3], 4, new int[5]);
            }

            public void CountBeyondTheOrder_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Order(new int[5], 4, new int[3]);
            }

            public static readonly int[][] AllocationKeys =
            {
                Scattered(Sort.UnrolledLimit), Scattered(Sort.InsertionSortLimit), Scattered(40000),
            };

            public static readonly int[] AllocationOrder = new int[40000];
            public static readonly int[] ReversedKeys =
                Enumerable.Range(0, Sort.InsertionSortLimit).Reverse().ToArray();
            public static readonly bool Warmed = Warm();

            [UnitTestSharp.IgnoreTest]
            public static bool Warm()
            {
                foreach (int[] keys in AllocationKeys)
                {
                    Sort.Order(keys, keys.Length, AllocationOrder);
                }

                Sort.Order(ReversedKeys, ReversedKeys.Length, AllocationOrder);
                return true;
            }

            [UnitTestSharp.AllocationTest]
            public void AnUnrolledBatch_AllocatesNothing()
            {
                Sort.Order(AllocationKeys[0], AllocationKeys[0].Length, AllocationOrder);

                CheckNoAllocations();
            }

            [UnitTestSharp.AllocationTest]
            public void AnInsertionOrderedBatch_AllocatesNothing()
            {
                Sort.Order(AllocationKeys[1], AllocationKeys[1].Length, AllocationOrder);

                CheckNoAllocations();
            }

            [UnitTestSharp.AllocationTest]
            public void ARadixOrderedBatch_AllocatesNothing()
            {
                Sort.Order(AllocationKeys[2], AllocationKeys[2].Length, AllocationOrder);

                CheckNoAllocations();
            }

            [UnitTestSharp.AllocationTest]
            public void AReversedBatch_AllocatesNothing()
            {
                Sort.Order(ReversedKeys, ReversedKeys.Length, AllocationOrder);

                CheckNoAllocations();
            }
        }

        public class ApplyOrderTests : UnitTestSharp.TestFixture
        {
            /// <summary>
            /// Applies an order to numbered items and checks the items follow it, the order is as it was, and the items
            /// past the count are untouched.
            /// </summary>
            [UnitTestSharp.IgnoreTest]
            public void CheckApplies(int[] order, int count)
            {
                int[] original = (int[])order.Clone();
                int[] items = Enumerable.Range(0, order.Length).Select(i => i * 10).ToArray();

                Sort.ApplyOrder(items, order, count);

                var expected = new List<int>();
                for (int i = 0; i < order.Length; ++i)
                {
                    expected.Add((i < count ? original[i] : i) * 10);
                }

                CheckEqual(expected, items.ToList());
                CheckEqual(original, order);
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckApplies(int[] order)
            {
                CheckApplies(order, order.Length);
            }

            public void NoItems_ChangesNothing()
            {
                CheckApplies(new[] { 1, 0 }, 0);
            }

            public void OneItem_ChangesNothing()
            {
                CheckApplies(new[] { 0 });
            }

            public void TheIdentity_ChangesNothing()
            {
                CheckApplies(new[] { 0, 1, 2, 3, 4 });
            }

            public void TwoItemsSwapped_AreSwapped()
            {
                CheckApplies(new[] { 1, 0 });
            }

            public void ACycleOfThree_IsFollowed()
            {
                CheckApplies(new[] { 1, 2, 0 });
            }

            public void TheOtherCycleOfThree_IsFollowed()
            {
                CheckApplies(new[] { 2, 0, 1 });
            }

            public void SeveralCyclesAndFixedPoints_AreFollowed()
            {
                CheckApplies(new[] { 1, 0, 2, 4, 5, 3, 6, 9, 8, 7 });
            }

            public void TheReversal_IsFollowed()
            {
                CheckApplies(Enumerable.Range(0, 11).Reverse().ToArray());
            }

            public void OnlyTheFirstCountItems_AreMoved()
            {
                CheckApplies(new[] { 2, 0, 1, 3, 4, 5 }, 3);
            }

            public void ManyItems_AreMoved()
            {
                int[] keys = Scattered(1000);

                CheckApplies(Enumerable.Range(0, 1000).OrderBy(i => keys[i]).ToArray());
            }

            public void ItemsThatAreReferences_AreMoved()
            {
                var items = new[] { "a", "b", "c", "d" };
                var order = new[] { 3, 1, 0, 2 };

                Sort.ApplyOrder(items, order, 4);

                CheckEqual(new[] { "d", "b", "a", "c" }, items);
            }

            public void ADuplicatePosition_ThrowsAndLeavesTheOrderAsItWas()
            {
                int[] order = { 1, 0, 1 };
                bool threw = false;
                try
                {
                    Sort.ApplyOrder(new[] { 10, 20, 30 }, order, 3);
                }
                catch (ArgumentException)
                {
                    threw = true;
                }

                CheckTrue(threw);
                CheckEqual(new[] { 1, 0, 1 }, order);
            }

            public void ADuplicateThatLeavesNoCycleToClose_ThrowsAndLeavesTheOrderAsItWas()
            {
                int[] order = { 0, 0 };
                bool threw = false;
                try
                {
                    Sort.ApplyOrder(new[] { 10, 20 }, order, 2);
                }
                catch (ArgumentException)
                {
                    threw = true;
                }

                CheckTrue(threw);
                CheckEqual(new[] { 0, 0 }, order);
            }

            public void APositionPastTheCount_ThrowsBeforeAnyItemMoves()
            {
                var items = new[] { 10, 20, 30 };
                var order = new[] { 1, 0, 3 };
                bool threw = false;
                try
                {
                    Sort.ApplyOrder(items, order, 3);
                }
                catch (ArgumentException)
                {
                    threw = true;
                }

                CheckTrue(threw);
                CheckEqual(new[] { 10, 20, 30 }, items);
                CheckEqual(new[] { 1, 0, 3 }, order);
            }

            public void ANegativePosition_ThrowsBeforeAnyItemMoves()
            {
                var items = new[] { 10, 20, 30 };
                var order = new[] { 1, 0, -1 };
                bool threw = false;
                try
                {
                    Sort.ApplyOrder(items, order, 3);
                }
                catch (ArgumentException)
                {
                    threw = true;
                }

                CheckTrue(threw);
                CheckEqual(new[] { 10, 20, 30 }, items);
                CheckEqual(new[] { 1, 0, -1 }, order);
            }

            public void NullItems_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.ApplyOrder<int>(null, new int[3], 3);
            }

            public void NullOrder_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.ApplyOrder(new int[3], null, 3);
            }

            public void NegativeCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.ApplyOrder(new int[3], new int[3], -1);
            }

            public void CountBeyondTheItems_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.ApplyOrder(new int[3], new int[5], 4);
            }

            public void CountBeyondTheOrder_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.ApplyOrder(new int[5], new int[3], 4);
            }

            public static readonly string[] AllocationItems = new string[1000];
            public static readonly int[] AllocationOrder = Enumerable.Range(0, 1000).Reverse().ToArray();
            public static readonly bool Warmed = Warm();

            [UnitTestSharp.IgnoreTest]
            public static bool Warm()
            {
                Sort.ApplyOrder(AllocationItems, AllocationOrder, AllocationItems.Length);
                return true;
            }

            [UnitTestSharp.AllocationTest]
            public void AppliedToReferences_AllocatesNothing()
            {
                Sort.ApplyOrder(AllocationItems, AllocationOrder, AllocationItems.Length);

                CheckNoAllocations();
            }
        }

        public class ItemsTests : UnitTestSharp.TestFixture
        {
            /// <summary>
            /// Puts the first <paramref name="count"/> keys' items in order, with each item's original position as its
            /// value.  Checks the items come out as a stable sort would give them, the order holds those positions, the
            /// keys are untouched, and everything past the count is untouched.
            /// </summary>
            [UnitTestSharp.IgnoreTest]
            public void CheckSorts(int[] keys, int count)
            {
                int[] original = (int[])keys.Clone();
                int[] items = Enumerable.Range(0, keys.Length).ToArray();
                int[] order = UnwrittenOrder(keys.Length + 2);
                int[] expectedOrder = ExpectedOrder(original, count);

                Sort.Items(keys, items, count, order);

                var expectedItems = new List<int>(expectedOrder);
                var expectedOrderWithTail = new List<int>(expectedOrder);
                for (int i = count; i < keys.Length; ++i)
                {
                    expectedItems.Add(i);
                }

                for (int i = count; i < order.Length; ++i)
                {
                    expectedOrderWithTail.Add(Unwritten);
                }

                CheckEqual(expectedItems, items.ToList());
                CheckEqual(expectedOrderWithTail, order.ToList());
                CheckEqual(original, keys);
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckSorts(int[] keys)
            {
                CheckSorts(keys, keys.Length);
            }

            public void ZeroItems_ChangesNothing()
            {
                var keys = new[] { 3, 1, 2 };
                var items = new[] { 0, 1, 2 };
                var order = UnwrittenOrder(3);

                Sort.Items(keys, items, 0, order);

                CheckEqual(new[] { 3, 1, 2 }, keys);
                CheckEqual(new[] { 0, 1, 2 }, items);
                CheckEqual(UnwrittenOrder(3), order);
            }

            public void OneItem_ChangesNothing()
            {
                var keys = new[] { 3, 1, 2 };
                var items = new[] { 0, 1, 2 };
                var order = UnwrittenOrder(3);

                Sort.Items(keys, items, 1, order);

                CheckEqual(new[] { 3, 1, 2 }, keys);
                CheckEqual(new[] { 0, 1, 2 }, items);
                CheckEqual(new[] { 0, Unwritten, Unwritten }, order);
            }

            public void AFewItems_AreSortedByTheirKeys()
            {
                CheckSorts(new[] { 5, 1, 4, 2, 3 });
            }

            public void AFewItemsAlreadyAscending_AreUnchanged()
            {
                CheckSorts(new[] { 1, 2, 2, 5, 9 });
            }

            public void AFewEqualKeys_KeepTheirOrder()
            {
                CheckSorts(new[] { 2, 1, 2, 1, 2, 1 });
            }

            public void EveryBatchSizeWithEqualKeys_KeepsTheirOrder()
            {
                foreach (int distinct in new[] { 1, 2, 3, 5 })
                {
                    for (int count = 2; count <= LargestBatchChecked; ++count)
                    {
                        CheckSorts(Enumerable.Range(0, count).Select(i => (i * 7 + 3) % distinct).ToArray());
                    }
                }
            }

            public void EveryBatchSizeInReverse_IsSorted()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    CheckSorts(Enumerable.Range(0, count).Reverse().ToArray());
                }
            }

            public void EveryBatchSizeAlreadyAscending_IsUnchanged()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    CheckSorts(Enumerable.Range(0, count).ToArray());
                }
            }

            public void EveryBatchSizeWithAnExtremeOutOfPlace_IsSorted()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    int[] keys = Enumerable.Range(0, count).ToArray();
                    keys[count / 2] = int.MinValue;
                    keys[count - 1] = int.MaxValue;
                    keys[0] = int.MaxValue;
                    CheckSorts(keys);
                }
            }

            public void EveryBatchSizeWithNegativeKeys_IsSorted()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    CheckSorts(Enumerable.Range(0, count).Select(i => (i * 37 % 101) - 50).ToArray());
                }
            }

            public void EveryBatchSizeScattered_IsSorted()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    CheckSorts(Scattered(count));
                }
            }

            public void EveryBatchSizeOfReferenceItems_AreMovedWithTheirKeys()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    int[] keys = Scattered(count);
                    string[] items = keys.Select(key => key.ToString()).ToArray();

                    Sort.Items(keys, items, count, new int[count]);

                    CheckEqual(keys.OrderBy(key => key).Select(key => key.ToString()).ToArray(), items);
                }
            }

            public void EveryBatchSizeOfReferenceItemsInReverse_AreMovedWithTheirKeys()
            {
                for (int count = 2; count <= LargestBatchChecked; ++count)
                {
                    int[] keys = Enumerable.Range(0, count).Select(i => count - i).ToArray();
                    string[] items = keys.Select(key => key.ToString()).ToArray();

                    Sort.Items(keys, items, count, new int[count]);

                    CheckEqual(Enumerable.Range(1, count).Select(key => key.ToString()).ToArray(), items);
                }
            }

            public void ManyItemsAlreadyAscending_AreUnchanged()
            {
                CheckSorts(Enumerable.Range(0, 1000).ToArray());
            }

            public void ManyItemsDescending_BecomeAscending()
            {
                CheckSorts(Enumerable.Range(0, 2000).Reverse().ToArray());
            }

            public void ManyScatteredItems_AreSorted()
            {
                CheckSorts(Scattered(5000));
            }

            public void ManyItemsWithManyTies_KeepTheirOrder()
            {
                CheckSorts(Enumerable.Range(0, 5000).Select(i => i * 7919 % 1000).ToArray());
            }

            public void OnlyTheFirstCountItems_AreSorted()
            {
                CheckSorts(Scattered(100), 60);
            }

            public void OnlyTheFirstCountItems_OfAFewAreSorted()
            {
                CheckSorts(Scattered(30), 20);
            }

            public void ItemsThatAreReferences_AreSortedWithTheirKeys()
            {
                var keys = Enumerable.Range(0, 30).Reverse().ToArray();
                var items = keys.Select(key => key.ToString()).ToArray();

                Sort.Items(keys, items, 30, new int[30]);

                CheckEqual(Enumerable.Range(0, 30).Select(key => key.ToString()).ToArray(), items);
            }

            public void NullKeys_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Items(null, new int[3], 3, new int[3]);
            }

            public void NullItems_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Items<int>(new int[3], null, 3, new int[3]);
            }

            public void NullOrder_ThrowsEvenForAFewItems()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.Items(new int[3], new int[3], 3, null);
            }

            public void NegativeCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Items(new int[3], new int[3], -1, new int[3]);
            }

            public void CountBeyondTheKeys_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Items(new int[3], new int[5], 4, new int[5]);
            }

            public void CountBeyondTheItems_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Items(new int[5], new int[3], 4, new int[5]);
            }

            public void CountBeyondTheOrder_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                Sort.Items(new int[5], new int[5], 4, new int[3]);
            }

            public static readonly int[] AllocationSource = Scattered(40000);
            public static readonly int[] AllocationKeys = new int[40000];
            public static readonly string[] AllocationItems = new string[40000];
            public static readonly int[] AllocationOrder = new int[40000];
            public static readonly bool Warmed = Warm();

            [UnitTestSharp.IgnoreTest]
            public static bool Warm()
            {
                foreach (int count in new[] { Sort.UnrolledLimit, Sort.InsertionSortLimit, AllocationKeys.Length })
                {
                    Array.Copy(AllocationSource, AllocationKeys, count);
                    Sort.Items(AllocationKeys, AllocationItems, count, AllocationOrder);
                }

                return true;
            }

            [UnitTestSharp.AllocationTest]
            public void AnInsertionSortedBatch_AllocatesNothing()
            {
                Array.Copy(AllocationSource, AllocationKeys, Sort.InsertionSortLimit);
                Sort.Items(AllocationKeys, AllocationItems, Sort.InsertionSortLimit, AllocationOrder);

                CheckNoAllocations();
            }

            [UnitTestSharp.AllocationTest]
            public void AnUnrolledBatch_AllocatesNothing()
            {
                Array.Copy(AllocationSource, AllocationKeys, Sort.UnrolledLimit);
                Sort.Items(AllocationKeys, AllocationItems, Sort.UnrolledLimit, AllocationOrder);

                CheckNoAllocations();
            }

            [UnitTestSharp.AllocationTest]
            public void ARadixSortedBatch_AllocatesNothing()
            {
                Array.Copy(AllocationSource, AllocationKeys, AllocationKeys.Length);
                Sort.Items(AllocationKeys, AllocationItems, AllocationKeys.Length, AllocationOrder);

                CheckNoAllocations();
            }

            [UnitTestSharp.AllocationTest]
            public void AReversedBatch_AllocatesNothing()
            {
                for (int i = 0; i < Sort.InsertionSortLimit; ++i)
                {
                    AllocationKeys[i] = Sort.InsertionSortLimit - i;
                }

                Sort.Items(AllocationKeys, AllocationItems, Sort.InsertionSortLimit, AllocationOrder);

                CheckNoAllocations();
            }
        }

        public class CopyOfKeysTests : UnitTestSharp.TestFixture
        {
            [UnitTestSharp.IgnoreTest]
            public void CheckCopies(int[] keys)
            {
                var original = (int[])keys.Clone();
                var expected = (int[])keys.Clone();
                Array.Sort(expected);

                int[] sorted = Sort.CopyOfKeys(keys);

                CheckEqual(expected, sorted);
                CheckEqual(original, keys);
                CheckFalse(ReferenceEquals(keys, sorted));
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckCopiesUnsigned(uint[] keys)
            {
                var original = (uint[])keys.Clone();
                var expected = (uint[])keys.Clone();
                Array.Sort(expected);

                uint[] sorted = Sort.CopyOfKeys(keys);

                CheckEqual(expected, sorted);
                CheckEqual(original, keys);
                CheckFalse(ReferenceEquals(keys, sorted));
            }

            public void NoKeys_ReturnsAnEmptyArray()
            {
                CheckCopies(new int[0]);
            }

            public void AFewKeys_AreSortedAndTheOriginalIsUntouched()
            {
                CheckCopies(new[] { 7, 1, 10, 4, 3 });
            }

            public void NegativesAmongAFewKeys_ComeFirst()
            {
                CheckCopies(new[] { 5, -3, 0, -100, 2, -1 });
            }

            public void TheExtremeKeys_AreSorted()
            {
                CheckCopies(new[] { 0, int.MaxValue, -1, int.MinValue, 1 });
            }

            public void DuplicatesAmongAFewKeys_AreKept()
            {
                CheckCopies(new[] { -2, 3, -2, 3, 0 });
            }

            public void EveryKeyWidthAroundTheCrossover_AreSorted()
            {
                for (int span = 1; span <= 32; ++span)
                {
                    foreach (int count in new[] { Sort.RadixCrossover(span) - 1, Sort.RadixCrossover(span),
                        Sort.RadixCrossover(span) + 1 })
                    {
                        CheckCopies(RadixKeySorterTests.Scrambled(count, SpanMask(span)));
                    }
                }
            }

            public void UnsignedEveryKeyWidthAroundTheCrossover_AreSorted()
            {
                for (int span = 1; span <= 32; ++span)
                {
                    foreach (int count in new[] { Sort.RadixCrossover(span) - 1, Sort.RadixCrossover(span),
                        Sort.RadixCrossover(span) + 1 })
                    {
                        CheckCopiesUnsigned(RadixKeySorterTests.Unsigned(
                            RadixKeySorterTests.Scrambled(count, SpanMask(span))));
                    }
                }
            }

            public void NarrowKeysAboveTheAnalyzeLimit_AreSorted()
            {
                CheckCopies(RadixKeySorterTests.Scrambled(Sort.AnalyzeLimit + 10, 0xF));
            }

            public void ManyKeys_AreSortedAndTheOriginalIsUntouched()
            {
                CheckCopies(RadixKeySorterTests.Scrambled(5000, 0x7FFFFFFF));
            }

            public void ManyKeysWithNegatives_ComeFirst()
            {
                int[] keys = RadixKeySorterTests.Scrambled(5000, 0x7FFFFFFF);
                for (int i = 0; i < keys.Length; i += 2)
                {
                    keys[i] = -keys[i];
                }

                CheckCopies(keys);
            }

            public void ManyAlreadyAscending_ReturnACopy()
            {
                CheckCopies(Enumerable.Range(0, 3000).ToArray());
            }

            public void ManyEqualKeys_ReturnACopy()
            {
                CheckCopies(Enumerable.Repeat(7, 3000).ToArray());
            }

            public void UnsignedAFewKeys_AreSorted()
            {
                CheckCopiesUnsigned(new uint[] { 10, 7, 4, 3, 1 });
            }

            public void UnsignedPastTheIntRange_AreSortedAsUnsigned()
            {
                CheckCopiesUnsigned(new uint[] { uint.MaxValue, 1u << 31, 0, int.MaxValue, 5 });
            }

            public void UnsignedManyKeys_AreSortedAndTheOriginalIsUntouched()
            {
                CheckCopiesUnsigned(RadixKeySorterTests.Unsigned(RadixKeySorterTests.Scrambled(5000, -1)));
            }

            public void UnsignedManyAlreadyAscending_ReturnACopy()
            {
                CheckCopiesUnsigned(Enumerable.Range(0, 3000).Select(i => (uint)i * 1000).ToArray());
            }

            public void UnsignedManyEqualKeys_ReturnACopy()
            {
                CheckCopiesUnsigned(Enumerable.Repeat(7u, 3000).ToArray());
            }

            public void NullKeys_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.CopyOfKeys((int[])null);
            }

            public void UnsignedNullKeys_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                Sort.CopyOfKeys((uint[])null);
            }
        }
    }
}