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