Mercurial > public > mercurial-scm > hg

comparison mercurial/ancestor.py @ 6428:cbdefda439b6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
symmetricdifference: change colors to sides
author Matt Mackall <mpm@selenic.com>
date Sat, 29 Mar 2008 12:39:47 -0500
parents 6b704ef9ed06
children 532ca442b903
comparison
equal deleted inserted replaced
6427:6b704ef9ed06 6428:cbdefda439b6
86 """symmetric difference of the sets of ancestors of a and b 86 """symmetric difference of the sets of ancestors of a and b
87 87
88 I.e. revisions that are ancestors of a or b, but not both. 88 I.e. revisions that are ancestors of a or b, but not both.
89 """ 89 """
90 # basic idea: 90 # basic idea:
91 # - mark a and b with different colors 91 # - mark a and b with different sides
92 # - if a parent's children are all on the same side, the parent is
93 # on that side, otherwise it is on no side
92 # - walk the graph in topological order with the help of a heap; 94 # - walk the graph in topological order with the help of a heap;
93 # for each revision r: 95 # - add unseen parents to side map
94 # - if r has only one color, we want to return it 96 # - clear side of any parent that has children on different sides
95 # - add colors[r] to its parents 97 # - track number of unvisited nodes that might still be on a side
96 # 98 # - quit when interesting nodes is zero
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 if a == b: 99 if a == b:
101 return [a] 100 return [a]
102 101
103 WHITE = 1 102 side = {a: -1, b: 1}
104 BLACK = 2
105 ALLCOLORS = WHITE | BLACK
106 colors = {a: WHITE, b: BLACK}
107
108 visit = [-a, -b] 103 visit = [-a, -b]
109 heapq.heapify(visit) 104 heapq.heapify(visit)
110 interesting = len(visit) 105 interesting = len(visit)
111 106
112 while interesting: 107 while interesting:
113 r = -heapq.heappop(visit) 108 r = -heapq.heappop(visit)
114 if colors[r] != ALLCOLORS: 109 if side[r]:
115 interesting -= 1 110 interesting -= 1
116
117 for p in pfunc(r): 111 for p in pfunc(r):
118 if p not in colors: 112 if p not in side:
119 # first time we see p; add it to visit 113 # first time we see p; add it to visit
120 colors[p] = colors[r] 114 side[p] = side[r]
121 if colors[p] != ALLCOLORS: 115 if side[p]:
122 interesting += 1 116 interesting += 1
123 heapq.heappush(visit, -p) 117 heapq.heappush(visit, -p)
124 elif colors[p] != ALLCOLORS and colors[p] != colors[r]: 118 elif side[p] and side[p] != side[r]:
125 # at first we thought we wanted p, but now 119 # p was interesting but now we know better
126 # we know we don't really want it 120 side[p] = 0
127 colors[p] |= colors[r]
128 interesting -= 1 121 interesting -= 1
129 122
130 return [r for r in colors if colors[r] != ALLCOLORS] 123 return [r for r in side if side[r]]