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