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