-// Find the first segment in the range [SegBegin,Segments.end()) that
-// intersects with LS. If no intersection is found, return the first SI
-// such that SI.start >= LS.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 < LS.End
-// SegBegin |--...
-// \ .
-// LS ...-|
-//
-// After set::upper_bound, we have SI.start >= LS.start:
-// SI |--...
-// /
-// LS |--...
-//
-// 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 &LS) {
- assert(LS.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 SI = Segments.upper_bound(LS);
- while (SI != SegBegin) {
- --SI;
- if (LS.Start >= SI->End)
- return ++SI;
- }
- return SI;
-}