https://github.com/python/cpython/commit/871934d4cf00687b3d1411c6e344af311646c1ae
commit: 871934d4cf00687b3d1411c6e344af311646c1ae
branch: master
author: Raymond Hettinger <rhettinger@users.noreply.github.com>
committer: GitHub <noreply@github.com>
date: 2020-10-19T22:04:01-07:00
summary:
bpo-4356: Add key function support to the bisect module (GH-20556)
files:
A Misc/NEWS.d/next/Library/2020-05-31-10-48-47.bpo-4356.P8kXqp.rst
M Doc/library/bisect.rst
M Doc/tools/susp-ignored.csv
M Lib/bisect.py
M Lib/test/test_bisect.py
M Modules/_bisectmodule.c
M Modules/clinic/_bisectmodule.c.h
diff --git a/Doc/library/bisect.rst b/Doc/library/bisect.rst
index 6bf7814b257f4..f34ee175ba657 100644
--- a/Doc/library/bisect.rst
+++ b/Doc/library/bisect.rst
@@ -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))
+.. function:: bisect_left(a, x, lo=0, hi=len(a), *, key=None)
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
@@ -31,39 +31,106 @@ The following functions are provided:
parameter to ``list.insert()`` assuming that *a* is already sorted.
The returned insertion point *i* partitions the array *a* into two halves so
- 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.
+ 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* specifies a :term:`key function` of one argument that is used to
+ extract a comparison key from each input element. The default value is
+ ``None`` (compare the elements directly).
+
+ .. versionchanged:: 3.10
+ Added the *key* parameter.
+
+
+.. function:: bisect_right(a, x, lo=0, hi=len(a), *, key=None)
bisect(a, x, lo=0, hi=len(a))
Similar to :func:`bisect_left`, but returns an insertion point which comes
after (to the right of) any existing entries of *x* in *a*.
The returned insertion point *i* partitions the array *a* into two halves so
- 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.
+ 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.
+
+ *key* specifies a :term:`key function` of one argument that is used to
+ extract a comparison key from each input element. The default value is
+ ``None`` (compare the elements directly).
+
+ .. versionchanged:: 3.10
+ Added the *key* parameter.
+
-.. function:: insort_left(a, x, lo=0, hi=len(a))
+.. function:: insort_left(a, x, lo=0, hi=len(a), *, key=None)
- 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.
+ Insert *x* in *a* in sorted order.
-.. function:: insort_right(a, x, lo=0, hi=len(a))
+ *key* specifies a :term:`key function` of one argument that is used to
+ extract a comparison key from each input element. The default value is
+ ``None`` (compare the elements directly).
+
+ This function first runs :func:`bisect_left` to locate an insertion point.
+ Next, it runs the :meth:`insert` method on *a* to insert *x* at the
+ appropriate position to maintain sort order.
+
+ Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
+ insertion step.
+
+ .. versionchanged:: 3.10
+ Added the *key* parameter.
+
+
+.. function:: insort_right(a, x, lo=0, hi=len(a), *, key=None)
insort(a, x, lo=0, hi=len(a))
Similar to :func:`insort_left`, but inserting *x* in *a* after any existing
entries of *x*.
+ *key* specifies a :term:`key function` of one argument that is used to
+ extract a comparison key from each input element. The default value is
+ ``None`` (compare the elements directly).
+
+ This function first runs :func:`bisect_right` to locate an insertion point.
+ Next, it runs the :meth:`insert` method on *a* to insert *x* at the
+ appropriate position to maintain sort order.
+
+ Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
+ insertion step.
+
+ .. versionchanged:: 3.10
+ Added the *key* parameter.
+
+
+Performance Notes
+-----------------
+
+When writing time sensitive code using *bisect()* and *insort()*, keep these
+thoughts in mind:
+
+* Bisection is effective for searching ranges of values.
+ For locating specific values, dictionaries are more performant.
+
+* The *insort()* functions are ``O(n)`` because the logarithmic search step
+ is dominated by the linear time insertion step.
+
+* The search functions are stateless and discard key function results after
+ they are used. Consequently, if the search functions are used in a loop,
+ the key function may be called again and again on the same array elements.
+ If the key function isn't fast, consider wrapping it with
+ :func:`functools.cache` to avoid duplicate computations. Alternatively,
+ consider searching an array of precomputed keys to locate the insertion
+ point (as shown in the examples section below).
+
.. seealso::
- `SortedCollection recipe
- <https://code.activestate.com/recipes/577197-sortedcollection/>`_ that uses
- bisect to build a full-featured collection class with straight-forward search
- methods and support for a key-function. The keys are precomputed to save
- unnecessary calls to the key function during searches.
+ * `Sorted Collections
+ <http://www.grantjenks.com/docs/sortedcollections/>`_ is a high performance
+ module that uses *bisect* to managed sorted collections of data.
+
+ * The `SortedCollection recipe
+ <https://code.activestate.com/recipes/577197-sortedcollection/>`_ uses
+ bisect to build a full-featured collection class with straight-forward search
+ methods and support for a key-function. The keys are precomputed to save
+ unnecessary calls to the key function during searches.
Searching Sorted Lists
@@ -110,8 +177,8 @@ lists::
raise ValueError
-Other Examples
---------------
+Examples
+--------
.. _bisect-example:
@@ -127,17 +194,12 @@ a 'B', and so on::
>>> [.grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']
-Unlike the :func:`sorted` function, it does not make sense for the :func:`bisect`
-functions to have *key* or *reversed* arguments because that would lead to an
-inefficient design (successive calls to bisect functions would not "remember"
-all of the previous key lookups).
-
-Instead, it is better to search a list of precomputed keys to find the index
-of the record in question::
+One technique to avoid repeated calls to a key function is to search a list of
+precomputed keys to find the index of a record::
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
- >>> data.sort(key=lambda r: r[1])
- >>> keys = [r[1] for r in data] # precomputed list of keys
+ >>> data.sort(key=lambda r: r[1]) # Or use operator.itemgetter(1).
+ >>> keys = [r[1] for r in data] # Precompute a list of keys.
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
diff --git a/Doc/tools/susp-ignored.csv b/Doc/tools/susp-ignored.csv
index 7be8d0abd69a5..f85d6946954d6 100644
--- a/Doc/tools/susp-ignored.csv
+++ b/Doc/tools/susp-ignored.csv
@@ -111,8 +111,6 @@ howto/urllib2,,:password,"""joe:password@example.com"""
library/ast,,:upper,lower:upper
library/ast,,:step,lower:upper:step
library/audioop,,:ipos,"# factor = audioop.findfactor(in_test[ipos*2:ipos*2+len(out_test)],"
-library/bisect,32,:hi,all(val >= x for val in a[i:hi])
-library/bisect,42,:hi,all(val > x for val in a[i:hi])
library/configparser,,:home,my_dir: ${Common:home_dir}/twosheds
library/configparser,,:option,${section:option}
library/configparser,,:path,python_dir: ${Frameworks:path}/Python/Versions/${Frameworks:Python}
diff --git a/Lib/bisect.py b/Lib/bisect.py
index 8336a4ed9ca0f..d37da74f7b405 100644
--- a/Lib/bisect.py
+++ b/Lib/bisect.py
@@ -1,6 +1,7 @@
"""Bisection algorithms."""
-def insort_right(a, x, lo=0, hi=None):
+
+def insort_right(a, x, lo=0, hi=None, *, key=None):
"""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.
@@ -8,11 +9,14 @@ def insort_right(a, x, lo=0, hi=None):
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
-
- lo = bisect_right(a, x, lo, hi)
+ if key is None:
+ lo = bisect_right(a, x, lo, hi)
+ else:
+ lo = bisect_right(a, key(x), lo, hi, key=key)
a.insert(lo, x)
-def bisect_right(a, x, lo=0, hi=None):
+
+def bisect_right(a, x, lo=0, hi=None, *, key=None):
"""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
@@ -27,14 +31,26 @@ def bisect_right(a, x, lo=0, hi=None):
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
- while lo < hi:
- mid = (lo+hi)//2
- # Use __lt__ to match the logic in list.sort() and in heapq
- if x < a[mid]: hi = mid
- else: lo = mid+1
+ # Note, the comparison uses "<" to match the
+ # __lt__() logic in list.sort() and in heapq.
+ if key is None:
+ while lo < hi:
+ mid = (lo + hi) // 2
+ if x < a[mid]:
+ hi = mid
+ else:
+ lo = mid + 1
+ else:
+ while lo < hi:
+ mid = (lo + hi) // 2
+ if x < key(a[mid]):
+ hi = mid
+ else:
+ lo = mid + 1
return lo
-def insort_left(a, x, lo=0, hi=None):
+
+def insort_left(a, x, lo=0, hi=None, *, key=None):
"""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.
@@ -43,11 +59,13 @@ def insort_left(a, x, lo=0, hi=None):
slice of a to be searched.
"""
- lo = bisect_left(a, x, lo, hi)
+ if key is None:
+ lo = bisect_left(a, x, lo, hi)
+ else:
+ lo = bisect_left(a, key(x), lo, hi, key=key)
a.insert(lo, x)
-
-def bisect_left(a, x, lo=0, hi=None):
+def bisect_left(a, x, lo=0, hi=None, *, key=None):
"""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
@@ -62,13 +80,25 @@ def bisect_left(a, x, lo=0, hi=None):
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
- while lo < hi:
- mid = (lo+hi)//2
- # Use __lt__ to match the logic in list.sort() and in heapq
- if a[mid] < x: lo = mid+1
- else: hi = mid
+ # Note, the comparison uses "<" to match the
+ # __lt__() logic in list.sort() and in heapq.
+ if key is None:
+ while lo < hi:
+ mid = (lo + hi) // 2
+ if a[mid] < x:
+ lo = mid + 1
+ else:
+ hi = mid
+ else:
+ while lo < hi:
+ mid = (lo + hi) // 2
+ if key(a[mid]) < x:
+ lo = mid + 1
+ else:
+ hi = mid
return lo
+
# Overwrite above definitions with a fast C implementation
try:
from _bisect import *
diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py
index fc7990d765e53..20f8b9d7c0aa8 100644
--- a/Lib/test/test_bisect.py
+++ b/Lib/test/test_bisect.py
@@ -200,6 +200,63 @@ def test_keyword_args(self):
self.module.insort(a=data, x=25, lo=1, hi=3)
self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
+ def test_lookups_with_key_function(self):
+ mod = self.module
+
+ # Invariant: Index with a keyfunc on an array
+ # should match the index on an array where
+ # key function has already been applied.
+
+ keyfunc = abs
+ arr = sorted([2, -4, 6, 8, -10], key=keyfunc)
+ precomputed_arr = list(map(keyfunc, arr))
+ for x in precomputed_arr:
+ self.assertEqual(
+ mod.bisect_left(arr, x, key=keyfunc),
+ mod.bisect_left(precomputed_arr, x)
+ )
+ self.assertEqual(
+ mod.bisect_right(arr, x, key=keyfunc),
+ mod.bisect_right(precomputed_arr, x)
+ )
+
+ keyfunc = str.casefold
+ arr = sorted('aBcDeEfgHhiIiij', key=keyfunc)
+ precomputed_arr = list(map(keyfunc, arr))
+ for x in precomputed_arr:
+ self.assertEqual(
+ mod.bisect_left(arr, x, key=keyfunc),
+ mod.bisect_left(precomputed_arr, x)
+ )
+ self.assertEqual(
+ mod.bisect_right(arr, x, key=keyfunc),
+ mod.bisect_right(precomputed_arr, x)
+ )
+
+ def test_insort(self):
+ from random import shuffle
+ mod = self.module
+
+ # Invariant: As random elements are inserted in
+ # a target list, the targetlist remains sorted.
+ keyfunc = abs
+ data = list(range(-10, 11)) + list(range(-20, 20, 2))
+ shuffle(data)
+ target = []
+ for x in data:
+ mod.insort_left(target, x, key=keyfunc)
+ self.assertEqual(
+ sorted(target, key=keyfunc),
+ target
+ )
+ target = []
+ for x in data:
+ mod.insort_right(target, x, key=keyfunc)
+ self.assertEqual(
+ sorted(target, key=keyfunc),
+ target
+ )
+
class TestBisectPython(TestBisect, unittest.TestCase):
module = py_bisect
diff --git a/Misc/NEWS.d/next/Library/2020-05-31-10-48-47.bpo-4356.P8kXqp.rst b/Misc/NEWS.d/next/Library/2020-05-31-10-48-47.bpo-4356.P8kXqp.rst
new file mode 100644
index 0000000000000..f5211d8a76f74
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2020-05-31-10-48-47.bpo-4356.P8kXqp.rst
@@ -0,0 +1 @@
+Add a key function to the bisect module.
diff --git a/Modules/_bisectmodule.c b/Modules/_bisectmodule.c
index 277e9755f2721..2d7c15bc1744b 100644
--- a/Modules/_bisectmodule.c
+++ b/Modules/_bisectmodule.c
@@ -16,7 +16,8 @@ module _bisect
_Py_IDENTIFIER(insert);
static inline Py_ssize_t
-internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
+internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
+ PyObject* key)
{
PyObject *litem;
Py_ssize_t mid;
@@ -39,6 +40,14 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t
litem = PySequence_GetItem(list, mid);
if (litem == NULL)
return -1;
+ if (key != Py_None) {
+ PyObject *newitem = PyObject_CallOneArg(key, litem);
+ if (newitem == NULL) {
+ Py_DECREF(litem);
+ return -1;
+ }
+ Py_SETREF(litem, newitem);
+ }
res = PyObject_RichCompareBool(item, litem, Py_LT);
Py_DECREF(litem);
if (res < 0)
@@ -58,6 +67,8 @@ _bisect.bisect_right -> Py_ssize_t
x: object
lo: Py_ssize_t = 0
hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+ *
+ key: object = None
Return the index where to insert item x in list a, assuming a is sorted.
@@ -71,10 +82,10 @@ slice of a to be searched.
static Py_ssize_t
_bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi)
-/*[clinic end generated code: output=419e150cf1d2a235 input=e72212b282c83375]*/
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
+/*[clinic end generated code: output=3a4bc09cc7c8a73d input=1313e9ca20c8bc3c]*/
{
- return internal_bisect_right(a, x, lo, hi);
+ return internal_bisect_right(a, x, lo, hi, key);
}
/*[clinic input]
@@ -84,6 +95,8 @@ _bisect.insort_right
x: object
lo: Py_ssize_t = 0
hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+ *
+ key: object = None
Insert item x in list a, and keep it sorted assuming a is sorted.
@@ -95,11 +108,22 @@ slice of a to be searched.
static PyObject *
_bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi)
-/*[clinic end generated code: output=c2caa3d4cd02035a input=d1c45bfa68182669]*/
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
+/*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/
{
- PyObject *result;
- Py_ssize_t index = internal_bisect_right(a, x, lo, hi);
+ PyObject *result, *key_x;
+ Py_ssize_t index;
+
+ if (key == Py_None) {
+ index = internal_bisect_right(a, x, lo, hi, key);
+ } else {
+ key_x = PyObject_CallOneArg(key, x);
+ if (x == NULL) {
+ return NULL;
+ }
+ index = internal_bisect_right(a, key_x, lo, hi, key);
+ Py_DECREF(key_x);
+ }
if (index < 0)
return NULL;
if (PyList_CheckExact(a)) {
@@ -117,7 +141,8 @@ _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
}
static inline Py_ssize_t
-internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
+internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
+ PyObject *key)
{
PyObject *litem;
Py_ssize_t mid;
@@ -140,6 +165,14 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h
litem = PySequence_GetItem(list, mid);
if (litem == NULL)
return -1;
+ if (key != Py_None) {
+ PyObject *newitem = PyObject_CallOneArg(key, litem);
+ if (newitem == NULL) {
+ Py_DECREF(litem);
+ return -1;
+ }
+ Py_SETREF(litem, newitem);
+ }
res = PyObject_RichCompareBool(litem, item, Py_LT);
Py_DECREF(litem);
if (res < 0)
@@ -160,6 +193,8 @@ _bisect.bisect_left -> Py_ssize_t
x: object
lo: Py_ssize_t = 0
hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+ *
+ key: object = None
Return the index where to insert item x in list a, assuming a is sorted.
@@ -173,10 +208,10 @@ slice of a to be searched.
static Py_ssize_t
_bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi)
-/*[clinic end generated code: output=af82168bc2856f24 input=2bd90f34afe5609f]*/
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
+/*[clinic end generated code: output=70749d6e5cae9284 input=3cbeec690f2f6c6e]*/
{
- return internal_bisect_left(a, x, lo, hi);
+ return internal_bisect_left(a, x, lo, hi, key);
}
@@ -187,6 +222,8 @@ _bisect.insort_left
x: object
lo: Py_ssize_t = 0
hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+ *
+ key: object = None
Insert item x in list a, and keep it sorted assuming a is sorted.
@@ -198,11 +235,22 @@ slice of a to be searched.
static PyObject *
_bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi)
-/*[clinic end generated code: output=9e8356c0844a182b input=bc4583308bce00cc]*/
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
+/*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/
{
- PyObject *result;
- Py_ssize_t index = internal_bisect_left(a, x, lo, hi);
+ PyObject *result, *key_x;
+ Py_ssize_t index;
+
+ if (key == Py_None) {
+ index = internal_bisect_left(a, x, lo, hi, key);
+ } else {
+ key_x = PyObject_CallOneArg(key, x);
+ if (x == NULL) {
+ return NULL;
+ }
+ index = internal_bisect_left(a, key_x, lo, hi, key);
+ Py_DECREF(key_x);
+ }
if (index < 0)
return NULL;
if (PyList_CheckExact(a)) {
diff --git a/Modules/clinic/_bisectmodule.c.h b/Modules/clinic/_bisectmodule.c.h
index 07fc9060d1d8f..304e46cf158a7 100644
--- a/Modules/clinic/_bisectmodule.c.h
+++ b/Modules/clinic/_bisectmodule.c.h
@@ -3,7 +3,7 @@ preserve
[clinic start generated code]*/
PyDoc_STRVAR(_bisect_bisect_right__doc__,
-"bisect_right($module, /, a, x, lo=0, hi=None)\n"
+"bisect_right($module, /, a, x, lo=0, hi=None, *, key=None)\n"
"--\n"
"\n"
"Return the index where to insert item x in list a, assuming a is sorted.\n"
@@ -20,20 +20,21 @@ PyDoc_STRVAR(_bisect_bisect_right__doc__,
static Py_ssize_t
_bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi);
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
static PyObject *
_bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
PyObject *return_value = NULL;
- static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+ static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static _PyArg_Parser _parser = {NULL, _keywords, "bisect_right", 0};
- PyObject *argsbuf[4];
+ PyObject *argsbuf[5];
Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
PyObject *a;
PyObject *x;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
+ PyObject *key = Py_None;
Py_ssize_t _return_value;
args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
@@ -62,11 +63,21 @@ _bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs,
goto skip_optional_pos;
}
}
- if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
- goto exit;
+ if (args[3]) {
+ if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+ goto exit;
+ }
+ if (!--noptargs) {
+ goto skip_optional_pos;
+ }
}
skip_optional_pos:
- _return_value = _bisect_bisect_right_impl(module, a, x, lo, hi);
+ if (!noptargs) {
+ goto skip_optional_kwonly;
+ }
+ key = args[4];
+skip_optional_kwonly:
+ _return_value = _bisect_bisect_right_impl(module, a, x, lo, hi, key);
if ((_return_value == -1) && PyErr_Occurred()) {
goto exit;
}
@@ -77,7 +88,7 @@ _bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs,
}
PyDoc_STRVAR(_bisect_insort_right__doc__,
-"insort_right($module, /, a, x, lo=0, hi=None)\n"
+"insort_right($module, /, a, x, lo=0, hi=None, *, key=None)\n"
"--\n"
"\n"
"Insert item x in list a, and keep it sorted assuming a is sorted.\n"
@@ -92,20 +103,21 @@ PyDoc_STRVAR(_bisect_insort_right__doc__,
static PyObject *
_bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi);
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
static PyObject *
_bisect_insort_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
PyObject *return_value = NULL;
- static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+ static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static _PyArg_Parser _parser = {NULL, _keywords, "insort_right", 0};
- PyObject *argsbuf[4];
+ PyObject *argsbuf[5];
Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
PyObject *a;
PyObject *x;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
+ PyObject *key = Py_None;
args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
if (!args) {
@@ -133,18 +145,28 @@ _bisect_insort_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs,
goto skip_optional_pos;
}
}
- if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
- goto exit;
+ if (args[3]) {
+ if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+ goto exit;
+ }
+ if (!--noptargs) {
+ goto skip_optional_pos;
+ }
}
skip_optional_pos:
- return_value = _bisect_insort_right_impl(module, a, x, lo, hi);
+ if (!noptargs) {
+ goto skip_optional_kwonly;
+ }
+ key = args[4];
+skip_optional_kwonly:
+ return_value = _bisect_insort_right_impl(module, a, x, lo, hi, key);
exit:
return return_value;
}
PyDoc_STRVAR(_bisect_bisect_left__doc__,
-"bisect_left($module, /, a, x, lo=0, hi=None)\n"
+"bisect_left($module, /, a, x, lo=0, hi=None, *, key=None)\n"
"--\n"
"\n"
"Return the index where to insert item x in list a, assuming a is sorted.\n"
@@ -161,20 +183,21 @@ PyDoc_STRVAR(_bisect_bisect_left__doc__,
static Py_ssize_t
_bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi);
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
static PyObject *
_bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
PyObject *return_value = NULL;
- static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+ static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static _PyArg_Parser _parser = {NULL, _keywords, "bisect_left", 0};
- PyObject *argsbuf[4];
+ PyObject *argsbuf[5];
Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
PyObject *a;
PyObject *x;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
+ PyObject *key = Py_None;
Py_ssize_t _return_value;
args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
@@ -203,11 +226,21 @@ _bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, P
goto skip_optional_pos;
}
}
- if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
- goto exit;
+ if (args[3]) {
+ if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+ goto exit;
+ }
+ if (!--noptargs) {
+ goto skip_optional_pos;
+ }
}
skip_optional_pos:
- _return_value = _bisect_bisect_left_impl(module, a, x, lo, hi);
+ if (!noptargs) {
+ goto skip_optional_kwonly;
+ }
+ key = args[4];
+skip_optional_kwonly:
+ _return_value = _bisect_bisect_left_impl(module, a, x, lo, hi, key);
if ((_return_value == -1) && PyErr_Occurred()) {
goto exit;
}
@@ -218,7 +251,7 @@ _bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, P
}
PyDoc_STRVAR(_bisect_insort_left__doc__,
-"insort_left($module, /, a, x, lo=0, hi=None)\n"
+"insort_left($module, /, a, x, lo=0, hi=None, *, key=None)\n"
"--\n"
"\n"
"Insert item x in list a, and keep it sorted assuming a is sorted.\n"
@@ -233,20 +266,21 @@ PyDoc_STRVAR(_bisect_insort_left__doc__,
static PyObject *
_bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi);
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
static PyObject *
_bisect_insort_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
PyObject *return_value = NULL;
- static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+ static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static _PyArg_Parser _parser = {NULL, _keywords, "insort_left", 0};
- PyObject *argsbuf[4];
+ PyObject *argsbuf[5];
Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
PyObject *a;
PyObject *x;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
+ PyObject *key = Py_None;
args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
if (!args) {
@@ -274,13 +308,23 @@ _bisect_insort_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, P
goto skip_optional_pos;
}
}
- if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
- goto exit;
+ if (args[3]) {
+ if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+ goto exit;
+ }
+ if (!--noptargs) {
+ goto skip_optional_pos;
+ }
}
skip_optional_pos:
- return_value = _bisect_insort_left_impl(module, a, x, lo, hi);
+ if (!noptargs) {
+ goto skip_optional_kwonly;
+ }
+ key = args[4];
+skip_optional_kwonly:
+ return_value = _bisect_insort_left_impl(module, a, x, lo, hi, key);
exit:
return return_value;
}
-/*[clinic end generated code: output=6cf46f205659f01a input=a9049054013a1b77]*/
+/*[clinic end generated code: output=b3a5be025aa4ed7e input=a9049054013a1b77]*/
_______________________________________________
Python-checkins mailing list
Python-checkins@python.org
https://mail.python.org/mailman/listinfo/python-checkins
commit: 871934d4cf00687b3d1411c6e344af311646c1ae
branch: master
author: Raymond Hettinger <rhettinger@users.noreply.github.com>
committer: GitHub <noreply@github.com>
date: 2020-10-19T22:04:01-07:00
summary:
bpo-4356: Add key function support to the bisect module (GH-20556)
files:
A Misc/NEWS.d/next/Library/2020-05-31-10-48-47.bpo-4356.P8kXqp.rst
M Doc/library/bisect.rst
M Doc/tools/susp-ignored.csv
M Lib/bisect.py
M Lib/test/test_bisect.py
M Modules/_bisectmodule.c
M Modules/clinic/_bisectmodule.c.h
diff --git a/Doc/library/bisect.rst b/Doc/library/bisect.rst
index 6bf7814b257f4..f34ee175ba657 100644
--- a/Doc/library/bisect.rst
+++ b/Doc/library/bisect.rst
@@ -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))
+.. function:: bisect_left(a, x, lo=0, hi=len(a), *, key=None)
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
@@ -31,39 +31,106 @@ The following functions are provided:
parameter to ``list.insert()`` assuming that *a* is already sorted.
The returned insertion point *i* partitions the array *a* into two halves so
- 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.
+ 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* specifies a :term:`key function` of one argument that is used to
+ extract a comparison key from each input element. The default value is
+ ``None`` (compare the elements directly).
+
+ .. versionchanged:: 3.10
+ Added the *key* parameter.
+
+
+.. function:: bisect_right(a, x, lo=0, hi=len(a), *, key=None)
bisect(a, x, lo=0, hi=len(a))
Similar to :func:`bisect_left`, but returns an insertion point which comes
after (to the right of) any existing entries of *x* in *a*.
The returned insertion point *i* partitions the array *a* into two halves so
- 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.
+ 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.
+
+ *key* specifies a :term:`key function` of one argument that is used to
+ extract a comparison key from each input element. The default value is
+ ``None`` (compare the elements directly).
+
+ .. versionchanged:: 3.10
+ Added the *key* parameter.
+
-.. function:: insort_left(a, x, lo=0, hi=len(a))
+.. function:: insort_left(a, x, lo=0, hi=len(a), *, key=None)
- 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.
+ Insert *x* in *a* in sorted order.
-.. function:: insort_right(a, x, lo=0, hi=len(a))
+ *key* specifies a :term:`key function` of one argument that is used to
+ extract a comparison key from each input element. The default value is
+ ``None`` (compare the elements directly).
+
+ This function first runs :func:`bisect_left` to locate an insertion point.
+ Next, it runs the :meth:`insert` method on *a* to insert *x* at the
+ appropriate position to maintain sort order.
+
+ Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
+ insertion step.
+
+ .. versionchanged:: 3.10
+ Added the *key* parameter.
+
+
+.. function:: insort_right(a, x, lo=0, hi=len(a), *, key=None)
insort(a, x, lo=0, hi=len(a))
Similar to :func:`insort_left`, but inserting *x* in *a* after any existing
entries of *x*.
+ *key* specifies a :term:`key function` of one argument that is used to
+ extract a comparison key from each input element. The default value is
+ ``None`` (compare the elements directly).
+
+ This function first runs :func:`bisect_right` to locate an insertion point.
+ Next, it runs the :meth:`insert` method on *a* to insert *x* at the
+ appropriate position to maintain sort order.
+
+ Keep in mind that the ``O(log n)`` search is dominated by the slow O(n)
+ insertion step.
+
+ .. versionchanged:: 3.10
+ Added the *key* parameter.
+
+
+Performance Notes
+-----------------
+
+When writing time sensitive code using *bisect()* and *insort()*, keep these
+thoughts in mind:
+
+* Bisection is effective for searching ranges of values.
+ For locating specific values, dictionaries are more performant.
+
+* The *insort()* functions are ``O(n)`` because the logarithmic search step
+ is dominated by the linear time insertion step.
+
+* The search functions are stateless and discard key function results after
+ they are used. Consequently, if the search functions are used in a loop,
+ the key function may be called again and again on the same array elements.
+ If the key function isn't fast, consider wrapping it with
+ :func:`functools.cache` to avoid duplicate computations. Alternatively,
+ consider searching an array of precomputed keys to locate the insertion
+ point (as shown in the examples section below).
+
.. seealso::
- `SortedCollection recipe
- <https://code.activestate.com/recipes/577197-sortedcollection/>`_ that uses
- bisect to build a full-featured collection class with straight-forward search
- methods and support for a key-function. The keys are precomputed to save
- unnecessary calls to the key function during searches.
+ * `Sorted Collections
+ <http://www.grantjenks.com/docs/sortedcollections/>`_ is a high performance
+ module that uses *bisect* to managed sorted collections of data.
+
+ * The `SortedCollection recipe
+ <https://code.activestate.com/recipes/577197-sortedcollection/>`_ uses
+ bisect to build a full-featured collection class with straight-forward search
+ methods and support for a key-function. The keys are precomputed to save
+ unnecessary calls to the key function during searches.
Searching Sorted Lists
@@ -110,8 +177,8 @@ lists::
raise ValueError
-Other Examples
---------------
+Examples
+--------
.. _bisect-example:
@@ -127,17 +194,12 @@ a 'B', and so on::
>>> [.grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']
-Unlike the :func:`sorted` function, it does not make sense for the :func:`bisect`
-functions to have *key* or *reversed* arguments because that would lead to an
-inefficient design (successive calls to bisect functions would not "remember"
-all of the previous key lookups).
-
-Instead, it is better to search a list of precomputed keys to find the index
-of the record in question::
+One technique to avoid repeated calls to a key function is to search a list of
+precomputed keys to find the index of a record::
>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
- >>> data.sort(key=lambda r: r[1])
- >>> keys = [r[1] for r in data] # precomputed list of keys
+ >>> data.sort(key=lambda r: r[1]) # Or use operator.itemgetter(1).
+ >>> keys = [r[1] for r in data] # Precompute a list of keys.
>>> data[bisect_left(keys, 0)]
('black', 0)
>>> data[bisect_left(keys, 1)]
diff --git a/Doc/tools/susp-ignored.csv b/Doc/tools/susp-ignored.csv
index 7be8d0abd69a5..f85d6946954d6 100644
--- a/Doc/tools/susp-ignored.csv
+++ b/Doc/tools/susp-ignored.csv
@@ -111,8 +111,6 @@ howto/urllib2,,:password,"""joe:password@example.com"""
library/ast,,:upper,lower:upper
library/ast,,:step,lower:upper:step
library/audioop,,:ipos,"# factor = audioop.findfactor(in_test[ipos*2:ipos*2+len(out_test)],"
-library/bisect,32,:hi,all(val >= x for val in a[i:hi])
-library/bisect,42,:hi,all(val > x for val in a[i:hi])
library/configparser,,:home,my_dir: ${Common:home_dir}/twosheds
library/configparser,,:option,${section:option}
library/configparser,,:path,python_dir: ${Frameworks:path}/Python/Versions/${Frameworks:Python}
diff --git a/Lib/bisect.py b/Lib/bisect.py
index 8336a4ed9ca0f..d37da74f7b405 100644
--- a/Lib/bisect.py
+++ b/Lib/bisect.py
@@ -1,6 +1,7 @@
"""Bisection algorithms."""
-def insort_right(a, x, lo=0, hi=None):
+
+def insort_right(a, x, lo=0, hi=None, *, key=None):
"""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.
@@ -8,11 +9,14 @@ def insort_right(a, x, lo=0, hi=None):
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
-
- lo = bisect_right(a, x, lo, hi)
+ if key is None:
+ lo = bisect_right(a, x, lo, hi)
+ else:
+ lo = bisect_right(a, key(x), lo, hi, key=key)
a.insert(lo, x)
-def bisect_right(a, x, lo=0, hi=None):
+
+def bisect_right(a, x, lo=0, hi=None, *, key=None):
"""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
@@ -27,14 +31,26 @@ def bisect_right(a, x, lo=0, hi=None):
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
- while lo < hi:
- mid = (lo+hi)//2
- # Use __lt__ to match the logic in list.sort() and in heapq
- if x < a[mid]: hi = mid
- else: lo = mid+1
+ # Note, the comparison uses "<" to match the
+ # __lt__() logic in list.sort() and in heapq.
+ if key is None:
+ while lo < hi:
+ mid = (lo + hi) // 2
+ if x < a[mid]:
+ hi = mid
+ else:
+ lo = mid + 1
+ else:
+ while lo < hi:
+ mid = (lo + hi) // 2
+ if x < key(a[mid]):
+ hi = mid
+ else:
+ lo = mid + 1
return lo
-def insort_left(a, x, lo=0, hi=None):
+
+def insort_left(a, x, lo=0, hi=None, *, key=None):
"""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.
@@ -43,11 +59,13 @@ def insort_left(a, x, lo=0, hi=None):
slice of a to be searched.
"""
- lo = bisect_left(a, x, lo, hi)
+ if key is None:
+ lo = bisect_left(a, x, lo, hi)
+ else:
+ lo = bisect_left(a, key(x), lo, hi, key=key)
a.insert(lo, x)
-
-def bisect_left(a, x, lo=0, hi=None):
+def bisect_left(a, x, lo=0, hi=None, *, key=None):
"""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
@@ -62,13 +80,25 @@ def bisect_left(a, x, lo=0, hi=None):
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
- while lo < hi:
- mid = (lo+hi)//2
- # Use __lt__ to match the logic in list.sort() and in heapq
- if a[mid] < x: lo = mid+1
- else: hi = mid
+ # Note, the comparison uses "<" to match the
+ # __lt__() logic in list.sort() and in heapq.
+ if key is None:
+ while lo < hi:
+ mid = (lo + hi) // 2
+ if a[mid] < x:
+ lo = mid + 1
+ else:
+ hi = mid
+ else:
+ while lo < hi:
+ mid = (lo + hi) // 2
+ if key(a[mid]) < x:
+ lo = mid + 1
+ else:
+ hi = mid
return lo
+
# Overwrite above definitions with a fast C implementation
try:
from _bisect import *
diff --git a/Lib/test/test_bisect.py b/Lib/test/test_bisect.py
index fc7990d765e53..20f8b9d7c0aa8 100644
--- a/Lib/test/test_bisect.py
+++ b/Lib/test/test_bisect.py
@@ -200,6 +200,63 @@ def test_keyword_args(self):
self.module.insort(a=data, x=25, lo=1, hi=3)
self.assertEqual(data, [10, 20, 25, 25, 25, 30, 40, 50])
+ def test_lookups_with_key_function(self):
+ mod = self.module
+
+ # Invariant: Index with a keyfunc on an array
+ # should match the index on an array where
+ # key function has already been applied.
+
+ keyfunc = abs
+ arr = sorted([2, -4, 6, 8, -10], key=keyfunc)
+ precomputed_arr = list(map(keyfunc, arr))
+ for x in precomputed_arr:
+ self.assertEqual(
+ mod.bisect_left(arr, x, key=keyfunc),
+ mod.bisect_left(precomputed_arr, x)
+ )
+ self.assertEqual(
+ mod.bisect_right(arr, x, key=keyfunc),
+ mod.bisect_right(precomputed_arr, x)
+ )
+
+ keyfunc = str.casefold
+ arr = sorted('aBcDeEfgHhiIiij', key=keyfunc)
+ precomputed_arr = list(map(keyfunc, arr))
+ for x in precomputed_arr:
+ self.assertEqual(
+ mod.bisect_left(arr, x, key=keyfunc),
+ mod.bisect_left(precomputed_arr, x)
+ )
+ self.assertEqual(
+ mod.bisect_right(arr, x, key=keyfunc),
+ mod.bisect_right(precomputed_arr, x)
+ )
+
+ def test_insort(self):
+ from random import shuffle
+ mod = self.module
+
+ # Invariant: As random elements are inserted in
+ # a target list, the targetlist remains sorted.
+ keyfunc = abs
+ data = list(range(-10, 11)) + list(range(-20, 20, 2))
+ shuffle(data)
+ target = []
+ for x in data:
+ mod.insort_left(target, x, key=keyfunc)
+ self.assertEqual(
+ sorted(target, key=keyfunc),
+ target
+ )
+ target = []
+ for x in data:
+ mod.insort_right(target, x, key=keyfunc)
+ self.assertEqual(
+ sorted(target, key=keyfunc),
+ target
+ )
+
class TestBisectPython(TestBisect, unittest.TestCase):
module = py_bisect
diff --git a/Misc/NEWS.d/next/Library/2020-05-31-10-48-47.bpo-4356.P8kXqp.rst b/Misc/NEWS.d/next/Library/2020-05-31-10-48-47.bpo-4356.P8kXqp.rst
new file mode 100644
index 0000000000000..f5211d8a76f74
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2020-05-31-10-48-47.bpo-4356.P8kXqp.rst
@@ -0,0 +1 @@
+Add a key function to the bisect module.
diff --git a/Modules/_bisectmodule.c b/Modules/_bisectmodule.c
index 277e9755f2721..2d7c15bc1744b 100644
--- a/Modules/_bisectmodule.c
+++ b/Modules/_bisectmodule.c
@@ -16,7 +16,8 @@ module _bisect
_Py_IDENTIFIER(insert);
static inline Py_ssize_t
-internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
+internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
+ PyObject* key)
{
PyObject *litem;
Py_ssize_t mid;
@@ -39,6 +40,14 @@ internal_bisect_right(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t
litem = PySequence_GetItem(list, mid);
if (litem == NULL)
return -1;
+ if (key != Py_None) {
+ PyObject *newitem = PyObject_CallOneArg(key, litem);
+ if (newitem == NULL) {
+ Py_DECREF(litem);
+ return -1;
+ }
+ Py_SETREF(litem, newitem);
+ }
res = PyObject_RichCompareBool(item, litem, Py_LT);
Py_DECREF(litem);
if (res < 0)
@@ -58,6 +67,8 @@ _bisect.bisect_right -> Py_ssize_t
x: object
lo: Py_ssize_t = 0
hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+ *
+ key: object = None
Return the index where to insert item x in list a, assuming a is sorted.
@@ -71,10 +82,10 @@ slice of a to be searched.
static Py_ssize_t
_bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi)
-/*[clinic end generated code: output=419e150cf1d2a235 input=e72212b282c83375]*/
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
+/*[clinic end generated code: output=3a4bc09cc7c8a73d input=1313e9ca20c8bc3c]*/
{
- return internal_bisect_right(a, x, lo, hi);
+ return internal_bisect_right(a, x, lo, hi, key);
}
/*[clinic input]
@@ -84,6 +95,8 @@ _bisect.insort_right
x: object
lo: Py_ssize_t = 0
hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+ *
+ key: object = None
Insert item x in list a, and keep it sorted assuming a is sorted.
@@ -95,11 +108,22 @@ slice of a to be searched.
static PyObject *
_bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi)
-/*[clinic end generated code: output=c2caa3d4cd02035a input=d1c45bfa68182669]*/
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
+/*[clinic end generated code: output=ac3bf26d07aedda2 input=44e1708e26b7b802]*/
{
- PyObject *result;
- Py_ssize_t index = internal_bisect_right(a, x, lo, hi);
+ PyObject *result, *key_x;
+ Py_ssize_t index;
+
+ if (key == Py_None) {
+ index = internal_bisect_right(a, x, lo, hi, key);
+ } else {
+ key_x = PyObject_CallOneArg(key, x);
+ if (x == NULL) {
+ return NULL;
+ }
+ index = internal_bisect_right(a, key_x, lo, hi, key);
+ Py_DECREF(key_x);
+ }
if (index < 0)
return NULL;
if (PyList_CheckExact(a)) {
@@ -117,7 +141,8 @@ _bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
}
static inline Py_ssize_t
-internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
+internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi,
+ PyObject *key)
{
PyObject *litem;
Py_ssize_t mid;
@@ -140,6 +165,14 @@ internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t h
litem = PySequence_GetItem(list, mid);
if (litem == NULL)
return -1;
+ if (key != Py_None) {
+ PyObject *newitem = PyObject_CallOneArg(key, litem);
+ if (newitem == NULL) {
+ Py_DECREF(litem);
+ return -1;
+ }
+ Py_SETREF(litem, newitem);
+ }
res = PyObject_RichCompareBool(litem, item, Py_LT);
Py_DECREF(litem);
if (res < 0)
@@ -160,6 +193,8 @@ _bisect.bisect_left -> Py_ssize_t
x: object
lo: Py_ssize_t = 0
hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+ *
+ key: object = None
Return the index where to insert item x in list a, assuming a is sorted.
@@ -173,10 +208,10 @@ slice of a to be searched.
static Py_ssize_t
_bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi)
-/*[clinic end generated code: output=af82168bc2856f24 input=2bd90f34afe5609f]*/
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
+/*[clinic end generated code: output=70749d6e5cae9284 input=3cbeec690f2f6c6e]*/
{
- return internal_bisect_left(a, x, lo, hi);
+ return internal_bisect_left(a, x, lo, hi, key);
}
@@ -187,6 +222,8 @@ _bisect.insort_left
x: object
lo: Py_ssize_t = 0
hi: Py_ssize_t(c_default='-1', accept={int, NoneType}) = None
+ *
+ key: object = None
Insert item x in list a, and keep it sorted assuming a is sorted.
@@ -198,11 +235,22 @@ slice of a to be searched.
static PyObject *
_bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi)
-/*[clinic end generated code: output=9e8356c0844a182b input=bc4583308bce00cc]*/
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key)
+/*[clinic end generated code: output=b1d33e5e7ffff11e input=3ab65d8784f585b1]*/
{
- PyObject *result;
- Py_ssize_t index = internal_bisect_left(a, x, lo, hi);
+ PyObject *result, *key_x;
+ Py_ssize_t index;
+
+ if (key == Py_None) {
+ index = internal_bisect_left(a, x, lo, hi, key);
+ } else {
+ key_x = PyObject_CallOneArg(key, x);
+ if (x == NULL) {
+ return NULL;
+ }
+ index = internal_bisect_left(a, key_x, lo, hi, key);
+ Py_DECREF(key_x);
+ }
if (index < 0)
return NULL;
if (PyList_CheckExact(a)) {
diff --git a/Modules/clinic/_bisectmodule.c.h b/Modules/clinic/_bisectmodule.c.h
index 07fc9060d1d8f..304e46cf158a7 100644
--- a/Modules/clinic/_bisectmodule.c.h
+++ b/Modules/clinic/_bisectmodule.c.h
@@ -3,7 +3,7 @@ preserve
[clinic start generated code]*/
PyDoc_STRVAR(_bisect_bisect_right__doc__,
-"bisect_right($module, /, a, x, lo=0, hi=None)\n"
+"bisect_right($module, /, a, x, lo=0, hi=None, *, key=None)\n"
"--\n"
"\n"
"Return the index where to insert item x in list a, assuming a is sorted.\n"
@@ -20,20 +20,21 @@ PyDoc_STRVAR(_bisect_bisect_right__doc__,
static Py_ssize_t
_bisect_bisect_right_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi);
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
static PyObject *
_bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
PyObject *return_value = NULL;
- static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+ static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static _PyArg_Parser _parser = {NULL, _keywords, "bisect_right", 0};
- PyObject *argsbuf[4];
+ PyObject *argsbuf[5];
Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
PyObject *a;
PyObject *x;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
+ PyObject *key = Py_None;
Py_ssize_t _return_value;
args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
@@ -62,11 +63,21 @@ _bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs,
goto skip_optional_pos;
}
}
- if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
- goto exit;
+ if (args[3]) {
+ if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+ goto exit;
+ }
+ if (!--noptargs) {
+ goto skip_optional_pos;
+ }
}
skip_optional_pos:
- _return_value = _bisect_bisect_right_impl(module, a, x, lo, hi);
+ if (!noptargs) {
+ goto skip_optional_kwonly;
+ }
+ key = args[4];
+skip_optional_kwonly:
+ _return_value = _bisect_bisect_right_impl(module, a, x, lo, hi, key);
if ((_return_value == -1) && PyErr_Occurred()) {
goto exit;
}
@@ -77,7 +88,7 @@ _bisect_bisect_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs,
}
PyDoc_STRVAR(_bisect_insort_right__doc__,
-"insort_right($module, /, a, x, lo=0, hi=None)\n"
+"insort_right($module, /, a, x, lo=0, hi=None, *, key=None)\n"
"--\n"
"\n"
"Insert item x in list a, and keep it sorted assuming a is sorted.\n"
@@ -92,20 +103,21 @@ PyDoc_STRVAR(_bisect_insort_right__doc__,
static PyObject *
_bisect_insort_right_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi);
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
static PyObject *
_bisect_insort_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
PyObject *return_value = NULL;
- static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+ static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static _PyArg_Parser _parser = {NULL, _keywords, "insort_right", 0};
- PyObject *argsbuf[4];
+ PyObject *argsbuf[5];
Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
PyObject *a;
PyObject *x;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
+ PyObject *key = Py_None;
args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
if (!args) {
@@ -133,18 +145,28 @@ _bisect_insort_right(PyObject *module, PyObject *const *args, Py_ssize_t nargs,
goto skip_optional_pos;
}
}
- if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
- goto exit;
+ if (args[3]) {
+ if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+ goto exit;
+ }
+ if (!--noptargs) {
+ goto skip_optional_pos;
+ }
}
skip_optional_pos:
- return_value = _bisect_insort_right_impl(module, a, x, lo, hi);
+ if (!noptargs) {
+ goto skip_optional_kwonly;
+ }
+ key = args[4];
+skip_optional_kwonly:
+ return_value = _bisect_insort_right_impl(module, a, x, lo, hi, key);
exit:
return return_value;
}
PyDoc_STRVAR(_bisect_bisect_left__doc__,
-"bisect_left($module, /, a, x, lo=0, hi=None)\n"
+"bisect_left($module, /, a, x, lo=0, hi=None, *, key=None)\n"
"--\n"
"\n"
"Return the index where to insert item x in list a, assuming a is sorted.\n"
@@ -161,20 +183,21 @@ PyDoc_STRVAR(_bisect_bisect_left__doc__,
static Py_ssize_t
_bisect_bisect_left_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi);
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
static PyObject *
_bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
PyObject *return_value = NULL;
- static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+ static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static _PyArg_Parser _parser = {NULL, _keywords, "bisect_left", 0};
- PyObject *argsbuf[4];
+ PyObject *argsbuf[5];
Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
PyObject *a;
PyObject *x;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
+ PyObject *key = Py_None;
Py_ssize_t _return_value;
args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
@@ -203,11 +226,21 @@ _bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, P
goto skip_optional_pos;
}
}
- if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
- goto exit;
+ if (args[3]) {
+ if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+ goto exit;
+ }
+ if (!--noptargs) {
+ goto skip_optional_pos;
+ }
}
skip_optional_pos:
- _return_value = _bisect_bisect_left_impl(module, a, x, lo, hi);
+ if (!noptargs) {
+ goto skip_optional_kwonly;
+ }
+ key = args[4];
+skip_optional_kwonly:
+ _return_value = _bisect_bisect_left_impl(module, a, x, lo, hi, key);
if ((_return_value == -1) && PyErr_Occurred()) {
goto exit;
}
@@ -218,7 +251,7 @@ _bisect_bisect_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, P
}
PyDoc_STRVAR(_bisect_insort_left__doc__,
-"insort_left($module, /, a, x, lo=0, hi=None)\n"
+"insort_left($module, /, a, x, lo=0, hi=None, *, key=None)\n"
"--\n"
"\n"
"Insert item x in list a, and keep it sorted assuming a is sorted.\n"
@@ -233,20 +266,21 @@ PyDoc_STRVAR(_bisect_insort_left__doc__,
static PyObject *
_bisect_insort_left_impl(PyObject *module, PyObject *a, PyObject *x,
- Py_ssize_t lo, Py_ssize_t hi);
+ Py_ssize_t lo, Py_ssize_t hi, PyObject *key);
static PyObject *
_bisect_insort_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, PyObject *kwnames)
{
PyObject *return_value = NULL;
- static const char * const _keywords[] = {"a", "x", "lo", "hi", NULL};
+ static const char * const _keywords[] = {"a", "x", "lo", "hi", "key", NULL};
static _PyArg_Parser _parser = {NULL, _keywords, "insort_left", 0};
- PyObject *argsbuf[4];
+ PyObject *argsbuf[5];
Py_ssize_t noptargs = nargs + (kwnames ? PyTuple_GET_SIZE(kwnames) : 0) - 2;
PyObject *a;
PyObject *x;
Py_ssize_t lo = 0;
Py_ssize_t hi = -1;
+ PyObject *key = Py_None;
args = _PyArg_UnpackKeywords(args, nargs, NULL, kwnames, &_parser, 2, 4, 0, argsbuf);
if (!args) {
@@ -274,13 +308,23 @@ _bisect_insort_left(PyObject *module, PyObject *const *args, Py_ssize_t nargs, P
goto skip_optional_pos;
}
}
- if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
- goto exit;
+ if (args[3]) {
+ if (!_Py_convert_optional_to_ssize_t(args[3], &hi)) {
+ goto exit;
+ }
+ if (!--noptargs) {
+ goto skip_optional_pos;
+ }
}
skip_optional_pos:
- return_value = _bisect_insort_left_impl(module, a, x, lo, hi);
+ if (!noptargs) {
+ goto skip_optional_kwonly;
+ }
+ key = args[4];
+skip_optional_kwonly:
+ return_value = _bisect_insort_left_impl(module, a, x, lo, hi, key);
exit:
return return_value;
}
-/*[clinic end generated code: output=6cf46f205659f01a input=a9049054013a1b77]*/
+/*[clinic end generated code: output=b3a5be025aa4ed7e input=a9049054013a1b77]*/
_______________________________________________
Python-checkins mailing list
Python-checkins@python.org
https://mail.python.org/mailman/listinfo/python-checkins