Return 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, and the second is no
()
| 309 | // The last triple is a dummy, (len(a), len(b), 0), and is the only |
| 310 | // triple with n==0. |
| 311 | func (m *SequenceMatcher) GetMatchingBlocks() []Match { |
| 312 | if m.matchingBlocks != nil { |
| 313 | return m.matchingBlocks |
| 314 | } |
| 315 | |
| 316 | var matchBlocks func(alo, ahi, blo, bhi int, matched []Match) []Match |
| 317 | matchBlocks = func(alo, ahi, blo, bhi int, matched []Match) []Match { |
| 318 | match := m.findLongestMatch(alo, ahi, blo, bhi) |
| 319 | i, j, k := match.A, match.B, match.Size |
| 320 | if match.Size > 0 { |
| 321 | if alo < i && blo < j { |
| 322 | matched = matchBlocks(alo, i, blo, j, matched) |
| 323 | } |
| 324 | matched = append(matched, match) |
| 325 | if i+k < ahi && j+k < bhi { |
| 326 | matched = matchBlocks(i+k, ahi, j+k, bhi, matched) |
| 327 | } |
| 328 | } |
| 329 | return matched |
| 330 | } |
| 331 | matched := matchBlocks(0, len(m.a), 0, len(m.b), nil) |
| 332 | |
| 333 | // It's possible that we have adjacent equal blocks in the |
| 334 | // matching_blocks list now. |
| 335 | nonAdjacent := []Match{} |
| 336 | i1, j1, k1 := 0, 0, 0 |
| 337 | for _, b := range matched { |
| 338 | // Is this block adjacent to i1, j1, k1? |
| 339 | i2, j2, k2 := b.A, b.B, b.Size |
| 340 | if i1+k1 == i2 && j1+k1 == j2 { |
| 341 | // Yes, so collapse them -- this just increases the length of |
| 342 | // the first block by the length of the second, and the first |
| 343 | // block so lengthened remains the block to compare against. |
| 344 | k1 += k2 |
| 345 | } else { |
| 346 | // Not adjacent. Remember the first block (k1==0 means it's |
| 347 | // the dummy we started with), and make the second block the |
| 348 | // new block to compare against. |
| 349 | if k1 > 0 { |
| 350 | nonAdjacent = append(nonAdjacent, Match{i1, j1, k1}) |
| 351 | } |
| 352 | i1, j1, k1 = i2, j2, k2 |
| 353 | } |
| 354 | } |
| 355 | if k1 > 0 { |
| 356 | nonAdjacent = append(nonAdjacent, Match{i1, j1, k1}) |
| 357 | } |
| 358 | |
| 359 | nonAdjacent = append(nonAdjacent, Match{len(m.a), len(m.b), 0}) |
| 360 | m.matchingBlocks = nonAdjacent |
| 361 | return m.matchingBlocks |
| 362 | } |
| 363 | |
| 364 | // Return list of 5-tuples describing how to turn a into b. |
| 365 | // |
no test coverage detected