equal
deleted
inserted
replaced
79 gy = y.next() |
79 gy = y.next() |
80 else: |
80 else: |
81 gx = x.next() |
81 gx = x.next() |
82 except StopIteration: |
82 except StopIteration: |
83 return None |
83 return None |
|
84 |
|
85 def symmetricdifference(a, b, pfunc): |
|
86 """symmetric difference of the sets of ancestors of a and b |
|
87 |
|
88 I.e. revisions that are ancestors of a or b, but not both. |
|
89 """ |
|
90 # basic idea: |
|
91 # - mark a and b with different colors |
|
92 # - walk the graph in topological order with the help of a heap; |
|
93 # for each revision r: |
|
94 # - if r has only one color, we want to return it |
|
95 # - add colors[r] to its parents |
|
96 # |
|
97 # We keep track of the number of revisions in the heap that |
|
98 # we may be interested in. We stop walking the graph as soon |
|
99 # as this number reaches 0. |
|
100 WHITE = 1 |
|
101 BLACK = 2 |
|
102 ALLCOLORS = WHITE | BLACK |
|
103 colors = {a: WHITE, b: BLACK} |
|
104 |
|
105 visit = [-a, -b] |
|
106 heapq.heapify(visit) |
|
107 n_wanted = len(visit) |
|
108 ret = [] |
|
109 |
|
110 while n_wanted: |
|
111 r = -heapq.heappop(visit) |
|
112 wanted = colors[r] != ALLCOLORS |
|
113 n_wanted -= wanted |
|
114 if wanted: |
|
115 ret.append(r) |
|
116 |
|
117 for p in pfunc(r): |
|
118 if p not in colors: |
|
119 # first time we see p; add it to visit |
|
120 n_wanted += wanted |
|
121 colors[p] = colors[r] |
|
122 heapq.heappush(visit, -p) |
|
123 elif colors[p] != ALLCOLORS and colors[p] != colors[r]: |
|
124 # at first we thought we wanted p, but now |
|
125 # we know we don't really want it |
|
126 n_wanted -= 1 |
|
127 colors[p] |= colors[r] |
|
128 |
|
129 del colors[r] |
|
130 |
|
131 return ret |