libs/ardour/tempo.cc

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