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