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