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