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