Repository: etcd-io/etcd
File: pkg/adt/interval_tree.go (Go)

Code before:
	x.parent = y
}

// Len gives the number of elements in the tree
func (ivt *intervalTree) Len() int { return ivt.count }

// Height is the number of levels in the tree; one node has height 1.
func (ivt *intervalTree) Height() int { return ivt.root.height(ivt.sentinel) }

// MaxHeight is the expected maximum tree height given the number of nodes
func (ivt *intervalTree) MaxHeight() int {
	return int((2 * math.Log2(float64(ivt.Len()+1))) + 0.5)
}

// IntervalVisitor is used on tree searches; return false to stop searching.
type IntervalVisitor func(n *IntervalValue) bool

// 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) {
	ivt.root.visit(&ivl, ivt.sentinel, func(n *intervalNode) bool { return ivv(&n.iv) })
}

// find the exact node for a given interval. The implementation follows
// Cormen "Introduction to Algorithms", Chapter 14 Exercise 14.3.5. for
// exact interval matching.
func (ivt *intervalTree) find(ivl Interval) *intervalNode {
	x := ivt.root
	// Search until hit sentinel or exact match.
	for x != ivt.sentinel {
		beginCompare := ivl.Begin.Compare(x.iv.Ivl.Begin)
		endCompare := ivl.End.Compare(x.iv.Ivl.End)
		if beginCompare == 0 && endCompare == 0 {
			return x
		}
		// Split on left endpoint. If left endpoints match,
		// instead split on right endpoints.
		if beginCompare < 0 {
			x = x.left
		} else if beginCompare == 0 {
			if endCompare < 0 {
				x = x.left
			} else {
				x = x.right
			}
		} else {
			x = x.right
		}
	}
	return x
}

Review comment (suggestion):
```suggestion
// find the exact node for a given interval. The implementation follows
// Cormen "Introduction to Algorithms", Chapter 14 Exercise 14.3.5. for
// exact interval matching. The search runs in O(log n) time on an n-node
// interval tree.
```

Code after:
	x.parent = y
}

// Len gives the number of elements in the tree
func (ivt *intervalTree) Len() int { return ivt.count }

// Height is the number of levels in the tree; one node has height 1.
func (ivt *intervalTree) Height() int { return ivt.root.height(ivt.sentinel) }

// MaxHeight is the expected maximum tree height given the number of nodes
func (ivt *intervalTree) MaxHeight() int {
	return int((2 * math.Log2(float64(ivt.Len()+1))) + 0.5)
}

// IntervalVisitor is used on tree searches; return false to stop searching.
type IntervalVisitor func(n *IntervalValue) bool

// 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) {
	ivt.root.visit(&ivl, ivt.sentinel, func(n *intervalNode) bool { return ivv(&n.iv) })
}

// find the exact node for a given interval. The implementation follows
// Cormen "Introduction to Algorithms", Chapter 14 Exercise 14.3.5. for
// exact interval matching. The search runs in O(log n) time on an n-node
// interval tree.
func (ivt *intervalTree) find(ivl Interval) *intervalNode {
	x := ivt.root
	// Search until hit sentinel or exact match.
	for x != ivt.sentinel {
		beginCompare := ivl.Begin.Compare(x.iv.Ivl.Begin)
		endCompare := ivl.End.Compare(x.iv.Ivl.End)
		if beginCompare == 0 && endCompare == 0 {
			return x
		}
		// Split on left endpoint. If left endpoints match,
		// instead split on right endpoints.
		if beginCompare < 0 {
			x = x.left
		} else if beginCompare == 0 {
			if endCompare < 0 {
				x = x.left
			} else {
				x = x.right
			}
		} else {
			x = x.right
		}
	}
	return x