Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.006 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'svn': 0.05; 'tree': 0.05; 'element': 0.07; 'python3': 0.07; 'tests.': 0.07; 'dan': 0.09; 'exception.': 0.09; 'inserted': 0.09; 'raises': 0.09; 'python': 0.11; 'attributes,': 0.16; 'compares': 0.16; 'finds': 0.16; 'none.': 0.16; 'restructured': 0.16; 'to:name:python list': 0.16; 'url:svn': 0.16; 'sat,': 0.16; 'wrote:': 0.18; 'code.': 0.18; 'discussion': 0.18; 'email addr:gmail.com>': 0.22; 'tests': 0.22; 'print': 0.22; 'versions': 0.24; "i've": 0.25; 'right.': 0.26; 'header:In-Reply-To:1': 0.27; 'moved': 0.30; 'message- id:@mail.gmail.com': 0.30; "i'm": 0.30; 'gives': 0.31; 'getting': 0.31; 'node': 0.31; 'subject:skip:i 10': 0.31; 'checked': 0.32; 'thanks!': 0.32; 'quite': 0.32; 'comment': 0.34; 'trouble': 0.34; 'at:': 0.34; 'could': 0.34; 'problem': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'version': 0.36; 'false': 0.36; 'module.': 0.36; 'method': 0.36; 'subject:?': 0.36; 'url:org': 0.36; 'should': 0.36; 'two': 0.37; 'being': 0.38; 'expected': 0.38; 'sometimes': 0.38; 'skip:& 10': 0.38; 'to:addr :python-list': 0.38; 'pm,': 0.38; 'to:addr:python.org': 0.39; 'changed': 0.39; 'either': 0.39; 'mentioned': 0.61; 'new': 0.61; 'entire': 0.61; 'provide': 0.64; 'more': 0.64; 'afraid': 0.65; 'grow': 0.77; 'yourself': 0.78; "it'd": 0.84; 'results,': 0.84; 'subject:Red': 0.84; 'items,': 0.91; '2013': 0.98 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:in-reply-to:references:date:message-id :subject:from:to:content-type; bh=oGau/JWmagwl0cDyCqVhv8FGfsiOJ8jHIzeTy52AMp8=; b=PSXOdTmagAe2PQAjw+l6fQIQaY/P6aNkraGk5ue1WhJoPSPSmcByuxdWFaHeAaKKeI SMg8XPnrqBMBZS/ZMMF/S0nerFrMl6A6apgDJ7pJjrrUS6mUuiEXwpHjpqiVZVZ2TgHX QozJLoyK/SXd92A8XAmEslk0sX4IyN3tV9uX2E+0uyIrDapRzBFDv8rXoW8ILZsnSL6b 1EjKelF4IkpWCWRi4n93/qgdVjwXbOxgSzI1Ha0MbqhBpZAmNsUL+WwSQhTM/aUnvYJ6 jmbkZ6vCfW1my9vpefpUAPXXr74ICIK0B/I0u3P/yI9I+sbC9HBPqLt/YMz6HM5KccWA bbTQ== MIME-Version: 1.0 X-Received: by 10.229.94.70 with SMTP id y6mr4341788qcm.46.1368322163879; Sat, 11 May 2013 18:29:23 -0700 (PDT) In-Reply-To: References: <5181ca0e$0$13974$862e30e2@ngroups.net> <518850f8$0$8157$862e30e2@ngroups.net> <518ade0f$1$60230$862e30e2@ngroups.net> <518baa27$0$7930$862e30e2@ngroups.net> Date: Sat, 11 May 2013 18:29:23 -0700 Subject: Re: Red Black Tree implementation? From: Dan Stromberg To: Python List Content-Type: multipart/alternative; boundary=14dae94ee3a3843a8504dc7b54f1 X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 103 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1368322168 news.xs4all.nl 15887 [2001:888:2000:d::a6]:35675 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:45167 --14dae94ee3a3843a8504dc7b54f1 Content-Type: text/plain; charset=ISO-8859-1 On Sat, May 11, 2013 at 4:24 PM, Dan Stromberg wrote: > > I'm afraid I'm having some trouble with the module. I've checked it into > my SVN at > http://stromberg.dnsalias.org/svn/red-black-tree-mod/trunk/duncan > > I have two versions of your tests in there now - "t" is minimally changed, > and test-red_black_tree_mod is pretty restructured to facilitate adding > more tests later. I get the same problem with either version of the tests. > > The problem I'm seeing is that the tree, when built from items, isn't > looking quite right. I inserted a print(tree) into the for loop, and I'm > getting the following, where I expected the tree to grow by one element on > each iteration: > > $ python t > 6 False None None > 6 False 3 None > 6 False 3 15 > 6 False 3 15 > I figured out that this was printing a single node and some of its attributes, not an entire tree. I changed it to print an entire tree using self.in_order(). I've also changed around the comparisons a bit, to use a __cmp__ method but still provide __eq__, __neq__ and a new __lt__. I'm up against a new problem now that it'd be nice if you could look at: In BinaryTree.find(), it sometimes compares the item being searched for against None. In 2.x, this gives strange results, but may be benign in this code. In 3.x, this raises an exception. I've added a comment about this in the SVN repo I mentioned above. You can see the traceback yourself with python3 test-red_black_tree_mod . What should BinaryTree.find() do if it finds a data.node that is None? Thanks! PS: Is it about time we moved this discussion off python-list? --14dae94ee3a3843a8504dc7b54f1 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

= On Sat, May 11, 2013 at 4:24 PM, Dan Stromberg <drsalists@gmail.com&= gt; wrote:

I'm afraid I'm having some trouble with the module.=A0 I've = checked it into my SVN at http://= stromberg.dnsalias.org/svn/red-black-tree-mod/trunk/duncan

I have two versions of your test= s in there now - "t" is minimally changed, and test-red_black_tre= e_mod is pretty restructured to facilitate adding more tests later.=A0 I ge= t the same problem with either version of the tests.

The problem I'm seeing is that th= e tree, when built from items, isn't looking quite right.=A0 I inserted= a print(tree) into the for loop, and I'm getting the following, where = I expected the tree to grow by one element on each iteration:

$ python t
6 False None None
6 False 3 None
6 False 3 15
6 = False 3 15
I figured out that thi= s was printing a single node and some of its attributes, not an entire tree= .=A0 I changed it to print an entire tree using self.in_order().

I've also changed around the comparisons a bit, to use a __cmp__ me= thod but still provide __eq__, __neq__ and a new __lt__.

= I'm up against a new problem now that it'd be nice if you could loo= k at:
In BinaryTree.find(), it sometimes compares the item being searc= hed for against None.=A0 In 2.x, this gives strange results, but may be ben= ign in this code.=A0 In 3.x, this raises an exception.=A0 I've added a = comment about this in the SVN repo I mentioned above.

You can see the traceback yourself with python3 test-red_bla= ck_tree_mod .

What should BinaryTree.find() do if it find= s a data.node that is None?
=A0
Thanks!

PS: Is it about time we moved this discussion off python-list?

--14dae94ee3a3843a8504dc7b54f1--