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