← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: Vincent Ladeuil
  • Date: 2009-06-16 09:37:53 UTC
  • mto: (4371.4.5 vila-better-heads)
  • mto: This revision was merged to the branch mainline in revision 4466.
  • Revision ID: v.ladeuil+lp@free.fr-20090616093753-ihx32neot2jqhqqn
A new recursive gdfo processing method.

* bzrlib/_known_graph_py.py:
(KnownGraph._find_gdfo): A new version in O(n) processing each
node only once.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
147
147
                node = next_node
148
148
 
149
149
    def _find_gdfo(self):
 
150
        nodes = self._nodes
 
151
        pending = []
 
152
        known_parent_gdfos = dict.fromkeys(nodes.keys(), 0)
 
153
 
 
154
        def update_childs(node):
 
155
            for child_key in node.child_keys:
 
156
                child = nodes[child_key]
 
157
                known_parent_gdfos[child_key] += 1
 
158
                if child.gdfo is None or node.gdfo + 1 > child.gdfo:
 
159
                    child.gdfo = node.gdfo + 1
 
160
                if known_parent_gdfos[child_key] == len(child.parent_keys):
 
161
                    # We are the last parent updating that node, we can
 
162
                    # continue from there
 
163
                    update_childs(child)
 
164
 
 
165
        for node in self._nodes.itervalues():
 
166
            if not node.parent_keys:
 
167
                node.gdfo = 1
 
168
                known_parent_gdfos[node.key] = 0
 
169
                update_childs(node)
 
170
 
 
171
    def x_find_gdfo(self):
150
172
        def find_tails():
151
173
            return [node for node in self._nodes.itervalues()
152
174
                       if not node.parent_keys]