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