| 203 | |
| 204 | public: |
| 205 | int64_t RunLengthOfEqualsFrom(int64_t base_index, int64_t base_length, |
| 206 | int64_t target_index, int64_t target_length) override { |
| 207 | // Ensure the first search for physical index on the values arrays is safe. |
| 208 | if (base_index >= base_length || target_index >= target_length) { |
| 209 | // Without values on either side, there is no run of equal values. |
| 210 | return 0; |
| 211 | } |
| 212 | |
| 213 | // Translate the two logical indices into physical indices. |
| 214 | int64_t physical_base_index = FindPhysicalIndexOnBase(base_index); |
| 215 | int64_t physical_target_index = FindPhysicalIndexOnTarget(target_index); |
| 216 | |
| 217 | int64_t run_length_of_equals = 0; |
| 218 | // The loop invariant (base_index < base_length && target_index < target_length) |
| 219 | // is valid when the loop starts because of the check above. |
| 220 | for (;;) { |
| 221 | const auto base_run_end = |
| 222 | static_cast<int64_t>(base_run_ends()[physical_base_index]) - base_.offset(); |
| 223 | const auto target_run_end = |
| 224 | static_cast<int64_t>(target_run_ends()[physical_target_index]) - |
| 225 | target_.offset(); |
| 226 | // The end of the runs containing the logical indices, by definition, ends |
| 227 | // after the logical indices. |
| 228 | DCHECK_LT(base_index, base_run_end); |
| 229 | DCHECK_LT(target_index, target_run_end); |
| 230 | |
| 231 | // Compare the physical values that make up the runs containing base_index |
| 232 | // and target_index. |
| 233 | if (!inner_value_comparator_->Equals(physical_base_index, physical_target_index)) { |
| 234 | // First difference found, stop because the run of equal values cannot |
| 235 | // be extended further. |
| 236 | break; |
| 237 | } |
| 238 | |
| 239 | const int64_t base_run = std::min(base_run_end, base_length) - base_index; |
| 240 | const int64_t target_run = std::min(target_run_end, target_length) - target_index; |
| 241 | // Due to the loop-invariant (base_index < base_length && target_index < |
| 242 | // target_length) and properties of the run-ends asserted above, both base_run and |
| 243 | // target_run are strictly greater than zero. |
| 244 | DCHECK_GT(base_run, 0); |
| 245 | DCHECK_GT(target_run, 0); |
| 246 | |
| 247 | // Skip the smallest run (or both runs if they are equal) |
| 248 | const int64_t increment = std::min(base_run, target_run); |
| 249 | physical_base_index += increment == base_run; |
| 250 | physical_target_index += increment == target_run; |
| 251 | |
| 252 | // Since both base_run and target_run are greater than zero, |
| 253 | // increment is also greater than zero... |
| 254 | DCHECK_GT(increment, 0); |
| 255 | // ...which implies that the loop will make progress and eventually terminate |
| 256 | // because base_index or target_index will equal base_length or target_length, |
| 257 | // respectively. |
| 258 | base_index += increment; |
| 259 | target_index += increment; |
| 260 | // The value representing the two runs are equal, so we can assume that at |
| 261 | // least `increment` (size of smallest run) values are equal. |
| 262 | run_length_of_equals += increment; |