classification
Title: range purports to implement the Sequence ABC, but is missing index and count methods
Type: behavior Stage: resolved
Components: Interpreter Core Versions: Python 3.2
process
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: stutzbach Nosy List: daniel.urban, eric.araujo, georg.brandl, mark.dickinson, rhettinger, stutzbach
Priority: critical Keywords: patch

Created on 2010-07-09 19:06 by stutzbach, last changed 2010-09-14 16:54 by stutzbach. This issue is now closed.

Files
File name Uploaded Description Edit
issue9213.diff daniel.urban, 2010-07-21 20:25 Patch (py3k branch)
issue9213a.diff daniel.urban, 2010-07-22 17:13 Patch (fixed refleak + tests) (py3k branch)
issue9213b.diff stutzbach, 2010-09-02 19:18 Adds support for non-longs, drops support for start/stop
Messages (13)
msg109784 - (view) Author: Daniel Stutzbach (stutzbach) (Python committer) Date: 2010-07-09 19:06
>>> isinstance(range, collections.Sequence)
True
>>> [method for method in set(dir(collections.Sequence)) - set(dir(range(1))) if not method.startswith('_')]
['index', 'count']
msg109785 - (view) Author: Daniel Stutzbach (stutzbach) (Python committer) Date: 2010-07-09 19:08
In Python 2.6 and 2.7, the same problem applies to xrange objects.
msg111112 - (view) Author: Daniel Urban (daniel.urban) * Date: 2010-07-21 20:25
The attached patch adds the range.count and range.index methods.
Pseudocode for the two method:

def count(self, ob):
    if ob in self:
        return 1
    else:
        return 0

def index(self, ob, start=0, stop=len(self)):
    if ob in self:
        idx = (ob - self.start) // self.step
        if start < 0:
            start = start + len(self)
        if stop < 0:
            stop = stop + len(self)
        if start <= idx < stop:
            return idx
    raise ValueError("{!r} is not in range".format(ob))
msg111195 - (view) Author: Daniel Urban (daniel.urban) * Date: 2010-07-22 17:13
Sorry, the previous patch has a reference leak. I'm attaching the fixed patch as issue9213a.diff (I also added a few tests with really big ranges).
msg114534 - (view) Author: Éric Araujo (eric.araujo) * (Python committer) Date: 2010-08-21 18:01
I can’t comment on C code, but the tests look good to me.
msg114633 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2010-08-22 01:25
I support adding index() and count() to range objects.
msg115396 - (view) Author: Daniel Stutzbach (stutzbach) (Python committer) Date: 2010-09-02 19:18
Thank you for the patch.

The patch doesn't handle the case where the object being searched for is !PyLong_CheckExact.  For example, the user might pass in a sub-type of int.  The existing range_contains supports that case, so it seems like we should support it in range_index and range_count.

The Sequence ABC's .index method doesn't include the optional start and stop parameters that are present on list.index.  Since it's not part of the ABC, it's not mandatory that we implement those for range.index.  The patch includes support for start and stop.

Attached is a greatly revised patch, with two significant changes:
- Adds support for !PyLong_CheckExact (using _PySequence_IterSearch)
- Drops support for the start and stop parameters to index

Dropping support for the start and stop parameters greatly simplified the code.  If we want to support start and stop, then the code will need to get more complicated to handle the !PyLong_CheckExact case (since PySequence_IterSearch doesn't support start and stop).

My patch abstracts out most of the code that had originally been in range_contains into a new function range_contains_long so that it can be called by range_contains, range_count, and range_index.  The diff makes that part look like a large change, but it's mostly a whitespace change (the refactored code lost one indentation level but is otherwise unchanged).

I uploaded Daniel Urban's patch and mine to Rietveld:
http://codereview.appspot.com/2146041/

Any strong feelings on whether range.index should support the start and stop arguments provided by list.index, tuple.index, and str.index, but not by collections.Sequence.index?
msg116018 - (view) Author: Daniel Urban (daniel.urban) * Date: 2010-09-10 13:30
> Attached is a greatly revised patch, with two significant changes:
> - Adds support for !PyLong_CheckExact (using _PySequence_IterSearch)

Thanks, indeed, we should support that.

> Any strong feelings on whether range.index should support the start and
> stop arguments provided by list.index, tuple.index, and str.index, but
> not by collections.Sequence.index?

I don't think that this is very important.
msg116120 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2010-09-11 21:18
I'd like to have this in 3.2.
msg116146 - (view) Author: Daniel Stutzbach (stutzbach) (Python committer) Date: 2010-09-12 03:52
Thanks, Georg, for prodding.  As a new committer, I have possibly been erring a little too far on the side of having my patches thoroughly reviewed before committing.

I'll commit the patch on Monday if no one raises objections (after re-testing, of course).
msg116352 - (view) Author: Daniel Stutzbach (stutzbach) (Python committer) Date: 2010-09-13 21:18
Committed as r84791.

Question: should this bugfix be backported to Python 3.1 and to xrange objects in Python 2.7?  Since it's a bugfix that adds new methods, it's a gray-area.  (same question applies to the closely related Issue #9212)
msg116372 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2010-09-14 06:30
I am -1 on adding new methods to builtins in bugfix releases.
msg116410 - (view) Author: Daniel Stutzbach (stutzbach) (Python committer) Date: 2010-09-14 16:54
Sounds reasonable to me.  I'll close this and the related 9212 (both fixes are already committed to the py3k branch).
History
Date User Action Args
2010-09-14 16:54:05stutzbachsetstatus: open -> closed

messages: + msg116410
stage: patch review -> resolved
2010-09-14 06:30:08georg.brandlsetmessages: + msg116372
2010-09-13 21:18:24stutzbachsetmessages: + msg116352
2010-09-12 03:52:52stutzbachsetresolution: accepted
messages: + msg116146
2010-09-11 21:18:15georg.brandlsetpriority: high -> critical
nosy: + georg.brandl
messages: + msg116120

2010-09-10 13:30:42daniel.urbansetmessages: + msg116018
2010-09-02 19:18:02stutzbachsetfiles: + issue9213b.diff

messages: + msg115396
2010-08-22 01:25:47rhettingersetmessages: + msg114633
2010-08-21 18:23:34gvanrossumsetnosy: - gvanrossum
2010-08-21 18:01:34eric.araujosetmessages: + msg114534
2010-07-22 17:13:58daniel.urbansetfiles: + issue9213a.diff

messages: + msg111195
2010-07-21 20:41:30pitrousetnosy: + gvanrossum, rhettinger, mark.dickinson
stage: test needed -> patch review

versions: - Python 2.6, Python 3.1, Python 2.7
2010-07-21 20:25:20daniel.urbansetfiles: + issue9213.diff

nosy: + daniel.urban
messages: + msg111112

keywords: + patch
2010-07-11 04:36:57rhettingersetpriority: normal -> high
2010-07-10 21:20:42eric.araujosetnosy: + eric.araujo
2010-07-09 19:08:11stutzbachsetmessages: + msg109785
versions: + Python 2.6, Python 2.7
2010-07-09 19:06:14stutzbachcreate