libs/evoral/src/ControlList.cpp

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