// Copyright 2016 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package ssa
import "fmt"
const (
rankLeaf rbrank = 1
rankZero rbrank = 0
)
type rbrank int8
// RBTint32 is a red-black tree with data stored at internal nodes,
// following Tarjan, Data Structures and Network Algorithms,
// pp 48-52, using explicit rank instead of red and black.
// Deletion is not yet implemented because it is not yet needed.
// Extra operations glb, lub, glbEq, lubEq are provided for
// use in sparse lookup algorithms.
type RBTint32 struct {
root *node32
// An extra-clever implementation will have special cases
// for small sets, but we are not extra-clever today.
}
func (t *RBTint32) String() string {
if t.root == nil {
return "[]"
}
return "[" + t.root.String() + "]"
}
func (t *node32) String() string {
s := ""
if t.left != nil {
s = t.left.String() + " "
}
s = s + fmt.Sprintf("k=%d,d=%v", t.key, t.data)
if t.right != nil {
s = s + " " + t.right.String()
}
return s
}
type node32 struct {
// Standard conventions hold for left = smaller, right = larger
left, right, parent *node32
data interface{}
key int32
rank rbrank // From Tarjan pp 48-49:
// If x is a node with a parent, then x.rank <= x.parent.rank <= x.rank+1.
// If x is a node with a grandparent, then x.rank < x.parent.parent.rank.
// If x is an "external [null] node", then x.rank = 0 && x.parent.rank = 1.
// Any node with one or more null children should have rank = 1.
}
// makeNode returns a new leaf node with the given key and nil data.
func (t *RBTint32) makeNode(key int32) *node32 {
return &node32{key: key, rank: rankLeaf}
}
// IsEmpty reports whether t is empty.
func (t *RBTint32) IsEmpty() bool {
return t.root == nil
}
// IsSingle reports whether t is a singleton (leaf).
func (t *RBTint32) IsSingle() bool {
return t.root != nil && t.root.isLeaf()
}
// VisitInOrder applies f to the key and data pairs in t,
// with keys ordered from smallest to largest.
func (t *RBTint32) VisitInOrder(f func(int32, interface{})) {
if t.root == nil {
return
}
t.root.visitInOrder(f)
}
func (n *node32) Data() interface{} {
if n == nil {
return nil
}
return n.data
}
func (n *node32) keyAndData() (k int32, d interface{}) {
if n == nil {
k = 0
d = nil
} else {
k = n.key
d = n.data
}
return
}
func (n *node32) Rank() rbrank {
if n == nil {
return 0
}
return n.rank
}
// Find returns the data associated with key in the tree, or
// nil if key is not in the tree.
func (t *RBTint32) Find(key int32) interface{} {
return t.root.find(key).Data()
}
// Insert adds key to the tree and associates key with data.
// If key was already in the tree, it updates the associated data.
// Insert returns the previous data associated with key,
// or nil if key was not present.
// Insert panics if data is nil.
func (t *RBTint32) Insert(key int32, data interface{}) interface{} {
if data == nil {
panic("Cannot insert nil data into tree")
}
n := t.root
var newroot *node32
if n == nil {
n = t.makeNode(key)
newroot = n
} else {
newroot, n = n.insert(key, t)
}
r := n.data
n.data = data
t.root = newroot
return r
}
// Min returns the minimum element of t and its associated data.
// If t is empty, then (0, nil) is returned.
func (t *RBTint32) Min() (k int32, d interface{}) {
return t.root.min().keyAndData()
}
// Max returns the maximum element of t and its associated data.
// If t is empty, then (0, nil) is returned.
func (t *RBTint32) Max() (k int32, d interface{}) {
return t.root.max().keyAndData()
}
// Glb returns the greatest-lower-bound-exclusive of x and its associated
// data. If x has no glb in the tree, then (0, nil) is returned.
func (t *RBTint32) Glb(x int32) (k int32, d interface{}) {
return t.root.glb(x, false).keyAndData()
}
// GlbEq returns the greatest-lower-bound-inclusive of x and its associated
// data. If x has no glbEQ in the tree, then (0, nil) is returned.
func (t *RBTint32) GlbEq(x int32) (k int32, d interface{}) {
return t.root.glb(x, true).keyAndData()
}
// Lub returns the least-upper-bound-exclusive of x and its associated
// data. If x has no lub in the tree, then (0, nil) is returned.
func (t *RBTint32) Lub(x int32) (k int32, d interface{}) {
return t.root.lub(x, false).keyAndData()
}
// LubEq returns the least-upper-bound-inclusive of x and its associated
// data. If x has no lubEq in the tree, then (0, nil) is returned.
func (t *RBTint32) LubEq(x int32) (k int32, d interface{}) {
return t.root.lub(x, true).keyAndData()
}
func (t *node32) isLeaf() bool {
return t.left == nil && t.right == nil
}
func (t *node32) visitInOrder(f func(int32, interface{})) {
if t.left != nil {
t.left.visitInOrder(f)
}
f(t.key, t.data)
if t.right != nil {
t.right.visitInOrder(f)
}
}
func (t *node32) maxChildRank() rbrank {
if t.left == nil {
if t.right == nil {
return rankZero
}
return t.right.rank
}
if t.right == nil {
return t.left.rank
}
if t.right.rank > t.left.rank {
return t.right.rank
}
return t.left.rank
}
func (t *node32) minChildRank() rbrank {
if t.left == nil || t.right == nil {
return rankZero
}
if t.right.rank < t.left.rank {
return t.right.rank
}
return t.left.rank
}
func (t *node32) find(key int32) *node32 {
for t != nil {
if key < t.key {
t = t.left
} else if key > t.key {
t = t.right
} else {
return t
}
}
return nil
}
func (t *node32) min() *node32 {
if t == nil {
return t
}
for t.left != nil {
t = t.left
}
return t
}
func (t *node32) max() *node32 {
if t == nil {
return t
}
for t.right != nil {
t = t.right
}
return t
}
func (t *node32) glb(key int32, allow_eq bool) *node32 {
var best *node32
for t != nil {
if key <= t.key {
if key == t.key && allow_eq {
return t
}
// t is too big, glb is to left.
t = t.left
} else {
// t is a lower bound, record it and seek a better one.
best = t
t = t.right
}
}
return best
}
func (t *node32) lub(key int32, allow_eq bool) *node32 {
var best *node32
for t != nil {
if key >= t.key {
if key == t.key && allow_eq {
return t
}
// t is too small, lub is to right.
t = t.right
} else {
// t is a upper bound, record it and seek a better one.
best = t
t = t.left
}
}
return best
}
func (t *node32) insert(x int32, w *RBTint32) (newroot, newnode *node32) {
// defaults
newroot = t
newnode = t
if x == t.key {
return
}
if x < t.key {
if t.left == nil {
n := w.makeNode(x)
n.parent = t
t.left = n
newnode = n
return
}
var new_l *node32
new_l, newnode = t.left.insert(x, w)
t.left = new_l
new_l.parent = t
newrank := 1 + new_l.maxChildRank()
if newrank > t.rank {
if newrank > 1+t.right.Rank() { // rotations required
if new_l.left.Rank() < new_l.right.Rank() {
// double rotation
t.left = new_l.rightToRoot()
}
newroot = t.leftToRoot()
return
} else {
t.rank = newrank
}
}
} else { // x > t.key
if t.right == nil {
n := w.makeNode(x)
n.parent = t
t.right = n
newnode = n
return
}
var new_r *node32
new_r, newnode = t.right.insert(x, w)
t.right = new_r
new_r.parent = t
newrank := 1 + new_r.maxChildRank()
if newrank > t.rank {
if newrank > 1+t.left.Rank() { // rotations required
if new_r.right.Rank() < new_r.left.Rank() {
// double rotation
t.right = new_r.leftToRoot()
}
newroot = t.rightToRoot()
return
} else {
t.rank = newrank
}
}
}
return
}
func (t *node32) rightToRoot() *node32 {
// this
// left right
// rl rr
//
// becomes
//
// right
// this rr
// left rl
//
right := t.right
rl := right.left
right.parent = t.parent
right.left = t
t.parent = right
// parent's child ptr fixed in caller
t.right = rl
if rl != nil {
rl.parent = t
}
return right
}
func (t *node32) leftToRoot() *node32 {
// this
// left right
// ll lr
//
// becomes
//
// left
// ll this
// lr right
//
left := t.left
lr := left.right
left.parent = t.parent
left.right = t
t.parent = left
// parent's child ptr fixed in caller
t.left = lr
if lr != nil {
lr.parent = t
}
return left
}
// next returns the successor of t in a left-to-right
// walk of the tree in which t is embedded.
func (t *node32) next() *node32 {
// If there is a right child, it is to the right
r := t.right
if r != nil {
return r.min()
}
// if t is p.left, then p, else repeat.
p := t.parent
for p != nil {
if p.left == t {
return p
}
t = p
p = t.parent
}
return nil
}
// prev returns the predecessor of t in a left-to-right
// walk of the tree in which t is embedded.
func (t *node32) prev() *node32 {
// If there is a left child, it is to the left
l := t.left
if l != nil {
return l.max()
}
// if t is p.right, then p, else repeat.
p := t.parent
for p != nil {
if p.right == t {
return p
}
t = p
p = t.parent
}
return nil
}