--- a/mercurial/ancestor.py Sat Mar 15 10:02:31 2008 -0500
+++ b/mercurial/ancestor.py Sat Mar 15 10:02:31 2008 -0500
@@ -81,3 +81,51 @@
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 colors
+ # - walk the graph in topological order with the help of a heap;
+ # for each revision r:
+ # - if r has only one color, we want to return it
+ # - add colors[r] to its parents
+ #
+ # We keep track of the number of revisions in the heap that
+ # we may be interested in. We stop walking the graph as soon
+ # as this number reaches 0.
+ WHITE = 1
+ BLACK = 2
+ ALLCOLORS = WHITE | BLACK
+ colors = {a: WHITE, b: BLACK}
+
+ visit = [-a, -b]
+ heapq.heapify(visit)
+ n_wanted = len(visit)
+ ret = []
+
+ while n_wanted:
+ r = -heapq.heappop(visit)
+ wanted = colors[r] != ALLCOLORS
+ n_wanted -= wanted
+ if wanted:
+ ret.append(r)
+
+ for p in pfunc(r):
+ if p not in colors:
+ # first time we see p; add it to visit
+ n_wanted += wanted
+ colors[p] = colors[r]
+ heapq.heappush(visit, -p)
+ elif colors[p] != ALLCOLORS and colors[p] != colors[r]:
+ # at first we thought we wanted p, but now
+ # we know we don't really want it
+ n_wanted -= 1
+ colors[p] |= colors[r]
+
+ del colors[r]
+
+ return ret