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

namespace Amphora.UnitTests
{
    public class RadixKeySorterTests : UnitTestSharp.TestFixture
    {
        /// <summary>
        /// Makes keys in no order that all fit in the bits of <paramref name="mask"/>.
        /// </summary>
        public static int[] Scrambled(int count, int mask)
        {
            var returnMe = new int[count];
            uint state = 12345;
            for (int i = 0; i < count; ++i)
            {
                state = unchecked(state * 1664525u + 1013904223u);
                returnMe[i] = (int)(state >> 1 ^ state << 7) & mask;
            }

            return returnMe;
        }

        public static uint[] Unsigned(int[] keys)
        {
            return keys.Select(key => (uint)key).ToArray();
        }

        public class SortTests : 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);

                sorter.Sort(keys, count);

                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);

                sorter.Sort(keys, count);

                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(Scrambled(10, 0xFFFF));
            }

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

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

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

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

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

            public void AllEqual_AreUnchanged()
            {
                CheckSorts(Enumerable.Repeat(7, 3000).ToArray());
            }

            public void ManyDuplicates_AreSorted()
            {
                CheckSorts(Scrambled(3000, 0x7));
            }

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

                CheckSorts(keys);
            }

            public void OnlyNegativeKeys_AreSorted()
            {
                CheckSorts(Scrambled(3000, 0x7FFFFFFF).Select(key => -key - 1).ToArray());
            }

            public void TheExtremeKeys_AreSorted()
            {
                var keys = new int[3000];
                for (int i = 0; i < keys.Length; ++i)
                {
                    keys[i] = new[] { int.MaxValue, int.MinValue, 0, -1, 1 }[i % 5];
                }

                CheckSorts(keys);
            }

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

            public void KeysDifferingOnlyInTheLowBits_AreSorted()
            {
                CheckSorts(Scrambled(3000, 0xFF));
            }

            public void KeysDifferingInTwoDigits_AreSorted()
            {
                CheckSorts(Scrambled(3000, 0xFFFF));
            }

            public void KeysDifferingOnlyInHighBits_AreSorted()
            {
                CheckSorts(Scrambled(3000, 0x00F00000));
            }

            public void KeysWhoseMiddleDigitNeverDiffers_AreSorted()
            {
                CheckSorts(Scrambled(3000, unchecked((int)0xF000000F)));
            }

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

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

            public void AfterABiggerBatch_ASmallerOneIsSorted()
            {
                var sorter = new RadixKeySorter();
                CheckSorts(sorter, Scrambled(20000, 0x7FFFFFFF), 20000);

                CheckSorts(sorter, Scrambled(2000, 0x7FFFFFFF), 2000);
            }

            public void AfterASmallerBatch_ABiggerOneIsSorted()
            {
                var sorter = new RadixKeySorter();
                CheckSorts(sorter, Scrambled(2000, 0x7FFFFFFF), 2000);

                CheckSorts(sorter, Scrambled(20000, 0x7FFFFFFF), 20000);
            }

            public void ArraysLongerThanTheCount_ReuseTheSpareSpace()
            {
                var sorter = new RadixKeySorter();
                CheckSorts(sorter, Scrambled(5000, 0x7FFFFFFF), 4000);

                CheckSorts(sorter, Scrambled(5000, 0x7FFFFFFF), 3000);
            }

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

            public void UnsignedKeysAcrossTheWholeRange_AreSorted()
            {
                CheckSortsUnsigned(Unsigned(Scrambled(20000, -1)));
            }

            public void UnsignedTheLargestKeys_AreSorted()
            {
                var keys = new uint[3000];
                for (int i = 0; i < keys.Length; ++i)
                {
                    keys[i] = new uint[] { uint.MaxValue, 0u, int.MaxValue, 1u << 31 }[i % 4];
                }

                CheckSortsUnsigned(keys);
            }

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

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

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

            /// <summary>
            /// Sorts keys with the bits they differ in found by <see cref="RadixKeySorter.FindDifferingBits"/>.
            /// </summary>
            [UnitTestSharp.IgnoreTest]
            public void CheckSortsGivenBits(RadixKeySorter sorter, int[] keys, int count)
            {
                var expected = (int[])keys.Clone();
                Array.Sort(expected, 0, count);
                int low;
                int high;
                bool anyNegative;
                RadixKeySorter.FindDifferingBits(keys, count, out low, out high, out anyNegative);

                sorter.Sort(keys, count, low, high, anyNegative);

                CheckEqual(expected, keys);
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckSortsUnsignedGivenBits(RadixKeySorter sorter, uint[] keys, int count)
            {
                var expected = (uint[])keys.Clone();
                Array.Sort(expected, 0, count);
                int low;
                int high;
                bool anyNegative;
                RadixKeySorter.FindDifferingBits((int[])(object)keys, count, out low, out high, out anyNegative);

                sorter.Sort(keys, count, low, high);

                CheckEqual(expected, keys);
            }

            public void GivenTheirBits_ManyKeysAreSorted()
            {
                CheckSortsGivenBits(new RadixKeySorter(), Scrambled(3000, 0x7FFFFFFF), 3000);
            }

            public void GivenTheirBits_AFewKeysAreSorted()
            {
                CheckSortsGivenBits(new RadixKeySorter(), Scrambled(10, 0xFFFF), 10);
            }

            public void GivenTheirBits_KeysInTheMiddleBitsAreSorted()
            {
                CheckSortsGivenBits(new RadixKeySorter(), Scrambled(3000, 0x00FF0000), 3000);
            }

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

                CheckSortsGivenBits(new RadixKeySorter(), keys, 3000);
            }

            public void GivenTheirBits_OnlyTheFirstCountAreSorted()
            {
                CheckSortsGivenBits(new RadixKeySorter(), Scrambled(4000, 0x7FFFFFFF), 3000);
            }

            public void GivenMoreBitsThanTheyDifferIn_KeysAreStillSorted()
            {
                int[] keys = Scrambled(3000, 0xFF);
                var expected = (int[])keys.Clone();
                Array.Sort(expected);

                new RadixKeySorter().Sort(keys, keys.Length, 0, 32, true);

                CheckEqual(expected, keys);
            }

            public void GivenNoBitsAndNoKeys_ChangesNothing()
            {
                var keys = new[] { 3, 1, 2 };

                new RadixKeySorter().Sort(keys, 0, 0, 0, false);

                CheckEqual(new[] { 3, 1, 2 }, keys);
            }

            public void GivenTheirBits_UnsignedKeysAreSorted()
            {
                CheckSortsUnsignedGivenBits(new RadixKeySorter(), Unsigned(Scrambled(3000, -1)), 3000);
            }

            public void GivenTheirBits_UnsignedKeysInTheMiddleBitsAreSorted()
            {
                CheckSortsUnsignedGivenBits(new RadixKeySorter(), Unsigned(Scrambled(3000, 0x00FF0000)), 3000);
            }

            public void GivenTheirBits_UnsignedOnlyTheFirstCountAreSorted()
            {
                CheckSortsUnsignedGivenBits(new RadixKeySorter(), Unsigned(Scrambled(4000, -1)), 3000);
            }

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

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

            public void GivenBits_CountBeyondTheKeysThrows()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                new RadixKeySorter().Sort(new int[3], 4, 0, 32, false);
            }

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

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

            public void GivenBits_UnsignedAnEndBeyondAKeyThrows()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                new RadixKeySorter().Sort(new uint[3], 3, 0, 33);
            }

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

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

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

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

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

            public static readonly int[] AllocationSource = 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);
                returnMe.Sort(AllocationKeys, 5000);
                return returnMe;
            }

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

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

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

                int[] sorted = new RadixKeySorter().SortedCopy(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 = new RadixKeySorter().SortedCopy(keys);

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

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

            public void AFewKeys_AreSortedAndTheOriginalIsUntouched()
            {
                CheckCopies(Scrambled(10, 0xFFFF));
            }

            public void ManyKeys_AreSortedAndTheOriginalIsUntouched()
            {
                CheckCopies(Scrambled(20000, 0x7FFFFFFF));
            }

            public void ManyKeysThatTakeOnePass_AreSorted()
            {
                CheckCopies(Scrambled(3000, 0xFF));
            }

            public void ManyKeysThatTakeTwoPasses_AreSorted()
            {
                CheckCopies(Scrambled(3000, 0xFFFF));
            }

            public void ManyKeysThatTakeThreePasses_AreSorted()
            {
                CheckCopies(Scrambled(3000, 0x7FFFFFFF));
            }

            public void OneKey_ReturnsACopy()
            {
                CheckCopies(new[] { 4 });
            }

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

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

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

                CheckCopies(keys);
            }

            public void UnsignedKeysPastTheIntRange_AreSortedAsUnsigned()
            {
                CheckCopiesUnsigned(Unsigned(Scrambled(3000, -1)));
            }

            public void UnsignedAFewKeys_AreSorted()
            {
                CheckCopiesUnsigned(Unsigned(Scrambled(10, -1)));
            }

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

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

            public void UnsignedKeysThatTakeOnePass_AreSorted()
            {
                CheckCopiesUnsigned(Unsigned(Scrambled(3000, 0xFF)));
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckCopiesGivenBits(int[] keys)
            {
                var original = (int[])keys.Clone();
                var expected = (int[])keys.Clone();
                Array.Sort(expected);
                int low = 0;
                int high = 0;
                bool anyNegative = false;
                if (keys.Length > 1)
                {
                    RadixKeySorter.FindDifferingBits(keys, keys.Length, out low, out high, out anyNegative);
                }

                int[] sorted = new RadixKeySorter().SortedCopy(keys, low, high, anyNegative);

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

            [UnitTestSharp.IgnoreTest]
            public void CheckCopiesUnsignedGivenBits(uint[] keys)
            {
                var original = (uint[])keys.Clone();
                var expected = (uint[])keys.Clone();
                Array.Sort(expected);
                int low = 0;
                int high = 0;
                if (keys.Length > 1)
                {
                    bool anyNegative;
                    RadixKeySorter.FindDifferingBits((int[])(object)keys, keys.Length, out low, out high,
                        out anyNegative);
                }

                uint[] sorted = new RadixKeySorter().SortedCopy(keys, low, high);

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

            public void GivenTheirBits_ManyKeysAreSortedAndTheOriginalIsUntouched()
            {
                CheckCopiesGivenBits(Scrambled(3000, 0x7FFFFFFF));
            }

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

                CheckCopiesGivenBits(keys);
            }

            public void GivenTheirBits_EqualKeysReturnACopy()
            {
                CheckCopiesGivenBits(Enumerable.Repeat(7, 3000).ToArray());
            }

            public void GivenTheirBits_NoKeysReturnsAnEmptyArray()
            {
                CheckCopiesGivenBits(new int[0]);
            }

            public void GivenTheirBits_OneKeyReturnsACopy()
            {
                CheckCopiesGivenBits(new[] { 4 });
            }

            public void GivenTheirBits_UnsignedKeysAreSortedAndTheOriginalIsUntouched()
            {
                CheckCopiesUnsignedGivenBits(Unsigned(Scrambled(3000, -1)));
            }

            public void GivenTheirBits_UnsignedEqualKeysReturnACopy()
            {
                CheckCopiesUnsignedGivenBits(Enumerable.Repeat(7u, 3000).ToArray());
            }

            public void GivenTheirBits_UnsignedOneKeyReturnsACopy()
            {
                CheckCopiesUnsignedGivenBits(new uint[] { 4 });
            }

            public void GivenBits_NullKeysThrow()
            {
                CheckThrow(typeof(ArgumentNullException));
                new RadixKeySorter().SortedCopy((int[])null, 0, 0, false);
            }

            public void GivenBits_UnsignedNullKeysThrow()
            {
                CheckThrow(typeof(ArgumentNullException));
                new RadixKeySorter().SortedCopy((uint[])null, 0, 0);
            }

            public void GivenBits_AStartBelowZeroThrows()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                new RadixKeySorter().SortedCopy(new int[3], -1, 4, false);
            }

            public void GivenBits_UnsignedAnEndBeforeTheStartThrows()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                new RadixKeySorter().SortedCopy(new uint[3], 5, 4);
            }

            public void NullKeys_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                new RadixKeySorter().SortedCopy((int[])null);
            }

            public void UnsignedNullKeys_Throws()
            {
                CheckThrow(typeof(ArgumentNullException));
                new RadixKeySorter().SortedCopy((uint[])null);
            }
        }

        public class CheckBitsTests : UnitTestSharp.TestFixture
        {
            public void EveryRangeWithinAKey_IsAccepted()
            {
                for (int low = 0; low <= 32; ++low)
                {
                    for (int high = low; high <= 32; ++high)
                    {
                        RadixKeySorter.CheckBits(low, high);
                    }
                }
            }

            public void ALowBelowZero_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                RadixKeySorter.CheckBits(-1, 5);
            }

            public void ALowBeyondAKey_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                RadixKeySorter.CheckBits(33, 33);
            }

            public void AHighBeforeTheLow_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                RadixKeySorter.CheckBits(5, 4);
            }

            public void AHighBeyondAKey_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                RadixKeySorter.CheckBits(0, 33);
            }
        }

        public class FindDifferingBitsTests : UnitTestSharp.TestFixture
        {
            [UnitTestSharp.IgnoreTest]
            public void CheckFinds(int[] keys, int count, int expectedLow, int expectedHigh, bool expectedNegative)
            {
                int low;
                int high;
                bool anyNegative;

                RadixKeySorter.FindDifferingBits(keys, count, out low, out high, out anyNegative);

                CheckEqual(expectedLow, low);
                CheckEqual(expectedHigh, high);
                CheckEqual(expectedNegative, anyNegative);
            }

            public void EqualKeys_DifferInNoBits()
            {
                CheckFinds(new[] { 5, 5, 5 }, 3, 0, 0, false);
            }

            public void KeysDifferingInTheLowBits_GiveThatRange()
            {
                CheckFinds(new[] { 4, 5, 6 }, 3, 0, 2, false);
            }

            public void KeysDifferingOnlyInTheMiddle_GiveThatRange()
            {
                CheckFinds(new[] { 0x100, 0x300, 0x200 }, 3, 8, 10, false);
            }

            public void KeysDifferingInTheTopBit_ReachBitThirtyOne()
            {
                CheckFinds(new[] { 0, 1 << 30 }, 2, 30, 31, false);
            }

            public void ANegativeFirstKey_IsNegative()
            {
                CheckFinds(new[] { -1, -1 }, 2, 0, 0, true);
            }

            public void ANegativeLaterKey_IsNegative()
            {
                CheckFinds(new[] { 1, 2, -3 }, 3, 0, 32, true);
            }

            public void OnlyTheFirstCountKeysAreLookedAt()
            {
                CheckFinds(new[] { 1, 3, -1 }, 2, 1, 2, false);
            }

            public void AWholeArray_IsLookedAtToItsEnd()
            {
                CheckFinds(new[] { 1, 3, 0x10 }, 3, 0, 5, false);
            }
        }

        public class ChoosePassesTests : UnitTestSharp.TestFixture
        {
            public void OneBit_TakesOnePass()
            {
                CheckEqual(1, RadixKeySorter.ChoosePasses(span: 1, count: 100000));
            }

            public void ADigitsWorthOfBits_TakesOnePass()
            {
                CheckEqual(1, RadixKeySorter.ChoosePasses(span: 8, count: 100000));
            }

            public void MoreBitsThanADigit_TakeMorePasses()
            {
                CheckTrue(RadixKeySorter.ChoosePasses(span: 31, count: 100000) >= 3);
            }

            public void NeverMoreBitsThanADigitCanHold_InAPass()
            {
                for (int span = 1; span <= 32; ++span)
                {
                    int passes = RadixKeySorter.ChoosePasses(span, count: 5000);

                    CheckTrue((span + passes - 1) / passes <= RadixKeySorter.MaxDigitBits);
                }
            }

            public void FewKeys_PreferNarrowerDigitsToClearingBigBuckets()
            {
                int fewKeys = RadixKeySorter.ChoosePasses(span: 16, count: 50);
                int manyKeys = RadixKeySorter.ChoosePasses(span: 16, count: 5000000);

                CheckTrue(fewKeys > manyKeys);
            }
        }

        public class FlipSignsTests : UnitTestSharp.TestFixture
        {
            public void SwapsWhichKeysSortFirst()
            {
                var keys = new[] { -1, 1 };

                RadixKeySorter.FlipSigns(keys, 2);

                CheckEqual(new[] { int.MaxValue, int.MinValue + 1 }, keys);
            }

            public void TwiceRestoresTheKeys()
            {
                int[] keys = Scrambled(100, -1);
                int[] original = (int[])keys.Clone();

                RadixKeySorter.FlipSigns(keys, 100);
                RadixKeySorter.FlipSigns(keys, 100);

                CheckEqual(original, keys);
            }

            public void OnlyTheFirstCountKeysChange()
            {
                var keys = new[] { 0, 0, 0 };

                RadixKeySorter.FlipSigns(keys, 2);

                CheckEqual(new[] { int.MinValue, int.MinValue, 0 }, keys);
            }
        }

        public class ClearCountsTests : UnitTestSharp.TestFixture
        {
            public void SetsEveryCountToZero()
            {
                var counts = new[] { 3, 1, 4, 1, 5 };

                RadixKeySorter.ClearCounts(counts);

                CheckEqual(new[] { 0, 0, 0, 0, 0 }, counts);
            }
        }

        public class BucketsForTests : UnitTestSharp.TestFixture
        {
            public void HasOneBucketForEachValueOfTheDigit()
            {
                var cache = new int[RadixKeySorter.MaxDigitBits + 1][];

                CheckEqual(64, RadixKeySorter.BucketsFor(cache, 6).Length);
                CheckEqual(2048, RadixKeySorter.BucketsFor(cache, 11).Length);
            }

            public void AskedAgain_ReturnsTheSameCounts()
            {
                var cache = new int[RadixKeySorter.MaxDigitBits + 1][];
                int[] first = RadixKeySorter.BucketsFor(cache, 5);

                CheckTrue(ReferenceEquals(first, RadixKeySorter.BucketsFor(cache, 5)));
            }

            public void ForDifferentDigitSizes_ReturnsDifferentCounts()
            {
                var cache = new int[RadixKeySorter.MaxDigitBits + 1][];

                CheckFalse(ReferenceEquals(RadixKeySorter.BucketsFor(cache, 5), RadixKeySorter.BucketsFor(cache, 6)));
            }
        }

        public class StartOffsetsTests : UnitTestSharp.TestFixture
        {
            public void TurnsCountsIntoWhereEachBucketStarts()
            {
                var counts = new[] { 2, 0, 3, 1 };

                RadixKeySorter.StartOffsets(counts);

                CheckEqual(new[] { 0, 2, 2, 5 }, counts);
            }
        }

        public class CountDigitsTests : UnitTestSharp.TestFixture
        {
            public void CountsTheKeysInEachBucketOfTheDigit()
            {
                var counts = new int[4];

                RadixKeySorter.CountDigits(new[] { 0, 1, 1, 2, 3, 3, 3 }, 7, counts, shift: 0, shiftedMask: 3);

                CheckEqual(new[] { 1, 2, 1, 3 }, counts);
            }

            public void LooksAtTheDigitAtTheShift()
            {
                var counts = new int[4];

                RadixKeySorter.CountDigits(new[] { 0x4, 0x8, 0xC, 0x0 }, 4, counts, shift: 2, shiftedMask: 3 << 2);

                CheckEqual(new[] { 1, 1, 1, 1 }, counts);
            }

            public void OnlyTheFirstCountKeysAreCounted()
            {
                var counts = new int[4];

                RadixKeySorter.CountDigits(new[] { 0, 1, 2, 3 }, 2, counts, shift: 0, shiftedMask: 3);

                CheckEqual(new[] { 1, 1, 0, 0 }, counts);
            }

            public void OfAll_CountsEveryKey()
            {
                var counts = new int[4];

                RadixKeySorter.CountDigitsOfAll(new[] { 0, 1, 1, 2, 3, 3, 3 }, counts, shift: 0, shiftedMask: 3);

                CheckEqual(new[] { 1, 2, 1, 3 }, counts);
            }
        }

        public class ScatterTests : UnitTestSharp.TestFixture
        {
            public void PutsEachKeyWhereItsBucketStartsAndKeepsTheOrderInABucket()
            {
                var target = new int[5];
                var starts = new[] { 0, 1, 3, 4 };

                RadixKeySorter.Scatter(new[] { 1, 0, 1, 3, 2 }, target, 5, starts, shift: 0, shiftedMask: 3);

                CheckEqual(new[] { 0, 1, 1, 2, 3 }, target);
            }

            public void OnlyTheFirstCountKeysMove()
            {
                var target = new int[3];
                var starts = new[] { 0, 1, 2, 2 };

                RadixKeySorter.Scatter(new[] { 1, 0, 2, 3 }, target, 3, starts, shift: 0, shiftedMask: 3);

                CheckEqual(new[] { 0, 1, 2 }, target);
            }

            public void OfAll_MovesEveryKey()
            {
                var target = new int[5];
                var starts = new[] { 0, 1, 3, 4 };

                RadixKeySorter.ScatterAll(new[] { 1, 0, 1, 3, 2 }, target, starts, shift: 0, shiftedMask: 3);

                CheckEqual(new[] { 0, 1, 1, 2, 3 }, target);
            }
        }
    }
}