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