//  delete the key-value pair with the given key rooted at h
func (st *RedBlackBST) delet(h *RBNode, key interface{}) *RBNode {
	if gotype.Compare(key, h.key) < 0 {
		if !st.isRed(h.left) && !st.isRed(h.left.left) {
			h = st.moveRedLeft(h)
		}
		h.left = st.delet(h.left, key)
	} else {
		if st.isRed(h.left) {
			h = st.rotateRight(h)
		}
		if gotype.Compare(key, h.key) == 0 && h.right == nil {
			return nil
		}
		if !st.isRed(h.right) && !st.isRed(h.right.left) {
			h = st.moveRedRight(h)
		}
		if gotype.Compare(key, h.key) == 0 {
			x := st.min(h.right)
			h.key = x.key
			h.val = x.val
			h.right = st.deleteMin(h.right)
		} else {
			h.right = st.delet(h.right, key)
		}
	}
	return st.balance(h)
}

func (self *MaxPQ) sink(k int) {
	for 2*k <= self.n {
		j := 2 * k
		if j < self.n && gotype.Compare(self.pq[j], self.pq[j+1]) < 0 {
			j++
		}
		if gotype.Compare(self.pq[k], self.pq[j]) >= 0 {
			break
		}
		self.pq[k], self.pq[j] = self.pq[j], self.pq[k]
		k = j
	}
}

//  insert the key-value pair in the subtree rooted at h
func (st *RedBlackBST) put(h *RBNode, key interface{}, val interface{}) *RBNode {
	if h == nil {
		return NewRBNode(key, val, RED)
	}
	cmp := gotype.Compare(key, h.key)
	if cmp < 0 {
		h.left = st.put(h.left, key, val)
	} else if cmp > 0 {
		h.right = st.put(h.right, key, val)
	} else {
		h.val = val
	}
	// fix-up any right-leaning links
	if st.isRed(h.right) && !st.isRed(h.left) {
		h = st.rotateLeft(h)
	}
	if st.isRed(h.left) && st.isRed(h.left.left) {
		h = st.rotateRight(h)
	}
	if st.isRed(h.left) && st.isRed(h.right) {
		st.flipColors(h)
	}
	h.n = st.size(h.left) + st.size(h.right) + 1
	return h
}

//  return the value associated with the key, or null if the key is not present
func (st *SequentialSearchST) Get(key interface{}) interface{} {
	for x := st.first; x != nil; x = x.next {
		if cmp := gotype.Compare(key, x.key); cmp == 0 {
			return x.val
		}
	}
	return nil
}

func (st *BinarySearchST) Floor(key interface{}) interface{} {
	i := st.Rank(key)
	if i < st.n && gotype.Compare(key, st.keys[i]) == 0 {
		return st.keys[i]
	}
	if i == 0 {
		return nil
	}
	return st.keys[i-1]
}

// Range search
func (st *BST) RangeSize(lo interface{}, hi interface{}) int {
	if gotype.Compare(lo, hi) > 0 {
		return 0
	}
	if st.Contains(hi) {
		return st.Rank(hi) - st.Rank(lo) + 1
	} else {
		return st.Rank(hi) - st.Rank(lo)
	}
}

func (st *BinarySearchST) Get(key interface{}) interface{} {
	if st.IsEmpty() {
		return nil
	}
	i := st.Rank(key)
	if i < st.n && gotype.Compare(st.keys[i], key) == 0 {
		return st.vals[i]
	}
	return nil
}

// add a key-value pair, replacing old key-value pair if key is already present
func (st *SequentialSearchST) Put(key interface{}, val interface{}) {
	for x := st.first; x != nil; x = x.next {
		if cmp := gotype.Compare(key, x.key); cmp == 0 {
			x.val = val
			return
		}
	}
	st.first = &STNode{key, val, st.first}
	st.n++
}

func (st *SequentialSearchST) delete(x *STNode, key interface{}) *STNode {
	if x == nil {
		return nil
	}
	if cmp := gotype.Compare(key, x.key); cmp == 0 {
		st.n--
		return x.next
	}
	x.next = st.delete(x.next, key)
	return x
}

func (st *BST) get(x *BstNode, key interface{}) interface{} {
	if x == nil {
		return nil
	}
	cmp := gotype.Compare(key, x.key)
	if cmp < 0 {
		return st.get(x.left, key)
	} else if cmp > 0 {
		return st.get(x.right, key)
	}
	return x.val
}

// Range search
func (st *BST) RangeKeys(lo interface{}, hi interface{}) []interface{} {
	queue := make([]interface{}, 0)
	var keys func(*BstNode, interface{}, interface{})
	keys = func(x *BstNode, lo interface{}, hi interface{}) {
		if x == nil {
			return
		}
		cmplo := gotype.Compare(lo, x.key)
		cmphi := gotype.Compare(hi, x.key)
		if cmplo < 0 {
			keys(x.left, lo, hi)
		}
		if cmplo <= 0 && cmphi >= 0 {
			queue = append(queue, x.key)
		}
		if cmphi > 0 {
			keys(x.right, lo, hi)
		}
	}
	keys(st.root, lo, hi)
	return queue
}

//  Number of keys in the subtree less than x.key.
func (st *BST) rank(key interface{}, x *BstNode) int {
	if x == nil {
		return 0
	}
	cmp := gotype.Compare(key, x.key)
	if cmp < 0 {
		return st.rank(key, x.left)
	} else if cmp > 0 {
		return 1 + st.size(x.left) + st.rank(key, x.right)
	} else {
		return st.size(x.left)
	}
}

// value associated with the given key in subtree rooted at x; null if no such key
func (st *RedBlackBST) get(x *RBNode, key interface{}) interface{} {
	var cmp int
	for x != nil {
		cmp = gotype.Compare(key, x.key)
		if cmp < 0 {
			x = x.left
		} else if cmp > 0 {
			x = x.right
		} else {
			return x.val
		}
	}
	return nil
}

func (st *BST) put(x *BstNode, key interface{}, val interface{}) *BstNode {
	if x == nil {
		return NewBstNode(key, val)
	}
	cmp := gotype.Compare(key, x.key)
	if cmp < 0 {
		x.left = st.put(x.left, key, val)
	} else if cmp > 0 {
		x.right = st.put(x.right, key, val)
	} else {
		x.val = val
	}
	x.n = 1 + st.size(x.left) + st.size(x.right)
	return x
}

func (st *BinarySearchST) RangeKeys(lo interface{}, hi interface{}) []interface{} {
	queue := make([]interface{}, 0, 100)
	if lo == nil || hi == nil {
		return nil
	}
	if gotype.Compare(lo, hi) > 0 {
		return nil
	}
	for i := st.Rank(lo); i < st.Rank(hi); i++ {
		queue = append(queue, st.keys[i])
	}
	if st.Contains(hi) {
		queue = append(queue, st.keys[st.Rank(hi)])
	}
	return queue
}

// return the number of keys in the table that are smaller than given key
func (st *BinarySearchST) Rank(key interface{}) int {
	var lo, hi, m, cmp int
	lo, hi = 0, st.n-1
	for lo <= hi { // <=, not <
		m = lo + (hi-lo)/2
		cmp = gotype.Compare(key, st.keys[m])
		if cmp < 0 {
			hi = m - 1
		} else if cmp > 0 {
			lo = m + 1
		} else {
			return m
		}
	}
	return lo
}

func (st *BST) floor(x *BstNode, key interface{}) *BstNode {
	if x == nil {
		return nil
	}
	cmp := gotype.Compare(key, x.key)
	if cmp == 0 {
		return x
	}
	if cmp < 0 {
		return st.floor(x.left, key)
	}
	t := st.floor(x.right, key)
	if t != nil {
		return t
	}
	return x
}

//  the smallest key in the subtree rooted at x greater than or equal to the given key
func (st *RedBlackBST) ceiling(x *RBNode, key interface{}) *RBNode {
	if x == nil {
		return nil
	}
	cmp := gotype.Compare(key, x.key)
	if cmp == 0 {
		return x
	}
	if cmp > 0 {
		return st.ceiling(x.right, key)
	}
	t := st.ceiling(x.left, key)
	if t != nil {
		return t
	} else {
		return x
	}
}

func (st *BST) ceiling(x *BstNode, key interface{}) *BstNode {
	if x == nil {
		return nil
	}
	cmp := gotype.Compare(key, x.key)
	if cmp == 0 {
		return x
	}
	if cmp < 0 {
		t := st.ceiling(x.left, key)
		if t != nil {
			return t
		} else {
			return x
		}
	}
	return st.ceiling(x.right, key)
}

// Remove the key-value pair if present
func (st *BinarySearchST) Delete(key interface{}) {
	if st.IsEmpty() {
		return
	}
	i := st.Rank(key)
	if i == st.n || gotype.Compare(key, st.keys[i]) != 0 {
		return
	}
	for j := i; j < st.n-1; j++ {
		st.keys[j] = st.keys[j+1]
		st.vals[j] = st.vals[j+1]
	}
	st.n--
	st.keys[st.n], st.vals[st.n] = nil, nil

	// resize if 1/4 full
	if st.n > 0 && st.n == len(st.keys)/4 {
		st.resize(len(st.keys) / 2)
	}
}