using System;
using System.Collections.Generic;
using System.Linq;
using DataStructures.AATree;
using FluentAssertions;
using NUnit.Framework;

namespace DataStructures.Tests
{
    internal class AaTreeTests
    {
        [Test]
        public void Constructor_UseCustomComparer_FormsCorrectTree()
        {
            var tree = new AaTree<int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            tree.GetMax().Should().Be(1);
            tree.GetMin().Should().Be(10);
            tree.GetKeysInOrder().SequenceEqual(new[] { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }).Should().BeTrue();
            Validate(tree.Root);
        }

        [Test]
        public void Add_MultipleKeys_FormsCorrectTree()
        {
            var tree = new AaTree<int>();

            foreach (var elem in new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 })
            {
                tree.Add(elem);
                tree.Count.Should().Be(elem);
                tree.Contains(elem).Should().BeTrue();
            }

            tree.GetKeysInOrder().SequenceEqual(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }).Should().BeTrue();
            tree.GetKeysPostOrder().SequenceEqual(new[] { 1, 3, 2, 5, 7, 10, 9, 8, 6, 4 }).Should().BeTrue();
            Validate(tree.Root);
        }

        [Test]
        public void Add_KeyAlreadyInTree_ThrowsException()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            Assert.Throws<ArgumentException>(() => tree.Add(1));
        }

        [Test]
        public void AddRange_MultipleKeys_FormsCorrectTree()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            tree.Count.Should().Be(10);
            tree.GetKeysInOrder().SequenceEqual(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }).Should().BeTrue();
            tree.GetKeysPostOrder().SequenceEqual(new[] { 1, 3, 2, 5, 7, 10, 9, 8, 6, 4 }).Should().BeTrue();
            Validate(tree.Root);
        }

        [Test]
        public void Remove_MultipleKeys_TreeStillValid()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });

            Remove(4).Should().NotThrow();
            tree.Contains(4).Should().BeFalse();
            tree.Count.Should().Be(9);

            Remove(8).Should().NotThrow();
            tree.Contains(8).Should().BeFalse();
            tree.Count.Should().Be(8);

            Remove(1).Should().NotThrow();
            tree.Contains(1).Should().BeFalse();
            tree.Count.Should().Be(7);

            Validate(tree.Root);

            Action Remove(int x) => () => tree.Remove(x);
        }

        [Test]
        public void Remove_KeyNotInTree_Throws()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });

            Action act = () => tree.Remove(999);
            act.Should().Throw<InvalidOperationException>();
        }

        [Test]
        public void Remove_EmptyTree_Throws()
        {
            var tree = new AaTree<int>();

            Action act = () => tree.Remove(999);
            act.Should().Throw<InvalidOperationException>();
        }

        [Test]
        public void Contains_NonEmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            tree.Contains(6).Should().BeTrue();
            tree.Contains(999).Should().BeFalse();
        }

        [Test]
        public void Contains_EmptyTree_ReturnsFalse()
        {
            var tree = new AaTree<int>();
            tree.Contains(999).Should().BeFalse();
        }

        [Test]
        public void GetMax_NonEmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            tree.GetMax().Should().Be(10);
        }

        [Test]
        public void GetMax_EmptyTree_ThrowsCorrectException()
        {
            var tree = new AaTree<int>();
            Assert.Throws<InvalidOperationException>(() => tree.GetMax());
        }

        [Test]
        public void GetMin_NonEmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            tree.GetMin().Should().Be(1);
        }

        [Test]
        public void GetMin_EmptyTree_ThrowsCorrectException()
        {
            var tree = new AaTree<int>();
            Assert.Throws<InvalidOperationException>(() => tree.GetMin());
        }

        [Test]
        public void GetKeysInOrder_NonEmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            tree.GetKeysInOrder().SequenceEqual(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }).Should().BeTrue();
        }

        [Test]
        public void GetKeysInOrder_EmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.GetKeysInOrder().ToList().Count.Should().Be(0);
        }

        [Test]
        public void GetKeysPreOrder_NonEmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            tree.GetKeysPreOrder().SequenceEqual(new[] { 4, 2, 1, 3, 6, 5, 8, 7, 9, 10 })
                .Should().BeTrue();
        }

        [Test]
        public void GetKeysPreOrder_EmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.GetKeysPreOrder().ToList().Count.Should().Be(0);
        }

        [Test]
        public void GetKeysPostOrder_NonEmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.AddRange(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 });
            tree.GetKeysPostOrder().SequenceEqual(new[] { 1, 3, 2, 5, 7, 10, 9, 8, 6, 4 })
                .Should().BeTrue();
        }

        [Test]
        public void GetKeysPostOrder_EmptyTree_ReturnsCorrectAnswer()
        {
            var tree = new AaTree<int>();
            tree.GetKeysPostOrder().ToList().Count.Should().Be(0);
        }

        /// <summary>
        ///     Checks various properties to determine if the tree is a valid AA Tree.
        ///     Throws exceptions if properties are violated.
        ///     Useful for debugging.
        /// </summary>
        /// <remarks>
        ///     The properties that are checked are:
        ///     <list type="number">
        ///         <item>The level of every leaf node is one.</item>
        ///         <item>The level of every left child is exactly one less than that of its parent.</item>
        ///         <item>The level of every right child is equal to or one less than that of its parent.</item>
        ///         <item>The level of every right grandchild is strictly less than that of its grandparent.</item>
        ///         <item>Every node of level greater than one has two children.</item>
        ///     </list>
        ///     More information: https://en.wikipedia.org/wiki/AA_tree .
        /// </remarks>
        /// <param name="node">The node to check from.</param>
        /// <returns>true if node passes all checks, false otherwise.</returns>
        private static bool Validate<T>(AaTreeNode<T>? node)
        {
            if (node is null)
            {
                return true;
            }

            // Check level == 1 if node if a leaf node.
            var leafNodeCheck = CheckLeafNode(node);

            // Check level of left child is exactly one less than parent.
            var leftCheck = CheckLeftSubtree(node);

            // Check level of right child is equal or one less than parent.
            var rightCheck = CheckRightSubtree(node);

            // Check right grandchild level is less than node.
            var grandchildCheck = CheckRightGrandChild(node);

            // Check if node has two children if not leaf.
            var nonLeafChildrenCheck = CheckNonLeafChildren(node);

            var thisNodeResult = leafNodeCheck && leftCheck && rightCheck;
            thisNodeResult = thisNodeResult && grandchildCheck && nonLeafChildrenCheck;

            return thisNodeResult && Validate(node.Left) && Validate(node.Right);
        }

        /// <summary>
        ///     Checks if node is a leaf, and if so if its level is 1.
        /// </summary>
        /// <param name="node">The node to check.</param>
        /// <returns>true if node passes check, false otherwise.</returns>
        private static bool CheckLeafNode<T>(AaTreeNode<T> node)
        {
            var condition = node.Left is null && node.Right is null && node.Level != 1;
            return !condition;
        }

        /// <summary>
        ///     Checks if left node's level is exactly one less than node's level.
        /// </summary>
        /// <param name="node">The node to check.</param>
        /// <returns>true if node passes check, false otherwise.</returns>
        private static bool CheckLeftSubtree<T>(AaTreeNode<T> node)
        {
            var condition = node.Left is not null && node.Level - node.Left.Level != 1;
            return !condition;
        }

        /// <summary>
        ///     Checks if right node's level is either equal to or one less than node's level.
        /// </summary>
        /// <param name="node">The node to check.</param>
        /// <returns>true if node passes check, false otherwise.</returns>
        private static bool CheckRightSubtree<T>(AaTreeNode<T> node)
        {
            var condition = node.Right is not null &&
                            node.Level - node.Right.Level != 1 &&
                            node.Level != node.Right.Level;
            return !condition;
        }

        /// <summary>
        ///     Checks if right grandchild's (right node's right node) level is less than node.
        /// </summary>
        /// <param name="node">The node to check.</param>
        /// <returns>true if node passes check, false otherwise.</returns>
        private static bool CheckRightGrandChild<T>(AaTreeNode<T> node)
        {
            var condition = node.Right?.Right is not null && node.Right.Level < node.Right.Right.Level;
            return !condition;
        }

        /// <summary>
        ///     Checks if node is not a leaf, and if so if it has two children.
        /// </summary>
        /// <param name="node">The node to check.</param>
        /// <returns>true if node passes check, false otherwise.</returns>
        private static bool CheckNonLeafChildren<T>(AaTreeNode<T> node)
        {
            var condition = node.Level > 1 && (node.Left is null || node.Right is null);
            return !condition;
        }
    }
}
