equal
deleted
inserted
replaced
938 self.cache = (node, n, text) |
938 self.cache = (node, n, text) |
939 return node |
939 return node |
940 |
940 |
941 def ancestor(self, a, b): |
941 def ancestor(self, a, b): |
942 """calculate the least common ancestor of nodes a and b""" |
942 """calculate the least common ancestor of nodes a and b""" |
|
943 |
|
944 # start with some short cuts for the linear cases |
|
945 if a == b: |
|
946 return a |
|
947 ra = self.rev(a) |
|
948 rb = self.rev(b) |
|
949 if ra < rb: |
|
950 last = b |
|
951 first = a |
|
952 else: |
|
953 last = a |
|
954 first = b |
|
955 |
|
956 # reachable won't include stop in the list, so we have to use a parent |
|
957 reachable = self.reachable(last, stop=self.parents(first)[0]) |
|
958 if first in reachable: |
|
959 return first |
|
960 |
943 # calculate the distance of every node from root |
961 # calculate the distance of every node from root |
944 dist = {nullid: 0} |
962 dist = {nullid: 0} |
945 for i in xrange(self.count()): |
963 for i in xrange(self.count()): |
946 n = self.node(i) |
964 n = self.node(i) |
947 p1, p2 = self.parents(n) |
965 p1, p2 = self.parents(n) |