"""Bisection algorithms."""

def __parse_param(a, x, hi, comp, key, reverse):
    """Converts the given parameters into variables usable by a bisect
    method."""

    # Default hi is Last
    if hi is None:
        hi = len(a)

    # Default Compare function is __builtin__.cmp
    # Note: Perhaps comp should be __lt__
    if comp == None:
        comp = cmp

    # Default Key is no-op
    # Use key(x) as search string (x_key)
    if key == None:
        key = lambda i:i
        x_key = x
    else:
        x_key = key(x)

    # Reverse logic means cmp == -1 for forward and cmp == +1 for
    # reverse
    if reverse:
        comp_res = +1
    else:
        comp_res = -1

    return hi, comp, key, x_key, comp_res

def insort_right(a, x, lo=0, hi=None, comp=None, key=None, rev=False):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.  comp provides an alternate element
    comparison function, key a function to serialize the encoding of
    each element and reverse to reverse the sort logic.
    """

    # Use helper to parse parameters
    hi, comp, key, x_key, comp_res = __parse_param(a, x, hi, comp, key, rev)

    while lo < hi:
        mid = (lo+hi)//2
        if comp(x_key, key(a[mid])) == comp_res: hi = mid
        else: lo = mid+1

    # Insert x into a
    a.insert(lo, x)

insort = insort_right   # backward compatibility

def bisect_right(a, x, lo=0, hi=None, comp=None, key=None, rev=False):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, i points just
    beyond the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.  comp provides an alternate element
    comparison function, key a function to serialize the encoding of
    each element and reverse to reverse the sort logic.
    """

    # Use helper to parse parameters
    hi, comp, key, x_key, comp_res = __parse_param(a, x, hi, comp, key, rev)

    while lo < hi:
        mid = (lo+hi)//2
        if comp(x_key, key(a[mid])) == comp_res: hi = mid
        else: lo = mid+1

    return lo

bisect = bisect_right   # backward compatibility

def insort_left(a, x, lo=0, hi=None, comp=None, key=None, rev=False):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.  comp provides an alternate element
    comparison function, key a function to serialize the encoding of
    each element and reverse to reverse the sort logic.
    """

    # Use helper to parse parameters
    hi, comp, key, x_key, comp_res = __parse_param(a, x, hi, comp, key, rev)

    while lo < hi:
        mid = (lo+hi)//2
        if comp(key(a[mid]), x_key) == comp_res: lo = mid+1
        else: hi = mid
    a.insert(lo, x)


def bisect_left(a, x, lo=0, hi=None, comp=None, key=None, rev=False):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, i points just
    before the leftmost x already there.  comp provides an alternate element
    comparison function, key a function to serialize the encoding of
    each element and reverse to reverse the sort logic.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    # Use helper to parse parameters
    hi, comp, key, x_key, comp_res = __parse_param(a, x, hi, comp, key, rev)

    while lo < hi:
        mid = (lo+hi)//2
        if comp(key(a[mid]), x_key) == comp_res: lo = mid+1
        else: hi = mid
    return lo

# Overwrite above definitions with a fast C implementation
try:
    # Postpone call to C-Implementation for testing of new Python version
    # The C-version will be implements if the python version passes
    #from _bisect import bisect_right, bisect_left, insort_left, insort_right, insort, bisect
    pass
except ImportError:
    pass