1 # ancestor.py - generic DAG ancestor algorithm for mercurial

     2 #

     3 # Copyright 2006 Matt Mackall <mpm@selenic.com>

     4 #

     5 # This software may be used and distributed according to the terms

     6 # of the GNU General Public License, incorporated herein by reference.

     7 

     8 import heapq

     9 

    10 def ancestor(a, b, pfunc):

    11     """

    12     return the least common ancestor of nodes a and b or None if there

    13     is no such ancestor.

    14 

    15     pfunc must return a list of parent vertices

    16     """

    17 

    18     if a == b:

    19         return a

    20 

    21     # find depth from root of all ancestors

    22     visit = [a, b]

    23     depth = {}

    24     while visit:

    25         vertex = visit[-1]

    26         pl = pfunc(vertex)

    27         if not pl:

    28             depth[vertex] = 0

    29             visit.pop()

    30         else:

    31             for p in pl:

    32                 if p == a or p == b: # did we find a or b as a parent?

    33                     return p # we're done

    34                 if p not in depth:

    35                     visit.append(p)

    36             if visit[-1] == vertex:

    37                 depth[vertex] = min([depth[p] for p in pl]) - 1

    38                 visit.pop()

    39 

    40     # traverse ancestors in order of decreasing distance from root

    41     def ancestors(vertex):

    42         h = [(depth[vertex], vertex)]

    43         seen = {}

    44         while h:

    45             d, n = heapq.heappop(h)

    46             if n not in seen:

    47                 seen[n] = 1

    48                 yield (d, n)

    49                 for p in pfunc(n):

    50                     heapq.heappush(h, (depth[p], p))

    51 

    52     def generations(vertex):

    53         sg, s = None, {}

    54         for g,v in ancestors(vertex):

    55             if g != sg:

    56                 if sg:

    57                     yield sg, s

    58                 sg, s = g, {v:1}

    59             else:

    60                 s[v] = 1

    61         yield sg, s

    62 

    63     x = generations(a)

    64     y = generations(b)

    65     gx = x.next()

    66     gy = y.next()

    67 

    68     # increment each ancestor list until it is closer to root than

    69     # the other, or they match

    70     try:

    71         while 1:

    72             if gx[0] == gy[0]:

    73                 for v in gx[1]:

    74                     if v in gy[1]:

    75                         return v

    76                 gy = y.next()

    77                 gx = x.next()

    78             elif gx[0] > gy[0]:

    79                 gy = y.next()

    80             else:

    81                 gx = x.next()

    82     except StopIteration:

    83         return None