/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: John Arbash Meinel
  • Date: 2009-08-17 18:36:14 UTC
  • mto: This revision was merged to the branch mainline in revision 4629.
  • Revision ID: john@arbash-meinel.com-20090817183614-ss5shqo00p002imm
Move the topo_sort implementation into KnownGraph, rather than calling back to it.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
18
18
"""
19
19
 
20
20
from bzrlib import (
 
21
    errors,
21
22
    revision,
22
23
    tsort,
23
24
    )
173
174
        return heads
174
175
 
175
176
    def topo_sort(self):
176
 
        as_parent_map = dict((node.key, node.parent_keys)
177
 
                             for node in self._nodes.itervalues()
178
 
                              if node.parent_keys is not None)
179
 
        return tsort.topo_sort(as_parent_map)
 
177
        """Return the nodes in topological order.
 
178
 
 
179
        All parents must occur before all children.
 
180
        """
 
181
        for node in self._nodes.itervalues():
 
182
            if node.gdfo is None:
 
183
                raise errors.GraphCycleError(self._nodes)
 
184
        pending = self._find_tails()
 
185
        pending_pop = pending.pop
 
186
        pending_append = pending.append
 
187
 
 
188
        topo_order = []
 
189
        topo_order_append = topo_order.append
 
190
 
 
191
        num_seen_parents = dict.fromkeys(self._nodes, 0)
 
192
        while pending:
 
193
            node = pending_pop()
 
194
            if node.parent_keys is not None:
 
195
                # We don't include ghost parents
 
196
                topo_order_append(node.key)
 
197
            for child_key in node.child_keys:
 
198
                child_node = self._nodes[child_key]
 
199
                seen_parents = num_seen_parents[child_key] + 1
 
200
                if seen_parents == len(child_node.parent_keys):
 
201
                    # All parents have been processed, enqueue this child
 
202
                    pending_append(child_node)
 
203
                    # This has been queued up, stop tracking it
 
204
                    del num_seen_parents[child_key]
 
205
                else:
 
206
                    num_seen_parents[child_key] = seen_parents
 
207
        # We started from the parents, so we don't need to do anymore work
 
208
        return topo_order
180
209
 
181
210
    def merge_sort(self, tip_key):
182
211
        """Compute the merge sorted graph output."""