Path: csiph.com!feeder.erje.net!1.eu.feeder.erje.net!newsfeed0.kamp.net!newsfeed.kamp.net!fu-berlin.de!uni-berlin.de!not-for-mail
From: Ian Kelly <ian.g.kelly@gmail.com>
Newsgroups: comp.lang.python
Subject: Re: how to convert code that uses cmp to python3
Date: Fri, 8 Apr 2016 08:17:17 -0600
Lines: 35
Message-ID: <mailman.85.1460125085.2253.python-list@python.org>
References: <57064D0D.1030701@rece.vub.ac.be> <mailman.21.1460030738.2253.python-list@python.org> <87r3egfqiv.fsf@elektro.pacujo.net> <570778ad$0$1587$c3e8da3$5496439d@news.astraweb.com> <CALwzidn7p8z7AE-HjZRuaZiFPQ1Je793_OHA5H7VYc8DVCu74A@mail.gmail.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8
In-Reply-To: <570778ad$0$1587$c3e8da3$5496439d@news.astraweb.com>
Precedence: list
Xref: csiph.com comp.lang.python:106682

On Fri, Apr 8, 2016 at 3:23 AM, Steven D'Aprano <steve@pearwood.info> wrote:
> On Fri, 8 Apr 2016 06:34 pm, Marko Rauhamaa wrote:
>
>> Antoon Pardon <antoon.pardon@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__?