This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

classification
Title: small change at bisect_left function for easy understanding
Type: Stage: resolved
Components: Library (Lib) Versions: Python 3.8
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: Windson Yang, miss-islington, rhettinger, tim.peters
Priority: normal Keywords:

Created on 2019-10-29 03:03 by Windson Yang, last changed 2022-04-11 14:59 by admin. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 16978 merged rhettinger, 2019-10-29 04:19
Messages (4)
msg355606 - (view) Author: Windson Yang (Windson Yang) * Date: 2019-10-29 03:03
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
msg355607 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-10-29 03:27
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.
msg355608 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-10-29 03:30
I concur with Tim.

Thank you for the suggestion though.
msg355612 - (view) Author: miss-islington (miss-islington) Date: 2019-10-29 04:38
New changeset 3c88199e0be352c0813f145d7c4c83af044268aa by Miss Skeleton (bot) (Raymond Hettinger) in branch 'master':
bpo-38626:  Add comment explaining why __lt__ is used. (GH-16978)
https://github.com/python/cpython/commit/3c88199e0be352c0813f145d7c4c83af044268aa
History
Date User Action Args
2022-04-11 14:59:22adminsetgithub: 82807
2019-10-29 04:38:56miss-islingtonsetnosy: + miss-islington
messages: + msg355612
2019-10-29 04:19:32rhettingersetpull_requests: + pull_request16504
2019-10-29 03:30:28rhettingersetstatus: open -> closed

nosy: + rhettinger
messages: + msg355608

resolution: rejected
stage: resolved
2019-10-29 03:27:53tim.peterssetassignee: rhettinger ->
messages: + msg355607
nosy: + tim.peters, - rhettinger
2019-10-29 03:26:53rhettingersetassignee: rhettinger

nosy: + rhettinger
2019-10-29 03:03:16Windson Yangcreate