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