using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Assessment3Part1
{
    internal class AVLBinaryNode : BinaryNode
    {
        public int height;
        public new AVLBinaryNode left;
        public new AVLBinaryNode right;


        public AVLBinaryNode(int value) : base(value)
        {

            height = 0;
        }
    }
    public class AVLBinaryGraph : BinaryGraph
    {
        private AVLBinaryNode root;


        public new void Insert(int value)
        {
            root = InsertCheck(root, value);
        }





        private AVLBinaryNode InsertCheck(AVLBinaryNode node, int value)
        {
            if (node == null)
            {
                node = new AVLBinaryNode(value);
            }
            else if (value < node.value)
            {
                node.left = InsertCheck(node.left, value);
            }
            else
            {
                node.right = InsertCheck(node.right, value);
            }
            node.height = 1 + (Math.Max(Height(node.left), Height(node.right)));

            //balancing

            int balance = GetHeightDifference(node);
            if(balance > 1 && value < node.left.value)
            {
                return RotateRight(node);
            }
            if (balance < -1 && value > node.right.value)
            {
                return RotateLeft(node);
            }
            if (balance > 1 && value >= node.left.value)
            {
                node.left = RotateLeft(node.left);
                return RotateRight(node);
            }
            if (balance < -1 && value <= node.right.value)
            {
                node.right = RotateRight(node.right);
                return RotateLeft(node);
            }
            return node;
        }


        private int Height(AVLBinaryNode node)
        {
            if (node == null)
            {
                return 0;
            }

            return node.height;

        }


        private int GetHeightDifference(AVLBinaryNode node)
        {
            if (node == null)
            {
                return 0;
            }
            return Height(node.left) - Height(node.right);

        }

        private AVLBinaryNode RotateRight(AVLBinaryNode parent)
        {
            AVLBinaryNode pivot = parent.left;
            AVLBinaryNode e = pivot.right;

            parent.left = e;
            pivot.right = parent;

            parent.height = 1 + Math.Max(Height(parent.left), Height(parent.right));
            pivot.height = 1 + Math.Max(Height(pivot.left), Height(pivot.right));

            return pivot;
        }

        private AVLBinaryNode RotateLeft(AVLBinaryNode parent)
        {
            AVLBinaryNode pivot = parent.right;
            AVLBinaryNode e = pivot.left;

            parent.right = e;
            pivot.left = parent;

            pivot.height = 1 + Math.Max(Height(pivot.left), Height(pivot.right));
            parent.height = 1 + Math.Max(Height(parent.left), Height(parent.right));

            return pivot;
        }

        public new void TraverseInOrder()
        {
            InOrderHelper(root);
            Console.WriteLine();
        }

        private void InOrderHelper(AVLBinaryNode node)
        {
            if (node != null)
            {
                InOrderHelper(node.left);
                Console.Write(node.value + " ");
                InOrderHelper(node.right);
            }
        }
        public new void TraversePreOrder()
        {
            PreOrderHelper(root);
            Console.WriteLine();
        }
        private void PreOrderHelper(AVLBinaryNode node)
        {
            if (node != null)
            {
                Console.Write(node.value + " ");
                PreOrderHelper(node.left);
                PreOrderHelper(node.right);
            }
        }
        public new bool Contains(int value)
        {
            return ContainsHelper(root, value);
        }
        private bool ContainsHelper(AVLBinaryNode node, int value)
        {
            if (node == null)
            {
                return false;
            }
            else if (node.value == value)
            {
                return true;
            }
            else if (value < node.value)
            {
                return ContainsHelper(node.left, value);
            }
            else
            {
                return ContainsHelper(node.right, value);
            }
        }

    }
}