libs/evoral/src/ControlList.cpp

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