Golang algorithms.Comparable类(方法)实例源码

func (this *BinarySearchTree) _delete(x *Node, key algorithms.Comparable) *Node {
	if x == nil {
		return nil
	}
	cmp := key.CompareTo(x.key)
	if cmp < 0 {
		x.left = this._delete(x.left, key)
	} else if cmp > 0 {
		x.right = this._delete(x.right, key)
	} else {
		if x.right == nil {
			return x.left
		}
		if x.left == nil {
			return x.right
		}
		t := x
		x = this.min(t.right)
		x.right = this.deleteMin(t.right)
		x.left = t.left
	}

	x.size = this.size(x.left) + this.size(x.right) + 1

	return x
}

func (this *BinarySearchTree) RangedSize(low, high algorithms.Comparable) int {
	if high.CompareTo(low) < 0 {
		return 0
	} else if this.Contains(high) {
		return this.Rank(high) - this.Rank(low) + 1
	} else {
		return this.Rank(high) - this.Rank(low)
	}
}

func (this *BinarySearchTree) get(x *Node, key algorithms.Comparable) interface{} {
	if x == nil {
		return nil
	}

	cmp := key.CompareTo(x.key)
	if cmp < 0 {
		return this.get(x.left, key)
	} else if cmp > 0 {
		return this.get(x.right, key)
	} else {
		return x.val
	}
}

func (this *BinarySearchTree) rank(x *Node, key algorithms.Comparable) int {
	if x == nil {
		return 0
	}

	cmp := key.CompareTo(x.key)
	if cmp < 0 {
		return this.rank(x.left, key)
	} else if cmp > 0 {
		return this.rank(x.right, key) + this.size(x.left) + 1
	} else {
		return this.size(x.left)
	}
}

func (this *BinarySearchTree) keys(x *Node, queue *container.Queue, low, high algorithms.Comparable) {
	if x == nil {
		return
	}
	cmplow := low.CompareTo(x.key)
	cmphigh := high.CompareTo(x.key)
	if cmplow < 0 {
		this.keys(x.left, queue, low, high)
	}
	if cmplow <= 0 && cmphigh >= 0 {
		queue.Push(x.key)
	}
	if cmphigh > 0 {
		this.keys(x.right, queue, low, high)
	}
}

func (this *BinarySearchTree) set(x *Node, key algorithms.Comparable, val interface{}) *Node {
	if x == nil {
		return NewNode(key, val, 1)
	}

	cmp := key.CompareTo(x.key)
	if cmp < 0 {
		x.left = this.set(x.left, key, val)
	} else if cmp > 0 {
		x.right = this.set(x.right, key, val)
	} else {
		x.val = val
	}

	x.size = this.size(x.left) + this.size(x.right) + 1

	return x
}

func (this *BinarySearchTree) ceil(x *Node, key algorithms.Comparable) *Node {
	if x == nil {
		return nil
	}

	cmp := key.CompareTo(x.key)
	if cmp == 0 {
		return x
	} else if cmp > 0 {
		return this.ceil(x.right, key)
	} else {
		t := this.ceil(x.left, key)
		if t != nil {
			return t
		} else {
			return x
		}
	}
}

func (this *sorter) Less(v, w algorithms.Comparable) bool {
	return v.CompareTo(w) < 0
}