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
  25 using namespace std;
  26
  27 namespace Evoral {
  28
  29
  30 inline bool event_time_less_than (ControlEvent* a, ControlEvent* b)
  31 {
  32         return a->when < b->when;
  33 }
  34
  35
  36 ControlList::ControlList (const Parameter& id)
  37         : _parameter(id)
  38         , _interpolation(Linear)
  39         , _curve(new Curve(*this))
  40 {
  41         _frozen = 0;
  42         _changed_when_thawed = false;
  43         _min_yval = id.min();
  44         _max_yval = id.max();
  45         _max_xval = 0; // means "no limit"
  46         _rt_insertion_point = _events.end();
  47         _lookup_cache.left = -1;
  48         _lookup_cache.range.first = _events.end();
  49         _search_cache.left = -1;
  50         _search_cache.range.first = _events.end();
  51         _sort_pending = false;
  52 }
  53
  54 ControlList::ControlList (const ControlList& other)
  55         : _parameter(other._parameter)
  56         , _interpolation(Linear)
  57         , _curve(new Curve(*this))
  58 {
  59         _frozen = 0;
  60         _changed_when_thawed = false;
  61         _min_yval = other._min_yval;
  62         _max_yval = other._max_yval;
  63         _max_xval = other._max_xval;
  64         _default_value = other._default_value;
  65         _rt_insertion_point = _events.end();
  66         _lookup_cache.range.first = _events.end();
  67         _search_cache.range.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(new Curve(*this))
  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         _rt_insertion_point = _events.end();
  89         _lookup_cache.range.first = _events.end();
  90         _search_cache.range.first = _events.end();
  91         _sort_pending = false;
  92
  93         /* now grab the relevant points, and shift them back if necessary */
  94
  95         boost::shared_ptr<ControlList> section = const_cast<ControlList*>(&other)->copy (start, end);
  96
  97         if (!section->empty()) {
  98                 for (iterator i = section->begin(); i != section->end(); ++i) {
  99                         _events.push_back (new ControlEvent ((*i)->when, (*i)->value));
 100                 }
 101         }
 102
 103         mark_dirty ();
 104 }
 105
 106 ControlList::~ControlList()
 107 {
 108         for (EventList::iterator x = _events.begin(); x != _events.end(); ++x) {
 109                 delete (*x);
 110         }
 111 }
 112
 113 boost::shared_ptr<ControlList>
 114 ControlList::create(Parameter id)
 115 {
 116         return boost::shared_ptr<ControlList>(new ControlList(id));
 117 }
 118
 119 bool
 120 ControlList::operator== (const ControlList& other)
 121 {
 122         return _events == other._events;
 123 }
 124
 125 ControlList&
 126 ControlList::operator= (const ControlList& other)
 127 {
 128         if (this != &other) {
 129
 130                 _events.clear ();
 131
 132                 for (const_iterator i = other._events.begin(); i != other._events.end(); ++i) {
 133                         _events.push_back (new ControlEvent (**i));
 134                 }
 135
 136                 _min_yval = other._min_yval;
 137                 _max_yval = other._max_yval;
 138                 _max_xval = other._max_xval;
 139                 _default_value = other._default_value;
 140
 141                 mark_dirty ();
 142                 maybe_signal_changed ();
 143         }
 144
 145         return *this;
 146 }
 147
 148 void
 149 ControlList::maybe_signal_changed ()
 150 {
 151         mark_dirty ();
 152
 153         if (_frozen)
 154                 _changed_when_thawed = true;
 155 }
 156
 157 void
 158 ControlList::clear ()
 159 {
 160         {
 161                 Glib::Mutex::Lock lm (_lock);
 162                 _events.clear ();
 163                 mark_dirty ();
 164         }
 165
 166         maybe_signal_changed ();
 167 }
 168
 169 void
 170 ControlList::x_scale (double factor)
 171 {
 172         Glib::Mutex::Lock lm (_lock);
 173         _x_scale (factor);
 174 }
 175
 176 bool
 177 ControlList::extend_to (double when)
 178 {
 179         Glib::Mutex::Lock lm (_lock);
 180         if (_events.empty() || _events.back()->when == when) {
 181                 return false;
 182         }
 183         double factor = when / _events.back()->when;
 184         _x_scale (factor);
 185         return true;
 186 }
 187
 188 void ControlList::_x_scale (double factor)
 189 {
 190         for (iterator i = _events.begin(); i != _events.end(); ++i) {
 191                 (*i)->when = floor ((*i)->when * factor);
 192         }
 193
 194         mark_dirty ();
 195 }
 196
 197 void
 198 ControlList::reposition_for_rt_add (double when)
 199 {
 200         _rt_insertion_point = _events.end();
 201 }
 202
 203 void
 204 ControlList::rt_add (double when, double value)
 205 {
 206         //cerr << "RT: alist " << this << " add " << value << " @ " << when << endl;
 207
 208         {
 209                 Glib::Mutex::Lock lm (_lock);
 210
 211                 iterator where;
 212                 ControlEvent cp (when, 0.0);
 213                 bool done = false;
 214
 215                 if ((_rt_insertion_point != _events.end()) && ((*_rt_insertion_point)->when < when) ) {
 216
 217                         /* we have a previous insertion point, so we should delete
 218                            everything between it and the position where we are going
 219                            to insert this point.
 220                         */
 221
 222                         iterator after = _rt_insertion_point;
 223
 224                         if (++after != _events.end()) {
 225                                 iterator far = after;
 226
 227                                 while (far != _events.end()) {
 228                                         if ((*far)->when > when) {
 229                                                 break;
 230                                         }
 231                                         ++far;
 232                                 }
 233
 234                                 if (_new_value) {
 235                                         where = far;
 236                                         _rt_insertion_point = where;
 237
 238                                         if ((*where)->when == when) {
 239                                                 (*where)->value = value;
 240                                                 done = true;
 241                                         }
 242                                 } else {
 243                                         where = _events.erase (after, far);
 244                                 }
 245
 246                         } else {
 247
 248                                 where = after;
 249
 250                         }
 251
 252                         iterator previous = _rt_insertion_point;
 253                         --previous;
 254
 255                         if (_rt_insertion_point != _events.begin() && (*_rt_insertion_point)->value == value && (*previous)->value == value) {
 256                                 (*_rt_insertion_point)->when = when;
 257                                 done = true;
 258
 259                         }
 260
 261                 } else {
 262
 263                         where = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
 264
 265                         if (where != _events.end()) {
 266                                 if ((*where)->when == when) {
 267                                         (*where)->value = value;
 268                                         done = true;
 269                                 }
 270                         }
 271                 }
 272
 273                 if (!done) {
 274                         _rt_insertion_point = _events.insert (where, new ControlEvent (when, value));
 275                 }
 276
 277                 _new_value = false;
 278                 mark_dirty ();
 279         }
 280
 281         maybe_signal_changed ();
 282 }
 283
 284 void
 285 ControlList::fast_simple_add (double when, double value)
 286 {
 287         /* to be used only for loading pre-sorted data from saved state */
 288         _events.insert (_events.end(), new ControlEvent (when, value));
 289         assert(_events.back());
 290 }
 291
 292 void
 293 ControlList::add (double when, double value)
 294 {
 295         /* this is for graphical editing */
 296
 297         {
 298                 Glib::Mutex::Lock lm (_lock);
 299                 ControlEvent cp (when, 0.0f);
 300                 bool insert = true;
 301                 iterator insertion_point;
 302
 303                 for (insertion_point = lower_bound (_events.begin(), _events.end(), &cp, time_comparator); insertion_point != _events.end(); ++insertion_point) {
 304
 305                         /* only one point allowed per time point */
 306
 307                         if ((*insertion_point)->when == when) {
 308                                 (*insertion_point)->value = value;
 309                                 insert = false;
 310                                 break;
 311                         }
 312
 313                         if ((*insertion_point)->when >= when) {
 314                                 break;
 315                         }
 316                 }
 317
 318                 if (insert) {
 319
 320                         _events.insert (insertion_point, new ControlEvent (when, value));
 321                         reposition_for_rt_add (0);
 322
 323                 }
 324
 325                 mark_dirty ();
 326         }
 327
 328         maybe_signal_changed ();
 329 }
 330
 331 void
 332 ControlList::erase (iterator i)
 333 {
 334         {
 335                 Glib::Mutex::Lock lm (_lock);
 336                 _events.erase (i);
 337                 reposition_for_rt_add (0);
 338                 mark_dirty ();
 339         }
 340         maybe_signal_changed ();
 341 }
 342
 343 void
 344 ControlList::erase (iterator start, iterator end)
 345 {
 346         {
 347                 Glib::Mutex::Lock lm (_lock);
 348                 _events.erase (start, end);
 349                 reposition_for_rt_add (0);
 350                 mark_dirty ();
 351         }
 352         maybe_signal_changed ();
 353 }
 354
 355 void
 356 ControlList::reset_range (double start, double endt)
 357 {
 358         bool reset = false;
 359
 360         {
 361         Glib::Mutex::Lock lm (_lock);
 362                 ControlEvent cp (start, 0.0f);
 363                 iterator s;
 364                 iterator e;
 365
 366                 if ((s = lower_bound (_events.begin(), _events.end(), &cp, time_comparator)) != _events.end()) {
 367
 368                         cp.when = endt;
 369                         e = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
 370
 371                         for (iterator i = s; i != e; ++i) {
 372                                 (*i)->value = _default_value;
 373                         }
 374
 375                         reset = true;
 376
 377                         mark_dirty ();
 378                 }
 379         }
 380
 381         if (reset) {
 382                 maybe_signal_changed ();
 383         }
 384 }
 385
 386 void
 387 ControlList::erase_range (double start, double endt)
 388 {
 389         bool erased = false;
 390
 391         {
 392                 Glib::Mutex::Lock lm (_lock);
 393                 ControlEvent cp (start, 0.0f);
 394                 iterator s;
 395                 iterator e;
 396
 397                 if ((s = lower_bound (_events.begin(), _events.end(), &cp, time_comparator)) != _events.end()) {
 398                         cp.when = endt;
 399                         e = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
 400                         _events.erase (s, e);
 401                         reposition_for_rt_add (0);
 402                         erased = true;
 403                         mark_dirty ();
 404                 }
 405
 406         }
 407
 408         if (erased) {
 409                 maybe_signal_changed ();
 410         }
 411 }
 412
 413 void
 414 ControlList::move_range (iterator start, iterator end, double xdelta, double ydelta)
 415 {
 416         /* note: we assume higher level logic is in place to avoid this
 417            reordering the time-order of control events in the list. ie. all
 418            points after end are later than (end)->when.
 419         */
 420
 421         {
 422                 Glib::Mutex::Lock lm (_lock);
 423
 424                 while (start != end) {
 425                         (*start)->when += xdelta;
 426                         (*start)->value += ydelta;
 427                         if (isnan ((*start)->value)) {
 428                                 abort ();
 429                         }
 430                         ++start;
 431                 }
 432
 433                 if (!_frozen) {
 434                         _events.sort (event_time_less_than);
 435                 } else {
 436                         _sort_pending = true;
 437                 }
 438
 439                 mark_dirty ();
 440         }
 441
 442         maybe_signal_changed ();
 443 }
 444
 445 void
 446 ControlList::slide (iterator before, double distance)
 447 {
 448         {
 449                 Glib::Mutex::Lock lm (_lock);
 450
 451                 if (before == _events.end()) {
 452                         return;
 453                 }
 454
 455                 while (before != _events.end()) {
 456                         (*before)->when += distance;
 457                         ++before;
 458                 }
 459         }
 460
 461         maybe_signal_changed ();
 462 }
 463
 464 void
 465 ControlList::modify (iterator iter, double when, double val)
 466 {
 467         /* note: we assume higher level logic is in place to avoid this
 468            reordering the time-order of control events in the list. ie. all
 469            points after *iter are later than when.
 470         */
 471
 472         {
 473                 Glib::Mutex::Lock lm (_lock);
 474
 475                 (*iter)->when = when;
 476                 (*iter)->value = val;
 477
 478                 if (isnan (val)) {
 479                         abort ();
 480                 }
 481
 482                 if (!_frozen) {
 483                         _events.sort (event_time_less_than);
 484                 } else {
 485                         _sort_pending = true;
 486                 }
 487
 488                 mark_dirty ();
 489         }
 490
 491         maybe_signal_changed ();
 492 }
 493
 494 std::pair<ControlList::iterator,ControlList::iterator>
 495 ControlList::control_points_adjacent (double xval)
 496 {
 497         Glib::Mutex::Lock lm (_lock);
 498         iterator i;
 499         ControlEvent cp (xval, 0.0f);
 500         std::pair<iterator,iterator> ret;
 501
 502         ret.first = _events.end();
 503         ret.second = _events.end();
 504
 505         for (i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator); i != _events.end(); ++i) {
 506
 507                 if (ret.first == _events.end()) {
 508                         if ((*i)->when >= xval) {
 509                                 if (i != _events.begin()) {
 510                                         ret.first = i;
 511                                         --ret.first;
 512                                 } else {
 513                                         return ret;
 514                                 }
 515                         }
 516                 }
 517
 518                 if ((*i)->when > xval) {
 519                         ret.second = i;
 520                         break;
 521                 }
 522         }
 523
 524         return ret;
 525 }
 526
 527 void
 528 ControlList::set_max_xval (double x)
 529 {
 530         _max_xval = x;
 531 }
 532
 533 void
 534 ControlList::freeze ()
 535 {
 536         _frozen++;
 537 }
 538
 539 void
 540 ControlList::thaw ()
 541 {
 542         assert(_frozen > 0);
 543
 544         if (--_frozen > 0) {
 545                 return;
 546         }
 547
 548         {
 549                 Glib::Mutex::Lock lm (_lock);
 550
 551                 if (_sort_pending) {
 552                         _events.sort (event_time_less_than);
 553                         _sort_pending = false;
 554                 }
 555         }
 556 }
 557
 558 void
 559 ControlList::mark_dirty () const
 560 {
 561         _lookup_cache.left = -1;
 562         _search_cache.left = -1;
 563         if (_curve)
 564                 _curve->mark_dirty();
 565 }
 566
 567 void
 568 ControlList::truncate_end (double last_coordinate)
 569 {
 570         {
 571                 Glib::Mutex::Lock lm (_lock);
 572                 ControlEvent cp (last_coordinate, 0);
 573                 ControlList::reverse_iterator i;
 574                 double last_val;
 575
 576                 if (_events.empty()) {
 577                         return;
 578                 }
 579
 580                 if (last_coordinate == _events.back()->when) {
 581                         return;
 582                 }
 583
 584                 if (last_coordinate > _events.back()->when) {
 585
 586                         /* extending end:
 587                         */
 588
 589                         iterator foo = _events.begin();
 590                         bool lessthantwo;
 591
 592                         if (foo == _events.end()) {
 593                                 lessthantwo = true;
 594                         } else if (++foo == _events.end()) {
 595                                 lessthantwo = true;
 596                         } else {
 597                                 lessthantwo = false;
 598                         }
 599
 600                         if (lessthantwo) {
 601                                 /* less than 2 points: add a new point */
 602                                 _events.push_back (new ControlEvent (last_coordinate, _events.back()->value));
 603                         } else {
 604
 605                                 /* more than 2 points: check to see if the last 2 values
 606                                    are equal. if so, just move the position of the
 607                                    last point. otherwise, add a new point.
 608                                 */
 609
 610                                 iterator penultimate = _events.end();
 611                                 --penultimate; /* points at last point */
 612                                 --penultimate; /* points at the penultimate point */
 613
 614                                 if (_events.back()->value == (*penultimate)->value) {
 615                                         _events.back()->when = last_coordinate;
 616                                 } else {
 617                                         _events.push_back (new ControlEvent (last_coordinate, _events.back()->value));
 618                                 }
 619                         }
 620
 621                 } else {
 622
 623                         /* shortening end */
 624
 625                         last_val = unlocked_eval (last_coordinate);
 626                         last_val = max ((double) _min_yval, last_val);
 627                         last_val = min ((double) _max_yval, last_val);
 628
 629                         i = _events.rbegin();
 630
 631                         /* make i point to the last control point */
 632
 633                         ++i;
 634
 635                         /* now go backwards, removing control points that are
 636                            beyond the new last coordinate.
 637                         */
 638
 639                         // FIXME: SLOW! (size() == O(n))
 640
 641                         uint32_t sz = _events.size();
 642
 643                         while (i != _events.rend() && sz > 2) {
 644                                 ControlList::reverse_iterator tmp;
 645
 646                                 tmp = i;
 647                                 ++tmp;
 648
 649                                 if ((*i)->when < last_coordinate) {
 650                                         break;
 651                                 }
 652
 653                                 _events.erase (i.base());
 654                                 --sz;
 655
 656                                 i = tmp;
 657                         }
 658
 659                         _events.back()->when = last_coordinate;
 660                         _events.back()->value = last_val;
 661                 }
 662
 663                 reposition_for_rt_add (0);
 664                 mark_dirty();
 665         }
 666
 667         maybe_signal_changed ();
 668 }
 669
 670 void
 671 ControlList::truncate_start (double overall_length)
 672 {
 673         {
 674                 Glib::Mutex::Lock lm (_lock);
 675                 iterator i;
 676                 double first_legal_value;
 677                 double first_legal_coordinate;
 678
 679                 assert(!_events.empty());
 680
 681                 if (overall_length == _events.back()->when) {
 682                         /* no change in overall length */
 683                         return;
 684                 }
 685
 686                 if (overall_length > _events.back()->when) {
 687
 688                         /* growing at front: duplicate first point. shift all others */
 689
 690                         double shift = overall_length - _events.back()->when;
 691                         uint32_t np;
 692
 693                         for (np = 0, i = _events.begin(); i != _events.end(); ++i, ++np) {
 694                                 (*i)->when += shift;
 695                         }
 696
 697                         if (np < 2) {
 698
 699                                 /* less than 2 points: add a new point */
 700                                 _events.push_front (new ControlEvent (0, _events.front()->value));
 701
 702                         } else {
 703
 704                                 /* more than 2 points: check to see if the first 2 values
 705                                    are equal. if so, just move the position of the
 706                                    first point. otherwise, add a new point.
 707                                 */
 708
 709                                 iterator second = _events.begin();
 710                                 ++second; /* points at the second point */
 711
 712                                 if (_events.front()->value == (*second)->value) {
 713                                         /* first segment is flat, just move start point back to zero */
 714                                         _events.front()->when = 0;
 715                                 } else {
 716                                         /* leave non-flat segment in place, add a new leading point. */
 717                                         _events.push_front (new ControlEvent (0, _events.front()->value));
 718                                 }
 719                         }
 720
 721                 } else {
 722
 723                         /* shrinking at front */
 724
 725                         first_legal_coordinate = _events.back()->when - overall_length;
 726                         first_legal_value = unlocked_eval (first_legal_coordinate);
 727                         first_legal_value = max (_min_yval, first_legal_value);
 728                         first_legal_value = min (_max_yval, first_legal_value);
 729
 730                         /* remove all events earlier than the new "front" */
 731
 732                         i = _events.begin();
 733
 734                         while (i != _events.end() && !_events.empty()) {
 735                                 ControlList::iterator tmp;
 736
 737                                 tmp = i;
 738                                 ++tmp;
 739
 740                                 if ((*i)->when > first_legal_coordinate) {
 741                                         break;
 742                                 }
 743
 744                                 _events.erase (i);
 745
 746                                 i = tmp;
 747                         }
 748
 749
 750                         /* shift all remaining points left to keep their same
 751                            relative position
 752                         */
 753
 754                         for (i = _events.begin(); i != _events.end(); ++i) {
 755                                 (*i)->when -= first_legal_coordinate;
 756                         }
 757
 758                         /* add a new point for the interpolated new value */
 759
 760                         _events.push_front (new ControlEvent (0, first_legal_value));
 761                 }
 762
 763                 reposition_for_rt_add (0);
 764
 765                 mark_dirty();
 766         }
 767
 768         maybe_signal_changed ();
 769 }
 770
 771 double
 772 ControlList::unlocked_eval (double x) const
 773 {
 774         pair<EventList::iterator,EventList::iterator> range;
 775         int32_t npoints;
 776         double lpos, upos;
 777         double lval, uval;
 778         double fraction;
 779
 780         const_iterator length_check_iter = _events.begin();
 781         for (npoints = 0; npoints < 4; ++npoints, ++length_check_iter)
 782                 if (length_check_iter == _events.end())
 783                         break;
 784
 785         switch (npoints) {
 786         case 0:
 787                 return _default_value;
 788
 789         case 1:
 790                 if (x >= _events.front()->when) {
 791                         return _events.front()->value;
 792                 } else {
 793                         // return _default_value;
 794                         return _events.front()->value;
 795                 }
 796
 797         case 2:
 798                 if (x >= _events.back()->when) {
 799                         return _events.back()->value;
 800                 } else if (x == _events.front()->when) {
 801                         return _events.front()->value;
 802                 } else if (x < _events.front()->when) {
 803                         // return _default_value;
 804                         return _events.front()->value;
 805                 }
 806
 807                 lpos = _events.front()->when;
 808                 lval = _events.front()->value;
 809                 upos = _events.back()->when;
 810                 uval = _events.back()->value;
 811
 812                 if (_interpolation == Discrete)
 813                         return lval;
 814
 815                 /* linear interpolation betweeen the two points
 816                 */
 817
 818                 fraction = (double) (x - lpos) / (double) (upos - lpos);
 819                 return lval + (fraction * (uval - lval));
 820
 821         default:
 822
 823                 if (x >= _events.back()->when) {
 824                         return _events.back()->value;
 825                 } else if (x == _events.front()->when) {
 826                         return _events.front()->value;
 827                 } else if (x < _events.front()->when) {
 828                         // return _default_value;
 829                         return _events.front()->value;
 830                 }
 831
 832                 return multipoint_eval (x);
 833                 break;
 834         }
 835
 836         /*NOTREACHED*/ /* stupid gcc */
 837         return 0.0;
 838 }
 839
 840 double
 841 ControlList::multipoint_eval (double x) const
 842 {
 843         double upos, lpos;
 844         double uval, lval;
 845         double fraction;
 846
 847         /* "Stepped" lookup (no interpolation) */
 848         /* FIXME: no cache.  significant? */
 849         if (_interpolation == Discrete) {
 850                 const ControlEvent cp (x, 0);
 851                 EventList::const_iterator i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
 852
 853                 // shouldn't have made it to multipoint_eval
 854                 assert(i != _events.end());
 855
 856                 if (i == _events.begin() || (*i)->when == x)
 857                         return (*i)->value;
 858                 else
 859                         return (*(--i))->value;
 860         }
 861
 862         /* Only do the range lookup if x is in a different range than last time
 863          * this was called (or if the lookup cache has been marked "dirty" (left<0) */
 864         if ((_lookup_cache.left < 0) ||
 865             ((_lookup_cache.left > x) ||
 866              (_lookup_cache.range.first == _events.end()) ||
 867              ((*_lookup_cache.range.second)->when < x))) {
 868
 869                 const ControlEvent cp (x, 0);
 870
 871                 _lookup_cache.range = equal_range (_events.begin(), _events.end(), &cp, time_comparator);
 872         }
 873
 874         pair<const_iterator,const_iterator> range = _lookup_cache.range;
 875
 876         if (range.first == range.second) {
 877
 878                 /* x does not exist within the list as a control point */
 879
 880                 _lookup_cache.left = x;
 881
 882                 if (range.first != _events.begin()) {
 883                         --range.first;
 884                         lpos = (*range.first)->when;
 885                         lval = (*range.first)->value;
 886                 }  else {
 887                         /* we're before the first point */
 888                         // return _default_value;
 889                         return _events.front()->value;
 890                 }
 891
 892                 if (range.second == _events.end()) {
 893                         /* we're after the last point */
 894                         return _events.back()->value;
 895                 }
 896
 897                 upos = (*range.second)->when;
 898                 uval = (*range.second)->value;
 899
 900                 /* linear interpolation betweeen the two points
 901                    on either side of x
 902                 */
 903
 904                 fraction = (double) (x - lpos) / (double) (upos - lpos);
 905                 return lval + (fraction * (uval - lval));
 906
 907         }
 908
 909         /* x is a control point in the data */
 910         _lookup_cache.left = -1;
 911         return (*range.first)->value;
 912 }
 913
 914 void
 915 ControlList::build_search_cache_if_necessary(double start, double end) const
 916 {
 917         /* Only do the range lookup if x is in a different range than last time
 918          * this was called (or if the search cache has been marked "dirty" (left<0) */
 919         if (!_events.empty() && ((_search_cache.left < 0) ||
 920                         ((_search_cache.left > start) ||
 921                          (_search_cache.right < end)))) {
 922
 923                 const ControlEvent start_point (start, 0);
 924                 const ControlEvent end_point (end, 0);
 925
 926                 //cerr << "REBUILD: (" << _search_cache.left << ".." << _search_cache.right << ") := ("
 927                 //      << start << ".." << end << ")" << endl;
 928
 929                 _search_cache.range.first = lower_bound (_events.begin(), _events.end(), &start_point, time_comparator);
 930                 _search_cache.range.second = upper_bound (_events.begin(), _events.end(), &end_point, time_comparator);
 931
 932                 _search_cache.left = start;
 933                 _search_cache.right = end;
 934         }
 935 }
 936
 937 /** Get the earliest event between \a start and \a end, using the current interpolation style.
 938  *
 939  * If an event is found, \a x and \a y are set to its coordinates.
 940  *
 941  * \param inclusive Include events with timestamp exactly equal to \a start
 942  * \return true if event is found (and \a x and \a y are valid).
 943  */
 944 bool
 945 ControlList::rt_safe_earliest_event(double start, double end, double& x, double& y, bool inclusive) const
 946 {
 947         // FIXME: It would be nice if this was unnecessary..
 948         Glib::Mutex::Lock lm(_lock, Glib::TRY_LOCK);
 949         if (!lm.locked()) {
 950                 return false;
 951         }
 952
 953         return rt_safe_earliest_event_unlocked(start, end, x, y, inclusive);
 954 }
 955
 956
 957 /** Get the earliest event between \a start and \a end, using the current interpolation style.
 958  *
 959  * If an event is found, \a x and \a y are set to its coordinates.
 960  *
 961  * \param inclusive Include events with timestamp exactly equal to \a start
 962  * \return true if event is found (and \a x and \a y are valid).
 963  */
 964 bool
 965 ControlList::rt_safe_earliest_event_unlocked(double start, double end, double& x, double& y, bool inclusive) const
 966 {
 967         if (_interpolation == Discrete)
 968                 return rt_safe_earliest_event_discrete_unlocked(start, end, x, y, inclusive);
 969         else
 970                 return rt_safe_earliest_event_linear_unlocked(start, end, x, y, inclusive);
 971 }
 972
 973
 974 /** Get the earliest event between \a start and \a end (Discrete (lack of) interpolation)
 975  *
 976  * If an event is found, \a x and \a y are set to its coordinates.
 977  *
 978  * \param inclusive Include events with timestamp exactly equal to \a start
 979  * \return true if event is found (and \a x and \a y are valid).
 980  */
 981 bool
 982 ControlList::rt_safe_earliest_event_discrete_unlocked (double start, double end, double& x, double& y, bool inclusive) const
 983 {
 984         build_search_cache_if_necessary(start, end);
 985
 986         const pair<const_iterator,const_iterator>& range = _search_cache.range;
 987
 988         if (range.first != _events.end()) {
 989                 const ControlEvent* const first = *range.first;
 990
 991                 const bool past_start = (inclusive ? first->when >= start : first->when > start);
 992
 993                 /* Earliest points is in range, return it */
 994                 if (past_start >= start && first->when < end) {
 995
 996                         x = first->when;
 997                         y = first->value;
 998
 999                         /* Move left of cache to this point
1000                          * (Optimize for immediate call this cycle within range) */
1001                         _search_cache.left = x;
1002                         ++_search_cache.range.first;
1003
1004                         assert(x >= start);
1005                         assert(x < end);
1006                         return true;
1007
1008                 } else {
1009                         return false;
1010                 }
1011
1012         /* No points in range */
1013         } else {
1014                 return false;
1015         }
1016 }
1017
1018 /** Get the earliest time the line crosses an integer (Linear interpolation).
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_linear_unlocked (double start, double end, double& x, double& y, bool inclusive) const
1027 {
1028         //cerr << "earliest_event(" << start << ", " << end << ", " << x << ", " << y << ", " << inclusive << endl;
1029
1030         const_iterator length_check_iter = _events.begin();
1031         if (_events.empty()) // 0 events
1032                 return false;
1033         else if (_events.end() == ++length_check_iter) // 1 event
1034                 return rt_safe_earliest_event_discrete_unlocked(start, end, x, y, inclusive);
1035
1036         // Hack to avoid infinitely repeating the same event
1037         build_search_cache_if_necessary(start, end);
1038
1039         pair<const_iterator,const_iterator> range = _search_cache.range;
1040
1041         if (range.first != _events.end()) {
1042
1043                 const ControlEvent* first = NULL;
1044                 const ControlEvent* next = NULL;
1045
1046                 /* Step is after first */
1047                 if (range.first == _events.begin() || (*range.first)->when == start) {
1048                         first = *range.first;
1049                         next = *(++range.first);
1050                         ++_search_cache.range.first;
1051
1052                 /* Step is before first */
1053                 } else {
1054                         const_iterator prev = range.first;
1055                         --prev;
1056                         first = *prev;
1057                         next = *range.first;
1058                 }
1059
1060                 if (inclusive && first->when == start) {
1061                         x = first->when;
1062                         y = first->value;
1063                         /* Move left of cache to this point
1064                          * (Optimize for immediate call this cycle within range) */
1065                         _search_cache.left = x;
1066                         //++_search_cache.range.first;
1067                         assert(inclusive ? x >= start : x > start);
1068                         return true;
1069                 }
1070
1071                 if (abs(first->value - next->value) <= 1) {
1072                         if (next->when <= end && (!inclusive || next->when > start)) {
1073                                 x = next->when;
1074                                 y = next->value;
1075                                 /* Move left of cache to this point
1076                                  * (Optimize for immediate call this cycle within range) */
1077                                 _search_cache.left = x;
1078                                 //++_search_cache.range.first;
1079                                 assert(inclusive ? x >= start : x > start);
1080                                 return true;
1081                         } else {
1082                                 return false;
1083                         }
1084                 }
1085
1086                 const double slope = (next->value - first->value) / (double)(next->when - first->when);
1087                 //cerr << "start y: " << start_y << endl;
1088
1089                 //y = first->value + (slope * fabs(start - first->when));
1090                 y = first->value;
1091
1092                 if (first->value < next->value) // ramping up
1093                         y = ceil(y);
1094                 else // ramping down
1095                         y = floor(y);
1096
1097                 x = first->when + (y - first->value) / (double)slope;
1098
1099                 while ((inclusive && x < start) || (x <= start && y != next->value)) {
1100
1101                         if (first->value < next->value) // ramping up
1102                                 y += 1.0;
1103                         else // ramping down
1104                                 y -= 1.0;
1105
1106                         x = first->when + (y - first->value) / (double)slope;
1107                 }
1108
1109                 /*cerr << first->value << " @ " << first->when << " ... "
1110                                 << next->value << " @ " << next->when
1111                                 << " = " << y << " @ " << x << endl;*/
1112
1113                 assert(    (y >= first->value && y <= next->value)
1114                                 || (y <= first->value && y >= next->value) );
1115
1116
1117                 const bool past_start = (inclusive ? x >= start : x > start);
1118                 if (past_start && x < end) {
1119                         /* Move left of cache to this point
1120                          * (Optimize for immediate call this cycle within range) */
1121                         _search_cache.left = x;
1122                         assert(inclusive ? x >= start : x > start);
1123                         return true;
1124                 } else {
1125                         return false;
1126                 }
1127
1128         /* No points in the future, so no steps (towards them) in the future */
1129         } else {
1130                 return false;
1131         }
1132 }
1133
1134 boost::shared_ptr<ControlList>
1135 ControlList::cut (iterator start, iterator end)
1136 {
1137         boost::shared_ptr<ControlList> nal = create (_parameter);
1138
1139         {
1140                 Glib::Mutex::Lock lm (_lock);
1141
1142                 for (iterator x = start; x != end; ) {
1143                         iterator tmp;
1144
1145                         tmp = x;
1146                         ++tmp;
1147
1148                         nal->_events.push_back (new ControlEvent (**x));
1149                         _events.erase (x);
1150
1151                         reposition_for_rt_add (0);
1152
1153                         x = tmp;
1154                 }
1155
1156                 mark_dirty ();
1157         }
1158
1159         maybe_signal_changed ();
1160
1161         return nal;
1162 }
1163
1164 boost::shared_ptr<ControlList>
1165 ControlList::cut_copy_clear (double start, double end, int op)
1166 {
1167         boost::shared_ptr<ControlList> nal = create (_parameter);
1168         iterator s, e;
1169         ControlEvent cp (start, 0.0);
1170         bool changed = false;
1171
1172         {
1173                 Glib::Mutex::Lock lm (_lock);
1174
1175                 if ((s = lower_bound (_events.begin(), _events.end(), &cp, time_comparator)) == _events.end()) {
1176                         return nal;
1177                 }
1178
1179                 cp.when = end;
1180                 e = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
1181
1182                 if (op != 2 && (*s)->when != start) {
1183                         nal->_events.push_back (new ControlEvent (0, unlocked_eval (start)));
1184                 }
1185
1186                 for (iterator x = s; x != e; ) {
1187                         iterator tmp;
1188
1189                         tmp = x;
1190                         ++tmp;
1191
1192                         changed = true;
1193
1194                         /* adjust new points to be relative to start, which
1195                            has been set to zero.
1196                         */
1197
1198                         if (op != 2) {
1199                                 nal->_events.push_back (new ControlEvent ((*x)->when - start, (*x)->value));
1200                         }
1201
1202                         if (op != 1) {
1203                                 _events.erase (x);
1204                         }
1205
1206                         x = tmp;
1207                 }
1208
1209                 if (op != 2 && nal->_events.back()->when != end - start) {
1210                         nal->_events.push_back (new ControlEvent (end - start, unlocked_eval (end)));
1211                 }
1212
1213                 if (changed) {
1214                         reposition_for_rt_add (0);
1215                 }
1216
1217                 mark_dirty ();
1218         }
1219
1220         maybe_signal_changed ();
1221
1222         return nal;
1223
1224 }
1225
1226 boost::shared_ptr<ControlList>
1227 ControlList::copy (iterator start, iterator end)
1228 {
1229         boost::shared_ptr<ControlList> nal = create (_parameter);
1230
1231         {
1232                 Glib::Mutex::Lock lm (_lock);
1233
1234                 for (iterator x = start; x != end; ) {
1235                         iterator tmp;
1236
1237                         tmp = x;
1238                         ++tmp;
1239
1240                         nal->_events.push_back (new ControlEvent (**x));
1241
1242                         x = tmp;
1243                 }
1244         }
1245
1246         return nal;
1247 }
1248
1249 boost::shared_ptr<ControlList>
1250 ControlList::cut (double start, double end)
1251 {
1252         return cut_copy_clear (start, end, 0);
1253 }
1254
1255 boost::shared_ptr<ControlList>
1256 ControlList::copy (double start, double end)
1257 {
1258         return cut_copy_clear (start, end, 1);
1259 }
1260
1261 void
1262 ControlList::clear (double start, double end)
1263 {
1264         (void) cut_copy_clear (start, end, 2);
1265 }
1266
1267 bool
1268 ControlList::paste (ControlList& alist, double pos, float times)
1269 {
1270         if (alist._events.empty()) {
1271                 return false;
1272         }
1273
1274         {
1275                 Glib::Mutex::Lock lm (_lock);
1276                 iterator where;
1277                 iterator prev;
1278                 double end = 0;
1279                 ControlEvent cp (pos, 0.0);
1280
1281                 where = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
1282
1283                 for (iterator i = alist.begin();i != alist.end(); ++i) {
1284                         _events.insert (where, new ControlEvent( (*i)->when+pos,( *i)->value));
1285                         end = (*i)->when + pos;
1286                 }
1287
1288
1289                 /* move all  points after the insertion along the timeline by
1290                    the correct amount.
1291                 */
1292
1293                 while (where != _events.end()) {
1294                         iterator tmp;
1295                         if ((*where)->when <= end) {
1296                                 tmp = where;
1297                                 ++tmp;
1298                                 _events.erase(where);
1299                                 where = tmp;
1300
1301                         } else {
1302                                 break;
1303                         }
1304                 }
1305
1306                 reposition_for_rt_add (0);
1307                 mark_dirty ();
1308         }
1309
1310         maybe_signal_changed ();
1311         return true;
1312 }
1313
1314 } // namespace Evoral
1315