how to convert code that uses cmp to python3

[Ian Kelly]

On Fri, Apr 8, 2016 at 3:23 AM, Steven D'Aprano <steve at pearwood.info> wrote:
> On Fri, 8 Apr 2016 06:34 pm, Marko Rauhamaa wrote:
>
>> Antoon Pardon <antoon.pardon at rece.vub.ac.be>:
>>
>>> In python2 descending the tree would only involve at most one
>>> expensive comparison, because using cmp would codify that comparison
>>> into an integer which would then be cheap to compare with 0. Now in
>>> python3, I may need to do two expensive comparisons, because there is
>>> no __cmp__ method, to make such a codefication.
>>
>> I think you should base your tree implementation on key.__lt__() only.
>> Only compare keys using <, nothing else, ever.
>
> I believe that's how list.sort() and sorted() work:
>
> py> class Spam(object):
> ...     def __init__(self, n):
> ...             self.n = n
> ...     def __lt__(self, other):
> ...             return self.n < other.n
> ...     def __repr__(self):
> ...             return repr(self.n)
> ...
> py> L = [Spam(5), Spam(3), Spam(9), Spam(1), Spam(2)]
> py> L
> [5, 3, 9, 1, 2]
> py> sorted(L)
> [1, 2, 3, 5, 9]
>
>
> as well as max() and min().

That's fine for those operations and probably insert, but how do you
search an AVL tree for a specific key without also using __eq__?