Jump to content
  • Advertisement
Sign in to follow this  
Josheir

Need help understanding line in code snippet for linked list queue please.

This topic is 904 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Here is an attached .pdf snippet of programming from the out of print  C++ Programmer's Notebook (publisher is PRENTICE HALL) : Using a Linked List Queue.

 

I am trying to understand the line:

 

if ( ++count > n/2-1) break;

 

how it works with regards to n. The variable n is incremented in the first do...while loop. If n is found to be odd then there is truncation.

 

( Most readable with Adobe Reader or other Adobe software. )

 

Thank you,

 

Josheir

Share this post


Link to post
Share on other sites
Advertisement

That code appears to be formatted for fitting in limited vertical space for printing - that is it's deliberately making the code less readable to make it fit on one page. It's also using three xors to swap two variables, instead of using std::swap(), which is much more readable (and probably faster too).

 

The line of code in question would be easier to read if it was split up into two or three separate statements:

++count;
int operandCount = (n/2) - 1;
if ( count > operandCount )
  break;

I think the reasoning behind the test is that when there's only binary operators available, there will always be a known ratio of operators to operands, and that is testing for it. It's not a very nice way to detect the end of the expression though.

 

That is:

- With an input of length 3, you must have one operator and two operands.

- Input of length 4 is invalid.

- Input of length 5 will always have two operators.

- etc.

Share this post


Link to post
Share on other sites

It's also using three xors to swap two variables, instead of using std::swap(), which is much more readable (and probably faster too).


(for pointers and integer types, the performance of three xors would be the same as std::swap on most processors. the three xors method avoids a temporary and may perform marginally better in some cases)

 

 


I am trying to understand the line:

if ( ++count > n/2-1) break;

how it works with regards to n. The variable n is incremented in the first do...while loop. If n is found to be odd then there is truncation.

n is the number of expressions entered.
count is the number of times expressions have been "merged" with parenthesis
since this code only appears to group two expressions and one operator per set of parenthesis, and because at least one expression must be an operator, it can have at most ((n / 2) - 1) groupings.

I must say, this is an awkward piece of code, it assumes all operations are associative, and it took me a minute to just understand what it was supposed to be doing, it took me a few more minutes to understand why it was breaking the loop that way. This was in a textbook??? If I encountered a piece of code as awkwardly written as this in a project I was working on, I would probably leave that project.

Edited by nfries88

Share this post


Link to post
Share on other sites

Thanks for the amazing trivia, frob. I didn't know that the x86 microcode was so sophisticated. If there's one take-away from this, it should be that programmers are wiser to name such oft-used utilities. It makes for easier mental parsing and future maintenance. I'm pretty sure a SWAP macro would have been possible when that text book was written.

 

Other examples that I sometimes find unnecessarily complicated :

-"shift left when multiplying by two." if one doesn't trust the compiler to make this one optimization then just write a template mult() or even just mult2() function.

 

- recursion of incomplete concepts such as factorial. Even mathematicians use "if" and "where"

Edited by m3mb3rsh1p

Share this post


Link to post
Share on other sites

Well, that helps!  It's not a complete working program.  The book was published in 2002.  I found it informative for the most part.  The author's idea was to be succint with code that is explained with arrows and text and also has descripion on the left.  I just coudn't understand this one program.

 

It is an educational text book, the publisher is Pearson Education.  It is however out of print.

 

The program in question wasn't all inclusive so to speak.  I do find it interesting too.

 

Thank you everyone,

 

Josheir

Edited by Josheir

Share this post


Link to post
Share on other sites

I actually didn't know that Frob. This is one of the things I was told to do when I first started programming, which based on the timeframe you've given was already at least a decade after it was useful.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!