grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n)

grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n)

[joeneeman, 2011-11-10 16:41:54]

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc
File lily/grob.cc (right):

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode536
lily/grob.cc:536: c = c->dim_cache_[a].parent_;
After this loop, balance will be 0, right? So the next loop won't do anything...

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode542
lily/grob.cc:542: while (c != d) {
{ on new line

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode542
lily/grob.cc:542: while (c != d) {
The old version would return 0 if there was no common refpoint (which is
possible if the grob hierarchy hasn't been fully built yet). I'd suggest a
"while (c && c != d)" to keep the old behavior.

[md5i, 2011-11-10 17:11:17]

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc
File lily/grob.cc (right):

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode536
lily/grob.cc:536: c = c->dim_cache_[a].parent_;
On 2011/11/10 16:41:54, joeneeman wrote:
> After this loop, balance will be 0, right? So the next loop won't do
anything...
It seems to me that this is true ... unless balance was negative before the
loop.  That's what the next loop is handling, I believe.

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode542
lily/grob.cc:542: while (c != d) {
On 2011/11/10 16:41:54, joeneeman wrote:
> The old version would return 0 if there was no common refpoint (which is
> possible if the grob hierarchy hasn't been fully built yet). I'd suggest a
> "while (c && c != d)" to keep the old behavior.
The balancing code above ensures that the d and c chains are the same length. 
Therefore if there is no common refpoint, the loop will exit when c and d are
both 0, which will maintain the old behavior.

[dak, 2011-11-10 17:26:34]

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc
File lily/grob.cc (right):

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode536
lily/grob.cc:536: c = c->dim_cache_[a].parent_;
On 2011/11/10 16:41:54, joeneeman wrote:
> After this loop, balance will be 0, right?

Only if it was't negative before.
> So the next loop won't do anything...

Depending on the sign of balance, either one or both loops will do nothing.  The
compiler is smart enough to know that after exiting the first loop body it will
not need to recheck the balance, so there is little point in uglifying the code.

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode542
lily/grob.cc:542: while (c != d) {
On 2011/11/10 16:41:54, joeneeman wrote:
> The old version would return 0 if there was no common refpoint (which is
> possible if the grob hierarchy hasn't been fully built yet). I'd suggest a
> "while (c && c != d)" to keep the old behavior.

I suggest we leave everything as it is.  If there is no common refpoint, both c
and d will become 0 at the same time, and the loop will exit without any extra
conditions.

The code passed the regtests first time through (after I changed <const_cast> to
a normal cast.  Surprised that g++ 4.6 does not know it).

I like it in this style and symmetry which captures the underlying idea pretty
nicely.

[joeneeman, 2011-11-10 19:10:35]

Ok, lgtm

[pkx166h, 2011-11-10 20:30:14]

Passes make and no reg test diffs

James

[Carl, 2011-11-12 17:06:15]

LGTM.

Thanks,

Carl

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc
File lily/grob.cc (right):

http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode542
lily/grob.cc:542: while (c != d) {
On 2011/11/10 16:41:54, joeneeman wrote:
> { on new line

This should be fixed by running fixcc.py, right?

[dak, 2011-11-12 17:11:47]

On 2011/11/12 17:06:15, Carl wrote:
> LGTM.
> 
> Thanks,
> 
> Carl
> 
> http://codereview.appspot.com/5371050/diff/1/lily/grob.cc
> File lily/grob.cc (right):
> 
> http://codereview.appspot.com/5371050/diff/1/lily/grob.cc#newcode542
> lily/grob.cc:542: while (c != d) {
> On 2011/11/10 16:41:54, joeneeman wrote:
> > { on new line
> 
> This should be fixed by running fixcc.py, right?

Oh.  I actually already fixed that in my version.  Just did not realize that I
had not uploaded it for review again.

And now I don't want to disturb the countdown...