libs/ardour/tempo.cc

   1 /*
   2     Copyright (C) 2000-2002 Paul Davis
   3
   4     This program is free software; you can redistribute it and/or modify
   5     it under the terms of the GNU General Public License as published by
   6     the Free Software Foundation; either version 2 of the License, or
   7     (at your option) any later version.
   8
   9     This program 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
  12     GNU General Public License for more details.
  13
  14     You should have received a copy of the GNU General Public License
  15     along with this program; if not, write to the Free Software
  16     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17
  18 */
  19
  20 #include <algorithm>
  21 #include <stdexcept>
  22 #include <cmath>
  23
  24 #include <unistd.h>
  25
  26 #include <glibmm/threads.h>
  27 #include "pbd/xml++.h"
  28 #include "evoral/types.hpp"
  29 #include "ardour/debug.h"
  30 #include "ardour/tempo.h"
  31
  32 #include "i18n.h"
  33 #include <locale.h>
  34
  35 using namespace std;
  36 using namespace ARDOUR;
  37 using namespace PBD;
  38
  39 using Timecode::BBT_Time;
  40
  41 /* _default tempo is 4/4 qtr=120 */
  42
  43 Meter    TempoMap::_default_meter (4.0, 4.0);
  44 Tempo    TempoMap::_default_tempo (120.0);
  45
  46 double
  47 Tempo::frames_per_beat (framecnt_t sr) const
  48 {
  49         return  (60.0 * sr) / _beats_per_minute;
  50 }
  51
  52 /***********************************************************************/
  53
  54 double
  55 Meter::frames_per_grid (const Tempo& tempo, framecnt_t sr) const
  56 {
  57         /* This is tempo- and meter-sensitive. The number it returns
  58            is based on the interval between any two lines in the
  59            grid that is constructed from tempo and meter sections.
  60
  61            The return value IS NOT interpretable in terms of "beats".
  62         */
  63
  64         return (60.0 * sr) / (tempo.beats_per_minute() * (_note_type/tempo.note_type()));
  65 }
  66
  67 double
  68 Meter::frames_per_bar (const Tempo& tempo, framecnt_t sr) const
  69 {
  70         return frames_per_grid (tempo, sr) * _divisions_per_bar;
  71 }
  72
  73 /***********************************************************************/
  74
  75 const string TempoSection::xml_state_node_name = "Tempo";
  76
  77 TempoSection::TempoSection (const XMLNode& node)
  78         : MetricSection (BBT_Time()), Tempo (TempoMap::default_tempo())
  79 {
  80         const XMLProperty *prop;
  81         BBT_Time start;
  82         LocaleGuard lg (X_("POSIX"));
  83
  84         if ((prop = node.property ("start")) == 0) {
  85                 error << _("TempoSection XML node has no \"start\" property") << endmsg;
  86                 throw failed_constructor();
  87         }
  88
  89         if (sscanf (prop->value().c_str(), "%" PRIu32 "|%" PRIu32 "|%" PRIu32,
  90                     &start.bars,
  91                     &start.beats,
  92                     &start.ticks) < 3) {
  93                 error << _("TempoSection XML node has an illegal \"start\" value") << endmsg;
  94                 throw failed_constructor();
  95         }
  96
  97         set_start (start);
  98
  99         if ((prop = node.property ("beats-per-minute")) == 0) {
 100                 error << _("TempoSection XML node has no \"beats-per-minute\" property") << endmsg;
 101                 throw failed_constructor();
 102         }
 103
 104         if (sscanf (prop->value().c_str(), "%lf", &_beats_per_minute) != 1 || _beats_per_minute < 0.0) {
 105                 error << _("TempoSection XML node has an illegal \"beats_per_minute\" value") << endmsg;
 106                 throw failed_constructor();
 107         }
 108
 109         if ((prop = node.property ("note-type")) == 0) {
 110                 /* older session, make note type be quarter by default */
 111                 _note_type = 4.0;
 112         } else {
 113                 if (sscanf (prop->value().c_str(), "%lf", &_note_type) != 1 || _note_type < 1.0) {
 114                         error << _("TempoSection XML node has an illegal \"note-type\" value") << endmsg;
 115                         throw failed_constructor();
 116                 }
 117         }
 118
 119         if ((prop = node.property ("movable")) == 0) {
 120                 error << _("TempoSection XML node has no \"movable\" property") << endmsg;
 121                 throw failed_constructor();
 122         }
 123
 124         set_movable (string_is_affirmative (prop->value()));
 125
 126         if ((prop = node.property ("bar-offset")) == 0) {
 127                 _bar_offset = -1.0;
 128         } else {
 129                 if (sscanf (prop->value().c_str(), "%lf", &_bar_offset) != 1 || _bar_offset < 0.0) {
 130                         error << _("TempoSection XML node has an illegal \"bar-offset\" value") << endmsg;
 131                         throw failed_constructor();
 132                 }
 133         }
 134 }
 135
 136 XMLNode&
 137 TempoSection::get_state() const
 138 {
 139         XMLNode *root = new XMLNode (xml_state_node_name);
 140         char buf[256];
 141         LocaleGuard lg (X_("POSIX"));
 142
 143         snprintf (buf, sizeof (buf), "%" PRIu32 "|%" PRIu32 "|%" PRIu32,
 144                   start().bars,
 145                   start().beats,
 146                   start().ticks);
 147         root->add_property ("start", buf);
 148         snprintf (buf, sizeof (buf), "%f", _beats_per_minute);
 149         root->add_property ("beats-per-minute", buf);
 150         snprintf (buf, sizeof (buf), "%f", _note_type);
 151         root->add_property ("note-type", buf);
 152         // snprintf (buf, sizeof (buf), "%f", _bar_offset);
 153         // root->add_property ("bar-offset", buf);
 154         snprintf (buf, sizeof (buf), "%s", movable()?"yes":"no");
 155         root->add_property ("movable", buf);
 156
 157         return *root;
 158 }
 159
 160 void
 161
 162 TempoSection::update_bar_offset_from_bbt (const Meter& m)
 163 {
 164         _bar_offset = ((start().beats - 1) * BBT_Time::ticks_per_beat + start().ticks) /
 165                 (m.divisions_per_bar() * BBT_Time::ticks_per_beat);
 166
 167         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Tempo set bar offset to %1 from %2 w/%3\n", _bar_offset, start(), m.divisions_per_bar()));
 168 }
 169
 170 void
 171 TempoSection::update_bbt_time_from_bar_offset (const Meter& meter)
 172 {
 173         BBT_Time new_start;
 174
 175         if (_bar_offset < 0.0) {
 176                 /* not set yet */
 177                 return;
 178         }
 179
 180         new_start.bars = start().bars;
 181
 182         double ticks = BBT_Time::ticks_per_beat * meter.divisions_per_bar() * _bar_offset;
 183         new_start.beats = (uint32_t) floor (ticks/BBT_Time::ticks_per_beat);
 184         new_start.ticks = 0; /* (uint32_t) fmod (ticks, BBT_Time::ticks_per_beat); */
 185
 186         /* remember the 1-based counting properties of beats */
 187         new_start.beats += 1;
 188
 189         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("from bar offset %1 and dpb %2, ticks = %3->%4 beats = %5\n",
 190                                                        _bar_offset, meter.divisions_per_bar(), ticks, new_start.ticks, new_start.beats));
 191
 192         set_start (new_start);
 193 }
 194
 195 /***********************************************************************/
 196
 197 const string MeterSection::xml_state_node_name = "Meter";
 198
 199 MeterSection::MeterSection (const XMLNode& node)
 200         : MetricSection (BBT_Time()), Meter (TempoMap::default_meter())
 201 {
 202         const XMLProperty *prop;
 203         BBT_Time start;
 204         LocaleGuard lg (X_("POSIX"));
 205
 206         if ((prop = node.property ("start")) == 0) {
 207                 error << _("MeterSection XML node has no \"start\" property") << endmsg;
 208                 throw failed_constructor();
 209         }
 210
 211         if (sscanf (prop->value().c_str(), "%" PRIu32 "|%" PRIu32 "|%" PRIu32,
 212                     &start.bars,
 213                     &start.beats,
 214                     &start.ticks) < 3) {
 215                 error << _("MeterSection XML node has an illegal \"start\" value") << endmsg;
 216                 throw failed_constructor();
 217         }
 218
 219         set_start (start);
 220
 221         /* beats-per-bar is old; divisions-per-bar is new */
 222
 223         if ((prop = node.property ("divisions-per-bar")) == 0) {
 224                 if ((prop = node.property ("beats-per-bar")) == 0) {
 225                         error << _("MeterSection XML node has no \"beats-per-bar\" or \"divisions-per-bar\" property") << endmsg;
 226                         throw failed_constructor();
 227                 }
 228         }
 229
 230         if (sscanf (prop->value().c_str(), "%lf", &_divisions_per_bar) != 1 || _divisions_per_bar < 0.0) {
 231                 error << _("MeterSection XML node has an illegal \"beats-per-bar\" or \"divisions-per-bar\" value") << endmsg;
 232                 throw failed_constructor();
 233         }
 234
 235         if ((prop = node.property ("note-type")) == 0) {
 236                 error << _("MeterSection XML node has no \"note-type\" property") << endmsg;
 237                 throw failed_constructor();
 238         }
 239
 240         if (sscanf (prop->value().c_str(), "%lf", &_note_type) != 1 || _note_type < 0.0) {
 241                 error << _("MeterSection XML node has an illegal \"note-type\" value") << endmsg;
 242                 throw failed_constructor();
 243         }
 244
 245         if ((prop = node.property ("movable")) == 0) {
 246                 error << _("MeterSection XML node has no \"movable\" property") << endmsg;
 247                 throw failed_constructor();
 248         }
 249
 250         set_movable (string_is_affirmative (prop->value()));
 251 }
 252
 253 XMLNode&
 254 MeterSection::get_state() const
 255 {
 256         XMLNode *root = new XMLNode (xml_state_node_name);
 257         char buf[256];
 258         LocaleGuard lg (X_("POSIX"));
 259
 260         snprintf (buf, sizeof (buf), "%" PRIu32 "|%" PRIu32 "|%" PRIu32,
 261                   start().bars,
 262                   start().beats,
 263                   start().ticks);
 264         root->add_property ("start", buf);
 265         snprintf (buf, sizeof (buf), "%f", _note_type);
 266         root->add_property ("note-type", buf);
 267         snprintf (buf, sizeof (buf), "%f", _divisions_per_bar);
 268         root->add_property ("divisions-per-bar", buf);
 269         snprintf (buf, sizeof (buf), "%s", movable()?"yes":"no");
 270         root->add_property ("movable", buf);
 271
 272         return *root;
 273 }
 274
 275 /***********************************************************************/
 276
 277 struct MetricSectionSorter {
 278     bool operator() (const MetricSection* a, const MetricSection* b) {
 279             return a->start() < b->start();
 280     }
 281 };
 282
 283 TempoMap::TempoMap (framecnt_t fr)
 284 {
 285         _frame_rate = fr;
 286         BBT_Time start;
 287
 288         start.bars = 1;
 289         start.beats = 1;
 290         start.ticks = 0;
 291
 292         TempoSection *t = new TempoSection (start, _default_tempo.beats_per_minute(), _default_tempo.note_type());
 293         MeterSection *m = new MeterSection (start, _default_meter.divisions_per_bar(), _default_meter.note_divisor());
 294
 295         t->set_movable (false);
 296         m->set_movable (false);
 297
 298         /* note: frame time is correct (zero) for both of these */
 299
 300         metrics.push_back (t);
 301         metrics.push_back (m);
 302 }
 303
 304 TempoMap::~TempoMap ()
 305 {
 306 }
 307
 308 void
 309 TempoMap::remove_tempo (const TempoSection& tempo, bool complete_operation)
 310 {
 311         bool removed = false;
 312
 313         {
 314                 Glib::Threads::RWLock::WriterLock lm (lock);
 315                 Metrics::iterator i;
 316
 317                 for (i = metrics.begin(); i != metrics.end(); ++i) {
 318                         if (dynamic_cast<TempoSection*> (*i) != 0) {
 319                                 if (tempo.frame() == (*i)->frame()) {
 320                                         if ((*i)->movable()) {
 321                                                 metrics.erase (i);
 322                                                 removed = true;
 323                                                 break;
 324                                         }
 325                                 }
 326                         }
 327                 }
 328
 329                 if (removed && complete_operation) {
 330                         recompute_map (false);
 331                 }
 332         }
 333
 334         if (removed && complete_operation) {
 335                 PropertyChanged (PropertyChange ());
 336         }
 337 }
 338
 339 void
 340 TempoMap::remove_meter (const MeterSection& tempo, bool complete_operation)
 341 {
 342         bool removed = false;
 343
 344         {
 345                 Glib::Threads::RWLock::WriterLock lm (lock);
 346                 Metrics::iterator i;
 347
 348                 for (i = metrics.begin(); i != metrics.end(); ++i) {
 349                         if (dynamic_cast<MeterSection*> (*i) != 0) {
 350                                 if (tempo.frame() == (*i)->frame()) {
 351                                         if ((*i)->movable()) {
 352                                                 metrics.erase (i);
 353                                                 removed = true;
 354                                                 break;
 355                                         }
 356                                 }
 357                         }
 358                 }
 359
 360                 if (removed && complete_operation) {
 361                         recompute_map (true);
 362                 }
 363         }
 364
 365         if (removed && complete_operation) {
 366                 PropertyChanged (PropertyChange ());
 367         }
 368 }
 369
 370 void
 371 TempoMap::do_insert (MetricSection* section)
 372 {
 373         bool need_add = true;
 374
 375         assert (section->start().ticks == 0);
 376
 377         /* we only allow new meters to be inserted on beat 1 of an existing
 378          * measure.
 379          */
 380
 381         if (dynamic_cast<MeterSection*>(section)) {
 382
 383                 /* we need to (potentially) update the BBT times of tempo
 384                    sections based on this new meter.
 385                 */
 386
 387                 if ((section->start().beats != 1) || (section->start().ticks != 0)) {
 388
 389                         BBT_Time corrected = section->start();
 390                         corrected.beats = 1;
 391                         corrected.ticks = 0;
 392
 393                         warning << string_compose (_("Meter changes can only be positioned on the first beat of a bar. Moving from %1 to %2"),
 394                                                    section->start(), corrected) << endmsg;
 395
 396                         section->set_start (corrected);
 397                 }
 398         }
 399
 400
 401
 402         /* Look for any existing MetricSection that is of the same type and
 403            in the same bar as the new one, and remove it before adding
 404            the new one. Note that this means that if we find a matching,
 405            existing section, we can break out of the loop since we're
 406            guaranteed that there is only one such match.
 407         */
 408
 409         for (Metrics::iterator i = metrics.begin(); i != metrics.end(); ++i) {
 410
 411                 bool const iter_is_tempo = dynamic_cast<TempoSection*> (*i) != 0;
 412                 bool const insert_is_tempo = dynamic_cast<TempoSection*> (section) != 0;
 413
 414                 if (iter_is_tempo && insert_is_tempo) {
 415
 416                         /* Tempo sections */
 417
 418                         if ((*i)->start().bars == section->start().bars &&
 419                             (*i)->start().beats == section->start().beats) {
 420
 421                                 if (!(*i)->movable()) {
 422
 423                                         /* can't (re)move this section, so overwrite
 424                                          * its data content (but not its properties as
 425                                          * a section).
 426                                          */
 427
 428                                         *(dynamic_cast<Tempo*>(*i)) = *(dynamic_cast<Tempo*>(section));
 429                                         need_add = false;
 430                                 } else {
 431                                         metrics.erase (i);
 432                                 }
 433                                 break;
 434                         }
 435
 436                 } else if (!iter_is_tempo && !insert_is_tempo) {
 437
 438                         /* Meter Sections */
 439
 440                         if ((*i)->start().bars == section->start().bars) {
 441
 442                                 if (!(*i)->movable()) {
 443
 444                                         /* can't (re)move this section, so overwrite
 445                                          * its data content (but not its properties as
 446                                          * a section
 447                                          */
 448
 449                                         *(dynamic_cast<Meter*>(*i)) = *(dynamic_cast<Meter*>(section));
 450                                         need_add = false;
 451                                 } else {
 452                                         metrics.erase (i);
 453
 454                                 }
 455
 456                                 break;
 457                         }
 458                 } else {
 459                         /* non-matching types, so we don't care */
 460                 }
 461         }
 462
 463         /* Add the given MetricSection, if we didn't just reset an existing
 464          * one above
 465          */
 466
 467         if (need_add) {
 468
 469                 Metrics::iterator i;
 470
 471                 for (i = metrics.begin(); i != metrics.end(); ++i) {
 472                         if ((*i)->start() > section->start()) {
 473                                 break;
 474                         }
 475                 }
 476
 477                 metrics.insert (i, section);
 478         }
 479 }
 480
 481 void
 482 TempoMap::replace_tempo (const TempoSection& ts, const Tempo& tempo, const BBT_Time& where)
 483 {
 484         const TempoSection& first (first_tempo());
 485
 486         if (ts.start() != first.start()) {
 487                 remove_tempo (ts, false);
 488                 add_tempo (tempo, where);
 489         } else {
 490                 {
 491                         Glib::Threads::RWLock::WriterLock lm (lock);
 492                         /* cannot move the first tempo section */
 493                         *((Tempo*)&first) = tempo;
 494                         recompute_map (false);
 495                 }
 496         }
 497
 498         PropertyChanged (PropertyChange ());
 499 }
 500
 501 void
 502 TempoMap::add_tempo (const Tempo& tempo, BBT_Time where)
 503 {
 504         {
 505                 Glib::Threads::RWLock::WriterLock lm (lock);
 506
 507                 /* new tempos always start on a beat */
 508                 where.ticks = 0;
 509
 510                 TempoSection* ts = new TempoSection (where, tempo.beats_per_minute(), tempo.note_type());
 511
 512                 /* find the meter to use to set the bar offset of this
 513                  * tempo section.
 514                  */
 515
 516                 const Meter* meter = &first_meter();
 517
 518                 /* as we start, we are *guaranteed* to have m.meter and m.tempo pointing
 519                    at something, because we insert the default tempo and meter during
 520                    TempoMap construction.
 521
 522                    now see if we can find better candidates.
 523                 */
 524
 525                 for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
 526
 527                         const MeterSection* m;
 528
 529                         if (where < (*i)->start()) {
 530                                 break;
 531                         }
 532
 533                         if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
 534                                 meter = m;
 535                         }
 536                 }
 537
 538                 ts->update_bar_offset_from_bbt (*meter);
 539
 540                 /* and insert it */
 541
 542                 do_insert (ts);
 543
 544                 recompute_map (false);
 545         }
 546
 547
 548         PropertyChanged (PropertyChange ());
 549 }
 550
 551 void
 552 TempoMap::replace_meter (const MeterSection& ms, const Meter& meter, const BBT_Time& where)
 553 {
 554         const MeterSection& first (first_meter());
 555
 556         if (ms.start() != first.start()) {
 557                 remove_meter (ms, false);
 558                 add_meter (meter, where);
 559         } else {
 560                 {
 561                         Glib::Threads::RWLock::WriterLock lm (lock);
 562                         /* cannot move the first meter section */
 563                         *((Meter*)&first) = meter;
 564                         recompute_map (true);
 565                 }
 566         }
 567
 568         PropertyChanged (PropertyChange ());
 569 }
 570
 571 void
 572 TempoMap::add_meter (const Meter& meter, BBT_Time where)
 573 {
 574         {
 575                 Glib::Threads::RWLock::WriterLock lm (lock);
 576
 577                 /* a new meter always starts a new bar on the first beat. so
 578                    round the start time appropriately. remember that
 579                    `where' is based on the existing tempo map, not
 580                    the result after we insert the new meter.
 581
 582                 */
 583
 584                 if (where.beats != 1) {
 585                         where.beats = 1;
 586                         where.bars++;
 587                 }
 588
 589                 /* new meters *always* start on a beat. */
 590                 where.ticks = 0;
 591
 592                 do_insert (new MeterSection (where, meter.divisions_per_bar(), meter.note_divisor()));
 593                 recompute_map (true);
 594         }
 595
 596
 597 #ifndef NDEBUG
 598         if (DEBUG_ENABLED(DEBUG::TempoMap)) {
 599                 dump (std::cerr);
 600         }
 601 #endif
 602
 603         PropertyChanged (PropertyChange ());
 604 }
 605
 606 void
 607 TempoMap::change_initial_tempo (double beats_per_minute, double note_type)
 608 {
 609         Tempo newtempo (beats_per_minute, note_type);
 610         TempoSection* t;
 611
 612         for (Metrics::iterator i = metrics.begin(); i != metrics.end(); ++i) {
 613                 if ((t = dynamic_cast<TempoSection*> (*i)) != 0) {
 614                         {
 615                                 Glib::Threads::RWLock::WriterLock lm (lock);
 616                                 *((Tempo*) t) = newtempo;
 617                                 recompute_map (false);
 618                         }
 619                         PropertyChanged (PropertyChange ());
 620                         break;
 621                 }
 622         }
 623 }
 624
 625 void
 626 TempoMap::change_existing_tempo_at (framepos_t where, double beats_per_minute, double note_type)
 627 {
 628         Tempo newtempo (beats_per_minute, note_type);
 629
 630         TempoSection* prev;
 631         TempoSection* first;
 632         Metrics::iterator i;
 633
 634         /* find the TempoSection immediately preceding "where"
 635          */
 636
 637         for (first = 0, i = metrics.begin(), prev = 0; i != metrics.end(); ++i) {
 638
 639                 if ((*i)->frame() > where) {
 640                         break;
 641                 }
 642
 643                 TempoSection* t;
 644
 645                 if ((t = dynamic_cast<TempoSection*>(*i)) != 0) {
 646                         if (!first) {
 647                                 first = t;
 648                         }
 649                         prev = t;
 650                 }
 651         }
 652
 653         if (!prev) {
 654                 if (!first) {
 655                         error << string_compose (_("no tempo sections defined in tempo map - cannot change tempo @ %1"), where) << endmsg;
 656                         return;
 657                 }
 658
 659                 prev = first;
 660         }
 661
 662         /* reset */
 663
 664         {
 665                 Glib::Threads::RWLock::WriterLock lm (lock);
 666                 /* cannot move the first tempo section */
 667                 *((Tempo*)prev) = newtempo;
 668                 recompute_map (false);
 669         }
 670
 671         PropertyChanged (PropertyChange ());
 672 }
 673
 674 const MeterSection&
 675 TempoMap::first_meter () const
 676 {
 677         const MeterSection *m = 0;
 678
 679         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
 680                 if ((m = dynamic_cast<const MeterSection *> (*i)) != 0) {
 681                         return *m;
 682                 }
 683         }
 684
 685         fatal << _("programming error: no tempo section in tempo map!") << endmsg;
 686         /*NOTREACHED*/
 687         return *m;
 688 }
 689
 690 const TempoSection&
 691 TempoMap::first_tempo () const
 692 {
 693         const TempoSection *t = 0;
 694
 695         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
 696                 if ((t = dynamic_cast<const TempoSection *> (*i)) != 0) {
 697                         return *t;
 698                 }
 699         }
 700
 701         fatal << _("programming error: no tempo section in tempo map!") << endmsg;
 702         /*NOTREACHED*/
 703         return *t;
 704 }
 705
 706 void
 707 TempoMap::require_map_to (framepos_t pos)
 708 {
 709         Glib::Threads::RWLock::WriterLock lm (lock);
 710
 711         if (_map.empty() || _map.back().frame < pos) {
 712                 extend_map (pos);
 713         }
 714 }
 715
 716 void
 717 TempoMap::require_map_to (const BBT_Time& bbt)
 718 {
 719         Glib::Threads::RWLock::WriterLock lm (lock);
 720
 721         /* since we have no idea where BBT is if its off the map, see the last
 722          * point in the map is past BBT, and if not add an arbitrary amount of
 723          * time until it is.
 724          */
 725
 726         int additional_minutes = 1;
 727
 728         while (1) {
 729                 if (!_map.empty() && _map.back().bar >= (bbt.bars + 1)) {
 730                         break;
 731                 }
 732                 /* add some more distance, using bigger steps each time */
 733                 extend_map (_map.back().frame + (_frame_rate * 60 * additional_minutes));
 734                 additional_minutes *= 2;
 735         }
 736 }
 737
 738 void
 739 TempoMap::recompute_map (bool reassign_tempo_bbt, framepos_t end)
 740 {
 741         /* CALLER MUST HOLD WRITE LOCK */
 742
 743         MeterSection* meter = 0;
 744         TempoSection* tempo = 0;
 745         double current_frame;
 746         BBT_Time current;
 747         Metrics::iterator next_metric;
 748
 749         if (end < 0) {
 750
 751                 /* we will actually stop once we hit
 752                    the last metric.
 753                 */
 754                 end = max_framepos;
 755
 756         } else {
 757                 if (!_map.empty ()) {
 758                         /* never allow the map to be shortened */
 759                         end = max (end, _map.back().frame);
 760                 }
 761         }
 762
 763         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("recomputing tempo map, zero to %1\n", end));
 764
 765         for (Metrics::iterator i = metrics.begin(); i != metrics.end(); ++i) {
 766                 MeterSection* ms;
 767
 768                 if ((ms = dynamic_cast<MeterSection *> (*i)) != 0) {
 769                         meter = ms;
 770                         break;
 771                 }
 772         }
 773
 774         for (Metrics::iterator i = metrics.begin(); i != metrics.end(); ++i) {
 775                 TempoSection* ts;
 776
 777                 if ((ts = dynamic_cast<TempoSection *> (*i)) != 0) {
 778                         tempo = ts;
 779                         break;
 780                 }
 781         }
 782
 783         /* assumes that the first meter & tempo are at frame zero */
 784         current_frame = 0;
 785         meter->set_frame (0);
 786         tempo->set_frame (0);
 787
 788         /* assumes that the first meter & tempo are at 1|1|0 */
 789         current.bars = 1;
 790         current.beats = 1;
 791         current.ticks = 0;
 792
 793         if (reassign_tempo_bbt) {
 794
 795                 MeterSection* rmeter = meter;
 796
 797                 DEBUG_TRACE (DEBUG::TempoMath, "\tUpdating tempo marks BBT time from bar offset\n");
 798
 799                 for (Metrics::iterator i = metrics.begin(); i != metrics.end(); ++i) {
 800
 801                         TempoSection* ts;
 802                         MeterSection* ms;
 803
 804                         if ((ts = dynamic_cast<TempoSection*>(*i)) != 0) {
 805
 806                                 /* reassign the BBT time of this tempo section
 807                                  * based on its bar offset position.
 808                                  */
 809
 810                                 ts->update_bbt_time_from_bar_offset (*rmeter);
 811
 812                         } else if ((ms = dynamic_cast<MeterSection*>(*i)) != 0) {
 813                                 rmeter = ms;
 814                         } else {
 815                                 fatal << _("programming error: unhandled MetricSection type") << endmsg;
 816                                 /*NOTREACHED*/
 817                         }
 818                 }
 819         }
 820
 821         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("start with meter = %1 tempo = %2\n", *((Meter*)meter), *((Tempo*)tempo)));
 822
 823         next_metric = metrics.begin();
 824         ++next_metric; // skip meter (or tempo)
 825         ++next_metric; // skip tempo (or meter)
 826
 827         _map.clear ();
 828
 829         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Add first bar at 1|1 @ %2\n", current.bars, current_frame));
 830         _map.push_back (BBTPoint (*meter, *tempo,(framepos_t) llrint(current_frame), 1, 1));
 831
 832         if (end == 0) {
 833                 /* silly call from Session::process() during startup
 834                  */
 835                 return;
 836         }
 837
 838         _extend_map (tempo, meter, next_metric, current, current_frame, end);
 839 }
 840
 841 void
 842 TempoMap::extend_map (framepos_t end)
 843 {
 844         /* CALLER MUST HOLD WRITE LOCK */
 845
 846         if (_map.empty()) {
 847                 recompute_map (false, end);
 848                 return;
 849         }
 850
 851         BBTPointList::const_iterator i = _map.end();
 852         Metrics::iterator next_metric;
 853
 854         --i;
 855
 856         BBT_Time last_metric_start;
 857
 858         if ((*i).tempo->frame() > (*i).meter->frame()) {
 859                 last_metric_start = (*i).tempo->start();
 860         } else {
 861                 last_metric_start = (*i).meter->start();
 862         }
 863
 864         /* find the metric immediately after the tempo + meter sections for the
 865          * last point in the map
 866          */
 867
 868         for (next_metric = metrics.begin(); next_metric != metrics.end(); ++next_metric) {
 869                 if ((*next_metric)->start() > last_metric_start) {
 870                         break;
 871                 }
 872         }
 873
 874         /* we cast away const here because this is the one place where we need
 875          * to actually modify the frame time of each metric section.
 876          */
 877
 878         _extend_map (const_cast<TempoSection*> ((*i).tempo),
 879                      const_cast<MeterSection*> ((*i).meter),
 880                      next_metric, BBT_Time ((*i).bar, (*i).beat, 0), (*i).frame, end);
 881 }
 882
 883 void
 884 TempoMap::_extend_map (TempoSection* tempo, MeterSection* meter,
 885                        Metrics::iterator next_metric,
 886                        BBT_Time current, framepos_t current_frame, framepos_t end)
 887 {
 888         /* CALLER MUST HOLD WRITE LOCK */
 889
 890         TempoSection* ts;
 891         MeterSection* ms;
 892         double beat_frames;
 893         framepos_t bar_start_frame;
 894
 895         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Extend map to %1 from %2 = %3\n", end, current, current_frame));
 896
 897         if (current.beats == 1) {
 898                 bar_start_frame = current_frame;
 899         } else {
 900                 bar_start_frame = 0;
 901         }
 902
 903         beat_frames = meter->frames_per_grid (*tempo,_frame_rate);
 904
 905         while (current_frame < end) {
 906
 907                 current.beats++;
 908                 current_frame += beat_frames;
 909
 910                 if (current.beats > meter->divisions_per_bar()) {
 911                         current.bars++;
 912                         current.beats = 1;
 913                 }
 914
 915                 if (next_metric != metrics.end()) {
 916
 917                         /* no operator >= so invert operator < */
 918
 919                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("now at %1 next metric @ %2\n", current, (*next_metric)->start()));
 920
 921                         if (!(current < (*next_metric)->start())) {
 922
 923                           set_metrics:
 924                                 if (((ts = dynamic_cast<TempoSection*> (*next_metric)) != 0)) {
 925
 926                                         tempo = ts;
 927
 928                                         /* new tempo section: if its on a beat,
 929                                          * we don't have to do anything other
 930                                          * than recompute various distances,
 931                                          * done further below as we transition
 932                                          * the next metric section.
 933                                          *
 934                                          * if its not on the beat, we have to
 935                                          * compute the duration of the beat it
 936                                          * is within, which will be different
 937                                          * from the preceding following ones
 938                                          * since it takes part of its duration
 939                                          * from the preceding tempo and part
 940                                          * from this new tempo.
 941                                          */
 942
 943                                         if (tempo->start().ticks != 0) {
 944
 945                                                 double next_beat_frames = tempo->frames_per_beat (_frame_rate);
 946
 947                                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("bumped into non-beat-aligned tempo metric at %1 = %2, adjust next beat using %3\n",
 948                                                                                                tempo->start(), current_frame, tempo->bar_offset()));
 949
 950                                                 /* back up to previous beat */
 951                                                 current_frame -= beat_frames;
 952
 953                                                 /* set tempo section location
 954                                                  * based on offset from last
 955                                                  * bar start
 956                                                  */
 957                                                 tempo->set_frame (bar_start_frame +
 958                                                                   llrint ((ts->bar_offset() * meter->divisions_per_bar() * beat_frames)));
 959
 960                                                 /* advance to the location of
 961                                                  * the new (adjusted) beat. do
 962                                                  * this by figuring out the
 963                                                  * offset within the beat that
 964                                                  * would have been there
 965                                                  * without the tempo
 966                                                  * change. then stretch the
 967                                                  * beat accordingly.
 968                                                  */
 969
 970                                                 double offset_within_old_beat = (tempo->frame() - current_frame) / beat_frames;
 971
 972                                                 current_frame += (offset_within_old_beat * beat_frames) + ((1.0 - offset_within_old_beat) * next_beat_frames);
 973
 974                                                 /* next metric doesn't have to
 975                                                  * match this precisely to
 976                                                  * merit a reloop ...
 977                                                  */
 978                                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Adjusted last beat to %1\n", current_frame));
 979
 980                                         } else {
 981
 982                                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("bumped into beat-aligned tempo metric at %1 = %2\n",
 983                                                                                                tempo->start(), current_frame));
 984                                                 tempo->set_frame (current_frame);
 985                                         }
 986
 987                                 } else if ((ms = dynamic_cast<MeterSection*>(*next_metric)) != 0) {
 988
 989                                         meter = ms;
 990
 991                                         /* new meter section: always defines the
 992                                          * start of a bar.
 993                                          */
 994
 995                                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("bumped into meter section at %1 vs %2 (%3)\n",
 996                                                                                        meter->start(), current, current_frame));
 997
 998                                         assert (current.beats == 1);
 999
1000                                         meter->set_frame (current_frame);
1001                                 }
1002
1003                                 beat_frames = meter->frames_per_grid (*tempo, _frame_rate);
1004
1005                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("New metric with beat frames = %1 dpb %2 meter %3 tempo %4\n",
1006                                                                                beat_frames, meter->divisions_per_bar(), *((Meter*)meter), *((Tempo*)tempo)));
1007
1008                                 ++next_metric;
1009
1010                                 if (next_metric != metrics.end() && ((*next_metric)->start() == current)) {
1011                                         /* same position so go back and set this one up before advancing
1012                                         */
1013                                         goto set_metrics;
1014                                 }
1015
1016                         }
1017                 }
1018
1019                 if (current.beats == 1) {
1020                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Add Bar at %1|1 @ %2\n", current.bars, current_frame));
1021                         _map.push_back (BBTPoint (*meter, *tempo,(framepos_t) llrint(current_frame), current.bars, 1));
1022                         bar_start_frame = current_frame;
1023                 } else {
1024                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Add Beat at %1|%2 @ %3\n", current.bars, current.beats, current_frame));
1025                         _map.push_back (BBTPoint (*meter, *tempo, (framepos_t) llrint(current_frame), current.bars, current.beats));
1026                 }
1027
1028                 if (next_metric == metrics.end()) {
1029                         /* no more metrics - we've timestamped them all, stop here */
1030                         if (end == max_framepos) {
1031                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("stop extending map now that we've reach the end @ %1|%2 = %3\n",
1032                                                                                current.bars, current.beats, current_frame));
1033                                 break;
1034                         }
1035                 }
1036         }
1037 }
1038
1039 TempoMetric
1040 TempoMap::metric_at (framepos_t frame) const
1041 {
1042         Glib::Threads::RWLock::ReaderLock lm (lock);
1043         TempoMetric m (first_meter(), first_tempo());
1044         const Meter* meter;
1045         const Tempo* tempo;
1046
1047         /* at this point, we are *guaranteed* to have m.meter and m.tempo pointing
1048            at something, because we insert the default tempo and meter during
1049            TempoMap construction.
1050
1051            now see if we can find better candidates.
1052         */
1053
1054         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1055
1056                 if ((*i)->frame() > frame) {
1057                         break;
1058                 }
1059
1060                 if ((tempo = dynamic_cast<const TempoSection*>(*i)) != 0) {
1061                         m.set_tempo (*tempo);
1062                 } else if ((meter = dynamic_cast<const MeterSection*>(*i)) != 0) {
1063                         m.set_meter (*meter);
1064                 }
1065
1066                 m.set_frame ((*i)->frame ());
1067                 m.set_start ((*i)->start ());
1068         }
1069
1070         return m;
1071 }
1072
1073 TempoMetric
1074 TempoMap::metric_at (BBT_Time bbt) const
1075 {
1076         Glib::Threads::RWLock::ReaderLock lm (lock);
1077         TempoMetric m (first_meter(), first_tempo());
1078         const Meter* meter;
1079         const Tempo* tempo;
1080
1081         /* at this point, we are *guaranteed* to have m.meter and m.tempo pointing
1082            at something, because we insert the default tempo and meter during
1083            TempoMap construction.
1084
1085            now see if we can find better candidates.
1086         */
1087
1088         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1089
1090                 BBT_Time section_start ((*i)->start());
1091
1092                 if (section_start.bars > bbt.bars || (section_start.bars == bbt.bars && section_start.beats > bbt.beats)) {
1093                         break;
1094                 }
1095
1096                 if ((tempo = dynamic_cast<const TempoSection*>(*i)) != 0) {
1097                         m.set_tempo (*tempo);
1098                 } else if ((meter = dynamic_cast<const MeterSection*>(*i)) != 0) {
1099                         m.set_meter (*meter);
1100                 }
1101
1102                 m.set_frame ((*i)->frame ());
1103                 m.set_start (section_start);
1104         }
1105
1106         return m;
1107 }
1108
1109 void
1110 TempoMap::bbt_time (framepos_t frame, BBT_Time& bbt)
1111 {
1112         require_map_to (frame);
1113
1114         Glib::Threads::RWLock::ReaderLock lm (lock);
1115
1116         if (frame < 0) {
1117                 bbt.bars = 1;
1118                 bbt.beats = 1;
1119                 bbt.ticks = 0;
1120                 warning << string_compose (_("tempo map asked for BBT time at frame %1\n"), frame) << endmsg;
1121                 return;
1122         }
1123
1124         return bbt_time (frame, bbt, bbt_before_or_at (frame));
1125 }
1126
1127 void
1128 TempoMap::bbt_time_rt (framepos_t frame, BBT_Time& bbt)
1129 {
1130         Glib::Threads::RWLock::ReaderLock lm (lock, Glib::Threads::TRY_LOCK);
1131
1132         if (!lm.locked()) {
1133                 throw std::logic_error ("TempoMap::bbt_time_rt() could not lock tempo map");
1134         }
1135
1136         if (_map.empty() || _map.back().frame < frame) {
1137                 throw std::logic_error (string_compose ("map not long enough to reach %1", frame));
1138         }
1139
1140         return bbt_time (frame, bbt, bbt_before_or_at (frame));
1141 }
1142
1143 void
1144 TempoMap::bbt_time (framepos_t frame, BBT_Time& bbt, const BBTPointList::const_iterator& i)
1145 {
1146         /* CALLER MUST HOLD READ LOCK */
1147
1148         bbt.bars = (*i).bar;
1149         bbt.beats = (*i).beat;
1150
1151         if ((*i).frame == frame) {
1152                 bbt.ticks = 0;
1153         } else {
1154                 bbt.ticks = llrint (((frame - (*i).frame) / (*i).tempo->frames_per_beat(_frame_rate)) *
1155                                     BBT_Time::ticks_per_beat);
1156         }
1157 }
1158
1159 framepos_t
1160 TempoMap::frame_time (const BBT_Time& bbt)
1161 {
1162         if (bbt.bars < 1) {
1163                 warning << string_compose (_("tempo map asked for frame time at bar < 1  (%1)\n"), bbt) << endmsg;
1164                 return 0;
1165         }
1166
1167         if (bbt.beats < 1) {
1168                 throw std::logic_error ("beats are counted from one");
1169         }
1170
1171         require_map_to (bbt);
1172
1173         Glib::Threads::RWLock::ReaderLock lm (lock);
1174
1175         BBTPointList::const_iterator s = bbt_before_or_at (BBT_Time (1, 1, 0));
1176         BBTPointList::const_iterator e = bbt_before_or_at (BBT_Time (bbt.bars, bbt.beats, 0));
1177
1178         if (bbt.ticks != 0) {
1179                 return ((*e).frame - (*s).frame) +
1180                         llrint ((*e).tempo->frames_per_beat (_frame_rate) * (bbt.ticks/BBT_Time::ticks_per_beat));
1181         } else {
1182                 return ((*e).frame - (*s).frame);
1183         }
1184 }
1185
1186 framecnt_t
1187 TempoMap::bbt_duration_at (framepos_t pos, const BBT_Time& bbt, int dir)
1188 {
1189         BBT_Time when;
1190         bbt_time (pos, when);
1191
1192         Glib::Threads::RWLock::ReaderLock lm (lock);
1193         return bbt_duration_at_unlocked (when, bbt, dir);
1194 }
1195
1196 framecnt_t
1197 TempoMap::bbt_duration_at_unlocked (const BBT_Time& when, const BBT_Time& bbt, int /*dir*/)
1198 {
1199         if (bbt.bars == 0 && bbt.beats == 0 && bbt.ticks == 0) {
1200                 return 0;
1201         }
1202
1203         /* round back to the previous precise beat */
1204         BBTPointList::const_iterator wi = bbt_before_or_at (BBT_Time (when.bars, when.beats, 0));
1205         BBTPointList::const_iterator start (wi);
1206         double tick_frames = 0;
1207
1208         assert (wi != _map.end());
1209
1210         /* compute how much rounding we did because of non-zero ticks */
1211
1212         if (when.ticks != 0) {
1213                 tick_frames = (*wi).tempo->frames_per_beat (_frame_rate) * (when.ticks/BBT_Time::ticks_per_beat);
1214         }
1215
1216         uint32_t bars = 0;
1217         uint32_t beats = 0;
1218
1219         while (wi != _map.end() && bars < bbt.bars) {
1220                 ++wi;
1221                 if ((*wi).is_bar()) {
1222                         ++bars;
1223                 }
1224         }
1225         assert (wi != _map.end());
1226
1227         while (wi != _map.end() && beats < bbt.beats) {
1228                 ++wi;
1229                 ++beats;
1230         }
1231         assert (wi != _map.end());
1232
1233         /* add any additional frames related to ticks in the added value */
1234
1235         if (bbt.ticks != 0) {
1236                 tick_frames += (*wi).tempo->frames_per_beat (_frame_rate) * (bbt.ticks/BBT_Time::ticks_per_beat);
1237         }
1238
1239         return ((*wi).frame - (*start).frame) + llrint (tick_frames);
1240 }
1241
1242 framepos_t
1243 TempoMap::round_to_bar (framepos_t fr, int dir)
1244 {
1245         return round_to_type (fr, dir, Bar);
1246 }
1247
1248 framepos_t
1249 TempoMap::round_to_beat (framepos_t fr, int dir)
1250 {
1251         return round_to_type (fr, dir, Beat);
1252 }
1253
1254 framepos_t
1255 TempoMap::round_to_beat_subdivision (framepos_t fr, int sub_num, int dir)
1256 {
1257         require_map_to (fr);
1258
1259         Glib::Threads::RWLock::ReaderLock lm (lock);
1260         BBTPointList::const_iterator i = bbt_before_or_at (fr);
1261         BBT_Time the_beat;
1262         uint32_t ticks_one_subdivisions_worth;
1263         uint32_t difference;
1264
1265         bbt_time (fr, the_beat, i);
1266
1267         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("round %1 to nearest 1/%2 beat, before-or-at = %3 @ %4|%5 precise = %6\n",
1268                                                      fr, sub_num, (*i).frame, (*i).bar, (*i).beat, the_beat));
1269
1270         ticks_one_subdivisions_worth = (uint32_t)BBT_Time::ticks_per_beat / sub_num;
1271
1272         if (dir > 0) {
1273
1274                 /* round to next (even if we're on a subdivision */
1275
1276                 uint32_t mod = the_beat.ticks % ticks_one_subdivisions_worth;
1277
1278                 if (mod == 0) {
1279                         /* right on the subdivision, so the difference is just the subdivision ticks */
1280                         the_beat.ticks += ticks_one_subdivisions_worth;
1281
1282                 } else {
1283                         /* not on subdivision, compute distance to next subdivision */
1284
1285                         the_beat.ticks += ticks_one_subdivisions_worth - mod;
1286                 }
1287
1288                 if (the_beat.ticks > BBT_Time::ticks_per_beat) {
1289                         assert (i != _map.end());
1290                         ++i;
1291                         assert (i != _map.end());
1292                         the_beat.ticks -= BBT_Time::ticks_per_beat;
1293                 }
1294
1295
1296         } else if (dir < 0) {
1297
1298                 /* round to previous (even if we're on a subdivision) */
1299
1300                 uint32_t mod = the_beat.ticks % ticks_one_subdivisions_worth;
1301
1302                 if (mod == 0) {
1303                         /* right on the subdivision, so the difference is just the subdivision ticks */
1304                         difference = ticks_one_subdivisions_worth;
1305                 } else {
1306                         /* not on subdivision, compute distance to previous subdivision, which
1307                            is just the modulus.
1308                         */
1309
1310                         difference = mod;
1311                 }
1312
1313                 if (the_beat.ticks < difference) {
1314                         if (i == _map.begin()) {
1315                                 /* can't go backwards from wherever pos is, so just return it */
1316                                 return fr;
1317                         }
1318                         --i;
1319                         the_beat.ticks = BBT_Time::ticks_per_beat - the_beat.ticks;
1320                 } else {
1321                         the_beat.ticks -= difference;
1322                 }
1323
1324         } else {
1325                 /* round to nearest */
1326
1327                 double rem;
1328
1329                 /* compute the distance to the previous and next subdivision */
1330
1331                 if ((rem = fmod ((double) the_beat.ticks, (double) ticks_one_subdivisions_worth)) > ticks_one_subdivisions_worth/2.0) {
1332
1333                         /* closer to the next subdivision, so shift forward */
1334
1335                         the_beat.ticks = lrint (the_beat.ticks + (ticks_one_subdivisions_worth - rem));
1336
1337                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("moved forward to %1\n", the_beat.ticks));
1338
1339                         if (the_beat.ticks > BBT_Time::ticks_per_beat) {
1340                                 assert (i != _map.end());
1341                                 ++i;
1342                                 assert (i != _map.end());
1343                                 the_beat.ticks -= BBT_Time::ticks_per_beat;
1344                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("fold beat to %1\n", the_beat));
1345                         }
1346
1347                 } else if (rem > 0) {
1348
1349                         /* closer to previous subdivision, so shift backward */
1350
1351                         if (rem > the_beat.ticks) {
1352                                 if (i == _map.begin()) {
1353                                         /* can't go backwards past zero, so ... */
1354                                         return 0;
1355                                 }
1356                                 /* step back to previous beat */
1357                                 --i;
1358                                 the_beat.ticks = lrint (BBT_Time::ticks_per_beat - rem);
1359                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("step back beat to %1\n", the_beat));
1360                         } else {
1361                                 the_beat.ticks = lrint (the_beat.ticks - rem);
1362                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("moved backward to %1\n", the_beat.ticks));
1363                         }
1364                 } else {
1365                         /* on the subdivision, do nothing */
1366                 }
1367         }
1368
1369         return (*i).frame + (the_beat.ticks/BBT_Time::ticks_per_beat) *
1370                 (*i).tempo->frames_per_beat (_frame_rate);
1371 }
1372
1373 framepos_t
1374 TempoMap::round_to_type (framepos_t frame, int dir, BBTPointType type)
1375 {
1376         require_map_to (frame);
1377
1378         Glib::Threads::RWLock::ReaderLock lm (lock);
1379         BBTPointList::const_iterator fi;
1380
1381         if (dir > 0) {
1382                 fi = bbt_after_or_at (frame);
1383         } else {
1384                 fi = bbt_before_or_at (frame);
1385         }
1386
1387         assert (fi != _map.end());
1388
1389         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("round from %1 (%3|%4 @ %5) to %6 in direction %2\n", frame, dir, (*fi).bar, (*fi).beat, (*fi).frame,
1390                                                      (type == Bar ? "bar" : "beat")));
1391
1392         switch (type) {
1393         case Bar:
1394                 if (dir < 0) {
1395                         /* find bar previous to 'frame' */
1396
1397                         if (fi == _map.begin()) {
1398                                 return 0;
1399                         }
1400
1401                         if ((*fi).is_bar() && (*fi).frame == frame) {
1402                                 --fi;
1403                         }
1404
1405                         while (!(*fi).is_bar()) {
1406                                 if (fi == _map.begin()) {
1407                                         break;
1408                                 }
1409                                 fi--;
1410                         }
1411                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("rounded to bar: map iter at %1|%2 %3, return\n",
1412                                                                      (*fi).bar, (*fi).beat, (*fi).frame));
1413                         return (*fi).frame;
1414
1415                 } else if (dir > 0) {
1416
1417                         /* find bar following 'frame' */
1418
1419                         if ((*fi).is_bar() && (*fi).frame == frame) {
1420                                 ++fi;
1421                         }
1422
1423                         while (!(*fi).is_bar()) {
1424                                 fi++;
1425                                 if (fi == _map.end()) {
1426                                         --fi;
1427                                         break;
1428                                 }
1429                         }
1430
1431                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("rounded to bar: map iter at %1|%2 %3, return\n",
1432                                                                      (*fi).bar, (*fi).beat, (*fi).frame));
1433                         return (*fi).frame;
1434
1435                 } else {
1436
1437                         /* true rounding: find nearest bar */
1438
1439                         BBTPointList::const_iterator prev = fi;
1440                         BBTPointList::const_iterator next = fi;
1441
1442                         if ((*fi).frame == frame) {
1443                                 return frame;
1444                         }
1445
1446                         while ((*prev).beat != 1) {
1447                                 if (prev == _map.begin()) {
1448                                         break;
1449                                 }
1450                                 prev--;
1451                         }
1452
1453                         while ((next != _map.end()) && (*next).beat != 1) {
1454                                 next++;
1455                         }
1456
1457                         if ((next == _map.end()) || (frame - (*prev).frame) < ((*next).frame - frame)) {
1458                                 return (*prev).frame;
1459                         } else {
1460                                 return (*next).frame;
1461                         }
1462
1463                 }
1464
1465                 break;
1466
1467         case Beat:
1468                 if (dir < 0) {
1469
1470                         if (fi == _map.begin()) {
1471                                 return 0;
1472                         }
1473
1474                         if ((*fi).frame >= frame) {
1475                                 DEBUG_TRACE (DEBUG::SnapBBT, "requested frame is on beat, step back\n");
1476                                 --fi;
1477                         }
1478                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("rounded to beat: map iter at %1|%2 %3, return\n",
1479                                                                      (*fi).bar, (*fi).beat, (*fi).frame));
1480                         return (*fi).frame;
1481                 } else if (dir > 0) {
1482                         if ((*fi).frame <= frame) {
1483                                 DEBUG_TRACE (DEBUG::SnapBBT, "requested frame is on beat, step forward\n");
1484                                 ++fi;
1485                         }
1486                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("rounded to beat: map iter at %1|%2 %3, return\n",
1487                                                                      (*fi).bar, (*fi).beat, (*fi).frame));
1488                         return (*fi).frame;
1489                 } else {
1490                         /* find beat nearest to frame */
1491                         if ((*fi).frame == frame) {
1492                                 return frame;
1493                         }
1494
1495                         BBTPointList::const_iterator prev = fi;
1496                         BBTPointList::const_iterator next = fi;
1497
1498                         /* fi is already the beat before_or_at frame, and
1499                            we've just established that its not at frame, so its
1500                            the beat before frame.
1501                         */
1502                         ++next;
1503
1504                         if ((next == _map.end()) || (frame - (*prev).frame) < ((*next).frame - frame)) {
1505                                 return (*prev).frame;
1506                         } else {
1507                                 return (*next).frame;
1508                         }
1509                 }
1510                 break;
1511         }
1512
1513         /* NOTREACHED */
1514         assert (false);
1515         return 0;
1516 }
1517
1518 void
1519 TempoMap::get_grid (TempoMap::BBTPointList::const_iterator& begin,
1520                     TempoMap::BBTPointList::const_iterator& end,
1521                     framepos_t lower, framepos_t upper)
1522 {
1523         {
1524                 Glib::Threads::RWLock::WriterLock lm (lock);
1525                 if (_map.empty() || (_map.back().frame < upper)) {
1526                         recompute_map (false, upper);
1527                 }
1528         }
1529
1530         begin = lower_bound (_map.begin(), _map.end(), lower);
1531         end = upper_bound (_map.begin(), _map.end(), upper);
1532 }
1533
1534 const TempoSection&
1535 TempoMap::tempo_section_at (framepos_t frame) const
1536 {
1537         Glib::Threads::RWLock::ReaderLock lm (lock);
1538         Metrics::const_iterator i;
1539         TempoSection* prev = 0;
1540
1541         for (i = metrics.begin(); i != metrics.end(); ++i) {
1542                 TempoSection* t;
1543
1544                 if ((t = dynamic_cast<TempoSection*> (*i)) != 0) {
1545
1546                         if ((*i)->frame() > frame) {
1547                                 break;
1548                         }
1549
1550                         prev = t;
1551                 }
1552         }
1553
1554         if (prev == 0) {
1555                 fatal << endmsg;
1556         }
1557
1558         return *prev;
1559 }
1560
1561 const Tempo&
1562 TempoMap::tempo_at (framepos_t frame) const
1563 {
1564         TempoMetric m (metric_at (frame));
1565         return m.tempo();
1566 }
1567
1568
1569 const Meter&
1570 TempoMap::meter_at (framepos_t frame) const
1571 {
1572         TempoMetric m (metric_at (frame));
1573         return m.meter();
1574 }
1575
1576 XMLNode&
1577 TempoMap::get_state ()
1578 {
1579         Metrics::const_iterator i;
1580         XMLNode *root = new XMLNode ("TempoMap");
1581
1582         {
1583                 Glib::Threads::RWLock::ReaderLock lm (lock);
1584                 for (i = metrics.begin(); i != metrics.end(); ++i) {
1585                         root->add_child_nocopy ((*i)->get_state());
1586                 }
1587         }
1588
1589         return *root;
1590 }
1591
1592 int
1593 TempoMap::set_state (const XMLNode& node, int /*version*/)
1594 {
1595         {
1596                 Glib::Threads::RWLock::WriterLock lm (lock);
1597
1598                 XMLNodeList nlist;
1599                 XMLNodeConstIterator niter;
1600                 Metrics old_metrics (metrics);
1601                 MeterSection* last_meter = 0;
1602                 metrics.clear();
1603
1604                 nlist = node.children();
1605
1606                 for (niter = nlist.begin(); niter != nlist.end(); ++niter) {
1607                         XMLNode* child = *niter;
1608
1609                         if (child->name() == TempoSection::xml_state_node_name) {
1610
1611                                 try {
1612                                         TempoSection* ts = new TempoSection (*child);
1613                                         metrics.push_back (ts);
1614
1615                                         if (ts->bar_offset() < 0.0) {
1616                                                 if (last_meter) {
1617                                                         ts->update_bar_offset_from_bbt (*last_meter);
1618                                                 }
1619                                         }
1620                                 }
1621
1622                                 catch (failed_constructor& err){
1623                                         error << _("Tempo map: could not set new state, restoring old one.") << endmsg;
1624                                         metrics = old_metrics;
1625                                         break;
1626                                 }
1627
1628                         } else if (child->name() == MeterSection::xml_state_node_name) {
1629
1630                                 try {
1631                                         MeterSection* ms = new MeterSection (*child);
1632                                         metrics.push_back (ms);
1633                                         last_meter = ms;
1634                                 }
1635
1636                                 catch (failed_constructor& err) {
1637                                         error << _("Tempo map: could not set new state, restoring old one.") << endmsg;
1638                                         metrics = old_metrics;
1639                                         break;
1640                                 }
1641                         }
1642                 }
1643
1644                 if (niter == nlist.end()) {
1645                         MetricSectionSorter cmp;
1646                         metrics.sort (cmp);
1647                 }
1648
1649                 /* check for multiple tempo/meters at the same location, which
1650                    ardour2 somehow allowed.
1651                 */
1652
1653                 Metrics::iterator prev = metrics.end();
1654                 for (Metrics::iterator i = metrics.begin(); i != metrics.end(); ++i) {
1655                         if (prev != metrics.end()) {
1656                                 if (dynamic_cast<MeterSection*>(*prev) && dynamic_cast<MeterSection*>(*i)) {
1657                                         if ((*prev)->start() == (*i)->start()) {
1658                                                 error << string_compose (_("Multiple meter definitions found at %1"), (*prev)->start()) << endmsg;
1659                                                 return -1;
1660                                         }
1661                                 } else if (dynamic_cast<TempoSection*>(*prev) && dynamic_cast<TempoSection*>(*i)) {
1662                                         if ((*prev)->start() == (*i)->start()) {
1663                                                 error << string_compose (_("Multiple tempo definitions found at %1"), (*prev)->start()) << endmsg;
1664                                                 return -1;
1665                                         }
1666                                 }
1667                         }
1668                         prev = i;
1669                 }
1670
1671                 recompute_map (true, -1);
1672         }
1673
1674         PropertyChanged (PropertyChange ());
1675
1676         return 0;
1677 }
1678
1679 void
1680 TempoMap::dump (std::ostream& o) const
1681 {
1682         Glib::Threads::RWLock::ReaderLock lm (lock, Glib::Threads::TRY_LOCK);
1683         const MeterSection* m;
1684         const TempoSection* t;
1685
1686         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1687
1688                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1689                         o << "Tempo @ " << *i << " (Bar-offset: " << t->bar_offset() << ") " << t->beats_per_minute() << " BPM (pulse = 1/" << t->note_type() << ") at " << t->start() << " frame= " << t->frame() << " (movable? "
1690                           << t->movable() << ')' << endl;
1691                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
1692                         o << "Meter @ " << *i << ' ' << m->divisions_per_bar() << '/' << m->note_divisor() << " at " << m->start() << " frame= " << m->frame()
1693                           << " (movable? " << m->movable() << ')' << endl;
1694                 }
1695         }
1696 }
1697
1698 int
1699 TempoMap::n_tempos() const
1700 {
1701         Glib::Threads::RWLock::ReaderLock lm (lock);
1702         int cnt = 0;
1703
1704         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1705                 if (dynamic_cast<const TempoSection*>(*i) != 0) {
1706                         cnt++;
1707                 }
1708         }
1709
1710         return cnt;
1711 }
1712
1713 int
1714 TempoMap::n_meters() const
1715 {
1716         Glib::Threads::RWLock::ReaderLock lm (lock);
1717         int cnt = 0;
1718
1719         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1720                 if (dynamic_cast<const MeterSection*>(*i) != 0) {
1721                         cnt++;
1722                 }
1723         }
1724
1725         return cnt;
1726 }
1727
1728 void
1729 TempoMap::insert_time (framepos_t where, framecnt_t amount)
1730 {
1731         {
1732                 Glib::Threads::RWLock::WriterLock lm (lock);
1733                 for (Metrics::iterator i = metrics.begin(); i != metrics.end(); ++i) {
1734                         if ((*i)->frame() >= where && (*i)->movable ()) {
1735                                 (*i)->set_frame ((*i)->frame() + amount);
1736                         }
1737                 }
1738
1739                 /* now reset the BBT time of all metrics, based on their new
1740                  * audio time. This is the only place where we do this reverse
1741                  * timestamp.
1742                  */
1743
1744                 Metrics::iterator i;
1745                 const MeterSection* meter;
1746                 const TempoSection* tempo;
1747                 MeterSection *m;
1748                 TempoSection *t;
1749
1750                 meter = &first_meter ();
1751                 tempo = &first_tempo ();
1752
1753                 BBT_Time start;
1754                 BBT_Time end;
1755
1756                 // cerr << "\n###################### TIMESTAMP via AUDIO ##############\n" << endl;
1757
1758                 bool first = true;
1759                 MetricSection* prev = 0;
1760
1761                 for (i = metrics.begin(); i != metrics.end(); ++i) {
1762
1763                         BBT_Time bbt;
1764                         TempoMetric metric (*meter, *tempo);
1765
1766                         if (prev) {
1767                                 metric.set_start (prev->start());
1768                                 metric.set_frame (prev->frame());
1769                         } else {
1770                                 // metric will be at frames=0 bbt=1|1|0 by default
1771                                 // which is correct for our purpose
1772                         }
1773
1774                         BBTPointList::const_iterator bi = bbt_before_or_at ((*i)->frame());
1775                         bbt_time ((*i)->frame(), bbt, bi);
1776
1777                         // cerr << "timestamp @ " << (*i)->frame() << " with " << bbt.bars << "|" << bbt.beats << "|" << bbt.ticks << " => ";
1778
1779                         if (first) {
1780                                 first = false;
1781                         } else {
1782
1783                                 if (bbt.ticks > BBT_Time::ticks_per_beat/2) {
1784                                         /* round up to next beat */
1785                                         bbt.beats += 1;
1786                                 }
1787
1788                                 bbt.ticks = 0;
1789
1790                                 if (bbt.beats != 1) {
1791                                         /* round up to next bar */
1792                                         bbt.bars += 1;
1793                                         bbt.beats = 1;
1794                                 }
1795                         }
1796
1797                         // cerr << bbt << endl;
1798
1799                         (*i)->set_start (bbt);
1800
1801                         if ((t = dynamic_cast<TempoSection*>(*i)) != 0) {
1802                                 tempo = t;
1803                                 // cerr << "NEW TEMPO, frame = " << (*i)->frame() << " start = " << (*i)->start() <<endl;
1804                         } else if ((m = dynamic_cast<MeterSection*>(*i)) != 0) {
1805                                 meter = m;
1806                                 // cerr << "NEW METER, frame = " << (*i)->frame() << " start = " << (*i)->start() <<endl;
1807                         } else {
1808                                 fatal << _("programming error: unhandled MetricSection type") << endmsg;
1809                                 /*NOTREACHED*/
1810                         }
1811
1812                         prev = (*i);
1813                 }
1814
1815                 recompute_map (true);
1816         }
1817
1818
1819         PropertyChanged (PropertyChange ());
1820 }
1821
1822 /** Add some (fractional) beats to a session frame position, and return the result in frames.
1823  *  pos can be -ve, if required.
1824  */
1825 framepos_t
1826 TempoMap::framepos_plus_beats (framepos_t pos, Evoral::MusicalTime beats) const
1827 {
1828         Glib::Threads::RWLock::ReaderLock lm (lock);
1829         Metrics::const_iterator next_tempo;
1830         const TempoSection* tempo = 0;
1831
1832         /* Find the starting tempo metric */
1833
1834         for (next_tempo = metrics.begin(); next_tempo != metrics.end(); ++next_tempo) {
1835
1836                 const TempoSection* t;
1837
1838                 if ((t = dynamic_cast<const TempoSection*>(*next_tempo)) != 0) {
1839
1840                         /* This is a bit of a hack, but pos could be -ve, and if it is,
1841                            we consider the initial metric changes (at time 0) to actually
1842                            be in effect at pos.
1843                         */
1844
1845                         framepos_t f = (*next_tempo)->frame ();
1846
1847                         if (pos < 0 && f == 0) {
1848                                 f = pos;
1849                         }
1850
1851                         if (f > pos) {
1852                                 break;
1853                         }
1854
1855                         tempo = t;
1856                 }
1857         }
1858
1859         /* We now have:
1860
1861            tempo       -> the Tempo for "pos"
1862            next_tempo  -> first tempo after "pos", possibly metrics.end()
1863         */
1864
1865         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("frame %1 plus %2 beats, start with tempo = %3 @ %4\n",
1866                                                        pos, beats, *((Tempo*)tempo), tempo->frame()));
1867
1868         while (beats) {
1869
1870                 /* Distance to the end of this section in frames */
1871                 framecnt_t distance_frames = (next_tempo == metrics.end() ? max_framepos : ((*next_tempo)->frame() - pos));
1872
1873                 /* Distance to the end in beats */
1874                 Evoral::MusicalTime distance_beats = distance_frames / tempo->frames_per_beat (_frame_rate);
1875
1876                 /* Amount to subtract this time */
1877                 double const delta = min (distance_beats, beats);
1878
1879                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("\tdistance to %1 = %2 (%3 beats)\n",
1880                                                                (next_tempo == metrics.end() ? max_framepos : (*next_tempo)->frame()),
1881                                                                distance_frames, distance_beats));
1882
1883                 /* Update */
1884                 beats -= delta;
1885                 pos += delta * tempo->frames_per_beat (_frame_rate);
1886
1887                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("\tnow at %1, %2 beats left\n", pos, beats));
1888
1889                 /* step forwards to next tempo section */
1890
1891                 if (next_tempo != metrics.end()) {
1892
1893                         tempo = dynamic_cast<const TempoSection*>(*next_tempo);
1894
1895                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("\tnew tempo = %1 @ %2 fpb = %3\n",
1896                                                                        *((Tempo*)tempo), tempo->frame(),
1897                                                                        tempo->frames_per_beat (_frame_rate)));
1898
1899                         while (next_tempo != metrics.end ()) {
1900
1901                                 ++next_tempo;
1902
1903                                 if (next_tempo != metrics.end() && dynamic_cast<const TempoSection*>(*next_tempo)) {
1904                                         break;
1905                                 }
1906                         }
1907                 }
1908         }
1909
1910         return pos;
1911 }
1912
1913 /** Subtract some (fractional) beats from a frame position, and return the result in frames */
1914 framepos_t
1915 TempoMap::framepos_minus_beats (framepos_t pos, Evoral::MusicalTime beats) const
1916 {
1917         Glib::Threads::RWLock::ReaderLock lm (lock);
1918         Metrics::const_reverse_iterator prev_tempo;
1919         const TempoSection* tempo = 0;
1920
1921         /* Find the starting tempo metric */
1922
1923         for (prev_tempo = metrics.rbegin(); prev_tempo != metrics.rend(); ++prev_tempo) {
1924
1925                 const TempoSection* t;
1926
1927                 if ((t = dynamic_cast<const TempoSection*>(*prev_tempo)) != 0) {
1928
1929                         /* This is a bit of a hack, but pos could be -ve, and if it is,
1930                            we consider the initial metric changes (at time 0) to actually
1931                            be in effect at pos.
1932                         */
1933
1934                         framepos_t f = (*prev_tempo)->frame ();
1935
1936                         if (pos < 0 && f == 0) {
1937                                 f = pos;
1938                         }
1939
1940                         /* this is slightly more complex than the forward case
1941                            because we reach the tempo in effect at pos after
1942                            passing through pos (rather before, as in the
1943                            forward case). having done that, we then need to
1944                            keep going to get the previous tempo (or
1945                            metrics.rend())
1946                         */
1947
1948                         if (f <= pos) {
1949                                 if (tempo == 0) {
1950                                         /* first tempo with position at or
1951                                            before pos
1952                                         */
1953                                         tempo = t;
1954                                 } else if (f < pos) {
1955                                         /* some other tempo section that
1956                                            is even earlier than 'tempo'
1957                                         */
1958                                         break;
1959                                 }
1960                         }
1961                 }
1962         }
1963
1964         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("frame %1 minus %2 beats, start with tempo = %3 @ %4 prev at beg? %5\n",
1965                                                        pos, beats, *((Tempo*)tempo), tempo->frame(),
1966                                                        prev_tempo == metrics.rend()));
1967
1968         /* We now have:
1969
1970            tempo       -> the Tempo for "pos"
1971            prev_tempo  -> the first metric before "pos", possibly metrics.rend()
1972         */
1973
1974         while (beats) {
1975
1976                 /* Distance to the start of this section in frames */
1977                 framecnt_t distance_frames = (pos - tempo->frame());
1978
1979                 /* Distance to the start in beats */
1980                 Evoral::MusicalTime distance_beats = distance_frames / tempo->frames_per_beat (_frame_rate);
1981
1982                 /* Amount to subtract this time */
1983                 double const sub = min (distance_beats, beats);
1984
1985                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("\tdistance to %1 = %2 (%3 beats)\n",
1986                                                                tempo->frame(), distance_frames, distance_beats));
1987                 /* Update */
1988
1989                 beats -= sub;
1990                 pos -= sub * tempo->frames_per_beat (_frame_rate);
1991
1992                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("\tnow at %1, %2 beats left, prev at end ? %3\n", pos, beats,
1993                                                                (prev_tempo == metrics.rend())));
1994
1995                 /* step backwards to prior TempoSection */
1996
1997                 if (prev_tempo != metrics.rend()) {
1998
1999                         tempo = dynamic_cast<const TempoSection*>(*prev_tempo);
2000
2001                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("\tnew tempo = %1 @ %2 fpb = %3\n",
2002                                                                        *((Tempo*)tempo), tempo->frame(),
2003                                                                        tempo->frames_per_beat (_frame_rate)));
2004
2005                         while (prev_tempo != metrics.rend ()) {
2006
2007                                 ++prev_tempo;
2008
2009                                 if (prev_tempo != metrics.rend() && dynamic_cast<const TempoSection*>(*prev_tempo) != 0) {
2010                                         break;
2011                                 }
2012                         }
2013                 } else {
2014                         pos -= llrint (beats * tempo->frames_per_beat (_frame_rate));
2015                         beats = 0;
2016                 }
2017         }
2018
2019         return pos;
2020 }
2021
2022 /** Add the BBT interval op to pos and return the result */
2023 framepos_t
2024 TempoMap::framepos_plus_bbt (framepos_t pos, BBT_Time op) const
2025 {
2026         Glib::Threads::RWLock::ReaderLock lm (lock);
2027         Metrics::const_iterator i;
2028         const MeterSection* meter;
2029         const MeterSection* m;
2030         const TempoSection* tempo;
2031         const TempoSection* t;
2032         double frames_per_beat;
2033         framepos_t effective_pos = max (pos, (framepos_t) 0);
2034
2035         meter = &first_meter ();
2036         tempo = &first_tempo ();
2037
2038         assert (meter);
2039         assert (tempo);
2040
2041         /* find the starting metrics for tempo & meter */
2042
2043         for (i = metrics.begin(); i != metrics.end(); ++i) {
2044
2045                 if ((*i)->frame() > effective_pos) {
2046                         break;
2047                 }
2048
2049                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
2050                         tempo = t;
2051                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
2052                         meter = m;
2053                 }
2054         }
2055
2056         /* We now have:
2057
2058            meter -> the Meter for "pos"
2059            tempo -> the Tempo for "pos"
2060            i     -> for first new metric after "pos", possibly metrics.end()
2061         */
2062
2063         /* now comes the complicated part. we have to add one beat a time,
2064            checking for a new metric on every beat.
2065         */
2066
2067         frames_per_beat = tempo->frames_per_beat (_frame_rate);
2068
2069         uint64_t bars = 0;
2070
2071         while (op.bars) {
2072
2073                 bars++;
2074                 op.bars--;
2075
2076                 /* check if we need to use a new metric section: has adding frames moved us
2077                    to or after the start of the next metric section? in which case, use it.
2078                 */
2079
2080                 if (i != metrics.end()) {
2081                         if ((*i)->frame() <= pos) {
2082
2083                                 /* about to change tempo or meter, so add the
2084                                  * number of frames for the bars we've just
2085                                  * traversed before we change the
2086                                  * frames_per_beat value.
2087                                  */
2088
2089                                 pos += llrint (frames_per_beat * (bars * meter->divisions_per_bar()));
2090                                 bars = 0;
2091
2092                                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
2093                                         tempo = t;
2094                                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
2095                                         meter = m;
2096                                 }
2097                                 ++i;
2098                                 frames_per_beat = tempo->frames_per_beat (_frame_rate);
2099
2100                         }
2101                 }
2102
2103         }
2104
2105         pos += llrint (frames_per_beat * (bars * meter->divisions_per_bar()));
2106
2107         uint64_t beats = 0;
2108
2109         while (op.beats) {
2110
2111                 /* given the current meter, have we gone past the end of the bar ? */
2112
2113                 beats++;
2114                 op.beats--;
2115
2116                 /* check if we need to use a new metric section: has adding frames moved us
2117                    to or after the start of the next metric section? in which case, use it.
2118                 */
2119
2120                 if (i != metrics.end()) {
2121                         if ((*i)->frame() <= pos) {
2122
2123                                 /* about to change tempo or meter, so add the
2124                                  * number of frames for the beats we've just
2125                                  * traversed before we change the
2126                                  * frames_per_beat value.
2127                                  */
2128
2129                                 pos += llrint (beats * frames_per_beat);
2130                                 beats = 0;
2131
2132                                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
2133                                         tempo = t;
2134                                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
2135                                         meter = m;
2136                                 }
2137                                 ++i;
2138                                 frames_per_beat = tempo->frames_per_beat (_frame_rate);
2139                         }
2140                 }
2141         }
2142
2143         pos += llrint (beats * frames_per_beat);
2144
2145         if (op.ticks) {
2146                 if (op.ticks >= BBT_Time::ticks_per_beat) {
2147                         pos += llrint (frames_per_beat + /* extra beat */
2148                                        (frames_per_beat * ((op.ticks % (uint32_t) BBT_Time::ticks_per_beat) /
2149                                                            (double) BBT_Time::ticks_per_beat)));
2150                 } else {
2151                         pos += llrint (frames_per_beat * (op.ticks / (double) BBT_Time::ticks_per_beat));
2152                 }
2153         }
2154
2155         return pos;
2156 }
2157
2158 /** Count the number of beats that are equivalent to distance when going forward,
2159     starting at pos.
2160 */
2161 Evoral::MusicalTime
2162 TempoMap::framewalk_to_beats (framepos_t pos, framecnt_t distance) const
2163 {
2164         Glib::Threads::RWLock::ReaderLock lm (lock);
2165         Metrics::const_iterator next_tempo;
2166         const TempoSection* tempo = 0;
2167         framepos_t effective_pos = max (pos, (framepos_t) 0);
2168
2169         /* Find the relevant initial tempo metric  */
2170
2171         for (next_tempo = metrics.begin(); next_tempo != metrics.end(); ++next_tempo) {
2172
2173                 const TempoSection* t;
2174
2175                 if ((t = dynamic_cast<const TempoSection*>(*next_tempo)) != 0) {
2176
2177                         if ((*next_tempo)->frame() > effective_pos) {
2178                                 break;
2179                         }
2180
2181                         tempo = t;
2182                 }
2183         }
2184
2185         /* We now have:
2186
2187            tempo -> the Tempo for "pos"
2188            next_tempo -> the next tempo after "pos", possibly metrics.end()
2189         */
2190
2191         assert (tempo);
2192
2193         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("frame %1 walk by %2 frames, start with tempo = %3 @ %4\n",
2194                                                        pos, distance, *((Tempo*)tempo), tempo->frame()));
2195
2196         Evoral::MusicalTime beats = 0;
2197
2198         while (distance) {
2199
2200                 /* End of this section */
2201                 framepos_t end;
2202                 /* Distance to `end' in frames */
2203                 framepos_t distance_to_end;
2204
2205                 if (next_tempo == metrics.end ()) {
2206                         /* We can't do (end - pos) if end is max_framepos, as it will overflow if pos is -ve */
2207                         end = max_framepos;
2208                         distance_to_end = max_framepos;
2209                 } else {
2210                         end = (*next_tempo)->frame ();
2211                         distance_to_end = end - pos;
2212                 }
2213
2214                 /* Amount to subtract this time */
2215                 double const sub = min (distance, distance_to_end);
2216
2217                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("to reach end at %1 (end ? %2), distance= %3 sub=%4\n", end, (next_tempo == metrics.end()),
2218                                                                distance_to_end, sub));
2219
2220                 /* Update */
2221                 pos += sub;
2222                 distance -= sub;
2223                 assert (tempo);
2224                 beats += sub / tempo->frames_per_beat (_frame_rate);
2225
2226                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("now at %1, beats = %2 distance left %3\n",
2227                                                                pos, beats, distance));
2228
2229                 /* Move on if there's anything to move to */
2230
2231                 if (next_tempo != metrics.end()) {
2232
2233                         tempo = dynamic_cast<const TempoSection*>(*next_tempo);
2234
2235                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("\tnew tempo = %1 @ %2 fpb = %3\n",
2236                                                                        *((Tempo*)tempo), tempo->frame(),
2237                                                                        tempo->frames_per_beat (_frame_rate)));
2238
2239                         while (next_tempo != metrics.end ()) {
2240
2241                                 ++next_tempo;
2242
2243                                 if (next_tempo != metrics.end() && dynamic_cast<const TempoSection*>(*next_tempo)) {
2244                                         break;
2245                                 }
2246                         }
2247
2248                         if (next_tempo == metrics.end()) {
2249                                 DEBUG_TRACE (DEBUG::TempoMath, "no more tempo sections\n");
2250                         } else {
2251                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("next tempo section is %1 @ %2\n",
2252                                                                                **next_tempo, (*next_tempo)->frame()));
2253                         }
2254
2255                 }
2256                 assert (tempo);
2257         }
2258
2259         return beats;
2260 }
2261
2262 TempoMap::BBTPointList::const_iterator
2263 TempoMap::bbt_before_or_at (framepos_t pos)
2264 {
2265         /* CALLER MUST HOLD READ LOCK */
2266
2267         BBTPointList::const_iterator i;
2268
2269         if (pos < 0) {
2270                 /* not really correct, but we should catch pos < 0 at a higher
2271                    level
2272                 */
2273                 return _map.begin();
2274         }
2275
2276         i = lower_bound (_map.begin(), _map.end(), pos);
2277         assert (i != _map.end());
2278         if ((*i).frame > pos) {
2279                 assert (i != _map.begin());
2280                 --i;
2281         }
2282         return i;
2283 }
2284
2285 struct bbtcmp {
2286     bool operator() (const BBT_Time& a, const BBT_Time& b) {
2287             return a < b;
2288     }
2289 };
2290
2291 TempoMap::BBTPointList::const_iterator
2292 TempoMap::bbt_before_or_at (const BBT_Time& bbt)
2293 {
2294         BBTPointList::const_iterator i;
2295         bbtcmp cmp;
2296
2297         i = lower_bound (_map.begin(), _map.end(), bbt, cmp);
2298         assert (i != _map.end());
2299         if ((*i).bar > bbt.bars || (*i).beat > bbt.beats) {
2300                 assert (i != _map.begin());
2301                 --i;
2302         }
2303         return i;
2304 }
2305
2306 TempoMap::BBTPointList::const_iterator
2307 TempoMap::bbt_after_or_at (framepos_t pos)
2308 {
2309         /* CALLER MUST HOLD READ LOCK */
2310
2311         BBTPointList::const_iterator i;
2312
2313         if (_map.back().frame == pos) {
2314                 i = _map.end();
2315                 assert (i != _map.begin());
2316                 --i;
2317                 return i;
2318         }
2319
2320         i = upper_bound (_map.begin(), _map.end(), pos);
2321         assert (i != _map.end());
2322         return i;
2323 }
2324
2325 std::ostream&
2326 operator<< (std::ostream& o, const Meter& m) {
2327         return o << m.divisions_per_bar() << '/' << m.note_divisor();
2328 }
2329
2330 std::ostream&
2331 operator<< (std::ostream& o, const Tempo& t) {
2332         return o << t.beats_per_minute() << " 1/" << t.note_type() << "'s per minute";
2333 }
2334
2335 std::ostream&
2336 operator<< (std::ostream& o, const MetricSection& section) {
2337
2338         o << "MetricSection @ " << section.frame() << " aka " << section.start() << ' ';
2339
2340         const TempoSection* ts;
2341         const MeterSection* ms;
2342
2343         if ((ts = dynamic_cast<const TempoSection*> (&section)) != 0) {
2344                 o << *((Tempo*) ts);
2345         } else if ((ms = dynamic_cast<const MeterSection*> (&section)) != 0) {
2346                 o << *((Meter*) ms);
2347         }
2348
2349         return o;
2350 }