Skip to content

bpo-4356: Add key parameter to functions in bisect module #11781

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
remilapeyre wants to merge 13 commits into from
Closed

bpo-4356: Add key parameter to functions in bisect module #11781

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
13 commits
Select commit Hold shift + click to select a range
e36dd1e
Add key parameter to functions in bisect module
Feb 7, 2019
d6082a5
Support None as argument
Feb 7, 2019
b7aaa1a
Fix documentation
Feb 7, 2019
1bc959d
Improve documentation
Mar 17, 2019
adb5a54
Merge remote-tracking branch 'origin/master' into add-key-argument-to…
May 31, 2019
e1ce337
Split logic for key=None
May 31, 2019
4337e73
Test that key is a keyword only argument
May 31, 2019
d9022a9
Make key a keyword only argument
May 31, 2019
84c18be
Add note in the documentation regarding lru_cache
May 31, 2019
54960ed
Add test for reverse support
May 31, 2019
ef98658
Add reverse support
May 31, 2019
49ef1f7
Whitelist suspicious constructs in documentation
May 31, 2019
6bfe7bc
Implement reverse bisect in Python
Jun 8, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
Add reverse support
  • Loading branch information
Rémi Lapeyre
Rémi Lapeyre committed May 31, 2019
commit ef986581f8fc062e907650320ee0bd11a06ccdab
25 changes: 14 additions & 11 deletions Doc/library/bisect.rst
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -21,7 +21,7 @@ example of the algorithm (the boundary conditions are already right!).
The following functions are provided:


.. function:: bisect_left(a, x, lo=0, hi=len(a), *, key=None)
.. function:: bisect_left(a, x, lo=0, hi=len(a), *, key=None, reverse=False)

Locate the insertion point for *x* in *a* to maintain sorted order.
The parameters *lo* and *hi* may be used to specify a subset of the list
Expand All @@ -37,6 +37,9 @@ The following functions are provided:
When specifying a custom *key* function, you should wrap it with
:func:`functools.lru_cache` if the *key* function is not already fast.

The parameter *reverse* is a boolean value. If set to ``True``, the list is
supposed to be sorted in descending order.

If *x* is already present in *a*, the insertion point will be before
(to the left of) any existing entries. The return value is suitable for
use as the first parameter to ``list.insert()`` assuming that *a* is
Expand All @@ -46,8 +49,8 @@ The following functions are provided:
that ``all(val < x for val in a[lo:i])`` for the left side and
``all(val >= x for val in a[i:hi])`` for the right side.

.. function:: bisect_right(a, x, lo=0, hi=len(a), *, key=None)
bisect(a, x, lo=0, hi=len(a), *, key=None)
.. function:: bisect_right(a, x, lo=0, hi=len(a), *, key=None, reverse=False)
bisect(a, x, lo=0, hi=len(a), *, key=None, reverse=False)

Similar to :func:`bisect_left`, but returns an insertion point which comes
after (to the right of) any existing entries of *x* in *a*.
Expand All @@ -56,15 +59,15 @@ The following functions are provided:
that ``all(val <= x for val in a[lo:i])`` for the left side and
``all(val > x for val in a[i:hi])`` for the right side.

.. function:: insort_left(a, x, lo=0, hi=len(a), *, key=None)
.. function:: insort_left(a, x, lo=0, hi=len(a), *, key=None, reverse=False)

Insert *x* in *a* in sorted order. This is equivalent to
``a.insert(bisect.bisect_left(a, x, lo, hi), x)`` assuming that *a* is
already sorted. Keep in mind that the O(log n) search is dominated by
the slow O(n) insertion step.

.. function:: insort_right(a, x, lo=0, hi=len(a), *, key=None)
insort(a, x, lo=0, hi=len(a), *, key=None)
.. function:: insort_right(a, x, lo=0, hi=len(a), *, key=None, reverse=False)
insort(a, x, lo=0, hi=len(a), *, key=None, reverse=False)

Similar to :func:`insort_left`, but inserting *x* in *a* after any existing
entries of *x*.
Expand All @@ -86,35 +89,35 @@ can be tricky or awkward to use for common searching tasks. The following five
functions show how to transform them into the standard lookups for sorted
lists::

def index(a, x, *, key=None):
def index(a, x, *, key=None, reverse=False):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x, key=key)
if i != len(a) and a[i] == x:
return i
raise ValueError

def find_lt(a, x, *, key=None):
def find_lt(a, x, *, key=None, reverse=False):
'Find rightmost value less than x'
i = bisect_left(a, x, key=key)
if i:
return a[i-1]
raise ValueError

def find_le(a, x, *, key=None):
def find_le(a, x, *, key=None, reverse=False):
'Find rightmost value less than or equal to x'
i = bisect_right(a, x, key=key)
if i:
return a[i-1]
raise ValueError

def find_gt(a, x, *, key=None):
def find_gt(a, x, *, key=None, reverse=False):
'Find leftmost value greater than x'
i = bisect_right(a, x, key=key)
if i != len(a):
return a[i]
raise ValueError

def find_ge(a, x, *, key=None):
def find_ge(a, x, *, key=None, reverse=False):
'Find leftmost item greater than or equal to x'
i = bisect_left(a, x, key=key)
if i != len(a):
Expand Down
12 changes: 6 additions & 6 deletions Lib/bisect.py
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,6 +1,6 @@
"""Bisection algorithms."""

def insort_right(a, x, lo=0, hi=None, *, key=None):
def insort_right(a, x, lo=0, hi=None, *, key=None, reverse=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.
Expand All @@ -12,10 +12,10 @@ def insort_right(a, x, lo=0, hi=None, *, key=None):
customize the order.
"""

lo = bisect_right(a, x, lo, hi, key=key)
lo = bisect_right(a, x, lo, hi, key=key, reverse=reverse)
a.insert(lo, x)

def bisect_right(a, x, lo=0, hi=None, *, key=None):
def bisect_right(a, x, lo=0, hi=None, *, key=None, reverse=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
Expand Down Expand Up @@ -53,7 +53,7 @@ def bisect_right(a, x, lo=0, hi=None, *, key=None):
lo = mid+1
return lo

def insort_left(a, x, lo=0, hi=None, *, key=None):
def insort_left(a, x, lo=0, hi=None, *, key=None, reverse=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.
Expand All @@ -65,11 +65,11 @@ def insort_left(a, x, lo=0, hi=None, *, key=None):
customize the order.
"""

lo = bisect_left(a, x, lo, hi, key=key)
lo = bisect_left(a, x, lo, hi, key=key, reverse=reverse)
a.insert(lo, x)


def bisect_left(a, x, lo=0, hi=None, *, key=None):
def bisect_left(a, x, lo=0, hi=None, *, key=None, reverse=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
Expand Down
58 changes: 36 additions & 22 deletions Modules/_bisectmodule.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -9,7 +9,8 @@ Converted to C by Dmitry Vasiliev (dima at hlabs.spb.ru).
_Py_IDENTIFIER(insert);

static inline Py_ssize_t
internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
PyObject *key, int reverse)
{
PyObject *litem;
PyObject *item_value = NULL;
Expand Down Expand Up @@ -38,6 +39,8 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t
goto fail;
}
}

int comparator = reverse ? Py_GT : Py_LT;
while (lo < hi) {
/* The (size_t)cast ensures that the addition and subsequent division
are performed as unsigned operations, avoiding difficulties from
Expand All @@ -48,7 +51,7 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t
goto fail;
}
if (key == NULL) {
res = PyObject_RichCompareBool(item_value, litem, Py_LT);
res = PyObject_RichCompareBool(item_value, litem, comparator);
}
else {
PyObject *arglist = Py_BuildValue("(O)", litem);
Expand All @@ -57,7 +60,7 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t
if (litem_value == NULL) {
goto fail;
}
res = PyObject_RichCompareBool(item_value, litem_value, Py_LT);
res = PyObject_RichCompareBool(item_value, litem_value, comparator);
Py_DECREF(litem_value);
}

Expand Down Expand Up @@ -85,24 +88,26 @@ bisect_right(PyObject *self, PyObject *args, PyObject *kw)
{
PyObject *list, *item;
PyObject *key = NULL;
int reverse = 0;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
Py_ssize_t index;
static char *keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static char *keywords[] = {"a", "x", "lo", "hi", "key", "reverse", NULL};

if (kw == NULL && PyTuple_GET_SIZE(args) == 2) {
list = PyTuple_GET_ITEM(args, 0);
item = PyTuple_GET_ITEM(args, 1);
}
else {
if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn$O:bisect_right",
keywords, &list, &item, &lo, &hi, &key))
if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn$Op:bisect_right",
keywords, &list, &item, &lo, &hi,
&key, &reverse))
return NULL;
}
if (key == Py_None) {
key = NULL;
}
index = internal_bisect_right(list, item, lo, hi, key);
index = internal_bisect_right(list, item, lo, hi, key, reverse);
if (index < 0) {
return NULL;
}
Expand All @@ -129,24 +134,26 @@ insort_right(PyObject *self, PyObject *args, PyObject *kw)
{
PyObject *list, *item, *result;
PyObject *key = NULL;
int reverse = 0;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
Py_ssize_t index;
static char *keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static char *keywords[] = {"a", "x", "lo", "hi", "key", "reverse", NULL};

if (kw == NULL && PyTuple_GET_SIZE(args) == 2) {
list = PyTuple_GET_ITEM(args, 0);
item = PyTuple_GET_ITEM(args, 1);
}
else {
if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn$O:insort_right",
keywords, &list, &item, &lo, &hi, &key))
if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn$Op:insort_right",
keywords, &list, &item, &lo, &hi,
&key, &reverse))
return NULL;
}
if (key == Py_None) {
key = NULL;
}
index = internal_bisect_right(list, item, lo, hi, key);
index = internal_bisect_right(list, item, lo, hi, key, reverse);
if (index < 0) {
return NULL;
}
Expand Down Expand Up @@ -178,7 +185,8 @@ Optional argument key is a function of one argument used to\n\
customize the order.\n");

static inline Py_ssize_t
internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
PyObject *key, int reverse)
{
PyObject *litem;
PyObject *item_value = NULL;
Expand Down Expand Up @@ -207,6 +215,8 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h
goto fail;
}
}

int comparator = reverse ? Py_GT : Py_LT;
while (lo < hi) {
/* The (size_t)cast ensures that the addition and subsequent division
are performed as unsigned operations, avoiding difficulties from
Expand All @@ -217,7 +227,7 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h
goto fail;
}
if (key == NULL) {
res = PyObject_RichCompareBool(litem, item_value, Py_LT);
res = PyObject_RichCompareBool(litem, item_value, comparator);
}
else {
PyObject *arglist = Py_BuildValue("(O)", litem);
Expand All @@ -226,7 +236,7 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h
if (litem_value == NULL) {
goto fail;
}
res = PyObject_RichCompareBool(litem_value, item_value, Py_LT);
res = PyObject_RichCompareBool(litem_value, item_value, comparator);
}

Py_DECREF(litem);
Expand All @@ -253,24 +263,26 @@ bisect_left(PyObject *self, PyObject *args, PyObject *kw)
{
PyObject *list, *item;
PyObject *key = NULL;
int reverse = 0;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
Py_ssize_t index;
static char *keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static char *keywords[] = {"a", "x", "lo", "hi", "key", "reverse", NULL};

if (kw == NULL && PyTuple_GET_SIZE(args) == 2) {
list = PyTuple_GET_ITEM(args, 0);
item = PyTuple_GET_ITEM(args, 1);
}
else {
if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn$O:bisect_left",
keywords, &list, &item, &lo, &hi, &key))
if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn$Op:bisect_left",
keywords, &list, &item, &lo, &hi,
&key, &reverse))
return NULL;
}
if (key == Py_None) {
key = NULL;
}
index = internal_bisect_left(list, item, lo, hi, key);
index = internal_bisect_left(list, item, lo, hi, key, reverse);
if (index < 0) {
return NULL;
}
Expand All @@ -297,23 +309,25 @@ insort_left(PyObject *self, PyObject *args, PyObject *kw)
{
PyObject *list, *item, *result;
PyObject *key = NULL;
int reverse = 0;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
Py_ssize_t index;
static char *keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static char *keywords[] = {"a", "x", "lo", "hi", "key", "reverse", NULL};

if (kw == NULL && PyTuple_GET_SIZE(args) == 2) {
list = PyTuple_GET_ITEM(args, 0);
item = PyTuple_GET_ITEM(args, 1);
} else {
if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn$O:insort_left",
keywords, &list, &item, &lo, &hi, &key))
if (!PyArg_ParseTupleAndKeywords(args, kw, "OO|nn$Op:insort_left",
keywords, &list, &item, &lo, &hi,
&key, &reverse))
return NULL;
}
if (key == Py_None) {
key = NULL;
}
index = internal_bisect_left(list, item, lo, hi, key);
index = internal_bisect_left(list, item, lo, hi, key, reverse);
if (index < 0)
return NULL;
if (PyList_CheckExact(list)) {
Expand Down