← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to multiparent.py

  • Committer: Aaron Bentley
  • Date: 2007-04-13 01:50:40 UTC
  • mto: (2520.4.1 bzr.mpbundle)
  • mto: This revision was merged to the branch mainline in revision 2631.
  • Revision ID: aaron.bentley@utoronto.ca-20070413015040-9p1zv3nxm036g3mi
Move topological iteration into an iterator

Show diffs side-by-side

added added

removed removed

Lines of Context:
multiparent.py
10
10
 
11
11
from bzrlib.tuned_gzip import GzipFile
12
12
 
 
13
def topo_iter(vf):
 
14
    seen = set()
 
15
    descendants = {}
 
16
    for version_id in vf.versions():
 
17
        for parent_id in vf.get_parents(version_id):
 
18
            descendants.setdefault(parent_id, []).append(version_id)
 
19
    cur = [v for v in vf.versions() if len(vf.get_parents(v)) == 0]
 
20
    while len(cur) > 0:
 
21
        next = []
 
22
        for version_id in cur:
 
23
            if version_id in seen:
 
24
                continue
 
25
            parents = vf.get_parents(version_id)
 
26
            if not seen.issuperset(parents):
 
27
                continue
 
28
            next.extend(descendants.get(version_id, []))
 
29
            yield version_id
 
30
            seen.add(version_id)
 
31
        cur = next
 
32
 
 
33
 
13
34
class MultiParent(object):
14
35
 
15
36
    def __init__(self, hunks=None):
311
332
        distances = {}
312
333
        descendants = {}
313
334
        snapshots = set()
314
 
        for version_id in vf.versions():
315
 
            for parent_id in vf.get_parents(version_id):
316
 
                descendants.setdefault(parent_id, []).append(version_id)
317
 
        cur = [v for v in vf.versions() if len(vf.get_parents(v)) == 0]
318
 
        while len(cur) > 0:
319
 
            next = []
320
 
            for version_id in cur:
321
 
                if version_id in distances:
322
 
                    continue
323
 
                parents = vf.get_parents(version_id)
324
 
                p_distances = [distances.get(p) for p in parents]
325
 
                if None in p_distances:
326
 
                    continue
327
 
                next.extend(descendants.get(version_id, []))
328
 
                if len(p_distances) == 0:
 
335
        for version_id in topo_iter(vf):
 
336
            p_distances = [distances[p] for p in vf.get_parents(version_id)]
 
337
            if len(p_distances) == 0:
 
338
                snapshots.add(version_id)
 
339
                distances[version_id] = 0
 
340
            else:
 
341
                max_distance = max(p_distances)
 
342
                if max_distance + 1 > self.snapshot_interval:
 
343
                    snapshots.add(version_id)
 
344
                    distances[version_id] = 0
 
345
                elif len(descendants) > 1 and max_distance > \
 
346
                    self.snapshot_interval -4 and False:
329
347
                    snapshots.add(version_id)
330
348
                    distances[version_id] = 0
331
349
                else:
332
 
                    max_distance = max(p_distances)
333
 
                    if max_distance + 1 > self.snapshot_interval:
334
 
                        snapshots.add(version_id)
335
 
                        distances[version_id] = 0
336
 
                    elif len(descendants) > 1 and max_distance > \
337
 
                        self.snapshot_interval -4 and False:
338
 
                        snapshots.add(version_id)
339
 
                        distances[version_id] = 0
340
 
                    else:
341
 
                        distances[version_id] = max_distance + 1
342
 
            cur = next
 
350
                    distances[version_id] = max_distance + 1
343
351
        return snapshots
344
352
 
345
353