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