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