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