map2SegmentLists

Low level routine for performing a binary operation on a pair of segment lists.

Assumes both lists are properly coalesced - NOT CHECKED. Violating this assumption is UB.

The resulting segment list is defined as follows. (This is a definition of the result, not the algorithm to calculate it.) For each pair of segments l and r from the left and right lists (respectively):

• let i be the intersection between l.interval and r.interval.

• if i is not empty, let o be the output of op(l.value, r.value, i).

• if o is not null, the result will contain a segment with value o on the interval i. Additionally, for each pair of segment s in either list and gap in the other list:

• let i be the intersection between s.interval and the gap.

• if i is not empty, let o be the output of either op(s.value, null, i) or op(null, s.value, i), depending on which list the segment came from.

• if o is not null, the result will contain a segment with value o on the interval i.

This routine performs a single pass down each list, with a computational complexity proportional to the total number of segments in both lists.