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         double divisions_per_bar;
 780         double beat_frames;
 781         double current_frame;
 782         BBT_Time current;
 783         Metrics::iterator next_metric;
 784
 785         if (end < 0) {
 786                 if (_map.empty()) {
 787                         /* compute 1 mins worth */
 788                         end = _frame_rate * 60;
 789                 } else {
 790                         end = _map.back().frame;
 791                 }
 792         }
 793
 794         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("recomputing tempo map, zero to %1\n", end));
 795
 796         _map.clear ();
 797
 798         for (Metrics::iterator i = metrics->begin(); i != metrics->end(); ++i) {
 799                 if ((ms = dynamic_cast<MeterSection *> (*i)) != 0) {
 800                         meter = ms;
 801                         break;
 802                 }
 803         }
 804
 805         for (Metrics::iterator i = metrics->begin(); i != metrics->end(); ++i) {
 806                 if ((ts = dynamic_cast<TempoSection *> (*i)) != 0) {
 807                         tempo = ts;
 808                         break;
 809                 }
 810         }
 811
 812         /* assumes that the first meter & tempo are at frame zero */
 813         current_frame = 0;
 814         meter->set_frame (0);
 815         tempo->set_frame (0);
 816
 817         /* assumes that the first meter & tempo are at 1|1|0 */
 818         current.bars = 1;
 819         current.beats = 1;
 820         current.ticks = 0;
 821
 822         divisions_per_bar = meter->divisions_per_bar ();
 823         beat_frames = meter->frames_per_division (*tempo,_frame_rate);
 824
 825         if (reassign_tempo_bbt) {
 826
 827                 MeterSection* rmeter = meter;
 828
 829                 DEBUG_TRACE (DEBUG::TempoMath, "\tUpdating tempo marks BBT time from bar offset\n");
 830
 831                 for (Metrics::iterator i = metrics->begin(); i != metrics->end(); ++i) {
 832
 833                         if ((ts = dynamic_cast<TempoSection*>(*i)) != 0) {
 834
 835                                 /* reassign the BBT time of this tempo section
 836                                  * based on its bar offset position.
 837                                  */
 838
 839                                 ts->update_bbt_time_from_bar_offset (*rmeter);
 840
 841                         } else if ((ms = dynamic_cast<MeterSection*>(*i)) != 0) {
 842                                 rmeter = ms;
 843                         } else {
 844                                 fatal << _("programming error: unhandled MetricSection type") << endmsg;
 845                                 /*NOTREACHED*/
 846                         }
 847                 }
 848         }
 849
 850         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("start with meter = %1 tempo = %2 dpb %3 fpb %4\n",
 851                                                        *((Meter*)meter), *((Tempo*)tempo), divisions_per_bar, beat_frames));
 852
 853         next_metric = metrics->begin();
 854         ++next_metric; // skip meter (or tempo)
 855         ++next_metric; // skip tempo (or meter)
 856
 857         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Add first bar at 1|1 @ %2\n", current.bars, current_frame));
 858         _map.push_back (BBTPoint (*meter, *tempo,(framepos_t) llrint(current_frame), 1, 1));
 859
 860         while (current_frame < end) {
 861
 862                 current.beats++;
 863                 current_frame += beat_frames;
 864
 865                 if (current.beats > meter->divisions_per_bar()) {
 866                         current.bars++;
 867                         current.beats = 1;
 868                 }
 869
 870                 if (next_metric != metrics->end()) {
 871
 872                         /* no operator >= so invert operator < */
 873
 874                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("now at %1 next metric @ %2\n", current, (*next_metric)->start()));
 875
 876                         if (!(current < (*next_metric)->start())) {
 877
 878                           set_metrics:
 879                                 if (((ts = dynamic_cast<TempoSection*> (*next_metric)) != 0)) {
 880
 881                                         tempo = ts;
 882
 883                                         /* new tempo section: if its on a beat,
 884                                          * we don't have to do anything other
 885                                          * than recompute various distances,
 886                                          * done further below as we transition
 887                                          * the next metric section.
 888                                          *
 889                                          * if its not on the beat, we have to
 890                                          * compute the duration of the beat it
 891                                          * is within, which will be different
 892                                          * from the preceding following ones
 893                                          * since it takes part of its duration
 894                                          * from the preceding tempo and part
 895                                          * from this new tempo.
 896                                          */
 897
 898                                         if (tempo->start().ticks != 0) {
 899
 900                                                 double next_beat_frames = meter->frames_per_division (*tempo,_frame_rate);
 901
 902                                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("bumped into non-beat-aligned tempo metric at %1 = %2, adjust next beat using %3\n",
 903                                                                                                tempo->start(), current_frame, tempo->bar_offset()));
 904
 905                                                 /* back up to previous beat */
 906                                                 current_frame -= beat_frames;
 907                                                 /* set tempo section location based on offset from last beat */
 908                                                 tempo->set_frame (current_frame + (ts->bar_offset() * beat_frames));
 909                                                 /* advance to the location of the new (adjusted) beat */
 910                                                 current_frame += (ts->bar_offset() * beat_frames) + ((1.0 - ts->bar_offset()) * next_beat_frames);
 911                                                 /* next metric doesn't have to
 912                                                  * match this precisely to
 913                                                  * merit a reloop ...
 914                                                  */
 915                                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Adjusted last beat to %1\n", current_frame));
 916
 917                                         } else {
 918
 919                                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("bumped into beat-aligned tempo metric at %1 = %2\n",
 920                                                                                                tempo->start(), current_frame));
 921                                                 tempo->set_frame (current_frame);
 922                                         }
 923
 924                                 } else if ((ms = dynamic_cast<MeterSection*>(*next_metric)) != 0) {
 925
 926                                         meter = ms;
 927
 928                                         /* new meter section: always defines the
 929                                          * start of a bar.
 930                                          */
 931
 932                                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("bumped into meter section at %1 vs %2 (%3)\n",
 933                                                                                        meter->start(), current, current_frame));
 934
 935                                         assert (current.beats == 1);
 936
 937                                         meter->set_frame (current_frame);
 938                                 }
 939
 940                                 divisions_per_bar = meter->divisions_per_bar ();
 941                                 beat_frames = meter->frames_per_division (*tempo, _frame_rate);
 942
 943                                 DEBUG_TRACE (DEBUG::TempoMath, string_compose ("New metric with beat frames = %1 dpb %2 meter %3 tempo %4\n",
 944                                                                                beat_frames, divisions_per_bar, *((Meter*)meter), *((Tempo*)tempo)));
 945
 946                                 ++next_metric;
 947
 948                                 if (next_metric != metrics->end() && ((*next_metric)->start() == current)) {
 949                                         /* same position so go back and set this one up before advancing
 950                                         */
 951                                         goto set_metrics;
 952                                 }
 953                         }
 954                 }
 955
 956                 if (current.beats == 1) {
 957                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Add Bar at %1|1 @ %2\n", current.bars, current_frame));
 958                         _map.push_back (BBTPoint (*meter, *tempo,(framepos_t) llrint(current_frame), current.bars, 1));
 959                 } else {
 960                         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("Add Beat at %1|%2 @ %3\n", current.bars, current.beats, current_frame));
 961                         _map.push_back (BBTPoint (*meter, *tempo, (framepos_t) llrint(current_frame), current.bars, current.beats));
 962                 }
 963         }
 964 }
 965
 966 TempoMetric
 967 TempoMap::metric_at (framepos_t frame) const
 968 {
 969         Glib::RWLock::ReaderLock lm (lock);
 970         TempoMetric m (first_meter(), first_tempo());
 971         const Meter* meter;
 972         const Tempo* tempo;
 973
 974         /* at this point, we are *guaranteed* to have m.meter and m.tempo pointing
 975            at something, because we insert the default tempo and meter during
 976            TempoMap construction.
 977
 978            now see if we can find better candidates.
 979         */
 980
 981         for (Metrics::const_iterator i = metrics->begin(); i != metrics->end(); ++i) {
 982
 983                 // cerr << "Looking at a metric section " << **i << endl;
 984
 985                 if ((*i)->frame() > frame) {
 986                         break;
 987                 }
 988
 989                 if ((tempo = dynamic_cast<const TempoSection*>(*i)) != 0) {
 990                         m.set_tempo (*tempo);
 991                 } else if ((meter = dynamic_cast<const MeterSection*>(*i)) != 0) {
 992                         m.set_meter (*meter);
 993                 }
 994
 995                 m.set_frame ((*i)->frame ());
 996                 m.set_start ((*i)->start ());
 997         }
 998
 999         // cerr << "for framepos " << frame << " returning " << m.meter() << " @ " << m.tempo() << " location " << m.frame() << " = " << m.start() << endl;
1000         return m;
1001 }
1002
1003 TempoMetric
1004 TempoMap::metric_at (BBT_Time bbt) const
1005 {
1006         Glib::RWLock::ReaderLock lm (lock);
1007         TempoMetric m (first_meter(), first_tempo());
1008         const Meter* meter;
1009         const Tempo* tempo;
1010
1011         /* at this point, we are *guaranteed* to have m.meter and m.tempo pointing
1012            at something, because we insert the default tempo and meter during
1013            TempoMap construction.
1014
1015            now see if we can find better candidates.
1016         */
1017
1018         for (Metrics::const_iterator i = metrics->begin(); i != metrics->end(); ++i) {
1019
1020                 BBT_Time section_start ((*i)->start());
1021
1022                 if (section_start.bars > bbt.bars || (section_start.bars == bbt.bars && section_start.beats > bbt.beats)) {
1023                         break;
1024                 }
1025
1026                 if ((tempo = dynamic_cast<const TempoSection*>(*i)) != 0) {
1027                         m.set_tempo (*tempo);
1028                 } else if ((meter = dynamic_cast<const MeterSection*>(*i)) != 0) {
1029                         m.set_meter (*meter);
1030                 }
1031
1032                 m.set_frame ((*i)->frame ());
1033                 m.set_start (section_start);
1034         }
1035
1036         return m;
1037 }
1038
1039 void
1040 TempoMap::bbt_time (framepos_t frame, BBT_Time& bbt)
1041 {
1042         {
1043                 Glib::RWLock::ReaderLock lm (lock);
1044                 BBTPointList::const_iterator i = bbt_before_or_at (frame);
1045                 bbt_time_unlocked (frame, bbt, i);
1046         }
1047 }
1048
1049 void
1050 TempoMap::bbt_time_unlocked (framepos_t frame, BBT_Time& bbt, const BBTPointList::const_iterator& i)
1051 {
1052         bbt.bars = (*i).bar;
1053         bbt.beats = (*i).beat;
1054
1055         if ((*i).frame == frame) {
1056                 bbt.ticks = 0;
1057         } else {
1058                 bbt.ticks = llrint (((frame - (*i).frame) / (*i).meter->frames_per_division(*((*i).tempo), _frame_rate)) *
1059                                     BBT_Time::ticks_per_bar_division);
1060         }
1061 }
1062
1063 framepos_t
1064 TempoMap::frame_time (const BBT_Time& bbt)
1065 {
1066         Glib::RWLock::ReaderLock lm (lock);
1067
1068         BBTPointList::const_iterator s = bbt_point_for (BBT_Time (1, 1, 0));
1069         BBTPointList::const_iterator e = bbt_point_for (BBT_Time (bbt.bars, bbt.beats, 0));
1070
1071         if (bbt.ticks != 0) {
1072                 return ((*e).frame - (*s).frame) +
1073                         llrint ((*e).meter->frames_per_division (*(*e).tempo, _frame_rate) * (bbt.ticks/BBT_Time::ticks_per_bar_division));
1074         } else {
1075                 return ((*e).frame - (*s).frame);
1076         }
1077 }
1078
1079 framecnt_t
1080 TempoMap::bbt_duration_at (framepos_t pos, const BBT_Time& bbt, int dir)
1081 {
1082         Glib::RWLock::ReaderLock lm (lock);
1083         framecnt_t frames = 0;
1084         BBT_Time when;
1085
1086         bbt_time (pos, when);
1087         frames = bbt_duration_at_unlocked (when, bbt,dir);
1088
1089         return frames;
1090 }
1091
1092 framecnt_t
1093 TempoMap::bbt_duration_at_unlocked (const BBT_Time& when, const BBT_Time& bbt, int dir)
1094 {
1095         if (bbt.bars == 0 && bbt.beats == 0 && bbt.ticks == 0) {
1096                 return 0;
1097         }
1098
1099         /* round back to the previous precise beat */
1100         BBTPointList::const_iterator wi = bbt_point_for (BBT_Time (when.bars, when.beats, 0));
1101         BBTPointList::const_iterator start (wi);
1102         double tick_frames = 0;
1103
1104         assert (wi != _map.end());
1105
1106         /* compute how much rounding we did because of non-zero ticks */
1107
1108         if (when.ticks != 0) {
1109                 tick_frames = (*wi).meter->frames_per_division (*(*wi).tempo, _frame_rate) * (when.ticks/BBT_Time::ticks_per_bar_division);
1110         }
1111
1112         uint32_t bars = 0;
1113         uint32_t beats = 0;
1114
1115         while (wi != _map.end() && bars < bbt.bars) {
1116                 ++wi;
1117                 if ((*wi).beat == 1) {
1118                         ++bars;
1119                 }
1120         }
1121         assert (wi != _map.end());
1122
1123         while (wi != _map.end() && beats < bbt.beats) {
1124                 ++wi;
1125                 ++beats;
1126         }
1127         assert (wi != _map.end());
1128
1129         /* add any additional frames related to ticks in the added value */
1130
1131         if (bbt.ticks != 0) {
1132                 tick_frames += (*wi).meter->frames_per_division (*(*wi).tempo, _frame_rate) * (bbt.ticks/BBT_Time::ticks_per_bar_division);
1133         }
1134
1135         return ((*wi).frame - (*start).frame) + llrint (tick_frames);
1136 }
1137
1138 framepos_t
1139 TempoMap::round_to_bar (framepos_t fr, int dir)
1140 {
1141         {
1142                 Glib::RWLock::ReaderLock lm (lock);
1143                 return round_to_type (fr, dir, Bar);
1144         }
1145 }
1146
1147 framepos_t
1148 TempoMap::round_to_beat (framepos_t fr, int dir)
1149 {
1150         {
1151                 Glib::RWLock::ReaderLock lm (lock);
1152                 return round_to_type (fr, dir, Beat);
1153         }
1154 }
1155
1156 framepos_t
1157 TempoMap::round_to_beat_subdivision (framepos_t fr, int sub_num, int dir)
1158 {
1159         Glib::RWLock::ReaderLock lm (lock);
1160         BBTPointList::const_iterator i = bbt_before_or_at (fr);
1161         BBT_Time the_beat;
1162         uint32_t ticks_one_subdivisions_worth;
1163         uint32_t difference;
1164
1165         bbt_time_unlocked (fr, the_beat, i);
1166
1167         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("round %1 to nearest 1/%2 beat, before-or-at = %3 @ %4|%5 precise = %6\n",
1168                                                      fr, sub_num, (*i).frame, (*i).bar, (*i).beat, the_beat));
1169
1170         ticks_one_subdivisions_worth = (uint32_t)BBT_Time::ticks_per_bar_division / sub_num;
1171
1172         if (dir > 0) {
1173
1174                 /* round to next (even if we're on a subdivision */
1175
1176                 uint32_t mod = the_beat.ticks % ticks_one_subdivisions_worth;
1177
1178                 if (mod == 0) {
1179                         /* right on the subdivision, so the difference is just the subdivision ticks */
1180                         the_beat.ticks += ticks_one_subdivisions_worth;
1181
1182                 } else {
1183                         /* not on subdivision, compute distance to next subdivision */
1184
1185                         the_beat.ticks += ticks_one_subdivisions_worth - mod;
1186                 }
1187
1188                 if (the_beat.ticks > BBT_Time::ticks_per_bar_division) {
1189                         assert (i != _map.end());
1190                         ++i;
1191                         assert (i != _map.end());
1192                         the_beat.ticks -= BBT_Time::ticks_per_bar_division;
1193                 }
1194
1195
1196         } else if (dir < 0) {
1197
1198                 /* round to previous (even if we're on a subdivision) */
1199
1200                 uint32_t mod = the_beat.ticks % ticks_one_subdivisions_worth;
1201
1202                 if (mod == 0) {
1203                         /* right on the subdivision, so the difference is just the subdivision ticks */
1204                         difference = ticks_one_subdivisions_worth;
1205                 } else {
1206                         /* not on subdivision, compute distance to previous subdivision, which
1207                            is just the modulus.
1208                         */
1209
1210                         difference = mod;
1211                 }
1212
1213                 if (the_beat.ticks < difference) {
1214                         if (i == _map.begin()) {
1215                                 /* can't go backwards from wherever pos is, so just return it */
1216                                 return fr;
1217                         }
1218                         --i;
1219                         the_beat.ticks = BBT_Time::ticks_per_bar_division - the_beat.ticks;
1220                 } else {
1221                         the_beat.ticks -= difference;
1222                 }
1223
1224         } else {
1225                 /* round to nearest */
1226
1227                 double rem;
1228
1229                 /* compute the distance to the previous and next subdivision */
1230
1231                 if ((rem = fmod ((double) the_beat.ticks, (double) ticks_one_subdivisions_worth)) > ticks_one_subdivisions_worth/2.0) {
1232
1233                         /* closer to the next subdivision, so shift forward */
1234
1235                         the_beat.ticks = lrint (the_beat.ticks + (ticks_one_subdivisions_worth - rem));
1236
1237                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("moved forward to %1\n", the_beat.ticks));
1238
1239                         if (the_beat.ticks > BBT_Time::ticks_per_bar_division) {
1240                                 assert (i != _map.end());
1241                                 ++i;
1242                                 assert (i != _map.end());
1243                                 the_beat.ticks -= BBT_Time::ticks_per_bar_division;
1244                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("fold beat to %1\n", the_beat));
1245                         }
1246
1247                 } else if (rem > 0) {
1248
1249                         /* closer to previous subdivision, so shift backward */
1250
1251                         if (rem > the_beat.ticks) {
1252                                 if (i == _map.begin()) {
1253                                         /* can't go backwards past zero, so ... */
1254                                         return 0;
1255                                 }
1256                                 /* step back to previous beat */
1257                                 --i;
1258                                 the_beat.ticks = lrint (BBT_Time::ticks_per_bar_division - rem);
1259                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("step back beat to %1\n", the_beat));
1260                         } else {
1261                                 the_beat.ticks = lrint (the_beat.ticks - rem);
1262                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("moved backward to %1\n", the_beat.ticks));
1263                         }
1264                 } else {
1265                         /* on the subdivision, do nothing */
1266                 }
1267         }
1268
1269         return (*i).frame + (the_beat.ticks/BBT_Time::ticks_per_bar_division) *
1270                 (*i).meter->frames_per_division (*((*i).tempo), _frame_rate);
1271 }
1272
1273 framepos_t
1274 TempoMap::round_to_type (framepos_t frame, int dir, BBTPointType type)
1275 {
1276         BBTPointList::const_iterator fi;
1277
1278         if (dir > 0) {
1279                 fi = bbt_after_or_at (frame);
1280         } else {
1281                 fi = bbt_before_or_at (frame);
1282         }
1283
1284         assert (fi != _map.end());
1285
1286         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));
1287
1288         switch (type) {
1289         case Bar:
1290                 if (dir < 0) {
1291                         /* find bar previous to 'frame' */
1292
1293                         if ((*fi).beat == 1 && (*fi).frame == frame) {
1294                                 --fi;
1295                         }
1296
1297                         while ((*fi).beat > 1) {
1298                                 if (fi == _map.begin()) {
1299                                         break;
1300                                 }
1301                                 fi--;
1302                         }
1303                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("rounded to bar: map iter at %1|%2 %3, return\n",
1304                                                                      (*fi).bar, (*fi).beat, (*fi).frame));
1305                         return (*fi).frame;
1306
1307                 } else if (dir > 0) {
1308
1309                         /* find bar following 'frame' */
1310
1311                         if ((*fi).beat == 1 && (*fi).frame == frame) {
1312                                 ++fi;
1313                         }
1314
1315                         while ((*fi).beat != 1) {
1316                                 fi++;
1317                                 if (fi == _map.end()) {
1318                                         --fi;
1319                                         break;
1320                                 }
1321                         }
1322
1323                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("rounded to bar: map iter at %1|%2 %3, return\n",
1324                                                                      (*fi).bar, (*fi).beat, (*fi).frame));
1325                         return (*fi).frame;
1326
1327                 } else {
1328
1329                         /* true rounding: find nearest bar */
1330
1331                         BBTPointList::const_iterator prev = fi;
1332                         BBTPointList::const_iterator next = fi;
1333
1334                         if ((*fi).frame == frame) {
1335                                 return frame;
1336                         }
1337
1338                         while ((*prev).beat != 1) {
1339                                 if (prev == _map.begin()) {
1340                                         break;
1341                                 }
1342                                 prev--;
1343                         }
1344
1345                         while ((*next).beat != 1) {
1346                                 next++;
1347                                 if (next == _map.end()) {
1348                                         --next;
1349                                         break;
1350                                 }
1351                         }
1352
1353                         if ((frame - (*prev).frame) < ((*next).frame - frame)) {
1354                                 return (*prev).frame;
1355                         } else {
1356                                 return (*next).frame;
1357                         }
1358
1359                 }
1360
1361                 break;
1362
1363         case Beat:
1364                 if (dir < 0) {
1365                         if ((*fi).frame >= frame) {
1366                                 DEBUG_TRACE (DEBUG::SnapBBT, "requested frame is on beat, step back\n");
1367                                 --fi;
1368                         }
1369                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("rounded to beat: map iter at %1|%2 %3, return\n",
1370                                                                      (*fi).bar, (*fi).beat, (*fi).frame));
1371                         return (*fi).frame;
1372                 } else if (dir > 0) {
1373                         if ((*fi).frame <= frame) {
1374                                 DEBUG_TRACE (DEBUG::SnapBBT, "requested frame is on beat, step forward\n");
1375                                 ++fi;
1376                         }
1377                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("rounded to beat: map iter at %1|%2 %3, return\n",
1378                                                                      (*fi).bar, (*fi).beat, (*fi).frame));
1379                         return (*fi).frame;
1380                 } else {
1381                         /* find beat nearest to frame */
1382                         if ((*fi).frame == frame) {
1383                                 return frame;
1384                         }
1385
1386                         BBTPointList::const_iterator prev = fi;
1387                         BBTPointList::const_iterator next = fi;
1388                         --prev;
1389                         ++next;
1390
1391                         if ((frame - (*prev).frame) < ((*next).frame - frame)) {
1392                                 return (*prev).frame;
1393                         } else {
1394                                 return (*next).frame;
1395                         }
1396                 }
1397                 break;
1398         }
1399
1400         /* NOTREACHED */
1401         assert (false);
1402         return 0;
1403 }
1404
1405 void
1406 TempoMap::map (TempoMap::BBTPointList::const_iterator& begin,
1407                TempoMap::BBTPointList::const_iterator& end,
1408                framepos_t lower, framepos_t upper)
1409 {
1410         if (_map.empty() || upper >= _map.back().frame) {
1411                 recompute_map (false, upper);
1412         }
1413
1414         begin = lower_bound (_map.begin(), _map.end(), lower);
1415         end = upper_bound (_map.begin(), _map.end(), upper);
1416 }
1417
1418 const TempoSection&
1419 TempoMap::tempo_section_at (framepos_t frame) const
1420 {
1421         Glib::RWLock::ReaderLock lm (lock);
1422         Metrics::const_iterator i;
1423         TempoSection* prev = 0;
1424
1425         for (i = metrics->begin(); i != metrics->end(); ++i) {
1426                 TempoSection* t;
1427
1428                 if ((t = dynamic_cast<TempoSection*> (*i)) != 0) {
1429
1430                         if ((*i)->frame() > frame) {
1431                                 break;
1432                         }
1433
1434                         prev = t;
1435                 }
1436         }
1437
1438         if (prev == 0) {
1439                 fatal << endmsg;
1440         }
1441
1442         return *prev;
1443 }
1444
1445 const Tempo&
1446 TempoMap::tempo_at (framepos_t frame) const
1447 {
1448         TempoMetric m (metric_at (frame));
1449         return m.tempo();
1450 }
1451
1452
1453 const Meter&
1454 TempoMap::meter_at (framepos_t frame) const
1455 {
1456         TempoMetric m (metric_at (frame));
1457         return m.meter();
1458 }
1459
1460 XMLNode&
1461 TempoMap::get_state ()
1462 {
1463         Metrics::const_iterator i;
1464         XMLNode *root = new XMLNode ("TempoMap");
1465
1466         {
1467                 Glib::RWLock::ReaderLock lm (lock);
1468                 for (i = metrics->begin(); i != metrics->end(); ++i) {
1469                         root->add_child_nocopy ((*i)->get_state());
1470                 }
1471         }
1472
1473         return *root;
1474 }
1475
1476 int
1477 TempoMap::set_state (const XMLNode& node, int /*version*/)
1478 {
1479         {
1480                 Glib::RWLock::WriterLock lm (lock);
1481
1482                 XMLNodeList nlist;
1483                 XMLNodeConstIterator niter;
1484                 Metrics old_metrics (*metrics);
1485                 MeterSection* last_meter = 0;
1486
1487                 metrics->clear();
1488
1489                 nlist = node.children();
1490
1491                 for (niter = nlist.begin(); niter != nlist.end(); ++niter) {
1492                         XMLNode* child = *niter;
1493
1494                         if (child->name() == TempoSection::xml_state_node_name) {
1495
1496                                 try {
1497                                         TempoSection* ts = new TempoSection (*child);
1498                                         metrics->push_back (ts);
1499
1500                                         if (ts->bar_offset() < 0.0) {
1501                                                 if (last_meter) {
1502                                                         ts->update_bar_offset_from_bbt (*last_meter);
1503                                                 }
1504                                         }
1505                                 }
1506
1507                                 catch (failed_constructor& err){
1508                                         error << _("Tempo map: could not set new state, restoring old one.") << endmsg;
1509                                         *metrics = old_metrics;
1510                                         break;
1511                                 }
1512
1513                         } else if (child->name() == MeterSection::xml_state_node_name) {
1514
1515                                 try {
1516                                         MeterSection* ms = new MeterSection (*child);
1517                                         metrics->push_back (ms);
1518                                         last_meter = ms;
1519                                 }
1520
1521                                 catch (failed_constructor& err) {
1522                                         error << _("Tempo map: could not set new state, restoring old one.") << endmsg;
1523                                         *metrics = old_metrics;
1524                                         break;
1525                                 }
1526                         }
1527                 }
1528
1529                 if (niter == nlist.end()) {
1530
1531                         MetricSectionSorter cmp;
1532                         metrics->sort (cmp);
1533                         recompute_map (true);
1534                 }
1535         }
1536
1537         PropertyChanged (PropertyChange ());
1538
1539         return 0;
1540 }
1541
1542 void
1543 TempoMap::dump (std::ostream& o) const
1544 {
1545         const MeterSection* m;
1546         const TempoSection* t;
1547
1548         for (Metrics::const_iterator i = metrics->begin(); i != metrics->end(); ++i) {
1549
1550                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1551                         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? "
1552                           << t->movable() << ')' << endl;
1553                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
1554                         o << "Meter @ " << *i << ' ' << m->divisions_per_bar() << '/' << m->note_divisor() << " at " << m->start() << " frame= " << m->frame()
1555                           << " (movable? " << m->movable() << ')' << endl;
1556                 }
1557         }
1558 }
1559
1560 int
1561 TempoMap::n_tempos() const
1562 {
1563         Glib::RWLock::ReaderLock lm (lock);
1564         int cnt = 0;
1565
1566         for (Metrics::const_iterator i = metrics->begin(); i != metrics->end(); ++i) {
1567                 if (dynamic_cast<const TempoSection*>(*i) != 0) {
1568                         cnt++;
1569                 }
1570         }
1571
1572         return cnt;
1573 }
1574
1575 int
1576 TempoMap::n_meters() const
1577 {
1578         Glib::RWLock::ReaderLock lm (lock);
1579         int cnt = 0;
1580
1581         for (Metrics::const_iterator i = metrics->begin(); i != metrics->end(); ++i) {
1582                 if (dynamic_cast<const MeterSection*>(*i) != 0) {
1583                         cnt++;
1584                 }
1585         }
1586
1587         return cnt;
1588 }
1589
1590 void
1591 TempoMap::insert_time (framepos_t where, framecnt_t amount)
1592 {
1593         for (Metrics::iterator i = metrics->begin(); i != metrics->end(); ++i) {
1594                 if ((*i)->frame() >= where && (*i)->movable ()) {
1595                         (*i)->set_frame ((*i)->frame() + amount);
1596                 }
1597         }
1598
1599         timestamp_metrics_from_audio_time ();
1600
1601         PropertyChanged (PropertyChange ());
1602 }
1603
1604 /** Add some (fractional) beats to a session frame position, and return the result in frames.
1605  *  pos can be -ve, if required.
1606  */
1607 framepos_t
1608 TempoMap::framepos_plus_beats (framepos_t pos, Evoral::MusicalTime beats)
1609 {
1610         Metrics::const_iterator i;
1611         const TempoSection* tempo;
1612
1613         /* Find the starting tempo */
1614
1615         for (i = metrics->begin(); i != metrics->end(); ++i) {
1616
1617                 /* This is a bit of a hack, but pos could be -ve, and if it is,
1618                    we consider the initial metric changes (at time 0) to actually
1619                    be in effect at pos.
1620                 */
1621                 framepos_t f = (*i)->frame ();
1622                 if (pos < 0 && f == 0) {
1623                         f = pos;
1624                 }
1625
1626                 if (f > pos) {
1627                         break;
1628                 }
1629
1630                 const TempoSection* t;
1631
1632                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1633                         tempo = t;
1634                 }
1635         }
1636
1637         /* We now have:
1638
1639            tempo -> the Tempo for "pos"
1640            i     -> for first new metric after "pos", possibly metrics->end()
1641         */
1642
1643         while (beats) {
1644
1645                 /* Distance to the end of this section in frames */
1646                 framecnt_t distance_frames = i == metrics->end() ? max_framepos : ((*i)->frame() - pos);
1647
1648                 /* Distance to the end in beats */
1649                 Evoral::MusicalTime distance_beats = distance_frames / tempo->frames_per_beat (_frame_rate);
1650
1651                 /* Amount to subtract this time */
1652                 double const sub = min (distance_beats, beats);
1653
1654                 /* Update */
1655                 beats -= sub;
1656                 pos += sub * tempo->frames_per_beat (_frame_rate);
1657
1658                 /* Move on if there's anything to move to */
1659                 if (i != metrics->end ()) {
1660                         const TempoSection* t;
1661
1662                         if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1663                                 tempo = t;
1664                         }
1665
1666                         ++i;
1667                 }
1668         }
1669
1670         return pos;
1671 }
1672
1673 /** Subtract some (fractional) beats to a frame position, and return the result in frames */
1674 framepos_t
1675 TempoMap::framepos_minus_beats (framepos_t pos, Evoral::MusicalTime beats)
1676 {
1677         Metrics::const_iterator i;
1678         const TempoSection* tempo = 0;
1679         const TempoSection* t;
1680
1681         /* Find the starting tempo */
1682
1683         for (i = metrics->begin(); i != metrics->end(); ++i) {
1684
1685                 /* This is a bit of a hack, but pos could be -ve, and if it is,
1686                    we consider the initial metric changes (at time 0) to actually
1687                    be in effect at pos.
1688                 */
1689                 framepos_t f = (*i)->frame ();
1690                 if (pos < 0 && f == 0) {
1691                         f = pos;
1692                 }
1693
1694                 if ((*i)->frame() > pos) {
1695                         break;
1696                 }
1697
1698                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1699                         tempo = t;
1700                 }
1701         }
1702
1703         bool no_more_tempos = false;
1704
1705         /* Move i back to the tempo before "pos" */
1706         if (i != metrics->begin ()) {
1707                 while (i != metrics->begin ()) {
1708                         --i;
1709                         t = dynamic_cast<TempoSection*> (*i);
1710                         if (t) {
1711                                 break;
1712                         }
1713                 }
1714         } else {
1715                 no_more_tempos = true;
1716         }
1717
1718         /* We now have:
1719
1720            tempo -> the Tempo for "pos"
1721            i     -> the first metric before "pos", unless no_more_tempos is true
1722         */
1723
1724         while (beats) {
1725
1726                 /* Distance to the end of this section in frames */
1727                 framecnt_t distance_frames = no_more_tempos ? max_framepos : (pos - (*i)->frame());
1728
1729                 /* Distance to the end in beats */
1730                 Evoral::MusicalTime distance_beats = distance_frames / tempo->frames_per_beat (_frame_rate);
1731
1732                 /* Amount to subtract this time */
1733                 double const sub = min (distance_beats, beats);
1734
1735                 /* Update */
1736                 beats -= sub;
1737                 pos -= sub * tempo->frames_per_beat (_frame_rate);
1738
1739                 /* Move i and tempo back, if there's anything to move to */
1740                 if (i != metrics->begin ()) {
1741                         while (i != metrics->begin ()) {
1742                                 --i;
1743                                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1744                                         tempo = t;
1745                                         break;
1746                                 }
1747                         }
1748                 } else {
1749                         no_more_tempos = true;
1750                 }
1751         }
1752
1753         return pos;
1754 }
1755
1756 /** Add the BBT interval op to pos and return the result */
1757 framepos_t
1758 TempoMap::framepos_plus_bbt (framepos_t pos, BBT_Time op)
1759 {
1760         Metrics::const_iterator i;
1761         const MeterSection* meter;
1762         const MeterSection* m;
1763         const TempoSection* tempo;
1764         const TempoSection* t;
1765         double frames_per_beat;
1766
1767         meter = &first_meter ();
1768         tempo = &first_tempo ();
1769
1770         assert (meter);
1771         assert (tempo);
1772
1773         /* find the starting metrics for tempo & meter */
1774
1775         for (i = metrics->begin(); i != metrics->end(); ++i) {
1776
1777                 if ((*i)->frame() > pos) {
1778                         break;
1779                 }
1780
1781                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1782                         tempo = t;
1783                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
1784                         meter = m;
1785                 }
1786         }
1787
1788         /* We now have:
1789
1790            meter -> the Meter for "pos"
1791            tempo -> the Tempo for "pos"
1792            i     -> for first new metric after "pos", possibly metrics->end()
1793         */
1794
1795         /* now comes the complicated part. we have to add one beat a time,
1796            checking for a new metric on every beat.
1797         */
1798
1799         frames_per_beat = tempo->frames_per_beat (_frame_rate);
1800
1801         uint64_t bars = 0;
1802
1803         while (op.bars) {
1804
1805                 bars++;
1806                 op.bars--;
1807
1808                 /* check if we need to use a new metric section: has adding frames moved us
1809                    to or after the start of the next metric section? in which case, use it.
1810                 */
1811
1812                 if (i != metrics->end()) {
1813                         if ((*i)->frame() <= pos) {
1814
1815                                 /* about to change tempo or meter, so add the
1816                                  * number of frames for the bars we've just
1817                                  * traversed before we change the
1818                                  * frames_per_beat value.
1819                                  */
1820
1821                                 pos += llrint (frames_per_beat * (bars * meter->divisions_per_bar()));
1822                                 bars = 0;
1823
1824                                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1825                                         tempo = t;
1826                                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
1827                                         meter = m;
1828                                 }
1829                                 ++i;
1830                                 frames_per_beat = tempo->frames_per_beat (_frame_rate);
1831
1832                         }
1833                 }
1834
1835         }
1836
1837         pos += llrint (frames_per_beat * (bars * meter->divisions_per_bar()));
1838
1839         uint64_t beats = 0;
1840
1841         while (op.beats) {
1842
1843                 /* given the current meter, have we gone past the end of the bar ? */
1844
1845                 beats++;
1846                 op.beats--;
1847
1848                 /* check if we need to use a new metric section: has adding frames moved us
1849                    to or after the start of the next metric section? in which case, use it.
1850                 */
1851
1852                 if (i != metrics->end()) {
1853                         if ((*i)->frame() <= pos) {
1854
1855                                 /* about to change tempo or meter, so add the
1856                                  * number of frames for the beats we've just
1857                                  * traversed before we change the
1858                                  * frames_per_beat value.
1859                                  */
1860
1861                                 pos += llrint (beats * frames_per_beat);
1862                                 beats = 0;
1863
1864                                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
1865                                         tempo = t;
1866                                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
1867                                         meter = m;
1868                                 }
1869                                 ++i;
1870                                 frames_per_beat = tempo->frames_per_beat (_frame_rate);
1871                         }
1872                 }
1873         }
1874
1875         pos += llrint (beats * frames_per_beat);
1876
1877         if (op.ticks) {
1878                 if (op.ticks >= BBT_Time::ticks_per_bar_division) {
1879                         pos += llrint (frames_per_beat + /* extra beat */
1880                                        (frames_per_beat * ((op.ticks % (uint32_t) BBT_Time::ticks_per_bar_division) /
1881                                                            (double) BBT_Time::ticks_per_bar_division)));
1882                 } else {
1883                         pos += llrint (frames_per_beat * (op.ticks / (double) BBT_Time::ticks_per_bar_division));
1884                 }
1885         }
1886
1887         return pos;
1888 }
1889
1890 /** Count the number of beats that are equivalent to distance when going forward,
1891     starting at pos.
1892 */
1893 Evoral::MusicalTime
1894 TempoMap::framewalk_to_beats (framepos_t pos, framecnt_t distance)
1895 {
1896         BBTPointList::const_iterator i = bbt_after_or_at (pos);
1897         Evoral::MusicalTime beats = 0;
1898         framepos_t end = pos + distance;
1899
1900         require_map_to (end);
1901
1902         /* if our starting BBTPoint is after pos, add a fractional beat
1903            to represent that distance.
1904         */
1905
1906         if ((*i).frame != pos) {
1907                 beats += ((*i).frame - pos) / (*i).meter->frames_per_division (*(*i).tempo, _frame_rate);
1908         }
1909
1910         while (i != _map.end() && (*i).frame < end) {
1911                 ++i;
1912                 beats++;
1913         }
1914         assert (i != _map.end());
1915
1916         /* if our ending BBTPoint is after the end, subtract a fractional beat
1917            to represent that distance.
1918         */
1919
1920         if ((*i).frame > end) {
1921                 beats -= ((*i).frame - end) / (*i).meter->frames_per_division (*(*i).tempo, _frame_rate);
1922         }
1923
1924         return beats;
1925 }
1926
1927 TempoMap::BBTPointList::const_iterator
1928 TempoMap::bbt_before_or_at (framepos_t pos)
1929 {
1930         require_map_to (pos);
1931         BBTPointList::const_iterator i = lower_bound (_map.begin(), _map.end(), pos);
1932         assert (i != _map.end());
1933         if ((*i).frame > pos) {
1934                 assert (i != _map.begin());
1935                 --i;
1936         }
1937         return i;
1938 }
1939
1940 TempoMap::BBTPointList::const_iterator
1941 TempoMap::bbt_after_or_at (framepos_t pos)
1942 {
1943         require_map_to (pos);
1944         BBTPointList::const_iterator i = upper_bound (_map.begin(), _map.end(), pos);
1945         assert (i != _map.end());
1946         return i;
1947 }
1948
1949 struct bbtcmp {
1950     bool operator() (const BBT_Time& a, const BBT_Time& b) {
1951             return a < b;
1952     }
1953 };
1954
1955 TempoMap::BBTPointList::const_iterator
1956 TempoMap::bbt_point_for (const BBT_Time& bbt)
1957 {
1958         bbtcmp cmp;
1959         int additional_minutes = 1;
1960
1961         while (_map.empty() || _map.back().bar < (bbt.bars + 1)) {
1962                 /* add some more distance, using bigger steps each time */
1963                 require_map_to (_map.back().frame + (_frame_rate * 60 * additional_minutes));
1964                 additional_minutes *= 2;
1965         }
1966
1967         BBTPointList::const_iterator i = lower_bound (_map.begin(), _map.end(), bbt, cmp);
1968         assert (i != _map.end());
1969         return i;
1970 }
1971
1972
1973 /** Compare the time of this with that of another MetricSection.
1974  *  @param with_bbt True to compare using start(), false to use frame().
1975  *  @return -1 for less than, 0 for equal, 1 for greater than.
1976  */
1977
1978 int
1979 MetricSection::compare (const MetricSection& other) const
1980 {
1981         if (start() == other.start()) {
1982                 return 0;
1983         } else if (start() < other.start()) {
1984                 return -1;
1985         } else {
1986                 return 1;
1987         }
1988
1989         /* NOTREACHED */
1990         return 0;
1991 }
1992
1993 bool
1994 MetricSection::operator== (const MetricSection& other) const
1995 {
1996         return compare (other) == 0;
1997 }
1998
1999 bool
2000 MetricSection::operator!= (const MetricSection& other) const
2001 {
2002         return compare (other) != 0;
2003 }
2004
2005 std::ostream&
2006 operator<< (std::ostream& o, const Meter& m) {
2007         return o << m.divisions_per_bar() << '/' << m.note_divisor();
2008 }
2009
2010 std::ostream&
2011 operator<< (std::ostream& o, const Tempo& t) {
2012         return o << t.beats_per_minute() << " 1/" << t.note_type() << "'s per minute";
2013 }
2014
2015 std::ostream&
2016 operator<< (std::ostream& o, const MetricSection& section) {
2017
2018         o << "MetricSection @ " << section.frame() << " aka " << section.start() << ' ';
2019
2020         const TempoSection* ts;
2021         const MeterSection* ms;
2022
2023         if ((ts = dynamic_cast<const TempoSection*> (&section)) != 0) {
2024                 o << *((Tempo*) ts);
2025         } else if ((ms = dynamic_cast<const MeterSection*> (&section)) != 0) {
2026                 o << *((Meter*) ms);
2027         }
2028
2029         return o;
2030 }