Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #46996 > unrolled thread

Tutorial on threaded binary tree part 1: simple unthreaded tree

Back to article view | Back to comp.lang.c++

Contents

  Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-01 10:32 +0100
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-01 20:23 +0000
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-01 16:54 -0500
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 03:15 +0100
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree leigh.v.johnston@googlemail.com - 2016-12-02 05:45 -0800
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Öö Tiib <ootiib@hot.ee> - 2016-12-02 08:30 -0800
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 15:32 +0000
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 16:15 +0000
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 15:55 +0000
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 00:58 +0100
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Melzzzzz <mel@zzzzz.com> - 2016-12-03 01:51 +0100
              Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 03:04 +0100
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 01:54 +0000
              Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 02:07 +0000
                Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 03:11 +0100
                  Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 02:17 +0000
                    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Öö Tiib <ootiib@hot.ee> - 2016-12-03 01:31 -0800
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:39 -0500
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-01 21:34 +0000
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-01 22:23 +0000
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 00:32 +0100
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-01 23:57 +0000
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 01:14 +0100
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-02 22:06 +0000
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Daniel <danielaparker@gmail.com> - 2016-12-01 20:12 -0800
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 05:53 +0100
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:45 -0500
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Ian Collins <ian-news@hotmail.com> - 2016-12-03 11:48 +1300
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:49 -0500
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Ian Collins <ian-news@hotmail.com> - 2016-12-03 11:52 +1300
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-02 19:44 -0500
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-09 22:05 -0800

Page 2 of 2 — ← Prev page 1 [2]

#47006

On 01.12.2016 22:34, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> I believe you have said in previous threads that you like it for
> "consistency" (which you don't seem to apply consistently throughout
> even this small code sample), but the use of auto deduced return types
> for methods and functions here feels gratuitous.  It doesn't add any
> clarity but comes at the expense of more tokens I have to scan through
> in order to see what is happening.

There are no deduced return types in this code.

Mainly because I mostly agree with your sentiment here. :)


[snip]
> Slavishly using auto and trailing return types on functions/methods
> (and not even consistently throughout) just takes something simple
> and makes it more complicated without any benefit.

Re consistency, this code is totally consistent:

* `void` for Pascal /procedures/ (no expression result functions).
* `auto` for Pascal functions (functions that return value).

:)

But the 100% consistency here is just a coincidence, due to the 
shortness of the code. I do not believe 100% consistency is good! In the 
end, I believe, this boils down to the reason why programming can't be 
automated: we need humans to supply intelligence.

Dang, there was a good quote about consistency, I've forgotten it...


Cheers!,

- Alf

[toc] | [prev] | [next] | [standalone]

#47007

[Please do not mail me a copy of your followup]

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> spake the secret code
<o1qc1t$3nc$1@dont-email.me> thusly:

>On 01.12.2016 22:34, Richard wrote:
>> [...]  but the use of auto deduced return types
>> for methods and functions here feels gratuitous.

>There are no deduced return types in this code.

OK, consider that nit picked.  s/deduced/trailing/.

>Re consistency, this code is totally consistent:
>
>* `void` for Pascal /procedures/ (no expression result functions).
>* `auto` for Pascal functions (functions that return value).

Again, back to the point of the audience that is reading this code.
The fact that you had to explain your "consistency" is buttressing my
assertion that this style is leading to less clarity and not more.

When I read the code, I see some things using trailing return types
and some things not using trailing return types.

If using auto is good enough for trailing type int, why isn't it
good enough for trailing type void?

If using classic return type without auto is good enough for void,
why isn't it good enough for int?

Etc.

Again, this style just makes me think "someone is all excited about
the new syntax of trailing return types and is using it gratuitously"
instead of using it where it adds clarity as in type deduction of a
return type from an expression using types of input arguments.
-- 
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
            The Terminals Wiki <http://terminals-wiki.org>
     The Computer Graphics Museum <http://computergraphicsmuseum.org>
  Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[toc] | [prev] | [next] | [standalone]

#47008

On 02.12.2016 00:57, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> spake the secret code
> <o1qc1t$3nc$1@dont-email.me> thusly:
>
>> On 01.12.2016 22:34, Richard wrote:
>>> [...]  but the use of auto deduced return types
>>> for methods and functions here feels gratuitous.
>
>> There are no deduced return types in this code.
>
> OK, consider that nit picked.  s/deduced/trailing/.

There is world of difference.


>> Re consistency, this code is totally consistent:
>>
>> * `void` for Pascal /procedures/ (no expression result functions).
>> * `auto` for Pascal functions (functions that return value).
>
> Again, back to the point of the audience that is reading this code.
> The fact that you had to explain your "consistency" is buttressing my
> assertion that this style is leading to less clarity and not more.
>
> When I read the code, I see some things using trailing return types
> and some things not using trailing return types.
>
> If using auto is good enough for trailing type int, why isn't it
> good enough for trailing type void?

For the very common single case of `void` functions, `auto` just adds 
verbosity (for member function implementations it can drastically reduce 
verbosity, but for simple `void` functions it adds wordage).

Also, as I see it it's very nice to have this class of functions singled 
out visually, as with the Pascal keyword `procedure` (which had that 
exact purpose: to single them out). Because in the basic meaning the 
`void` functions have a very different purpose, namely to /do/ something 
rather than /compute/ something. Of course it's possible to use either 
class of function for the opposite purpose, with just more awkward 
notation, but that's the basis – and via the C++11 and later support for 
move semantics, C++ now increasingly supports the style where 
computations yield function results, used in /expressions/.

Most computer scientist, I believe, view that usage as the ideal, that a 
routine that computes something should return that as its function 
result, and therefore agree that the C conflation of procedure and 
function was a bad choice. In original C one would have to let those 
procedures return `int`, either explicitly or via C implicit int. It was 
ugly, the code saying something different than the intention.


> If using classic return type without auto is good enough for void,
> why isn't it good enough for int?

Singling out `void`, procedures, is doable and has a reason (which IMO 
is strong and good).

Not so for `int`.

But people have argued that `int main()` is so idiomatic that it just 
feels wrong and perplexing to see it expressed with `auto`. I do that 
for consistency. And also, to introduce the syntax to more people. :)

Cheers!,

- Alf

[toc] | [prev] | [next] | [standalone]

#47036

[Please do not mail me a copy of your followup]

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> spake the secret code
<o1qeg2$a8c$1@dont-email.me> thusly:

>[...] And also, to introduce the syntax to more people. :)

Yes.  Gratuitous use of new syntax.
-- 
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
            The Terminals Wiki <http://terminals-wiki.org>
     The Computer Graphics Museum <http://computergraphicsmuseum.org>
  Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[toc] | [prev] | [next] | [standalone]

#47010

On Thursday, December 1, 2016 at 6:35:48 PM UTC-5, Alf P. Steinbach wrote:
> 
> Dang, there was a good quote about consistency, I've forgotten it...
> 
One of these?

“A foolish consistency is the hobgoblin of little minds"

- Ralph Waldo Emerson

"Do I contradict myself? Very well, then I contradict myself, I am large, I contain multitudes."

- Walt Whitman

[toc] | [prev] | [next] | [standalone]

#47011

On 02.12.2016 05:12, Daniel wrote:
> On Thursday, December 1, 2016 at 6:35:48 PM UTC-5, Alf P. Steinbach wrote:
>>
>> Dang, there was a good quote about consistency, I've forgotten it...
>>
> One of these?
>
> “A foolish consistency is the hobgoblin of little minds"
>
> - Ralph Waldo Emerson
>
> "Do I contradict myself? Very well, then I contradict myself, I am large, I contain multitudes."
>
> - Walt Whitman


Yep. Thanks!

Cheers!,

- Alf

[toc] | [prev] | [next] | [standalone]

#47040

On 12/01/2016 04:34 PM, Richard wrote:
> It's why we write ++i instead of i = i + 1 and if (predicate) instead
> of if (predicate == true).  In both cases, the former is simpler and
> expresses the exact same semantics.

no, actually

[toc] | [prev] | [next] | [standalone]

#47041

On 12/ 3/16 11:45 AM, ruben safir wrote:
> On 12/01/2016 04:34 PM, Richard wrote:
>> It's why we write ++i instead of i = i + 1 and if (predicate) instead
>> of if (predicate == true).  In both cases, the former is simpler and
>> expresses the exact same semantics.
>
> no, actually

How so?

-- 
Ian

[toc] | [prev] | [next] | [standalone]

#47042

On 12/02/2016 05:48 PM, Ian Collins wrote:
>> no, actually
> 
> How so?


it is undefined on the order of evaluation

[toc] | [prev] | [next] | [standalone]

#47043

On 12/ 3/16 11:49 AM, ruben safir wrote:
> On 12/02/2016 05:48 PM, Ian Collins wrote:
>>> no, actually
>>
>> How so?
>
>
> it is undefined on the order of evaluation

What is?

-- 
Ian

[toc] | [prev] | [next] | [standalone]

#47050

On 12/2/2016 5:49 PM, ruben safir wrote:
> On 12/02/2016 05:48 PM, Ian Collins wrote:
>>> no, actually
>>
>> How so?
> 
> 
> it is undefined on the order of evaluation
> 

It is perfectly defined.  The addition is performed before the
assignment.  The variable is only changed once - in the assignment.
There is no undefined operation.

Now there is undefined behavior in the expression i = i++ + 1.  But that
is a different situation.

-- 
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================

[toc] | [prev] | [next] | [standalone]

#47249

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> writes:

> This tutorial, if it works (it's an experiment), is intended to work
> this way:
>
> * I post some working code.
> * Learner(s) study it and ask about things.
> * Others answer questions and post critique or get bogged down in long
> sub-threads about sausages and swearing.
>
> The following code implements a simple sorted binary tree with traversal.
>
> There's no attempt at balancing, so this code does not deal nicely
> with sorted input in the big O sense.  Random input is the thing
> here.  I used the digits of pi.

I'm wondering if/when you might show a version with threaded
trees and/or balancing.

The iterative algorithm for AVL trees is somewhat tricky.
Combining that with threaded leaves is trickier still.  I was
able to do a recursive AVL-like insertion fairly easily (with
nodes having an explicit height field) but a more traditional
iterative algorithm proved to be more difficult.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c++

csiph-web