1 // Copyright (c) The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 5 #include <util/feefrac.h>
6 7 #include <util/check.h>
8 9 #include <array>
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.
70 if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
71 } while(true);
72 73 // Otherwise compare the better_somewhere values.
74 return better_somewhere[0] <=> better_somewhere[1];
75 }
76