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