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