Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!eweka.nl!lightspeed.eweka.nl!194.134.4.91.MISMATCH!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!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.004 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'svn': 0.05; 'tree': 0.05; 'element': 0.07; 'tests.': 0.07; 'dan': 0.09; 'inserted': 0.09; 'skip:2 30': 0.09; 'python': 0.11; '6:52': 0.16; 'intended.': 0.16; 'md5': 0.16; 'restructured': 0.16; 'thoughts?': 0.16; 'to:name:python list': 0.16; 'url:svn': 0.16; '\xa0you': 0.16; 'wrote:': 0.18; 'thu,': 0.19; 'version.': 0.19; 'seems': 0.21; '8bit%:5': 0.22; 'saying': 0.22; 'tests': 0.22; 'versions': 0.24; "i've": 0.25; 'compare': 0.26; 'right.': 0.26; 'header:In-Reply- To:1': 0.27; 'correct': 0.29; 'am,': 0.29; 'message- id:@mail.gmail.com': 0.30; "i'm": 0.30; 'url:mailman': 0.30; 'getting': 0.31; 'subject:skip:i 10': 0.31; 'checked': 0.32; 'thanks!': 0.32; 'quite': 0.32; 'url:python': 0.33; 'trouble': 0.34; 'problem': 0.35; 'equal': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'version': 0.36; 'false': 0.36; 'module.': 0.36; 'url:listinfo': 0.36; 'subject:?': 0.36; 'url:org': 0.36; 'should': 0.36; 'two': 0.37; 'expected': 0.38; 'skip:& 10': 0.38; 'to:addr:python-list': 0.38; 'issue': 0.38; 'previous': 0.38; 'skip:& 20': 0.39; 'though,': 0.39; 'sure': 0.39; 'to:addr:python.org': 0.39; 'either': 0.39; 'url:mail': 0.40; 'more': 0.64; 'afraid': 0.65; 'latest': 0.67; 'smith': 0.68; 'grow': 0.77; '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=ZUfCpjHbrlHO9aD6JblCd+eV29DdlLHV6BSxN3MrJ8k=; b=rxwbuHgzUfmTuIYnr287YqhiF0ezdt+IUDivlvxNx+4MHyZ+mweGrZBz9cSXRtao+d R2xkkXoQ3MN9QSfFsjZ98drbTp0vBsyd7+TFZq6dj01uShjdlPTiYCQMAJ1zXF9xR7b3 M5RQ3WyyZEtISG93pIdqyHqEd7hiT+5kipyaQCm1bkAruYbx4x6pk89n6jbVebjGyAnt y0WyrNX2Czc5sTE003L95hVAM7YtRUq2nTLNBxB+dcTYv9SQJrhAYRU6L5r3+ms3xfKc ZVnL/Hp/+xcL0Y5L4iUj6FLgvjAWrno9jSqFiRmAeRzN6R0+qt7boU6S7Cn+0NbBh7h1 ECxQ== MIME-Version: 1.0 X-Received: by 10.224.34.198 with SMTP id m6mr16222098qad.39.1368314682963; Sat, 11 May 2013 16:24:42 -0700 (PDT) In-Reply-To: <518baa27$0$7930$862e30e2@ngroups.net> 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 16:24:42 -0700 Subject: Re: Red Black Tree implementation? From: Dan Stromberg To: Python List Content-Type: multipart/alternative; boundary=20cf3074b7b09e79a204dc79967f 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: 158 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1368314691 news.xs4all.nl 15883 [2001:888:2000:d::a6]:43501 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:45161 --20cf3074b7b09e79a204dc79967f Content-Type: text/plain; charset=ISO-8859-1 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 6 False 3 11 6 False 3 11 6 False 3 11 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 11 False 6 15 Thoughts? BTW, printing an empty tree seems to say "sentinel". 'not sure if that was intended. Thanks! On Thu, May 9, 2013 at 6:52 AM, duncan smith wrote: > On 09/05/13 02:40, Dan Stromberg wrote: > >> OK, I've got one copy of trees.py with md5 >> 211f80c0fe7fb9cb42feb9645b4b3f**fe. You seem to be saying I should have >> two though, but I don't know that I do... >> >> > [snip] > > Yes, 211f80c0fe7fb9cb42feb9645b4b3f**fe is the correct checksum for the > latest version. The previous version had an issue when adding non-distinct > items (items that compare equal to items already in the tree). Cheers. > > Duncan > > -- > http://mail.python.org/**mailman/listinfo/python-list > --20cf3074b7b09e79a204dc79967f Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

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

I have two versions of your tests in there now - "t" is minimal= ly changed, and test-red_black_tree_mod is pretty restructured to facilitat= e adding more tests later.=A0 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.=A0 I inserted a print(tree) into the for loop, and I&#= 39;m getting the following, where I expected the tree to grow by one elemen= t on each iteration:

$ python t
6 False None None
6 False 3 None
6 False 3 15
6 = False 3 15
6 False 3 11
6 False 3 11
6 False 3 11
11 False 6 15=
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 False 6 15
11 Fals= e 6 15
11 False 6 15
11 False 6 15
11 False 6 15

Thoughts?

BTW= , printing an empty tree seems to say "sentinel".=A0 'not sur= e if that was intended.

Th= anks!



On Thu, May 9, 2013 at 6:52 AM, duncan smith &l= t;buzzard@inva= lid.invalid> wrote:
On 09/05/13 02:40, Dan Str= omberg wrote:
OK, I've got one copy of trees.py with md5
211f80c0fe7fb9cb42feb9645b4b3ffe. =A0You seem to be saying I should = have
two though, but I don't know that I do...


[snip]

Yes, 211f80c0fe7fb9cb42feb9645b4b3ffe is the correct checksum for th= e latest version. The previous version had an issue when adding non-distinc= t items (items that compare equal to items already in the tree). Cheers.

Duncan

--
http://mail.python.org/mailman/listinfo/python-list

--20cf3074b7b09e79a204dc79967f--