// -----------------------------------------------------------------------------
// Red Black Tree                                                             C#
// -----------------------------------------------------------------------------
// RedBlackTree(IComparer<T> comparer)
// int ElementCount
// RedBlackTree<T> Clone()
// bool Find(T key, bool findFirst, bool replace, out T item)
// int FindIndex(T key, bool findFirst)
// T GetItemByIndex(int index)
// bool Insert(T item, DuplicatePolicy dupPolicy, out T previous)
// bool Delete(T key, bool deleteFirst, out T item)
// IEnumerator<T> GetEnumerator()
// Func<T, int> BoundedRange(bool useFirst, T first, bool useLast, T last)
// Func<T, int> DoubleBoundedRange(T first, bool firstInclusive,
//                                 T last, bool lastInclusive)
// Func<T, int> LowerBoundedRange(T first, bool inclusive)
// Func<T, int> UpperBoundedRange(T last, bool inclusive)
// Func<T, int> EqualRange(T equalTo)
// int EntireRange(T item)
// IEnumerable<T> EnumerateRange(Func<T, int> range)
// IEnumerable<T> EnumerateRangeReversed(Func<T, int> range)
// bool DeleteItemFromRange(Func<T, int> range, bool deleteFirst, out T item)
// int DeleteRange(Func<T, int> range)
// int CountRange(Func<T, int> range)
// int FirstItemInRange(Func<T, int> range, out T item)
// int LastItemInRange(Func<T, int> range, out T item)
// -----------------------------------------------------------------------------
enum DuplicatePolicy
{
    InsertFirst,
    InsertLast,
    ReplaceFirst,
    ReplaceLast,
    DoNothing
};

class RedBlackTree<T> : IEnumerable<T>
{
    private readonly IComparer<T> comparer;
    private Node root;
    private int count;
    private int changeStamp;
    private Node[] stack;

    private Node[] GetNodeStack()
    {
        int maxDepth;
        if (count < 0x400)
            maxDepth = 21;
        else if (count < 0x10000)
            maxDepth = 41;
        else
            maxDepth = 65;
        if (stack == null || stack.Length < maxDepth)
            stack = new Node[maxDepth];
        return stack;
    }

    private class Node
    {
        public Node left, right;
        public T item;
        private const uint REDMASK = 0x80000000;
        private uint count;

        public bool IsRed
        {
            get { return (count & REDMASK) != 0; }
            set
            {
                if (value)
                    count |= REDMASK;
                else
                    count &= ~REDMASK;
            }
        }

        public int Count
        {
            get { return (int)(count & ~REDMASK); }
            set { count = (count & REDMASK) | (uint)value; }
        }

        public void IncrementCount()
        {
            ++count;
        }

        public void DecrementCount()
        {
            --count;
        }

        public Node Clone()
        {
            Node newNode = new Node();
            newNode.item = item;
            newNode.count = count;

            if (left != null)
                newNode.left = left.Clone();
            if (right != null)
                newNode.right = right.Clone();

            return newNode;
        }
    }

    internal void StopEnumerations()
    {
        ++changeStamp;
    }

    private void CheckEnumerationStamp(int startStamp)
    {
        if (startStamp != changeStamp)
        {
            throw new InvalidOperationException("Collection was modified");
        }
    }

    public RedBlackTree(IComparer<T> comparer)
    {
        this.comparer = comparer;
        this.count = 0;
        this.root = null;
    }

    public int ElementCount
    {
        get { return count; }
    }

    public RedBlackTree<T> Clone()
    {
        RedBlackTree<T> newTree = new RedBlackTree<T>(comparer);
        newTree.count = this.count;
        if (this.root != null)
            newTree.root = this.root.Clone();
        return newTree;
    }

    public bool Find(T key, bool findFirst, bool replace, out T item)
    {
        Node current = root;
        Node found = null;

        while (current != null)
        {
            int compare = comparer.Compare(key, current.item);

            if (compare < 0)
                current = current.left;
            else if (compare > 0)
                current = current.right;
            else
            {
                found = current;
                if (findFirst)
                    current = current.left;
                else
                    current = current.right;
            }
        }

        if (found != null)
        {
            item = found.item;
            if (replace)
                found.item = key;
            return true;
        }
        else
        {
            item = default(T);
            return false;
        }
    }

    public int FindIndex(T key, bool findFirst)
    {
        T dummy;
        if (findFirst)
            return FirstItemInRange(EqualRange(key), out dummy);
        else
            return LastItemInRange(EqualRange(key), out dummy);
    }

    public T GetItemByIndex(int index)
    {
        if (index < 0 || index >= count)
            throw new ArgumentOutOfRangeException("index");

        Node current = root;
        for (; ; )
        {
            int leftCount;

            if (current.left != null)
                leftCount = current.left.Count;
            else
                leftCount = 0;

            if (leftCount > index)
                current = current.left;
            else if (leftCount == index)
                return current.item;
            else
            {
                index -= leftCount + 1;
                current = current.right;
            }
        }
    }

    public bool Insert(T item, DuplicatePolicy dupPolicy, out T previous)
    {
        Node node = root;
        Node parent = null, gparent = null, ggparent = null;
        bool wentLeft = false, wentRight = false;
        bool rotated;
        Node duplicateFound = null;

        StopEnumerations();

        bool needStack = !((dupPolicy == DuplicatePolicy.InsertFirst) ||
                           (dupPolicy == DuplicatePolicy.InsertLast));
        Node[] nodeStack = null;
        int nodeStackPtr = 0;
        if (needStack)
            nodeStack = GetNodeStack();

        while (node != null)
        {
            if (node.left != null && node.left.IsRed &&
                node.right != null && node.right.IsRed)
            {
                node = InsertSplit(ggparent, gparent, parent, node,
                                   out rotated);
                if (needStack && rotated)
                {
                    nodeStackPtr -= 2;
                    if (nodeStackPtr < 0)
                        nodeStackPtr = 0;
                }
            }
            ggparent = gparent; gparent = parent; parent = node;
            int compare = comparer.Compare(item, node.item);
            if (compare == 0)
            {
                if (dupPolicy == DuplicatePolicy.DoNothing)
                {
                    previous = node.item;
                    for (int i = 0; i < nodeStackPtr; ++i)
                        nodeStack[i].DecrementCount();
                    return false;
                }
                else if (dupPolicy == DuplicatePolicy.InsertFirst ||
                         dupPolicy == DuplicatePolicy.ReplaceFirst)
                {
                    duplicateFound = node;
                    compare = -1;
                }
                else
                {
                    duplicateFound = node;
                    compare = 1;
                }
            }

            node.IncrementCount();
            if (needStack)
                nodeStack[nodeStackPtr++] = node;

            if (compare < 0)
            {
                node = node.left;
                wentLeft = true; wentRight = false;
            }
            else
            {
                node = node.right;
                wentRight = true; wentLeft = false;
            }
        }

        if (duplicateFound != null)
        {
            previous = duplicateFound.item;
            if (dupPolicy == DuplicatePolicy.ReplaceFirst ||
                dupPolicy == DuplicatePolicy.ReplaceLast)
            {
                duplicateFound.item = item;
                for (int i = 0; i < nodeStackPtr; ++i)
                    nodeStack[i].DecrementCount();

                return false;
            }
        }
        else
        {
            previous = default(T);
        }

        node = new Node();
        node.item = item;
        node.Count = 1;

        if (wentLeft)
            parent.left = node;
        else if (wentRight)
            parent.right = node;
        else
            root = node;

        InsertSplit(ggparent, gparent, parent, node, out rotated);

        count += 1;

        return (duplicateFound == null);
    }

    private Node InsertSplit(
        Node ggparent, Node gparent, Node parent, Node node,
        out bool rotated)
    {
        if (node != root)
            node.IsRed = true;
        if (node.left != null)
            node.left.IsRed = false;
        if (node.right != null)
            node.right.IsRed = false;

        if (parent != null && parent.IsRed)
        {
            if ((gparent.left == parent) != (parent.left == node))
            {
                Rotate(gparent, parent, node);
                parent = node;
            }

            gparent.IsRed = true;

            Rotate(ggparent, gparent, parent);

            parent.IsRed = false;
            rotated = true;
            return parent;
        }
        else
        {
            rotated = false;
            return node;
        }
    }

    private void Rotate(Node node, Node child, Node gchild)
    {
        if (gchild == child.left)
        {
            child.left = gchild.right;
            gchild.right = child;
        }
        else
        {
            child.right = gchild.left;
            gchild.left = child;
        }

        child.Count = (child.left != null ? child.left.Count : 0) +
                      (child.right != null ? child.right.Count : 0) + 1;
        gchild.Count = (gchild.left != null ? gchild.left.Count : 0) +
                       (gchild.right != null ? gchild.right.Count : 0) + 1;

        if (node == null)
            root = gchild;
        else if (child == node.left)
            node.left = gchild;
        else
            node.right = gchild;
    }

    public bool Delete(T key, bool deleteFirst, out T item)
    {
        return DeleteItemFromRange(EqualRange(key), deleteFirst, out item);
    }

    public IEnumerator<T> GetEnumerator()
    {
        return EnumerateRange(EntireRange).GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public Func<T, int> BoundedRange(bool useFirst, T first,
                                     bool useLast, T last)
    {
        return delegate (T item) {
            if (useFirst && comparer.Compare(first, item) > 0)
                return -1;
            else if (useLast && comparer.Compare(last, item) <= 0)
                return 1;
            else
                return 0;
        };
    }

    public Func<T, int> DoubleBoundedRange(T first, bool firstInclusive,
                                           T last, bool lastInclusive)
    {
        return delegate (T item) {
            if (firstInclusive)
            {
                if (comparer.Compare(first, item) > 0) return -1;
            }
            else
            {
                if (comparer.Compare(first, item) >= 0) return -1;
            }

            if (lastInclusive)
            {
                if (comparer.Compare(last, item) < 0) return 1;
            }
            else
            {
                if (comparer.Compare(last, item) <= 0) return 1;
            }

            return 0;
        };
    }

    public Func<T, int> LowerBoundedRange(T first, bool inclusive)
    {
        return delegate (T item) {
            if (inclusive)
            {
                if (comparer.Compare(first, item) > 0)
                    return -1;
                else
                    return 0;
            }
            else
            {
                if (comparer.Compare(first, item) >= 0)
                    return -1;
                else
                    return 0;
            }
        };
    }

    public Func<T, int> UpperBoundedRange(T last, bool inclusive)
    {
        return delegate (T item) {
            if (inclusive)
            {
                if (comparer.Compare(last, item) < 0)
                    return 1;
                else
                    return 0;
            }
            else
            {
                if (comparer.Compare(last, item) <= 0)
                    return 1;
                else
                    return 0;
            }
        };
    }

    public Func<T, int> EqualRange(T equalTo)
    {
        return delegate (T item) {
            return comparer.Compare(item, equalTo);
        };
    }

    public int EntireRange(T item)
    {
        return 0;
    }

    public IEnumerable<T> EnumerateRange(Func<T, int> range)
    {
        return EnumerateRangeInOrder(range, root);
    }

    private IEnumerable<T> EnumerateRangeInOrder(Func<T, int> range, Node node)
    {
        int startStamp = changeStamp;

        if (node != null)
        {
            int compare = range(node.item);

            if (compare >= 0)
            {
                foreach (T item in EnumerateRangeInOrder(range, node.left))
                {
                    yield return item;
                    CheckEnumerationStamp(startStamp);
                }
            }

            if (compare == 0)
            {
                yield return node.item;
                CheckEnumerationStamp(startStamp);
            }

            if (compare <= 0)
            {
                foreach (T item in EnumerateRangeInOrder(range, node.right))
                {
                    yield return item;
                    CheckEnumerationStamp(startStamp);
                }
            }
        }
    }

    public IEnumerable<T> EnumerateRangeReversed(Func<T, int> range)
    {
        return EnumerateRangeInReversedOrder(range, root);
    }

    private IEnumerable<T> EnumerateRangeInReversedOrder(Func<T, int> range,
                                                         Node node)
    {
        int startStamp = changeStamp;

        if (node != null)
        {
            int compare = range(node.item);

            if (compare <= 0)
            {
                foreach (T item in EnumerateRangeInReversedOrder(range, node.right))
                {
                    yield return item;
                    CheckEnumerationStamp(startStamp);
                }
            }

            if (compare == 0)
            {
                yield return node.item;
                CheckEnumerationStamp(startStamp);
            }

            if (compare >= 0)
            {
                foreach (T item in EnumerateRangeInReversedOrder(range, node.left))
                {
                    yield return item;
                    CheckEnumerationStamp(startStamp);
                }
            }
        }
    }

    public bool DeleteItemFromRange(Func<T, int> range, bool deleteFirst, out T item)
    {
        Node node;
        Node parent;
        Node gparent;
        Node sib;
        Node keyNode;

        StopEnumerations();

        if (root == null)
        {
            item = default(T);
            return false;
        }

        Node[] nodeStack = GetNodeStack();
        int nodeStackPtr = 0;

        node = root;
        sib = parent = gparent = null;
        keyNode = null;

        for (; ; )
        {
            if ((node.left == null || !node.left.IsRed) &&
                (node.right == null || !node.right.IsRed))
            {
                if (parent == null)
                    node.IsRed = true;
                else if ((sib.left == null || !sib.left.IsRed) &&
                         (sib.right == null || !sib.right.IsRed))
                {
                    node.IsRed = true;
                    sib.IsRed = true;
                    parent.IsRed = false;
                }
                else
                {
                    if (parent.left == node &&
                        (sib.right == null || !sib.right.IsRed))
                    {
                        Node tleft = sib.left;
                        Rotate(parent, sib, tleft);
                        sib = tleft;
                    }
                    else if (parent.right == node &&
                             (sib.left == null || !sib.left.IsRed))
                    {
                        Node tright = sib.right;
                        Rotate(parent, sib, tright);
                        sib = tright;
                    }

                    Rotate(gparent, parent, sib);
                    node.IsRed = true;
                    sib.IsRed = true;
                    sib.left.IsRed = false;
                    sib.right.IsRed = false;

                    sib.DecrementCount();
                    nodeStack[nodeStackPtr - 1] = sib;
                    parent.DecrementCount();
                    nodeStack[nodeStackPtr++] = parent;
                }
            }

            do
            {
                Node nextNode, nextSib;

                node.DecrementCount();
                nodeStack[nodeStackPtr++] = node;
                int compare = range(node.item);

                if (compare == 0)
                {
                    keyNode = node;
                    if (deleteFirst)
                    {
                        nextNode = node.left; nextSib = node.right;
                    }
                    else
                    {
                        nextNode = node.right; nextSib = node.left;
                    }
                }
                else if (compare > 0)
                {
                    nextNode = node.left; nextSib = node.right;
                }
                else
                {
                    nextNode = node.right; nextSib = node.left;
                }

                if (nextNode == null)
                    goto FINISHED;

                gparent = parent;
                parent = node;
                node = nextNode;
                sib = nextSib;
            } while (!parent.IsRed && node.IsRed);

            if (!parent.IsRed)
            {
                Rotate(gparent, parent, sib);

                sib.DecrementCount();
                nodeStack[nodeStackPtr - 1] = sib;
                parent.DecrementCount();
                nodeStack[nodeStackPtr++] = parent;

                sib.IsRed = false;
                parent.IsRed = true;
                gparent = sib;
                sib = (parent.left == node) ? parent.right : parent.left;
            }
        }

        FINISHED:
        if (keyNode == null)
        {
            for (int i = 0; i < nodeStackPtr; ++i)
                nodeStack[i].IncrementCount();

            if (root != null)
                root.IsRed = false;

            item = default(T);
            return false;
        }

        item = keyNode.item;

        if (keyNode != node)
        {
            keyNode.item = node.item;
        }

        Node replacement;
        if (node.left != null)
        {
            replacement = node.left;
            replacement.IsRed = false;
        }
        else if (node.right != null)
        {
            replacement = node.right;
            replacement.IsRed = false;
        }
        else
            replacement = null;

        if (parent == null)
            root = replacement;
        else if (parent.left == node)
            parent.left = replacement;
        else
            parent.right = replacement;

        if (root != null)
            root.IsRed = false;
        count -= 1;
        return true;
    }

    public int DeleteRange(Func<T, int> range)
    {
        bool deleted;
        int counter = 0;
        T dummy;

        do
        {
            deleted = DeleteItemFromRange(range, true, out dummy);
            if (deleted)
                ++counter;
        } while (deleted);

        return counter;
    }

    public int CountRange(Func<T, int> range)
    {
        return CountRangeUnderNode(range, root, false, false);
    }

    private int CountRangeUnderNode(Func<T, int> range, Node node,
                                    bool belowRangeTop, bool aboveRangeBottom)
    {
        if (node != null)
        {
            if (belowRangeTop && aboveRangeBottom)
                return node.Count;

            int compare = range(node.item);
            int counter;

            if (compare == 0)
            {
                counter = 1;
                counter += CountRangeUnderNode(range, node.left,
                                               true, aboveRangeBottom);
                counter += CountRangeUnderNode(range, node.right,
                                               belowRangeTop, true);
            }
            else if (compare < 0)
                counter = CountRangeUnderNode(range, node.right,
                                              belowRangeTop, aboveRangeBottom);
            else
                counter = CountRangeUnderNode(range, node.left,
                                              belowRangeTop, aboveRangeBottom);

            return counter;
        }
        else
        {
            return 0;
        }
    }

    public int FirstItemInRange(Func<T, int> range, out T item)
    {
        Node node = root, found = null;
        int curCount = 0, foundIndex = -1;

        while (node != null)
        {
            int compare = range(node.item);

            if (compare == 0)
            {
                found = node;
                if (node.left != null)
                    foundIndex = curCount + node.left.Count;
                else
                    foundIndex = curCount;
            }

            if (compare >= 0)
                node = node.left;
            else
            {
                if (node.left != null)
                    curCount += node.left.Count + 1;
                else
                    curCount += 1;
                node = node.right;
            }
        }

        if (found != null)
        {
            item = found.item;
            return foundIndex;
        }
        else
        {
            item = default(T);
            return -1;
        }
    }

    public int LastItemInRange(Func<T, int> range, out T item)
    {
        Node node = root, found = null;
        int curCount = 0, foundIndex = -1;

        while (node != null)
        {
            int compare = range(node.item);

            if (compare == 0)
            {
                found = node;
                if (node.left != null)
                    foundIndex = curCount + node.left.Count;
                else
                    foundIndex = curCount;
            }

            if (compare <= 0)
            {
                if (node.left != null)
                    curCount += node.left.Count + 1;
                else
                    curCount += 1;
                node = node.right;
            }
            else
                node = node.left;
        }

        if (found != null)
        {
            item = found.item;
            return foundIndex;
        }
        else
        {
            item = default(T);
            return foundIndex;
        }
    }
}
// -----------------------------------------------------------------------------