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