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