By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
464,638 Members | 1,109 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 464,638 IT Pros & Developers. It's quick & easy.

Is there a standard binary search with overridable comparisons?

P: n/a
I've got an ordered list of MyClasses that I want to be able to do
binary searches on, but against a tuple. MyClass has valid
__lt__(self, rhs) and __eq__(self, rhs) member functions that work
when rhs is a tuple.

This works:
l = [MyClass(..), MyClass(..), ...]
l.find((a,b))

But this doesn't:
bisect.bisect(l, (a,b))

I'm assuming this is because inside bisect, it does 'key < list[x]'
rather than 'list[x] < key', so it's the tuple's __lt__ that is
called, rather than MyClass's tuple.

Is there a way around this? Can I monkeypatch a new __lt__ into the
tuple class?

Here's some sample code that demonstrates the problem (it uses ints
rather than tuples, but the

import bisect
class MyC:
def __init__(self, v):
self.v = v

def __lt__(self, rhs):
return self.v < rhs

# cant search for int in a list of MyC's
l = sorted([MyC(x) for x in range(1000)])
bisect.bisect(l, 40)
1001 # AKA not found

# but, I can search for MyC in a list of ints
l = sorted(range(1000))
bisect.bisect(l, MyC(40))
41
Jun 27 '08 #1
Share this Question
Share on Google+
1 Reply

P: n/a
On Jun 18, 6:55 am, markscottwright <markscottwri...@gmail.comwrote:
I've got an ordered list of MyClasses that I want to be able to do
binary searches on, but against a tuple. MyClass has valid
__lt__(self, rhs) and __eq__(self, rhs) member functions that work
when rhs is a tuple.

This works:
l = [MyClass(..), MyClass(..), ...]
l.find((a,b))

But this doesn't:
bisect.bisect(l, (a,b))

I'm assuming
.... Don't. It can be dangerous.
this is because inside bisect, it does 'key < list[x]'
rather than 'list[x] < key', so it's the tuple's __lt__ that is
called, rather than MyClass's tuple.
Actually it appears (extremely gory details in Objects/object.c) that
it tries all rich comparison possibilities first:
tuple < myclass: not defined in tuple type
myclass tuple: not defined in MyClass
before falling through to the default (which is based on addresses).
>
Is there a way around this? Can I monkeypatch a new __lt__ into the
tuple class?
Looks like you need to implement MyClass.__gt__

I suspect someone will say that this section of the manual is trying
to tell us this:
"""
There are no reflected (swapped-argument) versions of these methods
(to be used when the left argument does not support the operation but
the right argument does); rather, __lt__() and __gt__() are each
other's reflection, __le__() and __ge__() are each other's reflection,
and __eq__() and __ne__() are their own reflection.
"""
.... "trying" being the operative word :-)

Alternatively, do you really need rich comparison? Consider defining
__cmp__ instead of 2 to 6 of the __lt__ etc brigade.

HTH,
John
Jun 27 '08 #2

This discussion thread is closed

Replies have been disabled for this discussion.