| 1 | package main |
| 2 | |
| 3 | import "slices" |
| 4 | |
| 5 | // Interval math shared by the trajectory summarizer: wall-clock spans, |
| 6 | // overlap-free unions, and subtraction for the disjoint wall decomposition. |
| 7 | |
| 8 | // intervalSpan returns the batch's wall clock (max end − min start) and |
| 9 | // whether any two intervals actually overlapped (true parallelism). |
| 10 | func intervalSpan(intervals [][2]int64) (wall int64, overlapped bool) { |
| 11 | sorted := append([][2]int64(nil), intervals...) |
| 12 | slices.SortFunc(sorted, func(a, b [2]int64) int { |
| 13 | switch { |
| 14 | case a[0] != b[0]: |
| 15 | return int(a[0] - b[0]) |
| 16 | default: |
| 17 | return int(a[1] - b[1]) |
| 18 | } |
| 19 | }) |
| 20 | minStart, maxEnd := sorted[0][0], sorted[0][1] |
| 21 | for _, iv := range sorted[1:] { |
| 22 | if iv[0] < maxEnd { |
| 23 | overlapped = true |
| 24 | } |
| 25 | maxEnd = max(maxEnd, iv[1]) |
| 26 | } |
| 27 | return maxEnd - minStart, overlapped |
| 28 | } |
| 29 | |
| 30 | // intervalUnion is the merged length of all intervals, so concurrent tool |
| 31 | // executions count wall-clock once. |
| 32 | func intervalUnion(intervals [][2]int64) int64 { |
| 33 | return ivsLen(mergeIntervals(intervals)) |
| 34 | } |
| 35 | |
| 36 | // mergeIntervals returns a sorted, overlap-free copy of intervals. |
| 37 | func mergeIntervals(intervals [][2]int64) [][2]int64 { |
| 38 | if len(intervals) == 0 { |
| 39 | return nil |
| 40 | } |
| 41 | sorted := append([][2]int64(nil), intervals...) |
| 42 | slices.SortFunc(sorted, func(a, b [2]int64) int { |
| 43 | switch { |
| 44 | case a[0] != b[0]: |
| 45 | return int(a[0] - b[0]) |
| 46 | default: |
| 47 | return int(a[1] - b[1]) |
| 48 | } |
| 49 | }) |
| 50 | out := [][2]int64{sorted[0]} |
| 51 | for _, iv := range sorted[1:] { |
| 52 | if last := &out[len(out)-1]; iv[0] <= last[1] { |
| 53 | last[1] = max(last[1], iv[1]) |
| 54 | continue |
| 55 | } |
| 56 | out = append(out, iv) |
| 57 | } |
| 58 | return out |
| 59 | } |
| 60 | |
| 61 | // clipIntervals returns base minus covered; both are merged internally. |
| 62 | func clipIntervals(base, covered [][2]int64) [][2]int64 { |
| 63 | base = mergeIntervals(base) |
| 64 | covered = mergeIntervals(covered) |
| 65 | var out [][2]int64 |
| 66 | j := 0 |
| 67 | for _, iv := range base { |
| 68 | lo := iv[0] |
| 69 | for j < len(covered) && covered[j][1] <= lo { |
| 70 | j++ |
| 71 | } |
| 72 | for k := j; k < len(covered) && covered[k][0] < iv[1]; k++ { |
| 73 | if covered[k][0] > lo { |
| 74 | out = append(out, [2]int64{lo, covered[k][0]}) |
| 75 | } |
| 76 | if lo = max(lo, covered[k][1]); lo >= iv[1] { |
| 77 | break |
| 78 | } |
| 79 | } |
| 80 | if lo < iv[1] { |
| 81 | out = append(out, [2]int64{lo, iv[1]}) |
| 82 | } |
| 83 | } |
| 84 | return out |
| 85 | } |
| 86 | |
| 87 | func ivsLen(intervals [][2]int64) int64 { |
| 88 | var total int64 |
| 89 | for _, iv := range intervals { |
| 90 | total += iv[1] - iv[0] |
| 91 | } |
| 92 | return total |
| 93 | } |
| 94 |