| 10 | #include <cstddef> |
| 11 | |
| 12 | std::partial_ordering CompareChunks(std::span<const FeeFrac> chunks0, std::span<const FeeFrac> chunks1) |
| 13 | { |
| 14 | /** Array to allow indexed access to input diagrams. */ |
| 15 | const std::array<std::span<const FeeFrac>, 2> chunk = {chunks0, chunks1}; |
| 16 | /** How many elements we have processed in each input. */ |
| 17 | size_t next_index[2] = {0, 0}; |
| 18 | /** Accumulated fee/sizes in diagrams, up to next_index[i] - 1. */ |
| 19 | FeeFrac accum[2]; |
| 20 | /** Whether the corresponding input is strictly better than the other at least in one place. */ |
| 21 | bool better_somewhere[2] = {false, false}; |
| 22 | /** Get the first unprocessed point in diagram number dia. */ |
| 23 | const auto next_point = [&](int dia) { return chunk[dia][next_index[dia]] + accum[dia]; }; |
| 24 | /** Get the last processed point in diagram number dia. */ |
| 25 | const auto prev_point = [&](int dia) { return accum[dia]; }; |
| 26 | /** Move to the next point in diagram number dia. */ |
| 27 | const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; }; |
| 28 | |
| 29 | do { |
| 30 | bool done_0 = next_index[0] == chunk[0].size(); |
| 31 | bool done_1 = next_index[1] == chunk[1].size(); |
| 32 | if (done_0 && done_1) break; |
| 33 | |
| 34 | // Determine which diagram has the first unprocessed point. If a single side is finished, use the |
| 35 | // other one. Only up to one can be done due to check above. |
| 36 | const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size; |
| 37 | |
| 38 | // Let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points |
| 39 | // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we |
| 40 | // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size, |
| 41 | // and can thus be expressed as FeeFracs. |
| 42 | const FeeFrac& point_p = next_point(unproc_side); |
| 43 | const FeeFrac& point_a = prev_point(!unproc_side); |
| 44 | |
| 45 | const auto slope_ap = point_p - point_a; |
| 46 | Assume(slope_ap.size > 0); |
| 47 | auto cmp = std::strong_ordering::equivalent; |
| 48 | if (done_0 || done_1) { |
| 49 | // If a single side has no points left, act as if AB has slope tail_feerate(of 0). |
| 50 | Assume(!(done_0 && done_1)); |
| 51 | cmp = ByRatio{slope_ap} <=> ByRatio{FeeFrac(0, 1)}; |
| 52 | } else { |
| 53 | // If both sides have points left, compute B, and the slope of AB explicitly. |
| 54 | const FeeFrac& point_b = next_point(!unproc_side); |
| 55 | const auto slope_ab = point_b - point_a; |
| 56 | Assume(slope_ab.size >= slope_ap.size); |
| 57 | cmp = ByRatio{slope_ap} <=> ByRatio{slope_ab}; |
| 58 | |
| 59 | // If B and P have the same size, B can be marked as processed (in addition to P, see |
| 60 | // below), as we've already performed a comparison at this size. |
| 61 | if (point_b.size == point_p.size) advance(!unproc_side); |
| 62 | } |
| 63 | // If P lies above AB, unproc_side is better in P. If P lies below AB, then !unproc_side is |
| 64 | // better in P. |
| 65 | if (std::is_gt(cmp)) better_somewhere[unproc_side] = true; |
| 66 | if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true; |
| 67 | advance(unproc_side); |
| 68 | |
| 69 | // If both diagrams are better somewhere, they are incomparable. |