libs/ardour/tempo.cc

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