GetMatchingBlocks returns a list of triples describing matching subsequences. Each triple is of the form (i, j, n), and means that a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in i and in j. It's also guaranteed that if (i, j, n) and (i', j', n') are adjacent triples in the list,
()
| 369 | // The last triple is a dummy, (len(a), len(b), 0), and is the only |
| 370 | // triple with n==0. |
| 371 | func (m *SequenceMatcher) GetMatchingBlocks() []Match { |
| 372 | if m.matchingBlocks != nil { |
| 373 | return m.matchingBlocks |
| 374 | } |
| 375 | |
| 376 | var matchBlocks func(alo, ahi, blo, bhi int, matched []Match) []Match |
| 377 | matchBlocks = func(alo, ahi, blo, bhi int, matched []Match) []Match { |
| 378 | match := m.findLongestMatch(alo, ahi, blo, bhi) |
| 379 | i, j, k := match.A, match.B, match.Size |
| 380 | if match.Size > 0 { |
| 381 | if alo < i && blo < j { |
| 382 | matched = matchBlocks(alo, i, blo, j, matched) |
| 383 | } |
| 384 | matched = append(matched, match) |
| 385 | if i+k < ahi && j+k < bhi { |
| 386 | matched = matchBlocks(i+k, ahi, j+k, bhi, matched) |
| 387 | } |
| 388 | } |
| 389 | return matched |
| 390 | } |
| 391 | matched := matchBlocks(0, len(m.a), 0, len(m.b), nil) |
| 392 | |
| 393 | // It's possible that we have adjacent equal blocks in the |
| 394 | // matching_blocks list now. |
| 395 | var nonAdjacent []Match |
| 396 | i1, j1, k1 := 0, 0, 0 |
| 397 | for _, b := range matched { |
| 398 | // Is this block adjacent to i1, j1, k1? |
| 399 | i2, j2, k2 := b.A, b.B, b.Size |
| 400 | if i1+k1 == i2 && j1+k1 == j2 { |
| 401 | // Yes, so collapse them -- this just increases the length of |
| 402 | // the first block by the length of the second, and the first |
| 403 | // block so lengthened remains the block to compare against. |
| 404 | k1 += k2 |
| 405 | } else { |
| 406 | // Not adjacent. Remember the first block (k1==0 means it's |
| 407 | // the dummy we started with), and make the second block the |
| 408 | // new block to compare against. |
| 409 | if k1 > 0 { |
| 410 | nonAdjacent = append(nonAdjacent, Match{i1, j1, k1}) |
| 411 | } |
| 412 | i1, j1, k1 = i2, j2, k2 |
| 413 | } |
| 414 | } |
| 415 | if k1 > 0 { |
| 416 | nonAdjacent = append(nonAdjacent, Match{i1, j1, k1}) |
| 417 | } |
| 418 | |
| 419 | nonAdjacent = append(nonAdjacent, Match{len(m.a), len(m.b), 0}) |
| 420 | m.matchingBlocks = nonAdjacent |
| 421 | return m.matchingBlocks |
| 422 | } |
| 423 | |
| 424 | // GetOpCodes returns a list of 5-tuples describing how to turn a into b. |
| 425 | // |
no test coverage detected