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