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
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
