libs/ardour/tempo.cc

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