libs/ardour/tempo.cc

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