/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/cdv/nofrillsprecisemerge.py

  • Committer: Aaron Bentley
  • Date: 2006-05-23 01:07:31 UTC
  • mto: This revision was merged to the branch mainline in revision 1727.
  • Revision ID: aaron.bentley@utoronto.ca-20060523010731-8ffa480f08c46c21
Reoganize patience-related code

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/cdv/nofrillsprecisemerge.py
1
 
from sets import Set as set
2
 
from copy import copy
3
 
from bisect import bisect
4
 
 
5
 
def unique_lcs(a, b):
6
 
    """Find the longest common subset for unique lines.
7
 
 
8
 
    :param a: An indexable object (such as string or list of strings)
9
 
    :param b: Another indexable object (such as string or list of strings)
10
 
    :return: A list of tuples, one for each line which is matched.
11
 
            [(line_in_a, line_in_b), ...]
12
 
 
13
 
    This only matches lines which are unique on both sides.
14
 
    This helps prevent common lines from over influencing match
15
 
    results.
16
 
    The longest common subset uses the Patience Sorting algorithm:
17
 
    http://en.wikipedia.org/wiki/Patience_sorting
18
 
    """
19
 
    # set index[line in a] = position of line in a unless
20
 
    # unless a is a duplicate, in which case it's set to None
21
 
    index = {}
22
 
    for i in xrange(len(a)):
23
 
        line = a[i]
24
 
        if line in index:
25
 
            index[line] = None
26
 
        else:
27
 
            index[line]= i
28
 
    # make btoa[i] = position of line i in a, unless
29
 
    # that line doesn't occur exactly once in both, 
30
 
    # in which case it's set to None
31
 
    btoa = [None] * len(b)
32
 
    index2 = {}
33
 
    for pos, line in enumerate(b):
34
 
        next = index.get(line)
35
 
        if next is not None:
36
 
            if line in index2:
37
 
                # unset the previous mapping, which we now know to
38
 
                # be invalid because the line isn't unique
39
 
                btoa[index2[line]] = None
40
 
                del index[line]
41
 
            else:
42
 
                index2[line] = pos
43
 
                btoa[pos] = next
44
 
    # this is the Patience sorting algorithm
45
 
    # see http://en.wikipedia.org/wiki/Patience_sorting
46
 
    backpointers = [None] * len(b)
47
 
    stacks = []
48
 
    lasts = []
49
 
    k = 0
50
 
    for bpos, apos in enumerate(btoa):
51
 
        if apos is None:
52
 
            continue
53
 
        # as an optimization, check if the next line comes at the end,
54
 
        # because it usually does
55
 
        if stacks and stacks[-1] < apos:
56
 
            k = len(stacks)
57
 
        # as an optimization, check if the next line comes right after
58
 
        # the previous line, because usually it does
59
 
        elif stacks and stacks[k] < apos and (k == len(stacks) - 1 or stacks[k+1] > apos):
60
 
            k += 1
61
 
        else:
62
 
            k = bisect(stacks, apos)
63
 
        if k > 0:
64
 
            backpointers[bpos] = lasts[k-1]
65
 
        if k < len(stacks):
66
 
            stacks[k] = apos
67
 
            lasts[k] = bpos
68
 
        else:
69
 
            stacks.append(apos)
70
 
            lasts.append(bpos)
71
 
    if len(lasts) == 0:
72
 
        return []
73
 
    result = []
74
 
    k = lasts[-1]
75
 
    while k is not None:
76
 
        result.append((btoa[k], k))
77
 
        k = backpointers[k]
78
 
    result.reverse()
79
 
    return result
80
 
 
81
 
assert unique_lcs('', '') == []
82
 
assert unique_lcs('a', 'a') == [(0, 0)]
83
 
assert unique_lcs('a', 'b') == []
84
 
assert unique_lcs('ab', 'ab') == [(0, 0), (1, 1)]
85
 
assert unique_lcs('abcde', 'cdeab') == [(2, 0), (3, 1), (4, 2)]
86
 
assert unique_lcs('cdeab', 'abcde') == [(0, 2), (1, 3), (2, 4)]
87
 
assert unique_lcs('abXde', 'abYde') == [(0, 0), (1, 1), (3, 3), (4, 4)]
88
 
assert unique_lcs('acbac', 'abc') == [(2, 1)]
89
 
 
90
 
def recurse_matches(a, b, ahi, bhi, answer, maxrecursion):
91
 
    """Find all of the matching text in the lines of a and b.
92
 
 
93
 
    :param a: A sequence
94
 
    :param b: Another sequence
95
 
    :param ahi: The maximum length of a to check, typically len(a)
96
 
    :param bhi: The maximum length of b to check, typically len(b)
97
 
    :param answer: The return array. Will be filled with tuples
98
 
                   indicating [(line_in_a), (line_in_b)]
99
 
    :param maxrecursion: The maximum depth to recurse.
100
 
                         Must be a positive integer.
101
 
    :return: None, the return value is in the parameter answer, which
102
 
             should be a list
103
 
 
104
 
    """
105
 
    oldlen = len(answer)
106
 
    if maxrecursion < 0:
107
 
        # this will never happen normally, this check is to prevent DOS attacks
108
 
        return
109
 
    oldlength = len(answer)
110
 
    if len(answer) == 0:
111
 
        alo, blo = 0, 0
112
 
    else:
113
 
        alo, blo = answer[-1]
114
 
        alo += 1
115
 
        blo += 1
116
 
    if alo == ahi or blo == bhi:
117
 
        return
118
 
    for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
119
 
        # recurse between lines which are unique in each file and match
120
 
        apos += alo
121
 
        bpos += blo
122
 
        recurse_matches(a, b, apos, bpos, answer, maxrecursion - 1)
123
 
        answer.append((apos, bpos))
124
 
    if len(answer) > oldlength:
125
 
        # find matches between the last match and the end
126
 
        recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
127
 
    elif a[alo] == b[blo]:
128
 
        # find matching lines at the very beginning
129
 
        while alo < ahi and blo < bhi and a[alo] == b[blo]:
130
 
            answer.append((alo, blo))
131
 
            alo += 1
132
 
            blo += 1
133
 
        recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
134
 
    elif a[ahi - 1] == b[bhi - 1]:
135
 
        # find matching lines at the very end
136
 
        nahi = ahi - 1
137
 
        nbhi = bhi - 1
138
 
        while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
139
 
            nahi -= 1
140
 
            nbhi -= 1
141
 
        recurse_matches(a, b, nahi, nbhi, answer, maxrecursion - 1)
142
 
        for i in xrange(ahi - nahi):
143
 
            answer.append((nahi + i, nbhi + i))
144
 
 
145
 
a1 = []
146
 
recurse_matches(['a', None, 'b', None, 'c'], ['a', 'a', 'b', 'c', 'c'], 5, 5, a1, 10)
147
 
assert a1 == [(0, 0), (2, 2), (4, 4)]
148
 
a2 = []
149
 
recurse_matches(['a', 'c', 'b', 'a', 'c'], ['a', 'b', 'c'], 5, 3, a2, 10)
150
 
assert  a2 == [(0, 0), (2, 1), (4, 2)]
151
 
 
152
 
a3 = []
153
 
recurse_matches(['a', 'B', 'c', 'c', 'D', 'e'], ['a', 'b', 'c', 'c', 'd', 'e'], 6, 6, a3, 10)
154
 
# FIXME: recurse_matches won't match non-unique lines, surrounded by bogus text
155
 
# This is what it should be
156
 
#assert a2 == [(0,0), (2,2), (3,3), (5,5)]
157
 
# This is what it currently gives:
158
 
assert a3 == [(0,0), (5,5)]