blob: fc9cc71ba036bf54596e29a6b24836f9ed293603 [file] [log] [blame]
 // 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 }