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