[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm
From: |
md5i . mail |
Subject: |
Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050) |
Date: |
Thu, 10 Nov 2011 17:11:17 +0000 |
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.
http://codereview.appspot.com/5371050/
- Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050),
md5i . mail <=
- Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050), dak, 2011/11/10
- Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050), joeneeman, 2011/11/10
- Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050), pkx166h, 2011/11/10
- Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050), Carl . D . Sorensen, 2011/11/12
- Re: grob.cc: rewrite O(n^2) algorithm in Grob::common_refpoint algorithm to O(n) (issue 5371050), dak, 2011/11/12