-// Find the first segment in the range [segBegin,segments_.end()) that
-// intersects with seg. If no intersection is found, return the first segI
-// such that segI.start >= seg.end
-//
-// This logic is tied to the underlying LiveSegments data structure. For now, we
-// use set::upper_bound to find the nearest starting position,
-// then reverse iterate to find the first overlap.
-//
-// Upon entry we have segBegin.start < seg.end
-// seg |--...
-// \ .
-// lvr ...-|
-//
-// After set::upper_bound, we have segI.start >= seg.start:
-// seg |--...
-// /
-// lvr |--...
-//
-// Assuming intervals are disjoint, if an intersection exists, it must be the
-// segment found or the one immediately preceeding it. We continue reverse
-// iterating to return the first overlapping segment.
-LiveIntervalUnion::SegmentIter
-LiveIntervalUnion::upperBound(SegmentIter segBegin,
- const LiveSegment &seg) {
- assert(seg.end > segBegin->start && "segment iterator precondition");
- // get the next LIU segment such that segI->start is not less than seg.start
- //
- // FIXME: Once we have a B+tree, we can make good use of segBegin as a hint to
- // upper_bound. For now, we're forced to search again from the root each time.
- SegmentIter segI = segments_.upper_bound(seg);
- while (segI != segBegin) {
- --segI;
- if (seg.start >= segI->end)
- return ++segI;
- }
- return segI;
-}