Mercurial > hg
comparison mercurial/ancestor.py @ 8465:23429ebd3f9d
ancestor: use set instead of dict
| author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
|---|---|
| date | Sun, 17 May 2009 03:53:13 +0200 |
| parents | 46293a0c7e9f |
| children | 806e6b6cb8d8 25e572394f5c |
comparison
equal
deleted
inserted
replaced
| 8464:7af92e70bb25 | 8465:23429ebd3f9d |
|---|---|
| 40 visit.pop() | 40 visit.pop() |
| 41 | 41 |
| 42 # traverse ancestors in order of decreasing distance from root | 42 # traverse ancestors in order of decreasing distance from root |
| 43 def ancestors(vertex): | 43 def ancestors(vertex): |
| 44 h = [(depth[vertex], vertex)] | 44 h = [(depth[vertex], vertex)] |
| 45 seen = {} | 45 seen = set() |
| 46 while h: | 46 while h: |
| 47 d, n = heapq.heappop(h) | 47 d, n = heapq.heappop(h) |
| 48 if n not in seen: | 48 if n not in seen: |
| 49 seen[n] = 1 | 49 seen.add(n) |
| 50 yield (d, n) | 50 yield (d, n) |
| 51 for p in parentcache[n]: | 51 for p in parentcache[n]: |
| 52 heapq.heappush(h, (depth[p], p)) | 52 heapq.heappush(h, (depth[p], p)) |
| 53 | 53 |
| 54 def generations(vertex): | 54 def generations(vertex): |
| 55 sg, s = None, {} | 55 sg, s = None, set() |
| 56 for g, v in ancestors(vertex): | 56 for g, v in ancestors(vertex): |
| 57 if g != sg: | 57 if g != sg: |
| 58 if sg: | 58 if sg: |
| 59 yield sg, s | 59 yield sg, s |
| 60 sg, s = g, {v:1} | 60 sg, s = g, set((v,)) |
| 61 else: | 61 else: |
| 62 s[v] = 1 | 62 s.add(v) |
| 63 yield sg, s | 63 yield sg, s |
| 64 | 64 |
| 65 x = generations(a) | 65 x = generations(a) |
| 66 y = generations(b) | 66 y = generations(b) |
| 67 gx = x.next() | 67 gx = x.next() |