libs/ardour/tempo.cc

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