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