libs/ardour/tempo.cc

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