1 /* This file is part of the KDE project
2  * Copyright (C) 2007 Marijn Kruisselbrink <mkruisselbrink@kde.org>
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Library General Public
6  * License as published by the Free Software Foundation; either
7  * version 2 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * Library General Public License for more details.
13  *
14  * You should have received a copy of the GNU Library General Public License
15  * along with this library; see the file COPYING.LIB.  If not, write to
16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  * Boston, MA 02110-1301, USA.
18  */
19 #include "Engraver.h"
20 #include "core/Bar.h"
21 #include "core/Sheet.h"
22 #include "core/Voice.h"
23 #include "core/Part.h"
24 #include "core/VoiceBar.h"
25 #include "core/VoiceElement.h"
26 #include "core/Clef.h"
27 #include "core/Staff.h"
28 #include "core/StaffSystem.h"
29 #include "core/KeySignature.h"
30 #include "core/TimeSignature.h"
31 #include "core/Chord.h"
32 #include "core/Note.h"
33 
34 #include <limits.h>
35 #include <math.h>
36 
37 #include <QList>
38 #include <QVector>
39 #include <QVarLengthArray>
40 #include <QMultiMap>
41 
42 #ifndef log2
43 # define log2(x) (log(x) / M_LN2)
44 #endif
45 
46 using namespace MusicCore;
47 
Engraver()48 Engraver::Engraver()
49 {
50 }
51 
engraveSheet(Sheet * sheet,int firstSystem,QSizeF size,bool doEngraveBars,int * lastSystem)52 void Engraver::engraveSheet(Sheet* sheet, int firstSystem, QSizeF size, bool doEngraveBars, int* lastSystem)
53 {
54     *lastSystem = -1;
55     int firstBar = 0;
56     if (firstSystem != 0) {
57         firstBar = sheet->staffSystem(firstSystem)->firstBar();
58     }
59 
60     //debugMusic << "Engraving from firstSystem:" << firstSystem << "firstBar:" << firstBar;
61 
62     if (doEngraveBars || true) {
63         // engrave all bars in the sheet
64         for (int i = firstBar; i < sheet->barCount(); i++) {
65             engraveBar(sheet->bar(i));
66         }
67     }
68 
69     // now layout bars in staff systems
70     int curSystem = firstSystem;
71     qreal deltay = sheet->staffSystem(firstSystem)->top() - sheet->staffSystem(0)->top();
72     QPointF p(0, sheet->staffSystem(curSystem)->top() - deltay);
73     int lastStart = firstBar;
74     qreal lineWidth = size.width();
75     qreal indent = sheet->staffSystem(curSystem)->indent();
76     lineWidth -= indent;
77     if (firstBar > 0) {
78         p.setX(indent - sheet->bar(firstBar-1)->prefix());
79     }
80     bool prevPrefixPlaced = firstBar != 0;
81     for (int i = firstBar; i < sheet->barCount(); i++) {
82         Bar* bar = sheet->bar(i);
83         bool prefixPlaced = false;
84         if (i > 0 && p.x() + bar->naturalSize() + bar->prefix() - indent > lineWidth) {
85             // scale all sizes
86             // first calculate the total scalable width and total fixed width of all preceding bars
87             qreal scalable = 0, fixed = 0;
88             for (int j = lastStart; j < i; j++) {
89                 scalable += sheet->bar(j)->size();
90                 fixed += sheet->bar(j)->prefix();
91             }
92             fixed += bar->prefix();
93             if (prevPrefixPlaced) {
94                 fixed -= sheet->bar(lastStart)->prefix();
95             }
96 
97             // if line is too width, half sizefactor until it is small enough
98             qreal minFactor = 1.0;
99             if (scalable + fixed > lineWidth) {
100                 for (int lim = 0; lim < 32; lim++) {
101                     minFactor /= 2;
102                     qreal newSize = engraveBars(sheet, lastStart, i-1, minFactor);
103                     if (newSize <= lineWidth) break;
104                 }
105             }
106             // double sizefactor until line becomes too width
107             qreal maxFactor = 2.0;
108             for (int lim = 0; lim < 32; lim++) {
109                 qreal newSize = engraveBars(sheet, lastStart, i-1, maxFactor);
110                 if (newSize >= lineWidth) break;
111                 maxFactor *= 2;
112             }
113             // now binary search between min and max factor for ideal factor
114             while (minFactor < maxFactor - 1e-4) {
115                 qreal middle = (minFactor + maxFactor) / 2;
116                 qreal newSize = engraveBars(sheet, lastStart, i-1, middle);
117                 if (newSize > lineWidth) {
118                     maxFactor = middle;
119                 } else {
120                     minFactor = middle;
121                 }
122             }
123 
124             QPointF sp = sheet->bar(lastStart)->position() - QPointF(sheet->bar(lastStart)->prefix(), 0);
125             for (int j = lastStart; j < i; j++) {
126                 sheet->bar(j)->setPosition(sp + QPointF(sheet->bar(j)->prefix(), 0));
127                 sp.setX(sp.x() + sheet->bar(j)->size() + sheet->bar(j)->prefix());
128             }
129             lastStart = i;
130             if (bar->prefix() > 0) {
131                 bar->setPrefixPosition(sp);
132                 prefixPlaced = true;
133             }
134             prevPrefixPlaced = prefixPlaced;
135 
136             curSystem++;
137             p.setY(sheet->staffSystem(curSystem)->top() - deltay);
138             sheet->staffSystem(curSystem)->setFirstBar(i);
139 
140             indent = 0;
141             QList<Clef*> clefs;
142             // Extra space for clef/key signature repeating
143             for (int partIdx = 0; partIdx < sheet->partCount(); partIdx++) {
144                 Part* part = sheet->part(partIdx);
145                 for (int staffIdx = 0; staffIdx < part->staffCount(); staffIdx++) {
146                     Staff* staff = part->staff(staffIdx);
147                     qreal w = 0;
148                     Clef* clef = staff->lastClefChange(i, 0);
149                     if (clef) {
150                         w += clef->width() + 15;
151                         clefs.append(clef);
152                     }
153                     KeySignature* ks = staff->lastKeySignatureChange(i);
154                     if (ks) w += ks->width() + 15;
155                     if (w > indent) indent = w;
156                 }
157             }
158             sheet->staffSystem(curSystem)->setIndent(indent);
159             sheet->staffSystem(curSystem)->setLineWidth(lineWidth);
160             sheet->staffSystem(curSystem)->setClefs(clefs);
161             lineWidth = size.width() - indent;
162             p.setX(indent - bar->prefix());
163 
164             if (p.y() + sheet->staffSystem(curSystem)->height() >= size.height()) {
165                 *lastSystem = curSystem-1;
166 
167                 // some code depends on having the position of the next bar
168                 sheet->bar(i)->setPosition(p + QPointF(bar->prefix(), 0), !prefixPlaced);
169                 sheet->bar(i)->setSize(sheet->bar(i)->naturalSize());
170 
171                 break;
172             }
173         }
174         sheet->bar(i)->setPosition(p + QPointF(bar->prefix(), 0), !prefixPlaced);
175         sheet->bar(i)->setSize(sheet->bar(i)->naturalSize());
176         p.setX(p.x() + sheet->bar(i)->size() + bar->prefix());
177     }
178     if (*lastSystem == -1) *lastSystem = curSystem;
179     // potentially scale last staff system if it is too wide
180     if (p.x() - indent > lineWidth) {
181         qreal scalable = 0, fixed = 0;
182         for (int j = lastStart; j < sheet->barCount(); j++) {
183             scalable += sheet->bar(j)->size();
184             fixed += sheet->bar(j)->prefix();
185         }
186         // now scale factor is (available width - fixed) / scalable width;
187         qreal factor = (lineWidth - fixed) / scalable;
188         Q_UNUSED(factor);
189         QPointF sp = sheet->bar(lastStart)->position() - QPointF(sheet->bar(lastStart)->prefix(), 0);
190         for (int j = lastStart; j < sheet->barCount(); j++) {
191             //sheet->bar(j)->setPosition(sp + QPointF(sheet->bar(j)->prefix(), 0));
192             //sheet->bar(j)->setSize(sheet->bar(j)->desiredSize() * factor);
193             sp.setX(sp.x() + sheet->bar(j)->size() + sheet->bar(j)->prefix());
194         }
195     }
196 
197     sheet->setStaffSystemCount(curSystem+1);
198 }
199 
engraveBars(Sheet * sheet,int firstBar,int lastBar,qreal sizeFactor)200 qreal Engraver::engraveBars(Sheet* sheet, int firstBar, int lastBar, qreal sizeFactor)
201 {
202     qreal size = 0;
203     for (int i = firstBar; i <= lastBar; i++) {
204         engraveBar(sheet->bar(i), sizeFactor);
205         size += sheet->bar(i)->size() + sheet->bar(i)->prefix();
206     }
207     return size;
208 }
209 
210 struct Simultanity {
211     int startTime;
212     int duration; ///< the duration of this simultanity (as in the startTime of the next one minus start time of this one)
213     int minChordDuration; ///< the duration of the shortest note not yet finished at this time
214     qreal space;
215     QList<VoiceElement*> voiceElements;
SimultanitySimultanity216     Simultanity(int time) : startTime(time), duration(0), minChordDuration(0), space(0) {}
217 };
218 
collectSimultanities(Sheet * sheet,int barIdx,QList<Simultanity> & simultanities,int & shortestNote)219 static void collectSimultanities(Sheet* sheet, int barIdx, QList<Simultanity>& simultanities, int& shortestNote)
220 {
221     Bar* bar = sheet->bar(barIdx);
222 
223     // collect all voices in all parts
224     QList<VoiceBar*> voices;
225     QList<int> voiceIds;
226     for (int p = 0; p < sheet->partCount(); p++) {
227         Part* part = sheet->part(p);
228         for (int v = 0; v < part->voiceCount(); v++) {
229             voices.append(bar->voice(part->voice(v)));
230             voiceIds.append(v);
231         }
232     }
233 
234     QVarLengthArray<int> nextTime(voices.size());
235     QVarLengthArray<int> nextIndex(voices.size());
236     // initialize stuff to 0
237     for (int i = 0; i < voices.size(); i++) {
238         nextTime[i] = 0;
239         nextIndex[i] = 0;
240     }
241 
242     QMultiMap<Staff*, VoiceBar*> staffVoices;
243     foreach (VoiceBar* vb, voices) {
244         for (int e = 0; e < vb->elementCount(); e++) {
245             Staff* s = vb->element(e)->staff();
246             if (!staffVoices.contains(s, vb)) staffVoices.insert(s, vb);
247         }
248     }
249 
250     shortestNote = INT_MAX;
251     // loop until all elements are placed
252     for (;;) {
253         // find earliest start time
254         int time = INT_MAX;
255         for (int i = 0; i < voices.size(); i++) {
256             if (nextIndex[i] < voices[i]->elementCount()) {
257                 if (nextTime[i] < time) time = nextTime[i];
258             }
259         }
260 
261         // none found, break
262         if (time == INT_MAX) break;
263 
264         // now add the correct items to a new simultanity
265         Simultanity sim(time);
266         for (int i = 0; i < voices.size(); i++) {
267             if (nextTime[i] == time && nextIndex[i] < voices[i]->elementCount()) {
268                 sim.voiceElements.append(voices[i]->element(nextIndex[i]));
269                 nextTime[i] += voices[i]->element(nextIndex[i])->length();
270                 shortestNote = qMin(shortestNote, voices[i]->element(nextIndex[i])->length());
271                 nextIndex[i]++;
272             }
273         }
274 
275         // figure out the length of the shortest note with index = nextIndex[i]-1
276         int minLength = INT_MAX;
277         for (int i = 0; i < voices.size(); i++) {
278             if (nextIndex[i] && nextTime[i] > time) {
279                 minLength = qMin(minLength, voices[i]->element(nextIndex[i]-1)->length());
280             }
281         }
282         sim.minChordDuration = minLength;
283 
284         simultanities.append(sim);
285     }
286 
287     // now fill in the duration of the simultanities
288     for (int i = 0; i < simultanities.size() - 1; i++) {
289         simultanities[i].duration = simultanities[i+1].startTime - simultanities[i].startTime;
290     }
291     if (simultanities.size()) {
292         Simultanity& sim = simultanities[simultanities.size() - 1];
293         sim.duration = 0;
294         for (int i = 0; i < sim.voiceElements.size(); i++) {
295             sim.duration = qMax(sim.duration, sim.voiceElements[i]->length());
296         }
297     }
298 }
299 
engraveBar(Bar * bar,qreal sizeFactor)300 void Engraver::engraveBar(Bar* bar, qreal sizeFactor)
301 {
302 
303     Sheet* sheet = bar->sheet();
304     int barIdx = sheet->indexOfBar(bar);
305 
306     QList<Simultanity> simultanities;
307     int shortestNoteLength; // 'm' in the formula
308     // collect simultanities
309     collectSimultanities(sheet, barIdx, simultanities, shortestNoteLength);
310 
311     // 'T' in the formula
312     qreal baseFactor = bar->sizeFactor() * sizeFactor - log2((qreal) qMin(shortestNoteLength, (int) Note8Length) / WholeLength);
313 
314     // assign space to simultanities according to durations
315     for (int i = 0; i < simultanities.size(); i++) {
316         Simultanity& sim = simultanities[i];
317 
318         qreal scaleFactor = (qreal) sim.duration / sim.minChordDuration; // 'e' in the formula
319         if (scaleFactor > 1) scaleFactor = 1;
320         qreal duration = (qreal) sim.duration / WholeLength;
321         sim.space = scaleFactor * ( log2(duration) + baseFactor );
322     }
323 
324     // give voice elements positions according to space assigned
325     qreal noteHeadSize = 7.0;
326 
327     qreal curx = 15.0;
328     for (int s = 0; s < simultanities.size(); s++) {
329         Simultanity& sim = simultanities[s];
330         foreach (VoiceElement* ve, sim.voiceElements) {
331             ve->setX(curx - ve->beatline());
332         }
333         curx += sim.space * noteHeadSize;
334     }
335 
336     // collect all voices in all parts
337     QList<VoiceBar*> voices;
338     QList<int> voiceIds;
339     for (int p = 0; p < sheet->partCount(); p++) {
340         Part* part = sheet->part(p);
341         for (int v = 0; v < part->voiceCount(); v++) {
342             voices.append(bar->voice(part->voice(v)));
343             rebeamBar(part, bar->voice(part->voice(v)));
344             voiceIds.append(v);
345         }
346     }
347 
348     QVarLengthArray<int> nextTime(voices.size());
349     QVarLengthArray<int> nextIndex(voices.size());
350     // initialize stuff to 0
351     for (int i = 0; i < voices.size(); i++) {
352         nextTime[i] = 0;
353         nextIndex[i] = 0;
354     }
355 
356     // collect staff elements in all staffs
357     int staffCount = 0;
358     for (int p = 0; p < sheet->partCount(); p++) {
359         staffCount += sheet->part(p)->staffCount();
360     }
361 
362     QVarLengthArray<QList<StaffElement*> > staffElements(staffCount);
363 
364     for (int st = 0, p = 0; p < sheet->partCount(); ++p) {
365         Part* part = sheet->part(p);
366         for (int s = 0; s < part->staffCount(); s++, st++) {
367             Staff* staff = part->staff(s);
368             for (int i = 0; i < bar->staffElementCount(staff); i++) {
369                 staffElements[st].append(bar->staffElement(staff, i));
370             }
371         }
372     }
373 
374     QMultiMap<Staff*, VoiceBar*> staffVoices;
375     foreach (VoiceBar* vb, voices) {
376         for (int e = 0; e < vb->elementCount(); e++) {
377             Staff* s = vb->element(e)->staff();
378             if (!staffVoices.contains(s, vb)) staffVoices.insert(s, vb);
379         }
380     }
381 
382     qreal x = 0; // this is the end position of the last placed elements
383     bool endOfPrefix = false;
384     QList<StaffElement*> prefix;
385     // loop until all elements are placed
386     for (;;) {
387         // find earliest start time
388         int time = INT_MAX;
389         for (int i = 0; i < voices.size(); i++) {
390             if (nextIndex[i] < voices[i]->elementCount()) {
391                 if (nextTime[i] < time) time = nextTime[i];
392             }
393         }
394 
395         bool staffElement = false;
396         int priority = INT_MIN;
397         for (int s = 0; s < staffCount; s++) {
398             if (staffElements[s].size() > 0) {
399                 if (staffElements[s][0]->startTime() <= time) {
400                     time = staffElements[s][0]->startTime();
401                     staffElement = true;
402                     if (staffElements[s][0]->priority() > priority) {
403                         priority = staffElements[s][0]->priority();
404                     }
405                 }
406             }
407         }
408 
409         if ((!staffElement || time > 0) && !endOfPrefix) {
410             // we've reached the end of the prefix; now update all already placed staff elements to have correct
411             // (negative) x coordinates, and set the size of the prefix.
412             if (prefix.size() > 0) {
413                 qreal prefixSize = x + 5;
414                 bar->setPrefix(prefixSize);
415                 foreach (StaffElement* se, prefix) {
416                     se->setX(se->x() - prefixSize);
417                 }
418                 x = 0;
419             } else {
420                 bar->setPrefix(0.0);
421             }
422             endOfPrefix = true;
423         }
424 
425         // none found, break
426         if (time == INT_MAX) break;
427 
428         qreal maxEnd = x;
429         // now update all items with correct start time
430         if (staffElement) {
431             for (int s = 0; s < staffCount; s++) {
432                 if (staffElements[s].size() > 0 && staffElements[s][0]->startTime() == time && staffElements[s][0]->priority() == priority) {
433                     StaffElement* se = staffElements[s].takeAt(0);
434                     qreal xpos = x + 15;
435                     se->setX(xpos);
436                     qreal xend = se->width() + xpos;
437                     if (xend > maxEnd) maxEnd = xend;
438                     if (!endOfPrefix) prefix.append(se);
439                 }
440             }
441         } else {
442             for (int i = 0; i < voices.size(); i++) {
443                 if (nextTime[i] == time && nextIndex[i] < voices[i]->elementCount()) {
444                     // If it is a chord, also figure out correct stem direction for the chord; right now
445                     // direction is only based on position of the notes, but in the future this should
446                     // also depend on other chord in other voices in the same staff
447                     Chord* c = dynamic_cast<Chord*>(voices[i]->element(nextIndex[i]));
448                     if (c) {
449                         // if this is the continuation or end of a beam, the first chord in the beam has the
450                         // correct stem direction already
451                         if (c->beamType(0) == BeamContinue || c->beamType(0) == BeamEnd) {
452                             c->setStemDirection(c->beamStart(0)->stemDirection());
453                         } else if (c->beamType(0) == BeamStart) {
454                             // for the start of a beam, check all the other chords in the beam to determine
455                             // the correct direction
456                             if (staffVoices.count(c->staff()) > 1) {
457                                 int voiceIdx = voiceIds[i];
458                                 c->setStemDirection(voiceIdx & 1 ? StemDown : StemUp);
459                             } else {
460                                 int numUp = 0;
461                                 int numDown = 0;
462                                 const Chord* endChord = c->beamEnd(0);
463                                 for (int j = nextIndex[i]; j < voices[i]->elementCount(); j++) {
464                                     Chord* chord = dynamic_cast<Chord*>(voices[i]->element(j));
465                                     if (!chord) continue;
466                                     if (chord->desiredStemDirection() == StemUp) {
467                                         numUp++;
468                                     } else {
469                                         numDown++;
470                                     }
471                                     if (chord == endChord) break;
472                                 }
473                                 if (numUp > numDown) {
474                                     c->setStemDirection(StemUp);
475                                 } else if (numUp < numDown) {
476                                     c->setStemDirection(StemDown);
477                                 } else {
478                                     c->setStemDirection(c->desiredStemDirection());
479                                 }
480                             }
481                         } else {
482                             Staff* staff = c->staff();
483                             if (staffVoices.count(staff) > 1) {
484                                 int voiceIdx = voiceIds[i];
485                                 c->setStemDirection(voiceIdx & 1 ? StemDown : StemUp);
486                             } else {
487                                 c->setStemDirection(c->desiredStemDirection());
488                             }
489                         }
490                     }
491 
492                     qreal xpos = x + 15;
493                     //voices[i]->element(nextIndex[i])->setX(xpos);
494                     qreal xend = voices[i]->element(nextIndex[i])->width() + xpos;
495                     if (xend > maxEnd) maxEnd = xend;
496                     nextTime[i] += voices[i]->element(nextIndex[i])->length();
497                     nextIndex[i]++;
498                 }
499             }
500         }
501 
502         x = maxEnd;
503     }
504     if (curx < 50) curx = 50;
505     bar->setSize(curx);
506 
507     // finally calculate correct stem lengths for all beamed groups of notes
508     foreach (VoiceBar* vb, voices) {
509         for (int i = 0; i < vb->elementCount(); i++) {
510             Chord* c = dynamic_cast<Chord*>(vb->element(i));
511             if (!c) continue;
512             if (c->beamType(0) == BeamStart) {
513                 // fetch all chords in the beam
514                 QList<Chord*> chords;
515                 QVector<QPointF> stemEnds;
516                 for (int j = i; j < vb->elementCount(); j++) {
517                     Chord* chord = dynamic_cast<Chord*>(vb->element(j));
518                     if (!chord) continue;
519                     if (chord->beamStart(0) == c) {
520                         chord->setStemLength(chord->desiredStemLength());
521                         chords.append(chord);
522                         stemEnds.append(QPointF(chord->stemX(), chord->stemEndY(false)));
523                     }
524                     if (chord == c->beamEnd(0)) {
525                         break;
526                     }
527                 }
528 
529                 for (int j = stemEnds.size()-1; j >= 0; j--) {
530                     stemEnds[j] -= stemEnds[0];
531                 }
532                 if (c->stemDirection() == StemUp) {
533                     for (int j = 0; j < stemEnds.size(); j++) {
534                         stemEnds[j].setY(-stemEnds[j].y());
535                     }
536                 }
537 
538                 // now somehow fit a line through all those points...
539                 qreal bestError = 1e99;
540                 qreal bestK = 0, bestL = 0;
541                 for (int a = 0; a < stemEnds.size(); a++) {
542                     for (int b = a+1; b < stemEnds.size(); b++) {
543                         // assume a line that passes through stemEnds[a] and stemEnds[b]
544                         // line is in form of k*x + l
545                         qreal k = (stemEnds[b].y() - stemEnds[a].y()) / (stemEnds[b].x() - stemEnds[a].x());
546                         qreal l = stemEnds[a].y() - (stemEnds[a].x() * k);
547 
548                         //debugMusic << "a:" << stemEnds[a] << ", b:" << stemEnds[b] << ", k:" << k << ", l:" << l;
549 
550                         //for (int j = 0; j < stemEnds.size(); j++) {
551                         //    debugMusic << "    " << stemEnds[j] << "; " << (k * stemEnds[j].x() + l);
552                         //}
553                         // check if it is entirely above all stemEnds, and calculate sum of distances to stemEnds
554                         bool validLine = true;
555                         qreal error = 0;
556                         for (int j = 0; j < stemEnds.size(); j++) {
557                             qreal y = k * stemEnds[j].x() + l;
558                             if (y < stemEnds[j].y() - 1e-9) {
559                                 validLine = false;
560                                 break;
561                             } else {
562                                 error += y - stemEnds[j].y();
563                             }
564                         }
565                         if (validLine) {
566                             if (error < bestError) {
567                                 bestError = error;
568                                 bestK = k;
569                                 bestL = l;
570                             }
571                         }
572                     }
573                 }
574 
575                 //debugMusic << "bestError:" << bestError << "bestK:" << bestK << "bestL:" << bestL;
576 
577                 c->setStemLength(c->desiredStemLength() + bestL / c->staff()->lineSpacing());
578                 Chord* endChord = c->beamEnd(0);
579                 qreal endY = stemEnds[stemEnds.size()-1].x() * bestK + bestL;
580                 //debugMusic << "old y:" << stemEnds[stemEnds.size()-1].y() << "new y:" << endY;
581                 qreal extra = endY - stemEnds[stemEnds.size()-1].y();
582                 endChord->setStemLength(endChord->desiredStemLength() + extra / endChord->staff()->lineSpacing());
583             }
584         }
585     }
586 }
587 
rebeamBar(Part * part,VoiceBar * vb)588 void Engraver::rebeamBar(Part* part, VoiceBar* vb)
589 {
590     Bar* bar = vb->bar();
591     TimeSignature* ts = part->staff(0)->lastTimeSignatureChange(bar);
592     if (!ts) return;
593 
594     QList<int> beats = ts->beatLengths();
595     int nextBeat = 0;
596     int passedBeats = 0;
597 
598     int curTime = 0;
599     int beamStartTime = 0;
600     for (int i = 0, beamStart = -1; i < vb->elementCount(); i++) {
601         VoiceElement* ve = vb->element(i);
602         Chord* c = dynamic_cast<Chord*>(ve);
603         if (!c) continue;
604         curTime += ve->length();
605 
606         if (c->duration() <= EighthNote && beamStart < 0) {
607             beamStart = i;
608             beamStartTime = curTime - ve->length();
609             for (int b = 0; b < c->beamCount(); b++) {
610                 c->setBeam(b, c, c, BeamFlag);
611             }
612         }
613 
614         int beatEnd = beats[nextBeat] + passedBeats;
615         if (curTime >= beatEnd || c->noteCount() == 0 || c->duration() > EighthNote || i == vb->elementCount()-1) {
616             int beamEnd = i;
617             if (c->duration() > EighthNote || c->noteCount() == 0) {
618                 beamEnd--;
619             }
620 
621             if (beamEnd > beamStart && beamStart >= 0) {
622                 Chord* sChord = dynamic_cast<Chord*>(vb->element(beamStart));
623                 Chord* eChord = dynamic_cast<Chord*>(vb->element(beamEnd));
624 
625                 int start[6] = {-1, -1, -1, -1, -1, -1};
626                 int startTime[6];
627 
628                 for (int j = beamStart, beamTime = beamStartTime; j <= beamEnd; j++) {
629                     Chord* chord = dynamic_cast<Chord*>(vb->element(j));
630                     if (chord) {
631                         int factor = Note8Length;
632                         for (int b = 1; b < chord->beamCount(); b++) {
633                             if (start[b] == -1) {
634                                 start[b] = j;
635                                 startTime[b] = beamTime;
636                             }
637                             factor /= 2;
638                         }
639                         for (int b = chord->beamCount(); b < 6; b++) {
640                             if (start[b] != -1) {
641                                 Chord* sc = static_cast<Chord*>(vb->element(start[b]));
642                                 Chord* ec = static_cast<Chord*>(vb->element(j-1));
643                                 if (sc == ec) {
644                                     int sTime = startTime[b];
645                                     int eTime = sTime + sc->length();
646                                     int preSTime = (sTime / factor) * factor; // largest multiple of factor <= sTime
647                                     int postETime = ((eTime + factor - 1) / factor) * factor; // smallest multiple of factor >= eTime
648                                     if (sTime - preSTime < postETime - eTime) {
649                                         sc->setBeam(b, sc, ec, BeamForwardHook);
650                                     } else {
651                                         sc->setBeam(b, sc, ec, BeamBackwardHook);
652                                     }
653                                 } else {
654                                     for (int k = start[b]; k < j; k++) {
655                                         Chord* chord = dynamic_cast<Chord*>(vb->element(k));
656                                         if (chord) chord->setBeam(b, sc, ec);
657                                     }
658                                 }
659                                 start[b] = -1;
660                             }
661                             factor /= 2;
662                         }
663 
664                         chord->setBeam(0, sChord, eChord);
665                         beamTime += chord->length();
666                     }
667                 }
668                 int factor = Note8Length;
669                 for (int b = 1; b < 6; b++) {
670                     if (start[b] != -1) {
671                         Chord* sc = static_cast<Chord*>(vb->element(start[b]));
672                         Chord* ec = static_cast<Chord*>(vb->element(beamEnd));
673                         if (sc == ec) {
674                             int sTime = startTime[b];
675                             int eTime = sTime + sc->length();
676                             int preSTime = (sTime / factor) * factor; // largest multiple of factor <= sTime
677                             int postETime = ((eTime + factor - 1) / factor) * factor; // smallest multiple of factor >= eTime
678                             if (sTime - preSTime < postETime - eTime) {
679                                 sc->setBeam(b, sc, ec, BeamForwardHook);
680                             } else {
681                                 sc->setBeam(b, sc, ec, BeamBackwardHook);
682                             }
683                         } else {
684                             for (int k = start[b]; k <= beamEnd; k++) {
685                                 Chord* chord = dynamic_cast<Chord*>(vb->element(k));
686                                 if (chord) chord->setBeam(b, sc, ec);
687                             }
688                         }
689                         start[b] = -1;
690                     }
691                     factor /= 2;
692                 }
693             }
694 
695             beamStart = -1;
696             while (curTime >= beatEnd) {
697                 passedBeats += beats[nextBeat];
698                 nextBeat++;
699                 if (nextBeat >= beats.size()) nextBeat = 0;
700                 beatEnd = passedBeats + beats[nextBeat];
701             }
702         }
703     }
704 }
705