Next Greater Element IV solution and explanation

def second_greater_element(nums):
    n = len(nums)
    res = [-1] * n
    stack1 = []
    stack2 = []

    for i in range(n - 1, -1, -1):
        while stack2 and nums[stack2[-1]] <= nums[i]:
            stack2.pop()
        while stack1 and nums[stack1[-1]] <= nums[i]:
            stack2.append(stack1.pop())
        if stack2:
            res[i] = nums[stack2[-1]]
        stack1.append(i)

    return res

nums = [2, 4, 0, 9, 6]
print(second_greater_element(nums))

import java.util.Stack;

public class Main {
    public static int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        
        for (int i = n - 1; i >= 0; --i) {
            while (!stack2.isEmpty() && nums[stack2.peek()] <= nums[i]) stack2.pop();
            while (!stack1.isEmpty() && nums[stack1.peek()] <= nums[i]) stack2.push(stack1.pop());
            res[i] = (stack2.isEmpty()) ? -1 : nums[stack2.peek()];
            stack1.push(i);
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 0, 9, 6};
        int[] res = secondGreaterElement(nums);

        for (int num : res) {
            System.out.print(num + " ");
        }
    }
}

#include <iostream>
#include <vector>
#include <stack>

std::vector<int> secondGreaterElement(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> res(n, -1);
    std::stack<int> stack1, stack2;

    for (int i = n - 1; i >= 0; --i) {
        while (!stack2.empty() && nums[stack2.top()] <= nums[i]) stack2.pop();
        while (!stack1.empty() && nums[stack1.top()] <= nums[i]) {
            stack2.push(stack1.top());
            stack1.pop();
        }
        if (!stack2.empty()) res[i] = nums[stack2.top()];
        stack1.push(i);
    }

    return res;
}

int main() {
    std::vector<int> nums = {2, 4, 0, 9, 6};
    std::vector<int> res = secondGreaterElement(nums);

    for (int num : res) {
        std::cout << num << " ";
    }

    return 0;
}

function secondGreaterElement(nums) {
    const n = nums.length;
    const res = new Array(n).fill(-1);
    const stack1 = [];
    const stack2 = [];

    for (let i = n - 1; i >= 0; --i) {
        while (stack2.length && nums[stack2[stack2.length - 1]] <= nums[i]) stack2.pop();
        while (stack1.length && nums[stack1[stack1.length - 1]] <= nums[i]) stack2.push(stack1.pop());
        if (stack2.length) res[i] = nums[stack2[stack2.length - 1]];
        stack1.push(i);
    }

    return res;
}

const nums = [2, 4, 0, 9, 6];
console.log(secondGreaterElement(nums));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

void secondGreaterElement(int* nums, int numsSize, int* res) {
    int* stack1 = (int*)malloc(sizeof(int) * numsSize);
    int* stack2 = (int*)malloc(sizeof(int) * numsSize);
    int top1 = -1, top2 = -1;

    for (int i = numsSize - 1; i >= 0; i--) {
        while (top2 >= 0 && nums[stack2[top2]] <= nums[i]) top2--;
        while (top1 >= 0 && nums[stack1[top1]] <= nums[i]) stack2[++top2] = stack1[top1--];
        res[i] = (top2 == -1) ? -1 : nums[stack2[top2]];
        stack1[++top1] = i;
    }

    free(stack1);
    free(stack2);
}

int main() {
    int nums[] = {2, 4, 0, 9, 6};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int* res = (int*)malloc(sizeof(int) * numsSize);

    secondGreaterElement(nums, numsSize, res);

    for (int i = 0; i < numsSize; i++) {
        printf("%d ", res[i]);
    }

    free(res);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public static int[] SecondGreaterElement(int[] nums) {
        int n = nums.Length;
        int[] res = new int[n];
        Stack<int> stack1 = new Stack<int>();
        Stack<int> stack2 = new Stack<int>();

        for (int i = n - 1; i >= 0; --i) {
            while (stack2.Count > 0 && nums[stack2.Peek()] <= nums[i]) stack2.Pop();
            while (stack1.Count > 0 && nums[stack1.Peek()] <= nums[i]) 
                stack2.Push(stack1.Pop());
            res[i] = (stack2.Count == 0) ? -1 : nums[stack2.Peek()];
            stack1.Push(i);
        }

        return res;
    }

    public static void Main() {
        int[] nums = {2, 4, 0, 9, 6};
        int[] res = SecondGreaterElement(nums);
        Console.WriteLine(string.Join(" ", res));
    }
}

import heapq

def second_greater_element(nums):
    n = len(nums)
    res = [-1] * n
    pq = []  # A list of (-value, index)

    for i in range(n - 1, -1, -1):
        while pq and pq[0][0] >= -nums[i]:
            heapq.heappop(pq)
        if pq:
            res[i] = -pq[0][0]
        heapq.heappush(pq, (-nums[i], i))

    return res

nums = [2, 4, 0, 9, 6]
print(second_greater_element(nums))

import java.util.PriorityQueue;
import java.util.Comparator;

public class Main {
    public static int[] secondGreaterElement(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> -a[0]));

        for (int i = n - 1; i >= 0; --i) {
            while (!pq.isEmpty() && pq.peek()[0] <= nums[i]) pq.poll();
            res[i] = pq.isEmpty() ? -1 : pq.peek()[0];
            pq.offer(new int[]{nums[i], i});
        }

        return res;
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 0, 9, 6};
        int[] res = secondGreaterElement(nums);

        for (int num : res) {
            System.out.print(num + " ");
        }
    }
}

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

std::vector<int> secondGreaterElement(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> res(n, -1);
    std::priority_queue<std::pair<int, int>> pq;

    for (int i = n - 1; i >= 0; --i) {
        while (!pq.empty() && pq.top().first <= nums[i]) pq.pop();
        if (!pq.empty()) res[i] = pq.top().first;
        pq.emplace(nums[i], i);
    }

    return res;
}

int main() {
    std::vector<int> nums = {2, 4, 0, 9, 6};
    std::vector<int> res = secondGreaterElement(nums);

    for (int num : res) {
        std::cout << num << " ";
    }

    return 0;
}

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  insert(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (
      index > 0 &&
      this.heap[Math.floor((index - 1) / 2)][0] < this.heap[index][0]
    ) {
      [this.heap[Math.floor((index - 1) / 2)], this.heap[index]] =
        [this.heap[index], this.heap[Math.floor((index - 1) / 2)]];
      index = Math.floor((index - 1) / 2);
    }
  }

  extractMax() {
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown(0);
    }
    return max;
  }

  sinkDown(index) {
    const length = this.heap.length;
    const element = this.heap[index];
    let swap = null;

    while (true) {
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild[0] > element[0]) {
          swap = leftChildIndex;
        }
      }
      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (swap === null && rightChild[0] > element[0]) ||
          (swap !== null && rightChild[0] > leftChild[0])
        ) {
          swap = rightChildIndex;
        }
      }
      if (swap === null) break;
      this.heap[index] = this.heap[swap];
      this.heap[swap] = element;
      index = swap;
    }
  }

  peek() {
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }
}

function secondGreaterElement(nums) {
  const n = nums.length;
  const res = new Array(n).fill(-1);
  const heap = new MaxHeap();

  for (let i = n - 1; i >= 0; --i) {
    while (heap.size() > 0 && heap.peek()[0] <= nums[i]) {
      heap.extractMax();
    }
    if (heap.size() > 0) {
      res[i] = heap.peek()[0];
    }
    heap.insert([nums[i], i]);
  }

  return res;
}

const nums = [2, 4, 0, 9, 6];
console.log(secondGreaterElement(nums));

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct {
    int value;
    int index;
} HeapNode;

void swap(HeapNode* x, HeapNode* y) {
    HeapNode temp = *x;
    *x = *y;
    *y = temp;
}

void heapify(HeapNode heap[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && heap[left].value > heap[largest].value) largest = left;
    if (right < n && heap[right].value > heap[largest].value) largest = right;

    if (largest != i) {
        swap(&heap[i], &heap[largest]);
        heapify(heap, n, largest);
    }
}

void insertHeap(HeapNode heap[], int* n, HeapNode newNode) {
    heap[*n] = newNode;
    int i = *n;
    (*n)++;

    while (i != 0 && heap[(i - 1) / 2].value < heap[i].value) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

void secondGreaterElement(int* nums, int numsSize, int* res) {
    HeapNode* heap = (HeapNode*)malloc(sizeof(HeapNode) * numsSize);
    int heapSize = 0;
    
    for (int i = numsSize - 1; i >= 0; i--) {
        while (heapSize > 0 && heap[0].value <= nums[i]){
            heapSize--;
            swap(&heap[0], &heap[heapSize]);
            heapify(heap, heapSize, 0);
        }
        res[i] = (heapSize == 0) ? -1 : heap[0].value;
        HeapNode newNode = {nums[i], i};
        insertHeap(heap, &heapSize, newNode);
    }

    free(heap);
}

int main() {
    int nums[] = {2, 4, 0, 9, 6};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int* res = (int*)malloc(sizeof(int) * numsSize);

    secondGreaterElement(nums, numsSize, res);

    for (int i = 0; i < numsSize; i++) {
        printf("%d ", res[i]);
    }

    free(res);
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public static int[] SecondGreaterElement(int[] nums) {
        int n = nums.Length;
        int[] res = new int[n];
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>(new IntComparer());

        for (int i = n - 1; i >= 0; i--) {
            while (pq.Count > 0 && pq.Peek().value <= nums[i]) pq.Dequeue();
            res[i] = (pq.Count == 0) ? -1 : pq.Peek().value;
            pq.Enqueue(nums[i], nums[i]);
        }

        return res;
    }

    public static void Main() {
        int[] nums = {2, 4, 0, 9, 6};
        int[] res = SecondGreaterElement(nums);

        foreach (int num in res) {
            Console.Write(num + " ");
        }
    }
}

public class IntComparer : IComparer<int> {
    public int Compare(int x, int y) {
        return y.CompareTo(x);
    }
}

function secondGreaterElement(nums: number[]): number[] {
    const n = nums.length;
    const arr: number[][] = [];
    for (let i = 0; i < n; ++i) {
        arr.push([nums[i], i]);
    }
    arr.sort((a, b) => (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
    const ans = Array(n).fill(-1);
    const ts = new TreeSet<number>();
    for (const [_, i] of arr) {
        let j = ts.higher(i);
        if (j !== undefined) {
            j = ts.higher(j);
            if (j !== undefined) {
                ans[i] = nums[j];
            }
        }
        ts.add(i);
    }
    return ans;
}

type Compare<T> = (lhs: T, rhs: T) => number;

class RBTreeNode<T = number> {
    data: T;
    count: number;
    left: RBTreeNode<T> | null;
    right: RBTreeNode<T> | null;
    parent: RBTreeNode<T> | null;
    color: number;
    constructor(data: T) {
        this.data = data;
        this.left = this.right = this.parent = null;
        this.color = 0;
        this.count = 1;
    }

    sibling(): RBTreeNode<T> | null {
        if (!this.parent) return null; // sibling null if no parent
        return this.isOnLeft() ? this.parent.right : this.parent.left;
    }

    isOnLeft(): boolean {
        return this === this.parent!.left;
    }

    hasRedChild(): boolean {
        return (
            Boolean(this.left && this.left.color === 0) ||
            Boolean(this.right && this.right.color === 0)
        );
    }
}

class RBTree<T> {
    root: RBTreeNode<T> | null;
    lt: (l: T, r: T) => boolean;
    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
        this.root = null;
        this.lt = (l: T, r: T) => compare(l, r) < 0;
    }

    rotateLeft(pt: RBTreeNode<T>): void {
        const right = pt.right!;
        pt.right = right.left;

        if (pt.right) pt.right.parent = pt;
        right.parent = pt.parent;

        if (!pt.parent) this.root = right;
        else if (pt === pt.parent.left) pt.parent.left = right;
        else pt.parent.right = right;

        right.left = pt;
        pt.parent = right;
    }

    rotateRight(pt: RBTreeNode<T>): void {
        const left = pt.left!;
        pt.left = left.right;

        if (pt.left) pt.left.parent = pt;
        left.parent = pt.parent;

        if (!pt.parent) this.root = left;
        else if (pt === pt.parent.left) pt.parent.left = left;
        else pt.parent.right = left;

        left.right = pt;
        pt.parent = left;
    }

    swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.color;
        p1.color = p2.color;
        p2.color = tmp;
    }

    swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.data;
        p1.data = p2.data;
        p2.data = tmp;
    }

    fixAfterInsert(pt: RBTreeNode<T>): void {
        let parent = null;
        let grandParent = null;

        while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
            parent = pt.parent;
            grandParent = pt.parent.parent;

            /*  Case : A
                Parent of pt is left child of Grand-parent of pt */
            if (parent === grandParent?.left) {
                const uncle = grandParent.right;

                /* Case : 1
                   The uncle of pt is also red
                   Only Recoloring required */
                if (uncle && uncle.color === 0) {
                    grandParent.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent;
                } else {
                    /* Case : 2
                       pt is right child of its parent
                       Left-rotation required */
                    if (pt === parent.right) {
                        this.rotateLeft(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is left child of its parent
                       Right-rotation required */
                    this.rotateRight(grandParent);
                    this.swapColor(parent!, grandParent);
                    pt = parent!;
                }
            } else {
                /* Case : B
               Parent of pt is right child of Grand-parent of pt */
                const uncle = grandParent!.left;

                /*  Case : 1
                    The uncle of pt is also red
                    Only Recoloring required */
                if (uncle != null && uncle.color === 0) {
                    grandParent!.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent!;
                } else {
                    /* Case : 2
                       pt is left child of its parent
                       Right-rotation required */
                    if (pt === parent.left) {
                        this.rotateRight(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is right child of its parent
                       Left-rotation required */
                    this.rotateLeft(grandParent!);
                    this.swapColor(parent!, grandParent!);
                    pt = parent!;
                }
            }
        }
        this.root!.color = 1;
    }

    delete(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        node.count--;
        if (!node.count) this.deleteNode(node);
        return true;
    }

    deleteAll(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        this.deleteNode(node);
        return true;
    }

    deleteNode(v: RBTreeNode<T>): void {
        const u = BSTreplace(v);

        // True when u and v are both black
        const uvBlack = (u === null || u.color === 1) && v.color === 1;
        const parent = v.parent!;

        if (!u) {
            // u is null therefore v is leaf
            if (v === this.root) this.root = null;
            // v is root, making root null
            else {
                if (uvBlack) {
                    // u and v both black
                    // v is leaf, fix double black at v
                    this.fixDoubleBlack(v);
                } else {
                    // u or v is red
                    if (v.sibling()) {
                        // sibling is not null, make it red"
                        v.sibling()!.color = 0;
                    }
                }
                // delete v from the tree
                if (v.isOnLeft()) parent.left = null;
                else parent.right = null;
            }
            return;
        }

        if (!v.left || !v.right) {
            // v has 1 child
            if (v === this.root) {
                // v is root, assign the value of u to v, and delete u
                v.data = u.data;
                v.left = v.right = null;
            } else {
                // Detach v from tree and move u up
                if (v.isOnLeft()) parent.left = u;
                else parent.right = u;
                u.parent = parent;
                if (uvBlack) this.fixDoubleBlack(u);
                // u and v both black, fix double black at u
                else u.color = 1; // u or v red, color u black
            }
            return;
        }

        // v has 2 children, swap data with successor and recurse
        this.swapData(u, v);
        this.deleteNode(u);

        // find node that replaces a deleted node in BST
        function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
            // when node have 2 children
            if (x.left && x.right) return successor(x.right);
            // when leaf
            if (!x.left && !x.right) return null;
            // when single child
            return x.left ?? x.right;
        }
        // find node that do not have a left child
        // in the subtree of the given node
        function successor(x: RBTreeNode<T>): RBTreeNode<T> {
            let temp = x;
            while (temp.left) temp = temp.left;
            return temp;
        }
    }

    fixDoubleBlack(x: RBTreeNode<T>): void {
        if (x === this.root) return; // Reached root

        const sibling = x.sibling();
        const parent = x.parent!;
        if (!sibling) {
            // No sibiling, double black pushed up
            this.fixDoubleBlack(parent);
        } else {
            if (sibling.color === 0) {
                // Sibling red
                parent.color = 0;
                sibling.color = 1;
                if (sibling.isOnLeft()) this.rotateRight(parent);
                // left case
                else this.rotateLeft(parent); // right case
                this.fixDoubleBlack(x);
            } else {
                // Sibling black
                if (sibling.hasRedChild()) {
                    // at least 1 red children
                    if (sibling.left && sibling.left.color === 0) {
                        if (sibling.isOnLeft()) {
                            // left left
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateRight(parent);
                        } else {
                            // right left
                            sibling.left.color = parent.color;
                            this.rotateRight(sibling);
                            this.rotateLeft(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            // left right
                            sibling.right!.color = parent.color;
                            this.rotateLeft(sibling);
                            this.rotateRight(parent);
                        } else {
                            // right right
                            sibling.right!.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateLeft(parent);
                        }
                    }
                    parent.color = 1;
                } else {
                    // 2 black children
                    sibling.color = 0;
                    if (parent.color === 1) this.fixDoubleBlack(parent);
                    else parent.color = 1;
                }
            }
        }
    }

    insert(data: T): boolean {
        // search for a position to insert
        let parent = this.root;
        while (parent) {
            if (this.lt(data, parent.data)) {
                if (!parent.left) break;
                else parent = parent.left;
            } else if (this.lt(parent.data, data)) {
                if (!parent.right) break;
                else parent = parent.right;
            } else break;
        }

        // insert node into parent
        const node = new RBTreeNode(data);
        if (!parent) this.root = node;
        else if (this.lt(node.data, parent.data)) parent.left = node;
        else if (this.lt(parent.data, node.data)) parent.right = node;
        else {
            parent.count++;
            return false;
        }
        node.parent = parent;
        this.fixAfterInsert(node);
        return true;
    }

    find(data: T): RBTreeNode<T> | null {
        let p = this.root;
        while (p) {
            if (this.lt(data, p.data)) {
                p = p.left;
            } else if (this.lt(p.data, data)) {
                p = p.right;
            } else break;
        }
        return p ?? null;
    }

    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.inOrder(root.left!)) yield v;
        yield root.data;
        for (const v of this.inOrder(root.right!)) yield v;
    }

    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.reverseInOrder(root.right!)) yield v;
        yield root.data;
        for (const v of this.reverseInOrder(root.left!)) yield v;
    }
}

class TreeSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size += successful ? 1 : 0;
        return successful;
    }

    delete(val: T): boolean {
        const deleted = this.tree.deleteAll(val);
        this._size -= deleted ? 1 : 0;
        return deleted;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) yield val;
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) yield val;
        return undefined;
    }
}

class TreeMultiSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size++;
        return successful;
    }

    delete(val: T): boolean {
        const successful = this.tree.delete(val);
        if (!successful) return false;
        this._size--;
        return true;
    }

    count(val: T): number {
        const node = this.tree.find(val);
        return node ? node.count : 0;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        yield* this.values();
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) {
            let count = this.count(val);
            while (count--) yield val;
        }
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the multi-set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) {
            let count = this.count(val);
            while (count--) yield val;
        }
        return undefined;
    }
}