[Python-Dev] Adding key and reverse args to bisect

[David A. Barrett]

I propose adding the key parameter
to the bisect.bisect routines.  This
would allow it to be used on lists with
an ordering other than the one "natural"
to the contained objects.

(and anywhere else it makes sense in the
bisect module).

Would this be easy enough to do?

It looks like the main difficulty may have to
do with the C implementation.

I've also noticed that sort appears far faster;
is the C implementation working as expected?

It may be nice to have the reverse parameter
as well, but I'm not sure how that could be
implemented right off the bat.

David A. Barrett

- - - -
Here's an example I've coded up for my own use
(reverse hasn't been implemented here):

def bisect_right(a, x, lo=0, hi=None, key=lambda x: x, reverse=False):
    """A keyed version of bisect.bisect_bisect_right:

    return i: for all e in a[:i] e <= x < f, for all f in a[i:]

    """
    if hi is None: hi = len(a)
    if reverse:
      while lo < hi:
	  mid = (lo+hi)//2
	  if key(a[mid]) < key(x): hi = mid
	  else: lo = mid+1
    else:
      while lo < hi:
	  mid = (lo+hi)//2
	  if key(x) < key(a[mid]): hi = mid
	  else: lo = mid+1
    return lo

def bisect_left(a, x, lo=0, hi=None, key=lambda x: x, reverse=False):
    """A keyed version of bisect.bisect_bisect_left:

    return i: for all e in a[:i] e < x <= f, for all f in a[i:]
    """
    if hi is None: hi = len(a)
    if reverse:
      while lo < hi:
	  mid = (lo+hi)//2
	  if key(x) < key(a[mid]): lo = mid+1
	  else: hi = mid
    else:
      while lo < hi:
	  mid = (lo+hi)//2
	  if key(a[mid]) < key(x): lo = mid+1
	  else: hi = mid
    return lo