Path 1: 213 calls (0.49)

list (213) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 2: 141 calls (0.32)

list (141) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 3: 19 calls (0.04)

list (19) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 4: 12 calls (0.03)

list (12) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 5: 12 calls (0.03)

list (12) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 6: 11 calls (0.03)

list (11) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 7: 8 calls (0.02)

list (8) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 8: 8 calls (0.02)

list (8) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 9: 6 calls (0.01)

list (6) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 10: 4 calls (0.01)

list (4) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 11: 2 calls (0.0)

list (2) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 12: 1 calls (0.0)

list (1) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks

Path 13: 1 calls (0.0)

list (1) 

1def get_matching_blocks(self):
2        """Return list of triples describing matching subsequences.
3
4        Each triple is of the form (i, j, n), and means that
5        a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
6        i and in j.  New in Python 2.5, it's also guaranteed that if
7        (i, j, n) and (i', j', n') are adjacent triples in the list, and
8        the second is not the last triple in the list, then i+n != i' or
9        j+n != j'.  IOW, adjacent triples never describe adjacent equal
10        blocks.
11
12        The last triple is a dummy, (len(a), len(b), 0), and is the only
13        triple with n==0.
14
15        >>> s = SequenceMatcher(None, "abxcd", "abcd")
16        >>> list(s.get_matching_blocks())
17        [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
18        """
19
20        if self.matching_blocks is not None:
21            return self.matching_blocks
22        la, lb = len(self.a), len(self.b)
23
24        # This is most naturally expressed as a recursive algorithm, but
25        # at least one user bumped into extreme use cases that exceeded
26        # the recursion limit on their box.  So, now we maintain a list
27        # ('queue`) of blocks we still need to look at, and append partial
28        # results to `matching_blocks` in a loop; the matches are sorted
29        # at the end.
30        queue = [(0, la, 0, lb)]
31        matching_blocks = []
32        while queue:
33            alo, ahi, blo, bhi = queue.pop()
34            i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
35            # a[alo:i] vs b[blo:j] unknown
36            # a[i:i+k] same as b[j:j+k]
37            # a[i+k:ahi] vs b[j+k:bhi] unknown
38            if k:   # if k is 0, there was no matching block
39                matching_blocks.append(x)
40                if alo < i and blo < j:
41                    queue.append((alo, i, blo, j))
42                if i+k < ahi and j+k < bhi:
43                    queue.append((i+k, ahi, j+k, bhi))
44        matching_blocks.sort()
45
46        # It's possible that we have adjacent equal blocks in the
47        # matching_blocks list now.  Starting with 2.5, this code was added
48        # to collapse them.
49        i1 = j1 = k1 = 0
50        non_adjacent = []
51        for i2, j2, k2 in matching_blocks:
52            # Is this block adjacent to i1, j1, k1?
53            if i1 + k1 == i2 and j1 + k1 == j2:
54                # Yes, so collapse them -- this just increases the length of
55                # the first block by the length of the second, and the first
56                # block so lengthened remains the block to compare against.
57                k1 += k2
58            else:
59                # Not adjacent.  Remember the first block (k1==0 means it's
60                # the dummy we started with), and make the second block the
61                # new block to compare against.
62                if k1:
63                    non_adjacent.append((i1, j1, k1))
64                i1, j1, k1 = i2, j2, k2
65        if k1:
66            non_adjacent.append((i1, j1, k1))
67
68        non_adjacent.append( (la, lb, 0) )
69        self.matching_blocks = list(map(Match._make, non_adjacent))
70        return self.matching_blocks