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