<commit_before>﻿using System;

namespace Algorithm.Sandbox.DataStructures
{
    public class AsRedBlackTreeNode<T> where T : IComparable
    {
        public T Value { get; set; }

        public AsRedBlackTree<T> Left { get; set; }
        public AsRedBlackTree<T> Right { get; set; }

        public bool IsLeaf => Left == null && Right == null;

        public AsRedBlackTreeNode(T value)
        {
            this.Value = value;
        }
    }

    public class AsRedBlackTree<T> where T : IComparable
    {
        public AsRedBlackTreeNode<T> Root { get; set; }

    }
}<commit_msg>red black tree prepare class<commit_after>﻿using System;

namespace Algorithm.Sandbox.DataStructures
{
    public enum RedBlackTreeNodeColor
    {
        Black,
        Red
    }

    public class AsRedBlackTreeNode<T> where T : IComparable
    {
        public T Value { get; set; }

        public AsRedBlackTreeNode<T> Parent { get; set; }

        public AsRedBlackTreeNode<T> Left { get; set; }
        public AsRedBlackTreeNode<T> Right { get; set; }

        public bool IsLeaf => Left == null && Right == null;
        public RedBlackTreeNodeColor NodeColor { get; set; }

        public AsRedBlackTreeNode<T> Sibling => this.Parent.Left == this ?
                                                this.Parent.Right : this.Parent.Left;

        public bool IsLeftChild => this.Parent.Left == this;
        public bool IsRightChild => this.Parent.Right == this;

        public AsRedBlackTreeNode(AsRedBlackTreeNode<T> parent, T value)
        {
            Parent = parent;
            Value = value;
        }
    }

    public class AsRedBlackTree<T> where T : IComparable
    {
        public AsRedBlackTreeNode<T> Root { get; set; }
        public int Count { get; private set; }

        //O(log(n)) worst O(n) for unbalanced tree
        public int GetHeight()
        {
            return GetHeight(Root);
        }

        //O(log(n)) worst O(n) for unbalanced tree
        private int GetHeight(AsRedBlackTreeNode<T> node)
        {
            if (node == null)
            {
                return -1;
            }

            return Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
        }
        //O(log(n)) always
        public bool HasItem(T value)
        {
            if (Root == null)
            {
                return false;
            }

            return Find(Root, value) != null;
        }
        public T FindMax()
        {
            return FindMax(Root).Value;
        }


        private AsRedBlackTreeNode<T> FindMax(AsRedBlackTreeNode<T> node)
        {
            if (node.Right == null)
            {
                return node;
            }

            return FindMax(node.Right);
        }

        public T FindMin()
        {
            return FindMin(Root).Value;
        }

        private AsRedBlackTreeNode<T> FindMin(AsRedBlackTreeNode<T> node)
        {
            if (node.Left == null)
            {
                return node;
            }

            return FindMin(node.Left);
        }

        //O(log(n)) worst O(n) for unbalanced tree
        private AsRedBlackTreeNode<T> Find(T value)
        {
            if (Root == null)
            {
                return null;
            }

            return Find(Root, value);
        }


        //find the node with the given identifier among descendants of parent and parent
        //uses pre-order traversal
        //O(log(n)) worst O(n) for unbalanced tree
        private AsRedBlackTreeNode<T> Find(AsRedBlackTreeNode<T> parent, T value)
        {
            if (parent == null)
            {
                return null;
            }

            if (parent.Value.CompareTo(value) == 0)
            {
                return parent;
            }

            var left = Find(parent.Left, value);

            if (left != null)
            {
                return left;
            }

            var right = Find(parent.Right, value);

            if (right != null)
            {
                return right;
            }

            return null;

        }

        private void RightRotate(AsRedBlackTreeNode<T> node)
        {
            var prevRoot = node;
            var leftRightChild = prevRoot.Left.Right;

            var newRoot = node.Left;

            //make left child as root
            prevRoot.Left.Parent = prevRoot.Parent;

            if (prevRoot.Parent != null)
            {
                if (prevRoot.Parent.Left == prevRoot)
                {
                    prevRoot.Parent.Left = prevRoot.Left;
                }
                else
                {
                    prevRoot.Parent.Right = prevRoot.Left;
                }
            }

            //move prev root as right child of current root
            newRoot.Right = prevRoot;
            prevRoot.Parent = newRoot;

            //move right child of left child of prev root to left child of right child of new root
            newRoot.Right.Left = leftRightChild;
            if (newRoot.Right.Left != null)
            {
                newRoot.Right.Left.Parent = newRoot.Right;
            }

            if (prevRoot == Root)
            {
                Root = newRoot;
            }

        }

        private void LeftRotate(AsRedBlackTreeNode<T> node)
        {
            var prevRoot = node;
            var rightLeftChild = prevRoot.Right.Left;

            var newRoot = node.Right;

            //make right child as root
            prevRoot.Right.Parent = prevRoot.Parent;

            if (prevRoot.Parent != null)
            {
                if (prevRoot.Parent.Left == prevRoot)
                {
                    prevRoot.Parent.Left = prevRoot.Right;
                }
                else
                {
                    prevRoot.Parent.Right = prevRoot.Right;
                }
            }


            //move prev root as left child of current root
            newRoot.Left = prevRoot;
            prevRoot.Parent = newRoot;

            //move left child of right child of prev root to right child of left child of new root
            newRoot.Left.Right = rightLeftChild;
            if (newRoot.Left.Right != null)
            {
                newRoot.Left.Right.Parent = newRoot.Left;
            }

            if (prevRoot == Root)
            {
                Root = newRoot;
            }
        }


        //O(log(n)) always
        public void Insert(T value)
        {
            if (Root == null)
            {
                Root = new AsRedBlackTreeNode<T>(null, value);
                Count++;
                return;
            }

            insert(Root, value);
        }
        //O(log(n)) always
        private void insert(AsRedBlackTreeNode<T> node, T value)
        {
            if (HasItem(value))
            {
                throw new Exception("Item exists");
            }

        }

        //O(log(n)) always
        public void Delete(T value)
        {
            if (Root == null)
            {
                throw new Exception("Empty Tree");
            }

            delete(Root, value);
        }
        //O(log(n)) always
        private void delete(AsRedBlackTreeNode<T> node, T value)
        {
            if (HasItem(value) == false)
            {
                throw new Exception("Item do not exist");
            }
        }
    }
}
{'fraction_non_alphanumeric': 0.08940666486047141, 'fraction_numerical': 0.000406393931183961, 'mean_word_length': 1.2352406902815622, 'pattern_counts': {'":': 0, '<': 29, '<?xml version=': 0, '>': 34, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3830291', 'n_tokens_mistral': 2024, 'n_tokens_neox': 1921, 'n_words': 506}