Method Find

pkg/segment/set.go:212–236

Find returns the segment or gap whose range contains the given key. If a segment is found, the returned Iterator is non-terminal and the returned GapIterator is terminal. Otherwise, the returned Iterator is terminal and the returned GapIterator is non-terminal.

(key Key)

// returned GapIterator is terminal. Otherwise, the returned Iterator is
// terminal and the returned GapIterator is non-terminal.
func (s *Set) Find(key Key) (Iterator, GapIterator) {
	n := &s.root
	for {
		// Binary search invariant: the correct value of i lies within [lower,
		// upper].
		lower := 0
		upper := n.nrSegments
		for lower < upper {
			i := lower + (upper-lower)/2
			if r := n.keys[i]; key < r.End {
				if key >= r.Start {
					return Iterator{n, i}, GapIterator{}
				}
				upper = i
			} else {
				lower = i + 1
			}
		}
		i := lower
		if !n.hasChildren {
			return Iterator{}, GapIterator{n, i}
		}
		n = n.children[i]
	}
}

// FindSegment returns the segment whose range contains the given key. If no
// such segment exists, FindSegment returns a terminal iterator.