libs/ardour/tempo.cc

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