kubernetes/vendor/go.etcd.io/etcd/pkg/v3/adt/interval_tree.go

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 {}