using System;
using System.Collections.Generic;

namespace Amphora.UnitTests
{
    using AnyTree = SumTree<int, SumTreeTests.Sums, SumTreeTests.SumsOperations>;

    public class SumTreeTests : UnitTestSharp.TestFixture
    {
        public struct Sums
        {
            public int A;
            public int B;
        }

        public struct SumsOperations : ISumOperations<Sums>
        {
            public Sums Add(Sums left, Sums right)
            {
                return new Sums { A = left.A + right.A, B = left.B + right.B };
            }
        }

        public struct ByA : ISumSelector<Sums>
        {
            public int Select(Sums sum)
            {
                return sum.A;
            }
        }

        public struct ByB : ISumSelector<Sums>
        {
            public int Select(Sums sum)
            {
                return sum.B;
            }
        }

        public class Tree : SumTree<int, Sums, SumsOperations>
        {
            public Tree(int fanout = DefaultFanout, int maxCount = MaxCount)
                : base(fanout, maxCount)
            {
            }
        }

        // Every fourth item adds nothing to A and every third adds one to B, so each search meets runs of items that
        // add nothing.
        public static Sums SumsOf(int item)
        {
            return new Sums { A = item % 4, B = item % 3 == 0 ? 1 : 0 };
        }

        public static int[] Items(int start, int count)
        {
            var returnMe = new int[count];
            for (int i = 0; i < count; ++i)
            {
                returnMe[i] = start + i;
            }

            return returnMe;
        }

        public static Sums[] SumsOfAll(int[] items)
        {
            var returnMe = new Sums[items.Length];
            for (int i = 0; i < items.Length; ++i)
            {
                returnMe[i] = SumsOf(items[i]);
            }

            return returnMe;
        }

        public static Tree TreeOf(int count, int fanout)
        {
            var returnMe = new Tree(fanout);
            for (int i = 0; i < count; ++i)
            {
                returnMe.Append(i, SumsOf(i));
            }

            return returnMe;
        }

        public static void Splice(Tree tree, List<int> model, int index, int removeCount, int[] inserted)
        {
            tree.Splice(index, removeCount, inserted, SumsOfAll(inserted), inserted.Length);
            model.RemoveRange(index, removeCount);
            model.InsertRange(index, inserted);
        }

        public static List<int> Modelled(int count)
        {
            return new List<int>(Items(0, count));
        }

        public static string FirstFindDifference(AnyTree tree, List<int> model, bool byA)
        {
            var prefix = new int[model.Count + 1];
            for (int i = 0; i < model.Count; ++i)
            {
                Sums sum = SumsOf(model[i]);
                prefix[i + 1] = prefix[i] + (byA ? sum.A : sum.B);
            }

            for (int target = -1; target <= prefix[model.Count] + 1; ++target)
            {
                int expected = 0;
                while (expected < model.Count && prefix[expected + 1] <= target)
                {
                    ++expected;
                }

                int position = byA ? tree.Find<ByA>(target, out int remainder) : tree.Find<ByB>(target, out remainder);
                if (position != expected || remainder != target - prefix[expected])
                {
                    return $"find {(byA ? "A" : "B")} {target}: {position} left {remainder}, expected {expected} left "
                        + $"{target - prefix[expected]}";
                }
            }

            return "";
        }

        // Compares the tree with the list it should be, through everything it answers.  Returns what differs first.
        public static string FirstDifference(AnyTree tree, List<int> model, bool searchToo = true)
        {
            try
            {
                tree.Validate();
            }
            catch (InvalidOperationException problem)
            {
                return "invalid: " + problem.Message;
            }

            if (tree.Count != model.Count)
            {
                return $"count {tree.Count}, expected {model.Count}";
            }

            Sums running = default;
            for (int i = 0; i <= model.Count; ++i)
            {
                Sums prefix = tree.PrefixSum(i);
                if (prefix.A != running.A || prefix.B != running.B)
                {
                    return $"prefix sum {i}: {prefix.A}, {prefix.B}, expected {running.A}, {running.B}";
                }

                if (i == model.Count)
                {
                    break;
                }

                if (tree[i] != model[i])
                {
                    return $"item {i}: {tree[i]}, expected {model[i]}";
                }

                Sums own = tree.SumAt(i);
                Sums expectedOwn = SumsOf(model[i]);
                if (own.A != expectedOwn.A || own.B != expectedOwn.B)
                {
                    return $"sum at {i}: {own.A}, {own.B}, expected {expectedOwn.A}, {expectedOwn.B}";
                }

                running = new SumsOperations().Add(running, expectedOwn);
            }

            Sums total = tree.Total;
            if (total.A != running.A || total.B != running.B)
            {
                return $"total {total.A}, {total.B}, expected {running.A}, {running.B}";
            }

            if (!searchToo)
            {
                return "";
            }

            string found = FirstFindDifference(tree, model, byA: true);

            return found != "" ? found : FirstFindDifference(tree, model, byA: false);
        }

        // Tries every splice of every size at every place in trees of several sizes.  Returns what differs first.
        public static string FirstSpliceDifference(int fanout, int[] treeSizes, int[] removeCounts,
            int[] insertedCounts)
        {
            foreach (int treeSize in treeSizes)
            {
                for (int index = 0; index <= treeSize; ++index)
                {
                    foreach (int removeCount in removeCounts)
                    {
                        if (removeCount > treeSize - index)
                        {
                            continue;
                        }

                        foreach (int insertedCount in insertedCounts)
                        {
                            Tree tree = TreeOf(treeSize, fanout);
                            List<int> model = Modelled(treeSize);
                            Splice(tree, model, index, removeCount, Items(1000, insertedCount));
                            string difference = FirstDifference(tree, model, searchToo: false);
                            if (difference != "")
                            {
                                return $"fanout {fanout}, {treeSize} items, splice({index}, {removeCount}, "
                                    + $"{insertedCount}): {difference}";
                            }
                        }
                    }
                }
            }

            return "";
        }

        public class CtorTests : UnitTestSharp.TestFixture
        {
            public void StartsEmpty()
            {
                var tree = new Tree();
                CheckEqual(0, tree.Count);
                CheckEqual(1, tree.Depth);
                CheckEqual(0, tree.Total.A);
                CheckEqual(Tree.DefaultFanout, tree.Fanout);
                CheckEqual("", FirstDifference(tree, new List<int>()));
            }

            public void KeepsTheFanout()
            {
                CheckEqual(7, new Tree(7).Fanout);
            }

            public void AFanoutOfTheMinimum_IsAllowed()
            {
                CheckEqual(Tree.MinimumFanout, new Tree(Tree.MinimumFanout).Fanout);
            }

            public void AFanoutBelowTheMinimum_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                new Tree(Tree.MinimumFanout - 1);
            }

            public void AMaxCountAboveTheCeiling_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                new Tree(maxCount: Tree.MaxCount + 1);
            }

            public void ANegativeMaxCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                new Tree(maxCount: -1);
            }

            public void AMaxCountOfZero_HoldsNothing()
            {
                var tree = new Tree(maxCount: 0);
                CheckThrow(typeof(ArgumentOutOfRangeException));
                tree.Append(1, SumsOf(1));
            }
        }

        public class AppendTests : UnitTestSharp.TestFixture
        {
            public void IntoAnEmptyTree_HoldsTheItem()
            {
                var tree = new Tree();
                tree.Append(7, SumsOf(7));
                CheckEqual("", FirstDifference(tree, new List<int> { 7 }));
            }

            public void FillingANodeAndPastIt_KeepsEveryItem()
            {
                foreach (int fanout in new[] { 4, 5, 16 })
                {
                    CheckEqual("", FirstDifference(TreeOf(fanout, fanout), Modelled(fanout)));
                    CheckEqual("", FirstDifference(TreeOf(fanout + 1, fanout), Modelled(fanout + 1)));
                }
            }

            public void ManyItems_KeepTheTreeBalanced()
            {
                Tree tree = TreeOf(3000, fanout: 4);
                CheckEqual("", FirstDifference(tree, Modelled(3000)));
                CheckTrue(tree.Depth > 3);
            }

            public void ManyItems_AtTheDefaultFanout_KeepTheTreeShallow()
            {
                Tree tree = TreeOf(20000, Tree.DefaultFanout);
                CheckEqual("", FirstDifference(tree, Modelled(20000), searchToo: false));
                CheckTrue(tree.Depth <= 5);
            }
        }

        public class SpliceTests : UnitTestSharp.TestFixture
        {
            public void AtFanoutFour_EverySmallSplice_MatchesAList()
            {
                CheckEqual("", FirstSpliceDifference(fanout: 4, treeSizes: new[] { 0, 1, 3, 4, 5, 9, 16, 17, 30 },
                    removeCounts: new[] { 0, 1, 2, 3, 5, 9, 17, 30 }, insertedCounts: new[] { 0, 1, 2, 3, 5, 9, 17 }));
            }

            public void AtFanoutFive_EverySmallSplice_MatchesAList()
            {
                CheckEqual("", FirstSpliceDifference(fanout: 5, treeSizes: new[] { 0, 2, 5, 6, 11, 26, 33 },
                    removeCounts: new[] { 0, 1, 4, 6, 12, 33 }, insertedCounts: new[] { 0, 1, 4, 6, 12 }));
            }

            public void AtTheDefaultFanout_EverySplice_OfTreesThatFitInTwoNodes_MatchesAList()
            {
                CheckEqual("", FirstSpliceDifference(fanout: 16, treeSizes: new[] { 0, 1, 16, 17 },
                    removeCounts: new[] { 0, 1, 7, 16, 40, 140 }, insertedCounts: new[] { 0, 1, 5, 16, 17, 50, 300 }));
            }

            public void AtTheDefaultFanout_EverySplice_OfSeventyItems_MatchesAList()
            {
                CheckEqual("", FirstSpliceDifference(fanout: 16, treeSizes: new[] { 70 },
                    removeCounts: new[] { 0, 1, 7, 16, 40, 140 }, insertedCounts: new[] { 0, 1, 5, 16, 17, 50, 300 }));
            }

            public void AtTheDefaultFanout_EverySplice_OfAHundredAndFortyItems_InsertingUpToAFewItems_MatchesAList()
            {
                CheckEqual("", FirstSpliceDifference(fanout: 16, treeSizes: new[] { 140 },
                    removeCounts: new[] { 0, 1, 7, 16, 40, 140 }, insertedCounts: new[] { 0, 1, 5 }));
            }

            public void AtTheDefaultFanout_EverySplice_OfAHundredAndFortyItems_InsertingAboutANode_MatchesAList()
            {
                CheckEqual("", FirstSpliceDifference(fanout: 16, treeSizes: new[] { 140 },
                    removeCounts: new[] { 0, 1, 7, 16, 40, 140 }, insertedCounts: new[] { 16, 17 }));
            }

            public void AtTheDefaultFanout_EverySplice_OfAHundredAndFortyItems_InsertingManyItems_MatchesAList()
            {
                CheckEqual("", FirstSpliceDifference(fanout: 16, treeSizes: new[] { 140 },
                    removeCounts: new[] { 0, 1, 7, 16, 40, 140 }, insertedCounts: new[] { 50, 300 }));
            }

            public void InsertingFarMoreThanANodeHolds_BuildsSeveralLevels()
            {
                var tree = new Tree(4);
                List<int> model = Modelled(0);
                Splice(tree, model, 0, 0, Items(0, 1000));
                CheckEqual("", FirstDifference(tree, model));
                CheckTrue(tree.Depth >= 5);
            }

            public void InsertingEnoughToFillARootOfNodes_MakesTwoLevels()
            {
                var tree = new Tree(4);
                List<int> model = Modelled(0);
                Splice(tree, model, 0, 0, Items(0, 12));
                CheckEqual("", FirstDifference(tree, model));
                CheckEqual(2, tree.Depth);
            }

            public void InsertingFarMoreThanANodeHolds_IntoTheMiddle_KeepsTheItemsAroundIt()
            {
                Tree tree = TreeOf(50, 4);
                List<int> model = Modelled(50);
                Splice(tree, model, 25, 0, Items(1000, 2000));
                CheckEqual("", FirstDifference(tree, model));
            }

            public void SplittingAndJoiningNodesOverAndOver_OnOneTree_MatchesAList()
            {
                foreach (int fanout in new[] { 4, 16 })
                {
                    Tree tree = TreeOf(fanout * 6, fanout);
                    List<int> model = Modelled(fanout * 6);
                    for (int round = 0; round < 40; ++round)
                    {
                        int at = round * 7 % model.Count;
                        Splice(tree, model, at, 0, Items(5000 + round * 100, fanout + 1 + round % 3 * fanout));
                        CheckEqual("", FirstDifference(tree, model, searchToo: false));
                        Splice(tree, model, at, fanout + 1 + round % 3 * fanout, new int[0]);
                        CheckEqual("", FirstDifference(tree, model, searchToo: false));
                    }
                }
            }

            public void GrowingAndShrinkingSeveralLevelsOverAndOver_OnOneTree_MatchesAList()
            {
                var tree = new Tree(4);
                List<int> model = Modelled(0);
                for (int round = 0; round < 8; ++round)
                {
                    Splice(tree, model, model.Count / 2, 0, Items(1000 * round, 300));
                    CheckEqual("", FirstDifference(tree, model, searchToo: false));
                    Splice(tree, model, 10, model.Count - 30, new int[0]);
                    CheckEqual("", FirstDifference(tree, model, searchToo: false));
                }
            }

            public void RemovingEverything_LeavesAnEmptyTreeThatTakesItemsAgain()
            {
                Tree tree = TreeOf(200, 4);
                List<int> model = Modelled(200);
                Splice(tree, model, 0, 200, new int[0]);
                CheckEqual("", FirstDifference(tree, model));
                CheckEqual(1, tree.Depth);
                Splice(tree, model, 0, 0, Items(500, 9));
                CheckEqual("", FirstDifference(tree, model));
            }

            public void RemovingAcrossManyNodes_AndPuttingBackFewer_MatchesAList()
            {
                Tree tree = TreeOf(500, 4);
                List<int> model = Modelled(500);
                Splice(tree, model, 17, 400, Items(1000, 3));
                CheckEqual("", FirstDifference(tree, model));
            }

            public void ReplacingAsManyItems_MatchesAList()
            {
                Tree tree = TreeOf(60, 4);
                List<int> model = Modelled(60);
                for (int index = 0; index < 60; index += 7)
                {
                    Splice(tree, model, index, 1, Items(2000 + index, 1));
                }

                CheckEqual("", FirstDifference(tree, model));
            }

            public void ManyEditsAtTheFront_KeepTheTreeBalanced()
            {
                var tree = new Tree(4);
                List<int> model = Modelled(0);
                for (int i = 0; i < 1500; ++i)
                {
                    Splice(tree, model, 0, 0, new[] { i });
                }

                CheckEqual("", FirstDifference(tree, model, searchToo: false));
                CheckTrue(tree.Depth <= 11);
            }

            public void RemovingMostItemsOfAShapelessTree_KeepsItShallow()
            {
                Tree tree = TreeOf(3000, 4);
                List<int> model = Modelled(3000);
                for (int index = 2990; index >= 0; index -= 10)
                {
                    Splice(tree, model, index, 9, new int[0]);
                }

                CheckEqual("", FirstDifference(tree, model, searchToo: false));
                CheckTrue(tree.Depth <= 10);
            }

            public void RemovingFromTheBack_OneItemAtATime_MatchesAList()
            {
                Tree tree = TreeOf(100, 4);
                List<int> model = Modelled(100);
                while (model.Count > 0)
                {
                    Splice(tree, model, model.Count - 1, 1, new int[0]);
                    CheckEqual("", FirstDifference(tree, model, searchToo: false));
                }
            }

            public void RemovingFromTheFront_OneItemAtATime_MatchesAList()
            {
                Tree tree = TreeOf(100, 4);
                List<int> model = Modelled(100);
                while (model.Count > 0)
                {
                    Splice(tree, model, 0, 1, new int[0]);
                    CheckEqual("", FirstDifference(tree, model, searchToo: false));
                }
            }

            public void NothingToDo_ChangesNothing()
            {
                Tree tree = TreeOf(10, 4);
                tree.Splice(4, 0, (int[])null, null, 0);
                CheckEqual("", FirstDifference(tree, Modelled(10)));
            }

            public void OnlyTheFirstInsertedCountItems_AreTaken()
            {
                Tree tree = TreeOf(10, 4);
                List<int> model = Modelled(10);
                int[] items = { 1000, 1001, 1002, 1003 };
                tree.Splice(4, 0, items, SumsOfAll(items), 2);
                model.InsertRange(4, new[] { 1000, 1001 });
                CheckEqual("", FirstDifference(tree, model));
            }

            public void AnIndexPastTheEnd_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(6, 0, (int[])null, null, 0);
            }

            public void ANegativeIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(-1, 0, (int[])null, null, 0);
            }

            public void RemovingMoreThanIsAfterTheIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 3, (int[])null, null, 0);
            }

            public void ANegativeRemoveCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, -1, (int[])null, null, 0);
            }

            public void ANegativeInsertedCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, new[] { 1 }, new[] { SumsOf(1) }, -1);
            }

            public void MoreInsertedItemsThanGiven_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, new[] { 1 }, new[] { SumsOf(1), SumsOf(2) }, 2);
            }

            public void MoreInsertedSumsThanGiven_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, new[] { 1, 2 }, new[] { SumsOf(1) }, 2);
            }

            public void InsertedItemsWithNoItemsGiven_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, null, new[] { SumsOf(1) }, 1);
            }

            public void InsertedItemsWithNoSumsGiven_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, new[] { 1 }, null, 1);
            }

            public void MoreItemsThanATreeCanHold_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, new[] { 1 }, new[] { SumsOf(1) }, Tree.MaxCount);
            }

            public void UpToAnInjectedLimit_Works()
            {
                var tree = new Tree(4, maxCount: 12);
                tree.Splice(0, 0, Items(0, 12), SumsOfAll(Items(0, 12)), 12);
                CheckEqual("", FirstDifference(tree, Modelled(12)));
            }

            public void PastAnInjectedLimit_Throws()
            {
                var tree = new Tree(4, maxCount: 12);
                CheckThrow(typeof(ArgumentOutOfRangeException));
                tree.Splice(0, 0, Items(0, 13), SumsOfAll(Items(0, 13)), 13);
            }

            public void ReplacingItemsPastAnInjectedLimit_Throws()
            {
                var limited = new Tree(4, maxCount: 10);
                limited.Splice(0, 0, Items(0, 8), SumsOfAll(Items(0, 8)), 8);
                limited.Splice(0, 3, Items(0, 5), SumsOfAll(Items(0, 5)), 5);
                CheckEqual(10, limited.Count);
                CheckThrow(typeof(ArgumentOutOfRangeException));
                limited.Splice(0, 3, Items(0, 4), SumsOfAll(Items(0, 4)), 4);
            }
        }

        public class SpliceOfListsTests : UnitTestSharp.TestFixture
        {
            public void MatchesAList()
            {
                foreach (int fanout in new[] { 4, 16 })
                {
                    Tree tree = TreeOf(50, fanout);
                    List<int> model = Modelled(50);
                    int[] inserted = Items(1000, 40);
                    tree.Splice(20, 10, new List<int>(inserted), new List<Sums>(SumsOfAll(inserted)), 40);
                    model.RemoveRange(20, 10);
                    model.InsertRange(20, inserted);
                    CheckEqual("", FirstDifference(tree, model));
                }
            }

            public void OnlyTheFirstInsertedCountItems_AreTaken()
            {
                Tree tree = TreeOf(10, 4);
                var items = new List<int> { 1000, 1001, 1002 };
                tree.Splice(4, 0, items, new List<Sums>(SumsOfAll(items.ToArray())), 2);
                CheckEqual("", FirstDifference(tree, new List<int> { 0, 1, 2, 3, 1000, 1001, 4, 5, 6, 7, 8, 9 }));
            }

            public void NothingToDo_ChangesNothing()
            {
                Tree tree = TreeOf(10, 4);
                tree.Splice(4, 0, (List<int>)null, null, 0);
                CheckEqual("", FirstDifference(tree, Modelled(10)));
            }

            public void MoreInsertedItemsThanGiven_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, new List<int> { 1 }, new List<Sums> { SumsOf(1), SumsOf(2) }, 2);
            }

            public void MoreInsertedSumsThanGiven_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, new List<int> { 1, 2 }, new List<Sums> { SumsOf(1) }, 2);
            }

            public void NoItemsGiven_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, (List<int>)null, new List<Sums> { SumsOf(1) }, 1);
            }

            public void NoSumsGiven_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(3, 0, new List<int> { 1 }, null, 1);
            }

            public void AnIndexPastTheEnd_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Splice(6, 0, new List<int>(), new List<Sums>(), 0);
            }
        }

        public class RemoveRangeTests : UnitTestSharp.TestFixture
        {
            [UnitTestSharp.IgnoreTest]
            public void CheckEveryRange(int fanout)
            {
                foreach (int treeSize in new[] { 0, 1, 4, 5, 13, 40, 70 })
                {
                    for (int index = 0; index <= treeSize; ++index)
                    {
                        for (int removeCount = 0; removeCount <= treeSize - index; ++removeCount)
                        {
                            Tree tree = TreeOf(treeSize, fanout);
                            List<int> model = Modelled(treeSize);
                            tree.RemoveRange(index, removeCount);
                            model.RemoveRange(index, removeCount);
                            string difference = FirstDifference(tree, model, searchToo: false);
                            CheckEqual("", difference == "" ? "" : $"fanout {fanout}, {treeSize} items, remove "
                                + $"({index}, {removeCount}): {difference}");
                        }
                    }
                }
            }

            public void EveryRange_OfSmallTrees_AtFanoutFour_MatchesAList()
            {
                CheckEveryRange(4);
            }

            public void EveryRange_OfSmallTrees_AtFanoutFive_MatchesAList()
            {
                CheckEveryRange(5);
            }

            public void EveryRange_OfSmallTrees_AtTheDefaultFanout_MatchesAList()
            {
                CheckEveryRange(16);
            }

            public void ALongRangeThroughManyLevels_MatchesAList()
            {
                foreach (int fanout in new[] { 4, 16 })
                {
                    Tree tree = TreeOf(6000, fanout);
                    List<int> model = Modelled(6000);
                    tree.RemoveRange(700, 4500);
                    model.RemoveRange(700, 4500);
                    CheckEqual("", FirstDifference(tree, model, searchToo: false));
                }
            }

            public void Everything_LeavesAnEmptyTree()
            {
                Tree tree = TreeOf(500, 4);
                tree.RemoveRange(0, 500);
                CheckEqual("", FirstDifference(tree, new List<int>()));
            }

            public void AnIndexPastTheEnd_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).RemoveRange(6, 0);
            }

            public void MoreThanIsAfterTheIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).RemoveRange(3, 3);
            }

            public void ANegativeCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).RemoveRange(3, -1);
            }
        }

        public class CopyToTests : UnitTestSharp.TestFixture
        {
            public static string FirstCopyDifference(int fanout, int treeSize)
            {
                Tree tree = TreeOf(treeSize, fanout);
                for (int index = 0; index <= treeSize; ++index)
                {
                    for (int copyCount = 0; copyCount <= treeSize - index; ++copyCount)
                    {
                        var items = new List<int>();
                        var sums = new List<Sums>();
                        tree.CopyTo(index, copyCount, items, sums);
                        for (int i = 0; i < copyCount; ++i)
                        {
                            if (items[i] != index + i || sums[i].A != SumsOf(index + i).A
                                || sums[i].B != SumsOf(index + i).B)
                            {
                                return $"fanout {fanout}, {treeSize} items, copy ({index}, {copyCount}): item {i}";
                            }
                        }

                        if (items.Count != copyCount || sums.Count != copyCount)
                        {
                            return $"fanout {fanout}, {treeSize} items, copy ({index}, {copyCount}): "
                                + $"{items.Count} items and {sums.Count} sums";
                        }
                    }
                }

                return "";
            }

            public void EveryRange_AtFanoutFour_MatchesTheItems()
            {
                CheckEqual("", FirstCopyDifference(fanout: 4, treeSize: 60));
            }

            public void EveryRange_AtTheDefaultFanout_MatchesTheItems()
            {
                CheckEqual("", FirstCopyDifference(fanout: 16, treeSize: 90));
            }

            public void ALongRangeThroughManyLevels_MatchesTheItems()
            {
                Tree tree = TreeOf(6000, 4);
                var items = new List<int>();
                var sums = new List<Sums>();
                tree.CopyTo(100, 5500, items, sums);
                CheckEqual(5500, items.Count);
                for (int i = 0; i < 5500; ++i)
                {
                    CheckEqual(100 + i, items[i]);
                }
            }

            public void AddsAfterWhatTheListsHold()
            {
                Tree tree = TreeOf(20, 4);
                var items = new List<int> { -1 };
                var sums = new List<Sums> { new Sums { A = -1, B = -1 } };
                tree.CopyTo(5, 3, items, sums);
                CheckEqual(4, items.Count);
                CheckEqual(-1, items[0]);
                CheckEqual(5, items[1]);
                CheckEqual(SumsOf(7).A, sums[3].A);
            }

            public void CopyingNothing_ChangesNothing()
            {
                var items = new List<int>();
                TreeOf(20, 4).CopyTo(5, 0, items, new List<Sums>());
                CheckEqual(0, items.Count);
            }

            public void AnIndexPastTheEnd_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).CopyTo(6, 0, new List<int>(), new List<Sums>());
            }

            public void MoreThanIsAfterTheIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).CopyTo(3, 3, new List<int>(), new List<Sums>());
            }

            public void ANegativeCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).CopyTo(3, -1, new List<int>(), new List<Sums>());
            }
        }

        public class IndexerTests : UnitTestSharp.TestFixture
        {
            public void ReadsEveryItem_ForwardAndBackward()
            {
                Tree tree = TreeOf(200, 4);
                for (int i = 0; i < 200; ++i)
                {
                    CheckEqual(i, tree[i]);
                }

                for (int i = 199; i >= 0; --i)
                {
                    CheckEqual(i, tree[i]);
                }
            }

            public void ReadsItemsFarApart_AfterEachOther()
            {
                Tree tree = TreeOf(200, 4);
                foreach (int index in new[] { 0, 199, 1, 100, 99, 101, 50, 150, 3 })
                {
                    CheckEqual(index, tree[index]);
                }
            }

            public void ReadsTheNewItems_AfterASplice()
            {
                Tree tree = TreeOf(100, 4);
                CheckEqual(50, tree[50]);
                tree.Splice(10, 0, new[] { 1000, 1001, 1002 }, SumsOfAll(new[] { 1000, 1001, 1002 }), 3);
                CheckEqual(47, tree[50]);
                CheckEqual(1001, tree[11]);
            }

            public void ReadsTheNextItems_AfterARemoval()
            {
                Tree tree = TreeOf(100, 4);
                CheckEqual(50, tree[50]);
                tree.Splice(10, 20, new int[0], new Sums[0], 0);
                CheckEqual(70, tree[50]);
            }

            public void ReadsNothing_AfterClear()
            {
                Tree tree = TreeOf(10, 4);
                CheckEqual(5, tree[5]);
                tree.Clear();
                CheckThrow(typeof(ArgumentOutOfRangeException));
                int unused = tree[5];
            }

            public void AnIndexAtTheCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                int unused = TreeOf(5, 4)[5];
            }

            public void ANegativeIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                int unused = TreeOf(5, 4)[-1];
            }

            public void StringItems_AreReadBack()
            {
                var tree = new SumTree<string, int, Int32SumOperations>(4);
                for (int i = 0; i < 30; ++i)
                {
                    tree.Append("item " + i, i);
                }

                CheckEqual("item 17", tree[17]);
                CheckEqual(17 * 18 / 2, tree.PrefixSum(18));
                CheckEqual(18, tree.Find<Int32SumSelector>(153, out int remainder));
                CheckEqual(0, remainder);
            }
        }

        public class PrefixSumTests : UnitTestSharp.TestFixture
        {
            public void OfNoItems_IsNothing()
            {
                Sums sum = TreeOf(10, 4).PrefixSum(0);
                CheckEqual(0, sum.A);
                CheckEqual(0, sum.B);
            }

            public void OfEveryLength_MatchesTheList()
            {
                foreach (int fanout in new[] { 4, 16 })
                {
                    CheckEqual("", FirstDifference(TreeOf(300, fanout), Modelled(300), searchToo: false));
                }
            }

            public void PastTheCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).PrefixSum(6);
            }

            public void OfANegativeLength_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).PrefixSum(-1);
            }
        }

        public class SumAtTests : UnitTestSharp.TestFixture
        {
            public void ReadsTheSumOfEachItem()
            {
                Tree tree = TreeOf(100, 4);
                for (int i = 0; i < 100; ++i)
                {
                    CheckEqual(SumsOf(i).A, tree.SumAt(i).A);
                    CheckEqual(SumsOf(i).B, tree.SumAt(i).B);
                }
            }

            public void AtTheCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).SumAt(5);
            }

            public void AtANegativeIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).SumAt(-1);
            }
        }

        public class FindTests : UnitTestSharp.TestFixture
        {
            public void ByEitherSum_MatchesTheList_AtEveryTarget()
            {
                foreach (int fanout in new[] { 4, 5, 16 })
                {
                    CheckEqual("", FirstDifference(TreeOf(120, fanout), Modelled(120)));
                }
            }

            public void InAnEmptyTree_FindsNothingAndLeavesTheTarget()
            {
                var tree = new Tree();
                CheckEqual(0, tree.Find<ByA>(9, out int remainder));
                CheckEqual(9, remainder);
            }

            public void PastTheTotal_FindsEveryItemAndLeavesTheRest()
            {
                Tree tree = TreeOf(40, 4);
                int position = tree.Find<ByA>(tree.Total.A + 5, out int remainder);
                CheckEqual(40, position);
                CheckEqual(5, remainder);
            }

            public void ATargetOfZero_PassesTheItemsThatAddNothing()
            {
                var tree = new Tree(4);
                int[] items = { 0, 4, 8, 12, 1, 4 };
                tree.Splice(0, 0, items, SumsOfAll(items), items.Length);
                CheckEqual(4, tree.Find<ByA>(0, out int remainder));
                CheckEqual(0, remainder);
            }

            public void ANegativeTarget_FindsNothing()
            {
                CheckEqual(0, TreeOf(40, 4).Find<ByA>(-3, out int remainder));
                CheckEqual(-3, remainder);
            }
        }

        public class FindLongTests : UnitTestSharp.TestFixture
        {
            public const long Scale = 3000000000L;

            public struct ByAScaled : ILongSumSelector<Sums>
            {
                public long Select(Sums sum)
                {
                    return sum.A * Scale;
                }
            }

            public void MatchesTheIntSearch_AtEveryTarget_OnTotalsPastAnInt()
            {
                foreach (int fanout in new[] { 4, 5, 16 })
                {
                    Tree tree = TreeOf(120, fanout);
                    for (int target = 0; target <= tree.Total.A + 2; ++target)
                    {
                        int expected = tree.Find<ByA>(target, out int expectedRemainder);
                        int position = tree.FindLong<ByAScaled>(target * Scale + 1, out long remainder);
                        CheckEqual(expected, position);
                        CheckEqual(expectedRemainder * Scale + 1, remainder);
                    }
                }
            }

            public void InAnEmptyTree_FindsNothingAndLeavesTheTarget()
            {
                var tree = new Tree();
                CheckEqual(0, tree.FindLong<ByAScaled>(Scale, out long remainder));
                CheckEqual(Scale, remainder);
            }

            public void PastTheTotal_FindsEveryItemAndLeavesTheRest()
            {
                Tree tree = TreeOf(40, 4);
                int position = tree.FindLong<ByAScaled>((tree.Total.A + 5) * Scale, out long remainder);
                CheckEqual(40, position);
                CheckEqual(5 * Scale, remainder);
            }

            public void ATargetOfZero_PassesTheItemsThatAddNothing()
            {
                var tree = new Tree(4);
                int[] items = { 0, 4, 8, 12, 1, 4 };
                tree.Splice(0, 0, items, SumsOfAll(items), items.Length);
                CheckEqual(4, tree.FindLong<ByAScaled>(0, out long remainder));
                CheckEqual(0, remainder);
            }

            public void ANegativeTarget_FindsNothing()
            {
                CheckEqual(0, TreeOf(40, 4).FindLong<ByAScaled>(-3, out long remainder));
                CheckEqual(-3, remainder);
            }
        }

        public class AddToSumTests : UnitTestSharp.TestFixture
        {
            public void ChangesThePrefixSumsAfterTheItem_AndTheSearches()
            {
                foreach (int index in new[] { 0, 1, 17, 63, 99 })
                {
                    Tree tree = TreeOf(100, 4);
                    List<int> model = Modelled(100);
                    int totalBefore = tree.Total.A;
                    tree.AddToSum(index, new Sums { A = 3, B = 2 });
                    Sums before = tree.PrefixSum(index);
                    Sums after = tree.PrefixSum(index + 1);
                    CheckEqual(SumsOf(index).A + 3, after.A - before.A);
                    CheckEqual(SumsOf(index).B + 2, after.B - before.B);
                    CheckEqual(totalBefore + 3, tree.Total.A);
                    CheckEqual(model[index], tree[index]);
                    tree.Validate();
                }
            }

            public void KeepsTheTreeValid_AcrossLaterSplices()
            {
                Tree tree = TreeOf(60, 4);
                tree.AddToSum(30, new Sums { A = 5, B = 5 });
                tree.Splice(20, 25, new int[0], new Sums[0], 0);
                tree.Validate();
                CheckEqual(35, tree.Count);
            }

            public void ANegativeChange_TakesFromTheSum()
            {
                Tree tree = TreeOf(10, 4);
                tree.AddToSum(3, new Sums { A = -3, B = 0 });
                CheckEqual(0, tree.SumAt(3).A);
            }

            public void AtTheCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).AddToSum(5, new Sums());
            }

            public void AtANegativeIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).AddToSum(-1, new Sums());
            }

            public void PastWhatTheSumsHold_Throws()
            {
                var tree = new SumTree<int, int, Int32SumOperations>(4);
                tree.Append(0, int.MaxValue);
                CheckThrow(typeof(OverflowException));
                tree.AddToSum(0, 1);
            }
        }

        public class ReplaceTests : UnitTestSharp.TestFixture
        {
            public void PutsTheItemInPlace_AndAddsTheChangeToTheSums()
            {
                foreach (int index in new[] { 0, 1, 17, 63, 99 })
                {
                    Tree tree = TreeOf(100, 4);
                    int totalBefore = tree.Total.A;
                    Sums before = tree.PrefixSum(index);
                    tree.Replace(index, 5000, new Sums { A = 3, B = 2 });
                    CheckEqual(5000, tree[index]);
                    if (index > 0)
                    {
                        CheckEqual(index - 1, tree[index - 1]);
                    }

                    if (index < 99)
                    {
                        CheckEqual(index + 1, tree[index + 1]);
                    }

                    CheckEqual(before.A, tree.PrefixSum(index).A);
                    CheckEqual(SumsOf(index).A + 3, tree.SumAt(index).A);
                    CheckEqual(SumsOf(index).B + 2, tree.SumAt(index).B);
                    CheckEqual(totalBefore + 3, tree.Total.A);
                    tree.Validate();
                }
            }

            public void ThenReadingBesideIt_StillGivesTheOtherItems()
            {
                Tree tree = TreeOf(100, 4);
                CheckEqual(40, tree[40]);
                tree.Replace(41, 5000, new Sums());
                CheckEqual(40, tree[40]);
                CheckEqual(5000, tree[41]);
                CheckEqual(42, tree[42]);
            }

            public void AtTheCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Replace(5, 1, new Sums());
            }

            public void AtANegativeIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).Replace(-1, 1, new Sums());
            }
        }

        public class ClearTests : UnitTestSharp.TestFixture
        {
            public void DropsEveryItem_AndTakesNewOnes()
            {
                Tree tree = TreeOf(300, 4);
                tree.Clear();
                CheckEqual("", FirstDifference(tree, new List<int>()));
                CheckEqual(1, tree.Depth);
                tree.Append(5, SumsOf(5));
                CheckEqual("", FirstDifference(tree, new List<int> { 5 }));
            }

            public static long BytesToBuild(Tree tree, int count)
            {
                long before = GC.GetAllocatedBytesForCurrentThread();
                for (int i = 0; i < count; ++i)
                {
                    tree.Append(i, SumsOf(i));
                }

                return GC.GetAllocatedBytesForCurrentThread() - before;
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckRefillsMatchAList(int fanout, int firstCount, int secondCount)
            {
                Tree tree = TreeOf(firstCount, fanout);
                tree.Clear(keepNodes: true);
                CheckEqual("", FirstDifference(tree, new List<int>()));
                for (int i = 0; i < secondCount; ++i)
                {
                    tree.Append(i, SumsOf(i));
                }

                CheckEqual("", Described($"{firstCount} items kept, {secondCount} put in",
                    FirstDifference(tree, Modelled(secondCount))));
            }

            public void KeepingNodes_ThenFillingAgain_MatchesAList_AtFanoutFour()
            {
                foreach (int secondCount in new[] { 0, 1, 3, 4, 5, 17, 70, 300, 600 })
                {
                    CheckRefillsMatchAList(4, firstCount: 300, secondCount);
                }
            }

            public void KeepingNodes_ThenFillingAgain_MatchesAList_AtTheDefaultFanout()
            {
                foreach (int secondCount in new[] { 0, 1, 16, 17, 257, 700 })
                {
                    CheckRefillsMatchAList(Tree.DefaultFanout, firstCount: 600, secondCount);
                }
            }

            public void KeepingNodes_OfATreeThatFitsOneNode_ThenFillingAgain_MatchesAList()
            {
                CheckRefillsMatchAList(4, firstCount: 3, secondCount: 40);
            }

            public void KeepingNodes_OfAnEmptyTree_LeavesATreeThatWorks()
            {
                var tree = new Tree(4);
                tree.Clear(keepNodes: true);
                tree.Clear(keepNodes: true);
                CheckEqual("", FirstDifference(tree, new List<int>()));
                tree.Append(5, SumsOf(5));
                CheckEqual("", FirstDifference(tree, new List<int> { 5 }));
            }

            public void KeepingNodes_SeveralTimesBeforeFillingAgain_MatchesAList()
            {
                Tree tree = TreeOf(300, 4);
                tree.Clear(keepNodes: true);
                for (int i = 0; i < 50; ++i)
                {
                    tree.Append(i, SumsOf(i));
                }

                tree.Clear(keepNodes: true);
                for (int i = 0; i < 400; ++i)
                {
                    tree.Append(i, SumsOf(i));
                }

                CheckEqual("", FirstDifference(tree, Modelled(400)));
            }

            public void AfterKeepingNodes_EditsStillMatchAList()
            {
                Tree tree = TreeOf(300, 4);
                tree.Clear(keepNodes: true);
                List<int> model = Modelled(0);
                Splice(tree, model, 0, 0, Items(0, 120));
                Splice(tree, model, 40, 50, Items(500, 7));
                Splice(tree, model, model.Count, 0, Items(700, 90));
                tree.RemoveRange(10, 60);
                model.RemoveRange(10, 60);
                tree.Join(tree.SplitOff(55));
                CheckEqual("", FirstDifference(tree, model));
            }

            public void KeepingNodes_LetsTheTreeBeFilledAgainAllocatingFarLess()
            {
                var fresh = new Tree(4);
                long freshBytes = BytesToBuild(fresh, 5000);
                Tree reused = TreeOf(5000, 4);
                reused.Clear(keepNodes: true);
                long reusedBytes = BytesToBuild(reused, 5000);
                CheckTrue(reusedBytes < freshBytes / 10);
            }

            public void NotKeepingNodes_FillsAgainAsAFreshTreeDoes()
            {
                var fresh = new Tree(4);
                long freshBytes = BytesToBuild(fresh, 5000);
                Tree cleared = TreeOf(5000, 4);
                cleared.Clear();
                CheckTrue(BytesToBuild(cleared, 5000) > freshBytes / 2);
            }

            public void DroppingTheKeptNodes_FillsAgainAsAFreshTreeDoes()
            {
                var fresh = new Tree(4);
                long freshBytes = BytesToBuild(fresh, 5000);
                Tree dropped = TreeOf(5000, 4);
                dropped.Clear(keepNodes: true);
                dropped.DropRetired();
                CheckTrue(BytesToBuild(dropped, 5000) > freshBytes / 2);
            }

            public void ClearingWithoutKeepingNodes_LetsGoOfNodesKeptBefore()
            {
                var fresh = new Tree(4);
                long freshBytes = BytesToBuild(fresh, 5000);
                Tree tree = TreeOf(5000, 4);
                tree.Clear(keepNodes: true);
                tree.Clear();
                CheckTrue(BytesToBuild(tree, 5000) > freshBytes / 2);
            }
        }

        public static Tree TreeOfItems(int start, int count, int fanout)
        {
            var returnMe = new Tree(fanout);
            for (int i = 0; i < count; ++i)
            {
                returnMe.Append(start + i, SumsOf(start + i));
            }

            return returnMe;
        }

        public static string Described(string what, string difference)
        {
            return difference == "" ? "" : what + ": " + difference;
        }

        public class SplitOffTests : UnitTestSharp.TestFixture
        {
            [UnitTestSharp.IgnoreTest]
            public void CheckEveryIndex(int[] counts, int fanout)
            {
                foreach (int count in counts)
                {
                    for (int index = 0; index <= count; ++index)
                    {
                        Tree tree = TreeOf(count, fanout);
                        AnyTree right = tree.SplitOff(index);
                        List<int> model = Modelled(count);
                        CheckEqual("", Described($"{count} items split at {index}, the part kept",
                            FirstDifference(tree, model.GetRange(0, index))));
                        CheckEqual("", Described($"{count} items split at {index}, the part taken",
                            FirstDifference(right, model.GetRange(index, count - index))));
                    }
                }
            }

            public void AtEveryIndex_OfSmallTrees_AtFanoutFour()
            {
                CheckEveryIndex(new[] { 1, 2, 3, 4, 5, 8, 17, 40, 70 }, fanout: 4);
            }

            public void AtEveryIndex_OfSmallTrees_AtFanoutFive()
            {
                CheckEveryIndex(new[] { 1, 5, 6, 26, 27, 60 }, fanout: 5);
            }

            public void AtEveryIndex_OfTreesOfThreeLevels_AtTheDefaultFanout()
            {
                CheckEveryIndex(new[] { 16, 17, 257 }, fanout: Tree.DefaultFanout);
            }

            public void AtTheEnd_TakesNothing_AndLeavesTheTreeAsItWas()
            {
                Tree tree = TreeOf(50, 4);
                AnyTree right = tree.SplitOff(50);
                CheckEqual("", FirstDifference(right, new List<int>()));
                CheckEqual("", FirstDifference(tree, Modelled(50)));
            }

            public void AtTheStart_TakesEveryItem_AndLeavesTheTreeEmptyButUsable()
            {
                Tree tree = TreeOf(50, 4);
                AnyTree right = tree.SplitOff(0);
                CheckEqual("", FirstDifference(right, Modelled(50)));
                CheckEqual("", FirstDifference(tree, new List<int>()));
                tree.Append(9, SumsOf(9));
                CheckEqual("", FirstDifference(tree, new List<int> { 9 }));
            }

            public void AfterItemsWereRead_ReadsTheItemsNowThere()
            {
                Tree tree = TreeOf(100, 4);
                CheckEqual(80, tree[80]);
                AnyTree right = tree.SplitOff(50);
                CheckEqual(80, right[30]);
                CheckEqual(40, tree[40]);
            }

            public void ThePartTaken_TakesFurtherEdits()
            {
                Tree tree = TreeOf(100, 4);
                AnyTree right = tree.SplitOff(37);
                List<int> model = Modelled(100).GetRange(37, 63);
                right.Splice(5, 30, new[] { 500, 501, 502 }, SumsOfAll(new[] { 500, 501, 502 }), 3);
                model.RemoveRange(5, 30);
                model.InsertRange(5, new[] { 500, 501, 502 });
                CheckEqual("", FirstDifference(right, model));
            }

            public void ThePartKept_TakesFurtherEdits()
            {
                Tree tree = TreeOf(100, 4);
                tree.SplitOff(37);
                List<int> model = Modelled(37);
                Splice(tree, model, 10, 20, Items(500, 40));
                CheckEqual("", FirstDifference(tree, model));
            }

            public void ThePartTaken_KeepsTheLimit()
            {
                var tree = new Tree(4, maxCount: 10);
                tree.Join(TreeOfItems(0, 8, 4));
                AnyTree right = tree.SplitOff(4);
                right.Splice(0, 0, Items(500, 6), SumsOfAll(Items(500, 6)), 6);
                CheckEqual(10, right.Count);
                CheckThrow(typeof(ArgumentOutOfRangeException));
                right.Append(9, SumsOf(9));
            }

            public void PastTheCount_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).SplitOff(6);
            }

            public void AtANegativeIndex_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                TreeOf(5, 4).SplitOff(-1);
            }
        }

        public class JoinTests : UnitTestSharp.TestFixture
        {
            [UnitTestSharp.IgnoreTest]
            public void CheckEveryPair(int[] counts, int fanout)
            {
                foreach (int leftCount in counts)
                {
                    foreach (int rightCount in counts)
                    {
                        Tree left = TreeOf(leftCount, fanout);
                        Tree right = TreeOfItems(1000, rightCount, fanout);
                        List<int> model = Modelled(leftCount);
                        model.AddRange(Items(1000, rightCount));
                        left.Join(right);
                        CheckEqual("", Described($"{leftCount} items joined to {rightCount}, the joined tree",
                            FirstDifference(left, model)));
                        CheckEqual("", Described($"{leftCount} items joined to {rightCount}, the tree given",
                            FirstDifference(right, new List<int>())));
                    }
                }
            }

            [UnitTestSharp.IgnoreTest]
            public void CheckSplitAndJoinBack(int count, int fanout)
            {
                for (int index = 0; index <= count; ++index)
                {
                    Tree tree = TreeOf(count, fanout);
                    tree.Join(tree.SplitOff(index));
                    CheckEqual("", Described($"{count} items split at {index} and joined back",
                        FirstDifference(tree, Modelled(count))));
                }
            }

            public void EveryPairOfSizes_AtFanoutFour()
            {
                CheckEveryPair(new[] { 0, 1, 3, 4, 5, 16, 17, 70 }, fanout: 4);
            }

            public void EveryPairOfSizes_AtFanoutFive()
            {
                CheckEveryPair(new[] { 0, 1, 5, 6, 26, 27, 80 }, fanout: 5);
            }

            public void EveryPairOfSizes_AtTheDefaultFanout()
            {
                CheckEveryPair(new[] { 0, 1, 16, 17, 257, 300 }, fanout: Tree.DefaultFanout);
            }

            public void AfterASplitAtEveryIndex_RestoresTheTree_AtFanoutFour()
            {
                CheckSplitAndJoinBack(100, fanout: 4);
            }

            public void AfterASplitAtEveryIndex_RestoresTheTree_AtTheDefaultFanout()
            {
                CheckSplitAndJoinBack(300, fanout: Tree.DefaultFanout);
            }

            public void ManyTimesOverSeamsAllAlongTheTree_KeepsTheTreeFromDeepening()
            {
                Tree tree = TreeOf(2000, 4);
                int depthAtStart = tree.Depth;
                for (int round = 0; round < 1000; ++round)
                {
                    tree.Join(tree.SplitOff(round * 977 % 2000));
                }

                CheckEqual("", FirstDifference(tree, Modelled(2000), searchToo: false));
                CheckEqual(depthAtStart, tree.Depth);
            }

            public void JoinedTree_TakesFurtherEdits()
            {
                Tree tree = TreeOf(40, 4);
                tree.Join(TreeOfItems(1000, 70, 4));
                List<int> model = Modelled(40);
                model.AddRange(Items(1000, 70));
                Splice(tree, model, 30, 20, Items(500, 5));
                Splice(tree, model, 0, 0, Items(600, 30));
                Splice(tree, model, model.Count, 0, Items(700, 30));
                CheckEqual("", FirstDifference(tree, model));
            }

            public void AfterItemsWereRead_ReadsTheItemsNowThere()
            {
                Tree tree = TreeOf(40, 4);
                Tree other = TreeOfItems(1000, 70, 4);
                CheckEqual(39, tree[39]);
                CheckEqual(1000, other[0]);
                tree.Join(other);
                CheckEqual(1069, tree[109]);
                CheckEqual(1000, tree[40]);
                CheckEqual(39, tree[39]);
            }

            public void TheTreeGiven_TakesNewItems()
            {
                Tree tree = TreeOf(40, 4);
                Tree other = TreeOfItems(1000, 70, 4);
                tree.Join(other);
                other.Append(5, SumsOf(5));
                CheckEqual("", FirstDifference(other, new List<int> { 5 }));
            }

            public void ATreeWithADifferentFanout_Throws()
            {
                CheckThrow(typeof(ArgumentException));
                TreeOf(5, 4).Join(TreeOf(5, 5));
            }

            public void RangesTakenOutAndPutBackElsewhere_ManyTimes_LeaveTheTreeNearItsSize()
            {
                Tree tree = TreeOf(20000, 4);
                tree.CountNodes(out int leavesAtStart, out int innerAtStart);
                int depthAtStart = tree.Depth;
                for (int round = 1; round <= 2000; ++round)
                {
                    int start = round * 7919 % 19000;
                    int end = start + round * 104729 % 1000;
                    AnyTree following = tree.SplitOff(end);
                    AnyTree range = tree.SplitOff(start);
                    tree.Join(following);
                    AnyTree rest = tree.SplitOff(round * 6007 % tree.Count);
                    tree.Join(range);
                    tree.Join(rest);
                }

                tree.CountNodes(out int leaves, out int inner);
                tree.Validate();
                CheckEqual(TreeOf(20000, 4).Total.A, tree.Total.A);
                CheckEqual(20000, tree.Count);
                CheckTrue(tree.Depth <= depthAtStart + 5);
                CheckTrue(leaves <= leavesAtStart * 5 / 4);
                CheckTrue(inner <= innerAtStart * 2);
            }

            public void UpToTheLimit_Works()
            {
                var tree = new Tree(4, maxCount: 10);
                tree.Join(TreeOfItems(0, 5, 4));
                tree.Join(TreeOfItems(5, 5, 4));
                CheckEqual("", FirstDifference(tree, Modelled(10)));
            }

            public void PastTheLimit_Throws_AndChangesNeitherTree()
            {
                var tree = new Tree(4, maxCount: 10);
                tree.Join(TreeOfItems(0, 5, 4));
                Tree other = TreeOfItems(5, 6, 4);
                bool threw = false;
                try
                {
                    tree.Join(other);
                }
                catch (ArgumentOutOfRangeException)
                {
                    threw = true;
                }

                CheckTrue(threw);
                CheckEqual("", FirstDifference(tree, Modelled(5)));
                CheckEqual("", FirstDifference(other, new List<int>(Items(5, 6))));
            }

            public void ATreeToItself_Throws()
            {
                Tree tree = TreeOf(5, 4);
                CheckThrow(typeof(ArgumentException));
                tree.Join(tree);
            }
        }

        public class TotalTests : UnitTestSharp.TestFixture
        {
            public void FollowsASplitOff_AfterBeingRead()
            {
                Tree tree = TreeOf(10, 4);
                int before = tree.Total.A;
                AnyTree right = tree.SplitOff(4);
                CheckEqual(SumsOf(0).A + SumsOf(1).A + SumsOf(2).A + SumsOf(3).A, tree.Total.A);
                CheckEqual(before - tree.Total.A, right.Total.A);
            }

            public void FollowsAJoin_AfterBeingRead()
            {
                Tree tree = TreeOf(10, 4);
                Tree other = TreeOfItems(1000, 10, 4);
                int treeBefore = tree.Total.A;
                int otherBefore = other.Total.A;
                tree.Join(other);
                CheckEqual(treeBefore + otherBefore, tree.Total.A);
                CheckEqual(0, other.Total.A);
            }

            public void AddsEveryItem()
            {
                Tree tree = TreeOf(100, 4);
                int expectedA = 0;
                int expectedB = 0;
                for (int i = 0; i < 100; ++i)
                {
                    expectedA += SumsOf(i).A;
                    expectedB += SumsOf(i).B;
                }

                CheckEqual(expectedA, tree.Total.A);
                CheckEqual(expectedB, tree.Total.B);
            }

            public void FollowsAnAppend_AfterBeingRead()
            {
                Tree tree = TreeOf(10, 4);
                int before = tree.Total.A;
                tree.Append(7, SumsOf(7));
                CheckEqual(before + SumsOf(7).A, tree.Total.A);
            }

            public void FollowsASplice_AfterBeingRead()
            {
                Tree tree = TreeOf(10, 4);
                int before = tree.Total.A;
                tree.Splice(2, 3, new[] { 50 }, new[] { SumsOf(50) }, 1);
                CheckEqual(before - SumsOf(2).A - SumsOf(3).A - SumsOf(4).A + SumsOf(50).A, tree.Total.A);
            }

            public void FollowsARemoveRange_AfterBeingRead()
            {
                Tree tree = TreeOf(10, 4);
                int before = tree.Total.A;
                tree.RemoveRange(2, 3);
                CheckEqual(before - SumsOf(2).A - SumsOf(3).A - SumsOf(4).A, tree.Total.A);
            }

            public void FollowsAReplace_AfterBeingRead()
            {
                Tree tree = TreeOf(10, 4);
                int before = tree.Total.A;
                tree.Replace(4, 4, SumsOf(9));
                CheckEqual(before + SumsOf(9).A, tree.Total.A);
            }

            public void FollowsAnAddToSum_AfterBeingRead()
            {
                Tree tree = TreeOf(10, 4);
                int before = tree.Total.A;
                tree.AddToSum(4, SumsOf(9));
                CheckEqual(before + SumsOf(9).A, tree.Total.A);
            }

            public void FollowsAClear_AfterBeingRead()
            {
                Tree tree = TreeOf(10, 4);
                CheckTrue(tree.Total.A != 0);
                tree.Clear();
                CheckEqual(0, tree.Total.A);
            }
        }

        public class CountNodesTests : UnitTestSharp.TestFixture
        {
            public void OfAnEmptyTree_IsOneLeaf()
            {
                new Tree().CountNodes(out int leaves, out int inner);
                CheckEqual(1, leaves);
                CheckEqual(0, inner);
            }

            public void OfATreeThatFitsANode_IsOneLeaf()
            {
                TreeOf(4, 4).CountNodes(out int leaves, out int inner);
                CheckEqual(1, leaves);
                CheckEqual(0, inner);
            }

            public void OfATreeOfTwoLevels_IsItsLeavesUnderOneRoot()
            {
                TreeOf(12, 4).CountNodes(out int leaves, out int inner);
                CheckEqual(4, leaves);
                CheckEqual(1, inner);
            }

            public void OfATallTree_HoldsEveryItemAndHasNodesAboveTheLeaves()
            {
                Tree tree = TreeOf(2000, 4);
                tree.CountNodes(out int leaves, out int inner);
                CheckGreater(leaves * 4, 1999);
                CheckGreater(inner, leaves / 4 - 1);
                CheckTrue(inner < leaves);
            }
        }

        public class DepthTests : UnitTestSharp.TestFixture
        {
            public void GrowsWithTheItems_AndShrinksBack()
            {
                Tree tree = TreeOf(500, 4);
                int tall = tree.Depth;
                CheckTrue(tall >= 4);
                tree.Splice(2, 496, new int[0], new Sums[0], 0);
                CheckEqual(1, tree.Depth);
                CheckEqual("", FirstDifference(tree, new List<int> { 0, 1, 498, 499 }));
            }
        }
    }
}