views:

538

answers:

8

Guys, I have the following code that is inside a big while loop that iterates over a tree. This is as fast as I can get this routine but I have to use a goto. I am not fundamentally against goto but if I can avoid them I would like to. (I am not trying to start a flame war, please.)

The constraints:

  1. The current=current->child() is expensive (it's a shared_ptr) so I'd like to minimize the use of that operation at all cost.
  2. After the operation current should be the last child it found.
  3. cnt must count each child it encounters.
  4. cnt++ will be replaced by some other operation (or several operations) and should only appear once :)

the code:

insideloopy:
cnt++;
if ( current->hasChild() )
{
    current = current->child();
    goto insideloopy;
}

Edit: Sorry guys, originally forgot to mention cnt++ should only appear once. It will be some kind of operation on the node, and should thus only be there one time. I'm also trying to avoid making that another function call.

+18  A: 
cnt++;
while(current->hasChild())
{
   cnt++;
   current = current->child();
}

EDIT:

If you only want cnt++ to be in your code once:

while(true)
{
    cnt++;
    if(current->hasChild())
       current = current->child();
    else
       break;
}
LorenVS
cnt++ should only appear once.
Stefano Borini
you can avoid if statement by using do while loop, instead.
Artem Barger
i'm trying to avoid the extra if,.. keep it fast :)
Ron
Its true, this seems more natural to me, but who knows, I might have a really strange coding style :)
LorenVS
I personally try to avoid `while (true)` if at all possible.
Thorarin
Very close to the solution that I ended up accepting. Not sure who was first though, tried to upvote your comment though.
Ron
> I personally try to avoid while (true) if at all possibleThat's funny,.. maybe we could you a goto!!
Ron
@Thorarin. they are not necessary evil, provided they finish, and they are kept small.
Stefano Borini
@Stefano: I agree, and I don't get out of my way to avoid them. Often they are the best solution, especially in C# which I usually work in. However, with the comma operator available, it is easily avoided in this particular case.
Thorarin
+24  A: 

Original answer

Assuming this is C or C++:

while (cnt++, current->hasChild())
{
    current = current->child();
}

I'm not a big fan of the comma operator usually, but I don't like repeating myself either :)

Updated 'fun' answer

After learning that cnt++ is actually some multiline operation, this particular syntax would be less than ideal. Something more along the lines of your accepted answer would be better.

If you want to be really funky, this would also work:

do 
{
    cnt++;
} while (current->hasChild() && (current = current->child()));

Now I feel really dirty though, with my abusing the short circuiting on the && operator :)

Sane answer

Exercises in compactness aside and striving for readable code, I'm forced to conclude that one of the existing answers is best suited (I'm just including this for completeness' sake):

while (true)
{
   cnt++;
   if (!current->hasChild()) break;
   current = current->child();
}

The while (true) will be optimized by the compiler into a regular infinite loop, so there is only one conditional statement (if you care about that).

The only thing going against this solution is if your node operation was a long piece of code. I don't mind infinite loops so much, as long as I can see where they terminate at a glance. Then again, if it were really long, it should be a function anyway.

Thorarin
Works in C as well, I think.
Dave Hinton
In this case, works very well, and you can pack everything on a single line.
Stefano Borini
that is very compact indeed! :) and would work for the example but the cnt++ will be multiple operation in the actually application. Not sure what that will look like.Not a big fan of the comma operator either.
Ron
@Ron: with multiple statements, your accepted answer is probably the best solution. Too bad you didn't put that in your original question :P@Stefano: I'd split it over 2 lines I think. Some code style nazis don't like omitting braces though :(
Thorarin
Sorry about that. This was my first question here and I never expected it to be such a race to get the first answer!
Ron
There's always a run on these. Nice compact question, short answer. Easy points :)
Thorarin
I'm sure I'll come up with another one :)
Ron
Upvote for justice :p
WebDevHobo
A: 

while (current->hasChild()) { cnt++; current = current->child(); }

Or am I missing something?

Achim
that misses the first child.
Ron
+11  A: 
insideloopy:
cnt++;
if ( current->hasChild() )
{
    current = current->child();
    goto insideloopy;
}

I love infinite loops.

while (true) {
   cnt++;
   if (!current->hasChild()) break;
   current = current->child();
}

Of course you can do it in many other ways (see other answers). do while, put the check in the while, etc. In my solution, I wanted to map nearly to what you are doing (an infinite goto, unless break)

Stefano Borini
Fantastic! Good work. I just couldn't get my brain in action this morning.
Ron
This one is a little better than LorenVS' infinite loop version, because of the inverted logic. I still think my comma operator use is warranted and more readable though :P
Thorarin
@unknown: didn't you said, that you trying to avoid extra if?
Artem Barger
doesn't the while(true) pretty much become an unconditional jump?
Ron
I too prefer the reversed if logic here - but I feel LorenVS 6 minute earlier version was robbed of the accepted answer rep. ;) He'll have to settle for my measly +1.
Aardvark
Sorry LorenVS, I am not sure who was first as you ended up editing your answer (after I clarified the requirements). What does the 'answered time' reflect,.. first post or last edit?
Ron
imho, the break is just a hidden goto.
xtofl
+3  A: 

You can use break to get out of the loop in the middle of the code:

while (true) {
   cnt++;
   if (!current->hasChild()) break;
   current = current->child();
}
Guffa
yep! That's it.
Ron
no need to break; that's just a hidden goto, imho.
xtofl
@xtofl: Yes, but one that has a well-defined and easy to find target. That makes a lot of difference.
sbi
A: 
for(cnt++ ; current->hasChild() ; cnt++) {
   current = current->child();
}
nos
except for the fact that cnt++ is probably going to be multiple statements...
xtofl
So? The comma operator could be used here if the cnt++ has to expand to multiple statements. Not that it would be a good idea...
if cnt++ is multiple statements, it should perhaps be a function rather. And you can easily do for(cnt++,i = 0,current=firstChild(); ...; ...) if you need to.
nos
A: 

I'd investigate the possibility of making current->child() return NULL when it has no child if it doesn't already -- that seems the best possible result and leaving it undefined in this case seems error prone -- and then use:

for (; current; current = current->child())
{
    cnt++;
}
AProgrammer
The current->child() call is expensive compared to the hasChild() call. hence I want to avoid it if possible.
Ron
Is current->child() expensive even if hasChild() return false? If so, I'd simply wrap it with an hasChild() precondition.
AProgrammer
That would violate the second constraint however: *After the operation current should be the last child it found.*
Thorarin
A: 

No break statements:

notDone=true;
while(notDone){
   cnt++;
   if ( current->hasChild() ){
       current = current->child();
   } else {
       notDone=false;
   }
}
Greg Miller
Avoiding break is overrated, imo. Are you going to be proving correctness for this algorithm? Will break make it that much harder?
Thorarin
Break won't make it harder - it will introduce two possible code paths to the first statement after the loop, which requires analysis of both prior states. But the code above has two possible code paths to the loop-end where the condition is re-checked ("if" clause and "else" clause), which requires analysis of both prior states. "else" is just goto in disguise ;-)
Steve Jessop