Thursday, December 1, 2016

Digest for comp.lang.c++@googlegroups.com - 24 updates in 6 topics

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 01 10:32AM +0100

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.
 
 
[code]
namespace cppx {
struct No_copy_or_move
{
auto operator=( No_copy_or_move const& ) -> No_copy_or_move& =
delete;
auto operator=( No_copy_or_move&& ) -> No_copy_or_move& = delete;
 
No_copy_or_move() = default;
No_copy_or_move( No_copy_or_move const& ) = delete;
No_copy_or_move( No_copy_or_move&& ) = delete;
};
} // namespace cppx
 
namespace my {
 
using Value = double;
 
class Tree
: public cppx::No_copy_or_move
{
private:
struct Node
{
Node* left;
Node* right;
Value value;
};
 
Node* root_ = nullptr;
 
template< class Func >
static void apply_in_infix_order( Node* root, Func const& f )
{
if( root != nullptr )
{
apply_in_infix_order( root->left, f );
f( root->value );
apply_in_infix_order( root->right, f );
}
}
 
public:
void add( Value const& value )
{
Node** p_ptr = &root_;
while( *p_ptr != nullptr )
{
Node*& ref_ptr = *p_ptr;
p_ptr = &(value < ref_ptr->value? ref_ptr->left :
ref_ptr->right);
}
*p_ptr = new Node{ nullptr, nullptr, value };
}
 
template< class Func >
void for_each( Func const& f )
{
apply_in_infix_order( root_, f );
}
 
Tree() = default;
};
} // my
 
#include <iostream>
using namespace std;
auto main()
-> int
{
my::Tree t;
for( int const v : {3, 1, 4, 1, 5, 9, 2, 6, 5, 4} )
{
t.add( v );
}
t.for_each(
[]( double x ) { cout << x << ' '; }
);
cout << endl;
}
}
[/code]
 
 
Enjoy,
 
- Alf
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 01 08:23PM

On 01/12/2016 09:32, Alf P. Steinbach wrote:
> }
> }
> [/code]
 
Without balancing your tree is as good as useless; your post was totally
pointless.
 
/Flibble
legalize+jeeves@mail.xmission.com (Richard): Dec 01 09:34PM

[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.
 
"Everything should be made as simple as possible, but no simpler."
(Attributed to Einstein, <https://en.wikiquote.org/wiki/Albert_Einstein#1920s>)
 
To my mind, that means writing things in the simplest form with as
few tokens as possible.
 
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.
 
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.
 
Yes, it's a matter of style and not correctness, so your opinion may
differ -- I assume it does as you wrote it that way. Consider that when
we write code, we should think of the next person that is reading it
and not use code as an attempt to inculcate the rest of the world into
using our personal preferences.
 
Given that matters of style are personal taste, barring other
operational or security considerations, my tendency is to borrow the
style of Kernighan and Ritchie when writing code in C/C++. There are
many stylistic fads and opinions which differ from their style and I
uniformly have found them all to be of no benefit, or at best they
solve a problem in the wrong way. Your code exhibits one or two of
these tendencies but I don't consider them to be worth elevating to a
point of discussion as much as the gratuitous use of auto deduced
return types.
--
"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>
Jerry Stuckle <jstucklex@attglobal.net>: Dec 01 04:54PM -0500

On 12/1/2016 3:23 PM, Mr Flibble wrote:
 
> Without balancing your tree is as good as useless; your post was totally
> pointless.
 
> /Flibble
 
No, it's not. This is a start and builds the tree correctly. Balancing
can come later. It's just a matter of adding about 4 functions and call
them from the appropriate places. The existing code will still work.
 
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 01 10:23PM

On 01/12/2016 21:34, Richard wrote:
> these tendencies but I don't consider them to be worth elevating to a
> point of discussion as much as the gratuitous use of auto deduced
> return types.
 
+1
 
(Alf will now go off in a strop and write a Hello, World! program so he
can write "auto main() -> int" again like some crazy OCD cat person.)
 
/Flibble
xerofoify <xerofoify@gmail.com>: Nov 30 06:12PM -0800

On Wednesday, November 30, 2016 at 4:48:08 PM UTC-5, Alf P. Steinbach wrote:
 
> Can you explain what you mean by "threaded tree"?
 
> Cheers!,
 
> - Alf
 
I meant number one. Huge thanks seems I can't figure out how to implement the threads and was unable to find an example of a threaded binary tree not a regular one.
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 01 03:29AM +0100

On 01.12.2016 03:12, xerofoify wrote:
 
> I meant number one. Huge thanks seems I can't figure out how to
> implement the threads and was unable to find an example of a threaded
> binary tree not a regular one.
 
As I recall Niklaus Wirth described this in detail in his now classic
"Algorithm + Data Structures = Programs" book. I may be wrong, maybe he
was just describing balancing, but the book is worth reading anyway. :)
The Oberon (programming language) version, as opposed to the original
Pascal version, is available as a legal free PDF download, somewhere.
 
Anyway, the extra pointer(s) you need depend on the order you want to
visit the nodes in.
 
For an ordinary in-order traversal (left sub-tree, then root, then right
sub-tree) an upward parent pointer in each node suffices, in addition to
the downward left and right pointers. It works because in an in-order
traversal, when you're about to process the data in a node X, you have
already processed the left sub-tree. It's a little tricky, but drawing a
figure and doing this by hand should pave the way. :)
 
I suggest you start by making a non-threaded binary tree and simply use
"fat" iterators, iterators that remember the path down the tree,
essentially the stack of nodes that one needs back up through to go
logically forward. `std::stack` comes to mind as useful for that.
 
I am not entirely /sure/ but I think that approach will give you
insights that will ease the implementation of threaded tree.
 
 
Cheers & hth.,
 
_ Alf
xerofoify <xerofoify@gmail.com>: Nov 30 06:58PM -0800

On Wednesday, November 30, 2016 at 9:32:29 PM UTC-5, Alf P. Steinbach wrote:
> insights that will ease the implementation of threaded tree.
 
> Cheers & hth.,
 
> _ Alf
 
That book is talking about balancing trees. I was wondering if there were any examples of threading somewhere online as I have yet to find any.
Jerry Stuckle <jstucklex@attglobal.net>: Dec 01 12:03AM -0500

On 11/30/2016 9:12 PM, xerofoify wrote:
 
>> Cheers!,
 
>> - Alf
 
> I meant number one. Huge thanks seems I can't figure out how to implement the threads and was unable to find an example of a threaded binary tree not a regular one.
 
Besides the left and right pointers, the only other pointer you need is
one to the parent node. All the rest is done in the iterator.
 
It takes a bit more work to maintain the parent pointer, but not that
much. Get the rest of your binary tree working first, then add the
parent pointer. Finally you can write an iterator class for it.
 
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================
"Öö Tiib" <ootiib@hot.ee>: Nov 30 11:51PM -0800

On Wednesday, 30 November 2016 23:19:47 UTC+2, xerofoify wrote:
> > };
 
> Look I have tried that too. My exact question was and I have no idea how to even after drawing it out write this code. Also there are no docs on this online or elsewhere to my knowledge. The more you just tell me my code doesn't work does not help, I am looking for either proper documentation on how to do this or an example that actually works not a this doesn't work and draw it out
> answer.
 
Then tell that you need explanation and tutorial. Here is link to tutorial
how to program it:
http://algorithms.tutorialhorizon.com/double-threaded-binary-tree-complete-implementation/
Unfortunately it is written in Java there, but the idea in C++ is same.
In C++ we just have to manage lifetime of discarded nodes and that part
is not needed in Java that has garbage collection.
"Öö Tiib" <ootiib@hot.ee>: Dec 01 01:56AM -0800

On Thursday, 1 December 2016 07:03:43 UTC+2, Jerry Stuckle wrote:
 
> It takes a bit more work to maintain the parent pointer, but not that
> much. Get the rest of your binary tree working first, then add the
> parent pointer. Finally you can write an iterator class for it.
 
Yes, actually that is the most straightforward binary tree that you
describe where nodes have parent_, left_ and right_ pointers.
I think such binary tree is among best performant.
 
However there is "threaded binary tree" that does not use parent_
pointers but instead reuses the left_ and right_ pointers of leafs for
additional back traversal. It is rare tree design so I am not sure in what
situations it is better. OP asked about that tree.
Gareth Owen <gwowen@gmail.com>: Dec 01 04:47PM


> Then tell that you need explanation and tutorial. Here is link to
> tutorial how to program it:
 
You quoted 400 lines of code to say that?
Stuart Redmann <DerTopper@web.de>: Dec 01 06:21PM +0100


>> Then tell that you need explanation and tutorial. Here is link to
>> tutorial how to program it:
 
> You quoted 400 lines of code to say that?
 
+1 (SCNR, Leigh)
 
I'm reading this on a cell phone, so it's a PITA to scroll through pages of
unnecessary quoted text. In general, I would not bother, but a posting from
you, Öö Tiib, is usually worth reading.
 
Regards,
Stuart
legalize+jeeves@mail.xmission.com (Richard): Dec 01 05:25PM

[Please do not mail me a copy of your followup]
 
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> spake the secret code
>> class ThreadedTree{
 
>Well I'd like to help but that's just a wall of code to me. Unless I
>spend (too much) time delving into it. Which I'm not going to do.
 
Yeah, basically this whole thread has been "here's a big pile of
code. Will someone debug it for me?"
 
When I asked the OP if they had written unit tests to probe all the
control paths of their implementation, they said yes they did that,
but I've never seen any indication that any unit tests were written.
--
"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>
Jerry Stuckle <jstucklex@attglobal.net>: Dec 01 01:37PM -0500

On 12/1/2016 4:56 AM, Öö Tiib wrote:
> pointers but instead reuses the left_ and right_ pointers of leafs for
> additional back traversal. It is rare tree design so I am not sure in what
> situations it is better. OP asked about that tree.
 
A threaded binary tree does not preclude the use of parent pointers. It
just means the tree can be transversed in both directions. If you do
not have a parent pointer, this is normally done through recursion.
It's a bit easier to code (if you understand recursion, anyway) because
you don't need to maintain the parent pointers.
 
But it's tougher if you are just passed a node and need to find its
parent. That typically means starting from the base of the tree and
going down until you find your node, then working your way back up.
Parent pointers solve this problem.
 
So, advantages and disadvantages to both ways.
 
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================
"Christopher J. Pisz" <cpisz@austin.rr.com>: Nov 30 07:30PM -0600

What happened to it?
The last post I see in my reader is dated 5/22/2016 and there doesn't
seem to be more to download, is it just me?
"Christopher J. Pisz" <cpisz@austin.rr.com>: Nov 30 07:31PM -0600

On 11/30/2016 7:30 PM, Christopher J. Pisz wrote:
> What happened to it?
> The last post I see in my reader is dated 5/22/2016 and there doesn't
> seem to be more to download, is it just me?
 
mode*r*ated
Same question applies
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Dec 01 03:13AM +0100

On 01.12.2016 02:31, Christopher J. Pisz wrote:
>> seem to be more to download, is it just me?
 
> mode*r*ated
> Same question applies
 
The moderation system stopped working. It was based on free hosting. If
you search this group you may find the posting where Victor Bazarov, the
last mod to hold the fort, explained this.
 
 
Cheers & hth.,
 
- Alf (for the clc++m mods)
woodbrian77@gmail.com: Nov 30 06:28PM -0800

On Wednesday, November 30, 2016 at 8:17:01 PM UTC-6, Alf P. Steinbach wrote:
 
> The moderation system stopped working. It was based on free hosting. If
> you search this group you may find the posting where Victor Bazarov, the
> last mod to hold the fort, explained this.
 
This is a related thread
https://groups.google.com/forum/#!topic/comp.lang.c++/HKwMUav0gco
 
 
Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net
woodbrian77@gmail.com: Nov 30 06:44PM -0800

> > last mod to hold the fort, explained this.
 
> This is a related thread
> https://groups.google.com/forum/#!topic/comp.lang.c++/HKwMUav0gco
 
I'm part of the royal priesthood mentioned in that thread.
 

Brian
Ebenezer Enterprises - "But you are a chosen people, a royal priesthood,
a holy nation, G-d's special possession, that you may declare the
praises of Him who called you out of darkness into His wonderful light."
First Peter 2:9
 
http://webEbenezer.net
Ramine <ramine@1.1>: Nov 30 08:01PM -0500

Hello........
 
Here is the problems with Functional programming and the functional
language Haskel
 
Parallel programming is still prone to Deadlocks with Mvars in
Haskel.
 
Parallel programming with Haskel is still prone to Starvation.
 
Please read the book Real World Haskel from O'Rreilly to understand this.
 
And Functional programming has a problem on the criterion of readability:
 
Functional programming: A step backward
 
Read here:
 
http://www.javaworld.com/article/2078610/java-concurrency/functional-programming--a-step-backward.html
 
 
Thank you,
Amine Moulay Ramdane.
bleachbot <bleachbot@httrack.com>: Dec 01 01:39AM +0100

bleachbot <bleachbot@httrack.com>: Dec 01 02:00AM +0100

Ramine <ramine@1.1>: Nov 30 07:39PM -0500

Hello.......
 
Functional programming: A step backward
 
Read here:
 
http://www.javaworld.com/article/2078610/java-concurrency/functional-programming--a-step-backward.html
 
 
Thank you,
Amine Moulay Ramdane.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)