LEFT | RIGHT |
1 /* | 1 /* |
2 This file is part of LilyPond, the GNU music typesetter. | 2 This file is part of LilyPond, the GNU music typesetter. |
3 | 3 |
4 Copyright (C) 1997--2011 Han-Wen Nienhuys <hanwen@xs4all.nl> | 4 Copyright (C) 1997--2011 Han-Wen Nienhuys <hanwen@xs4all.nl> |
5 | 5 |
6 LilyPond is free software: you can redistribute it and/or modify | 6 LilyPond is free software: you can redistribute it and/or modify |
7 it under the terms of the GNU General Public License as published by | 7 it under the terms of the GNU General Public License as published by |
8 the Free Software Foundation, either version 3 of the License, or | 8 the Free Software Foundation, either version 3 of the License, or |
9 (at your option) any later version. | 9 (at your option) any later version. |
10 | 10 |
(...skipping 495 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
506 } | 506 } |
507 | 507 |
508 /**************************************************************** | 508 /**************************************************************** |
509 REFPOINTS | 509 REFPOINTS |
510 ****************************************************************/ | 510 ****************************************************************/ |
511 | 511 |
512 /* Find the group-element which has both #this# and #s# */ | 512 /* Find the group-element which has both #this# and #s# */ |
513 Grob * | 513 Grob * |
514 Grob::common_refpoint (Grob const *s, Axis a) const | 514 Grob::common_refpoint (Grob const *s, Axis a) const |
515 { | 515 { |
516 /* I don't like the quadratic aspect of this code, but I see no | 516 |
517 other way. The largest chain of parents might be 10 high or so, | 517 /* Catching the trivial cases is likely costlier than just running |
518 so it shouldn't be a real issue. */ | 518 through: one can't avoid going to the respective chain ends |
519 for (Grob const *c = this; c; c = c->dim_cache_[a].parent_) | 519 anyway. We might save the second run through when the chain ends |
520 for (Grob const *d = s; d; d = d->dim_cache_[a].parent_) | 520 differ, but keeping track of the ends makes the loop more costly. |
521 if (d == c) | 521 */ |
522 return (Grob *) d; | 522 |
523 | 523 int balance = 0; |
524 return 0; | 524 Grob const *c; |
| 525 Grob const *d; |
| 526 |
| 527 for (c = this; c; ++balance) |
| 528 c = c->dim_cache_[a].parent_; |
| 529 |
| 530 for (d = s; d; --balance) |
| 531 d = d->dim_cache_[a].parent_; |
| 532 |
| 533 /* Cut down ancestry to same size */ |
| 534 |
| 535 for (c = this; balance > 0; --balance) |
| 536 c = c->dim_cache_[a].parent_; |
| 537 |
| 538 for (d = s; balance < 0; ++balance) |
| 539 d = d->dim_cache_[a].parent_; |
| 540 |
| 541 /* Now find point where our lineages converge */ |
| 542 while (c != d) |
| 543 { |
| 544 c = c->dim_cache_[a].parent_; |
| 545 d = d->dim_cache_[a].parent_; |
| 546 } |
| 547 |
| 548 return (Grob *) c; |
525 } | 549 } |
526 | 550 |
527 void | 551 void |
528 Grob::set_parent (Grob *g, Axis a) | 552 Grob::set_parent (Grob *g, Axis a) |
529 { | 553 { |
530 dim_cache_[a].parent_ = g; | 554 dim_cache_[a].parent_ = g; |
531 } | 555 } |
532 | 556 |
533 Grob * | 557 Grob * |
534 Grob::get_parent (Axis a) const | 558 Grob::get_parent (Axis a) const |
(...skipping 344 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
879 if (Align_interface::has_interface (commony)) | 903 if (Align_interface::has_interface (commony)) |
880 return true; | 904 return true; |
881 | 905 |
882 for (Grob *g = this; g && g != commony; g = g->get_parent (Y_AXIS)) | 906 for (Grob *g = this; g && g != commony; g = g->get_parent (Y_AXIS)) |
883 if (Align_interface::has_interface (g)) | 907 if (Align_interface::has_interface (g)) |
884 return true; | 908 return true; |
885 | 909 |
886 return false; | 910 return false; |
887 } | 911 } |
888 | 912 |
LEFT | RIGHT |