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

namespace Amphora.UnitTests
{
    public class IndexedPriorityQueueTests : UnitTestSharp.TestFixture
    {
        /// <summary>
        /// Makes a queue holding one item per letter of <paramref name="names"/>, with the priorities given in order.
        /// </summary>
        public static IndexedPriorityQueue<int, string> Filled(string names, params int[] priorities)
        {
            var returnMe = new IndexedPriorityQueue<int, string>();
            for (int i = 0; i < names.Length; ++i)
            {
                returnMe.Enqueue(names[i].ToString(), priorities[i]);
            }

            return returnMe;
        }

        public static string Drain(IndexedPriorityQueue<int, string> queue)
        {
            var returnMe = new List<string>();
            while (queue.Count > 0)
            {
                returnMe.Add(queue.Dequeue());
            }

            return string.Join(",", returnMe);
        }

        /// <summary>
        /// Enqueues an item nothing else references, returning a weak reference to it.
        /// </summary>
        // Out of line so the JIT can't keep the item alive in a local of the test itself.
        [System.Runtime.CompilerServices.MethodImpl(System.Runtime.CompilerServices.MethodImplOptions.NoInlining)]
        public static WeakReference EnqueueUnreachableItem(IndexedPriorityQueue<int, object> queue, out int handle)
        {
            var item = new object();
            handle = queue.Enqueue(item, priority: 1);
            return new WeakReference(item);
        }

        public static void CollectGarbage()
        {
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
        }

        public class CtorTests : UnitTestSharp.TestFixture
        {
            public void StartsEmpty()
            {
                CheckEqual(0, new IndexedPriorityQueue<int, string>().Count);
            }

            public void ByDefault_ReservesNothing()
            {
                CheckEqual(0, new IndexedPriorityQueue<int, string>().Capacity);
            }

            public void ReservesTheCapacityAskedFor()
            {
                CheckEqual(10, new IndexedPriorityQueue<int, string>(capacity: 10).Capacity);
            }

            public void NegativeCapacity_Throws()
            {
                CheckThrow(typeof(ArgumentOutOfRangeException));
                new IndexedPriorityQueue<int, string>(capacity: -1);
            }
        }

        public class CountTests : UnitTestSharp.TestFixture
        {
            public void CountsTheItemsHeld()
            {
                CheckEqual(3, Filled("abc", 1, 2, 3).Count);
            }

            public void FallsWhenItemsLeave()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                queue.Enqueue("b", 2);
                int third = queue.Enqueue("c", 3);

                queue.Dequeue();
                CheckEqual(2, queue.Count);
                queue.Remove(third);
                CheckEqual(1, queue.Count);
            }
        }

        public class CapacityTests : UnitTestSharp.TestFixture
        {
            public void WhenFull_DoublesOnTheNextEnqueue()
            {
                var queue = new IndexedPriorityQueue<int, string>(capacity: 2);
                queue.Enqueue("a", 1);
                queue.Enqueue("b", 2);
                CheckEqual(2, queue.Capacity);

                queue.Enqueue("c", 3);

                CheckEqual(4, queue.Capacity);
            }

            public void WhenEmpty_GrowsToFour()
            {
                var queue = new IndexedPriorityQueue<int, string>();

                queue.Enqueue("a", 1);

                CheckEqual(4, queue.Capacity);
            }

            public void IsUnchangedByItemsLeaving()
            {
                var queue = Filled("abcde", 5, 4, 3, 2, 1);
                int capacity = queue.Capacity;

                queue.Dequeue();
                queue.Dequeue();

                CheckEqual(capacity, queue.Capacity);
            }
        }

        public class FirstPriorityTests : UnitTestSharp.TestFixture
        {
            public void IsTheSmallestPriorityHeld()
            {
                CheckEqual(2, Filled("abc", 5, 2, 9).FirstPriority);
            }

            public void IsTheNextPriorityOnceTheFirstLeaves()
            {
                var queue = Filled("abc", 5, 2, 9);

                queue.Dequeue();

                CheckEqual(5, queue.FirstPriority);
            }

            public void LeavesTheItemInTheQueue()
            {
                var queue = Filled("abc", 5, 2, 9);

                CheckEqual(2, queue.FirstPriority);
                CheckEqual(3, queue.Count);
            }

            public void WhenEmpty_Throws()
            {
                CheckThrow(typeof(InvalidOperationException));
                int priority = new IndexedPriorityQueue<int, string>().FirstPriority;
            }
        }

        public class FirstTests : UnitTestSharp.TestFixture
        {
            public void IsTheItemWithTheSmallestPriority()
            {
                CheckEqual("b", Filled("abc", 5, 2, 9).First);
            }

            public void LeavesTheItemInTheQueue()
            {
                var queue = Filled("abc", 5, 2, 9);

                CheckEqual("b", queue.First);
                CheckEqual("b", queue.First);
                CheckEqual(3, queue.Count);
            }

            public void WhenEmpty_Throws()
            {
                CheckThrow(typeof(InvalidOperationException));
                string item = new IndexedPriorityQueue<int, string>().First;
            }
        }

        public class ContainsTests : UnitTestSharp.TestFixture
        {
            public void AHandleFromEnqueue_IsHeld()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);

                CheckTrue(queue.Contains(handle));
            }

            public void AfterDequeue_IsFalse()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);

                queue.Dequeue();

                CheckFalse(queue.Contains(handle));
            }

            public void AfterRemove_IsFalse()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);

                queue.Remove(handle);

                CheckFalse(queue.Contains(handle));
            }

            public void AfterClear_IsFalse()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);

                queue.Clear();

                CheckFalse(queue.Contains(handle));
            }

            public void ANegativeHandle_IsFalse()
            {
                CheckFalse(Filled("a", 1).Contains(-1));
            }

            public void AHandleNeverIssued_IsFalse()
            {
                var queue = new IndexedPriorityQueue<int, string>(capacity: 10);
                queue.Enqueue("a", 1);

                CheckFalse(queue.Contains(1));
                CheckFalse(queue.Contains(10));
            }
        }

        public class PriorityOfTests : UnitTestSharp.TestFixture
        {
            public void IsThePriorityTheItemWasEnqueuedWith()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 5);
                int handle = queue.Enqueue("b", 2);
                queue.Enqueue("c", 9);

                CheckEqual(2, queue.PriorityOf(handle));
            }

            public void IsUnchangedByOtherItemsLeaving()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int last = queue.Enqueue("a", 50);
                for (int i = 0; i < 20; ++i)
                {
                    queue.Enqueue("x", i);
                }

                for (int i = 0; i < 10; ++i)
                {
                    queue.Dequeue();
                }

                CheckEqual(50, queue.PriorityOf(last));
            }

            public void ForAHandleNotHeld_Throws()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);
                queue.Dequeue();

                CheckThrow(typeof(ArgumentException));
                queue.PriorityOf(handle);
            }
        }

        public class EnqueueTests : UnitTestSharp.TestFixture
        {
            public static readonly IndexedPriorityQueue<int, string> AllocationQueue =
                new IndexedPriorityQueue<int, string>(capacity: 8);

            public void ReturnsADifferentHandleForEachItemHeld()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                var handles = new HashSet<int>();

                for (int i = 0; i < 10; ++i)
                {
                    handles.Add(queue.Enqueue("x", i));
                }

                CheckEqual(10, handles.Count);
            }

            public void AfterAnItemLeaves_ReusesItsHandle()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                int second = queue.Enqueue("b", 2);
                queue.Enqueue("c", 3);
                queue.Remove(second);

                int reused = queue.Enqueue("d", 4);

                CheckEqual(second, reused);
                CheckEqual(4, queue.PriorityOf(reused));
            }

            public void ReusesTheHandlesOfSeveralItemsThatLeft()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int first = queue.Enqueue("a", 1);
                int second = queue.Enqueue("b", 2);
                queue.Remove(first);
                queue.Remove(second);

                var handles = new HashSet<int> { queue.Enqueue("c", 3), queue.Enqueue("d", 4) };

                CheckTrue(handles.SetEquals(new[] { first, second }));
            }

            public void PastTheCapacity_KeepsEveryItem()
            {
                var queue = new IndexedPriorityQueue<int, string>(capacity: 2);

                for (int i = 9; i >= 0; --i)
                {
                    queue.Enqueue("n" + i, i);
                }

                CheckEqual("n0,n1,n2,n3,n4,n5,n6,n7,n8,n9", Drain(queue));
            }

            public void PastTheCapacity_KeepsTheHandlesOfItemsHeld()
            {
                var queue = new IndexedPriorityQueue<int, string>(capacity: 2);
                int first = queue.Enqueue("a", 7);
                int second = queue.Enqueue("b", 3);

                for (int i = 0; i < 10; ++i)
                {
                    queue.Enqueue("x", 100 + i);
                }

                CheckEqual(7, queue.PriorityOf(first));
                CheckEqual(3, queue.PriorityOf(second));
            }

            public void EqualPriorities_ComeOutInTheOrderEnqueued()
            {
                var queue = Filled("abcdefghijklmnopqrst", 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1);

                CheckEqual("a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t", Drain(queue));
            }

            public void EqualPriorities_AfterAnItemWasRemovedAndAnotherAdded_StillComeOutInOrder()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                int middle = queue.Enqueue("b", 1);
                queue.Enqueue("c", 1);
                queue.Remove(middle);
                queue.Enqueue("d", 1);
                queue.Enqueue("e", 0);

                CheckEqual("e,a,c,d", Drain(queue));
            }

            public void TimeSpanPriorities_ComeOutEarliestFirst()
            {
                var queue = new IndexedPriorityQueue<TimeSpan, string>();
                queue.Enqueue("late", TimeSpan.FromSeconds(3));
                queue.Enqueue("early", TimeSpan.FromSeconds(1));
                queue.Enqueue("soon", TimeSpan.FromSeconds(2));

                CheckEqual("early", queue.Dequeue());
                CheckEqual("soon", queue.Dequeue());
                CheckEqual("late", queue.Dequeue());
            }

            public void NegativePriorities_ComeOutBeforeZero()
            {
                var queue = Filled("abc", 0, -5, 3);

                CheckEqual("b,a,c", Drain(queue));
            }

            [UnitTestSharp.AllocationTest]
            public void WithinTheCapacity_AllocatesNothing()
            {
                AllocationQueue.Clear();
                AllocationQueue.Enqueue("a", 2);
                AllocationQueue.Enqueue("b", 1);
                AllocationQueue.Dequeue();

                CheckNoAllocations();
                CheckEqual("a", AllocationQueue.First);
            }
        }

        public class DequeueTests : UnitTestSharp.TestFixture
        {
            public void ReturnsTheSmallestPriorityFirst()
            {
                CheckEqual("b,d,e,c,a", Drain(Filled("abcde", 5, 1, 4, 2, 3)));
            }

            public void ReturnsTheItemsOfADescendingRunInAscendingOrder()
            {
                CheckEqual("e,d,c,b,a", Drain(Filled("abcde", 5, 4, 3, 2, 1)));
            }

            public void ManyDistinctPriorities_ComeOutInOrder()
            {
                var queue = new IndexedPriorityQueue<int, int>();
                for (int i = 0; i < 101; ++i)
                {
                    int priority = (i * 37) % 101;
                    queue.Enqueue(priority, priority);
                }

                for (int expected = 0; expected < 101; ++expected)
                {
                    CheckEqual(expected, queue.Dequeue());
                }
            }

            public void ManyItemsWithTiesAndRemovals_ComeOutSortedAndInOrderEnqueued()
            {
                var queue = new IndexedPriorityQueue<int, int>();
                var handles = new int[200];
                for (int i = 0; i < 200; ++i)
                {
                    handles[i] = queue.Enqueue(i, (i * 53) % 29);
                }

                for (int i = 0; i < 200; i += 3)
                {
                    queue.Remove(handles[i]);
                }

                var expected = Enumerable.Range(0, 200).Where(i => i % 3 != 0).OrderBy(i => (i * 53) % 29).ToList();
                var actual = new List<int>();
                while (queue.Count > 0)
                {
                    actual.Add(queue.Dequeue());
                }

                CheckEqual(expected, actual);
            }

            public void EndsTheHandleOfTheItem()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);

                queue.Dequeue();

                CheckFalse(queue.Contains(handle));
            }

            public void LeavesTheOtherHandlesAlone()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                int other = queue.Enqueue("b", 2);
                queue.Enqueue("c", 3);

                queue.Dequeue();

                CheckEqual(2, queue.PriorityOf(other));
            }

            public void ReleasesTheItem()
            {
                var queue = new IndexedPriorityQueue<int, object>();
                int handle;
                WeakReference item = EnqueueUnreachableItem(queue, out handle);
                queue.Dequeue();

                CollectGarbage();

                CheckFalse(item.IsAlive);
            }

            public void WhenEmpty_Throws()
            {
                CheckThrow(typeof(InvalidOperationException));
                new IndexedPriorityQueue<int, string>().Dequeue();
            }

            public static readonly IndexedPriorityQueue<int, string> AllocationQueue =
                new IndexedPriorityQueue<int, string>(capacity: 8);

            [UnitTestSharp.AllocationTest]
            public void ThenEnqueuingAgain_AllocatesNothing()
            {
                AllocationQueue.Clear();
                AllocationQueue.Enqueue("a", 1);
                AllocationQueue.Enqueue("b", 2);
                AllocationQueue.Dequeue();
                AllocationQueue.Enqueue("c", 3);

                CheckNoAllocations();
                CheckEqual("b", AllocationQueue.First);
            }
        }

        public class RemoveTests : UnitTestSharp.TestFixture
        {
            public void ReturnsTheItem()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                int handle = queue.Enqueue("b", 2);

                CheckEqual("b", queue.Remove(handle));
            }

            public void TakesTheItemOutOfTheOrder()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                int handle = queue.Enqueue("b", 2);
                queue.Enqueue("c", 3);

                queue.Remove(handle);

                CheckEqual("a,c", Drain(queue));
            }

            public void OfTheFirstItem_LeavesTheRestInOrder()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);
                queue.Enqueue("b", 2);
                queue.Enqueue("c", 3);

                queue.Remove(handle);

                CheckEqual("b,c", Drain(queue));
            }

            public void OfTheOnlyItem_EmptiesTheQueue()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);

                queue.Remove(handle);

                CheckEqual(0, queue.Count);
            }

            public void OfTheItemInTheLastSlot_LeavesTheRestInOrder()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                queue.Enqueue("b", 2);
                int handle = queue.Enqueue("c", 3);

                queue.Remove(handle);

                CheckEqual("a,b", Drain(queue));
            }

            public void WhenTheReplacementBelongsHigher_LeavesTheRestInOrder()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                queue.Enqueue("b", 10);
                queue.Enqueue("c", 2);
                int removed = queue.Enqueue("d", 11);
                queue.Enqueue("e", 12);
                queue.Enqueue("f", 3);
                queue.Enqueue("g", 4);

                queue.Remove(removed);

                CheckEqual("a,c,f,g,b,e", Drain(queue));
            }

            public void WhenTheReplacementBelongsLower_LeavesTheRestInOrder()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                int removed = queue.Enqueue("b", 2);
                queue.Enqueue("c", 3);
                queue.Enqueue("d", 4);
                queue.Enqueue("e", 5);
                queue.Enqueue("f", 6);
                queue.Enqueue("g", 7);
                queue.Enqueue("h", 8);

                queue.Remove(removed);

                CheckEqual("a,c,d,e,f,g,h", Drain(queue));
            }

            public void AmongEqualPriorities_LeavesTheRestInTheOrderEnqueued()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                queue.Enqueue("a", 1);
                queue.Enqueue("b", 1);
                int handle = queue.Enqueue("c", 1);
                queue.Enqueue("d", 1);
                queue.Enqueue("e", 1);

                queue.Remove(handle);

                CheckEqual("a,b,d,e", Drain(queue));
            }

            public void EndsTheHandleOfTheItem()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);

                queue.Remove(handle);

                CheckFalse(queue.Contains(handle));
            }

            public void LeavesTheOtherHandlesAlone()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int removed = queue.Enqueue("a", 1);
                int other = queue.Enqueue("b", 2);
                int last = queue.Enqueue("c", 3);

                queue.Remove(removed);

                CheckEqual(2, queue.PriorityOf(other));
                CheckEqual(3, queue.PriorityOf(last));
            }

            public void ReleasesTheItem()
            {
                var queue = new IndexedPriorityQueue<int, object>();
                int handle;
                WeakReference item = EnqueueUnreachableItem(queue, out handle);
                queue.Remove(handle);

                CollectGarbage();

                CheckFalse(item.IsAlive);
            }

            public void ForAHandleAlreadyRemoved_Throws()
            {
                var queue = new IndexedPriorityQueue<int, string>();
                int handle = queue.Enqueue("a", 1);
                queue.Remove(handle);

                CheckThrow(typeof(ArgumentException));
                queue.Remove(handle);
            }

            public void ForAHandleNeverIssued_Throws()
            {
                var queue = Filled("a", 1);

                CheckThrow(typeof(ArgumentException));
                queue.Remove(5);
            }

            public void ForANegativeHandle_Throws()
            {
                var queue = Filled("a", 1);

                CheckThrow(typeof(ArgumentException));
                queue.Remove(-1);
            }
        }

        public class ClearTests : UnitTestSharp.TestFixture
        {
            public void EmptiesTheQueue()
            {
                var queue = Filled("abc", 3, 2, 1);

                queue.Clear();

                CheckEqual(0, queue.Count);
            }

            public void OfAnEmptyQueue_ChangesNothing()
            {
                var queue = new IndexedPriorityQueue<int, string>();

                queue.Clear();

                CheckEqual(0, queue.Count);
            }

            public void LeavesTheQueueUsable()
            {
                var queue = Filled("abc", 3, 2, 1);
                queue.Dequeue();

                queue.Clear();
                queue.Enqueue("x", 2);
                queue.Enqueue("y", 1);

                CheckEqual("y,x", Drain(queue));
            }

            public void ReleasesTheItems()
            {
                var queue = new IndexedPriorityQueue<int, object>();
                int handle;
                WeakReference item = EnqueueUnreachableItem(queue, out handle);

                queue.Clear();
                CollectGarbage();

                CheckFalse(item.IsAlive);
            }

            public void KeepsEqualPrioritiesInTheOrderEnqueuedAfterwards()
            {
                var queue = Filled("abc", 1, 1, 1);

                queue.Clear();
                queue.Enqueue("x", 1);
                queue.Enqueue("y", 1);
                queue.Enqueue("z", 1);

                CheckEqual("x,y,z", Drain(queue));
            }
        }
    }
}