diff --git a/mercurial/dagutil.py b/mercurial/dagutil.py deleted file mode 100644 --- a/mercurial/dagutil.py +++ /dev/null @@ -1,49 +0,0 @@ -# dagutil.py - dag utilities for mercurial -# -# Copyright 2010 Benoit Boissinot -# and Peter Arrenbrecht -# -# This software may be used and distributed according to the terms of the -# GNU General Public License version 2 or any later version. - -from __future__ import absolute_import - -from .node import nullrev - -from . import ( - dagop, -) - -class revlogdag(object): - '''dag interface to a revlog''' - - def __init__(self, revlog): - self._revlog = revlog - - def linearize(self, ixs): - '''linearize and topologically sort a list of revisions - - The linearization process tries to create long runs of revs where - a child rev comes immediately after its first parent. This is done by - visiting the heads of the given revs in inverse topological order, - and for each visited rev, visiting its second parent, then its first - parent, then adding the rev itself to the output list. - ''' - sorted = [] - visit = list(dagop.headrevs(ixs, self._revlog.parentrevs)) - visit.sort(reverse=True) - finished = set() - - while visit: - cur = visit.pop() - if cur < 0: - cur = -cur - 1 - if cur not in finished: - sorted.append(cur) - finished.add(cur) - else: - visit.append(-cur - 1) - visit += [p for p in self._revlog.parentrevs(cur) - if p != nullrev and p in ixs and p not in finished] - assert len(sorted) == len(ixs) - return sorted