libs/evoral/src/ControlList.cpp

   1 /* This file is part of Evoral.
   2  * Copyright (C) 2008 David Robillard <http://drobilla.net>
   3  * Copyright (C) 2000-2008 Paul Davis
   4  *
   5  * Evoral is free software; you can redistribute it and/or modify it under the
   6  * terms of the GNU General Public License as published by the Free Software
   7  * Foundation; either version 2 of the License, or (at your option) any later
   8  * version.
   9  *
  10  * Evoral is distributed in the hope that it will be useful, but WITHOUT ANY
  11  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  12  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17  */
  18
  19 #include <cmath>
  20
  21 #ifdef COMPILER_MSVC
  22 #include <float.h>
  23
  24 // 'std::isnan()' is not available in MSVC.
  25 #define isnan_local(val) (bool)_isnan((double)val)
  26 #else
  27 #define isnan_local std::isnan
  28 #endif
  29
  30 #include <cassert>
  31 #include <cmath>
  32 #include <iostream>
  33 #include <utility>
  34
  35 #include "evoral/ControlList.hpp"
  36 #include "evoral/Curve.hpp"
  37 #include "evoral/ParameterDescriptor.hpp"
  38 #include "evoral/TypeMap.hpp"
  39 #include "evoral/types.hpp"
  40
  41 #include "pbd/control_math.h"
  42 #include "pbd/compose.h"
  43 #include "pbd/debug.h"
  44
  45 using namespace std;
  46 using namespace PBD;
  47
  48 namespace Evoral {
  49
  50 inline bool event_time_less_than (ControlEvent* a, ControlEvent* b)
  51 {
  52         return a->when < b->when;
  53 }
  54
  55 ControlList::ControlList (const Parameter& id, const ParameterDescriptor& desc)
  56         : _parameter(id)
  57         , _desc(desc)
  58         , _interpolation (default_interpolation ())
  59         , _curve(0)
  60 {
  61         _frozen = 0;
  62         _changed_when_thawed = false;
  63         _lookup_cache.left = -1;
  64         _lookup_cache.range.first = _events.end();
  65         _lookup_cache.range.second = _events.end();
  66         _search_cache.left = -1;
  67         _search_cache.first = _events.end();
  68         _sort_pending = false;
  69         new_write_pass = true;
  70         _in_write_pass = false;
  71         did_write_during_pass = false;
  72         insert_position = -1;
  73         most_recent_insert_iterator = _events.end();
  74 }
  75
  76 ControlList::ControlList (const ControlList& other)
  77         : _parameter(other._parameter)
  78         , _desc(other._desc)
  79         , _interpolation(other._interpolation)
  80         , _curve(0)
  81 {
  82         _frozen = 0;
  83         _changed_when_thawed = false;
  84         _lookup_cache.range.first = _events.end();
  85         _lookup_cache.range.second = _events.end();
  86         _search_cache.first = _events.end();
  87         _sort_pending = false;
  88         new_write_pass = true;
  89         _in_write_pass = false;
  90         did_write_during_pass = false;
  91         insert_position = -1;
  92         most_recent_insert_iterator = _events.end();
  93
  94         // XXX copy_events() emits Dirty, but this is just assignment copy/construction
  95         copy_events (other);
  96 }
  97
  98 ControlList::ControlList (const ControlList& other, double start, double end)
  99         : _parameter(other._parameter)
 100         , _desc(other._desc)
 101         , _interpolation(other._interpolation)
 102         , _curve(0)
 103 {
 104         _frozen = 0;
 105         _changed_when_thawed = false;
 106         _lookup_cache.range.first = _events.end();
 107         _lookup_cache.range.second = _events.end();
 108         _search_cache.first = _events.end();
 109         _sort_pending = false;
 110
 111         /* now grab the relevant points, and shift them back if necessary */
 112
 113         boost::shared_ptr<ControlList> section = const_cast<ControlList*>(&other)->copy (start, end);
 114
 115         if (!section->empty()) {
 116                 // XXX copy_events() emits Dirty, but this is just assignment copy/construction
 117                 copy_events (*(section.get()));
 118         }
 119
 120         new_write_pass = false;
 121         _in_write_pass = false;
 122         did_write_during_pass = false;
 123         insert_position = -1;
 124         most_recent_insert_iterator = _events.end();
 125
 126         mark_dirty ();
 127 }
 128
 129 ControlList::~ControlList()
 130 {
 131         for (EventList::iterator x = _events.begin(); x != _events.end(); ++x) {
 132                 delete (*x);
 133         }
 134         _events.clear ();
 135
 136         delete _curve;
 137 }
 138
 139 boost::shared_ptr<ControlList>
 140 ControlList::create(const Parameter& id, const ParameterDescriptor& desc)
 141 {
 142         return boost::shared_ptr<ControlList>(new ControlList(id, desc));
 143 }
 144
 145 bool
 146 ControlList::operator== (const ControlList& other)
 147 {
 148         return _events == other._events;
 149 }
 150
 151 ControlList&
 152 ControlList::operator= (const ControlList& other)
 153 {
 154         if (this != &other) {
 155                 _frozen = 0;
 156                 _changed_when_thawed = false;
 157                 _sort_pending = false;
 158
 159                 insert_position = other.insert_position;
 160                 new_write_pass = true;
 161                 _in_write_pass = false;
 162                 did_write_during_pass = false;
 163                 insert_position = -1;
 164
 165                 _parameter = other._parameter;
 166                 _desc = other._desc;
 167                 _interpolation = other._interpolation;
 168
 169                 // XXX copy_events() emits Dirty, but this is just assignment copy/construction
 170                 copy_events (other);
 171         }
 172
 173         return *this;
 174 }
 175
 176 void
 177 ControlList::copy_events (const ControlList& other)
 178 {
 179         {
 180                 Glib::Threads::RWLock::WriterLock lm (_lock);
 181                 for (EventList::iterator x = _events.begin(); x != _events.end(); ++x) {
 182                         delete (*x);
 183                 }
 184                 _events.clear ();
 185                 Glib::Threads::RWLock::ReaderLock olm (other._lock);
 186                 for (const_iterator i = other.begin(); i != other.end(); ++i) {
 187                         _events.push_back (new ControlEvent ((*i)->when, (*i)->value));
 188                 }
 189                 unlocked_invalidate_insert_iterator ();
 190                 mark_dirty ();
 191         }
 192         maybe_signal_changed ();
 193 }
 194
 195 void
 196 ControlList::create_curve()
 197 {
 198         _curve = new Curve(*this);
 199 }
 200
 201 void
 202 ControlList::destroy_curve()
 203 {
 204         delete _curve;
 205         _curve = NULL;
 206 }
 207
 208 ControlList::InterpolationStyle
 209 ControlList::default_interpolation () const
 210 {
 211         if (_desc.toggled) {
 212                 return Discrete;
 213         } else if (_desc.logarithmic) {
 214                 return Logarithmic;
 215         }
 216         return Linear;
 217 }
 218
 219 void
 220 ControlList::maybe_signal_changed ()
 221 {
 222         mark_dirty ();
 223
 224         if (_frozen) {
 225                 _changed_when_thawed = true;
 226         }
 227 }
 228
 229 void
 230 ControlList::clear ()
 231 {
 232         {
 233                 Glib::Threads::RWLock::WriterLock lm (_lock);
 234                 for (EventList::iterator x = _events.begin(); x != _events.end(); ++x) {
 235                         delete (*x);
 236                 }
 237                 _events.clear ();
 238                 unlocked_invalidate_insert_iterator ();
 239                 mark_dirty ();
 240         }
 241
 242         maybe_signal_changed ();
 243 }
 244
 245 void
 246 ControlList::x_scale (double factor)
 247 {
 248         Glib::Threads::RWLock::WriterLock lm (_lock);
 249         _x_scale (factor);
 250 }
 251
 252 bool
 253 ControlList::extend_to (double when)
 254 {
 255         Glib::Threads::RWLock::WriterLock lm (_lock);
 256         if (_events.empty() || _events.back()->when == when) {
 257                 return false;
 258         }
 259         double factor = when / _events.back()->when;
 260         _x_scale (factor);
 261         return true;
 262 }
 263
 264 void
 265 ControlList::y_transform (boost::function<double(double)> callback)
 266 {
 267         {
 268                 Glib::Threads::RWLock::WriterLock lm (_lock);
 269                 for (iterator i = _events.begin(); i != _events.end(); ++i) {
 270                         (*i)->value = callback ((*i)->value);
 271                 }
 272                 mark_dirty ();
 273         }
 274         maybe_signal_changed ();
 275 }
 276
 277 void
 278 ControlList::list_merge (ControlList const& other, boost::function<double(double, double)> callback)
 279 {
 280         {
 281                 Glib::Threads::RWLock::WriterLock lm (_lock);
 282                 EventList nel;
 283                 /* First scale existing events, copy into a new list.
 284                  * The original list is needed later to interpolate
 285                  * for new events only present in the master list.
 286                  */
 287                 for (iterator i = _events.begin(); i != _events.end(); ++i) {
 288                         float val = callback ((*i)->value, other.eval ((*i)->when));
 289                         nel.push_back (new ControlEvent ((*i)->when , val));
 290                 }
 291                 /* Now add events which are only present in the master-list. */
 292                 const EventList& evl (other.events());
 293                 for (const_iterator i = evl.begin(); i != evl.end(); ++i) {
 294                         bool found = false;
 295                         // TODO: optimize, remember last matching iterator (lists are sorted)
 296                         for (iterator j = _events.begin(); j != _events.end(); ++j) {
 297                                 if ((*i)->when == (*j)->when) {
 298                                         found = true;
 299                                         break;
 300                                 }
 301                         }
 302                         /* skip events that have already been merge in the first pass */
 303                         if (found) {
 304                                 continue;
 305                         }
 306                         float val = callback (unlocked_eval ((*i)->when), (*i)->value);
 307                         nel.push_back (new ControlEvent ((*i)->when, val));
 308                 }
 309                 nel.sort (event_time_less_than);
 310
 311                 for (EventList::iterator x = _events.begin(); x != _events.end(); ++x) {
 312                         delete (*x);
 313                 }
 314                 _events.clear ();
 315                 _events = nel;
 316
 317                 unlocked_remove_duplicates ();
 318                 unlocked_invalidate_insert_iterator ();
 319                 mark_dirty ();
 320         }
 321         maybe_signal_changed ();
 322 }
 323
 324 void
 325 ControlList::_x_scale (double factor)
 326 {
 327         for (iterator i = _events.begin(); i != _events.end(); ++i) {
 328                 (*i)->when *= factor;
 329         }
 330
 331         mark_dirty ();
 332 }
 333
 334 struct ControlEventTimeComparator {
 335         bool operator() (ControlEvent* a, ControlEvent* b) {
 336                 return a->when < b->when;
 337         }
 338 };
 339
 340 void
 341 ControlList::thin (double thinning_factor)
 342 {
 343         if (thinning_factor == 0.0 || _desc.toggled) {
 344                 return;
 345         }
 346
 347         bool changed = false;
 348
 349         {
 350                 Glib::Threads::RWLock::WriterLock lm (_lock);
 351
 352                 ControlEvent* prevprev = 0;
 353                 ControlEvent* cur = 0;
 354                 ControlEvent* prev = 0;
 355                 iterator pprev;
 356                 int counter = 0;
 357
 358                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 thin from %2 events\n", this, _events.size()));
 359
 360                 for (iterator i = _events.begin(); i != _events.end(); ++i) {
 361
 362                         cur = *i;
 363                         counter++;
 364
 365                         if (counter > 2) {
 366
 367                                 /* compute the area of the triangle formed by 3 points
 368                                  */
 369
 370                                 double area = fabs ((prevprev->when * (prev->value - cur->value)) +
 371                                                     (prev->when * (cur->value - prevprev->value)) +
 372                                                     (cur->when * (prevprev->value - prev->value)));
 373
 374                                 if (area < thinning_factor) {
 375                                         iterator tmp = pprev;
 376
 377                                         /* pprev will change to current
 378                                            i is incremented to the next event
 379                                            as we loop.
 380                                         */
 381
 382                                         pprev = i;
 383                                         _events.erase (tmp);
 384                                         changed = true;
 385                                         continue;
 386                                 }
 387                         }
 388
 389                         prevprev = prev;
 390                         prev = cur;
 391                         pprev = i;
 392                 }
 393
 394                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 thin => %2 events\n", this, _events.size()));
 395
 396                 if (changed) {
 397                         unlocked_invalidate_insert_iterator ();
 398                         mark_dirty ();
 399                 }
 400         }
 401
 402         if (changed) {
 403                 maybe_signal_changed ();
 404         }
 405 }
 406
 407 void
 408 ControlList::fast_simple_add (double when, double value)
 409 {
 410         Glib::Threads::RWLock::WriterLock lm (_lock);
 411         /* to be used only for loading pre-sorted data from saved state */
 412         _events.insert (_events.end(), new ControlEvent (when, value));
 413
 414         mark_dirty ();
 415 }
 416
 417 void
 418 ControlList::invalidate_insert_iterator ()
 419 {
 420         Glib::Threads::RWLock::WriterLock lm (_lock);
 421         unlocked_invalidate_insert_iterator ();
 422 }
 423
 424 void
 425 ControlList::unlocked_invalidate_insert_iterator ()
 426 {
 427         most_recent_insert_iterator = _events.end();
 428 }
 429
 430 void
 431 ControlList::unlocked_remove_duplicates ()
 432 {
 433         if (_events.size() < 2) {
 434                 return;
 435         }
 436         iterator i = _events.begin();
 437         iterator prev = i++;
 438         while (i != _events.end()) {
 439                 if ((*prev)->when == (*i)->when && (*prev)->value == (*i)->value) {
 440                         i = _events.erase (i);
 441                 } else {
 442                         ++prev;
 443                         ++i;
 444                 }
 445         }
 446 }
 447
 448 void
 449 ControlList::start_write_pass (double when)
 450 {
 451         Glib::Threads::RWLock::WriterLock lm (_lock);
 452
 453         DEBUG_TRACE (DEBUG::ControlList, string_compose ("%1: setup write pass @ %2\n", this, when));
 454
 455         new_write_pass = true;
 456         did_write_during_pass = false;
 457         insert_position = when;
 458
 459         /* leave the insert iterator invalid, so that we will do the lookup
 460            of where it should be in a "lazy" way - deferring it until
 461            we actually add the first point (which may never happen).
 462         */
 463
 464         unlocked_invalidate_insert_iterator ();
 465 }
 466
 467 void
 468 ControlList::write_pass_finished (double /*when*/, double thinning_factor)
 469 {
 470         DEBUG_TRACE (DEBUG::ControlList, "write pass finished\n");
 471
 472         if (did_write_during_pass) {
 473                 thin (thinning_factor);
 474                 did_write_during_pass = false;
 475         }
 476         new_write_pass = true;
 477         _in_write_pass = false;
 478 }
 479
 480 void
 481 ControlList::set_in_write_pass (bool yn, bool add_point, double when)
 482 {
 483         DEBUG_TRACE (DEBUG::ControlList, string_compose ("now in write pass @ %1, add point ? %2\n", when, add_point));
 484
 485         _in_write_pass = yn;
 486
 487         if (yn && add_point) {
 488                 add_guard_point (when);
 489         }
 490 }
 491
 492 void
 493 ControlList::add_guard_point (double when)
 494 {
 495         ControlEvent cp (when, 0.0);
 496         most_recent_insert_iterator = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
 497
 498         double eval_value = unlocked_eval (insert_position);
 499
 500         if (most_recent_insert_iterator == _events.end()) {
 501
 502                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 insert iterator at end, adding eval-value there %2\n", this, eval_value));
 503                 _events.push_back (new ControlEvent (when, eval_value));
 504                 /* leave insert iterator at the end */
 505
 506         } else if ((*most_recent_insert_iterator)->when == when) {
 507
 508                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 insert iterator at existing point, setting eval-value there %2\n", this, eval_value));
 509
 510                 /* most_recent_insert_iterator points to a control event
 511                    already at the insert position, so there is
 512                    nothing to do.
 513
 514                    ... except ...
 515
 516                    advance most_recent_insert_iterator so that the "real"
 517                    insert occurs in the right place, since it
 518                    points to the control event just inserted.
 519                 */
 520
 521                 ++most_recent_insert_iterator;
 522         } else {
 523
 524                 /* insert a new control event at the right spot
 525                  */
 526
 527                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 insert eval-value %2 just before iterator @ %3\n",
 528                                                                  this, eval_value, (*most_recent_insert_iterator)->when));
 529
 530                 most_recent_insert_iterator = _events.insert (most_recent_insert_iterator, new ControlEvent (when, eval_value));
 531
 532                 /* advance most_recent_insert_iterator so that the "real"
 533                  * insert occurs in the right place, since it
 534                  * points to the control event just inserted.
 535                  */
 536
 537                 ++most_recent_insert_iterator;
 538         }
 539
 540         /* don't do this again till the next write pass */
 541
 542         new_write_pass = false;
 543 }
 544
 545 bool
 546 ControlList::in_write_pass () const
 547 {
 548         return _in_write_pass;
 549 }
 550
 551 bool
 552 ControlList::editor_add (double when, double value, bool with_guard)
 553 {
 554         /* this is for making changes from a graphical line editor
 555         */
 556
 557         ControlEvent cp (when, 0.0f);
 558         iterator i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
 559
 560         if (i != _events.end () && (*i)->when == when) {
 561                 return false;
 562         }
 563
 564         /* clamp new value to allowed range */
 565         value = std::min ((double)_desc.upper, std::max ((double)_desc.lower, value));
 566
 567         if (_events.empty()) {
 568
 569                 /* as long as the point we're adding is not at zero,
 570                  * add an "anchor" point there.
 571                  */
 572
 573                 if (when >= 1) {
 574                         _events.insert (_events.end(), new ControlEvent (0, value));
 575                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 added value %2 at zero\n", this, value));
 576                 }
 577         }
 578
 579         insert_position = when;
 580         if (with_guard) {
 581                 if (when > 64) {
 582                         add_guard_point (when - 64);
 583                 }
 584                 maybe_add_insert_guard (when);
 585         }
 586
 587         iterator result;
 588         DEBUG_TRACE (DEBUG::ControlList, string_compose ("editor_add: actually add when= %1 value= %2\n", when, value));
 589         result = _events.insert (i, new ControlEvent (when, value));
 590
 591         if (i == result) {
 592                 return false;
 593         }
 594
 595         mark_dirty ();
 596         maybe_signal_changed ();
 597
 598         return true;
 599 }
 600
 601 void
 602 ControlList::maybe_add_insert_guard (double when)
 603 {
 604         if (most_recent_insert_iterator != _events.end()) {
 605                 if ((*most_recent_insert_iterator)->when - when > 64) {
 606                         /* Next control point is some distance from where our new point is
 607                            going to go, so add a new point to avoid changing the shape of
 608                            the line too much.  The insert iterator needs to point to the
 609                            new control point so that our insert will happen correctly. */
 610                         most_recent_insert_iterator = _events.insert (
 611                                 most_recent_insert_iterator,
 612                                 new ControlEvent (when + 64, (*most_recent_insert_iterator)->value));
 613                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 added insert guard point @ %2 = %3\n",
 614                                                                          this, when + 64,
 615                                                                          (*most_recent_insert_iterator)->value));
 616                 }
 617         }
 618 }
 619
 620 /** If we would just be adding to a straight line, move the previous point instead. */
 621 bool
 622 ControlList::maybe_insert_straight_line (double when, double value)
 623 {
 624         if (_events.empty()) {
 625                 return false;
 626         }
 627
 628         if (_events.back()->value == value) {
 629                 // Point b at the final point, which we know exists
 630                 EventList::iterator b = _events.end();
 631                 --b;
 632                 if (b == _events.begin()) {
 633                         return false;  // No previous point
 634                 }
 635
 636                 // Check the previous point's value
 637                 --b;
 638                 if ((*b)->value == value) {
 639                         /* At least two points with the exact same value (straight
 640                            line), just move the final point to the new time. */
 641                         _events.back()->when = when;
 642                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("final value of %1 moved to %2\n", value, when));
 643                         return true;
 644                 }
 645         }
 646         return false;
 647 }
 648
 649 ControlList::iterator
 650 ControlList::erase_from_iterator_to (iterator iter, double when)
 651 {
 652         while (iter != _events.end()) {
 653                 if ((*iter)->when < when) {
 654                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 erase existing @ %2\n", this, (*iter)->when));
 655                         delete *iter;
 656                         iter = _events.erase (iter);
 657                         continue;
 658                 } else if ((*iter)->when >= when) {
 659                         break;
 660                 }
 661                 ++iter;
 662         }
 663         return iter;
 664 }
 665
 666 /* this is for making changes from some kind of user interface or
 667  * control surface (GUI, MIDI, OSC etc)
 668  */
 669 void
 670 ControlList::add (double when, double value, bool with_guards, bool with_initial)
 671 {
 672         /* clamp new value to allowed range */
 673         value = std::min ((double)_desc.upper, std::max ((double)_desc.lower, value));
 674
 675         DEBUG_TRACE (DEBUG::ControlList,
 676                      string_compose ("@%1 add %2 at %3 guards = %4 write pass = %5 (new? %6) at end? %7\n",
 677                                      this, value, when, with_guards, _in_write_pass, new_write_pass,
 678                                      (most_recent_insert_iterator == _events.end())));
 679         {
 680                 Glib::Threads::RWLock::WriterLock lm (_lock);
 681                 ControlEvent cp (when, 0.0f);
 682                 iterator insertion_point;
 683
 684                 if (_events.empty() && with_initial) {
 685
 686                         /* empty: add an "anchor" point if the point we're adding past time 0 */
 687
 688                         if (when >= 1) {
 689                                 if (_desc.toggled) {
 690                                         const double opp_val = ((value < 0.5) ? 1.0 : 0.0);
 691                                         _events.insert (_events.end(), new ControlEvent (0, opp_val));
 692                                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 added toggled value %2 at zero\n", this, opp_val));
 693
 694                                 } else {
 695                                         _events.insert (_events.end(), new ControlEvent (0, value));
 696                                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 added default value %2 at zero\n", this, _desc.normal));
 697                                 }
 698                         }
 699                 }
 700
 701                 if (_in_write_pass && new_write_pass) {
 702
 703                         /* first write in a write pass: add guard point if requested */
 704
 705                         if (with_guards) {
 706                                 add_guard_point (insert_position);
 707                                 did_write_during_pass = true;
 708                         } else {
 709                                 /* not adding a guard, but we need to set iterator appropriately */
 710                                 const ControlEvent cp (when, 0.0);
 711                                 most_recent_insert_iterator = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
 712                         }
 713                         new_write_pass = false;
 714
 715                 } else if (_in_write_pass &&
 716                            (most_recent_insert_iterator == _events.end() || when > (*most_recent_insert_iterator)->when)) {
 717
 718                         /* in write pass: erase from most recent insert to now */
 719
 720                         if (most_recent_insert_iterator != _events.end()) {
 721                                 /* advance to avoid deleting the last inserted point itself. */
 722                                 ++most_recent_insert_iterator;
 723                         }
 724
 725                         most_recent_insert_iterator = erase_from_iterator_to(most_recent_insert_iterator, when);
 726                         if (with_guards) {
 727                                 maybe_add_insert_guard (when);
 728                         }
 729
 730                 } else if (!_in_write_pass) {
 731
 732                         /* not in a write pass: figure out the iterator we should insert in front of */
 733
 734                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("compute(b) MRI for position %1\n", when));
 735                         ControlEvent cp (when, 0.0f);
 736                         most_recent_insert_iterator = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
 737                 }
 738
 739                 /* OK, now we're really ready to add a new point */
 740
 741                 if (most_recent_insert_iterator == _events.end()) {
 742                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 appending new point at end\n", this));
 743
 744                         const bool done = maybe_insert_straight_line (when, value);
 745                         if (!done) {
 746                                 _events.push_back (new ControlEvent (when, value));
 747                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("\tactually appended, size now %1\n", _events.size()));
 748                         }
 749
 750                         most_recent_insert_iterator = _events.end();
 751                         --most_recent_insert_iterator;
 752
 753                 } else if ((*most_recent_insert_iterator)->when == when) {
 754
 755                         if ((*most_recent_insert_iterator)->value != value) {
 756                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 reset existing point to new value %2\n", this, value));
 757
 758                                 /* only one point allowed per time point, so add a guard point
 759                                  * before it if needed then reset the value of the point.
 760                                  */
 761
 762                                 (*most_recent_insert_iterator)->value = value;
 763
 764                                 /* if we modified the final value, then its as
 765                                  * if we inserted a new point as far as the
 766                                  * next addition, so make sure we know that.
 767                                  */
 768
 769                                 if (_events.back()->when == when) {
 770                                         most_recent_insert_iterator = _events.end();
 771                                 }
 772
 773                         } else {
 774                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 same time %2, same value value %3\n", this, when, value));
 775                         }
 776
 777                 } else {
 778                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 insert new point at %2 at iterator at %3\n", this, when, (*most_recent_insert_iterator)->when));
 779                         bool done = false;
 780                         /* check for possible straight line here until maybe_insert_straight_line () handles the insert iterator properly*/
 781                         if (most_recent_insert_iterator != _events.begin ()) {
 782                                 bool have_point2 = false;
 783                                 --most_recent_insert_iterator;
 784                                 const bool have_point1 = (*most_recent_insert_iterator)->value == value;
 785
 786                                 if (most_recent_insert_iterator != _events.begin ()) {
 787                                         --most_recent_insert_iterator;
 788                                         have_point2 = (*most_recent_insert_iterator)->value == value;
 789                                         ++most_recent_insert_iterator;
 790                                 }
 791
 792                                 if (have_point1 && have_point2) {
 793                                         (*most_recent_insert_iterator)->when = when;
 794                                         done = true;
 795                                 } else {
 796                                         ++most_recent_insert_iterator;
 797                                 }
 798                         }
 799                         //done = maybe_insert_straight_line (when, value) || done;
 800                         /* if the transport is stopped, add guard points (?) */
 801                         if (!done && !_in_write_pass && when > 64) {
 802                                 add_guard_point (when - 64);
 803                                 maybe_add_insert_guard (when);
 804                         }
 805
 806                         if (with_guards) {
 807                                 maybe_add_insert_guard (when);
 808                         }
 809
 810                         if (!done) {
 811                                 EventList::iterator x = _events.insert (most_recent_insert_iterator, new ControlEvent (when, value));
 812                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 inserted new value before MRI, size now %2\n", this, _events.size()));
 813                                 most_recent_insert_iterator = x;
 814                         }
 815                 }
 816
 817                 mark_dirty ();
 818         }
 819
 820         maybe_signal_changed ();
 821 }
 822
 823 void
 824 ControlList::erase (iterator i)
 825 {
 826         {
 827                 Glib::Threads::RWLock::WriterLock lm (_lock);
 828                 if (most_recent_insert_iterator == i) {
 829                         unlocked_invalidate_insert_iterator ();
 830                 }
 831                 _events.erase (i);
 832                 mark_dirty ();
 833         }
 834         maybe_signal_changed ();
 835 }
 836
 837 void
 838 ControlList::erase (iterator start, iterator end)
 839 {
 840         {
 841                 Glib::Threads::RWLock::WriterLock lm (_lock);
 842                 _events.erase (start, end);
 843                 unlocked_invalidate_insert_iterator ();
 844                 mark_dirty ();
 845         }
 846         maybe_signal_changed ();
 847 }
 848
 849 /** Erase the first event which matches the given time and value */
 850 void
 851 ControlList::erase (double when, double value)
 852 {
 853         {
 854                 Glib::Threads::RWLock::WriterLock lm (_lock);
 855
 856                 iterator i = begin ();
 857                 while (i != end() && ((*i)->when != when || (*i)->value != value)) {
 858                         ++i;
 859                 }
 860
 861                 if (i != end ()) {
 862                         _events.erase (i);
 863                         if (most_recent_insert_iterator == i) {
 864                                 unlocked_invalidate_insert_iterator ();
 865                         }
 866                 }
 867
 868                 mark_dirty ();
 869         }
 870
 871         maybe_signal_changed ();
 872 }
 873
 874 void
 875 ControlList::erase_range (double start, double endt)
 876 {
 877         bool erased = false;
 878
 879         {
 880                 Glib::Threads::RWLock::WriterLock lm (_lock);
 881                 erased = erase_range_internal (start, endt, _events);
 882
 883                 if (erased) {
 884                         mark_dirty ();
 885                 }
 886
 887         }
 888
 889         if (erased) {
 890                 maybe_signal_changed ();
 891         }
 892 }
 893
 894 bool
 895 ControlList::erase_range_internal (double start, double endt, EventList & events)
 896 {
 897         bool erased = false;
 898         ControlEvent cp (start, 0.0f);
 899         iterator s;
 900         iterator e;
 901
 902         if ((s = lower_bound (events.begin(), events.end(), &cp, time_comparator)) != events.end()) {
 903                 cp.when = endt;
 904                 e = upper_bound (events.begin(), events.end(), &cp, time_comparator);
 905                 events.erase (s, e);
 906                 if (s != e) {
 907                         unlocked_invalidate_insert_iterator ();
 908                         erased = true;
 909                 }
 910         }
 911
 912         return erased;
 913 }
 914
 915 void
 916 ControlList::slide (iterator before, double distance)
 917 {
 918         {
 919                 Glib::Threads::RWLock::WriterLock lm (_lock);
 920
 921                 if (before == _events.end()) {
 922                         return;
 923                 }
 924
 925                 while (before != _events.end()) {
 926                         (*before)->when += distance;
 927                         ++before;
 928                 }
 929
 930                 mark_dirty ();
 931         }
 932
 933         maybe_signal_changed ();
 934 }
 935
 936 void
 937 ControlList::shift (double pos, double frames)
 938 {
 939         {
 940                 Glib::Threads::RWLock::WriterLock lm (_lock);
 941
 942                 for (iterator i = _events.begin(); i != _events.end(); ++i) {
 943                         if ((*i)->when >= pos) {
 944                                 (*i)->when += frames;
 945                         }
 946                 }
 947
 948                 mark_dirty ();
 949         }
 950
 951         maybe_signal_changed ();
 952 }
 953
 954 void
 955 ControlList::modify (iterator iter, double when, double val)
 956 {
 957         /* note: we assume higher level logic is in place to avoid this
 958          * reordering the time-order of control events in the list. ie. all
 959          * points after *iter are later than when.
 960          */
 961
 962         /* catch possible float/double rounding errors from higher levels */
 963         val = std::min ((double)_desc.upper, std::max ((double)_desc.lower, val));
 964
 965         {
 966                 Glib::Threads::RWLock::WriterLock lm (_lock);
 967
 968                 (*iter)->when = when;
 969                 (*iter)->value = val;
 970                 if (isnan_local (val)) {
 971                         abort ();
 972                 }
 973
 974                 if (!_frozen) {
 975                         _events.sort (event_time_less_than);
 976                         unlocked_remove_duplicates ();
 977                         unlocked_invalidate_insert_iterator ();
 978                 } else {
 979                         _sort_pending = true;
 980                 }
 981
 982                 mark_dirty ();
 983         }
 984
 985         maybe_signal_changed ();
 986 }
 987
 988 std::pair<ControlList::iterator,ControlList::iterator>
 989 ControlList::control_points_adjacent (double xval)
 990 {
 991         Glib::Threads::RWLock::ReaderLock lm (_lock);
 992         iterator i;
 993         ControlEvent cp (xval, 0.0f);
 994         std::pair<iterator,iterator> ret;
 995
 996         ret.first = _events.end();
 997         ret.second = _events.end();
 998
 999         for (i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator); i != _events.end(); ++i) {
1000
1001                 if (ret.first == _events.end()) {
1002                         if ((*i)->when >= xval) {
1003                                 if (i != _events.begin()) {
1004                                         ret.first = i;
1005                                         --ret.first;
1006                                 } else {
1007                                         return ret;
1008                                 }
1009                         }
1010                 }
1011
1012                 if ((*i)->when > xval) {
1013                         ret.second = i;
1014                         break;
1015                 }
1016         }
1017
1018         return ret;
1019 }
1020
1021 void
1022 ControlList::freeze ()
1023 {
1024         _frozen++;
1025 }
1026
1027 void
1028 ControlList::thaw ()
1029 {
1030         assert(_frozen > 0);
1031
1032         if (--_frozen > 0) {
1033                 return;
1034         }
1035
1036         {
1037                 Glib::Threads::RWLock::WriterLock lm (_lock);
1038
1039                 if (_sort_pending) {
1040                         _events.sort (event_time_less_than);
1041                         unlocked_remove_duplicates ();
1042                         unlocked_invalidate_insert_iterator ();
1043                         _sort_pending = false;
1044                 }
1045         }
1046 }
1047
1048 void
1049 ControlList::mark_dirty () const
1050 {
1051         _lookup_cache.left = -1;
1052         _lookup_cache.range.first = _events.end();
1053         _lookup_cache.range.second = _events.end();
1054         _search_cache.left = -1;
1055         _search_cache.first = _events.end();
1056
1057         if (_curve) {
1058                 _curve->mark_dirty();
1059         }
1060
1061         Dirty (); /* EMIT SIGNAL */
1062 }
1063
1064 void
1065 ControlList::truncate_end (double last_coordinate)
1066 {
1067         {
1068                 Glib::Threads::RWLock::WriterLock lm (_lock);
1069                 ControlEvent cp (last_coordinate, 0);
1070                 ControlList::reverse_iterator i;
1071                 double last_val;
1072
1073                 if (_events.empty()) {
1074                         return;
1075                 }
1076
1077                 if (last_coordinate == _events.back()->when) {
1078                         return;
1079                 }
1080
1081                 if (last_coordinate > _events.back()->when) {
1082
1083                         /* extending end:
1084                          */
1085
1086                         iterator foo = _events.begin();
1087                         bool lessthantwo;
1088
1089                         if (foo == _events.end()) {
1090                                 lessthantwo = true;
1091                         } else if (++foo == _events.end()) {
1092                                 lessthantwo = true;
1093                         } else {
1094                                 lessthantwo = false;
1095                         }
1096
1097                         if (lessthantwo) {
1098                                 /* less than 2 points: add a new point */
1099                                 _events.push_back (new ControlEvent (last_coordinate, _events.back()->value));
1100                         } else {
1101
1102                                 /* more than 2 points: check to see if the last 2 values
1103                                    are equal. if so, just move the position of the
1104                                    last point. otherwise, add a new point.
1105                                 */
1106
1107                                 iterator penultimate = _events.end();
1108                                 --penultimate; /* points at last point */
1109                                 --penultimate; /* points at the penultimate point */
1110
1111                                 if (_events.back()->value == (*penultimate)->value) {
1112                                         _events.back()->when = last_coordinate;
1113                                 } else {
1114                                         _events.push_back (new ControlEvent (last_coordinate, _events.back()->value));
1115                                 }
1116                         }
1117
1118                 } else {
1119
1120                         /* shortening end */
1121
1122                         last_val = unlocked_eval (last_coordinate);
1123                         last_val = max ((double) _desc.lower, last_val);
1124                         last_val = min ((double) _desc.upper, last_val);
1125
1126                         i = _events.rbegin();
1127
1128                         /* make i point to the last control point */
1129
1130                         ++i;
1131
1132                         /* now go backwards, removing control points that are
1133                            beyond the new last coordinate.
1134                         */
1135
1136                         // FIXME: SLOW! (size() == O(n))
1137
1138                         uint32_t sz = _events.size();
1139
1140                         while (i != _events.rend() && sz > 2) {
1141                                 ControlList::reverse_iterator tmp;
1142
1143                                 tmp = i;
1144                                 ++tmp;
1145
1146                                 if ((*i)->when < last_coordinate) {
1147                                         break;
1148                                 }
1149
1150                                 _events.erase (i.base());
1151                                 --sz;
1152
1153                                 i = tmp;
1154                         }
1155
1156                         _events.back()->when = last_coordinate;
1157                         _events.back()->value = last_val;
1158                 }
1159
1160                 unlocked_invalidate_insert_iterator ();
1161                 mark_dirty();
1162         }
1163
1164         maybe_signal_changed ();
1165 }
1166
1167 void
1168 ControlList::truncate_start (double overall_length)
1169 {
1170         {
1171                 Glib::Threads::RWLock::WriterLock lm (_lock);
1172                 iterator i;
1173                 double first_legal_value;
1174                 double first_legal_coordinate;
1175
1176                 if (_events.empty()) {
1177                         /* nothing to truncate */
1178                         return;
1179                 } else if (overall_length == _events.back()->when) {
1180                         /* no change in overall length */
1181                         return;
1182                 }
1183
1184                 if (overall_length > _events.back()->when) {
1185
1186                         /* growing at front: duplicate first point. shift all others */
1187
1188                         double shift = overall_length - _events.back()->when;
1189                         uint32_t np;
1190
1191                         for (np = 0, i = _events.begin(); i != _events.end(); ++i, ++np) {
1192                                 (*i)->when += shift;
1193                         }
1194
1195                         if (np < 2) {
1196
1197                                 /* less than 2 points: add a new point */
1198                                 _events.push_front (new ControlEvent (0, _events.front()->value));
1199
1200                         } else {
1201
1202                                 /* more than 2 points: check to see if the first 2 values
1203                                    are equal. if so, just move the position of the
1204                                    first point. otherwise, add a new point.
1205                                 */
1206
1207                                 iterator second = _events.begin();
1208                                 ++second; /* points at the second point */
1209
1210                                 if (_events.front()->value == (*second)->value) {
1211                                         /* first segment is flat, just move start point back to zero */
1212                                         _events.front()->when = 0;
1213                                 } else {
1214                                         /* leave non-flat segment in place, add a new leading point. */
1215                                         _events.push_front (new ControlEvent (0, _events.front()->value));
1216                                 }
1217                         }
1218
1219                 } else {
1220
1221                         /* shrinking at front */
1222
1223                         first_legal_coordinate = _events.back()->when - overall_length;
1224                         first_legal_value = unlocked_eval (first_legal_coordinate);
1225                         first_legal_value = max ((double)_desc.lower, first_legal_value);
1226                         first_legal_value = min ((double)_desc.upper, first_legal_value);
1227
1228                         /* remove all events earlier than the new "front" */
1229
1230                         i = _events.begin();
1231
1232                         while (i != _events.end() && !_events.empty()) {
1233                                 ControlList::iterator tmp;
1234
1235                                 tmp = i;
1236                                 ++tmp;
1237
1238                                 if ((*i)->when > first_legal_coordinate) {
1239                                         break;
1240                                 }
1241
1242                                 _events.erase (i);
1243
1244                                 i = tmp;
1245                         }
1246
1247
1248                         /* shift all remaining points left to keep their same
1249                            relative position
1250                         */
1251
1252                         for (i = _events.begin(); i != _events.end(); ++i) {
1253                                 (*i)->when -= first_legal_coordinate;
1254                         }
1255
1256                         /* add a new point for the interpolated new value */
1257
1258                         _events.push_front (new ControlEvent (0, first_legal_value));
1259                 }
1260
1261                 unlocked_invalidate_insert_iterator ();
1262                 mark_dirty();
1263         }
1264
1265         maybe_signal_changed ();
1266 }
1267
1268 double
1269 ControlList::unlocked_eval (double x) const
1270 {
1271         pair<EventList::iterator,EventList::iterator> range;
1272         int32_t npoints;
1273         double lpos, upos;
1274         double lval, uval;
1275         double fraction;
1276
1277         const_iterator length_check_iter = _events.begin();
1278         for (npoints = 0; npoints < 4; ++npoints, ++length_check_iter) {
1279                 if (length_check_iter == _events.end()) {
1280                         break;
1281                 }
1282         }
1283
1284         switch (npoints) {
1285         case 0:
1286                 return _desc.normal;
1287
1288         case 1:
1289                 return _events.front()->value;
1290
1291         case 2:
1292                 if (x >= _events.back()->when) {
1293                         return _events.back()->value;
1294                 } else if (x <= _events.front()->when) {
1295                         return _events.front()->value;
1296                 }
1297
1298                 lpos = _events.front()->when;
1299                 lval = _events.front()->value;
1300                 upos = _events.back()->when;
1301                 uval = _events.back()->value;
1302
1303                 fraction = (double) (x - lpos) / (double) (upos - lpos);
1304
1305                 switch (_interpolation) {
1306                         case Discrete:
1307                                 return lval;
1308                         case Logarithmic:
1309                                 return interpolate_logarithmic (lval, uval, fraction, _desc.lower, _desc.upper);
1310                         case Exponential:
1311                                 return interpolate_gain (lval, uval, fraction, _desc.upper);
1312                         case Curved:
1313                                 /* only used x-fade curves, never direct eval */
1314                                 assert (0);
1315                         default: // Linear
1316                                 return interpolate_linear (lval, uval, fraction);
1317                 }
1318
1319         default:
1320                 if (x >= _events.back()->when) {
1321                         return _events.back()->value;
1322                 } else if (x <= _events.front()->when) {
1323                         return _events.front()->value;
1324                 }
1325
1326                 return multipoint_eval (x);
1327         }
1328
1329         abort(); /*NOTREACHED*/ /* stupid gcc */
1330         return _desc.normal;
1331 }
1332
1333 double
1334 ControlList::multipoint_eval (double x) const
1335 {
1336         double upos, lpos;
1337         double uval, lval;
1338         double fraction;
1339
1340         /* "Stepped" lookup (no interpolation) */
1341         /* FIXME: no cache.  significant? */
1342         if (_interpolation == Discrete) {
1343                 const ControlEvent cp (x, 0);
1344                 EventList::const_iterator i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
1345
1346                 // shouldn't have made it to multipoint_eval
1347                 assert(i != _events.end());
1348
1349                 if (i == _events.begin() || (*i)->when == x)
1350                         return (*i)->value;
1351                 else
1352                         return (*(--i))->value;
1353         }
1354
1355         /* Only do the range lookup if x is in a different range than last time
1356          * this was called (or if the lookup cache has been marked "dirty" (left<0) */
1357         if ((_lookup_cache.left < 0) ||
1358             ((_lookup_cache.left > x) ||
1359              (_lookup_cache.range.first == _events.end()) ||
1360              ((*_lookup_cache.range.second)->when < x))) {
1361
1362                 const ControlEvent cp (x, 0);
1363
1364                 _lookup_cache.range = equal_range (_events.begin(), _events.end(), &cp, time_comparator);
1365         }
1366
1367         pair<const_iterator,const_iterator> range = _lookup_cache.range;
1368
1369         if (range.first == range.second) {
1370
1371                 /* x does not exist within the list as a control point */
1372
1373                 _lookup_cache.left = x;
1374
1375                 if (range.first != _events.begin()) {
1376                         --range.first;
1377                         lpos = (*range.first)->when;
1378                         lval = (*range.first)->value;
1379                 }  else {
1380                         /* we're before the first point */
1381                         // return _default_value;
1382                         return _events.front()->value;
1383                 }
1384
1385                 if (range.second == _events.end()) {
1386                         /* we're after the last point */
1387                         return _events.back()->value;
1388                 }
1389
1390                 upos = (*range.second)->when;
1391                 uval = (*range.second)->value;
1392
1393                 fraction = (double) (x - lpos) / (double) (upos - lpos);
1394
1395                 switch (_interpolation) {
1396                         case Logarithmic:
1397                                 return interpolate_logarithmic (lval, uval, fraction, _desc.lower, _desc.upper);
1398                         case Exponential:
1399                                 return interpolate_gain (lval, uval, fraction, _desc.upper);
1400                         case Discrete:
1401                                 /* should not reach here */
1402                                 assert (0);
1403                         case Curved:
1404                                 /* only used x-fade curves, never direct eval */
1405                                 assert (0);
1406                         default: // Linear
1407                                 return interpolate_linear (lval, uval, fraction);
1408                                 break;
1409                 }
1410                 assert (0);
1411         }
1412
1413         /* x is a control point in the data */
1414         _lookup_cache.left = -1;
1415         return (*range.first)->value;
1416 }
1417
1418 void
1419 ControlList::build_search_cache_if_necessary (double start) const
1420 {
1421         if (_events.empty()) {
1422                 /* Empty, nothing to cache, move to end. */
1423                 _search_cache.first = _events.end();
1424                 _search_cache.left = 0;
1425                 return;
1426         } else if ((_search_cache.left < 0) || (_search_cache.left > start)) {
1427                 /* Marked dirty (left < 0), or we're too far forward, re-search. */
1428
1429                 const ControlEvent start_point (start, 0);
1430
1431                 _search_cache.first = lower_bound (_events.begin(), _events.end(), &start_point, time_comparator);
1432                 _search_cache.left = start;
1433         }
1434
1435         /* We now have a search cache that is not too far right, but it may be too
1436            far left and need to be advanced. */
1437
1438         while (_search_cache.first != end() && (*_search_cache.first)->when < start) {
1439                 ++_search_cache.first;
1440         }
1441         _search_cache.left = start;
1442 }
1443
1444 /** Get the earliest event after \a start using the current interpolation style.
1445  *
1446  * If an event is found, \a x and \a y are set to its coordinates.
1447  *
1448  * \param inclusive Include events with timestamp exactly equal to \a start
1449  * \return true if event is found (and \a x and \a y are valid).
1450  */
1451 bool
1452 ControlList::rt_safe_earliest_event (double start, double& x, double& y, bool inclusive) const
1453 {
1454         // FIXME: It would be nice if this was unnecessary..
1455         Glib::Threads::RWLock::ReaderLock lm(_lock, Glib::Threads::TRY_LOCK);
1456         if (!lm.locked()) {
1457                 return false;
1458         }
1459
1460         return rt_safe_earliest_event_unlocked (start, x, y, inclusive);
1461 }
1462
1463
1464 /** Get the earliest event after \a start using the current interpolation style.
1465  *
1466  * If an event is found, \a x and \a y are set to its coordinates.
1467  *
1468  * \param inclusive Include events with timestamp exactly equal to \a start
1469  * \return true if event is found (and \a x and \a y are valid).
1470  */
1471 bool
1472 ControlList::rt_safe_earliest_event_unlocked (double start, double& x, double& y, bool inclusive) const
1473 {
1474         if (_interpolation == Discrete) {
1475                 return rt_safe_earliest_event_discrete_unlocked(start, x, y, inclusive);
1476         } else {
1477                 return rt_safe_earliest_event_linear_unlocked(start, x, y, inclusive);
1478         }
1479 }
1480
1481
1482 /** Get the earliest event after \a start without interpolation.
1483  *
1484  * If an event is found, \a x and \a y are set to its coordinates.
1485  *
1486  * \param inclusive Include events with timestamp exactly equal to \a start
1487  * \return true if event is found (and \a x and \a y are valid).
1488  */
1489 bool
1490 ControlList::rt_safe_earliest_event_discrete_unlocked (double start, double& x, double& y, bool inclusive) const
1491 {
1492         build_search_cache_if_necessary (start);
1493
1494         if (_search_cache.first != _events.end()) {
1495                 const ControlEvent* const first = *_search_cache.first;
1496
1497                 const bool past_start = (inclusive ? first->when >= start : first->when > start);
1498
1499                 /* Earliest points is in range, return it */
1500                 if (past_start) {
1501
1502                         x = first->when;
1503                         y = first->value;
1504
1505                         /* Move left of cache to this point
1506                          * (Optimize for immediate call this cycle within range) */
1507                         _search_cache.left = x;
1508                         ++_search_cache.first;
1509
1510                         assert(x >= start);
1511                         return true;
1512
1513                 } else {
1514                         return false;
1515                 }
1516
1517                 /* No points in range */
1518         } else {
1519                 return false;
1520         }
1521 }
1522
1523 /** Get the earliest time the line crosses an integer (Linear interpolation).
1524  *
1525  * If an event is found, \a x and \a y are set to its coordinates.
1526  *
1527  * \param inclusive Include events with timestamp exactly equal to \a start
1528  * \return true if event is found (and \a x and \a y are valid).
1529  */
1530 bool
1531 ControlList::rt_safe_earliest_event_linear_unlocked (double start, double& x, double& y, bool inclusive) const
1532 {
1533         // cout << "earliest_event(start: " << start << ", x: " << x << ", y: " << y << ", inclusive: " << inclusive <<  ")" << endl;
1534
1535         const_iterator length_check_iter = _events.begin();
1536         if (_events.empty()) { // 0 events
1537                 return false;
1538         } else if (_events.end() == ++length_check_iter) { // 1 event
1539                 return rt_safe_earliest_event_discrete_unlocked (start, x, y, inclusive);
1540         }
1541
1542         // Hack to avoid infinitely repeating the same event
1543         build_search_cache_if_necessary (start);
1544
1545         if (_search_cache.first != _events.end()) {
1546
1547                 const ControlEvent* first = NULL;
1548                 const ControlEvent* next = NULL;
1549
1550                 if (_search_cache.first == _events.begin() || (*_search_cache.first)->when <= start) {
1551                         /* Step is after first */
1552                         first = *_search_cache.first;
1553                         ++_search_cache.first;
1554                         if (_search_cache.first == _events.end()) {
1555                                 return false;
1556                         }
1557                         next = *_search_cache.first;
1558
1559                 } else {
1560                         /* Step is before first */
1561                         const_iterator prev = _search_cache.first;
1562                         --prev;
1563                         first = *prev;
1564                         next = *_search_cache.first;
1565                 }
1566
1567                 if (inclusive && first->when == start) {
1568                         x = first->when;
1569                         y = first->value;
1570                         /* Move left of cache to this point
1571                          * (Optimize for immediate call this cycle within range) */
1572                         _search_cache.left = x;
1573                         return true;
1574                 } else if (next->when < start || (!inclusive && next->when == start)) {
1575                         /* "Next" is before the start, no points left. */
1576                         return false;
1577                 }
1578
1579                 if (fabs(first->value - next->value) <= 1) {
1580                         if (next->when > start) {
1581                                 x = next->when;
1582                                 y = next->value;
1583                                 /* Move left of cache to this point
1584                                  * (Optimize for immediate call this cycle within range) */
1585                                 _search_cache.left = x;
1586                                 return true;
1587                         } else {
1588                                 return false;
1589                         }
1590                 }
1591
1592                 const double slope = (next->value - first->value) / (double)(next->when - first->when);
1593                 //cerr << "start y: " << start_y << endl;
1594
1595                 //y = first->value + (slope * fabs(start - first->when));
1596                 y = first->value;
1597
1598                 if (first->value < next->value) // ramping up
1599                         y = ceil(y);
1600                 else // ramping down
1601                         y = floor(y);
1602
1603                 x = first->when + (y - first->value) / (double)slope;
1604
1605                 while ((inclusive && x < start) || (x <= start && y != next->value)) {
1606
1607                         if (first->value < next->value) // ramping up
1608                                 y += 1.0;
1609                         else // ramping down
1610                                 y -= 1.0;
1611
1612                         x = first->when + (y - first->value) / (double)slope;
1613                 }
1614
1615                 /*cerr << first->value << " @ " << first->when << " ... "
1616                   << next->value << " @ " << next->when
1617                   << " = " << y << " @ " << x << endl;*/
1618
1619                 assert(    (y >= first->value && y <= next->value)
1620                            || (y <= first->value && y >= next->value) );
1621
1622
1623                 const bool past_start = (inclusive ? x >= start : x > start);
1624                 if (past_start) {
1625                         /* Move left of cache to this point
1626                          * (Optimize for immediate call this cycle within range) */
1627                         _search_cache.left = x;
1628                         assert(inclusive ? x >= start : x > start);
1629                         return true;
1630                 } else {
1631                         if (inclusive) {
1632                                 x = next->when;
1633                         } else {
1634                                 x = start;
1635                         }
1636                         _search_cache.left = x;
1637                         return true;
1638                 }
1639
1640         } else {
1641                 /* No points in the future, so no steps (towards them) in the future */
1642                 return false;
1643         }
1644 }
1645
1646
1647 /** @param start Start position in model coordinates.
1648  *  @param end End position in model coordinates.
1649  *  @param op 0 = cut, 1 = copy, 2 = clear.
1650  */
1651 boost::shared_ptr<ControlList>
1652 ControlList::cut_copy_clear (double start, double end, int op)
1653 {
1654         boost::shared_ptr<ControlList> nal = create (_parameter, _desc);
1655         iterator s, e;
1656         ControlEvent cp (start, 0.0);
1657
1658         {
1659                 Glib::Threads::RWLock::WriterLock lm (_lock);
1660
1661                 /* first, determine s & e, two iterators that define the range of points
1662                    affected by this operation
1663                 */
1664
1665                 if ((s = lower_bound (_events.begin(), _events.end(), &cp, time_comparator)) == _events.end()) {
1666                         return nal;
1667                 }
1668
1669                 /* and the last that is at or after `end' */
1670                 cp.when = end;
1671                 e = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
1672
1673
1674                 /* if "start" isn't the location of an existing point,
1675                    evaluate the curve to get a value for the start. Add a point to
1676                    both the existing event list, and if its not a "clear" operation,
1677                    to the copy ("nal") as well.
1678
1679                    Note that the time positions of the points in each list are different
1680                    because we want the copy ("nal") to have a zero time reference.
1681                 */
1682
1683
1684                 /* before we begin any cut/clear operations, get the value of the curve
1685                    at "end".
1686                 */
1687
1688                 double end_value = unlocked_eval (end);
1689
1690                 if ((*s)->when != start) {
1691
1692                         double val = unlocked_eval (start);
1693
1694                         if (op == 0) { // cut
1695                                 if (start > _events.front()->when) {
1696                                         _events.insert (s, (new ControlEvent (start, val)));
1697                                 }
1698                         }
1699
1700                         if (op != 2) { // ! clear
1701                                 nal->_events.push_back (new ControlEvent (0, val));
1702                         }
1703                 }
1704
1705                 for (iterator x = s; x != e; ) {
1706
1707                         /* adjust new points to be relative to start, which
1708                            has been set to zero.
1709                         */
1710
1711                         if (op != 2) {
1712                                 nal->_events.push_back (new ControlEvent ((*x)->when - start, (*x)->value));
1713                         }
1714
1715                         if (op != 1) {
1716                                 x = _events.erase (x);
1717                         } else {
1718                                 ++x;
1719                         }
1720                 }
1721
1722                 if (e == _events.end() || (*e)->when != end) {
1723
1724                         /* only add a boundary point if there is a point after "end"
1725                          */
1726
1727                         if (op == 0 && (e != _events.end() && end < (*e)->when)) { // cut
1728                                 _events.insert (e, new ControlEvent (end, end_value));
1729                         }
1730
1731                         if (op != 2 && (e != _events.end() && end < (*e)->when)) { // cut/copy
1732                                 nal->_events.push_back (new ControlEvent (end - start, end_value));
1733                         }
1734                 }
1735
1736                 unlocked_invalidate_insert_iterator ();
1737                 mark_dirty ();
1738         }
1739
1740         if (op != 1) {
1741                 maybe_signal_changed ();
1742         }
1743
1744         return nal;
1745 }
1746
1747
1748 boost::shared_ptr<ControlList>
1749 ControlList::cut (double start, double end)
1750 {
1751         return cut_copy_clear (start, end, 0);
1752 }
1753
1754 boost::shared_ptr<ControlList>
1755 ControlList::copy (double start, double end)
1756 {
1757         return cut_copy_clear (start, end, 1);
1758 }
1759
1760 void
1761 ControlList::clear (double start, double end)
1762 {
1763         cut_copy_clear (start, end, 2);
1764 }
1765
1766 /** @param pos Position in model coordinates */
1767 bool
1768 ControlList::paste (const ControlList& alist, double pos)
1769 {
1770         if (alist._events.empty()) {
1771                 return false;
1772         }
1773
1774         {
1775                 Glib::Threads::RWLock::WriterLock lm (_lock);
1776                 iterator where;
1777                 iterator prev;
1778                 double end = 0;
1779                 ControlEvent cp (pos, 0.0);
1780
1781                 where = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
1782
1783                 for (const_iterator i = alist.begin();i != alist.end(); ++i) {
1784                         double value = (*i)->value;
1785                         if (alist.parameter() != parameter()) {
1786                                 const ParameterDescriptor& src_desc = alist.descriptor();
1787
1788                                 // This does not work for logscale and will probably also not do
1789                                 // the right thing for integer_step and sr_dependent parameters.
1790                                 //
1791                                 // TODO various flags from from ARDOUR::ParameterDescriptor
1792                                 // to Evoral::ParameterDescriptor
1793
1794                                 value -= src_desc.lower;  // translate to 0-relative
1795                                 value /= (src_desc.upper - src_desc.lower);  // normalize range
1796                                 value *= (_desc.upper - _desc.lower);  // scale to our range
1797                                 value += _desc.lower;  // translate to our offset
1798                                 if (_desc.toggled) {
1799                                         value = (value < 0.5) ? 0.0 : 1.0;
1800                                 }
1801                                 /* catch possible rounding errors */
1802                                 value = std::min ((double)_desc.upper, std::max ((double)_desc.lower, value));
1803                         }
1804                         _events.insert (where, new ControlEvent((*i)->when + pos, value));
1805                         end = (*i)->when + pos;
1806                 }
1807
1808
1809                 /* move all  points after the insertion along the timeline by
1810                    the correct amount.
1811                 */
1812
1813                 while (where != _events.end()) {
1814                         iterator tmp;
1815                         if ((*where)->when <= end) {
1816                                 tmp = where;
1817                                 ++tmp;
1818                                 _events.erase(where);
1819                                 where = tmp;
1820
1821                         } else {
1822                                 break;
1823                         }
1824                 }
1825
1826                 unlocked_invalidate_insert_iterator ();
1827                 mark_dirty ();
1828         }
1829
1830         maybe_signal_changed ();
1831         return true;
1832 }
1833
1834 /** Move automation around according to a list of region movements.
1835  *  @param return true if anything was changed, otherwise false (ie nothing needed changing)
1836  */
1837 bool
1838 ControlList::move_ranges (const list< RangeMove<double> >& movements)
1839 {
1840         typedef list< RangeMove<double> > RangeMoveList;
1841
1842         {
1843                 Glib::Threads::RWLock::WriterLock lm (_lock);
1844
1845                 /* a copy of the events list before we started moving stuff around */
1846                 EventList old_events = _events;
1847
1848                 /* clear the source and destination ranges in the new list */
1849                 bool things_erased = false;
1850                 for (RangeMoveList::const_iterator i = movements.begin (); i != movements.end (); ++i) {
1851
1852                         if (erase_range_internal (i->from, i->from + i->length, _events)) {
1853                                 things_erased = true;
1854                         }
1855
1856                         if (erase_range_internal (i->to, i->to + i->length, _events)) {
1857                                 things_erased = true;
1858                         }
1859                 }
1860
1861                 /* if nothing was erased, there is nothing to do */
1862                 if (!things_erased) {
1863                         return false;
1864                 }
1865
1866                 /* copy the events into the new list */
1867                 for (RangeMoveList::const_iterator i = movements.begin (); i != movements.end (); ++i) {
1868                         iterator j = old_events.begin ();
1869                         const double limit = i->from + i->length;
1870                         const double dx    = i->to - i->from;
1871                         while (j != old_events.end () && (*j)->when <= limit) {
1872                                 if ((*j)->when >= i->from) {
1873                                         ControlEvent* ev = new ControlEvent (**j);
1874                                         ev->when += dx;
1875                                         _events.push_back (ev);
1876                                 }
1877                                 ++j;
1878                         }
1879                 }
1880
1881                 if (!_frozen) {
1882                         _events.sort (event_time_less_than);
1883                         unlocked_remove_duplicates ();
1884                         unlocked_invalidate_insert_iterator ();
1885                 } else {
1886                         _sort_pending = true;
1887                 }
1888
1889                 mark_dirty ();
1890         }
1891
1892         maybe_signal_changed ();
1893         return true;
1894 }
1895
1896 bool
1897 ControlList::set_interpolation (InterpolationStyle s)
1898 {
1899         if (_interpolation == s) {
1900                 return true;
1901         }
1902
1903         switch (s) {
1904                 case Logarithmic:
1905                         if (_desc.lower * _desc.upper <= 0 || _desc.upper <= _desc.lower) {
1906                                 return false;
1907                         }
1908                         break;
1909                 case Exponential:
1910                         if (_desc.lower != 0 || _desc.upper <= _desc.lower) {
1911                                 return false;
1912                         }
1913                 default:
1914                         break;
1915         }
1916
1917         _interpolation = s;
1918         InterpolationChanged (s); /* EMIT SIGNAL */
1919         return true;
1920 }
1921
1922 bool
1923 ControlList::operator!= (ControlList const & other) const
1924 {
1925         if (_events.size() != other._events.size()) {
1926                 return true;
1927         }
1928
1929         EventList::const_iterator i = _events.begin ();
1930         EventList::const_iterator j = other._events.begin ();
1931
1932         while (i != _events.end() && (*i)->when == (*j)->when && (*i)->value == (*j)->value) {
1933                 ++i;
1934                 ++j;
1935         }
1936
1937         if (i != _events.end ()) {
1938                 return true;
1939         }
1940
1941         return (
1942                 _parameter != other._parameter ||
1943                 _interpolation != other._interpolation ||
1944                 _desc.lower != other._desc.lower ||
1945                 _desc.upper != other._desc.upper ||
1946                 _desc.normal != other._desc.normal
1947                 );
1948 }
1949
1950 void
1951 ControlList::dump (ostream& o)
1952 {
1953         /* NOT LOCKED ... for debugging only */
1954
1955         for (EventList::iterator x = _events.begin(); x != _events.end(); ++x) {
1956                 o << (*x)->value << " @ " << (uint64_t) (*x)->when << endl;
1957         }
1958 }
1959
1960 } // namespace Evoral
1961