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) {
 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::add (double when, double value, bool with_guards, bool with_default)
 486 {
 487         /* this is for making changes from some kind of user interface or
 488            control surface (GUI, MIDI, OSC etc)
 489         */
 490
 491         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 add %2 at %3 w/erase = %4 (new ? %6) at end ? %5\n",
 492                                                          this, value, when, _in_write_pass, (most_recent_insert_iterator == _events.end()), new_write_pass));
 493         {
 494                 Glib::Threads::Mutex::Lock lm (_lock);
 495                 ControlEvent cp (when, 0.0f);
 496                 iterator insertion_point;
 497
 498                 if (_events.empty() && with_default) {
 499
 500                         /* as long as the point we're adding is not at zero,
 501                          * add an "anchor" point there.
 502                          */
 503
 504                         if (when >= 1) {
 505                                 _events.insert (_events.end(), new ControlEvent (0, _default_value));
 506                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 added default value %2 at zero\n", this, _default_value));
 507                         }
 508                 }
 509
 510                 if (_in_write_pass && new_write_pass) {
 511
 512                         if (with_guards) {
 513                                 add_guard_point (insert_position);
 514                                 did_write_during_pass = true;
 515                         }
 516
 517                 } else if (most_recent_insert_iterator == _events.end() || when > (*most_recent_insert_iterator)->when) {
 518
 519                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 %2 erase from existing iterator (@end ? %3)\n",
 520                                                                          this, (_in_write_pass  ? "DO" : "DON'T"),
 521                                                                          (most_recent_insert_iterator == _events.end())));
 522
 523                         if (_in_write_pass) {
 524                                 while (most_recent_insert_iterator != _events.end()) {
 525                                         if ((*most_recent_insert_iterator)->when < when) {
 526                                                 if (_in_write_pass) {
 527                                                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 erase existing @ %2\n", this, (*most_recent_insert_iterator)));
 528                                                         delete *most_recent_insert_iterator;
 529                                                         most_recent_insert_iterator = _events.erase (most_recent_insert_iterator);
 530                                                         continue;
 531                                                 }
 532                                         } else if ((*most_recent_insert_iterator)->when >= when) {
 533                                                 break;
 534                                         }
 535                                         ++most_recent_insert_iterator;
 536                                 }
 537
 538                                 if (with_guards && most_recent_insert_iterator != _events.end()) {
 539                                         if ((*most_recent_insert_iterator)->when - when > 64) {
 540                                                 /* next control point is some
 541                                                  * distance from where our new
 542                                                  * point is going to go - add a
 543                                                  * new point to avoid changing
 544                                                  * the shape of the line too
 545                                                  * much. the insert iterator needs
 546                                                  * to point to the new control
 547                                                  * point so that our insert
 548                                                  * will happen correctly.
 549                                                  */
 550                                                 most_recent_insert_iterator = _events.insert (most_recent_insert_iterator,
 551                                                                                               new ControlEvent (when+1, (*most_recent_insert_iterator)->value));
 552                                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 added post-erase guard point @ %2 = %3\n",
 553                                                                                                  this, when+1,
 554                                                                                                  (*most_recent_insert_iterator)->value));
 555                                         }
 556                                 }
 557
 558                         } else {
 559
 560                                 /* not in a write pass: figure out the iterator we should insert in front of */
 561
 562                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("compute MRI for position %1\n", when));
 563                                 ControlEvent cp (when, 0.0f);
 564                                 most_recent_insert_iterator = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
 565                         }
 566
 567                 } else {
 568
 569                         /* not in a write pass, adding a point within existing
 570                          * data: figure out the iterator we should insert in
 571                          * front of
 572                          */
 573
 574                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("compute(b) MRI for position %1\n", when));
 575                         ControlEvent cp (when, 0.0f);
 576                         most_recent_insert_iterator = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
 577                 }
 578
 579                 /* OK, now we're really ready to add a new point
 580                  */
 581
 582                 if (most_recent_insert_iterator == _events.end()) {
 583                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 appending new point at end\n", this));
 584
 585                         bool done = false;
 586
 587                         /* check if would just be adding to a straight line,
 588                          * and don't add another point if so
 589                          */
 590
 591                         if (!_events.empty()) { // avoid O(N) _events.size() here
 592                                 if (_events.back()->value == value) {
 593                                         EventList::iterator b = _events.end();
 594                                         --b; // final point, which we know exists
 595                                         if (b != _events.begin()) { // step back again, but check first that it is legal
 596                                                 --b; // penultimate-point
 597                                                 if ((*b)->value == value) {
 598                                                         /* there are at least two points with the exact same value ...
 599                                                          * straight line - just move the final
 600                                                          * point to the new time
 601                                                          */
 602                                                         _events.back()->when = when;
 603                                                         done = true;
 604                                                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("final value of %1 moved to %2\n", value, when));
 605                                                 }
 606                                         }
 607                                 }
 608                         }
 609
 610                         if (!done) {
 611                                 _events.push_back (new ControlEvent (when, value));
 612                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("\tactually appended, size now %1\n", _events.size()));
 613                         }
 614
 615                         if (!_in_write_pass) {
 616                                 most_recent_insert_iterator = _events.end();
 617                                 --most_recent_insert_iterator;
 618                         }
 619
 620                 } else if ((*most_recent_insert_iterator)->when == when) {
 621
 622                         if ((*most_recent_insert_iterator)->value != value) {
 623                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 reset existing point to new value %2\n", this, value));
 624
 625                                 /* only one point allowed per time point, so just
 626                                  * reset the value here.
 627                                  */
 628
 629                                 (*most_recent_insert_iterator)->value = value;
 630
 631                                 /* if we modified the final value, then its as
 632                                  * if we inserted a new point as far as the
 633                                  * next addition, so make sure we know that.
 634                                  */
 635
 636                                 if (_in_write_pass && _events.back()->when == when) {
 637                                         most_recent_insert_iterator = _events.end();
 638                                 }
 639
 640                         } else {
 641                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 same time %2, same value value %3\n", this, when, value));
 642                         }
 643
 644                 } else {
 645                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 insert new point at %2 at iterator at %3\n", this, when, (*most_recent_insert_iterator)->when));
 646
 647                         bool done = false;
 648
 649                         /* check if would just be adding to a straight line,
 650                          * and don't add another point if so
 651                          */
 652
 653                         if (most_recent_insert_iterator != _events.begin()) {
 654                                 EventList::iterator b = most_recent_insert_iterator;
 655                                 --b; // prior point, which we know exists
 656                                 if ((*b)->value == value) { // same value as the point we plan to insert
 657                                         if (b != _events.begin()) { // step back again, which may not be possible
 658                                                 EventList::iterator bb = b;
 659                                                 --bb; // next-to-prior-point
 660                                                 if ((*bb)->value == value) {
 661                                                         /* straight line - just move the prior
 662                                                          * point to the new time
 663                                                          */
 664                                                         (*b)->when = when;
 665
 666                                                         if (!_in_write_pass) {
 667                                                                 most_recent_insert_iterator = b;
 668                                                         }
 669
 670                                                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("final value of %1 moved to %2\n", value, when));
 671                                                         done = true;
 672                                                 }
 673                                         }
 674                                 }
 675                         }
 676
 677                         if (with_guards && most_recent_insert_iterator != _events.end()) {
 678                                 if ((*most_recent_insert_iterator)->when - when > 64) {
 679                                         /* next control point is some
 680                                          * distance from where our new
 681                                          * point is going to go - add a
 682                                          * new point to avoid changing
 683                                          * the shape of the line too
 684                                          * much. the insert iterator needs
 685                                          * to point to the new control
 686                                          * point so that our insert
 687                                          * will happen correctly.
 688                                          */
 689                                         most_recent_insert_iterator = _events.insert (most_recent_insert_iterator,
 690                                                                                       new ControlEvent (when+1, (*most_recent_insert_iterator)->value));
 691                                         DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 added insert-post-erase guard point @ %2 = %3\n",
 692                                                                                          this, when+1,
 693                                                                                          (*most_recent_insert_iterator)->value));
 694                                 }
 695                         }
 696
 697                         if (!done) {
 698                                 EventList::iterator x = _events.insert (most_recent_insert_iterator, new ControlEvent (when, value));
 699                                 DEBUG_TRACE (DEBUG::ControlList, string_compose ("@%1 inserted new value before MRI, size now %2\n", this, _events.size()));
 700
 701                                 if (!_in_write_pass) {
 702                                         most_recent_insert_iterator = x;
 703                                 }
 704                         }
 705                 }
 706
 707                 mark_dirty ();
 708         }
 709
 710         maybe_signal_changed ();
 711 }
 712
 713 void
 714 ControlList::erase (iterator i)
 715 {
 716         {
 717                 Glib::Threads::Mutex::Lock lm (_lock);
 718                 if (most_recent_insert_iterator == i) {
 719                         unlocked_invalidate_insert_iterator ();
 720                 }
 721                 _events.erase (i);
 722                 mark_dirty ();
 723         }
 724         maybe_signal_changed ();
 725 }
 726
 727 void
 728 ControlList::erase (iterator start, iterator end)
 729 {
 730         {
 731                 Glib::Threads::Mutex::Lock lm (_lock);
 732                 _events.erase (start, end);
 733                 unlocked_invalidate_insert_iterator ();
 734                 mark_dirty ();
 735         }
 736         maybe_signal_changed ();
 737 }
 738
 739 /** Erase the first event which matches the given time and value */
 740 void
 741 ControlList::erase (double when, double value)
 742 {
 743         {
 744                 Glib::Threads::Mutex::Lock lm (_lock);
 745
 746                 iterator i = begin ();
 747                 while (i != end() && ((*i)->when != when || (*i)->value != value)) {
 748                         ++i;
 749                 }
 750
 751                 if (i != end ()) {
 752                         _events.erase (i);
 753                         if (most_recent_insert_iterator == i) {
 754                                 unlocked_invalidate_insert_iterator ();
 755                         }
 756                 }
 757
 758                 mark_dirty ();
 759         }
 760
 761         maybe_signal_changed ();
 762 }
 763
 764 void
 765 ControlList::erase_range (double start, double endt)
 766 {
 767         bool erased = false;
 768
 769         {
 770                 Glib::Threads::Mutex::Lock lm (_lock);
 771                 erased = erase_range_internal (start, endt, _events);
 772
 773                 if (erased) {
 774                         mark_dirty ();
 775                 }
 776
 777         }
 778
 779         if (erased) {
 780                 maybe_signal_changed ();
 781         }
 782 }
 783
 784 bool
 785 ControlList::erase_range_internal (double start, double endt, EventList & events)
 786 {
 787         bool erased = false;
 788         ControlEvent cp (start, 0.0f);
 789         iterator s;
 790         iterator e;
 791
 792         if ((s = lower_bound (events.begin(), events.end(), &cp, time_comparator)) != events.end()) {
 793                 cp.when = endt;
 794                 e = upper_bound (events.begin(), events.end(), &cp, time_comparator);
 795                 events.erase (s, e);
 796                 if (s != e) {
 797                         unlocked_invalidate_insert_iterator ();
 798                         erased = true;
 799                 }
 800         }
 801
 802         return erased;
 803 }
 804
 805 void
 806 ControlList::slide (iterator before, double distance)
 807 {
 808         {
 809                 Glib::Threads::Mutex::Lock lm (_lock);
 810
 811                 if (before == _events.end()) {
 812                         return;
 813                 }
 814
 815                 while (before != _events.end()) {
 816                         (*before)->when += distance;
 817                         ++before;
 818                 }
 819
 820                 mark_dirty ();
 821         }
 822
 823         maybe_signal_changed ();
 824 }
 825
 826 void
 827 ControlList::shift (double pos, double frames)
 828 {
 829         {
 830                 Glib::Threads::Mutex::Lock lm (_lock);
 831
 832                 for (iterator i = _events.begin(); i != _events.end(); ++i) {
 833                         if ((*i)->when >= pos) {
 834                                 (*i)->when += frames;
 835                         }
 836                 }
 837
 838                 mark_dirty ();
 839         }
 840
 841         maybe_signal_changed ();
 842 }
 843
 844 void
 845 ControlList::modify (iterator iter, double when, double val)
 846 {
 847         /* note: we assume higher level logic is in place to avoid this
 848            reordering the time-order of control events in the list. ie. all
 849            points after *iter are later than when.
 850         */
 851
 852         {
 853                 Glib::Threads::Mutex::Lock lm (_lock);
 854
 855                 (*iter)->when = when;
 856                 (*iter)->value = val;
 857                 if (isnan_local (val)) {
 858                         abort ();
 859                 }
 860
 861                 if (!_frozen) {
 862                         _events.sort (event_time_less_than);
 863                         unlocked_invalidate_insert_iterator ();
 864                 } else {
 865                         _sort_pending = true;
 866                 }
 867
 868                 mark_dirty ();
 869         }
 870
 871         maybe_signal_changed ();
 872 }
 873
 874 std::pair<ControlList::iterator,ControlList::iterator>
 875 ControlList::control_points_adjacent (double xval)
 876 {
 877         Glib::Threads::Mutex::Lock lm (_lock);
 878         iterator i;
 879         ControlEvent cp (xval, 0.0f);
 880         std::pair<iterator,iterator> ret;
 881
 882         ret.first = _events.end();
 883         ret.second = _events.end();
 884
 885         for (i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator); i != _events.end(); ++i) {
 886
 887                 if (ret.first == _events.end()) {
 888                         if ((*i)->when >= xval) {
 889                                 if (i != _events.begin()) {
 890                                         ret.first = i;
 891                                         --ret.first;
 892                                 } else {
 893                                         return ret;
 894                                 }
 895                         }
 896                 }
 897
 898                 if ((*i)->when > xval) {
 899                         ret.second = i;
 900                         break;
 901                 }
 902         }
 903
 904         return ret;
 905 }
 906
 907 void
 908 ControlList::freeze ()
 909 {
 910         _frozen++;
 911 }
 912
 913 void
 914 ControlList::thaw ()
 915 {
 916         assert(_frozen > 0);
 917
 918         if (--_frozen > 0) {
 919                 return;
 920         }
 921
 922         {
 923                 Glib::Threads::Mutex::Lock lm (_lock);
 924
 925                 if (_sort_pending) {
 926                         _events.sort (event_time_less_than);
 927                         unlocked_invalidate_insert_iterator ();
 928                         _sort_pending = false;
 929                 }
 930         }
 931 }
 932
 933 void
 934 ControlList::mark_dirty () const
 935 {
 936         _lookup_cache.left = -1;
 937         _lookup_cache.range.first = _events.end();
 938         _lookup_cache.range.second = _events.end();
 939         _search_cache.left = -1;
 940         _search_cache.first = _events.end();
 941
 942         if (_curve) {
 943                 _curve->mark_dirty();
 944         }
 945
 946         Dirty (); /* EMIT SIGNAL */
 947 }
 948
 949 void
 950 ControlList::truncate_end (double last_coordinate)
 951 {
 952         {
 953                 Glib::Threads::Mutex::Lock lm (_lock);
 954                 ControlEvent cp (last_coordinate, 0);
 955                 ControlList::reverse_iterator i;
 956                 double last_val;
 957
 958                 if (_events.empty()) {
 959                         return;
 960                 }
 961
 962                 if (last_coordinate == _events.back()->when) {
 963                         return;
 964                 }
 965
 966                 if (last_coordinate > _events.back()->when) {
 967
 968                         /* extending end:
 969                          */
 970
 971                         iterator foo = _events.begin();
 972                         bool lessthantwo;
 973
 974                         if (foo == _events.end()) {
 975                                 lessthantwo = true;
 976                         } else if (++foo == _events.end()) {
 977                                 lessthantwo = true;
 978                         } else {
 979                                 lessthantwo = false;
 980                         }
 981
 982                         if (lessthantwo) {
 983                                 /* less than 2 points: add a new point */
 984                                 _events.push_back (new ControlEvent (last_coordinate, _events.back()->value));
 985                         } else {
 986
 987                                 /* more than 2 points: check to see if the last 2 values
 988                                    are equal. if so, just move the position of the
 989                                    last point. otherwise, add a new point.
 990                                 */
 991
 992                                 iterator penultimate = _events.end();
 993                                 --penultimate; /* points at last point */
 994                                 --penultimate; /* points at the penultimate point */
 995
 996                                 if (_events.back()->value == (*penultimate)->value) {
 997                                         _events.back()->when = last_coordinate;
 998                                 } else {
 999                                         _events.push_back (new ControlEvent (last_coordinate, _events.back()->value));
1000                                 }
1001                         }
1002
1003                 } else {
1004
1005                         /* shortening end */
1006
1007                         last_val = unlocked_eval (last_coordinate);
1008                         last_val = max ((double) _min_yval, last_val);
1009                         last_val = min ((double) _max_yval, last_val);
1010
1011                         i = _events.rbegin();
1012
1013                         /* make i point to the last control point */
1014
1015                         ++i;
1016
1017                         /* now go backwards, removing control points that are
1018                            beyond the new last coordinate.
1019                         */
1020
1021                         // FIXME: SLOW! (size() == O(n))
1022
1023                         uint32_t sz = _events.size();
1024
1025                         while (i != _events.rend() && sz > 2) {
1026                                 ControlList::reverse_iterator tmp;
1027
1028                                 tmp = i;
1029                                 ++tmp;
1030
1031                                 if ((*i)->when < last_coordinate) {
1032                                         break;
1033                                 }
1034
1035                                 _events.erase (i.base());
1036                                 --sz;
1037
1038                                 i = tmp;
1039                         }
1040
1041                         _events.back()->when = last_coordinate;
1042                         _events.back()->value = last_val;
1043                 }
1044
1045                 unlocked_invalidate_insert_iterator ();
1046                 mark_dirty();
1047         }
1048
1049         maybe_signal_changed ();
1050 }
1051
1052 void
1053 ControlList::truncate_start (double overall_length)
1054 {
1055         {
1056                 Glib::Threads::Mutex::Lock lm (_lock);
1057                 iterator i;
1058                 double first_legal_value;
1059                 double first_legal_coordinate;
1060
1061                 assert(!_events.empty());
1062
1063                 if (overall_length == _events.back()->when) {
1064                         /* no change in overall length */
1065                         return;
1066                 }
1067
1068                 if (overall_length > _events.back()->when) {
1069
1070                         /* growing at front: duplicate first point. shift all others */
1071
1072                         double shift = overall_length - _events.back()->when;
1073                         uint32_t np;
1074
1075                         for (np = 0, i = _events.begin(); i != _events.end(); ++i, ++np) {
1076                                 (*i)->when += shift;
1077                         }
1078
1079                         if (np < 2) {
1080
1081                                 /* less than 2 points: add a new point */
1082                                 _events.push_front (new ControlEvent (0, _events.front()->value));
1083
1084                         } else {
1085
1086                                 /* more than 2 points: check to see if the first 2 values
1087                                    are equal. if so, just move the position of the
1088                                    first point. otherwise, add a new point.
1089                                 */
1090
1091                                 iterator second = _events.begin();
1092                                 ++second; /* points at the second point */
1093
1094                                 if (_events.front()->value == (*second)->value) {
1095                                         /* first segment is flat, just move start point back to zero */
1096                                         _events.front()->when = 0;
1097                                 } else {
1098                                         /* leave non-flat segment in place, add a new leading point. */
1099                                         _events.push_front (new ControlEvent (0, _events.front()->value));
1100                                 }
1101                         }
1102
1103                 } else {
1104
1105                         /* shrinking at front */
1106
1107                         first_legal_coordinate = _events.back()->when - overall_length;
1108                         first_legal_value = unlocked_eval (first_legal_coordinate);
1109                         first_legal_value = max (_min_yval, first_legal_value);
1110                         first_legal_value = min (_max_yval, first_legal_value);
1111
1112                         /* remove all events earlier than the new "front" */
1113
1114                         i = _events.begin();
1115
1116                         while (i != _events.end() && !_events.empty()) {
1117                                 ControlList::iterator tmp;
1118
1119                                 tmp = i;
1120                                 ++tmp;
1121
1122                                 if ((*i)->when > first_legal_coordinate) {
1123                                         break;
1124                                 }
1125
1126                                 _events.erase (i);
1127
1128                                 i = tmp;
1129                         }
1130
1131
1132                         /* shift all remaining points left to keep their same
1133                            relative position
1134                         */
1135
1136                         for (i = _events.begin(); i != _events.end(); ++i) {
1137                                 (*i)->when -= first_legal_coordinate;
1138                         }
1139
1140                         /* add a new point for the interpolated new value */
1141
1142                         _events.push_front (new ControlEvent (0, first_legal_value));
1143                 }
1144
1145                 unlocked_invalidate_insert_iterator ();
1146                 mark_dirty();
1147         }
1148
1149         maybe_signal_changed ();
1150 }
1151
1152 double
1153 ControlList::unlocked_eval (double x) const
1154 {
1155         pair<EventList::iterator,EventList::iterator> range;
1156         int32_t npoints;
1157         double lpos, upos;
1158         double lval, uval;
1159         double fraction;
1160
1161         const_iterator length_check_iter = _events.begin();
1162         for (npoints = 0; npoints < 4; ++npoints, ++length_check_iter) {
1163                 if (length_check_iter == _events.end()) {
1164                         break;
1165                 }
1166         }
1167
1168         switch (npoints) {
1169         case 0:
1170                 return _default_value;
1171
1172         case 1:
1173                 return _events.front()->value;
1174
1175         case 2:
1176                 if (x >= _events.back()->when) {
1177                         return _events.back()->value;
1178                 } else if (x <= _events.front()->when) {
1179                         return _events.front()->value;
1180                 }
1181
1182                 lpos = _events.front()->when;
1183                 lval = _events.front()->value;
1184                 upos = _events.back()->when;
1185                 uval = _events.back()->value;
1186
1187                 if (_interpolation == Discrete) {
1188                         return lval;
1189                 }
1190
1191                 /* linear interpolation betweeen the two points */
1192                 fraction = (double) (x - lpos) / (double) (upos - lpos);
1193                 return lval + (fraction * (uval - lval));
1194
1195         default:
1196                 if (x >= _events.back()->when) {
1197                         return _events.back()->value;
1198                 } else if (x <= _events.front()->when) {
1199                         return _events.front()->value;
1200                 }
1201
1202                 return multipoint_eval (x);
1203         }
1204
1205         abort(); /*NOTREACHED*/ /* stupid gcc */
1206         return _default_value;
1207 }
1208
1209 double
1210 ControlList::multipoint_eval (double x) const
1211 {
1212         double upos, lpos;
1213         double uval, lval;
1214         double fraction;
1215
1216         /* "Stepped" lookup (no interpolation) */
1217         /* FIXME: no cache.  significant? */
1218         if (_interpolation == Discrete) {
1219                 const ControlEvent cp (x, 0);
1220                 EventList::const_iterator i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
1221
1222                 // shouldn't have made it to multipoint_eval
1223                 assert(i != _events.end());
1224
1225                 if (i == _events.begin() || (*i)->when == x)
1226                         return (*i)->value;
1227                 else
1228                         return (*(--i))->value;
1229         }
1230
1231         /* Only do the range lookup if x is in a different range than last time
1232          * this was called (or if the lookup cache has been marked "dirty" (left<0) */
1233         if ((_lookup_cache.left < 0) ||
1234             ((_lookup_cache.left > x) ||
1235              (_lookup_cache.range.first == _events.end()) ||
1236              ((*_lookup_cache.range.second)->when < x))) {
1237
1238                 const ControlEvent cp (x, 0);
1239
1240                 _lookup_cache.range = equal_range (_events.begin(), _events.end(), &cp, time_comparator);
1241         }
1242
1243         pair<const_iterator,const_iterator> range = _lookup_cache.range;
1244
1245         if (range.first == range.second) {
1246
1247                 /* x does not exist within the list as a control point */
1248
1249                 _lookup_cache.left = x;
1250
1251                 if (range.first != _events.begin()) {
1252                         --range.first;
1253                         lpos = (*range.first)->when;
1254                         lval = (*range.first)->value;
1255                 }  else {
1256                         /* we're before the first point */
1257                         // return _default_value;
1258                         return _events.front()->value;
1259                 }
1260
1261                 if (range.second == _events.end()) {
1262                         /* we're after the last point */
1263                         return _events.back()->value;
1264                 }
1265
1266                 upos = (*range.second)->when;
1267                 uval = (*range.second)->value;
1268
1269                 /* linear interpolation betweeen the two points
1270                    on either side of x
1271                 */
1272
1273                 fraction = (double) (x - lpos) / (double) (upos - lpos);
1274                 return lval + (fraction * (uval - lval));
1275
1276         }
1277
1278         /* x is a control point in the data */
1279         _lookup_cache.left = -1;
1280         return (*range.first)->value;
1281 }
1282
1283 void
1284 ControlList::build_search_cache_if_necessary (double start) const
1285 {
1286         /* Only do the range lookup if x is in a different range than last time
1287          * this was called (or if the search cache has been marked "dirty" (left<0) */
1288         if (_events.empty()) {
1289                 _search_cache.first = _events.end();
1290                 _search_cache.left = 0;
1291         } else if ((_search_cache.left < 0) || (_search_cache.left > start)) {
1292
1293                 const ControlEvent start_point (start, 0);
1294
1295                 //cerr << "REBUILD: (" << _search_cache.left << ".." << _search_cache.right << ") := ("
1296                 //      << start << ".." << end << ")" << endl;
1297
1298                 _search_cache.first = lower_bound (_events.begin(), _events.end(), &start_point, time_comparator);
1299                 _search_cache.left = start;
1300         }
1301 }
1302
1303 /** Get the earliest event after \a start using the current interpolation style.
1304  *
1305  * If an event is found, \a x and \a y are set to its coordinates.
1306  *
1307  * \param inclusive Include events with timestamp exactly equal to \a start
1308  * \return true if event is found (and \a x and \a y are valid).
1309  */
1310 bool
1311 ControlList::rt_safe_earliest_event (double start, double& x, double& y, bool inclusive) const
1312 {
1313         // FIXME: It would be nice if this was unnecessary..
1314         Glib::Threads::Mutex::Lock lm(_lock, Glib::Threads::TRY_LOCK);
1315         if (!lm.locked()) {
1316                 return false;
1317         }
1318
1319         return rt_safe_earliest_event_unlocked (start, x, y, inclusive);
1320 }
1321
1322
1323 /** Get the earliest event after \a start using the current interpolation style.
1324  *
1325  * If an event is found, \a x and \a y are set to its coordinates.
1326  *
1327  * \param inclusive Include events with timestamp exactly equal to \a start
1328  * \return true if event is found (and \a x and \a y are valid).
1329  */
1330 bool
1331 ControlList::rt_safe_earliest_event_unlocked (double start, double& x, double& y, bool inclusive) const
1332 {
1333         if (_interpolation == Discrete) {
1334                 return rt_safe_earliest_event_discrete_unlocked(start, x, y, inclusive);
1335         } else {
1336                 return rt_safe_earliest_event_linear_unlocked(start, x, y, inclusive);
1337         }
1338 }
1339
1340
1341 /** Get the earliest event after \a start without 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_discrete_unlocked (double start, double& x, double& y, bool inclusive) const
1350 {
1351         build_search_cache_if_necessary (start);
1352
1353         if (_search_cache.first != _events.end()) {
1354                 const ControlEvent* const first = *_search_cache.first;
1355
1356                 const bool past_start = (inclusive ? first->when >= start : first->when > start);
1357
1358                 /* Earliest points is in range, return it */
1359                 if (past_start) {
1360
1361                         x = first->when;
1362                         y = first->value;
1363
1364                         /* Move left of cache to this point
1365                          * (Optimize for immediate call this cycle within range) */
1366                         _search_cache.left = x;
1367                         ++_search_cache.first;
1368
1369                         assert(x >= start);
1370                         return true;
1371
1372                 } else {
1373                         return false;
1374                 }
1375
1376                 /* No points in range */
1377         } else {
1378                 return false;
1379         }
1380 }
1381
1382 /** Get the earliest time the line crosses an integer (Linear interpolation).
1383  *
1384  * If an event is found, \a x and \a y are set to its coordinates.
1385  *
1386  * \param inclusive Include events with timestamp exactly equal to \a start
1387  * \return true if event is found (and \a x and \a y are valid).
1388  */
1389 bool
1390 ControlList::rt_safe_earliest_event_linear_unlocked (double start, double& x, double& y, bool inclusive) const
1391 {
1392         // cout << "earliest_event(start: " << start << ", x: " << x << ", y: " << y << ", inclusive: " << inclusive <<  ")" << endl;
1393
1394         const_iterator length_check_iter = _events.begin();
1395         if (_events.empty()) { // 0 events
1396                 return false;
1397         } else if (_events.end() == ++length_check_iter) { // 1 event
1398                 return rt_safe_earliest_event_discrete_unlocked (start, x, y, inclusive);
1399         }
1400
1401         // Hack to avoid infinitely repeating the same event
1402         build_search_cache_if_necessary (start);
1403
1404         if (_search_cache.first != _events.end()) {
1405
1406                 const ControlEvent* first = NULL;
1407                 const ControlEvent* next = NULL;
1408
1409                 /* Step is after first */
1410                 if (_search_cache.first == _events.begin() || (*_search_cache.first)->when <= start) {
1411                         first = *_search_cache.first;
1412                         ++_search_cache.first;
1413                         if (_search_cache.first == _events.end()) {
1414                                 return false;
1415                         }
1416                         next = *_search_cache.first;
1417
1418                         /* Step is before first */
1419                 } else {
1420                         const_iterator prev = _search_cache.first;
1421                         --prev;
1422                         first = *prev;
1423                         next = *_search_cache.first;
1424                 }
1425
1426                 if (inclusive && first->when == start) {
1427                         x = first->when;
1428                         y = first->value;
1429                         /* Move left of cache to this point
1430                          * (Optimize for immediate call this cycle within range) */
1431                         _search_cache.left = x;
1432                         return true;
1433                 } else if (next->when < start || (!inclusive && next->when == start)) {
1434                         /* "Next" is before the start, no points left. */
1435                         return false;
1436                 }
1437
1438                 if (fabs(first->value - next->value) <= 1) {
1439                         if (next->when > start) {
1440                                 x = next->when;
1441                                 y = next->value;
1442                                 /* Move left of cache to this point
1443                                  * (Optimize for immediate call this cycle within range) */
1444                                 _search_cache.left = x;
1445                                 return true;
1446                         } else {
1447                                 return false;
1448                         }
1449                 }
1450
1451                 const double slope = (next->value - first->value) / (double)(next->when - first->when);
1452                 //cerr << "start y: " << start_y << endl;
1453
1454                 //y = first->value + (slope * fabs(start - first->when));
1455                 y = first->value;
1456
1457                 if (first->value < next->value) // ramping up
1458                         y = ceil(y);
1459                 else // ramping down
1460                         y = floor(y);
1461
1462                 x = first->when + (y - first->value) / (double)slope;
1463
1464                 while ((inclusive && x < start) || (x <= start && y != next->value)) {
1465
1466                         if (first->value < next->value) // ramping up
1467                                 y += 1.0;
1468                         else // ramping down
1469                                 y -= 1.0;
1470
1471                         x = first->when + (y - first->value) / (double)slope;
1472                 }
1473
1474                 /*cerr << first->value << " @ " << first->when << " ... "
1475                   << next->value << " @ " << next->when
1476                   << " = " << y << " @ " << x << endl;*/
1477
1478                 assert(    (y >= first->value && y <= next->value)
1479                            || (y <= first->value && y >= next->value) );
1480
1481
1482                 const bool past_start = (inclusive ? x >= start : x > start);
1483                 if (past_start) {
1484                         /* Move left of cache to this point
1485                          * (Optimize for immediate call this cycle within range) */
1486                         _search_cache.left = x;
1487                         assert(inclusive ? x >= start : x > start);
1488                         return true;
1489                 } else {
1490                         if (inclusive) {
1491                                 x = next->when;
1492                         } else {
1493                                 x = start;
1494                         }
1495                         _search_cache.left = x;
1496                         return true;
1497                 }
1498
1499                 /* No points in the future, so no steps (towards them) in the future */
1500         } else {
1501                 return false;
1502         }
1503 }
1504
1505
1506 /** @param start Start position in model coordinates.
1507  *  @param end End position in model coordinates.
1508  *  @param op 0 = cut, 1 = copy, 2 = clear.
1509  */
1510 boost::shared_ptr<ControlList>
1511 ControlList::cut_copy_clear (double start, double end, int op)
1512 {
1513         boost::shared_ptr<ControlList> nal = create (_parameter, _desc);
1514         iterator s, e;
1515         ControlEvent cp (start, 0.0);
1516
1517         {
1518                 Glib::Threads::Mutex::Lock lm (_lock);
1519
1520                 /* first, determine s & e, two iterators that define the range of points
1521                    affected by this operation
1522                 */
1523
1524                 if ((s = lower_bound (_events.begin(), _events.end(), &cp, time_comparator)) == _events.end()) {
1525                         return nal;
1526                 }
1527
1528                 /* and the last that is at or after `end' */
1529                 cp.when = end;
1530                 e = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
1531
1532
1533                 /* if "start" isn't the location of an existing point,
1534                    evaluate the curve to get a value for the start. Add a point to
1535                    both the existing event list, and if its not a "clear" operation,
1536                    to the copy ("nal") as well.
1537
1538                    Note that the time positions of the points in each list are different
1539                    because we want the copy ("nal") to have a zero time reference.
1540                 */
1541
1542
1543                 /* before we begin any cut/clear operations, get the value of the curve
1544                    at "end".
1545                 */
1546
1547                 double end_value = unlocked_eval (end);
1548
1549                 if ((*s)->when != start) {
1550
1551                         double val = unlocked_eval (start);
1552
1553                         if (op == 0) { // cut
1554                                 if (start > _events.front()->when) {
1555                                         _events.insert (s, (new ControlEvent (start, val)));
1556                                 }
1557                         }
1558
1559                         if (op != 2) { // ! clear
1560                                 nal->_events.push_back (new ControlEvent (0, val));
1561                         }
1562                 }
1563
1564                 for (iterator x = s; x != e; ) {
1565
1566                         /* adjust new points to be relative to start, which
1567                            has been set to zero.
1568                         */
1569
1570                         if (op != 2) {
1571                                 nal->_events.push_back (new ControlEvent ((*x)->when - start, (*x)->value));
1572                         }
1573
1574                         if (op != 1) {
1575                                 x = _events.erase (x);
1576                         } else {
1577                                 ++x;
1578                         }
1579                 }
1580
1581                 if (e == _events.end() || (*e)->when != end) {
1582
1583                         /* only add a boundary point if there is a point after "end"
1584                          */
1585
1586                         if (op == 0 && (e != _events.end() && end < (*e)->when)) { // cut
1587                                 _events.insert (e, new ControlEvent (end, end_value));
1588                         }
1589
1590                         if (op != 2 && (e != _events.end() && end < (*e)->when)) { // cut/copy
1591                                 nal->_events.push_back (new ControlEvent (end - start, end_value));
1592                         }
1593                 }
1594
1595                 unlocked_invalidate_insert_iterator ();
1596                 mark_dirty ();
1597         }
1598
1599         if (op != 1) {
1600                 maybe_signal_changed ();
1601         }
1602
1603         return nal;
1604 }
1605
1606
1607 boost::shared_ptr<ControlList>
1608 ControlList::cut (double start, double end)
1609 {
1610         return cut_copy_clear (start, end, 0);
1611 }
1612
1613 boost::shared_ptr<ControlList>
1614 ControlList::copy (double start, double end)
1615 {
1616         return cut_copy_clear (start, end, 1);
1617 }
1618
1619 void
1620 ControlList::clear (double start, double end)
1621 {
1622         cut_copy_clear (start, end, 2);
1623 }
1624
1625 /** @param pos Position in model coordinates */
1626 bool
1627 ControlList::paste (const ControlList& alist, double pos, float /*times*/)
1628 {
1629         if (alist._events.empty()) {
1630                 return false;
1631         }
1632
1633         {
1634                 Glib::Threads::Mutex::Lock lm (_lock);
1635                 iterator where;
1636                 iterator prev;
1637                 double end = 0;
1638                 ControlEvent cp (pos, 0.0);
1639
1640                 where = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
1641
1642                 for (const_iterator i = alist.begin();i != alist.end(); ++i) {
1643                         _events.insert (where, new ControlEvent( (*i)->when+pos,( *i)->value));
1644                         end = (*i)->when + pos;
1645                 }
1646
1647
1648                 /* move all  points after the insertion along the timeline by
1649                    the correct amount.
1650                 */
1651
1652                 while (where != _events.end()) {
1653                         iterator tmp;
1654                         if ((*where)->when <= end) {
1655                                 tmp = where;
1656                                 ++tmp;
1657                                 _events.erase(where);
1658                                 where = tmp;
1659
1660                         } else {
1661                                 break;
1662                         }
1663                 }
1664
1665                 unlocked_invalidate_insert_iterator ();
1666                 mark_dirty ();
1667         }
1668
1669         maybe_signal_changed ();
1670         return true;
1671 }
1672
1673 /** Move automation around according to a list of region movements.
1674  *  @param return true if anything was changed, otherwise false (ie nothing needed changing)
1675  */
1676 bool
1677 ControlList::move_ranges (const list< RangeMove<double> >& movements)
1678 {
1679         typedef list< RangeMove<double> > RangeMoveList;
1680
1681         {
1682                 Glib::Threads::Mutex::Lock lm (_lock);
1683
1684                 /* a copy of the events list before we started moving stuff around */
1685                 EventList old_events = _events;
1686
1687                 /* clear the source and destination ranges in the new list */
1688                 bool things_erased = false;
1689                 for (RangeMoveList::const_iterator i = movements.begin (); i != movements.end (); ++i) {
1690
1691                         if (erase_range_internal (i->from, i->from + i->length, _events)) {
1692                                 things_erased = true;
1693                         }
1694
1695                         if (erase_range_internal (i->to, i->to + i->length, _events)) {
1696                                 things_erased = true;
1697                         }
1698                 }
1699
1700                 /* if nothing was erased, there is nothing to do */
1701                 if (!things_erased) {
1702                         return false;
1703                 }
1704
1705                 /* copy the events into the new list */
1706                 for (RangeMoveList::const_iterator i = movements.begin (); i != movements.end (); ++i) {
1707                         iterator j = old_events.begin ();
1708                         const double limit = i->from + i->length;
1709                         const double dx    = i->to - i->from;
1710                         while (j != old_events.end () && (*j)->when <= limit) {
1711                                 if ((*j)->when >= i->from) {
1712                                         ControlEvent* ev = new ControlEvent (**j);
1713                                         ev->when += dx;
1714                                         _events.push_back (ev);
1715                                 }
1716                                 ++j;
1717                         }
1718                 }
1719
1720                 if (!_frozen) {
1721                         _events.sort (event_time_less_than);
1722                         unlocked_invalidate_insert_iterator ();
1723                 } else {
1724                         _sort_pending = true;
1725                 }
1726
1727                 mark_dirty ();
1728         }
1729
1730         maybe_signal_changed ();
1731         return true;
1732 }
1733
1734 void
1735 ControlList::set_interpolation (InterpolationStyle s)
1736 {
1737         if (_interpolation == s) {
1738                 return;
1739         }
1740
1741         _interpolation = s;
1742         InterpolationChanged (s); /* EMIT SIGNAL */
1743 }
1744
1745 bool
1746 ControlList::operator!= (ControlList const & other) const
1747 {
1748         if (_events.size() != other._events.size()) {
1749                 return true;
1750         }
1751
1752         EventList::const_iterator i = _events.begin ();
1753         EventList::const_iterator j = other._events.begin ();
1754
1755         while (i != _events.end() && (*i)->when == (*j)->when && (*i)->value == (*j)->value) {
1756                 ++i;
1757                 ++j;
1758         }
1759
1760         if (i != _events.end ()) {
1761                 return true;
1762         }
1763
1764         return (
1765                 _parameter != other._parameter ||
1766                 _interpolation != other._interpolation ||
1767                 _min_yval != other._min_yval ||
1768                 _max_yval != other._max_yval ||
1769                 _default_value != other._default_value
1770                 );
1771 }
1772
1773 void
1774 ControlList::dump (ostream& o)
1775 {
1776         /* NOT LOCKED ... for debugging only */
1777
1778         for (EventList::iterator x = _events.begin(); x != _events.end(); ++x) {
1779                 o << (*x)->value << " @ " << (uint64_t) (*x)->when << endl;
1780         }
1781 }
1782
1783 } // namespace Evoral
1784