libs/ardour/tempo.cc

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