Title: Bisect upgrades: key/cmp/reverse, parameterized handedness
Type: Stage:
Components: Library (Lib) Versions: Python 2.7
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: dan.uznanski, rhettinger
Priority: normal Keywords: patch

Created on 2008-07-16 12:21 by dan.uznanski, last changed 2008-07-16 13:00 by rhettinger. This issue is now closed.

File name Uploaded Description Edit
bisect-2.7.diff dan.uznanski, 2008-07-16 12:21 A diff that upgrades bisect, its tests, and its documentation.
Messages (2)
msg69773 - (view) Author: Dan Uznanski (dan.uznanski) Date: 2008-07-16 12:21
Attached find a unified diff that upgrades the bisect module in two 
important ways:

1. bisect and friends now understand cmp, key, and reverse, the same way 
that list.sort does.

2. bisect and insort now have parameterized handedness: instead of using 
two different functions depending on whether you want new items to show 
up before or after existing ones, bisect and insort now take a flag 
called 'right' which can change the handedness on the fly.

Currently this code fails two existing regression tests: 
test_backcompatibility, because bisect is no longer the same as 
bisect_right; and test_non_sequence, because insort now raises 
AttributeError instead of TypeError when called on an int.

Still to do, in order of priority as perceived by me:

1. A C version of the code needs to be written.

2. The error handling should be worked over by somebody with more 
knowledge than I - the regression tests assume that particular failures 
(len-only, get-only, and non-sequence) will happen with one of TypeError 
or AttributeError when in reality they may raise the other.

3. The tests for new functionality should be made more exhaustive.

4. The in-module documentation probably needs cleaning; the rst 
documentation needs my name added to it (a good deal of the existing 
writing is still Fred L Drake's, so I won't replace) and needs to have 
the "section 3.6.4" part linked to Mutable Sequence Types; I couldn't 
find an actual example of that linkage.

5. The godawful conditions in bisect should probably get cleaned up.
msg69779 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-07-16 13:00

1. In Py3.0, the cmp argument has been dropped completely.  It has been 
supplanted by the key function.

2. Previous feature requests for cmp/key/reverse have been rejected. 
The problem is that in a series of searches or insertions the key 
function should not be called more than once (as it is with sort), but 
the bisect functions potentially call it many times will the same 
argument.  The granularity is wrong.  Adding the cmp/key/reverse 
arguments tends to discourage correct design with a separate key table 
and a set of indexes.

3. Guido has articulated as design principle that prefer separate 
functions to having a flag, so the separate handedness functions should 
not be combined.  Also, the current design reflects typical use cases 
where an app decides on a handedness and never changes that decision.  
It would be a waste to repeated pass in a handedness argument that 
never changes.

Marking this as rejected so that you don't lose more time writing C 
versions and whatnot.
Date User Action Args
2008-07-16 13:00:35rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg69779
2008-07-16 12:56:11georg.brandlsetassignee: rhettinger
nosy: + rhettinger
2008-07-16 12:21:35dan.uznanskicreate