# HG changeset patch
# User Matt Mackall <mpm@selenic.com>
# Date 1206812387 18000
# Node ID cbdefda439b61cee48c21cb8e7305ef0a5c9b6d6
# Parent  6b704ef9ed06a48d3de875589bd40db731488c9b
symmetricdifference: change colors to sides

diff -r 6b704ef9ed06 -r cbdefda439b6 mercurial/ancestor.py
--- a/mercurial/ancestor.py	Sat Mar 29 12:39:47 2008 -0500
+++ b/mercurial/ancestor.py	Sat Mar 29 12:39:47 2008 -0500
@@ -88,43 +88,36 @@
     I.e. revisions that are ancestors of a or b, but not both.
     """
     # basic idea:
-    # - mark a and b with different colors
+    # - 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;
-    #   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.
+    #   - 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]
 
-    WHITE = 1
-    BLACK = 2
-    ALLCOLORS = WHITE | BLACK
-    colors = {a: WHITE, b: BLACK}
-
+    side = {a: -1, b: 1}
     visit = [-a, -b]
     heapq.heapify(visit)
     interesting = len(visit)
 
     while interesting:
         r = -heapq.heappop(visit)
-        if colors[r] != ALLCOLORS:
+        if side[r]:
             interesting -= 1
-
         for p in pfunc(r):
-            if p not in colors:
+            if p not in side:
                 # first time we see p; add it to visit
-                colors[p] = colors[r]
-                if colors[p] != ALLCOLORS:
+                side[p] = side[r]
+                if side[p]:
                     interesting += 1
                 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
-                colors[p] |= colors[r]
+            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 colors if colors[r] != ALLCOLORS]
+    return [r for r in side if side[r]]