using Newtonsoft.Json;
using System;

namespace My.Collections;

public class RedBlackTree<TKey, TValue> where TKey : IComparable<TKey>
{
    private class Node
    {
        public TKey Key { get; set; }
        public TValue Value { get; set; }
        public bool IsRed { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }

        public void FlipColors()
        {
            IsRed = !IsRed;
            Left.IsRed = !IsRed;
            Right.IsRed = !IsRed;
        }
        public Node RotateRight()
        {
            Node newParent = Left;

            Left = newParent.Right;
            newParent.Right = this;
            newParent.IsRed = newParent.Right.IsRed;
            newParent.Right.IsRed = true;

            return newParent;
        }

        public Node RotateLeft()
        {
            Node newParent = Right;

            Right = newParent.Left;
            newParent.Left = this;
            newParent.IsRed = newParent.Left.IsRed;
            newParent.Left.IsRed = true;

            return newParent;
        }
        public override string ToString()
        {
            return $"{Key} ({(IsRed ? "red" : "black")}), Left/Right: {Left.Key} {Right.Key}";
        }
    }
    [JsonProperty]
    private Node root;

    [JsonProperty]
    public int Count { get; private set; }

    public void Add(TKey key, TValue value)
    {
        root = AddTo(root, key, value);
        root.IsRed = false;

        Count++;
    }

    public bool Contains(TKey key)
    {
        Node node = root;

        while (node != null)
        {
            int c = key.CompareTo(node.Key);

            if (c == 0)
                return true;

            if (c < 0)
                node = node.Left;
            else
                node = node.Right;
        }
        return false;
    }

    public TValue this[TKey key]
    {
        get
        {
            Node node = root;

            while (node != null)
            {
                int c = key.CompareTo(node.Key);

                if (c == 0)
                    return node.Value;

                if (c < 0)
                    node = node.Left;
                else
                    node = node.Right;
            }
            throw new ArgumentException("Key does'nt exist.");
        }
    }

    private static Node AddTo(Node node, TKey key, TValue value)
    {
        if (node == null)
            return new Node() { Key = key, Value = value, IsRed = true };

        int cmp = key.CompareTo(node.Key);
        if (cmp < 0)
            node.Left = AddTo(node.Left, key, value);
        else if (cmp > 0)
            node.Right = AddTo(node.Right, key, value);
        else
            node.Value = value;

        if (IsRed(node.Right) && !IsRed(node.Left))     // Regel für Linkslastigkeit
            node = node.RotateLeft();

        if (IsRed(node.Left) && IsRed(node.Left.Left))  // Keine aufeinanderfolgenden roten Knoten
            node = node.RotateRight();

        if (IsRed(node.Left) && IsRed(node.Right))      // keine zwei roten Kindknoten
            node.FlipColors();

        return node;
    }
    private static bool IsRed(Node node)
    {
        if (node == null)   // Null-Verweise stellen schwarze Blätter dar
            return false;

        return node.IsRed;
    }
    public override string ToString()
    {
        string s = "";
        int level = 0;

        Traverse(root, level, ref s);

        return s;
    }

    private static void Traverse(Node node, int level, ref string s)
    {
        if (node == null)
            return;

        string color = node.IsRed ? "red" : "black";
        s += "".PadLeft(level, ' ') + $"{node.Key} ({color})\n";
        Traverse(node.Left, level + 2, ref s);
        Traverse(node.Right, level + 2, ref s);
    }
}
