type Comparable … type rbcolor … const black … const red … func (c rbcolor) String() string { … } type Interval … // Compare on an interval gives == if the interval overlaps. func (ivl *Interval) Compare(c Comparable) int { … } type intervalNode … func (x *intervalNode) color(sentinel *intervalNode) rbcolor { … } func (x *intervalNode) height(sentinel *intervalNode) int { … } func (x *intervalNode) min(sentinel *intervalNode) *intervalNode { … } // successor is the next in-order node in the tree func (x *intervalNode) successor(sentinel *intervalNode) *intervalNode { … } // updateMax updates the maximum values for a node and its ancestors func (x *intervalNode) updateMax(sentinel *intervalNode) { … } type nodeVisitor … // visit will call a node visitor on each node that overlaps the given interval func (x *intervalNode) visit(iv *Interval, sentinel *intervalNode, nv nodeVisitor) bool { … } type IntervalValue … type IntervalTree … // NewIntervalTree returns a new interval tree. func NewIntervalTree() IntervalTree { … } type intervalTree … // Delete removes the node with the given interval from the tree, returning // true if a node is in fact removed. func (ivt *intervalTree) Delete(ivl Interval) bool { … } // "Introduction to Algorithms" (Cormen et al, 3rd ed.), chapter 13.4, p326 // // RB-DELETE-FIXUP(T, z) // // while x ≠ T.root and x.color == BLACK // if x == x.p.left // w = x.p.right // if w.color == RED // w.color = BLACK // x.p.color = RED // LEFT-ROTATE(T, x, p) // if w.left.color == BLACK and w.right.color == BLACK // w.color = RED // x = x.p // else if w.right.color == BLACK // w.left.color = BLACK // w.color = RED // RIGHT-ROTATE(T, w) // w = w.p.right // w.color = x.p.color // x.p.color = BLACK // LEFT-ROTATE(T, w.p) // x = T.root // else // w = x.p.left // if w.color == RED // w.color = BLACK // x.p.color = RED // RIGHT-ROTATE(T, x, p) // if w.right.color == BLACK and w.left.color == BLACK // w.color = RED // x = x.p // else if w.left.color == BLACK // w.right.color = BLACK // w.color = RED // LEFT-ROTATE(T, w) // w = w.p.left // w.color = x.p.color // x.p.color = BLACK // RIGHT-ROTATE(T, w.p) // x = T.root // // x.color = BLACK func (ivt *intervalTree) deleteFixup(x *intervalNode) { … } func (ivt *intervalTree) createIntervalNode(ivl Interval, val interface{ … } // Insert adds a node with the given interval into the tree. func (ivt *intervalTree) Insert(ivl Interval, val interface{ … } // "Introduction to Algorithms" (Cormen et al, 3rd ed.), chapter 13.3, p316 // // RB-INSERT-FIXUP(T, z) // // while z.p.color == RED // if z.p == z.p.p.left // y = z.p.p.right // if y.color == RED // z.p.color = BLACK // y.color = BLACK // z.p.p.color = RED // z = z.p.p // else if z == z.p.right // z = z.p // LEFT-ROTATE(T, z) // z.p.color = BLACK // z.p.p.color = RED // RIGHT-ROTATE(T, z.p.p) // else // y = z.p.p.left // if y.color == RED // z.p.color = BLACK // y.color = BLACK // z.p.p.color = RED // z = z.p.p // else if z == z.p.right // z = z.p // RIGHT-ROTATE(T, z) // z.p.color = BLACK // z.p.p.color = RED // LEFT-ROTATE(T, z.p.p) // // T.root.color = BLACK func (ivt *intervalTree) insertFixup(z *intervalNode) { … } // rotateLeft moves x so it is left of its right child // // "Introduction to Algorithms" (Cormen et al, 3rd ed.), chapter 13.2, p313 // // LEFT-ROTATE(T, x) // // y = x.right // x.right = y.left // // if y.left ≠ T.nil // y.left.p = x // // y.p = x.p // // if x.p == T.nil // T.root = y // else if x == x.p.left // x.p.left = y // else // x.p.right = y // // y.left = x // x.p = y func (ivt *intervalTree) rotateLeft(x *intervalNode) { … } // rotateRight moves x so it is right of its left child // // RIGHT-ROTATE(T, x) // // y = x.left // x.left = y.right // // if y.right ≠ T.nil // y.right.p = x // // y.p = x.p // // if x.p == T.nil // T.root = y // else if x == x.p.right // x.p.right = y // else // x.p.left = y // // y.right = x // x.p = y func (ivt *intervalTree) rotateRight(x *intervalNode) { … } // replaceParent replaces x's parent with y func (ivt *intervalTree) replaceParent(x *intervalNode, y *intervalNode) { … } // Len gives the number of elements in the tree func (ivt *intervalTree) Len() int { … } // Height is the number of levels in the tree; one node has height 1. func (ivt *intervalTree) Height() int { … } // MaxHeight is the expected maximum tree height given the number of nodes func (ivt *intervalTree) MaxHeight() int { … } type IntervalVisitor … // Visit calls a visitor function on every tree node intersecting the given interval. // It will visit each interval [x, y) in ascending order sorted on x. func (ivt *intervalTree) Visit(ivl Interval, ivv IntervalVisitor) { … } // find the exact node for a given interval func (ivt *intervalTree) find(ivl Interval) *intervalNode { … } // Find gets the IntervalValue for the node matching the given interval func (ivt *intervalTree) Find(ivl Interval) (ret *IntervalValue) { … } // Intersects returns true if there is some tree node intersecting the given interval. func (ivt *intervalTree) Intersects(iv Interval) bool { … } // Contains returns true if the interval tree's keys cover the entire given interval. func (ivt *intervalTree) Contains(ivl Interval) bool { … } // Stab returns a slice with all elements in the tree intersecting the interval. func (ivt *intervalTree) Stab(iv Interval) (ivs []*IntervalValue) { … } // Union merges a given interval tree into the receiver. func (ivt *intervalTree) Union(inIvt IntervalTree, ivl Interval) { … } type visitedInterval … func (vi visitedInterval) String() string { … } // visitLevel traverses tree in level order. // used for testing func (ivt *intervalTree) visitLevel() []visitedInterval { … } type StringComparable … func (s StringComparable) Compare(c Comparable) int { … } func NewStringInterval(begin, end string) Interval { … } func NewStringPoint(s string) Interval { … } type StringAffineComparable … func (s StringAffineComparable) Compare(c Comparable) int { … } func NewStringAffineInterval(begin, end string) Interval { … } func NewStringAffinePoint(s string) Interval { … } func NewInt64Interval(a int64, b int64) Interval { … } func newInt64EmptyInterval() Interval { … } func NewInt64Point(a int64) Interval { … } type Int64Comparable … func (v Int64Comparable) Compare(c Comparable) int { … } type BytesAffineComparable … func (b BytesAffineComparable) Compare(c Comparable) int { … } func NewBytesAffineInterval(begin, end []byte) Interval { … } func NewBytesAffinePoint(b []byte) Interval { … }
Codebase Browser
kubernetes