using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Azimuth.DataStructures;

namespace Azimuth.UnitTests.DataStructures
{
    public class PriorityQueueTests : UnitTestSharp.TestFixture
    {
        public void AddElements()
        {
            var pq = new PriorityQueue<int>();

            pq.Add(1, 2);
            pq.Add(0, 4);
            pq.Add(7, 1);

            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 4),
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(7, 1),
            };

            CheckEqual(expected, pq);
        }

        public void AddElements_Batch()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 4),
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(7, 1),
            };

            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(7, 1),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);

            CheckEqual(expected, pq);
        }

        public void IsEmpty_Empty()
        {
            var pq = new PriorityQueue<int>();

            Check(pq.IsEmpty);
        }

        public void IsEmpty_NotEmpty()
        {
            var pq = new PriorityQueue<int>();
            pq.Add(9, 10);

            CheckFalse(pq.IsEmpty);
        }

        public void RemoveAll_Full()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 2),
                new KeyValuePair<Scalar, int>(0, 1),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);

            pq.RemoveAll(x => x.Value == 1 || x.Value == 2);

            CheckEqual(expected, pq);
        }

        public void Remove_Existing()
        {
            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 2),
                new KeyValuePair<Scalar, int>(0, 1),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);

            pq.Remove(jumbled[0]);
            pq.Remove(jumbled[2]);

            CheckEqual(jumbled[1], pq.First());
        }

        public void PopElements()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 2),
                new KeyValuePair<Scalar, int>(0, 1),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 2),
                new KeyValuePair<Scalar, int>(0, 1),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);

            CheckEqual(expected, pq.PopHighestPriorityElements());
            Check(pq.IsEmpty);
        }

        public void PopElements_Empty()
        {
            var pq = new PriorityQueue<int>();
            
            CheckEqual(new int[] { }, pq.PopHighestPriorityElements());
        }

        public void FuzzyPopElements()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var removedElements = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 2),
                new KeyValuePair<Scalar, int>(Scalar.FuzzyEqualityEpsilon * .49, 1),
                new KeyValuePair<Scalar, int>(Scalar.FuzzyEqualityEpsilon * .99, 4),
            };

            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 2),
                new KeyValuePair<Scalar, int>(Scalar.FuzzyEqualityEpsilon * .49, 1),
                new KeyValuePair<Scalar, int>(Scalar.FuzzyEqualityEpsilon * .99, 4),
                new KeyValuePair<Scalar, int>(Scalar.FuzzyEqualityEpsilon  * 1.49, 7),
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);

            var elements = pq.PopHighestPriorityElements();

            CheckEqual(removedElements, elements);
            CheckEqual(1, pq.Count());
            CheckEqual(7, pq.First().Value);
        }

        public void BatchRemove()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 4),
                new KeyValuePair<Scalar, int>(1, 2),                
            };
 
            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(7, 1),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var toRemove = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(7, 1),
            }; 

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);
            pq.BatchRemove(toRemove);

            CheckEqual(expected, pq);
        }

        public void BatchRemove_RedundantRemove()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 4),
                new KeyValuePair<Scalar, int>(1, 2),                
            };

            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(7, 1),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var toRemove = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(7, 1),
                new KeyValuePair<Scalar, int>(7, 1),
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);
            pq.BatchRemove(toRemove);

            CheckEqual(expected, pq);
        }

        public void BatchRemove_Redundant()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(0, 4),
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(7, 1),
            };

            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(7, 1),
                new KeyValuePair<Scalar, int>(7, 1),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var toRemove = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(7, 1),
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);
            pq.BatchRemove(toRemove);

            CheckEqual(expected, pq);
        }

        public void PopHighestPriorityElement_Empty()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(expected);

            CheckThrow(typeof(Exception));
            var actual = pq.PopHighestPriorityElement();
        }

        public void PopHighestPriorityElement_Basic()
        {
            var expected = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(7, 1),
            };

            var jumbled = new KeyValuePair<Scalar, int>[]
            {
                new KeyValuePair<Scalar, int>(7, 1),
                new KeyValuePair<Scalar, int>(1, 2),
                new KeyValuePair<Scalar, int>(0, 4),
            };

            var pq = new PriorityQueue<int>();
            pq.BatchAdd(jumbled);
            var actual = pq.PopHighestPriorityElement();

            CheckEqual(0, actual.Key);
            CheckEqual(4, actual.Value);

            CheckEqual(expected, pq);
        }
    }
}