splay tree(top-down,foldable).cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    public static void Main()
    {
        int n = 2000;
        SplayTree<int> tree = new SplayTree<int>();
        HashSet<int> set = new HashSet<int>();
        Random rng = new Random();
        while (true)
        {
            var a = rng.Next(0, n);
            //var a = int.Parse(Console.ReadLine());
            Debug.Assert(tree.Add(a) == set.Add(a));
            Debug.Assert(tree.Count == set.Count);
        }
    }
}

class SplayTree<T> where T : IComparable<T>
{
    Node root;
    public int Count => root?.Size ?? 0;

    public bool Add(T value)
    {
        if (root == null) { root = new Node() { Value = value, Size = 1 }; return true; }
        Splay(value);
        var compareRes = value.CompareTo(root.Value);
        if (compareRes < 0 /*value < root.Value*/)
        {
            var topNode = new Node() { Value = value, Left = root.Left, Right = root };
            root.Left = null;
            root.CalcSize();
            root = topNode;
        }
        else if (compareRes > 0 /*value > root.Value*/)
        {
            var topNode = new Node() { Value = value, Left = root, Right = root.Right };
            root.Right = null;
            root.CalcSize();
            root = topNode;
        }
        else return false;
        root.CalcSize();
        return true;
    }

    public bool Remove(T value)
    {
        if (root == null) return false;
        Splay(value);
        if (value.CompareTo(root.Value) != 0) return false;
        var lRoot = root.Left;
        var rRoot = root.Right;
        if (lRoot == null) root = rRoot;
        else if (rRoot == null) root = lRoot;
        else
        {
            root = lRoot;
            Splay(value);
            root.Right = rRoot;
            root.CalcSize();
        }
        return true;
    }

    private void Splay(T value)
    {
        if (root == null) return;

        Node leftRoot = null;
        Node rightRoot = null;

        Node currentNode = root;
        while (true)
        {
            Node tmpSubtree;
            int direction, compareRes;

            compareRes = value.CompareTo(currentNode.Value);
            if (compareRes < 0/*value < currentNode.Value*/)
            {
                if (currentNode.Left == null) break;
                direction = -1;
                tmpSubtree = currentNode;
                currentNode = tmpSubtree.Left;
                //tmpSubtree.Left = null; ←あとで追加できる
            }
            else if (compareRes > 0/*value > currentNode.Value*/)
            {
                if (currentNode.Right == null) break;
                direction = 1;
                tmpSubtree = currentNode;
                currentNode = tmpSubtree.Right;
                //tmpSubtree.Right = null; ←あとで追加できる
            }
            else break;

            compareRes = value.CompareTo(currentNode.Value);
            if (compareRes < 0 //value < currentNode.Value
                && currentNode.Left != null)
            {
                if (direction == -1)
                {
                    //Zig-Zig
                    tmpSubtree.Left = currentNode.Right;
                    currentNode.Right = tmpSubtree;
                    var nextNode = currentNode.Left;
                    currentNode.Left = rightRoot;
                    rightRoot = currentNode;
                    currentNode = nextNode;
                }
                else
                {
                    //Zig-Zag
                    tmpSubtree.Right = leftRoot;
                    leftRoot = tmpSubtree;
                    var nextNode = currentNode.Left;
                    currentNode.Left = rightRoot;
                    rightRoot = currentNode;
                    currentNode = nextNode;
                }
            }
            else if (compareRes > 0 //value > currentNode.Value
                && currentNode.Right != null)
            {
                if (direction == 1)
                {
                    //Zig-Zig
                    tmpSubtree.Right = currentNode.Left;
                    currentNode.Left = tmpSubtree;
                    var nextNode = currentNode.Right;
                    currentNode.Right = leftRoot;
                    leftRoot = currentNode;
                    currentNode = nextNode;
                }
                else
                {
                    //Zig-Zag
                    tmpSubtree.Left = rightRoot;
                    rightRoot = tmpSubtree;
                    var nextNode = currentNode.Right;
                    currentNode.Right = leftRoot;
                    leftRoot = currentNode;
                    currentNode = nextNode;
                }
            }
            else
            {
                //Zig
                if (direction == -1)
                {
                    tmpSubtree.Left = rightRoot;
                    rightRoot = tmpSubtree;
                }
                else
                {
                    tmpSubtree.Right = leftRoot;
                    leftRoot = tmpSubtree;
                }
                break;
            }
            tmpSubtree.CalcSize();
        }
        root = currentNode;
        //foldタイム
        while (leftRoot != null)
        {
            var nextRoot = leftRoot.Right;
            leftRoot.Right = root.Left;
            leftRoot.CalcSize();
            root.Left = leftRoot;
            leftRoot = nextRoot;
        }
        while (rightRoot != null)
        {
            var nextRoot = rightRoot.Left;
            rightRoot.Left = root.Right;
            rightRoot.CalcSize();
            root.Right = rightRoot;
            //rightRoot.Right = null;
            rightRoot = nextRoot;
        }
        root.CalcSize();
    }

    class Node
    {
        public T Value;
        public Node Left;
        public Node Right;
        public int Size;
        public void CalcSize()
        {
            if (this == Left) throw new Exception();
            if (this == Right) throw new Exception();
            Size = 1 + (Left?.Size ?? 0) + (Right?.Size ?? 0);
        }
    }
}

splay tree(top-down,stupid).cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using static System.Math;

public static class P
{
    public static void Main()
    {
        int n = 2000;
        SplayTree<int> tree = new SplayTree<int>();
        HashSet<int> set = new HashSet<int>();
        Random rng = new Random();
        while (true)
        {
            var a = rng.Next(0, n);
            Debug.Assert(tree.Add(a) == set.Add(a));
        }
    }
}

class SplayTree<T> where T : IComparable<T>
{
    Node root;

    public bool Add(T value)
    {
        if (root == null) { root = new Node() { Value = value, Size = 1 }; return true; }
        Splay(value);
        var compareRes = value.CompareTo(root.Value);
        if (compareRes < 0 /*value < root.Value*/)
        {
            var topNode = new Node() { Value = value, Left = root.Left, Right = root };
            root.Left = null;
            root.CalcSize();
            root = topNode;
        }
        else if (compareRes > 0 /*value > root.Value*/)
        {
            var topNode = new Node() { Value = value, Left = root, Right = root.Right };
            root.Right = null;
            root.CalcSize();
            root = topNode;
        }
        else return false;
        root.CalcSize();
        return true;
    }

    public bool Remove(T value)
    {
        if (root == null) return false;
        Splay(value);
        if (value.CompareTo(root.Value) != 0) return false;
        var lRoot = root.Left;
        var rRoot = root.Right;
        if (lRoot == null) root = rRoot;
        else if (rRoot == null) root = lRoot;
        else
        {
            root = lRoot;
            Splay(value);
            root.Right = rRoot;
            root.CalcSize();
        }
        return true;
    }

    private void Splay(T value)
    {
        if (root == null) return;

        Node leftRoot = null;
        Node rightRoot = null;
        Node leftJoint = null;
        Node rightJoint = null;

        Node currentNode = root;
        while (true)
        {
            Node tmpSubtree;
            int direction, compareRes;

            compareRes = value.CompareTo(currentNode.Value);
            if (compareRes < 0/*value < currentNode.Value*/)
            {
                if (currentNode.Left == null) break;
                direction = -1;
                tmpSubtree = currentNode;
                currentNode = tmpSubtree.Left;
                tmpSubtree.Left = null;
            }
            else if (compareRes > 0/*value > currentNode.Value*/)
            {
                if (currentNode.Right == null) break;
                direction = 1;
                tmpSubtree = currentNode;
                currentNode = tmpSubtree.Right;
                tmpSubtree.Right = null;
            }
            else break;

            compareRes = value.CompareTo(currentNode.Value);
            if (compareRes < 0 //value < currentNode.Value
                && currentNode.Left != null)
            {
                if (direction == -1)
                {
                    //Zig-Zig
                    tmpSubtree.Left = currentNode.Right;
                    currentNode.Right = tmpSubtree;
                    if (rightRoot == null) rightRoot = (rightJoint = currentNode);
                    else rightJoint = (rightJoint.Left = currentNode);
                    currentNode = currentNode.Left;
                    //rightJoint.Left = null;
                }
                else
                {
                    //Zig-Zag
                    if (leftRoot == null) { leftJoint = (leftRoot = tmpSubtree); }
                    else { leftJoint = (leftJoint.Right = tmpSubtree); }

                    if (rightRoot == null) { rightJoint = (rightRoot = currentNode); }
                    else { rightJoint = (rightJoint.Left = currentNode); ; }
                    currentNode = rightJoint.Left;
                    //rightJoint.Left = null;
                }
            }
            else if (compareRes > 0 //value > currentNode.Value
                && currentNode.Right != null)
            {
                if (direction == 1)
                {
                    //Zig-Zig
                    tmpSubtree.Right = currentNode.Left;
                    currentNode.Left = tmpSubtree;
                    if (leftRoot == null) leftRoot = (leftJoint = currentNode);
                    else leftJoint = (leftJoint.Right = currentNode);
                    currentNode = currentNode.Right;
                    //leftJoint.Right = null;
                }
                else
                {
                    //Zig-Zag
                    if (rightRoot == null) { rightJoint = (rightRoot = tmpSubtree); }
                    else { rightJoint = (rightJoint.Left = tmpSubtree); }

                    if (leftRoot == null) { leftJoint = (leftRoot = currentNode); }
                    else { leftJoint = (leftJoint.Right = currentNode); ; }
                    currentNode = leftJoint.Right;
                    //leftJoint.Right = null;
                }
            }
            else
            {
                //Zig
                if (direction == -1)
                {
                    if (rightRoot == null) { rightJoint = (rightRoot = tmpSubtree); }
                    else { rightJoint = (rightJoint.Left = tmpSubtree); }
                }
                else
                {
                    if (leftRoot == null) { leftJoint = (leftRoot = tmpSubtree); }
                    else { leftJoint = (leftJoint.Right = tmpSubtree); }
                }
                break;
            }
        }
        if (leftJoint != null) leftJoint.Right = null;
        if (rightJoint != null) rightJoint.Left = null;
        if (currentNode.Left != null)
            if (leftRoot == null) leftRoot = currentNode.Left;
            else leftJoint.Right = currentNode.Left; //currentNode.Left = null
        if (currentNode.Right != null)
            if (rightRoot == null) rightRoot = currentNode.Right;
            else rightJoint.Left = currentNode.Right; //currentNode.Right = null

        currentNode.Left = leftRoot;
        currentNode.Right = rightRoot;
        root = currentNode;
    }

    class Node
    {
        public T Value;
        public Node Left;
        public Node Right;
        public int Size;
        public void CalcSize() => Size = 1 + (Left?.Size ?? 0) + (Right?.Size ?? 0);
    }
}