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 #include <cmath>
  23
  24 #include <unistd.h>
  25
  26 #include <glibmm/threads.h>
  27
  28 #include "pbd/enumwriter.h"
  29 #include "pbd/xml++.h"
  30 #include "evoral/Beats.hpp"
  31
  32 #include "ardour/debug.h"
  33 #include "ardour/lmath.h"
  34 #include "ardour/tempo.h"
  35
  36 #include "pbd/i18n.h"
  37 #include <locale.h>
  38
  39 using namespace std;
  40 using namespace ARDOUR;
  41 using namespace PBD;
  42
  43 using Timecode::BBT_Time;
  44
  45 /* _default tempo is 4/4 qtr=120 */
  46
  47 Meter    TempoMap::_default_meter (4.0, 4.0);
  48 Tempo    TempoMap::_default_tempo (120.0);
  49
  50 framepos_t
  51 MetricSection::frame_at_minute (const double& time) const
  52 {
  53         return (framepos_t) floor ((time * 60.0 * _sample_rate) + 0.5);
  54 }
  55
  56 double
  57 MetricSection::minute_at_frame (const framepos_t& frame) const
  58 {
  59         return (frame / (double) _sample_rate) / 60.0;
  60 }
  61
  62 /***********************************************************************/
  63
  64 double
  65 Meter::frames_per_grid (const Tempo& tempo, framecnt_t sr) const
  66 {
  67         /* This is tempo- and meter-sensitive. The number it returns
  68            is based on the interval between any two lines in the
  69            grid that is constructed from tempo and meter sections.
  70
  71            The return value IS NOT interpretable in terms of "beats".
  72         */
  73
  74         return (60.0 * sr) / (tempo.beats_per_minute() * (_note_type/tempo.note_type()));
  75 }
  76
  77 double
  78 Meter::frames_per_bar (const Tempo& tempo, framecnt_t sr) const
  79 {
  80         return frames_per_grid (tempo, sr) * _divisions_per_bar;
  81 }
  82
  83 /***********************************************************************/
  84
  85 const string TempoSection::xml_state_node_name = "Tempo";
  86
  87 TempoSection::TempoSection (const XMLNode& node, framecnt_t sample_rate)
  88         : MetricSection (0.0, 0, MusicTime, true, sample_rate)
  89         , Tempo (TempoMap::default_tempo())
  90         , _c_func (0.0)
  91         , _active (true)
  92         , _locked_to_meter (false)
  93 {
  94         XMLProperty const * prop;
  95         LocaleGuard lg;
  96         BBT_Time bbt;
  97         double pulse;
  98         uint32_t frame;
  99         double minute;
 100
 101         _legacy_bbt = BBT_Time (0, 0, 0);
 102
 103         if ((prop = node.property ("start")) != 0) {
 104                 if (sscanf (prop->value().c_str(), "%" PRIu32 "|%" PRIu32 "|%" PRIu32,
 105                             &bbt.bars,
 106                             &bbt.beats,
 107                             &bbt.ticks) == 3) {
 108                         /* legacy session - start used to be in bbt*/
 109                         _legacy_bbt = bbt;
 110                         pulse = -1.0;
 111                         info << _("Legacy session detected. TempoSection XML node will be altered.") << endmsg;
 112                 }
 113         }
 114
 115         if ((prop = node.property ("pulse")) != 0) {
 116                 if (sscanf (prop->value().c_str(), "%lf", &pulse) != 1) {
 117                         error << _("TempoSection XML node has an illegal \"pulse\" value") << endmsg;
 118                 }
 119         }
 120
 121         set_pulse (pulse);
 122
 123         if ((prop = node.property ("frame")) != 0) {
 124                 if (sscanf (prop->value().c_str(), "%" PRIu32, &frame) != 1) {
 125                         error << _("TempoSection XML node has an illegal \"frame\" value") << endmsg;
 126                 } else {
 127                         set_minute (minute_at_frame (frame));
 128                 }
 129         }
 130
 131         if ((prop = node.property ("minute")) != 0) {
 132                 if (sscanf (prop->value().c_str(), "%lf", &minute) != 1) {
 133                         error << _("TempoSection XML node has an illegal \"minute\" value") << endmsg;
 134                 } else {
 135                         set_minute (minute);
 136                 }
 137         }
 138
 139         if ((prop = node.property ("beats-per-minute")) == 0) {
 140                 error << _("TempoSection XML node has no \"beats-per-minute\" property") << endmsg;
 141                 throw failed_constructor();
 142         }
 143
 144         if (sscanf (prop->value().c_str(), "%lf", &_beats_per_minute) != 1 || _beats_per_minute < 0.0) {
 145                 error << _("TempoSection XML node has an illegal \"beats_per_minute\" value") << endmsg;
 146                 throw failed_constructor();
 147         }
 148
 149         if ((prop = node.property ("note-type")) == 0) {
 150                 /* older session, make note type be quarter by default */
 151                 _note_type = 4.0;
 152         } else {
 153                 if (sscanf (prop->value().c_str(), "%lf", &_note_type) != 1 || _note_type < 1.0) {
 154                         error << _("TempoSection XML node has an illegal \"note-type\" value") << endmsg;
 155                         throw failed_constructor();
 156         }
 157         }
 158
 159         if ((prop = node.property ("movable")) == 0) {
 160                 error << _("TempoSection XML node has no \"movable\" property") << endmsg;
 161                 throw failed_constructor();
 162         }
 163
 164         set_movable (string_is_affirmative (prop->value()));
 165
 166         if ((prop = node.property ("active")) == 0) {
 167                 warning << _("TempoSection XML node has no \"active\" property") << endmsg;
 168                 set_active(true);
 169         } else {
 170                 set_active (string_is_affirmative (prop->value()));
 171         }
 172
 173         if ((prop = node.property ("tempo-type")) == 0) {
 174                 _type = Constant;
 175         } else {
 176                 _type = Type (string_2_enum (prop->value(), _type));
 177         }
 178
 179         if ((prop = node.property ("lock-style")) == 0) {
 180                 if (movable()) {
 181                         set_position_lock_style (MusicTime);
 182                 } else {
 183                         set_position_lock_style (AudioTime);
 184                 }
 185         } else {
 186                 set_position_lock_style (PositionLockStyle (string_2_enum (prop->value(), position_lock_style())));
 187         }
 188
 189         if ((prop = node.property ("locked-to-meter")) == 0) {
 190                 set_locked_to_meter (false);
 191         } else {
 192                 set_locked_to_meter (string_is_affirmative (prop->value()));
 193         }
 194 }
 195
 196 XMLNode&
 197 TempoSection::get_state() const
 198 {
 199         XMLNode *root = new XMLNode (xml_state_node_name);
 200         char buf[256];
 201         LocaleGuard lg;
 202
 203         snprintf (buf, sizeof (buf), "%lf", pulse());
 204         root->add_property ("pulse", buf);
 205         snprintf (buf, sizeof (buf), "%li", frame());
 206         root->add_property ("frame", buf);
 207         snprintf (buf, sizeof (buf), "%lf", minute());
 208         root->add_property ("minute", buf);
 209         snprintf (buf, sizeof (buf), "%lf", _beats_per_minute);
 210         root->add_property ("beats-per-minute", buf);
 211         snprintf (buf, sizeof (buf), "%lf", _note_type);
 212         root->add_property ("note-type", buf);
 213         snprintf (buf, sizeof (buf), "%s", movable()?"yes":"no");
 214         root->add_property ("movable", buf);
 215         snprintf (buf, sizeof (buf), "%s", active()?"yes":"no");
 216         root->add_property ("active", buf);
 217         root->add_property ("tempo-type", enum_2_string (_type));
 218         root->add_property ("lock-style", enum_2_string (position_lock_style()));
 219         root->add_property ("locked-to-meter", locked_to_meter()?"yes":"no");
 220
 221         return *root;
 222 }
 223
 224 void
 225 TempoSection::set_type (Type type)
 226 {
 227         _type = type;
 228 }
 229
 230 /** returns the tempo in beats per minute at the zero-based (relative to session) minute.
 231 */
 232 double
 233 TempoSection::tempo_at_minute (const double& m) const
 234 {
 235
 236         if (_type == Constant || _c_func == 0.0) {
 237                 return beats_per_minute();
 238         }
 239
 240         return _tempo_at_time (m - minute());
 241 }
 242
 243 /** returns the zero-based minute (relative to session)
 244    where the tempo in beats per minute occurs in this section.
 245    pulse p is only used for constant tempi.
 246    note that the tempo map may have multiple such values.
 247 */
 248 double
 249 TempoSection::minute_at_tempo (const double& bpm, const double& p) const
 250 {
 251         if (_type == Constant || _c_func == 0.0) {
 252                 return (((p - pulse())  * note_type()) / beats_per_minute()) + minute();
 253         }
 254
 255         return _time_at_tempo (bpm) + minute();
 256 }
 257 /** returns the tempo in beats per minute at the zero-based (relative to session) pulse.
 258 */
 259 double
 260 TempoSection::tempo_at_pulse (const double& p) const
 261 {
 262
 263         if (_type == Constant || _c_func == 0.0) {
 264                 return beats_per_minute();
 265         }
 266
 267         return _tempo_at_pulse (p - pulse());
 268 }
 269
 270 /** returns the zero-based pulse (relative to session)
 271    where the tempo in qn beats per minute occurs given frame f. frame f is only used for constant tempi.
 272    note that the session tempo map may have multiple beats at a given tempo.
 273 */
 274 double
 275 TempoSection::pulse_at_tempo (const double& bpm, const double& m) const
 276 {
 277         if (_type == Constant || _c_func == 0.0) {
 278                 const double pulses = (((m - minute()) * beats_per_minute()) / note_type()) + pulse();
 279                 return pulses;
 280         }
 281
 282         return _pulse_at_tempo (bpm) + pulse();
 283 }
 284
 285 /** returns the zero-based pulse (relative to session origin)
 286    where the zero-based frame (relative to session)
 287    lies.
 288 */
 289 double
 290 TempoSection::pulse_at_frame (const framepos_t& f) const
 291 {
 292         return pulse_at_minute (minute_at_frame (f));
 293 }
 294
 295 double
 296 TempoSection::pulse_at_minute (const double& m) const
 297 {
 298         if (_type == Constant || _c_func == 0.0) {
 299                 return (((m - minute()) * beats_per_minute()) / _note_type) + pulse();
 300         }
 301
 302         return _pulse_at_time (m - minute()) + pulse();
 303 }
 304
 305 /** returns the zero-based frame (relative to session start frame)
 306    where the zero-based pulse (relative to session start)
 307    falls.
 308 */
 309
 310 framepos_t
 311 TempoSection::frame_at_pulse (const double& p) const
 312 {
 313         return frame_at_minute (minute_at_pulse (p));
 314 }
 315
 316 double
 317 TempoSection::minute_at_pulse (const double& p) const
 318 {
 319         if (_type == Constant || _c_func == 0.0) {
 320                 return (((p - pulse()) * note_type()) / beats_per_minute()) + minute();
 321         }
 322
 323         return _time_at_pulse (p - pulse()) + minute();
 324 }
 325
 326 /*
 327 Ramp Overview
 328
 329       |                     *
 330 Tempo |                   *
 331 Tt----|-----------------*|
 332 Ta----|--------------|*  |
 333       |            * |   |
 334       |         *    |   |
 335       |     *        |   |
 336 T0----|*             |   |
 337   *   |              |   |
 338       _______________|___|____
 339       time           a   t (next tempo)
 340       [        c         ] defines c
 341
 342 Duration in beats at time a is the integral of some Tempo function.
 343 In our case, the Tempo function (Tempo at time t) is
 344 T(t) = T0(e^(ct))
 345
 346 with function constant
 347 c = log(Ta/T0)/a
 348 so
 349 a = log(Ta/T0)/c
 350
 351 The integral over t of our Tempo function (the beat function, which is the duration in beats at some time t) is:
 352 b(t) = T0(e^(ct) - 1) / c
 353
 354 To find the time t at beat duration b, we use the inverse function of the beat function (the time function) which can be shown to be:
 355 t(b) = log((c.b / T0) + 1) / c
 356
 357 The time t at which Tempo T occurs is a as above:
 358 t(T) = log(T / T0) / c
 359
 360 The beat at which a Tempo T occurs is:
 361 b(T) = (T - T0) / c
 362
 363 The Tempo at which beat b occurs is:
 364 T(b) = b.c + T0
 365
 366 We define c for this tempo ramp by placing a new tempo section at some time t after this one.
 367 Our problem is that we usually don't know t.
 368 We almost always know the duration in beats between this and the new section, so we need to find c in terms of the beat function.
 369 Where a = t (i.e. when a is equal to the time of the next tempo section), the beat function reveals:
 370 t = b log (Ta / T0) / (T0 (e^(log (Ta / T0)) - 1))
 371
 372 By substituting our expanded t as a in the c function above, our problem is reduced to:
 373 c = T0 (e^(log (Ta / T0)) - 1) / b
 374
 375 Of course the word 'beat' has been left loosely defined above.
 376 In music, a beat is defined by the musical pulse (which comes from the tempo)
 377 and the meter in use at a particular time (how many  pulse divisions there are in one bar).
 378 It would be more accurate to substitute the work 'pulse' for 'beat' above.
 379
 380 Anyway ...
 381
 382 We can now store c for future time calculations.
 383 If the following tempo section (the one that defines c in conjunction with this one)
 384 is changed or moved, c is no longer valid.
 385
 386 The public methods are session-relative.
 387
 388 Most of this stuff is taken from this paper:
 389
 390 WHERE’S THE BEAT?
 391 TOOLS FOR DYNAMIC TEMPO CALCULATIONS
 392 Jan C. Schacher
 393 Martin Neukom
 394 Zurich University of Arts
 395 Institute for Computer Music and Sound Technology
 396
 397 https://www.zhdk.ch/fileadmin/data_subsites/data_icst/Downloads/Timegrid/ICST_Tempopolyphony_ICMC07.pdf
 398
 399 */
 400
 401 /*
 402   compute this ramp's function constant using the end tempo (in qn beats per minute)
 403   and duration (pulses into global start) of some later tempo section.
 404 */
 405 double
 406 TempoSection::compute_c_func_pulse (const double& end_bpm, const double& end_pulse) const
 407 {
 408         double const log_tempo_ratio = log (end_bpm / beats_per_minute());
 409         return (beats_per_minute() * expm1 (log_tempo_ratio)) / ((end_pulse - pulse()) * _note_type);
 410 }
 411
 412 /* compute the function constant from some later tempo section, given tempo (quarter notes/min.) and distance (in frames) from session origin */
 413 double
 414 TempoSection::compute_c_func_minute (const double& end_bpm, const double& end_minute) const
 415 {
 416         return c_func (end_bpm, end_minute - minute());
 417 }
 418
 419 /* position function */
 420 double
 421 TempoSection::a_func (double end_bpm, double c_func) const
 422 {
 423         return log (end_bpm / beats_per_minute()) / c_func;
 424 }
 425
 426 /*function constant*/
 427 double
 428 TempoSection::c_func (double end_bpm, double end_time) const
 429 {
 430         return log (end_bpm / beats_per_minute()) / end_time;
 431 }
 432
 433 /* tempo in bpm at time in minutes */
 434 double
 435 TempoSection::_tempo_at_time (const double& time) const
 436 {
 437         return exp (_c_func * time) * beats_per_minute();
 438 }
 439
 440 /* time in minutes at tempo in bpm */
 441 double
 442 TempoSection::_time_at_tempo (const double& tempo) const
 443 {
 444         return log (tempo / beats_per_minute()) / _c_func;
 445 }
 446
 447 /* pulse at tempo in bpm */
 448 double
 449 TempoSection::_pulse_at_tempo (const double& tempo) const
 450 {
 451         return ((tempo - beats_per_minute()) / _c_func) / _note_type;
 452 }
 453
 454 /* tempo in bpm at pulse */
 455 double
 456 TempoSection::_tempo_at_pulse (const double& pulse) const
 457 {
 458         return (pulse * _note_type * _c_func) + beats_per_minute();
 459 }
 460
 461 /* pulse at time in minutes */
 462 double
 463 TempoSection::_pulse_at_time (const double& time) const
 464 {
 465         return expm1 (_c_func * time) * (beats_per_minute() / (_c_func * _note_type));
 466 }
 467
 468 /* time in minutes at pulse */
 469 double
 470 TempoSection::_time_at_pulse (const double& pulse) const
 471 {
 472         return log1p ((_c_func * pulse * _note_type) / beats_per_minute()) / _c_func;
 473 }
 474
 475 /***********************************************************************/
 476
 477 const string MeterSection::xml_state_node_name = "Meter";
 478
 479 MeterSection::MeterSection (const XMLNode& node, const framecnt_t sample_rate)
 480         : MetricSection (0.0, 0, MusicTime, false, sample_rate), Meter (TempoMap::default_meter())
 481 {
 482         XMLProperty const * prop;
 483         LocaleGuard lg;
 484         BBT_Time bbt;
 485         double pulse = 0.0;
 486         double beat = 0.0;
 487         framepos_t frame = 0;
 488         pair<double, BBT_Time> start;
 489         double minute = 0.0;
 490
 491         if ((prop = node.property ("start")) != 0) {
 492                 if (sscanf (prop->value().c_str(), "%" PRIu32 "|%" PRIu32 "|%" PRIu32,
 493                     &bbt.bars,
 494                     &bbt.beats,
 495                     &bbt.ticks) < 3) {
 496                         error << _("MeterSection XML node has an illegal \"start\" value") << endmsg;
 497                 } else {
 498                         /* legacy session - start used to be in bbt*/
 499                         info << _("Legacy session detected - MeterSection XML node will be altered.") << endmsg;
 500                         pulse = -1.0;
 501                 }
 502         }
 503
 504         if ((prop = node.property ("pulse")) != 0) {
 505                 if (sscanf (prop->value().c_str(), "%lf", &pulse) != 1) {
 506                         error << _("MeterSection XML node has an illegal \"pulse\" value") << endmsg;
 507                 }
 508         }
 509         set_pulse (pulse);
 510
 511         if ((prop = node.property ("beat")) != 0) {
 512                 if (sscanf (prop->value().c_str(), "%lf", &beat) != 1) {
 513                         error << _("MeterSection XML node has an illegal \"beat\" value") << endmsg;
 514                 }
 515         }
 516
 517         start.first = beat;
 518
 519         if ((prop = node.property ("bbt")) == 0) {
 520                 warning << _("MeterSection XML node has no \"bbt\" property") << endmsg;
 521         } else if (sscanf (prop->value().c_str(), "%" PRIu32 "|%" PRIu32 "|%" PRIu32,
 522                     &bbt.bars,
 523                     &bbt.beats,
 524                     &bbt.ticks) < 3) {
 525                 error << _("MeterSection XML node has an illegal \"bbt\" value") << endmsg;
 526                 throw failed_constructor();
 527         }
 528
 529         start.second = bbt;
 530         set_beat (start);
 531
 532         if ((prop = node.property ("frame")) != 0) {
 533                 if (sscanf (prop->value().c_str(), "%li", &frame) != 1) {
 534                         error << _("MeterSection XML node has an illegal \"frame\" value") << endmsg;
 535                 } else {
 536                         set_minute (minute_at_frame (frame));
 537                 }
 538         }
 539         if ((prop = node.property ("minute")) != 0) {
 540                 if (sscanf (prop->value().c_str(), "%lf", &minute) != 1) {
 541                         error << _("MeterSection XML node has an illegal \"frame\" value") << endmsg;
 542                 } else {
 543                         set_minute (minute);
 544                 }
 545         }
 546
 547         /* beats-per-bar is old; divisions-per-bar is new */
 548
 549         if ((prop = node.property ("divisions-per-bar")) == 0) {
 550                 if ((prop = node.property ("beats-per-bar")) == 0) {
 551                         error << _("MeterSection XML node has no \"beats-per-bar\" or \"divisions-per-bar\" property") << endmsg;
 552                         throw failed_constructor();
 553                 }
 554         }
 555         if (sscanf (prop->value().c_str(), "%lf", &_divisions_per_bar) != 1 || _divisions_per_bar < 0.0) {
 556                 error << _("MeterSection XML node has an illegal \"divisions-per-bar\" value") << endmsg;
 557                 throw failed_constructor();
 558         }
 559
 560         if ((prop = node.property ("note-type")) == 0) {
 561                 error << _("MeterSection XML node has no \"note-type\" property") << endmsg;
 562                 throw failed_constructor();
 563         }
 564         if (sscanf (prop->value().c_str(), "%lf", &_note_type) != 1 || _note_type < 0.0) {
 565                 error << _("MeterSection XML node has an illegal \"note-type\" value") << endmsg;
 566                 throw failed_constructor();
 567         }
 568
 569         if ((prop = node.property ("movable")) == 0) {
 570                 error << _("MeterSection XML node has no \"movable\" property") << endmsg;
 571                 throw failed_constructor();
 572         }
 573
 574         set_movable (string_is_affirmative (prop->value()));
 575
 576         if ((prop = node.property ("lock-style")) == 0) {
 577                 warning << _("MeterSection XML node has no \"lock-style\" property") << endmsg;
 578                 if (movable()) {
 579                         set_position_lock_style (MusicTime);
 580                 } else {
 581                         set_position_lock_style (AudioTime);
 582                 }
 583         } else {
 584                 set_position_lock_style (PositionLockStyle (string_2_enum (prop->value(), position_lock_style())));
 585         }
 586 }
 587
 588 XMLNode&
 589 MeterSection::get_state() const
 590 {
 591         XMLNode *root = new XMLNode (xml_state_node_name);
 592         char buf[256];
 593         LocaleGuard lg;
 594
 595         snprintf (buf, sizeof (buf), "%lf", pulse());
 596         root->add_property ("pulse", buf);
 597         snprintf (buf, sizeof (buf), "%" PRIu32 "|%" PRIu32 "|%" PRIu32,
 598                   bbt().bars,
 599                   bbt().beats,
 600                   bbt().ticks);
 601         root->add_property ("bbt", buf);
 602         snprintf (buf, sizeof (buf), "%lf", beat());
 603         root->add_property ("beat", buf);
 604         snprintf (buf, sizeof (buf), "%lf", _note_type);
 605         root->add_property ("note-type", buf);
 606         snprintf (buf, sizeof (buf), "%li", frame());
 607         root->add_property ("frame", buf);
 608         snprintf (buf, sizeof (buf), "%lf", minute());
 609         root->add_property ("minute", buf);
 610         root->add_property ("lock-style", enum_2_string (position_lock_style()));
 611         snprintf (buf, sizeof (buf), "%lf", _divisions_per_bar);
 612         root->add_property ("divisions-per-bar", buf);
 613         snprintf (buf, sizeof (buf), "%s", movable()?"yes":"no");
 614         root->add_property ("movable", buf);
 615
 616         return *root;
 617 }
 618
 619 /***********************************************************************/
 620 /*
 621   Tempo Map Overview
 622
 623   The Shaggs - Things I Wonder
 624   https://www.youtube.com/watch?v=9wQK6zMJOoQ
 625
 626   Tempo is the rate of the musical pulse.
 627   Meter divides pulse into measures and beats.
 628
 629   TempoSection - provides pulse in the form of beats_per_minute() - the number of quarter notes in one minute.
 630   Note that 'beats' in Tempo::beats_per_minute() are quarter notes (pulse based). In the rest of tempo map,
 631   'beat' usually refers to accumulated BBT beats (pulse and meter based).
 632
 633   MeterSecion - divides pulse into measures (via divisions_per_bar) and beats (via note_divisor).
 634
 635   Both tempo and meter have a pulse position and a frame position.
 636   Meters also have a beat position, which is always 0.0 for the first one.
 637   TempoSection and MeterSection may be locked to either audio or music (position lock style).
 638   The lock style determines the 'true' position of the section wich is used to calculate the other postion parameters of the section.
 639
 640   The first tempo and first meter are special. they must move together, and must be locked to audio.
 641   Audio locked tempos which lie before the first meter are made inactive.
 642   They will be re-activated if the first meter is again placed before them.
 643
 644   With tempo sections potentially being ramped, meters provide a way of mapping beats to whole pulses without
 645   referring to the tempo function(s) involved as the distance in whole pulses between a meter and a subsequent beat is
 646   sb->beat() - meter->beat() / meter->note_divisor().
 647   Because every meter falls on a known pulse, (derived from its bar), the rest is easy as the duration in pulses between
 648   two meters is of course
 649   (meater_b->bar - meter_a->bar) * meter_a->divisions_per_bar / meter_a->note_divisor.
 650
 651   Beat calculations are based on meter sections and all pulse and tempo calculations are based on tempo sections.
 652   Beat to frame conversion of course requires the use of meter and tempo.
 653
 654   Remembering that ramped tempo sections interact, it is important to avoid referring to any other tempos when moving tempo sections,
 655   Here, beats (meters) are used to determine the new pulse (see predict_tempo_position())
 656
 657   Recomputing the map is the process where the 'missing' position
 658   (tempo pulse or meter pulse & beat in the case of AudioTime, frame for MusicTime) is calculated.
 659   We construct the tempo map by first using the frame or pulse position (depending on position lock style) of each tempo.
 660   We then use this tempo map (really just the tempos) to find the pulse or frame position of each meter (again depending on lock style).
 661
 662   Having done this, we can now find any musical duration by selecting the tempo and meter covering the position (or tempo) in question
 663   and querying its appropriate meter/tempo.
 664
 665   It is important to keep the _metrics in an order that makes sense.
 666   Because ramped MusicTime and AudioTime tempos can interact with each other,
 667   reordering is frequent. Care must be taken to keep _metrics in a solved state.
 668   Solved means ordered by frame or pulse with frame-accurate precision (see check_solved()).
 669
 670   Music and Audio
 671
 672   Music and audio-locked objects may seem interchangeable on the surface, but when translating
 673   between audio samples and beat, remember that a sample is only a quantised approximation
 674   of the actual time (in minutes) of a beat.
 675   Thus if a gui user points to the frame occupying the start of a music-locked object on 1|3|0, it does not
 676   mean that this frame is the actual location in time of 1|3|0.
 677
 678   You cannot use a frame measurement to determine beat distance except under special circumstances
 679   (e.g. where the user has requested that a beat lie on a SMPTE frame or if the tempo is known to be constant over the duration).
 680
 681   This means is that a user operating on a musical grid must supply the desired beat position and/or current beat quantization in order for the
 682   sample space the user is operating at to be translated correctly to the object.
 683
 684   The current approach is to interpret the supplied frame using the grid division the user has currently selected.
 685   If the user has no musical grid set, they are actually operating in sample space (even SMPTE frames are rounded to audio frame), so
 686   the supplied audio frame is interpreted as the desired musical location (beat_at_frame()).
 687
 688   tldr: Beat, being a function of time, has nothing to do with sample rate, but time quantization can get in the way of precision.
 689
 690   When frame_at_beat() is called, the position calculation is performed in pulses and minutes.
 691   The result is rounded to audio frames.
 692   When beat_at_frame() is called, the frame is converted to minutes, with no rounding performed on the result.
 693
 694   So :
 695   frame_at_beat (beat_at_frame (frame)) == frame
 696   but :
 697   beat_at_frame (frame_at_beat (beat)) != beat due to the time quantization of frame_at_beat().
 698
 699   Doing the second one will result in a beat distance error of up to 0.5 audio samples.
 700   So instead work in pulses and/or beats and only use beat position to caclulate frame position (e.g. after tempo change).
 701   For audio-locked objects, use frame position to calculate beat position.
 702
 703   The above pointless example would then do:
 704   beat_at_pulse (pulse_at_beat (beat)) to avoid rounding.
 705
 706 */
 707 struct MetricSectionSorter {
 708     bool operator() (const MetricSection* a, const MetricSection* b) {
 709             return a->pulse() < b->pulse();
 710     }
 711 };
 712
 713 struct MetricSectionFrameSorter {
 714     bool operator() (const MetricSection* a, const MetricSection* b) {
 715             return a->frame() < b->frame();
 716     }
 717 };
 718
 719 TempoMap::TempoMap (framecnt_t fr)
 720 {
 721         _frame_rate = fr;
 722         BBT_Time start (1, 1, 0);
 723
 724         TempoSection *t = new TempoSection (0.0, 0.0, _default_tempo.beats_per_minute(), _default_tempo.note_type(), TempoSection::Ramp, AudioTime, fr);
 725         MeterSection *m = new MeterSection (0.0, 0.0, 0.0, start, _default_meter.divisions_per_bar(), _default_meter.note_divisor(), AudioTime, fr);
 726
 727         t->set_movable (false);
 728         m->set_movable (false);
 729
 730         /* note: frame time is correct (zero) for both of these */
 731
 732         _metrics.push_back (t);
 733         _metrics.push_back (m);
 734
 735 }
 736
 737 TempoMap::~TempoMap ()
 738 {
 739         Metrics::const_iterator d = _metrics.begin();
 740         while (d != _metrics.end()) {
 741                 delete (*d);
 742                 ++d;
 743         }
 744         _metrics.clear();
 745 }
 746
 747 framepos_t
 748 TempoMap::frame_at_minute (const double time) const
 749 {
 750         return (framepos_t) floor ((time * 60.0 * _frame_rate) + 0.5);
 751 }
 752
 753 double
 754 TempoMap::minute_at_frame (const framepos_t frame) const
 755 {
 756         return (frame / (double) _frame_rate) / 60.0;
 757 }
 758
 759 void
 760 TempoMap::remove_tempo (const TempoSection& tempo, bool complete_operation)
 761 {
 762         bool removed = false;
 763
 764         {
 765                 Glib::Threads::RWLock::WriterLock lm (lock);
 766                 if ((removed = remove_tempo_locked (tempo))) {
 767                         if (complete_operation) {
 768                                 recompute_map (_metrics);
 769                         }
 770                 }
 771         }
 772
 773         if (removed && complete_operation) {
 774                 PropertyChanged (PropertyChange ());
 775         }
 776 }
 777
 778 bool
 779 TempoMap::remove_tempo_locked (const TempoSection& tempo)
 780 {
 781         Metrics::iterator i;
 782
 783         for (i = _metrics.begin(); i != _metrics.end(); ++i) {
 784                 if (dynamic_cast<TempoSection*> (*i) != 0) {
 785                         if (tempo.frame() == (*i)->frame()) {
 786                                 if ((*i)->movable()) {
 787                                         delete (*i);
 788                                         _metrics.erase (i);
 789                                         return true;
 790                                 }
 791                         }
 792                 }
 793         }
 794
 795         return false;
 796 }
 797
 798 void
 799 TempoMap::remove_meter (const MeterSection& tempo, bool complete_operation)
 800 {
 801         bool removed = false;
 802
 803         {
 804                 Glib::Threads::RWLock::WriterLock lm (lock);
 805                 if ((removed = remove_meter_locked (tempo))) {
 806                         if (complete_operation) {
 807                                 recompute_map (_metrics);
 808                         }
 809                 }
 810         }
 811
 812         if (removed && complete_operation) {
 813                 PropertyChanged (PropertyChange ());
 814         }
 815 }
 816
 817 bool
 818 TempoMap::remove_meter_locked (const MeterSection& meter)
 819 {
 820
 821         if (meter.position_lock_style() == AudioTime) {
 822                 /* remove meter-locked tempo */
 823                 for (Metrics::iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
 824                         TempoSection* t = 0;
 825                         if ((t = dynamic_cast<TempoSection*> (*i)) != 0) {
 826                                 if (t->locked_to_meter() && meter.frame() == (*i)->frame()) {
 827                                         delete (*i);
 828                                         _metrics.erase (i);
 829                                         break;
 830                                 }
 831                         }
 832                 }
 833         }
 834
 835         for (Metrics::iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
 836                 if (dynamic_cast<MeterSection*> (*i) != 0) {
 837                         if (meter.frame() == (*i)->frame()) {
 838                                 if ((*i)->movable()) {
 839                                         delete (*i);
 840                                         _metrics.erase (i);
 841                                         return true;
 842                                 }
 843                         }
 844                 }
 845         }
 846
 847         return false;
 848 }
 849
 850 void
 851 TempoMap::do_insert (MetricSection* section)
 852 {
 853         bool need_add = true;
 854         /* we only allow new meters to be inserted on beat 1 of an existing
 855          * measure.
 856          */
 857         MeterSection* m = 0;
 858         if ((m = dynamic_cast<MeterSection*>(section)) != 0) {
 859
 860                 if ((m->bbt().beats != 1) || (m->bbt().ticks != 0)) {
 861
 862                         pair<double, BBT_Time> corrected = make_pair (m->beat(), m->bbt());
 863                         corrected.second.beats = 1;
 864                         corrected.second.ticks = 0;
 865                         corrected.first = beat_at_bbt_locked (_metrics, corrected.second);
 866                         warning << string_compose (_("Meter changes can only be positioned on the first beat of a bar. Moving from %1 to %2"),
 867                                                    m->bbt(), corrected.second) << endmsg;
 868                         //m->set_pulse (corrected);
 869                 }
 870         }
 871
 872         /* Look for any existing MetricSection that is of the same type and
 873            in the same bar as the new one, and remove it before adding
 874            the new one. Note that this means that if we find a matching,
 875            existing section, we can break out of the loop since we're
 876            guaranteed that there is only one such match.
 877         */
 878
 879         for (Metrics::iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
 880
 881                 TempoSection* const tempo = dynamic_cast<TempoSection*> (*i);
 882                 TempoSection* const insert_tempo = dynamic_cast<TempoSection*> (section);
 883                 MeterSection* const meter = dynamic_cast<MeterSection*> (*i);
 884                 MeterSection* const insert_meter = dynamic_cast<MeterSection*> (section);
 885
 886                 if (tempo && insert_tempo) {
 887
 888                         /* Tempo sections */
 889                         bool const ipm = insert_tempo->position_lock_style() == MusicTime;
 890                         if ((ipm && tempo->pulse() == insert_tempo->pulse()) || (!ipm && tempo->frame() == insert_tempo->frame())) {
 891
 892                                 if (!tempo->movable()) {
 893
 894                                         /* can't (re)move this section, so overwrite
 895                                          * its data content (but not its properties as
 896                                          * a section).
 897                                          */
 898
 899                                         *(dynamic_cast<Tempo*>(*i)) = *(dynamic_cast<Tempo*>(insert_tempo));
 900                                         (*i)->set_position_lock_style (AudioTime);
 901                                         TempoSection* t;
 902                                         if ((t = dynamic_cast<TempoSection*>(*i)) != 0) {
 903                                                 t->set_type (insert_tempo->type());
 904                                         }
 905                                         need_add = false;
 906                                 } else {
 907                                         delete (*i);
 908                                         _metrics.erase (i);
 909                                 }
 910                                 break;
 911                         }
 912
 913                 } else if (meter && insert_meter) {
 914
 915                         /* Meter Sections */
 916
 917                         bool const ipm = insert_meter->position_lock_style() == MusicTime;
 918
 919                         if ((ipm && meter->beat() == insert_meter->beat()) || (!ipm && meter->frame() == insert_meter->frame())) {
 920
 921                                 if (!meter->movable()) {
 922
 923                                         /* can't (re)move this section, so overwrite
 924                                          * its data content (but not its properties as
 925                                          * a section
 926                                          */
 927
 928                                         *(dynamic_cast<Meter*>(*i)) = *(dynamic_cast<Meter*>(insert_meter));
 929                                         (*i)->set_position_lock_style (AudioTime);
 930                                         need_add = false;
 931                                 } else {
 932                                         delete (*i);
 933                                         _metrics.erase (i);
 934                                 }
 935
 936                                 break;
 937                         }
 938                 } else {
 939                         /* non-matching types, so we don't care */
 940                 }
 941         }
 942
 943         /* Add the given MetricSection, if we didn't just reset an existing
 944          * one above
 945          */
 946
 947         if (need_add) {
 948                 MeterSection* const insert_meter = dynamic_cast<MeterSection*> (section);
 949                 TempoSection* const insert_tempo = dynamic_cast<TempoSection*> (section);
 950                 Metrics::iterator i;
 951                 if (insert_meter) {
 952                         for (i = _metrics.begin(); i != _metrics.end(); ++i) {
 953                                 MeterSection* const meter = dynamic_cast<MeterSection*> (*i);
 954
 955                                 if (meter) {
 956                                         bool const ipm = insert_meter->position_lock_style() == MusicTime;
 957                                         if ((ipm && meter->beat() > insert_meter->beat()) || (!ipm && meter->frame() > insert_meter->frame())) {
 958                                                 break;
 959                                         }
 960                                 }
 961                         }
 962                 } else if (insert_tempo) {
 963                         for (i = _metrics.begin(); i != _metrics.end(); ++i) {
 964                                 TempoSection* const tempo = dynamic_cast<TempoSection*> (*i);
 965
 966                                 if (tempo) {
 967                                         bool const ipm = insert_tempo->position_lock_style() == MusicTime;
 968                                         if ((ipm && tempo->pulse() > insert_tempo->pulse()) || (!ipm && tempo->frame() > insert_tempo->frame())) {
 969                                                 break;
 970                                         }
 971                                 }
 972                         }
 973                 }
 974
 975                 _metrics.insert (i, section);
 976                 //dump (_metrics, std::cout);
 977         }
 978 }
 979 /* user supplies the exact pulse if pls == MusicTime */
 980 TempoSection*
 981 TempoMap::add_tempo (const Tempo& tempo, const double& pulse, const framepos_t& frame, ARDOUR::TempoSection::Type type, PositionLockStyle pls)
 982 {
 983         TempoSection* ts = 0;
 984         {
 985                 Glib::Threads::RWLock::WriterLock lm (lock);
 986                 ts = add_tempo_locked (tempo, pulse, minute_at_frame (frame), type, pls, true);
 987         }
 988
 989
 990         PropertyChanged (PropertyChange ());
 991
 992         return ts;
 993 }
 994
 995 void
 996 TempoMap::replace_tempo (const TempoSection& ts, const Tempo& tempo, const double& pulse, const framepos_t& frame, TempoSection::Type type, PositionLockStyle pls)
 997 {
 998         const bool locked_to_meter = ts.locked_to_meter();
 999
1000         {
1001                 Glib::Threads::RWLock::WriterLock lm (lock);
1002                 TempoSection& first (first_tempo());
1003                 if (ts.frame() != first.frame()) {
1004                         remove_tempo_locked (ts);
1005                         add_tempo_locked (tempo, pulse, minute_at_frame (frame), type, pls, true, locked_to_meter);
1006                 } else {
1007                         first.set_type (type);
1008                         first.set_pulse (0.0);
1009                         first.set_minute (minute_at_frame (frame));
1010                         first.set_position_lock_style (AudioTime);
1011                         {
1012                                 /* cannot move the first tempo section */
1013                                 *static_cast<Tempo*>(&first) = tempo;
1014                                 recompute_map (_metrics);
1015                         }
1016                 }
1017         }
1018
1019         PropertyChanged (PropertyChange ());
1020 }
1021
1022 TempoSection*
1023 TempoMap::add_tempo_locked (const Tempo& tempo, double pulse, double minute
1024                             , TempoSection::Type type, PositionLockStyle pls, bool recompute, bool locked_to_meter)
1025 {
1026         TempoSection* t = new TempoSection (pulse, minute, tempo.beats_per_minute(), tempo.note_type(), type, pls, _frame_rate);
1027         t->set_locked_to_meter (locked_to_meter);
1028         bool solved = false;
1029
1030         do_insert (t);
1031
1032         if (recompute) {
1033                 if (pls == AudioTime) {
1034                         solved = solve_map_minute (_metrics, t, t->minute());
1035                 } else {
1036                         solved = solve_map_pulse (_metrics, t, t->pulse());
1037                 }
1038                 recompute_meters (_metrics);
1039         }
1040
1041         if (!solved && recompute) {
1042                 recompute_map (_metrics);
1043         }
1044
1045         return t;
1046 }
1047
1048 MeterSection*
1049 TempoMap::add_meter (const Meter& meter, const double& beat, const Timecode::BBT_Time& where, PositionLockStyle pls)
1050 {
1051         MeterSection* m = 0;
1052         {
1053                 Glib::Threads::RWLock::WriterLock lm (lock);
1054                 m = add_meter_locked (meter, beat, where, pls, true);
1055         }
1056
1057
1058 #ifndef NDEBUG
1059         if (DEBUG_ENABLED(DEBUG::TempoMap)) {
1060                 dump (_metrics, std::cerr);
1061         }
1062 #endif
1063
1064         PropertyChanged (PropertyChange ());
1065         return m;
1066 }
1067
1068 void
1069 TempoMap::replace_meter (const MeterSection& ms, const Meter& meter, const BBT_Time& where, PositionLockStyle pls)
1070 {
1071         {
1072                 Glib::Threads::RWLock::WriterLock lm (lock);
1073                 const double beat = beat_at_bbt_locked (_metrics, where);
1074
1075                 if (ms.movable()) {
1076                         remove_meter_locked (ms);
1077                         add_meter_locked (meter, beat, where, pls, true);
1078                 } else {
1079                         MeterSection& first (first_meter());
1080                         TempoSection& first_t (first_tempo());
1081                         /* cannot move the first meter section */
1082                         *static_cast<Meter*>(&first) = meter;
1083                         first.set_position_lock_style (AudioTime);
1084                         first.set_pulse (0.0);
1085                         //first.set_minute (minute_at_frame (frame));
1086                         pair<double, BBT_Time> beat = make_pair (0.0, BBT_Time (1, 1, 0));
1087                         first.set_beat (beat);
1088                         first_t.set_minute (first.minute());
1089                         first_t.set_pulse (0.0);
1090                         first_t.set_position_lock_style (AudioTime);
1091                         recompute_map (_metrics);
1092                 }
1093         }
1094
1095         PropertyChanged (PropertyChange ());
1096 }
1097
1098 MeterSection*
1099 TempoMap::add_meter_locked (const Meter& meter, double beat, const BBT_Time& where, PositionLockStyle pls, bool recompute)
1100 {
1101         const MeterSection& prev_m = meter_section_at_minute_locked  (_metrics, minute_at_beat_locked (_metrics, beat) - minute_at_frame (1));
1102         const double pulse = ((where.bars - prev_m.bbt().bars) * (prev_m.divisions_per_bar() / prev_m.note_divisor())) + prev_m.pulse();
1103         const double time_minutes = minute_at_pulse_locked (_metrics, pulse);
1104         TempoSection* mlt = 0;
1105
1106         if (pls == AudioTime) {
1107                 /* add meter-locked tempo */
1108                 mlt = add_tempo_locked (tempo_at_minute_locked (_metrics, time_minutes), pulse,  time_minutes, TempoSection::Ramp, AudioTime, true, true);
1109
1110                 if (!mlt) {
1111                         return 0;
1112                 }
1113
1114         }
1115
1116         MeterSection* new_meter = new MeterSection (pulse, time_minutes, beat, where, meter.divisions_per_bar(), meter.note_divisor(), pls, _frame_rate);
1117         bool solved = false;
1118
1119         do_insert (new_meter);
1120
1121         if (recompute) {
1122
1123                 if (pls == AudioTime) {
1124                         solved = solve_map_minute (_metrics, new_meter, time_minutes);
1125                 } else {
1126                         solved = solve_map_bbt (_metrics, new_meter, where);
1127                         /* required due to resetting the pulse of meter-locked tempi above.
1128                            Arguably  solve_map_bbt() should use solve_map_pulse (_metrics, TempoSection) instead,
1129                            but afaict this cannot cause the map to be left unsolved (these tempi are all audio locked).
1130                         */
1131                         recompute_map (_metrics);
1132                 }
1133         }
1134
1135         if (!solved && recompute) {
1136                 /* if this has failed to solve, there is little we can do other than to ensure that
1137                    the new map is recalculated.
1138                 */
1139                 warning << "Adding meter may have left the tempo map unsolved." << endmsg;
1140                 recompute_map (_metrics);
1141         }
1142
1143         return new_meter;
1144 }
1145
1146 void
1147 TempoMap::change_initial_tempo (double beats_per_minute, double note_type)
1148 {
1149         Tempo newtempo (beats_per_minute, note_type);
1150         TempoSection* t;
1151
1152         for (Metrics::iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
1153                 if ((t = dynamic_cast<TempoSection*> (*i)) != 0) {
1154                         if (!t->active()) {
1155                                 continue;
1156                         }
1157                         {
1158                                 Glib::Threads::RWLock::WriterLock lm (lock);
1159                                 *((Tempo*) t) = newtempo;
1160                                 recompute_map (_metrics);
1161                         }
1162                         PropertyChanged (PropertyChange ());
1163                         break;
1164                 }
1165         }
1166 }
1167
1168 void
1169 TempoMap::change_existing_tempo_at (framepos_t where, double beats_per_minute, double note_type)
1170 {
1171         Tempo newtempo (beats_per_minute, note_type);
1172
1173         TempoSection* prev;
1174         TempoSection* first;
1175         Metrics::iterator i;
1176
1177         /* find the TempoSection immediately preceding "where"
1178          */
1179
1180         for (first = 0, i = _metrics.begin(), prev = 0; i != _metrics.end(); ++i) {
1181
1182                 if ((*i)->frame() > where) {
1183                         break;
1184                 }
1185
1186                 TempoSection* t;
1187
1188                 if ((t = dynamic_cast<TempoSection*>(*i)) != 0) {
1189                         if (!t->active()) {
1190                                 continue;
1191                         }
1192                         if (!first) {
1193                                 first = t;
1194                         }
1195                         prev = t;
1196                 }
1197         }
1198
1199         if (!prev) {
1200                 if (!first) {
1201                         error << string_compose (_("no tempo sections defined in tempo map - cannot change tempo @ %1"), where) << endmsg;
1202                         return;
1203                 }
1204
1205                 prev = first;
1206         }
1207
1208         /* reset */
1209
1210         {
1211                 Glib::Threads::RWLock::WriterLock lm (lock);
1212                 /* cannot move the first tempo section */
1213                 *((Tempo*)prev) = newtempo;
1214                 recompute_map (_metrics);
1215         }
1216
1217         PropertyChanged (PropertyChange ());
1218 }
1219
1220 const MeterSection&
1221 TempoMap::first_meter () const
1222 {
1223         const MeterSection *m = 0;
1224
1225         for (Metrics::const_iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
1226                 if ((m = dynamic_cast<const MeterSection *> (*i)) != 0) {
1227                         return *m;
1228                 }
1229         }
1230
1231         fatal << _("programming error: no meter section in tempo map!") << endmsg;
1232         abort(); /*NOTREACHED*/
1233         return *m;
1234 }
1235
1236 MeterSection&
1237 TempoMap::first_meter ()
1238 {
1239         MeterSection *m = 0;
1240
1241         /* CALLER MUST HOLD LOCK */
1242
1243         for (Metrics::iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
1244                 if ((m = dynamic_cast<MeterSection *> (*i)) != 0) {
1245                         return *m;
1246                 }
1247         }
1248
1249         fatal << _("programming error: no tempo section in tempo map!") << endmsg;
1250         abort(); /*NOTREACHED*/
1251         return *m;
1252 }
1253
1254 const TempoSection&
1255 TempoMap::first_tempo () const
1256 {
1257         const TempoSection *t = 0;
1258
1259         /* CALLER MUST HOLD LOCK */
1260
1261         for (Metrics::const_iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
1262                 if ((t = dynamic_cast<const TempoSection *> (*i)) != 0) {
1263                         if (!t->active()) {
1264                                 continue;
1265                         }
1266                         if (!t->movable()) {
1267                                 return *t;
1268                         }
1269                 }
1270         }
1271
1272         fatal << _("programming error: no tempo section in tempo map!") << endmsg;
1273         abort(); /*NOTREACHED*/
1274         return *t;
1275 }
1276
1277 TempoSection&
1278 TempoMap::first_tempo ()
1279 {
1280         TempoSection *t = 0;
1281
1282         for (Metrics::const_iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
1283                 if ((t = dynamic_cast<TempoSection *> (*i)) != 0) {
1284                         if (!t->active()) {
1285                                 continue;
1286                         }
1287                         if (!t->movable()) {
1288                                 return *t;
1289                         }
1290                 }
1291         }
1292
1293         fatal << _("programming error: no tempo section in tempo map!") << endmsg;
1294         abort(); /*NOTREACHED*/
1295         return *t;
1296 }
1297 void
1298 TempoMap::recompute_tempi (Metrics& metrics)
1299 {
1300         TempoSection* prev_t = 0;
1301
1302         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1303                 TempoSection* t;
1304
1305                 if ((*i)->is_tempo()) {
1306                         t = static_cast<TempoSection*> (*i);
1307                         if (!t->active()) {
1308                                 continue;
1309                         }
1310                         if (!t->movable()) {
1311                                 if (!prev_t) {
1312                                         t->set_pulse (0.0);
1313                                         prev_t = t;
1314                                         continue;
1315                                 }
1316                         }
1317                         if (prev_t) {
1318                                 if (t->position_lock_style() == AudioTime) {
1319                                         prev_t->set_c_func (prev_t->compute_c_func_minute (t->beats_per_minute(), t->minute()));
1320                                         if (!t->locked_to_meter()) {
1321                                                 t->set_pulse (prev_t->pulse_at_tempo (t->beats_per_minute(), t->minute()));
1322                                         }
1323
1324                                 } else {
1325                                         prev_t->set_c_func (prev_t->compute_c_func_pulse (t->beats_per_minute(), t->pulse()));
1326                                         t->set_minute (prev_t->minute_at_tempo (t->beats_per_minute(), t->pulse()));
1327
1328                                 }
1329                         }
1330                         prev_t = t;
1331                 }
1332         }
1333         prev_t->set_c_func (0.0);
1334 }
1335
1336 /* tempos must be positioned correctly.
1337    the current approach is to use a meter's bbt time as its base position unit.
1338    an audio-locked meter requires a recomputation of pulse and beat (but not bbt),
1339    while a music-locked meter requires recomputations of frame pulse and beat (but not bbt)
1340 */
1341 void
1342 TempoMap::recompute_meters (Metrics& metrics)
1343 {
1344         MeterSection* meter = 0;
1345         MeterSection* prev_m = 0;
1346
1347         for (Metrics::const_iterator mi = metrics.begin(); mi != metrics.end(); ++mi) {
1348                 if (!(*mi)->is_tempo()) {
1349                         meter = static_cast<MeterSection*> (*mi);
1350                         if (meter->position_lock_style() == AudioTime) {
1351                                 double pulse = 0.0;
1352                                 pair<double, BBT_Time> b_bbt;
1353                                 TempoSection* meter_locked_tempo = 0;
1354                                 for (Metrics::const_iterator ii = metrics.begin(); ii != metrics.end(); ++ii) {
1355                                         TempoSection* t;
1356                                         if ((*ii)->is_tempo()) {
1357                                                 t = static_cast<TempoSection*> (*ii);
1358                                                 if ((t->locked_to_meter() || !t->movable()) && t->frame() == meter->frame()) {
1359                                                         meter_locked_tempo = t;
1360                                                         break;
1361                                                 }
1362                                         }
1363                                 }
1364
1365                                 if (prev_m) {
1366                                         const double beats = (meter->bbt().bars - prev_m->bbt().bars) * prev_m->divisions_per_bar();
1367                                         if (beats + prev_m->beat() != meter->beat()) {
1368                                                 /* reordering caused a bbt change */
1369                                                 b_bbt = make_pair (beats + prev_m->beat()
1370                                                                    , BBT_Time ((beats / prev_m->divisions_per_bar()) + prev_m->bbt().bars, 1, 0));
1371                                                 pulse = prev_m->pulse() + (beats / prev_m->note_divisor());
1372
1373                                         } else if (meter->movable()) {
1374                                                 b_bbt = make_pair (meter->beat(), meter->bbt());
1375                                                 pulse = prev_m->pulse() + (beats / prev_m->note_divisor());
1376                                         }
1377                                 } else {
1378                                         b_bbt = make_pair (0.0, BBT_Time (1, 1, 0));
1379                                 }
1380                                 if (meter_locked_tempo) {
1381                                         meter_locked_tempo->set_pulse (pulse);
1382                                 }
1383                                 meter->set_beat (b_bbt);
1384                                 meter->set_pulse (pulse);
1385
1386                         } else {
1387                                 /* MusicTime */
1388                                 double pulse = 0.0;
1389                                 pair<double, BBT_Time> b_bbt;
1390                                 if (prev_m) {
1391                                         const double beats = (meter->bbt().bars - prev_m->bbt().bars) * prev_m->divisions_per_bar();
1392                                         if (beats + prev_m->beat() != meter->beat()) {
1393                                                 /* reordering caused a bbt change */
1394                                                 b_bbt = make_pair (beats + prev_m->beat()
1395                                                                    , BBT_Time ((beats / prev_m->divisions_per_bar()) + prev_m->bbt().bars, 1, 0));
1396                                         } else {
1397                                                 b_bbt = make_pair (beats + prev_m->beat(), meter->bbt());
1398                                         }
1399                                         pulse = (beats / prev_m->note_divisor()) + prev_m->pulse();
1400                                 } else {
1401                                         /* shouldn't happen - the first is audio-locked */
1402                                         pulse = pulse_at_beat_locked (metrics, meter->beat());
1403                                         b_bbt = make_pair (meter->beat(), meter->bbt());
1404                                 }
1405
1406                                 meter->set_beat (b_bbt);
1407                                 meter->set_pulse (pulse);
1408                                 meter->set_minute (minute_at_pulse_locked (metrics, pulse));
1409                         }
1410
1411                         prev_m = meter;
1412                 }
1413         }
1414 }
1415
1416 void
1417 TempoMap::recompute_map (Metrics& metrics, framepos_t end)
1418 {
1419         /* CALLER MUST HOLD WRITE LOCK */
1420
1421         DEBUG_TRACE (DEBUG::TempoMath, string_compose ("recomputing tempo map, zero to %1\n", end));
1422
1423         if (end == 0) {
1424                 /* silly call from Session::process() during startup
1425                  */
1426                 return;
1427         }
1428
1429         recompute_tempi (metrics);
1430         recompute_meters (metrics);
1431 }
1432
1433 TempoMetric
1434 TempoMap::metric_at (framepos_t frame, Metrics::const_iterator* last) const
1435 {
1436         Glib::Threads::RWLock::ReaderLock lm (lock);
1437         TempoMetric m (first_meter(), first_tempo());
1438
1439         /* at this point, we are *guaranteed* to have m.meter and m.tempo pointing
1440            at something, because we insert the default tempo and meter during
1441            TempoMap construction.
1442
1443            now see if we can find better candidates.
1444         */
1445
1446         for (Metrics::const_iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
1447
1448                 if ((*i)->frame() > frame) {
1449                         break;
1450                 }
1451
1452                 m.set_metric(*i);
1453
1454                 if (last) {
1455                         *last = i;
1456                 }
1457         }
1458
1459         return m;
1460 }
1461
1462 /* XX meters only */
1463 TempoMetric
1464 TempoMap::metric_at (BBT_Time bbt) const
1465 {
1466         Glib::Threads::RWLock::ReaderLock lm (lock);
1467         TempoMetric m (first_meter(), first_tempo());
1468
1469         /* at this point, we are *guaranteed* to have m.meter and m.tempo pointing
1470            at something, because we insert the default tempo and meter during
1471            TempoMap construction.
1472
1473            now see if we can find better candidates.
1474         */
1475
1476         for (Metrics::const_iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
1477                 MeterSection* mw;
1478                 if (!(*i)->is_tempo()) {
1479                         mw = static_cast<MeterSection*> (*i);
1480                         BBT_Time section_start (mw->bbt());
1481
1482                         if (section_start.bars > bbt.bars || (section_start.bars == bbt.bars && section_start.beats > bbt.beats)) {
1483                                 break;
1484                         }
1485
1486                         m.set_metric (*i);
1487                 }
1488         }
1489
1490         return m;
1491 }
1492
1493 /** Returns the beat duration corresponding to the supplied frame, possibly returning a negative value.
1494  * @param frame The session frame position.
1495  * @return The beat duration according to the tempo map at the supplied frame.
1496  * If the supplied frame lies before the first meter, the returned beat duration will be negative.
1497  * The returned beat is obtained using the first meter and the continuation of the tempo curve (backwards).
1498  *
1499  * This function uses both tempo and meter.
1500  */
1501 double
1502 TempoMap::beat_at_frame (const framecnt_t& frame) const
1503 {
1504         Glib::Threads::RWLock::ReaderLock lm (lock);
1505
1506         return beat_at_minute_locked (_metrics, minute_at_frame (frame));
1507 }
1508
1509 /* This function uses both tempo and meter.*/
1510 double
1511 TempoMap::beat_at_minute_locked (const Metrics& metrics, const double& minute) const
1512 {
1513         const TempoSection& ts = tempo_section_at_minute_locked (metrics, minute);
1514         MeterSection* prev_m = 0;
1515         MeterSection* next_m = 0;
1516
1517         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1518                 if (!(*i)->is_tempo()) {
1519                         if (prev_m && (*i)->minute() > minute) {
1520                                 next_m = static_cast<MeterSection*> (*i);
1521                                 break;
1522                         }
1523                         prev_m = static_cast<MeterSection*> (*i);
1524                 }
1525         }
1526
1527         const double beat = prev_m->beat() + (ts.pulse_at_minute (minute) - prev_m->pulse()) * prev_m->note_divisor();
1528
1529         /* audio locked meters fake their beat */
1530         if (next_m && next_m->beat() < beat) {
1531                 return next_m->beat();
1532         }
1533
1534         return beat;
1535 }
1536
1537 framepos_t
1538 TempoMap::frame_at_beat (const double& beat) const
1539 {
1540         Glib::Threads::RWLock::ReaderLock lm (lock);
1541
1542         return frame_at_minute (minute_at_beat_locked (_metrics, beat));
1543 }
1544
1545 /* meter & tempo section based */
1546 double
1547 TempoMap::minute_at_beat_locked (const Metrics& metrics, const double& beat) const
1548 {
1549         MeterSection* prev_m = 0;
1550         TempoSection* prev_t = 0;
1551
1552         MeterSection* m;
1553
1554         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1555                 if (!(*i)->is_tempo()) {
1556                         m = static_cast<MeterSection*> (*i);
1557                         if (prev_m && m->beat() > beat) {
1558                                 break;
1559                         }
1560                         prev_m = m;
1561                 }
1562         }
1563
1564         TempoSection* t;
1565
1566         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1567                 if ((*i)->is_tempo()) {
1568                         t = static_cast<TempoSection*> (*i);
1569                         if (prev_t && ((t->pulse() - prev_m->pulse()) * prev_m->note_divisor()) + prev_m->beat() > beat) {
1570                                 break;
1571                         }
1572                         prev_t = t;
1573                 }
1574
1575         }
1576
1577         return prev_t->minute_at_pulse (((beat - prev_m->beat()) / prev_m->note_divisor()) + prev_m->pulse());
1578 }
1579
1580 Tempo
1581 TempoMap::tempo_at_frame (const framepos_t& frame) const
1582 {
1583         Glib::Threads::RWLock::ReaderLock lm (lock);
1584
1585         return tempo_at_minute_locked (_metrics, minute_at_frame (frame));
1586 }
1587
1588 Tempo
1589 TempoMap::tempo_at_minute_locked (const Metrics& metrics, const double& minute) const
1590 {
1591         TempoSection* prev_t = 0;
1592
1593         TempoSection* t;
1594
1595         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1596                 if ((*i)->is_tempo()) {
1597                         t = static_cast<TempoSection*> (*i);
1598                         if (!t->active()) {
1599                                 continue;
1600                         }
1601                         if ((prev_t) && t->minute() > minute) {
1602                                 /* t is the section past frame */
1603                                 const double ret_bpm = prev_t->tempo_at_minute (minute);
1604                                 const Tempo ret_tempo (ret_bpm, prev_t->note_type());
1605                                 return ret_tempo;
1606                         }
1607                         prev_t = t;
1608                 }
1609         }
1610
1611         const double ret = prev_t->beats_per_minute();
1612         const Tempo ret_tempo (ret, prev_t->note_type ());
1613
1614         return ret_tempo;
1615 }
1616
1617 /** returns the frame at which the supplied tempo occurs, or
1618  *  the frame of the last tempo section (search exhausted)
1619  *  only the position of the first occurence will be returned
1620  *  (extend me)
1621 */
1622 framepos_t
1623 TempoMap::frame_at_tempo (const Tempo& tempo) const
1624 {
1625         Glib::Threads::RWLock::ReaderLock lm (lock);
1626
1627         return frame_at_minute (minute_at_tempo_locked (_metrics, tempo));
1628 }
1629
1630 double
1631 TempoMap::minute_at_tempo_locked (const Metrics& metrics, const Tempo& tempo) const
1632 {
1633         TempoSection* prev_t = 0;
1634         const double tempo_bpm = tempo.beats_per_minute();
1635
1636         Metrics::const_iterator i;
1637
1638         for (i = metrics.begin(); i != metrics.end(); ++i) {
1639                 TempoSection* t;
1640                 if ((*i)->is_tempo()) {
1641                         t = static_cast<TempoSection*> (*i);
1642
1643                         if (!t->active()) {
1644                                 continue;
1645                         }
1646
1647                         const double t_bpm = t->beats_per_minute();
1648
1649                         if (t_bpm == tempo_bpm) {
1650                                 return t->minute();
1651                         }
1652
1653                         if (prev_t) {
1654                                 const double prev_t_bpm = prev_t->beats_per_minute();
1655
1656                                 if ((t_bpm > tempo_bpm && prev_t_bpm < tempo_bpm) || (t_bpm < tempo_bpm && prev_t_bpm > tempo_bpm)) {
1657                                         return prev_t->minute_at_tempo (tempo_bpm, prev_t->pulse());
1658                                 }
1659                         }
1660                         prev_t = t;
1661                 }
1662         }
1663
1664         return prev_t->minute();
1665 }
1666
1667 Tempo
1668 TempoMap::tempo_at_pulse_locked (const Metrics& metrics, const double& pulse) const
1669 {
1670         TempoSection* prev_t = 0;
1671
1672         TempoSection* t;
1673
1674         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1675                 if ((*i)->is_tempo()) {
1676                         t = static_cast<TempoSection*> (*i);
1677                         if (!t->active()) {
1678                                 continue;
1679                         }
1680                         if ((prev_t) && t->pulse() > pulse) {
1681                                 /* t is the section past frame */
1682                                 const double ret_bpm = prev_t->tempo_at_pulse (pulse);
1683                                 const Tempo ret_tempo (ret_bpm, prev_t->note_type());
1684                                 return ret_tempo;
1685                         }
1686                         prev_t = t;
1687                 }
1688         }
1689
1690         const double ret = prev_t->beats_per_minute();
1691         const Tempo ret_tempo (ret, prev_t->note_type ());
1692
1693         return ret_tempo;
1694 }
1695
1696 double
1697 TempoMap::pulse_at_tempo_locked (const Metrics& metrics, const Tempo& tempo) const
1698 {
1699         TempoSection* prev_t = 0;
1700         const double tempo_bpm = tempo.beats_per_minute();
1701
1702         Metrics::const_iterator i;
1703
1704         for (i = metrics.begin(); i != metrics.end(); ++i) {
1705                 TempoSection* t;
1706                 if ((*i)->is_tempo()) {
1707                         t = static_cast<TempoSection*> (*i);
1708
1709                         if (!t->active()) {
1710                                 continue;
1711                         }
1712
1713                         const double t_bpm = t->beats_per_minute();
1714
1715                         if (t_bpm == tempo_bpm) {
1716                                 return t->pulse();
1717                         }
1718
1719                         if (prev_t) {
1720                                 const double prev_t_bpm = prev_t->beats_per_minute();
1721
1722                                 if ((t_bpm > tempo_bpm && prev_t_bpm < tempo_bpm) || (t_bpm < tempo_bpm && prev_t_bpm > tempo_bpm)) {
1723                                         return prev_t->pulse_at_tempo (tempo_bpm, prev_t->minute());
1724                                 }
1725                         }
1726                         prev_t = t;
1727                 }
1728         }
1729
1730         return prev_t->minute();
1731 }
1732
1733 /** more precise than doing tempo_at_frame (frame_at_beat (b)),
1734  *  as there is no intermediate frame rounding.
1735  */
1736 Tempo
1737 TempoMap::tempo_at_beat (const double& beat) const
1738 {
1739         Glib::Threads::RWLock::ReaderLock lm (lock);
1740         const MeterSection* prev_m = &meter_section_at_beat_locked (_metrics, beat);
1741         const TempoSection* prev_t = &tempo_section_at_beat_locked (_metrics, beat);
1742
1743         return Tempo (prev_t->tempo_at_pulse (((beat - prev_m->beat()) / prev_m->note_divisor()) + prev_m->pulse()), prev_t->note_type());
1744 }
1745
1746 double
1747 TempoMap::beat_at_tempo (const Tempo& tempo) const
1748 {
1749         Glib::Threads::RWLock::ReaderLock lm (lock);
1750         const double pulse = pulse_at_tempo_locked (_metrics, tempo);
1751
1752         return beat_at_pulse_locked (_metrics, pulse);
1753 }
1754
1755 double
1756 TempoMap::pulse_at_beat (const double& beat) const
1757 {
1758         Glib::Threads::RWLock::ReaderLock lm (lock);
1759         return pulse_at_beat_locked (_metrics, beat);
1760 }
1761
1762 double
1763 TempoMap::pulse_at_beat_locked (const Metrics& metrics, const double& beat) const
1764 {
1765         const MeterSection* prev_m = &meter_section_at_beat_locked (metrics, beat);
1766
1767         return prev_m->pulse() + ((beat - prev_m->beat()) / prev_m->note_divisor());
1768 }
1769
1770 double
1771 TempoMap::beat_at_pulse (const double& pulse) const
1772 {
1773         Glib::Threads::RWLock::ReaderLock lm (lock);
1774         return beat_at_pulse_locked (_metrics, pulse);
1775 }
1776
1777 double
1778 TempoMap::beat_at_pulse_locked (const Metrics& metrics, const double& pulse) const
1779 {
1780         MeterSection* prev_m = 0;
1781
1782         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1783                 MeterSection* m;
1784                 if (!(*i)->is_tempo()) {
1785                         m = static_cast<MeterSection*> (*i);
1786                         if (prev_m && m->pulse() > pulse) {
1787                                 break;
1788                         }
1789                         prev_m = m;
1790                 }
1791         }
1792
1793         double const ret = ((pulse - prev_m->pulse()) * prev_m->note_divisor()) + prev_m->beat();
1794         return ret;
1795 }
1796
1797 double
1798 TempoMap::pulse_at_frame (const framepos_t& frame) const
1799 {
1800         Glib::Threads::RWLock::ReaderLock lm (lock);
1801         return pulse_at_minute_locked (_metrics, minute_at_frame (frame));
1802 }
1803
1804 /* tempo section based */
1805 double
1806 TempoMap::pulse_at_minute_locked (const Metrics& metrics, const double& minute) const
1807 {
1808         /* HOLD (at least) THE READER LOCK */
1809         TempoSection* prev_t = 0;
1810
1811         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1812                 TempoSection* t;
1813                 if ((*i)->is_tempo()) {
1814                         t = static_cast<TempoSection*> (*i);
1815                         if (!t->active()) {
1816                                 continue;
1817                         }
1818                         if (prev_t && t->minute() > minute) {
1819                                 /*the previous ts is the one containing the frame */
1820                                 const double ret = prev_t->pulse_at_minute (minute);
1821                                 /* audio locked section in new meter*/
1822                                 if (t->pulse() < ret) {
1823                                         return t->pulse();
1824                                 }
1825                                 return ret;
1826                         }
1827                         prev_t = t;
1828                 }
1829         }
1830
1831         /* treated as constant for this ts */
1832         const double pulses_in_section = ((minute - prev_t->minute()) * prev_t->beats_per_minute()) / prev_t->note_type();
1833
1834         return pulses_in_section + prev_t->pulse();
1835 }
1836
1837 framepos_t
1838 TempoMap::frame_at_pulse (const double& pulse) const
1839 {
1840         Glib::Threads::RWLock::ReaderLock lm (lock);
1841
1842         return frame_at_minute (minute_at_pulse_locked (_metrics, pulse));
1843 }
1844
1845 /* tempo section based */
1846 double
1847 TempoMap::minute_at_pulse_locked (const Metrics& metrics, const double& pulse) const
1848 {
1849         /* HOLD THE READER LOCK */
1850
1851         const TempoSection* prev_t = 0;
1852
1853         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1854                 TempoSection* t;
1855
1856                 if ((*i)->is_tempo()) {
1857                         t = static_cast<TempoSection*> (*i);
1858                         if (!t->active()) {
1859                                 continue;
1860                         }
1861                         if (prev_t && t->pulse() > pulse) {
1862                                 return prev_t->minute_at_pulse (pulse);
1863                         }
1864
1865                         prev_t = t;
1866                 }
1867         }
1868         /* must be treated as constant, irrespective of _type */
1869         double const dtime = ((pulse - prev_t->pulse()) * prev_t->note_type()) / prev_t->beats_per_minute();
1870
1871         return dtime + prev_t->minute();
1872 }
1873
1874 double
1875 TempoMap::beat_at_bbt (const Timecode::BBT_Time& bbt)
1876 {
1877         Glib::Threads::RWLock::ReaderLock lm (lock);
1878         return beat_at_bbt_locked (_metrics, bbt);
1879 }
1880
1881
1882 double
1883 TempoMap::beat_at_bbt_locked (const Metrics& metrics, const Timecode::BBT_Time& bbt) const
1884 {
1885         /* CALLER HOLDS READ LOCK */
1886
1887         MeterSection* prev_m = 0;
1888
1889         /* because audio-locked meters have 'fake' integral beats,
1890            there is no pulse offset here.
1891         */
1892         MeterSection* m;
1893
1894         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1895                 if (!(*i)->is_tempo()) {
1896                         m = static_cast<MeterSection*> (*i);
1897                         if (prev_m) {
1898                                 const double bars_to_m = (m->beat() - prev_m->beat()) / prev_m->divisions_per_bar();
1899                                 if ((bars_to_m + (prev_m->bbt().bars - 1)) > (bbt.bars - 1)) {
1900                                         break;
1901                                 }
1902                         }
1903                         prev_m = m;
1904                 }
1905         }
1906
1907         const double remaining_bars = bbt.bars - prev_m->bbt().bars;
1908         const double remaining_bars_in_beats = remaining_bars * prev_m->divisions_per_bar();
1909         const double ret = remaining_bars_in_beats + prev_m->beat() + (bbt.beats - 1) + (bbt.ticks / BBT_Time::ticks_per_beat);
1910
1911         return ret;
1912 }
1913
1914 Timecode::BBT_Time
1915 TempoMap::bbt_at_beat (const double& beats)
1916 {
1917         Glib::Threads::RWLock::ReaderLock lm (lock);
1918         return bbt_at_beat_locked (_metrics, beats);
1919 }
1920
1921 Timecode::BBT_Time
1922 TempoMap::bbt_at_beat_locked (const Metrics& metrics, const double& b) const
1923 {
1924         /* CALLER HOLDS READ LOCK */
1925         MeterSection* prev_m = 0;
1926         const double beats = max (0.0, b);
1927
1928         MeterSection* m = 0;
1929
1930         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
1931                 if (!(*i)->is_tempo()) {
1932                         m = static_cast<MeterSection*> (*i);
1933                         if (prev_m) {
1934                                 if (m->beat() > beats) {
1935                                         /* this is the meter after the one our beat is on*/
1936                                         break;
1937                                 }
1938                         }
1939
1940                         prev_m = m;
1941                 }
1942         }
1943
1944         const double beats_in_ms = beats - prev_m->beat();
1945         const uint32_t bars_in_ms = (uint32_t) floor (beats_in_ms / prev_m->divisions_per_bar());
1946         const uint32_t total_bars = bars_in_ms + (prev_m->bbt().bars - 1);
1947         const double remaining_beats = beats_in_ms - (bars_in_ms * prev_m->divisions_per_bar());
1948         const double remaining_ticks = (remaining_beats - floor (remaining_beats)) * BBT_Time::ticks_per_beat;
1949
1950         BBT_Time ret;
1951
1952         ret.ticks = (uint32_t) floor (remaining_ticks + 0.5);
1953         ret.beats = (uint32_t) floor (remaining_beats);
1954         ret.bars = total_bars;
1955
1956         /* 0 0 0 to 1 1 0 - based mapping*/
1957         ++ret.bars;
1958         ++ret.beats;
1959
1960         if (ret.ticks >= BBT_Time::ticks_per_beat) {
1961                 ++ret.beats;
1962                 ret.ticks -= BBT_Time::ticks_per_beat;
1963         }
1964
1965         if (ret.beats >= prev_m->divisions_per_bar() + 1) {
1966                 ++ret.bars;
1967                 ret.beats = 1;
1968         }
1969
1970         return ret;
1971 }
1972
1973 double
1974 TempoMap::pulse_at_bbt (const Timecode::BBT_Time& bbt)
1975 {
1976         Glib::Threads::RWLock::ReaderLock lm (lock);
1977
1978         return pulse_at_bbt_locked (_metrics, bbt);
1979 }
1980
1981 double
1982 TempoMap::pulse_at_bbt_rt (const Timecode::BBT_Time& bbt)
1983 {
1984         Glib::Threads::RWLock::ReaderLock lm (lock);
1985
1986         if (!lm.locked()) {
1987                 throw std::logic_error ("TempoMap::pulse_at_bbt_rt() could not lock tempo map");
1988         }
1989
1990         return pulse_at_bbt_locked (_metrics, bbt);
1991 }
1992
1993 double
1994 TempoMap::pulse_at_bbt_locked (const Metrics& metrics, const Timecode::BBT_Time& bbt) const
1995 {
1996         /* CALLER HOLDS READ LOCK */
1997
1998         MeterSection* prev_m = 0;
1999
2000         /* because audio-locked meters have 'fake' integral beats,
2001            there is no pulse offset here.
2002         */
2003         MeterSection* m;
2004
2005         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
2006                 if (!(*i)->is_tempo()) {
2007                         m = static_cast<MeterSection*> (*i);
2008                         if (prev_m) {
2009                                 if (m->bbt().bars > bbt.bars) {
2010                                         break;
2011                                 }
2012                         }
2013                         prev_m = m;
2014                 }
2015         }
2016
2017         const double remaining_bars = bbt.bars - prev_m->bbt().bars;
2018         const double remaining_pulses = remaining_bars * prev_m->divisions_per_bar() / prev_m->note_divisor();
2019         const double ret = remaining_pulses + prev_m->pulse() + (((bbt.beats - 1) + (bbt.ticks / BBT_Time::ticks_per_beat)) / prev_m->note_divisor());
2020
2021         return ret;
2022 }
2023
2024 Timecode::BBT_Time
2025 TempoMap::bbt_at_pulse (const double& pulse)
2026 {
2027         Glib::Threads::RWLock::ReaderLock lm (lock);
2028
2029         return bbt_at_pulse_locked (_metrics, pulse);
2030 }
2031
2032 Timecode::BBT_Time
2033 TempoMap::bbt_at_pulse_locked (const Metrics& metrics, const double& pulse) const
2034 {
2035         MeterSection* prev_m = 0;
2036
2037         MeterSection* m = 0;
2038
2039         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
2040
2041                 if (!(*i)->is_tempo()) {
2042                         m = static_cast<MeterSection*> (*i);
2043
2044                         if (prev_m) {
2045                                 double const pulses_to_m = m->pulse() - prev_m->pulse();
2046                                 if (prev_m->pulse() + pulses_to_m > pulse) {
2047                                         /* this is the meter after the one our beat is on*/
2048                                         break;
2049                                 }
2050                         }
2051
2052                         prev_m = m;
2053                 }
2054         }
2055
2056         const double beats_in_ms = (pulse - prev_m->pulse()) * prev_m->note_divisor();
2057         const uint32_t bars_in_ms = (uint32_t) floor (beats_in_ms / prev_m->divisions_per_bar());
2058         const uint32_t total_bars = bars_in_ms + (prev_m->bbt().bars - 1);
2059         const double remaining_beats = beats_in_ms - (bars_in_ms * prev_m->divisions_per_bar());
2060         const double remaining_ticks = (remaining_beats - floor (remaining_beats)) * BBT_Time::ticks_per_beat;
2061
2062         BBT_Time ret;
2063
2064         ret.ticks = (uint32_t) floor (remaining_ticks + 0.5);
2065         ret.beats = (uint32_t) floor (remaining_beats);
2066         ret.bars = total_bars;
2067
2068         /* 0 0 0 to 1 1 0 mapping*/
2069         ++ret.bars;
2070         ++ret.beats;
2071
2072         if (ret.ticks >= BBT_Time::ticks_per_beat) {
2073                 ++ret.beats;
2074                 ret.ticks -= BBT_Time::ticks_per_beat;
2075         }
2076
2077         if (ret.beats >= prev_m->divisions_per_bar() + 1) {
2078                 ++ret.bars;
2079                 ret.beats = 1;
2080         }
2081
2082         return ret;
2083 }
2084
2085 BBT_Time
2086 TempoMap::bbt_at_frame (framepos_t frame)
2087 {
2088         if (frame < 0) {
2089                 BBT_Time bbt;
2090                 bbt.bars = 1;
2091                 bbt.beats = 1;
2092                 bbt.ticks = 0;
2093                 warning << string_compose (_("tempo map asked for BBT time at frame %1\n"), frame) << endmsg;
2094                 return bbt;
2095         }
2096         Glib::Threads::RWLock::ReaderLock lm (lock);
2097
2098         return bbt_at_minute_locked (_metrics, minute_at_frame (frame));
2099 }
2100
2101 BBT_Time
2102 TempoMap::bbt_at_frame_rt (framepos_t frame)
2103 {
2104         Glib::Threads::RWLock::ReaderLock lm (lock, Glib::Threads::TRY_LOCK);
2105
2106         if (!lm.locked()) {
2107                 throw std::logic_error ("TempoMap::bbt_at_frame_rt() could not lock tempo map");
2108         }
2109
2110         return bbt_at_minute_locked (_metrics, minute_at_frame (frame));
2111 }
2112
2113 Timecode::BBT_Time
2114 TempoMap::bbt_at_minute_locked (const Metrics& metrics, const double& minute) const
2115 {
2116         if (minute < 0) {
2117                 BBT_Time bbt;
2118                 bbt.bars = 1;
2119                 bbt.beats = 1;
2120                 bbt.ticks = 0;
2121                 return bbt;
2122         }
2123
2124         const TempoSection& ts = tempo_section_at_minute_locked (metrics, minute);
2125         MeterSection* prev_m = 0;
2126         MeterSection* next_m = 0;
2127
2128         MeterSection* m;
2129
2130         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
2131                 if (!(*i)->is_tempo()) {
2132                         m = static_cast<MeterSection*> (*i);
2133                         if (prev_m && m->minute() > minute) {
2134                                 next_m = m;
2135                                 break;
2136                         }
2137                         prev_m = m;
2138                 }
2139         }
2140
2141         double beat = prev_m->beat() + (ts.pulse_at_minute (minute) - prev_m->pulse()) * prev_m->note_divisor();
2142
2143         /* handle frame before first meter */
2144         if (minute < prev_m->minute()) {
2145                 beat = 0.0;
2146         }
2147         /* audio locked meters fake their beat */
2148         if (next_m && next_m->beat() < beat) {
2149                 beat = next_m->beat();
2150         }
2151
2152         beat = max (0.0, beat);
2153
2154         const double beats_in_ms = beat - prev_m->beat();
2155         const uint32_t bars_in_ms = (uint32_t) floor (beats_in_ms / prev_m->divisions_per_bar());
2156         const uint32_t total_bars = bars_in_ms + (prev_m->bbt().bars - 1);
2157         const double remaining_beats = beats_in_ms - (bars_in_ms * prev_m->divisions_per_bar());
2158         const double remaining_ticks = (remaining_beats - floor (remaining_beats)) * BBT_Time::ticks_per_beat;
2159
2160         BBT_Time ret;
2161
2162         ret.ticks = (uint32_t) floor (remaining_ticks + 0.5);
2163         ret.beats = (uint32_t) floor (remaining_beats);
2164         ret.bars = total_bars;
2165
2166         /* 0 0 0 to 1 1 0 - based mapping*/
2167         ++ret.bars;
2168         ++ret.beats;
2169
2170         if (ret.ticks >= BBT_Time::ticks_per_beat) {
2171                 ++ret.beats;
2172                 ret.ticks -= BBT_Time::ticks_per_beat;
2173         }
2174
2175         if (ret.beats >= prev_m->divisions_per_bar() + 1) {
2176                 ++ret.bars;
2177                 ret.beats = 1;
2178         }
2179
2180         return ret;
2181 }
2182
2183 framepos_t
2184 TempoMap::frame_at_bbt (const BBT_Time& bbt)
2185 {
2186         if (bbt.bars < 1) {
2187                 warning << string_compose (_("tempo map asked for frame time at bar < 1  (%1)\n"), bbt) << endmsg;
2188                 return 0;
2189         }
2190
2191         if (bbt.beats < 1) {
2192                 throw std::logic_error ("beats are counted from one");
2193         }
2194         Glib::Threads::RWLock::ReaderLock lm (lock);
2195
2196         return frame_at_minute (minute_at_bbt_locked (_metrics, bbt));
2197 }
2198
2199 /* meter & tempo section based */
2200 double
2201 TempoMap::minute_at_bbt_locked (const Metrics& metrics, const BBT_Time& bbt) const
2202 {
2203         /* HOLD THE READER LOCK */
2204
2205         const double ret = minute_at_beat_locked (metrics, beat_at_bbt_locked (metrics, bbt));
2206         return ret;
2207 }
2208
2209 /**
2210  * Returns the distance from 0 in quarter pulses at the supplied frame.
2211  *
2212  * Plugin APIs don't count ticks in the same way PROGRAM_NAME does.
2213  * We use ticks per beat whereas the rest of the world uses ticks per quarter note.
2214  * This is more or less the VST's ppqPos (a scalar you use to obtain tick position
2215  * in whatever ppqn you're using).
2216  *
2217  * @param frame The distance in frames relative to session 0 whose quarter note distance you would like.
2218  * @return The quarter note (quarter pulse) distance from session 0 to the supplied frame. Ignores meter.
2219 */
2220
2221 double
2222 TempoMap::quarter_note_at_frame (const framepos_t frame)
2223 {
2224         Glib::Threads::RWLock::ReaderLock lm (lock);
2225
2226         const double ret = quarter_note_at_minute_locked (_metrics, minute_at_frame (frame));
2227
2228         return ret;
2229 }
2230
2231 double
2232 TempoMap::quarter_note_at_minute_locked (const Metrics& metrics, const double minute) const
2233 {
2234         const double ret = pulse_at_minute_locked (metrics, minute) * 4.0;
2235
2236         return ret;
2237 }
2238
2239 double
2240 TempoMap::quarter_note_at_frame_rt (const framepos_t frame)
2241 {
2242         Glib::Threads::RWLock::ReaderLock lm (lock, Glib::Threads::TRY_LOCK);
2243
2244         if (!lm.locked()) {
2245                 throw std::logic_error ("TempoMap::quarter_note_at_frame_rt() could not lock tempo map");
2246         }
2247
2248         const double ret = pulse_at_minute_locked (_metrics, minute_at_frame (frame)) * 4.0;
2249
2250         return ret;
2251 }
2252
2253 framepos_t
2254 TempoMap::frame_at_quarter_note (const double quarter_note)
2255 {
2256         Glib::Threads::RWLock::ReaderLock lm (lock);
2257
2258         const framepos_t ret = frame_at_minute (minute_at_quarter_note_locked (_metrics, quarter_note));
2259
2260         return ret;
2261 }
2262
2263 double
2264 TempoMap::minute_at_quarter_note_locked (const Metrics& metrics, const double quarter_note) const
2265 {
2266         const double ret = minute_at_pulse_locked (metrics, quarter_note / 4.0);
2267
2268         return ret;
2269 }
2270
2271 double
2272 TempoMap::quarter_note_at_beat (const double beat)
2273 {
2274         Glib::Threads::RWLock::ReaderLock lm (lock);
2275
2276         const double ret = quarter_note_at_beat_locked (_metrics, beat);
2277
2278         return ret;
2279 }
2280
2281 double
2282 TempoMap::quarter_note_at_beat_locked (const Metrics& metrics, const double beat) const
2283 {
2284         const double ret = pulse_at_beat_locked (metrics, beat) * 4.0;
2285
2286         return ret;
2287 }
2288
2289 double
2290 TempoMap::beat_at_quarter_note (const double quarter_note)
2291 {
2292         Glib::Threads::RWLock::ReaderLock lm (lock);
2293
2294         const double ret = beat_at_quarter_note_locked (_metrics, quarter_note);
2295
2296         return ret;
2297 }
2298
2299 double
2300 TempoMap::beat_at_quarter_note_locked (const Metrics& metrics, const double quarter_note) const
2301 {
2302
2303         return beat_at_pulse_locked (metrics, quarter_note / 4.0);
2304 }
2305
2306 framecnt_t
2307 TempoMap::frames_between_quarter_notes (const double start, const double end)
2308 {
2309         Glib::Threads::RWLock::ReaderLock lm (lock);
2310
2311         return frame_at_minute (minutes_between_quarter_notes_locked (_metrics, start, end));
2312 }
2313
2314 double
2315 TempoMap::minutes_between_quarter_notes_locked (const Metrics& metrics, const double start, const double end)
2316 {
2317
2318         return minute_at_pulse_locked (metrics, end / 4.0) - minute_at_pulse_locked (metrics, start / 4.0);
2319 }
2320
2321 bool
2322 TempoMap::check_solved (const Metrics& metrics) const
2323 {
2324         TempoSection* prev_t = 0;
2325         MeterSection* prev_m = 0;
2326
2327         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
2328                 TempoSection* t;
2329                 MeterSection* m;
2330                 if ((*i)->is_tempo()) {
2331                         t = static_cast<TempoSection*> (*i);
2332                         if (!t->active()) {
2333                                 continue;
2334                         }
2335                         if (prev_t) {
2336                                 /* check ordering */
2337                                 if ((t->minute() <= prev_t->minute()) || (t->pulse() <= prev_t->pulse())) {
2338                                         return false;
2339                                 }
2340
2341                                 /* precision check ensures tempo and frames align.*/
2342                                 if (t->frame() != frame_at_minute (prev_t->minute_at_tempo (t->beats_per_minute(), t->pulse()))) {
2343                                         if (!t->locked_to_meter()) {
2344                                                 return false;
2345                                         }
2346                                 }
2347
2348                                 /* gradient limit - who knows what it should be?
2349                                    things are also ok (if a little chaotic) without this
2350                                 */
2351                                 if (fabs (prev_t->c_func()) > 1000.0) {
2352                                         //std::cout << "c : " << prev_t->c_func() << std::endl;
2353                                         return false;
2354                                 }
2355                         }
2356                         prev_t = t;
2357                 }
2358
2359                 if (!(*i)->is_tempo()) {
2360                         m = static_cast<MeterSection*> (*i);
2361                         if (prev_m && m->position_lock_style() == AudioTime) {
2362                                 const TempoSection* t = &tempo_section_at_minute_locked (metrics, minute_at_frame (m->frame() - 1));
2363                                 const double nascent_m_minute = t->minute_at_pulse (m->pulse());
2364                                 /* Here we check that a preceding section of music doesn't overlap a subsequent one.
2365                                 */
2366                                 if (t && (nascent_m_minute > m->minute() || nascent_m_minute < 0.0)) {
2367                                         return false;
2368                                 }
2369                         }
2370
2371                         prev_m = m;
2372                 }
2373
2374         }
2375
2376         return true;
2377 }
2378
2379 bool
2380 TempoMap::set_active_tempos (const Metrics& metrics, const framepos_t& frame)
2381 {
2382         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
2383                 TempoSection* t;
2384                 if ((*i)->is_tempo()) {
2385                         t = static_cast<TempoSection*> (*i);
2386                         if (!t->movable()) {
2387                                 t->set_active (true);
2388                                 continue;
2389                         }
2390                         if (t->movable() && t->active () && t->position_lock_style() == AudioTime && t->frame() < frame) {
2391                                 t->set_active (false);
2392                                 t->set_pulse (0.0);
2393                         } else if (t->movable() && t->position_lock_style() == AudioTime && t->frame() > frame) {
2394                                 t->set_active (true);
2395                         } else if (t->movable() && t->position_lock_style() == AudioTime && t->frame() == frame) {
2396                                 return false;
2397                         }
2398                 }
2399         }
2400         return true;
2401 }
2402
2403 bool
2404 TempoMap::solve_map_minute (Metrics& imaginary, TempoSection* section, const double& minute)
2405 {
2406         TempoSection* prev_t = 0;
2407         TempoSection* section_prev = 0;
2408         double first_m_minute = 0.0;
2409
2410         /* can't move a tempo before the first meter */
2411         for (Metrics::iterator i = imaginary.begin(); i != imaginary.end(); ++i) {
2412                 MeterSection* m;
2413                 if (!(*i)->is_tempo()) {
2414                         m = static_cast<MeterSection*> (*i);
2415                         if (!m->movable()) {
2416                                 first_m_minute = m->minute();
2417                                 break;
2418                         }
2419                 }
2420         }
2421         if (section->movable() && minute <= first_m_minute) {
2422                 return false;
2423         }
2424
2425         section->set_active (true);
2426         section->set_minute (minute);
2427
2428         for (Metrics::iterator i = imaginary.begin(); i != imaginary.end(); ++i) {
2429                 TempoSection* t;
2430                 if ((*i)->is_tempo()) {
2431                         t = static_cast<TempoSection*> (*i);
2432
2433                         if (!t->active()) {
2434                                 continue;
2435                         }
2436                         if (prev_t) {
2437                                 if (t == section) {
2438                                         section_prev = prev_t;
2439                                         if (t->locked_to_meter()) {
2440                                                 prev_t = t;
2441                                         }
2442                                         continue;
2443                                 }
2444                                 if (t->position_lock_style() == MusicTime) {
2445                                         prev_t->set_c_func (prev_t->compute_c_func_pulse (t->beats_per_minute(), t->pulse()));
2446                                         t->set_minute (prev_t->minute_at_tempo (t->beats_per_minute(), t->pulse()));
2447                                 } else {
2448                                         prev_t->set_c_func (prev_t->compute_c_func_minute (t->beats_per_minute(), t->minute()));
2449                                         if (!t->locked_to_meter()) {
2450                                                 t->set_pulse (prev_t->pulse_at_tempo (t->beats_per_minute(), t->minute()));
2451                                         }
2452                                 }
2453                         }
2454                         prev_t = t;
2455                 }
2456         }
2457
2458         if (section_prev) {
2459                 section_prev->set_c_func (section_prev->compute_c_func_minute (section->beats_per_minute(), minute));
2460                 if (!section->locked_to_meter()) {
2461                         section->set_pulse (section_prev->pulse_at_tempo (section->beats_per_minute(), minute));
2462                 }
2463         }
2464
2465 #if (0)
2466         recompute_tempi (imaginary);
2467
2468         if (check_solved (imaginary)) {
2469                 return true;
2470         } else {
2471                 dunp (imaginary, std::cout);
2472         }
2473 #endif
2474
2475         MetricSectionFrameSorter fcmp;
2476         imaginary.sort (fcmp);
2477
2478         recompute_tempi (imaginary);
2479
2480         if (check_solved (imaginary)) {
2481                 return true;
2482         }
2483
2484         return false;
2485 }
2486
2487 bool
2488 TempoMap::solve_map_pulse (Metrics& imaginary, TempoSection* section, const double& pulse)
2489 {
2490         TempoSection* prev_t = 0;
2491         TempoSection* section_prev = 0;
2492
2493         section->set_pulse (pulse);
2494
2495         for (Metrics::iterator i = imaginary.begin(); i != imaginary.end(); ++i) {
2496                 TempoSection* t;
2497                 if ((*i)->is_tempo()) {
2498                         t = static_cast<TempoSection*> (*i);
2499                         if (!t->active()) {
2500                                 continue;
2501                         }
2502                         if (!t->movable()) {
2503                                 t->set_pulse (0.0);
2504                                 prev_t = t;
2505                                 continue;
2506                         }
2507                         if (prev_t) {
2508                                 if (t == section) {
2509                                         section_prev = prev_t;
2510                                         continue;
2511                                 }
2512                                 if (t->position_lock_style() == MusicTime) {
2513                                         prev_t->set_c_func (prev_t->compute_c_func_pulse (t->beats_per_minute(), t->pulse()));
2514                                         t->set_minute (prev_t->minute_at_tempo (t->beats_per_minute(), t->pulse()));
2515                                 } else {
2516                                         prev_t->set_c_func (prev_t->compute_c_func_minute (t->beats_per_minute(), t->minute()));
2517                                         if (!t->locked_to_meter()) {
2518                                                 t->set_pulse (prev_t->pulse_at_tempo (t->beats_per_minute(), t->minute()));
2519                                         }
2520                                 }
2521                         }
2522                         prev_t = t;
2523                 }
2524         }
2525
2526         if (section_prev) {
2527                 section_prev->set_c_func (section_prev->compute_c_func_pulse (section->beats_per_minute(), pulse));
2528                 section->set_minute (section_prev->minute_at_tempo (section->beats_per_minute(), pulse));
2529         }
2530
2531 #if (0)
2532         recompute_tempi (imaginary);
2533
2534         if (check_solved (imaginary)) {
2535                 return true;
2536         } else {
2537                 dunp (imaginary, std::cout);
2538         }
2539 #endif
2540
2541         MetricSectionSorter cmp;
2542         imaginary.sort (cmp);
2543
2544         recompute_tempi (imaginary);
2545         /* Reordering
2546          * XX need a restriction here, but only for this case,
2547          * as audio locked tempos don't interact in the same way.
2548          *
2549          * With music-locked tempos, the solution to cross-dragging can fly off the screen
2550          * e.g.
2551          * |50 bpm                        |250 bpm |60 bpm
2552          *                drag 250 to the pulse after 60->
2553          * a clue: dragging the second 60 <- past the 250 would cause no such problem.
2554          */
2555         if (check_solved (imaginary)) {
2556                 return true;
2557         }
2558
2559         return false;
2560 }
2561
2562 bool
2563 TempoMap::solve_map_minute (Metrics& imaginary, MeterSection* section, const double& minute)
2564 {
2565         /* disallow moving first meter past any subsequent one, and any movable meter before the first one */
2566         const MeterSection* other =  &meter_section_at_minute_locked (imaginary, minute);
2567         if ((!section->movable() && other->movable()) || (!other->movable() && section->movable() && other->minute() >= minute)) {
2568                 return false;
2569         }
2570
2571         if (!section->movable()) {
2572                 /* lock the first tempo to our first meter */
2573                 if (!set_active_tempos (imaginary, section->frame_at_minute (minute))) {
2574                         return false;
2575                 }
2576         }
2577
2578         TempoSection* meter_locked_tempo = 0;
2579
2580         for (Metrics::const_iterator ii = imaginary.begin(); ii != imaginary.end(); ++ii) {
2581                 TempoSection* t;
2582                 if ((*ii)->is_tempo()) {
2583                         t = static_cast<TempoSection*> (*ii);
2584                         if ((t->locked_to_meter() || !t->movable()) && t->minute() == section->minute()) {
2585                                 meter_locked_tempo = t;
2586                                 break;
2587                         }
2588                 }
2589         }
2590
2591         if (!meter_locked_tempo) {
2592                 return false;
2593         }
2594
2595         MeterSection* prev_m = 0;
2596         Metrics future_map;
2597         TempoSection* tempo_copy = copy_metrics_and_point (imaginary, future_map, meter_locked_tempo);
2598         bool solved = false;
2599
2600         for (Metrics::iterator i = imaginary.begin(); i != imaginary.end(); ++i) {
2601                 MeterSection* m;
2602                 if (!(*i)->is_tempo()) {
2603                         m = static_cast<MeterSection*> (*i);
2604                         if (m == section){
2605                                 if (prev_m && section->movable()) {
2606                                         const double beats = (pulse_at_minute_locked (imaginary, minute) - prev_m->pulse()) * prev_m->note_divisor();
2607                                         if (beats + prev_m->beat() < section->beat()) {
2608                                                 /* set the section pulse according to its musical position,
2609                                                  * as an earlier time than this has been requested.
2610                                                 */
2611                                                 const double new_pulse = ((section->beat() - prev_m->beat())
2612                                                                           / prev_m->note_divisor()) + prev_m->pulse();
2613
2614                                                 tempo_copy->set_position_lock_style (MusicTime);
2615                                                 if ((solved = solve_map_pulse (future_map, tempo_copy, new_pulse))) {
2616                                                         meter_locked_tempo->set_position_lock_style (MusicTime);
2617                                                         section->set_position_lock_style (MusicTime);
2618                                                         section->set_pulse (new_pulse);
2619                                                         solve_map_pulse (imaginary, meter_locked_tempo, new_pulse);
2620                                                         meter_locked_tempo->set_position_lock_style (AudioTime);
2621                                                         section->set_position_lock_style (AudioTime);
2622                                                         section->set_minute (meter_locked_tempo->minute());
2623
2624                                                 } else {
2625                                                         solved = false;
2626                                                 }
2627
2628                                                 Metrics::const_iterator d = future_map.begin();
2629                                                 while (d != future_map.end()) {
2630                                                         delete (*d);
2631                                                         ++d;
2632                                                 }
2633
2634                                                 if (!solved) {
2635                                                         return false;
2636                                                 }
2637                                         } else {
2638                                                 /* all is ok. set section's locked tempo if allowed.
2639                                                    possibly disallowed if there is an adjacent audio-locked tempo.
2640                                                    XX this check could possibly go. its never actually happened here.
2641                                                 */
2642                                                 MeterSection* meter_copy = const_cast<MeterSection*>
2643                                                         (&meter_section_at_minute_locked (future_map, section->minute()));
2644
2645                                                 meter_copy->set_minute (minute);
2646
2647                                                 if ((solved = solve_map_minute (future_map, tempo_copy, minute))) {
2648                                                         section->set_minute (minute);
2649                                                         meter_locked_tempo->set_pulse (((section->beat() - prev_m->beat())
2650                                                                                                 / prev_m->note_divisor()) + prev_m->pulse());
2651                                                         solve_map_minute (imaginary, meter_locked_tempo, minute);
2652                                                 } else {
2653                                                         solved = false;
2654                                                 }
2655
2656                                                 Metrics::const_iterator d = future_map.begin();
2657                                                 while (d != future_map.end()) {
2658                                                         delete (*d);
2659                                                         ++d;
2660                                                 }
2661
2662                                                 if (!solved) {
2663                                                         return false;
2664                                                 }
2665                                         }
2666                                 } else {
2667                                         /* not movable (first meter atm) */
2668
2669                                         tempo_copy->set_minute (minute);
2670                                         tempo_copy->set_pulse (0.0);
2671
2672                                         if ((solved = solve_map_minute (future_map, tempo_copy, minute))) {
2673                                                 section->set_minute (minute);
2674                                                 meter_locked_tempo->set_minute (minute);
2675                                                 meter_locked_tempo->set_pulse (0.0);
2676                                                 solve_map_minute (imaginary, meter_locked_tempo, minute);
2677                                         } else {
2678                                                 solved = false;
2679                                         }
2680
2681                                         Metrics::const_iterator d = future_map.begin();
2682                                         while (d != future_map.end()) {
2683                                                 delete (*d);
2684                                                 ++d;
2685                                         }
2686
2687                                         if (!solved) {
2688                                                 return false;
2689                                         }
2690
2691                                         pair<double, BBT_Time> b_bbt = make_pair (0.0, BBT_Time (1, 1, 0));
2692                                         section->set_beat (b_bbt);
2693                                         section->set_pulse (0.0);
2694
2695                                 }
2696                                 break;
2697                         }
2698
2699                         prev_m = m;
2700                 }
2701         }
2702
2703         MetricSectionFrameSorter fcmp;
2704         imaginary.sort (fcmp);
2705
2706         recompute_meters (imaginary);
2707
2708         return true;
2709 }
2710
2711 bool
2712 TempoMap::solve_map_bbt (Metrics& imaginary, MeterSection* section, const BBT_Time& when)
2713 {
2714         /* disallow setting section to an existing meter's bbt */
2715         for (Metrics::iterator i = imaginary.begin(); i != imaginary.end(); ++i) {
2716                 MeterSection* m;
2717                 if (!(*i)->is_tempo()) {
2718                         m = static_cast<MeterSection*> (*i);
2719                         if (m != section && m->bbt().bars == when.bars) {
2720                                 return false;
2721                         }
2722                 }
2723         }
2724
2725         MeterSection* prev_m = 0;
2726         MeterSection* section_prev = 0;
2727
2728         for (Metrics::iterator i = imaginary.begin(); i != imaginary.end(); ++i) {
2729                 MeterSection* m;
2730                 if (!(*i)->is_tempo()) {
2731                         m = static_cast<MeterSection*> (*i);
2732                         pair<double, BBT_Time> b_bbt;
2733                         double new_pulse = 0.0;
2734
2735                         if (prev_m && m->bbt().bars > when.bars && !section_prev){
2736                                 section_prev = prev_m;
2737                                 const double beats = (when.bars - section_prev->bbt().bars) * section_prev->divisions_per_bar();
2738                                 const double pulse = (beats / section_prev->note_divisor()) + section_prev->pulse();
2739                                 pair<double, BBT_Time> b_bbt = make_pair (beats + section_prev->beat(), when);
2740
2741                                 section->set_beat (b_bbt);
2742                                 section->set_pulse (pulse);
2743                                 section->set_minute (minute_at_pulse_locked (imaginary, pulse));
2744                                 prev_m = section;
2745                                 continue;
2746                         }
2747
2748                         if (m->position_lock_style() == AudioTime) {
2749                                 TempoSection* meter_locked_tempo = 0;
2750
2751                                 for (Metrics::const_iterator ii = imaginary.begin(); ii != imaginary.end(); ++ii) {
2752                                         TempoSection* t;
2753                                         if ((*ii)->is_tempo()) {
2754                                                 t = static_cast<TempoSection*> (*ii);
2755                                                 if ((t->locked_to_meter() || !t->movable()) && t->frame() == m->frame()) {
2756                                                         meter_locked_tempo = t;
2757                                                         break;
2758                                                 }
2759                                         }
2760                                 }
2761
2762                                 if (!meter_locked_tempo) {
2763                                         return false;
2764                                 }
2765
2766                                 if (prev_m) {
2767                                         const double beats = ((m->bbt().bars - prev_m->bbt().bars) * prev_m->divisions_per_bar());
2768
2769                                         if (beats + prev_m->beat() != m->beat()) {
2770                                                 /* tempo/ meter change caused a change in beat (bar). */
2771                                                 b_bbt = make_pair (beats + prev_m->beat()
2772                                                                    , BBT_Time ((beats / prev_m->divisions_per_bar()) + prev_m->bbt().bars, 1, 0));
2773                                                 new_pulse = prev_m->pulse() + (beats / prev_m->note_divisor());
2774                                         } else if (m->movable()) {
2775                                                 b_bbt = make_pair (m->beat(), m->bbt());
2776                                                 new_pulse = prev_m->pulse() + (beats / prev_m->note_divisor());
2777                                         }
2778                                 } else {
2779                                         b_bbt = make_pair (0.0, BBT_Time (1, 1, 0));
2780                                 }
2781
2782                                 meter_locked_tempo->set_pulse (new_pulse);
2783                                 m->set_beat (b_bbt);
2784                                 m->set_pulse (new_pulse);
2785
2786                         } else {
2787                                 /* MusicTime */
2788                                 const double beats = ((m->bbt().bars - prev_m->bbt().bars) * prev_m->divisions_per_bar());
2789                                 if (beats + prev_m->beat() != m->beat()) {
2790                                         /* tempo/ meter change caused a change in beat (bar). */
2791                                         b_bbt = make_pair (beats + prev_m->beat()
2792                                                            , BBT_Time ((beats / prev_m->divisions_per_bar()) + prev_m->bbt().bars, 1, 0));
2793                                 } else {
2794                                         b_bbt = make_pair (beats + prev_m->beat()
2795                                                            , m->bbt());
2796                                 }
2797                                 new_pulse = (beats / prev_m->note_divisor()) + prev_m->pulse();
2798                                 m->set_beat (b_bbt);
2799                                 m->set_pulse (new_pulse);
2800                                 m->set_minute (minute_at_pulse_locked (imaginary, new_pulse));
2801                         }
2802
2803                         prev_m = m;
2804                 }
2805         }
2806
2807         if (!section_prev) {
2808
2809                 const double beats = (when.bars - prev_m->bbt().bars) * prev_m->divisions_per_bar();
2810                 const double pulse = (beats / prev_m->note_divisor()) + prev_m->pulse();
2811                 pair<double, BBT_Time> b_bbt = make_pair (beats + prev_m->beat(), when);
2812
2813                 section->set_beat (b_bbt);
2814                 section->set_pulse (pulse);
2815                 section->set_minute (minute_at_pulse_locked (imaginary, pulse));
2816         }
2817
2818         MetricSectionSorter cmp;
2819         imaginary.sort (cmp);
2820
2821         recompute_meters (imaginary);
2822
2823         return true;
2824 }
2825
2826 /** places a copy of _metrics into copy and returns a pointer
2827  *  to section's equivalent in copy.
2828  */
2829 TempoSection*
2830 TempoMap::copy_metrics_and_point (const Metrics& metrics, Metrics& copy, TempoSection* section)
2831 {
2832         TempoSection* ret = 0;
2833
2834         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
2835                 TempoSection* t;
2836                 MeterSection* m;
2837                 if ((*i)->is_tempo()) {
2838                         t = static_cast<TempoSection*> (*i);
2839                         if (t == section) {
2840                                 ret = new TempoSection (*t);
2841                                 copy.push_back (ret);
2842                                 continue;
2843                         }
2844
2845                         TempoSection* cp = new TempoSection (*t);
2846                         copy.push_back (cp);
2847                 }
2848                 if (!(*i)->is_tempo()) {
2849                         m = static_cast<MeterSection *> (*i);
2850                         MeterSection* cp = new MeterSection (*m);
2851                         copy.push_back (cp);
2852                 }
2853         }
2854
2855         return ret;
2856 }
2857
2858 MeterSection*
2859 TempoMap::copy_metrics_and_point (const Metrics& metrics, Metrics& copy, MeterSection* section)
2860 {
2861         MeterSection* ret = 0;
2862
2863         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
2864                 TempoSection* t;
2865                 MeterSection* m;
2866                 if ((*i)->is_tempo()) {
2867                         t = static_cast<TempoSection*> (*i);
2868                         TempoSection* cp = new TempoSection (*t);
2869                         copy.push_back (cp);
2870                 }
2871
2872                 if (!(*i)->is_tempo()) {
2873                         m = static_cast<MeterSection *> (*i);
2874                         if (m == section) {
2875                                 ret = new MeterSection (*m);
2876                                 copy.push_back (ret);
2877                                 continue;
2878                         }
2879                         MeterSection* cp = new MeterSection (*m);
2880                         copy.push_back (cp);
2881                 }
2882         }
2883
2884         return ret;
2885 }
2886
2887 /** answers the question "is this a valid beat position for this tempo section?".
2888  *  it returns true if the tempo section can be moved to the requested bbt position,
2889  *  leaving the tempo map in a solved state.
2890  * @param section the tempo section to be moved
2891  * @param bbt the requested new position for the tempo section
2892  * @return true if the tempo section can be moved to the position, otherwise false.
2893  */
2894 bool
2895 TempoMap::can_solve_bbt (TempoSection* ts, const BBT_Time& bbt)
2896 {
2897         Metrics copy;
2898         TempoSection* tempo_copy = 0;
2899
2900         {
2901                 Glib::Threads::RWLock::ReaderLock lm (lock);
2902                 tempo_copy = copy_metrics_and_point (_metrics, copy, ts);
2903                 if (!tempo_copy) {
2904                         return false;
2905                 }
2906         }
2907
2908         const bool ret = solve_map_pulse (copy, tempo_copy, pulse_at_bbt_locked (copy, bbt));
2909
2910         Metrics::const_iterator d = copy.begin();
2911         while (d != copy.end()) {
2912                 delete (*d);
2913                 ++d;
2914         }
2915
2916         return ret;
2917 }
2918
2919 /**
2920 * This is for a gui that needs to know the pulse or frame of a tempo section if it were to be moved to some bbt time,
2921 * taking any possible reordering as a consequence of this into account.
2922 * @param section - the section to be altered
2923 * @param bbt - the bbt where the altered tempo will fall
2924 * @return returns - the position in pulses and frames (as a pair) where the new tempo section will lie.
2925 */
2926 pair<double, framepos_t>
2927 TempoMap::predict_tempo_position (TempoSection* section, const BBT_Time& bbt)
2928 {
2929         Metrics future_map;
2930         pair<double, framepos_t> ret = make_pair (0.0, 0);
2931
2932         Glib::Threads::RWLock::ReaderLock lm (lock);
2933
2934         TempoSection* tempo_copy = copy_metrics_and_point (_metrics, future_map, section);
2935
2936         const double beat = beat_at_bbt_locked (future_map, bbt);
2937
2938         if (solve_map_pulse (future_map, tempo_copy, pulse_at_beat_locked (future_map, beat))) {
2939                 ret.first = tempo_copy->pulse();
2940                 ret.second = tempo_copy->frame();
2941         } else {
2942                 ret.first = section->pulse();
2943                 ret.second = section->frame();
2944         }
2945
2946         Metrics::const_iterator d = future_map.begin();
2947         while (d != future_map.end()) {
2948                 delete (*d);
2949                 ++d;
2950         }
2951         return ret;
2952 }
2953
2954 void
2955 TempoMap::gui_move_tempo (TempoSection* ts, const framepos_t& frame, const int& sub_num)
2956 {
2957         Metrics future_map;
2958
2959         if (ts->position_lock_style() == MusicTime) {
2960                 {
2961                         /* if we're snapping to a musical grid, set the pulse exactly instead of via the supplied frame. */
2962                         Glib::Threads::RWLock::WriterLock lm (lock);
2963                         TempoSection* tempo_copy = copy_metrics_and_point (_metrics, future_map, ts);
2964
2965                         tempo_copy->set_position_lock_style (AudioTime);
2966
2967                         if (solve_map_minute (future_map, tempo_copy, minute_at_frame (frame))) {
2968                                 const double beat = exact_beat_at_frame_locked (future_map, frame, sub_num);
2969                                 const double pulse = pulse_at_beat_locked (future_map, beat);
2970
2971                                 if (solve_map_pulse (future_map, tempo_copy, pulse)) {
2972                                         solve_map_pulse (_metrics, ts, pulse);
2973                                         recompute_meters (_metrics);
2974                                 }
2975                         }
2976                 }
2977
2978         } else {
2979
2980                 {
2981                         Glib::Threads::RWLock::WriterLock lm (lock);
2982                         TempoSection* tempo_copy = copy_metrics_and_point (_metrics, future_map, ts);
2983
2984                         if (solve_map_minute (future_map, tempo_copy, minute_at_frame (frame))) {
2985                                 if (sub_num != 0) {
2986                                         /* We're moving the object that defines the grid while snapping to it...
2987                                          * Placing the ts at the beat corresponding to the requested frame may shift the
2988                                          * grid in such a way that the mouse is left hovering over a completerly different division,
2989                                          * causing jittering when the mouse next moves (esp. large tempo deltas).
2990                                          * To avoid this, place the ts at the requested frame in a dummy map
2991                                          * then find the closest beat subdivision to that frame in the dummy.
2992                                          * This alters the snap behaviour slightly in that we snap to beat divisions
2993                                          * in the future map rather than the existing one.
2994                                          */
2995                                         const double beat = exact_beat_at_frame_locked (future_map, frame, sub_num);
2996                                         const double pulse = pulse_at_beat_locked (future_map, beat);
2997
2998                                         if (solve_map_pulse (future_map, tempo_copy, pulse)) {
2999                                                 /* snapping to a grid. force MusicTime temporarily. */
3000                                                 ts->set_position_lock_style (MusicTime);
3001                                                 solve_map_pulse (_metrics, ts, pulse);
3002                                                 ts->set_position_lock_style (AudioTime);
3003
3004                                                 recompute_meters (_metrics);
3005                                         }
3006                                 } else {
3007                                         solve_map_minute (_metrics, ts, minute_at_frame (frame));
3008                                         recompute_meters (_metrics);
3009                                 }
3010                         }
3011                 }
3012         }
3013
3014         Metrics::const_iterator d = future_map.begin();
3015         while (d != future_map.end()) {
3016                 delete (*d);
3017                 ++d;
3018         }
3019
3020         MetricPositionChanged (); // Emit Signal
3021 }
3022
3023 void
3024 TempoMap::gui_move_meter (MeterSection* ms, const framepos_t& frame)
3025 {
3026         Metrics future_map;
3027
3028         if (ms->position_lock_style() == AudioTime) {
3029
3030                 {
3031                         Glib::Threads::RWLock::WriterLock lm (lock);
3032                         MeterSection* copy = copy_metrics_and_point (_metrics, future_map, ms);
3033
3034                         if (solve_map_minute (future_map, copy, minute_at_frame (frame))) {
3035                                 solve_map_minute (_metrics, ms, minute_at_frame (frame));
3036                                 recompute_tempi (_metrics);
3037                         }
3038                 }
3039         } else {
3040                 {
3041                         Glib::Threads::RWLock::WriterLock lm (lock);
3042                         MeterSection* copy = copy_metrics_and_point (_metrics, future_map, ms);
3043
3044                         const double beat = beat_at_minute_locked (_metrics, minute_at_frame (frame));
3045                         const Timecode::BBT_Time bbt = bbt_at_beat_locked (_metrics, beat);
3046
3047                         if (solve_map_bbt (future_map, copy, bbt)) {
3048                                 solve_map_bbt (_metrics, ms, bbt);
3049                                 recompute_tempi (_metrics);
3050                         }
3051                 }
3052         }
3053
3054         Metrics::const_iterator d = future_map.begin();
3055         while (d != future_map.end()) {
3056                 delete (*d);
3057                 ++d;
3058         }
3059
3060         MetricPositionChanged (); // Emit Signal
3061 }
3062
3063 bool
3064 TempoMap::gui_change_tempo (TempoSection* ts, const Tempo& bpm)
3065 {
3066         Metrics future_map;
3067         bool can_solve = false;
3068         {
3069                 Glib::Threads::RWLock::WriterLock lm (lock);
3070                 TempoSection* tempo_copy = copy_metrics_and_point (_metrics, future_map, ts);
3071                 tempo_copy->set_beats_per_minute (bpm.beats_per_minute());
3072                 recompute_tempi (future_map);
3073
3074                 if (check_solved (future_map)) {
3075                         ts->set_beats_per_minute (bpm.beats_per_minute());
3076                         recompute_map (_metrics);
3077                         can_solve = true;
3078                 }
3079         }
3080
3081         Metrics::const_iterator d = future_map.begin();
3082         while (d != future_map.end()) {
3083                 delete (*d);
3084                 ++d;
3085         }
3086         if (can_solve) {
3087                 MetricPositionChanged (); // Emit Signal
3088         }
3089         return can_solve;
3090 }
3091
3092 void
3093 TempoMap::gui_dilate_tempo (TempoSection* ts, const framepos_t& frame, const framepos_t& end_frame, const double& pulse)
3094 {
3095         /*
3096           Ts (future prev_t)   Tnext
3097           |                    |
3098           |     [drag^]        |
3099           |----------|----------
3100                 e_f  pulse(frame)
3101         */
3102
3103         Metrics future_map;
3104
3105         {
3106                 Glib::Threads::RWLock::WriterLock lm (lock);
3107
3108                 if (!ts) {
3109                         return;
3110                 }
3111
3112                 TempoSection* prev_t = copy_metrics_and_point (_metrics, future_map, ts);
3113                 TempoSection* prev_to_prev_t = 0;
3114                 const frameoffset_t fr_off = end_frame - frame;
3115
3116                 if (prev_t && prev_t->pulse() > 0.0) {
3117                         prev_to_prev_t = const_cast<TempoSection*>(&tempo_section_at_minute_locked (future_map, minute_at_frame (prev_t->frame() - 1)));
3118                 }
3119
3120                 TempoSection* next_t = 0;
3121                 for (Metrics::iterator i = future_map.begin(); i != future_map.end(); ++i) {
3122                         TempoSection* t = 0;
3123                         if ((*i)->is_tempo()) {
3124                                 t = static_cast<TempoSection*> (*i);
3125                                 if (t->frame() > ts->frame()) {
3126                                         next_t = t;
3127                                         break;
3128                                 }
3129                         }
3130                 }
3131                 /* minimum allowed measurement distance in frames */
3132                 const framepos_t min_dframe = 2;
3133
3134                 /* the change in frames is the result of changing the slope of at most 2 previous tempo sections.
3135                    constant to constant is straightforward, as the tempo prev to prev_t has constant slope.
3136                 */
3137                 double contribution = 0.0;
3138
3139                 if (next_t && prev_to_prev_t && prev_to_prev_t->type() == TempoSection::Ramp) {
3140                         contribution = (prev_t->frame() - prev_to_prev_t->frame()) / (double) (next_t->frame() - prev_to_prev_t->frame());
3141                 }
3142
3143                 const frameoffset_t prev_t_frame_contribution = fr_off - (contribution * (double) fr_off);
3144
3145                 const double start_pulse = prev_t->pulse_at_frame (frame);
3146                 const double end_pulse = prev_t->pulse_at_frame (end_frame);
3147
3148                 double new_bpm;
3149
3150                 if (prev_t->type() == TempoSection::Constant || prev_t->c_func() == 0.0) {
3151
3152                         if (prev_t->position_lock_style() == MusicTime) {
3153                                 if (prev_to_prev_t && prev_to_prev_t->type() == TempoSection::Ramp) {
3154                                         if (frame > prev_to_prev_t->frame() + min_dframe && (frame + prev_t_frame_contribution) > prev_to_prev_t->frame() + min_dframe) {
3155
3156                                                 new_bpm = prev_t->beats_per_minute() * ((frame - prev_to_prev_t->frame())
3157                                                                                         / (double) ((frame + prev_t_frame_contribution) - prev_to_prev_t->frame()));
3158                                         } else {
3159                                                 new_bpm = prev_t->beats_per_minute();
3160                                         }
3161                                 } else {
3162                                         /* prev to prev is irrelevant */
3163
3164                                         if (start_pulse > prev_t->pulse() && end_pulse > prev_t->pulse()) {
3165                                                 new_bpm = prev_t->beats_per_minute() * ((start_pulse - prev_t->pulse()) / (end_pulse - prev_t->pulse()));
3166                                         } else {
3167                                                 new_bpm = prev_t->beats_per_minute();
3168                                         }
3169                                 }
3170                         } else {
3171                                 /* AudioTime */
3172                                 if (prev_to_prev_t && prev_to_prev_t->type() == TempoSection::Ramp) {
3173                                         if (frame > prev_to_prev_t->frame() + min_dframe && end_frame > prev_to_prev_t->frame() + min_dframe) {
3174
3175                                                 new_bpm = prev_t->beats_per_minute() * ((frame - prev_to_prev_t->frame())
3176                                                                                         / (double) ((end_frame) - prev_to_prev_t->frame()));
3177                                         } else {
3178                                                 new_bpm = prev_t->beats_per_minute();
3179                                         }
3180                                 } else {
3181                                         /* prev_to_prev_t is irrelevant */
3182
3183                                         if (frame > prev_t->frame() + min_dframe && end_frame > prev_t->frame() + min_dframe) {
3184                                                 new_bpm = prev_t->beats_per_minute() * ((frame - prev_t->frame()) / (double) (end_frame - prev_t->frame()));
3185                                         } else {
3186                                                 new_bpm = prev_t->beats_per_minute();
3187                                         }
3188                                 }
3189                         }
3190                 } else {
3191
3192                         double frame_ratio = 1.0;
3193                         double pulse_ratio = 1.0;
3194                         const double pulse_pos = prev_t->frame_at_pulse (pulse);
3195
3196                         if (prev_to_prev_t) {
3197                                 if (pulse_pos > prev_to_prev_t->frame() + min_dframe && (pulse_pos - fr_off) > prev_to_prev_t->frame() + min_dframe) {
3198                                         frame_ratio = (((pulse_pos - fr_off) - prev_to_prev_t->frame()) / (double) ((pulse_pos) - prev_to_prev_t->frame()));
3199                                 }
3200                                 if (end_pulse > prev_to_prev_t->pulse() && start_pulse > prev_to_prev_t->pulse()) {
3201                                         pulse_ratio = ((start_pulse - prev_to_prev_t->pulse()) / (end_pulse - prev_to_prev_t->pulse()));
3202                                 }
3203                         } else {
3204                                 if (pulse_pos > prev_t->frame() + min_dframe && (pulse_pos - fr_off) > prev_t->frame() + min_dframe) {
3205                                         frame_ratio = (((pulse_pos - fr_off) - prev_t->frame()) / (double) ((pulse_pos) - prev_t->frame()));
3206                                 }
3207                                 pulse_ratio = (start_pulse / end_pulse);
3208                         }
3209                         new_bpm = prev_t->beats_per_minute() * (pulse_ratio * frame_ratio);
3210                 }
3211
3212                 /* don't clamp and proceed here.
3213                    testing has revealed that this can go negative,
3214                    which is an entirely different thing to just being too low.
3215                 */
3216                 if (new_bpm < 0.5) {
3217                         return;
3218                 }
3219                 new_bpm = min (new_bpm, (double) 1000.0);
3220                 prev_t->set_beats_per_minute (new_bpm);
3221                 recompute_tempi (future_map);
3222                 recompute_meters (future_map);
3223
3224                 if (check_solved (future_map)) {
3225                         ts->set_beats_per_minute (new_bpm);
3226                         recompute_tempi (_metrics);
3227                         recompute_meters (_metrics);
3228                 }
3229         }
3230
3231         Metrics::const_iterator d = future_map.begin();
3232         while (d != future_map.end()) {
3233                 delete (*d);
3234                 ++d;
3235         }
3236
3237         MetricPositionChanged (); // Emit Signal
3238 }
3239
3240 /** Returns the exact beat corresponding to the bar, beat or quarter note subdivision nearest to
3241  * the supplied frame, possibly returning a negative value.
3242  * @param frame  The session frame position.
3243  * @param sub_num The subdivision to use when rounding the beat.
3244  * A value of -1 indicates rounding to BBT bar. 1 indicates rounding to BBT beats.
3245  * Positive integers indicate quarter note (non BBT) divisions.
3246  * 0 indicates that the returned beat should not be rounded.
3247  * @return The beat position of the supplied frame.
3248  * If the supplied frame lies before the first meter, the return will be negative,
3249  * in which case the returned beat uses the first meter (for BBT subdivisions) and
3250  * the continuation of the tempo curve (backwards).
3251  *
3252  * This function uses both tempo and meter.
3253  */
3254 double
3255 TempoMap::exact_beat_at_frame (const framepos_t& frame, const int32_t sub_num)
3256 {
3257         Glib::Threads::RWLock::ReaderLock lm (lock);
3258
3259         return exact_beat_at_frame_locked (_metrics, frame, sub_num);
3260 }
3261
3262 double
3263 TempoMap::exact_beat_at_frame_locked (const Metrics& metrics, const framepos_t& frame, const int32_t divisions)
3264 {
3265         return beat_at_pulse_locked (_metrics, exact_qn_at_frame_locked (metrics, frame, divisions) / 4.0);
3266 }
3267
3268 /** Returns the exact quarter note corresponding to the bar, beat or quarter note subdivision nearest to
3269  * the supplied frame, possibly returning a negative value.
3270  * @param frame  The session frame position.
3271  * @param sub_num The subdivision to use when rounding the quarter note.
3272  * A value of -1 indicates rounding to BBT bar. 1 indicates rounding to BBT beats.
3273  * Positive integers indicate quarter note (non BBT) divisions.
3274  * 0 indicates that the returned quarter note should not be rounded.
3275  * @return The quarter note position of the supplied frame.
3276  * If the supplied frame lies before the first meter, the return will be negative,
3277  * in which case the returned quarter note uses the first meter (for BBT subdivisions) and
3278  * the continuation of the tempo curve (backwards).
3279  *
3280  * This function uses both tempo and meter.
3281  */
3282 double
3283 TempoMap::exact_qn_at_frame (const framepos_t& frame, const int32_t sub_num)
3284 {
3285         Glib::Threads::RWLock::ReaderLock lm (lock);
3286
3287         return exact_qn_at_frame_locked (_metrics, frame, sub_num);
3288 }
3289
3290 double
3291 TempoMap::exact_qn_at_frame_locked (const Metrics& metrics, const framepos_t& frame, const int32_t sub_num)
3292 {
3293         double qn = quarter_note_at_minute_locked (metrics, minute_at_frame (frame));
3294
3295         if (sub_num > 1) {
3296                 qn = floor (qn) + (floor (((qn - floor (qn)) * (double) sub_num) + 0.5) / sub_num);
3297         } else if (sub_num == 1) {
3298                 /* the gui requested exact musical (BBT) beat */
3299                 qn = quarter_note_at_beat_locked (metrics, floor (beat_at_minute_locked (metrics, minute_at_frame (frame)) + 0.5));
3300         } else if (sub_num == -1) {
3301                 /* snap to  bar */
3302                 Timecode::BBT_Time bbt = bbt_at_pulse_locked (metrics, qn / 4.0);
3303                 bbt.beats = 1;
3304                 bbt.ticks = 0;
3305
3306                 const double prev_b = pulse_at_bbt_locked (metrics, bbt) * 4.0;
3307                 ++bbt.bars;
3308                 const double next_b = pulse_at_bbt_locked (metrics, bbt) * 4.0;
3309
3310                 if ((qn - prev_b) > (next_b - prev_b) / 2.0) {
3311                         qn = next_b;
3312                 } else {
3313                         qn = prev_b;
3314                 }
3315         }
3316
3317         return qn;
3318 }
3319
3320 framecnt_t
3321 TempoMap::bbt_duration_at (framepos_t pos, const BBT_Time& bbt, int dir)
3322 {
3323         Glib::Threads::RWLock::ReaderLock lm (lock);
3324
3325         BBT_Time pos_bbt = bbt_at_minute_locked (_metrics, minute_at_frame (pos));
3326         const framecnt_t offset = frame_at_minute (minute_at_bbt_locked (_metrics, pos_bbt));
3327         const double divisions = meter_section_at_minute_locked (_metrics, minute_at_frame (pos)).divisions_per_bar();
3328
3329         if (dir > 0) {
3330                 pos_bbt.bars += bbt.bars;
3331
3332                 pos_bbt.ticks += bbt.ticks;
3333                 if ((double) pos_bbt.ticks > BBT_Time::ticks_per_beat) {
3334                         pos_bbt.beats += 1;
3335                         pos_bbt.ticks -= BBT_Time::ticks_per_beat;
3336                 }
3337
3338                 pos_bbt.beats += bbt.beats;
3339                 if ((double) pos_bbt.beats > divisions) {
3340                         pos_bbt.bars += 1;
3341                         pos_bbt.beats -= divisions;
3342                 }
3343
3344                 return frame_at_minute (minute_at_bbt_locked (_metrics, pos_bbt)) - offset;
3345         } else {
3346                 pos_bbt.bars -= bbt.bars;
3347
3348                 if (pos_bbt.ticks < bbt.ticks) {
3349                         if (pos_bbt.beats == 1) {
3350                                 pos_bbt.bars--;
3351                                 pos_bbt.beats = divisions;
3352                         } else {
3353                                 pos_bbt.beats--;
3354                         }
3355                         pos_bbt.ticks = BBT_Time::ticks_per_beat - (bbt.ticks - pos_bbt.ticks);
3356                 } else {
3357                         pos_bbt.ticks -= bbt.ticks;
3358                 }
3359
3360                 if (pos_bbt.beats <= bbt.beats) {
3361                         pos_bbt.bars--;
3362                         pos_bbt.beats = divisions - (bbt.beats - pos_bbt.beats);
3363                 } else {
3364                         pos_bbt.beats -= bbt.beats;
3365                 }
3366
3367                 return offset - frame_at_minute (minute_at_bbt_locked (_metrics, pos_bbt));
3368         }
3369
3370         return 0;
3371 }
3372
3373 framepos_t
3374 TempoMap::round_to_bar (framepos_t fr, RoundMode dir)
3375 {
3376         return round_to_type (fr, dir, Bar);
3377 }
3378
3379 framepos_t
3380 TempoMap::round_to_beat (framepos_t fr, RoundMode dir)
3381 {
3382         return round_to_type (fr, dir, Beat);
3383 }
3384
3385 framepos_t
3386 TempoMap::round_to_beat_subdivision (framepos_t fr, int sub_num, RoundMode dir)
3387 {
3388         Glib::Threads::RWLock::ReaderLock lm (lock);
3389         uint32_t ticks = (uint32_t) floor (max (0.0, beat_at_minute_locked (_metrics, minute_at_frame (fr))) * BBT_Time::ticks_per_beat);
3390         uint32_t beats = (uint32_t) floor (ticks / BBT_Time::ticks_per_beat);
3391         uint32_t ticks_one_subdivisions_worth = (uint32_t) BBT_Time::ticks_per_beat / sub_num;
3392
3393         ticks -= beats * BBT_Time::ticks_per_beat;
3394
3395         if (dir > 0) {
3396                 /* round to next (or same iff dir == RoundUpMaybe) */
3397
3398                 uint32_t mod = ticks % ticks_one_subdivisions_worth;
3399
3400                 if (mod == 0 && dir == RoundUpMaybe) {
3401                         /* right on the subdivision, which is fine, so do nothing */
3402
3403                 } else if (mod == 0) {
3404                         /* right on the subdivision, so the difference is just the subdivision ticks */
3405                         ticks += ticks_one_subdivisions_worth;
3406
3407                 } else {
3408                         /* not on subdivision, compute distance to next subdivision */
3409
3410                         ticks += ticks_one_subdivisions_worth - mod;
3411                 }
3412
3413                 if (ticks >= BBT_Time::ticks_per_beat) {
3414                         ticks -= BBT_Time::ticks_per_beat;
3415                 }
3416         } else if (dir < 0) {
3417
3418                 /* round to previous (or same iff dir == RoundDownMaybe) */
3419
3420                 uint32_t difference = ticks % ticks_one_subdivisions_worth;
3421
3422                 if (difference == 0 && dir == RoundDownAlways) {
3423                         /* right on the subdivision, but force-rounding down,
3424                            so the difference is just the subdivision ticks */
3425                         difference = ticks_one_subdivisions_worth;
3426                 }
3427
3428                 if (ticks < difference) {
3429                         ticks = BBT_Time::ticks_per_beat - ticks;
3430                 } else {
3431                         ticks -= difference;
3432                 }
3433
3434         } else {
3435                 /* round to nearest */
3436                 double rem;
3437
3438                 /* compute the distance to the previous and next subdivision */
3439
3440                 if ((rem = fmod ((double) ticks, (double) ticks_one_subdivisions_worth)) > ticks_one_subdivisions_worth/2.0) {
3441
3442                         /* closer to the next subdivision, so shift forward */
3443
3444                         ticks = lrint (ticks + (ticks_one_subdivisions_worth - rem));
3445
3446                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("moved forward to %1\n", ticks));
3447
3448                         if (ticks > BBT_Time::ticks_per_beat) {
3449                                 ++beats;
3450                                 ticks -= BBT_Time::ticks_per_beat;
3451                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("fold beat to %1\n", beats));
3452                         }
3453
3454                 } else if (rem > 0) {
3455
3456                         /* closer to previous subdivision, so shift backward */
3457
3458                         if (rem > ticks) {
3459                                 if (beats == 0) {
3460                                         /* can't go backwards past zero, so ... */
3461                                         return 0;
3462                                 }
3463                                 /* step back to previous beat */
3464                                 --beats;
3465                                 ticks = lrint (BBT_Time::ticks_per_beat - rem);
3466                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("step back beat to %1\n", beats));
3467                         } else {
3468                                 ticks = lrint (ticks - rem);
3469                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("moved backward to %1\n", ticks));
3470                         }
3471                 } else {
3472                         /* on the subdivision, do nothing */
3473                 }
3474         }
3475
3476         const framepos_t ret_frame = frame_at_minute (minute_at_beat_locked (_metrics, beats + (ticks / BBT_Time::ticks_per_beat)));
3477
3478         return ret_frame;
3479 }
3480
3481 framepos_t
3482 TempoMap::round_to_quarter_note_subdivision (framepos_t fr, int sub_num, RoundMode dir)
3483 {
3484         Glib::Threads::RWLock::ReaderLock lm (lock);
3485         uint32_t ticks = (uint32_t) floor (max (0.0, quarter_note_at_minute_locked (_metrics, minute_at_frame (fr))) * BBT_Time::ticks_per_beat);
3486         uint32_t beats = (uint32_t) floor (ticks / BBT_Time::ticks_per_beat);
3487         uint32_t ticks_one_subdivisions_worth = (uint32_t) BBT_Time::ticks_per_beat / sub_num;
3488
3489         ticks -= beats * BBT_Time::ticks_per_beat;
3490
3491         if (dir > 0) {
3492                 /* round to next (or same iff dir == RoundUpMaybe) */
3493
3494                 uint32_t mod = ticks % ticks_one_subdivisions_worth;
3495
3496                 if (mod == 0 && dir == RoundUpMaybe) {
3497                         /* right on the subdivision, which is fine, so do nothing */
3498
3499                 } else if (mod == 0) {
3500                         /* right on the subdivision, so the difference is just the subdivision ticks */
3501                         ticks += ticks_one_subdivisions_worth;
3502
3503                 } else {
3504                         /* not on subdivision, compute distance to next subdivision */
3505
3506                         ticks += ticks_one_subdivisions_worth - mod;
3507                 }
3508
3509                 if (ticks >= BBT_Time::ticks_per_beat) {
3510                         ticks -= BBT_Time::ticks_per_beat;
3511                 }
3512         } else if (dir < 0) {
3513
3514                 /* round to previous (or same iff dir == RoundDownMaybe) */
3515
3516                 uint32_t difference = ticks % ticks_one_subdivisions_worth;
3517
3518                 if (difference == 0 && dir == RoundDownAlways) {
3519                         /* right on the subdivision, but force-rounding down,
3520                            so the difference is just the subdivision ticks */
3521                         difference = ticks_one_subdivisions_worth;
3522                 }
3523
3524                 if (ticks < difference) {
3525                         ticks = BBT_Time::ticks_per_beat - ticks;
3526                 } else {
3527                         ticks -= difference;
3528                 }
3529
3530         } else {
3531                 /* round to nearest */
3532                 double rem;
3533
3534                 /* compute the distance to the previous and next subdivision */
3535
3536                 if ((rem = fmod ((double) ticks, (double) ticks_one_subdivisions_worth)) > ticks_one_subdivisions_worth/2.0) {
3537
3538                         /* closer to the next subdivision, so shift forward */
3539
3540                         ticks = lrint (ticks + (ticks_one_subdivisions_worth - rem));
3541
3542                         DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("moved forward to %1\n", ticks));
3543
3544                         if (ticks > BBT_Time::ticks_per_beat) {
3545                                 ++beats;
3546                                 ticks -= BBT_Time::ticks_per_beat;
3547                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("fold beat to %1\n", beats));
3548                         }
3549
3550                 } else if (rem > 0) {
3551
3552                         /* closer to previous subdivision, so shift backward */
3553
3554                         if (rem > ticks) {
3555                                 if (beats == 0) {
3556                                         /* can't go backwards past zero, so ... */
3557                                         return 0;
3558                                 }
3559                                 /* step back to previous beat */
3560                                 --beats;
3561                                 ticks = lrint (BBT_Time::ticks_per_beat - rem);
3562                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("step back beat to %1\n", beats));
3563                         } else {
3564                                 ticks = lrint (ticks - rem);
3565                                 DEBUG_TRACE (DEBUG::SnapBBT, string_compose ("moved backward to %1\n", ticks));
3566                         }
3567                 } else {
3568                         /* on the subdivision, do nothing */
3569                 }
3570         }
3571
3572         const framepos_t ret_frame = frame_at_minute (minute_at_quarter_note_locked (_metrics, beats + (ticks / BBT_Time::ticks_per_beat)));
3573
3574         return ret_frame;
3575 }
3576
3577 framepos_t
3578 TempoMap::round_to_type (framepos_t frame, RoundMode dir, BBTPointType type)
3579 {
3580         Glib::Threads::RWLock::ReaderLock lm (lock);
3581
3582         const double beat_at_framepos = max (0.0, beat_at_minute_locked (_metrics, minute_at_frame (frame)));
3583         BBT_Time bbt (bbt_at_beat_locked (_metrics, beat_at_framepos));
3584
3585         switch (type) {
3586         case Bar:
3587                 if (dir < 0) {
3588                         /* find bar previous to 'frame' */
3589                         bbt.beats = 1;
3590                         bbt.ticks = 0;
3591                         return frame_at_minute (minute_at_bbt_locked (_metrics, bbt));
3592
3593                 } else if (dir > 0) {
3594                         /* find bar following 'frame' */
3595                         ++bbt.bars;
3596                         bbt.beats = 1;
3597                         bbt.ticks = 0;
3598                         return frame_at_minute (minute_at_bbt_locked (_metrics, bbt));
3599                 } else {
3600                         /* true rounding: find nearest bar */
3601                         framepos_t raw_ft = frame_at_minute (minute_at_bbt_locked (_metrics, bbt));
3602                         bbt.beats = 1;
3603                         bbt.ticks = 0;
3604                         framepos_t prev_ft = frame_at_minute (minute_at_bbt_locked (_metrics, bbt));
3605                         ++bbt.bars;
3606                         framepos_t next_ft = frame_at_minute (minute_at_bbt_locked (_metrics, bbt));
3607
3608                         if ((raw_ft - prev_ft) > (next_ft - prev_ft) / 2) {
3609                                 return next_ft;
3610                         } else {
3611                                 return prev_ft;
3612                         }
3613                 }
3614
3615                 break;
3616
3617         case Beat:
3618                 if (dir < 0) {
3619                         return frame_at_minute (minute_at_beat_locked (_metrics, floor (beat_at_framepos)));
3620                 } else if (dir > 0) {
3621                         return frame_at_minute (minute_at_beat_locked (_metrics, ceil (beat_at_framepos)));
3622                 } else {
3623                         return frame_at_minute (minute_at_beat_locked (_metrics, floor (beat_at_framepos + 0.5)));
3624                 }
3625                 break;
3626         }
3627
3628         return 0;
3629 }
3630
3631 void
3632 TempoMap::get_grid (vector<TempoMap::BBTPoint>& points,
3633                     framepos_t lower, framepos_t upper, uint32_t bar_mod)
3634 {
3635         Glib::Threads::RWLock::ReaderLock lm (lock);
3636         int32_t cnt = ceil (beat_at_minute_locked (_metrics, minute_at_frame (lower)));
3637         framecnt_t pos = 0;
3638         /* although the map handles negative beats, bbt doesn't. */
3639         if (cnt < 0.0) {
3640                 cnt = 0.0;
3641         }
3642
3643         if (minute_at_beat_locked (_metrics, cnt) >= minute_at_frame (upper)) {
3644                 return;
3645         }
3646         if (bar_mod == 0) {
3647                 while (pos >= 0 && pos < upper) {
3648                         pos = frame_at_minute (minute_at_beat_locked (_metrics, cnt));
3649                         const TempoSection tempo = tempo_section_at_minute_locked (_metrics, minute_at_frame (pos));
3650                         const MeterSection meter = meter_section_at_minute_locked (_metrics, minute_at_frame (pos));
3651                         const BBT_Time bbt = bbt_at_beat_locked (_metrics, cnt);
3652                         points.push_back (BBTPoint (meter, tempo_at_minute_locked (_metrics, minute_at_frame (pos)), pos, bbt.bars, bbt.beats, tempo.c_func()));
3653                         ++cnt;
3654                 }
3655         } else {
3656                 BBT_Time bbt = bbt_at_minute_locked (_metrics, minute_at_frame (lower));
3657                 bbt.beats = 1;
3658                 bbt.ticks = 0;
3659
3660                 if (bar_mod != 1) {
3661                         bbt.bars -= bbt.bars % bar_mod;
3662                         ++bbt.bars;
3663                 }
3664
3665                 while (pos >= 0 && pos < upper) {
3666                         pos = frame_at_minute (minute_at_bbt_locked (_metrics, bbt));
3667                         const TempoSection tempo = tempo_section_at_minute_locked (_metrics, minute_at_frame (pos));
3668                         const MeterSection meter = meter_section_at_minute_locked (_metrics, minute_at_frame (pos));
3669                         points.push_back (BBTPoint (meter, tempo_at_minute_locked (_metrics, minute_at_frame (pos)), pos, bbt.bars, bbt.beats, tempo.c_func()));
3670                         bbt.bars += bar_mod;
3671                 }
3672         }
3673 }
3674
3675 const TempoSection&
3676 TempoMap::tempo_section_at_frame (framepos_t frame) const
3677 {
3678         Glib::Threads::RWLock::ReaderLock lm (lock);
3679
3680         return tempo_section_at_minute_locked (_metrics, minute_at_frame (frame));
3681 }
3682
3683 const TempoSection&
3684 TempoMap::tempo_section_at_minute_locked (const Metrics& metrics, double minute) const
3685 {
3686         TempoSection* prev = 0;
3687
3688         TempoSection* t;
3689
3690         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
3691
3692                 if ((*i)->is_tempo()) {
3693                         t = static_cast<TempoSection*> (*i);
3694                         if (!t->active()) {
3695                                 continue;
3696                         }
3697                         if (prev && t->minute() > minute) {
3698                                 break;
3699                         }
3700
3701                         prev = t;
3702                 }
3703         }
3704
3705         if (prev == 0) {
3706                 fatal << endmsg;
3707                 abort(); /*NOTREACHED*/
3708         }
3709
3710         return *prev;
3711 }
3712
3713 const TempoSection&
3714 TempoMap::tempo_section_at_beat_locked (const Metrics& metrics, const double& beat) const
3715 {
3716         TempoSection* prev_t = 0;
3717         const MeterSection* prev_m = &meter_section_at_beat_locked (metrics, beat);
3718
3719         TempoSection* t;
3720
3721         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
3722                 if ((*i)->is_tempo()) {
3723                         t = static_cast<TempoSection*> (*i);
3724                         if (prev_t && ((t->pulse() - prev_m->pulse()) * prev_m->note_divisor()) + prev_m->beat() > beat) {
3725                                 break;
3726                         }
3727                         prev_t = t;
3728                 }
3729
3730         }
3731         return *prev_t;
3732 }
3733
3734 /* don't use this to calculate length (the tempo is only correct for this frame).
3735    do that stuff based on the beat_at_frame and frame_at_beat api
3736 */
3737 double
3738 TempoMap::frames_per_beat_at (const framepos_t& frame, const framecnt_t& sr) const
3739 {
3740         Glib::Threads::RWLock::ReaderLock lm (lock);
3741
3742         const TempoSection* ts_at = 0;
3743         const TempoSection* ts_after = 0;
3744         Metrics::const_iterator i;
3745         TempoSection* t;
3746
3747         for (i = _metrics.begin(); i != _metrics.end(); ++i) {
3748
3749                 if ((*i)->is_tempo()) {
3750                         t = static_cast<TempoSection*> (*i);
3751                         if (!t->active()) {
3752                                 continue;
3753                         }
3754                         if (ts_at && (*i)->frame() > frame) {
3755                                 ts_after = t;
3756                                 break;
3757                         }
3758                         ts_at = t;
3759                 }
3760         }
3761
3762         if (ts_after) {
3763                 return  (60.0 * _frame_rate) / ts_at->tempo_at_minute (minute_at_frame (frame));
3764         }
3765         /* must be treated as constant tempo */
3766         return ts_at->frames_per_beat (_frame_rate);
3767 }
3768
3769 const MeterSection&
3770 TempoMap::meter_section_at_frame (framepos_t frame) const
3771 {
3772         Glib::Threads::RWLock::ReaderLock lm (lock);
3773         return meter_section_at_minute_locked (_metrics, minute_at_frame (frame));
3774 }
3775
3776 const MeterSection&
3777 TempoMap::meter_section_at_minute_locked (const Metrics& metrics, double minute) const
3778 {
3779         Metrics::const_iterator i;
3780         MeterSection* prev = 0;
3781
3782         MeterSection* m;
3783
3784         for (i = metrics.begin(); i != metrics.end(); ++i) {
3785
3786                 if (!(*i)->is_tempo()) {
3787                         m = static_cast<MeterSection*> (*i);
3788
3789                         if (prev && (*i)->minute() > minute) {
3790                                 break;
3791                         }
3792
3793                         prev = m;
3794                 }
3795         }
3796
3797         if (prev == 0) {
3798                 fatal << endmsg;
3799                 abort(); /*NOTREACHED*/
3800         }
3801
3802         return *prev;
3803 }
3804
3805 const MeterSection&
3806 TempoMap::meter_section_at_beat_locked (const Metrics& metrics, const double& beat) const
3807 {
3808         MeterSection* prev_m = 0;
3809
3810         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
3811                 MeterSection* m;
3812                 if (!(*i)->is_tempo()) {
3813                         m = static_cast<MeterSection*> (*i);
3814                         if (prev_m && m->beat() > beat) {
3815                                 break;
3816                         }
3817                         prev_m = m;
3818                 }
3819
3820         }
3821         return *prev_m;
3822 }
3823
3824 const MeterSection&
3825 TempoMap::meter_section_at_beat (double beat) const
3826 {
3827         Glib::Threads::RWLock::ReaderLock lm (lock);
3828         return meter_section_at_beat_locked (_metrics, beat);
3829 }
3830
3831 const Meter&
3832 TempoMap::meter_at_frame (framepos_t frame) const
3833 {
3834         TempoMetric m (metric_at (frame));
3835         return m.meter();
3836 }
3837
3838 void
3839 TempoMap::fix_legacy_session ()
3840 {
3841         MeterSection* prev_m = 0;
3842         TempoSection* prev_t = 0;
3843
3844         for (Metrics::iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
3845                 MeterSection* m;
3846                 TempoSection* t;
3847
3848                 if ((m = dynamic_cast<MeterSection*>(*i)) != 0) {
3849                         if (!m->movable()) {
3850                                 pair<double, BBT_Time> bbt = make_pair (0.0, BBT_Time (1, 1, 0));
3851                                 m->set_beat (bbt);
3852                                 m->set_pulse (0.0);
3853                                 m->set_minute (0.0);
3854                                 m->set_position_lock_style (AudioTime);
3855                                 prev_m = m;
3856                                 continue;
3857                         }
3858                         if (prev_m) {
3859                                 pair<double, BBT_Time> start = make_pair (((m->bbt().bars - 1) * prev_m->note_divisor())
3860                                                                           + (m->bbt().beats - 1)
3861                                                                           + (m->bbt().ticks / BBT_Time::ticks_per_beat)
3862                                                                           , m->bbt());
3863                                 m->set_beat (start);
3864                                 const double start_beat = ((m->bbt().bars - 1) * prev_m->note_divisor())
3865                                         + (m->bbt().beats - 1)
3866                                         + (m->bbt().ticks / BBT_Time::ticks_per_beat);
3867                                 m->set_pulse (start_beat / prev_m->note_divisor());
3868                         }
3869                         prev_m = m;
3870                 } else if ((t = dynamic_cast<TempoSection*>(*i)) != 0) {
3871
3872                         if (!t->active()) {
3873                                 continue;
3874                         }
3875
3876                         if (!t->movable()) {
3877                                 t->set_pulse (0.0);
3878                                 t->set_minute (0.0);
3879                                 t->set_position_lock_style (AudioTime);
3880                                 prev_t = t;
3881                                 continue;
3882                         }
3883
3884                         if (prev_t) {
3885                                 const double beat = ((t->legacy_bbt().bars - 1) * ((prev_m) ? prev_m->note_divisor() : 4.0))
3886                                         + (t->legacy_bbt().beats - 1)
3887                                         + (t->legacy_bbt().ticks / BBT_Time::ticks_per_beat);
3888                                 if (prev_m) {
3889                                         t->set_pulse (beat / prev_m->note_divisor());
3890                                 } else {
3891                                         /* really shouldn't happen but.. */
3892                                         t->set_pulse (beat / 4.0);
3893                                 }
3894                         }
3895                         prev_t = t;
3896                 }
3897         }
3898 }
3899
3900 XMLNode&
3901 TempoMap::get_state ()
3902 {
3903         Metrics::const_iterator i;
3904         XMLNode *root = new XMLNode ("TempoMap");
3905
3906         {
3907                 Glib::Threads::RWLock::ReaderLock lm (lock);
3908                 for (i = _metrics.begin(); i != _metrics.end(); ++i) {
3909                         root->add_child_nocopy ((*i)->get_state());
3910                 }
3911         }
3912
3913         return *root;
3914 }
3915
3916 int
3917 TempoMap::set_state (const XMLNode& node, int /*version*/)
3918 {
3919         {
3920                 Glib::Threads::RWLock::WriterLock lm (lock);
3921
3922                 XMLNodeList nlist;
3923                 XMLNodeConstIterator niter;
3924                 Metrics old_metrics (_metrics);
3925                 _metrics.clear();
3926
3927                 nlist = node.children();
3928
3929                 for (niter = nlist.begin(); niter != nlist.end(); ++niter) {
3930                         XMLNode* child = *niter;
3931
3932                         if (child->name() == TempoSection::xml_state_node_name) {
3933
3934                                 try {
3935                                         TempoSection* ts = new TempoSection (*child, _frame_rate);
3936                                         _metrics.push_back (ts);
3937                                 }
3938
3939                                 catch (failed_constructor& err){
3940                                         error << _("Tempo map: could not set new state, restoring old one.") << endmsg;
3941                                         _metrics = old_metrics;
3942                                         old_metrics.clear();
3943                                         break;
3944                                 }
3945
3946                         } else if (child->name() == MeterSection::xml_state_node_name) {
3947
3948                                 try {
3949                                         MeterSection* ms = new MeterSection (*child, _frame_rate);
3950                                         _metrics.push_back (ms);
3951                                 }
3952
3953                                 catch (failed_constructor& err) {
3954                                         error << _("Tempo map: could not set new state, restoring old one.") << endmsg;
3955                                         _metrics = old_metrics;
3956                                         old_metrics.clear();
3957                                         break;
3958                                 }
3959                         }
3960                 }
3961
3962                 if (niter == nlist.end()) {
3963                         MetricSectionSorter cmp;
3964                         _metrics.sort (cmp);
3965                 }
3966
3967                 /* check for legacy sessions where bbt was the base musical unit for tempo */
3968                 for (Metrics::const_iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
3969                         TempoSection* t;
3970                         if ((t = dynamic_cast<TempoSection*> (*i)) != 0) {
3971                                 if (t->legacy_bbt().bars != 0) {
3972                                         fix_legacy_session();
3973                                         break;
3974                                 }
3975                                 break;
3976                         }
3977                 }
3978
3979                 /* check for multiple tempo/meters at the same location, which
3980                    ardour2 somehow allowed.
3981                 */
3982
3983                 Metrics::iterator prev = _metrics.end();
3984                 for (Metrics::iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
3985                         if (prev != _metrics.end()) {
3986                                 MeterSection* ms;
3987                                 MeterSection* prev_m;
3988                                 TempoSection* ts;
3989                                 TempoSection* prev_t;
3990                                 if ((prev_m = dynamic_cast<MeterSection*>(*prev)) != 0 && (ms = dynamic_cast<MeterSection*>(*i)) != 0) {
3991                                         if (prev_m->pulse() == ms->pulse()) {
3992                                                 cerr << string_compose (_("Multiple meter definitions found at %1"), prev_m->pulse()) << endmsg;
3993                                                 error << string_compose (_("Multiple meter definitions found at %1"), prev_m->pulse()) << endmsg;
3994                                                 return -1;
3995                                         }
3996                                 } else if ((prev_t = dynamic_cast<TempoSection*>(*prev)) != 0 && (ts = dynamic_cast<TempoSection*>(*i)) != 0) {
3997                                         if (prev_t->pulse() == ts->pulse()) {
3998                                                 cerr << string_compose (_("Multiple tempo definitions found at %1"), prev_t->pulse()) << endmsg;
3999                                                 error << string_compose (_("Multiple tempo definitions found at %1"), prev_t->pulse()) << endmsg;
4000                                                 return -1;
4001                                         }
4002                                 }
4003                         }
4004                         prev = i;
4005                 }
4006
4007                 recompute_map (_metrics);
4008
4009                 Metrics::const_iterator d = old_metrics.begin();
4010                 while (d != old_metrics.end()) {
4011                         delete (*d);
4012                         ++d;
4013                 }
4014                 old_metrics.clear ();
4015         }
4016
4017         PropertyChanged (PropertyChange ());
4018
4019         return 0;
4020 }
4021
4022 void
4023 TempoMap::dump (const Metrics& metrics, std::ostream& o) const
4024 {
4025         Glib::Threads::RWLock::ReaderLock lm (lock, Glib::Threads::TRY_LOCK);
4026         const MeterSection* m;
4027         const TempoSection* t;
4028         const TempoSection* prev_t = 0;
4029
4030         for (Metrics::const_iterator i = metrics.begin(); i != metrics.end(); ++i) {
4031
4032                 if ((t = dynamic_cast<const TempoSection*>(*i)) != 0) {
4033                         o << "Tempo @ " << *i << t->beats_per_minute() << " BPM (pulse = 1/" << t->note_type()
4034                           << " type= " << enum_2_string (t->type()) << ") "  << " at pulse= " << t->pulse()
4035                           << " minute= " << t->minute() << " frame= " << t->frame() << " (movable? " << t->movable() << ')'
4036                           << " pos lock: " << enum_2_string (t->position_lock_style()) << std::endl;
4037                         if (prev_t) {
4038                                 o << std::setprecision (17) << "  current      : " << t->beats_per_minute()
4039                                   << " | " << t->pulse() << " | " << t->frame() << " | " << t->minute() << std::endl;
4040                                 o << "  previous     : " << prev_t->beats_per_minute()
4041                                   << " | " << prev_t->pulse() << " | " << prev_t->frame() << " | " << prev_t->minute() << std::endl;
4042                                 o << "  calculated   : " << prev_t->tempo_at_pulse (t->pulse())
4043                                   << " | " << prev_t->pulse_at_tempo (t->beats_per_minute(), t->minute())
4044                                   << " | " << frame_at_minute (prev_t->minute_at_tempo (t->beats_per_minute(), t->pulse()))
4045                                   << " | " << prev_t->minute_at_tempo (t->beats_per_minute(), t->pulse()) << std::endl;
4046                         }
4047                         prev_t = t;
4048                 } else if ((m = dynamic_cast<const MeterSection*>(*i)) != 0) {
4049                         o << "Meter @ " << *i << ' ' << m->divisions_per_bar() << '/' << m->note_divisor() << " at " << m->bbt()
4050                           << " frame= " << m->frame() << " pulse: " << m->pulse() <<  " beat : " << m->beat()
4051                           << " pos lock: " << enum_2_string (m->position_lock_style()) << " (movable? " << m->movable() << ')' << endl;
4052                 }
4053         }
4054         o << "------" << std::endl;
4055 }
4056
4057 int
4058 TempoMap::n_tempos() const
4059 {
4060         Glib::Threads::RWLock::ReaderLock lm (lock);
4061         int cnt = 0;
4062
4063         for (Metrics::const_iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
4064                 if ((*i)->is_tempo()) {
4065                         cnt++;
4066                 }
4067         }
4068
4069         return cnt;
4070 }
4071
4072 int
4073 TempoMap::n_meters() const
4074 {
4075         Glib::Threads::RWLock::ReaderLock lm (lock);
4076         int cnt = 0;
4077
4078         for (Metrics::const_iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
4079                 if (!(*i)->is_tempo()) {
4080                         cnt++;
4081                 }
4082         }
4083
4084         return cnt;
4085 }
4086
4087 void
4088 TempoMap::insert_time (framepos_t where, framecnt_t amount)
4089 {
4090         for (Metrics::reverse_iterator i = _metrics.rbegin(); i != _metrics.rend(); ++i) {
4091                 if ((*i)->frame() >= where && (*i)->movable ()) {
4092                         MeterSection* ms;
4093                         TempoSection* ts;
4094
4095                         if ((ms = dynamic_cast <MeterSection*>(*i)) != 0) {
4096                                 gui_move_meter (ms, (*i)->frame() + amount);
4097                         }
4098
4099                         if ((ts = dynamic_cast <TempoSection*>(*i)) != 0) {
4100                                 gui_move_tempo (ts, (*i)->frame() + amount, 0);
4101                         }
4102                 }
4103         }
4104
4105         PropertyChanged (PropertyChange ());
4106 }
4107
4108 bool
4109 TempoMap::remove_time (framepos_t where, framecnt_t amount)
4110 {
4111         bool moved = false;
4112
4113         std::list<MetricSection*> metric_kill_list;
4114
4115         TempoSection* last_tempo = NULL;
4116         MeterSection* last_meter = NULL;
4117         bool tempo_after = false; // is there a tempo marker at the first sample after the removed range?
4118         bool meter_after = false; // is there a meter marker likewise?
4119         {
4120                 Glib::Threads::RWLock::WriterLock lm (lock);
4121                 for (Metrics::iterator i = _metrics.begin(); i != _metrics.end(); ++i) {
4122                         if ((*i)->frame() >= where && (*i)->frame() < where+amount) {
4123                                 metric_kill_list.push_back(*i);
4124                                 TempoSection *lt = dynamic_cast<TempoSection*> (*i);
4125                                 if (lt)
4126                                         last_tempo = lt;
4127                                 MeterSection *lm = dynamic_cast<MeterSection*> (*i);
4128                                 if (lm)
4129                                         last_meter = lm;
4130                         }
4131                         else if ((*i)->frame() >= where) {
4132                                 // TODO: make sure that moved tempo/meter markers are rounded to beat/bar boundaries
4133                                 (*i)->set_minute ((*i)->minute() - minute_at_frame (amount));
4134                                 if ((*i)->frame() == where) {
4135                                         // marker was immediately after end of range
4136                                         tempo_after = dynamic_cast<TempoSection*> (*i);
4137                                         meter_after = dynamic_cast<MeterSection*> (*i);
4138                                 }
4139                                 moved = true;
4140                         }
4141                 }
4142
4143                 //find the last TEMPO and METER metric (if any) and move it to the cut point so future stuff is correct
4144                 if (last_tempo && !tempo_after) {
4145                         metric_kill_list.remove(last_tempo);
4146                         last_tempo->set_minute (minute_at_frame (where));
4147                         moved = true;
4148                 }
4149                 if (last_meter && !meter_after) {
4150                         metric_kill_list.remove(last_meter);
4151                         last_meter->set_minute (minute_at_frame (where));
4152                         moved = true;
4153                 }
4154
4155                 //remove all the remaining metrics
4156                 for (std::list<MetricSection*>::iterator i = metric_kill_list.begin(); i != metric_kill_list.end(); ++i) {
4157                         _metrics.remove(*i);
4158                         moved = true;
4159                 }
4160
4161                 if (moved) {
4162                         recompute_map (_metrics);
4163                 }
4164         }
4165         PropertyChanged (PropertyChange ());
4166         return moved;
4167 }
4168
4169 /** Add some (fractional) Beats to a session frame position, and return the result in frames.
4170  *  pos can be -ve, if required.
4171  */
4172 framepos_t
4173 TempoMap::framepos_plus_qn (framepos_t frame, Evoral::Beats quarter_note) const
4174 {
4175         Glib::Threads::RWLock::ReaderLock lm (lock);
4176
4177         return frame_at_minute (minute_at_quarter_note_locked (_metrics, quarter_note_at_minute_locked (_metrics, minute_at_frame (frame)) + quarter_note.to_double()));
4178 }
4179
4180 framepos_t
4181 TempoMap::framepos_plus_bbt (framepos_t pos, BBT_Time op) const
4182 {
4183         Glib::Threads::RWLock::ReaderLock lm (lock);
4184
4185         BBT_Time pos_bbt = bbt_at_beat_locked (_metrics, beat_at_minute_locked (_metrics, minute_at_frame (pos)));
4186         pos_bbt.ticks += op.ticks;
4187         if (pos_bbt.ticks >= BBT_Time::ticks_per_beat) {
4188                 ++pos_bbt.beats;
4189                 pos_bbt.ticks -= BBT_Time::ticks_per_beat;
4190         }
4191         pos_bbt.beats += op.beats;
4192         /* the meter in effect will start on the bar */
4193         double divisions_per_bar = meter_section_at_beat (beat_at_bbt_locked (_metrics, BBT_Time (pos_bbt.bars + op.bars, 1, 0))).divisions_per_bar();
4194         while (pos_bbt.beats >= divisions_per_bar + 1) {
4195                 ++pos_bbt.bars;
4196                 divisions_per_bar = meter_section_at_beat (beat_at_bbt_locked (_metrics, BBT_Time (pos_bbt.bars + op.bars, 1, 0))).divisions_per_bar();
4197                 pos_bbt.beats -= divisions_per_bar;
4198         }
4199         pos_bbt.bars += op.bars;
4200
4201         return frame_at_minute (minute_at_bbt_locked (_metrics, pos_bbt));
4202 }
4203
4204 /** Count the number of beats that are equivalent to distance when going forward,
4205     starting at pos.
4206 */
4207 Evoral::Beats
4208 TempoMap::framewalk_to_qn (framepos_t pos, framecnt_t distance) const
4209 {
4210         Glib::Threads::RWLock::ReaderLock lm (lock);
4211
4212         return Evoral::Beats (quarter_note_at_minute_locked (_metrics, minute_at_frame (pos + distance)) - quarter_note_at_minute_locked (_metrics, minute_at_frame (pos)));
4213 }
4214
4215 struct bbtcmp {
4216     bool operator() (const BBT_Time& a, const BBT_Time& b) {
4217             return a < b;
4218     }
4219 };
4220
4221 std::ostream&
4222 operator<< (std::ostream& o, const Meter& m) {
4223         return o << m.divisions_per_bar() << '/' << m.note_divisor();
4224 }
4225
4226 std::ostream&
4227 operator<< (std::ostream& o, const Tempo& t) {
4228         return o << t.beats_per_minute() << " 1/" << t.note_type() << "'s per minute";
4229 }
4230
4231 std::ostream&
4232 operator<< (std::ostream& o, const MetricSection& section) {
4233
4234         o << "MetricSection @ " << section.frame() << ' ';
4235
4236         const TempoSection* ts;
4237         const MeterSection* ms;
4238
4239         if ((ts = dynamic_cast<const TempoSection*> (&section)) != 0) {
4240                 o << *((const Tempo*) ts);
4241         } else if ((ms = dynamic_cast<const MeterSection*> (&section)) != 0) {
4242                 o << *((const Meter*) ms);
4243         }
4244
4245         return o;
4246 }