Is there a standard binary search with overridable comparisons?

John Machin sjmachin at lexicon.net
Wed Jun 18 01:36:32 CEST 2008


On Jun 18, 6:55 am, markscottwright <markscottwri... at gmail.com> wrote:
> 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



More information about the Python-list mailing list