libs/ardour/tempo.cc

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