libs/evoral/src/ControlList.cpp

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