libs/evoral/src/ControlList.cpp

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