[Patches] [ python-Patches-1002085 ] O(1) xrange membership testing

[SourceForge.net]

Patches item #1002085, was opened at 2004-08-02 09:43
Message generated for change (Comment added) made by boredzo
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1002085&group_id=5470

Category: Core (C code)
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Mac-arena the Bored Zo (boredzo)
Assigned to: Nobody/Anonymous (nobody)
Summary: O(1) xrange membership testing

Initial Comment:
this patch applies to anonymous CVS as of 2004-08-02 at 07:
54:58 PDT.

it adds O(1) membership testing; for example:

Python 2.4a1+ (#2, Aug  2 2004, 09:11:43) 
[GCC 3.3 20030304 (Apple Computer, Inc. build 1495)] on 
darwin
Type "help", "copyright", "credits" or "license" for more 
information.
>>> import sys
>>> sys.maxint
2147483647
>>> sys.maxint in xrange(sys.maxint)
False

in current CVS, this would take untold hours to complete 
(because Python arrives at this answer by iterating on the 
sequence). this patch adds a __contains__ method to the 
xrange object which examines the xrange's pattern and 
determines the correct answer instantly based on that pattern.

----------------------------------------------------------------------

>Comment By: Mac-arena the Bored Zo (boredzo)
Date: 2004-08-02 12:42

Message:
Logged In: YES 
user_id=711099

found and fixed a bug: the new __contains__ method didn't check for 
an exception from PyInt_AsLong.

----------------------------------------------------------------------

Comment By: Mac-arena the Bored Zo (boredzo)
Date: 2004-08-02 11:25

Message:
Logged In: YES 
user_id=711099

heh, no I didn't check the checkbox. thanks for reminding me. :)

the original patch didn't include unit tests, but that is a good idea. ;) 
so I've added changes to test_xrange.py.

----------------------------------------------------------------------

Comment By: Ronald Oussoren (ronaldoussoren)
Date: 2004-08-02 10:28

Message:
Logged In: YES 
user_id=580910

You forgot to add the patch (did you check the checkbox?).

BTW. Does your patch include unittests?

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=1002085&group_id=5470