comparison mercurial/stabletailgraph/stabletailsort.py @ 50525:1a4f54574e3d

stabletailgraph: clarify naiveness of current implementation

Both the naive and the actual versions of the algorithms are going to co-exist
for the tests. This makes is clearer that this one is naive.

50524:58adcabc295f

        return p1, nullrev
    else:
        return p1, p2


def _stable_tail_sort(cl, head_rev):
    """
    Naive topological iterator of the ancestors given by the stable-tail sort.

    The stable-tail sort of a node "h" is defined as the sequence:
    sts(h) := [h] + excl(h) + sts(pt(h))

            tail_ancestors = ancestor.lazyancestors(
                cl.parentrevs, (pt,), inclusive=True
            )
            exclusive_ancestors = (
                a for a in _stable_tail_sort(cl, px) if a not in tail_ancestors
            )

            excl_part_size = cl.fast_rank(cursor_rev) - cl.fast_rank(pt) - 1
            yield from itertools.islice(exclusive_ancestors, excl_part_size)
            cursor_rev = pt

50525:1a4f54574e3d

        return p1, nullrev
    else:
        return p1, p2


def _stable_tail_sort_naive(cl, head_rev):
    """
    Naive topological iterator of the ancestors given by the stable-tail sort.

    The stable-tail sort of a node "h" is defined as the sequence:
    sts(h) := [h] + excl(h) + sts(pt(h))

            tail_ancestors = ancestor.lazyancestors(
                cl.parentrevs, (pt,), inclusive=True
            )
            exclusive_ancestors = (
                a
                for a in _stable_tail_sort_naive(cl, px)
                if a not in tail_ancestors
            )

            excl_part_size = cl.fast_rank(cursor_rev) - cl.fast_rank(pt) - 1
            yield from itertools.islice(exclusive_ancestors, excl_part_size)
            cursor_rev = pt