Mercurial > public > mercurial-scm > hg
diff mercurial/ancestor.py @ 6429:532ca442b903
symmetricdifference: move back to copies
It's too tightly dependent on known revlog ordering to fit well in ancestors
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Sat, 29 Mar 2008 12:39:47 -0500 |
parents | cbdefda439b6 |
children | 8d78fc991b71 |
line wrap: on
line diff
--- a/mercurial/ancestor.py Sat Mar 29 12:39:47 2008 -0500 +++ b/mercurial/ancestor.py Sat Mar 29 12:39:47 2008 -0500 @@ -81,43 +81,3 @@ gx = x.next() except StopIteration: return None - -def symmetricdifference(a, b, pfunc): - """symmetric difference of the sets of ancestors of a and b - - I.e. revisions that are ancestors of a or b, but not both. - """ - # basic idea: - # - mark a and b with different sides - # - if a parent's children are all on the same side, the parent is - # on that side, otherwise it is on no side - # - walk the graph in topological order with the help of a heap; - # - add unseen parents to side map - # - clear side of any parent that has children on different sides - # - track number of unvisited nodes that might still be on a side - # - quit when interesting nodes is zero - if a == b: - return [a] - - side = {a: -1, b: 1} - visit = [-a, -b] - heapq.heapify(visit) - interesting = len(visit) - - while interesting: - r = -heapq.heappop(visit) - if side[r]: - interesting -= 1 - for p in pfunc(r): - if p not in side: - # first time we see p; add it to visit - side[p] = side[r] - if side[p]: - interesting += 1 - heapq.heappush(visit, -p) - elif side[p] and side[p] != side[r]: - # p was interesting but now we know better - side[p] = 0 - interesting -= 1 - - return [r for r in side if side[r]]