small change at bisect_left function for easy understanding

[Windsooon]

BPO	38626
Nosy	@tim-one, @rhettinger, @miss-islington, @Windsooon
PRs	bpo-38626: Add comment explaining why __lt__ is used. #16978

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2019-10-29.03:30:28.840>
created_at = <Date 2019-10-29.03:03:16.796>
labels = ['3.8', 'library']
title = 'small change at bisect_left function for easy understanding'
updated_at = <Date 2019-10-29.04:38:56.486>
user = 'https://github.com/Windsooon'

bugs.python.org fields:

activity = <Date 2019-10-29.04:38:56.486>
actor = 'miss-islington'
assignee = 'none'
closed = True
closed_date = <Date 2019-10-29.03:30:28.840>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2019-10-29.03:03:16.796>
creator = 'Windson Yang'
dependencies = []
files = []
hgrepos = []
issue_num = 38626
keywords = []
message_count = 4.0
messages = ['355606', '355607', '355608', '355612']
nosy_count = 4.0
nosy_names = ['tim.peters', 'rhettinger', 'miss-islington', 'Windson Yang']
pr_nums = ['16978']
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue38626'
versions = ['Python 3.8']

[Windsooon]

bisect_left should be similar to bisect_right. However, the current implement didn't reflect it. A little bit update for the bisect_left function could make the user easy to understand their relation.

def bisect_left(a, x, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # <= should be the only difference between bisect_left and bisect_right
        if x <= a[mid]: hi = mid
        else: lo = mid+1
    return lo

[tim-one]

So as far as possible, CPython only uses __lt__ ("<") element comparisons for its order-sensitive algorithms. This is documented for list.sort(), but the bisect and heapq modules strive to do the same.

The point is to minimize the number of comparison methods a new type needs to implement to participate (and "just one: __lt__" is ideal).

Your change would require they implement "__le__" too, so is unlikely to be accepted for CPython.

[rhettinger]

I concur with Tim.

Thank you for the suggestion though.

[miss-islington]

New changeset 3c88199 by Miss Skeleton (bot) (Raymond Hettinger) in branch 'master':
bpo-38626: Add comment explaining why __lt__ is used. (GH-16978)
3c88199