#

# Copyright 2005, 2006 Benoit Boissinot <benoit.boissinot@ens-lyon.org>

# Inspired by git bisect, extension skeleton taken from mq.py.

#

# This software may be used and distributed according to the terms

# of the GNU General Public License, incorporated herein by reference.

    clparents = changelog.parentrevs

    # only the earliest bad revision matters

    badrev = min([changelog.rev(n) for n in state['bad']])

    bad = changelog.node(badrev)

    skip = dict.fromkeys([changelog.rev(n) for n in state['skip']])

    # build ancestors array

    ancestors = [[]] * (changelog.count() + 1) # an extra for [-1]

    # clear good revs from array

    for node in state['good']:

        ancestors[changelog.rev(node)] = None

    for rev in xrange(changelog.count(), -1, -1):

        if ancestors[rev] is None:

            for prev in clparents(rev):

                ancestors[prev] = None

    if ancestors[badrev] is None:

        raise util.Abort(_("Inconsistent state, %s:%s is good and bad")

                         % (badrev, hg.short(bad)))

    # build children dict

    children = {}

    visit = [badrev]

    candidates = []

    while visit:

        rev = visit.pop(0)

        if ancestors[rev] == []:

            candidates.append(rev)

            for prev in clparents(rev):

                if prev != -1:

                    if prev in children:

                        children[prev].append(rev)

                    else:

                        children[prev] = [rev]

                        visit.append(prev)

    candidates.sort()

    # have we narrowed it down to one entry?

    tot = len(candidates)

    if tot == 1:

        return (bad, 0)

    perfect = tot / 2

    # find the best node to test

    best_rev = None

    best_len = -1

    poison = {}

    for rev in candidates:

        if rev in poison:

            for c in children.get(rev, []):

                poison[c] = True # poison children

            continue

        a = ancestors[rev] or [rev]

        ancestors[rev] = None

        x = len(a) # number of ancestors

        y = tot - x # number of non-ancestors

        value = min(x, y) # how good is this test?

        if value > best_len and rev not in skip:

            best_len = value

            best_rev = rev

            if value == perfect: # found a perfect candidate? quit early

                break

        if y < perfect: # all downhill from here?

            for c in children.get(rev, []):

                poison[c] = True # poison children

            continue

        for c in children.get(rev, []):

            if ancestors[c]:

                ancestors[c] = dict.fromkeys(ancestors[c] + a).keys()

            else:

                ancestors[c] = a + [c]

    assert best_rev is not None

    best_node = changelog.node(best_rev)

    return (best_node, tot)