| 428 | } |
| 429 | |
| 430 | void Next() { |
| 431 | ++edit_count_; |
| 432 | // base_begin_ is used as a dummy value here since Iterator may not be default |
| 433 | // constructible. The newly allocated range is completely overwritten below. |
| 434 | endpoint_base_.resize(StorageOffset(edit_count_ + 1), base_begin_); |
| 435 | insert_.resize(StorageOffset(edit_count_ + 1), false); |
| 436 | |
| 437 | auto previous_offset = StorageOffset(edit_count_ - 1); |
| 438 | auto current_offset = StorageOffset(edit_count_); |
| 439 | |
| 440 | // try deleting from base first |
| 441 | for (int64_t i = 0, i_out = 0; i < edit_count_; ++i, ++i_out) { |
| 442 | auto previous_endpoint = GetEditPoint(edit_count_ - 1, i + previous_offset); |
| 443 | endpoint_base_[i_out + current_offset] = DeleteOne(previous_endpoint).base; |
| 444 | } |
| 445 | |
| 446 | // check if inserting from target could do better |
| 447 | for (int64_t i = 0, i_out = 1; i < edit_count_; ++i, ++i_out) { |
| 448 | // retrieve the previously computed best endpoint for (edit_count_, i_out) |
| 449 | // for comparison with the best endpoint achievable with an insertion |
| 450 | auto endpoint_after_deletion = GetEditPoint(edit_count_, i_out + current_offset); |
| 451 | |
| 452 | auto previous_endpoint = GetEditPoint(edit_count_ - 1, i + previous_offset); |
| 453 | auto endpoint_after_insertion = InsertOne(previous_endpoint); |
| 454 | |
| 455 | if (endpoint_after_insertion.base - endpoint_after_deletion.base >= 0) { |
| 456 | // insertion was more efficient; keep it and mark the insertion in insert_ |
| 457 | insert_[i_out + current_offset] = true; |
| 458 | endpoint_base_[i_out + current_offset] = endpoint_after_insertion.base; |
| 459 | } |
| 460 | } |
| 461 | |
| 462 | // check for completion |
| 463 | EditPoint finish = {base_end_, target_end_}; |
| 464 | for (int64_t i_out = 0; i_out < edit_count_ + 1; ++i_out) { |
| 465 | if (GetEditPoint(edit_count_, i_out + current_offset) == finish) { |
| 466 | finish_index_ = i_out + current_offset; |
| 467 | return; |
| 468 | } |
| 469 | } |
| 470 | } |
| 471 | |
| 472 | bool Done() { return finish_index_ != -1; } |
| 473 | |