libs/evoral/src/ControlList.cpp

   1 /* This file is part of Evoral.
   2  * Copyright (C) 2008 David Robillard <http://drobilla.net>
   3  * Copyright (C) 2000-2008 Paul Davis
   4  *
   5  * Evoral is free software; you can redistribute it and/or modify it under the
   6  * terms of the GNU General Public License as published by the Free Software
   7  * Foundation; either version 2 of the License, or (at your option) any later
   8  * version.
   9  *
  10  * Evoral is distributed in the hope that it will be useful, but WITHOUT ANY
  11  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  12  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17  */
  18
  19 #include <cmath>
  20 #include <cassert>
  21 #include <utility>
  22 #include <iostream>
  23 #include "evoral/ControlList.hpp"
  24 #include "evoral/Curve.hpp"
  25
  26 using namespace std;
  27
  28 namespace Evoral {
  29
  30
  31 inline bool event_time_less_than (ControlEvent* a, ControlEvent* b)
  32 {
  33         return a->when < b->when;
  34 }
  35
  36
  37 ControlList::ControlList (const Parameter& id)
  38         : _parameter(id)
  39         , _interpolation(Linear)
  40         , _curve(0)
  41 {
  42         _frozen = 0;
  43         _changed_when_thawed = false;
  44         _min_yval = id.min();
  45         _max_yval = id.max();
  46         _max_xval = 0; // means "no limit"
  47         _default_value = 0;
  48         _lookup_cache.left = -1;
  49         _lookup_cache.range.first = _events.end();
  50         _search_cache.left = -1;
  51         _search_cache.first = _events.end();
  52         _sort_pending = false;
  53 }
  54
  55 ControlList::ControlList (const ControlList& other)
  56         : _parameter(other._parameter)
  57         , _interpolation(Linear)
  58         , _curve(0)
  59 {
  60         _frozen = 0;
  61         _changed_when_thawed = false;
  62         _min_yval = other._min_yval;
  63         _max_yval = other._max_yval;
  64         _max_xval = other._max_xval;
  65         _default_value = other._default_value;
  66         _lookup_cache.range.first = _events.end();
  67         _search_cache.first = _events.end();
  68         _sort_pending = false;
  69
  70         for (const_iterator i = other._events.begin(); i != other._events.end(); ++i) {
  71                 _events.push_back (new ControlEvent (**i));
  72         }
  73
  74         mark_dirty ();
  75 }
  76
  77 ControlList::ControlList (const ControlList& other, double start, double end)
  78         : _parameter(other._parameter)
  79         , _interpolation(Linear)
  80         , _curve(0)
  81 {
  82         _frozen = 0;
  83         _changed_when_thawed = false;
  84         _min_yval = other._min_yval;
  85         _max_yval = other._max_yval;
  86         _max_xval = other._max_xval;
  87         _default_value = other._default_value;
  88         _lookup_cache.range.first = _events.end();
  89         _search_cache.first = _events.end();
  90         _sort_pending = false;
  91
  92         /* now grab the relevant points, and shift them back if necessary */
  93
  94         boost::shared_ptr<ControlList> section = const_cast<ControlList*>(&other)->copy (start, end);
  95
  96         if (!section->empty()) {
  97                 for (iterator i = section->begin(); i != section->end(); ++i) {
  98                         _events.push_back (new ControlEvent ((*i)->when, (*i)->value));
  99                 }
 100         }
 101
 102         mark_dirty ();
 103 }
 104
 105 ControlList::~ControlList()
 106 {
 107         for (EventList::iterator x = _events.begin(); x != _events.end(); ++x) {
 108                 delete (*x);
 109         }
 110
 111         for (list<NascentInfo*>::iterator n = nascent.begin(); n != nascent.end(); ++n) {
 112                 for (EventList::iterator x = (*n)->events.begin(); x != (*n)->events.end(); ++x) {
 113                         delete *x;
 114                 }
 115                 delete (*n);
 116         }
 117
 118         delete _curve;
 119 }
 120
 121 boost::shared_ptr<ControlList>
 122 ControlList::create(Parameter id)
 123 {
 124         return boost::shared_ptr<ControlList>(new ControlList(id));
 125 }
 126
 127 bool
 128 ControlList::operator== (const ControlList& other)
 129 {
 130         return _events == other._events;
 131 }
 132
 133 ControlList&
 134 ControlList::operator= (const ControlList& other)
 135 {
 136         if (this != &other) {
 137
 138                 _events.clear ();
 139
 140                 for (const_iterator i = other._events.begin(); i != other._events.end(); ++i) {
 141                         _events.push_back (new ControlEvent (**i));
 142                 }
 143
 144                 _min_yval = other._min_yval;
 145                 _max_yval = other._max_yval;
 146                 _max_xval = other._max_xval;
 147                 _default_value = other._default_value;
 148
 149                 mark_dirty ();
 150                 maybe_signal_changed ();
 151         }
 152
 153         return *this;
 154 }
 155
 156 void
 157 ControlList::create_curve()
 158 {
 159         _curve = new Curve(*this);
 160 }
 161
 162 void
 163 ControlList::destroy_curve()
 164 {
 165         delete _curve;
 166         _curve = NULL;
 167 }
 168
 169 void
 170 ControlList::maybe_signal_changed ()
 171 {
 172         mark_dirty ();
 173
 174         if (_frozen) {
 175                 _changed_when_thawed = true;
 176         }
 177 }
 178
 179 void
 180 ControlList::clear ()
 181 {
 182         {
 183                 Glib::Mutex::Lock lm (_lock);
 184                 _events.clear ();
 185                 mark_dirty ();
 186         }
 187
 188         maybe_signal_changed ();
 189 }
 190
 191 void
 192 ControlList::x_scale (double factor)
 193 {
 194         Glib::Mutex::Lock lm (_lock);
 195         _x_scale (factor);
 196 }
 197
 198 bool
 199 ControlList::extend_to (double when)
 200 {
 201         Glib::Mutex::Lock lm (_lock);
 202         if (_events.empty() || _events.back()->when == when) {
 203                 return false;
 204         }
 205         double factor = when / _events.back()->when;
 206         _x_scale (factor);
 207         return true;
 208 }
 209
 210 void
 211 ControlList::_x_scale (double factor)
 212 {
 213         for (iterator i = _events.begin(); i != _events.end(); ++i) {
 214                 (*i)->when *= factor;
 215         }
 216
 217         mark_dirty ();
 218 }
 219
 220 void
 221 ControlList::write_pass_finished (double when)
 222 {
 223         merge_nascent (when);
 224 }
 225
 226
 227 struct ControlEventTimeComparator {
 228         bool operator() (ControlEvent* a, ControlEvent* b) {
 229                 return a->when < b->when;
 230         }
 231 };
 232
 233 void
 234 ControlList::merge_nascent (double when)
 235 {
 236         {
 237                 Glib::Mutex::Lock lm (_lock);
 238
 239                 if (nascent.empty()) {
 240                         return;
 241                 }
 242
 243                 for (list<NascentInfo*>::iterator n = nascent.begin(); n != nascent.end(); ++n) {
 244
 245                         NascentInfo* ninfo = *n;
 246                         EventList& nascent_events (ninfo->events);
 247                         bool need_adjacent_start_clamp;
 248                         bool need_adjacent_end_clamp;
 249
 250                         if (nascent_events.empty()) {
 251                                 delete ninfo;
 252                                 continue;
 253                         }
 254
 255                         nascent_events.sort (ControlEventTimeComparator ());
 256
 257                         if (ninfo->start_time < 0.0) {
 258                                 ninfo->start_time = nascent_events.front()->when;
 259                         }
 260
 261                         if (ninfo->end_time < 0.0) {
 262                                 ninfo->end_time = when;
 263                         }
 264
 265                         bool preexisting = !_events.empty();
 266
 267                         if (!preexisting) {
 268
 269                                 _events = nascent_events;
 270
 271                         } else if (ninfo->end_time < _events.front()->when) {
 272
 273                                 /* all points in nascent are before the first existing point */
 274
 275                                 _events.insert (_events.begin(), nascent_events.begin(), nascent_events.end());
 276
 277                         } else if (ninfo->start_time > _events.back()->when) {
 278
 279                                 /* all points in nascent are after the last existing point */
 280
 281                                 _events.insert (_events.end(), nascent_events.begin(), nascent_events.end());
 282
 283                         } else {
 284
 285                                 /* find the range that overlaps with nascent events,
 286                                    and insert the contents of nascent events.
 287                                 */
 288
 289                                 iterator i;
 290                                 iterator range_begin = _events.end();
 291                                 iterator range_end = _events.end();
 292                                 double end_value = unlocked_eval (ninfo->end_time);
 293                                 double start_value = unlocked_eval (ninfo->start_time - 1);
 294
 295                                 need_adjacent_end_clamp = true;
 296                                 need_adjacent_start_clamp = true;
 297
 298                                 for (i = _events.begin(); i != _events.end(); ++i) {
 299
 300                                         if ((*i)->when == ninfo->start_time) {
 301                                                 /* existing point at same time, remove it
 302                                                    and the consider the next point instead.
 303                                                 */
 304                                                 i = _events.erase (i);
 305
 306                                                 if (i == _events.end()) {
 307                                                         break;
 308                                                 }
 309
 310                                                 if (range_begin == _events.end()) {
 311                                                         range_begin = i;
 312                                                         need_adjacent_start_clamp = false;
 313                                                 } else {
 314                                                         need_adjacent_end_clamp = false;
 315                                                 }
 316
 317                                                 if ((*i)->when > ninfo->end_time) {
 318                                                         range_end = i;
 319                                                         break;
 320                                                 }
 321
 322                                         } else if ((*i)->when > ninfo->start_time) {
 323
 324                                                 if (range_begin == _events.end()) {
 325                                                         range_begin = i;
 326                                                 }
 327
 328                                                 if ((*i)->when > ninfo->end_time) {
 329                                                         range_end = i;
 330                                                         break;
 331                                                 }
 332                                         }
 333                                 }
 334
 335                                 /* Now:
 336                                    range_begin is the first event on our list after the first nascent event
 337                                    range_end   is the first event on our list after the last  nascent event
 338
 339                                    range_begin may be equal to _events.end() iff the last event on our list
 340                                    was at the same time as the first nascent event.
 341                                 */
 342
 343                                 if (range_begin != _events.begin()) {
 344                                         /* clamp point before */
 345                                         if (need_adjacent_start_clamp) {
 346                                                 _events.insert (range_begin, new ControlEvent (ninfo->start_time, start_value));
 347                                         }
 348                                 }
 349
 350                                 _events.insert (range_begin, nascent_events.begin(), nascent_events.end());
 351
 352                                 if (range_end != _events.end()) {
 353                                         /* clamp point after */
 354                                         if (need_adjacent_end_clamp) {
 355                                                 _events.insert (range_begin, new ControlEvent (ninfo->end_time, end_value));
 356                                         }
 357                                 }
 358
 359                                 _events.erase (range_begin, range_end);
 360                         }
 361
 362                         delete ninfo;
 363                 }
 364
 365                 nascent.clear ();
 366
 367                 if (writing()) {
 368                         nascent.push_back (new NascentInfo ());
 369                 }
 370         }
 371
 372         maybe_signal_changed ();
 373 }
 374
 375 void
 376 ControlList::rt_add (double when, double value)
 377 {
 378         // this is for automation recording
 379
 380         if (touch_enabled() && !touching()) {
 381                 return;
 382         }
 383
 384         //cerr << "RT: alist " << this << " add " << value << " @ " << when << endl;
 385
 386         Glib::Mutex::Lock lm (_lock, Glib::TRY_LOCK);
 387
 388         if (lm.locked()) {
 389                 assert (!nascent.empty());
 390                 /* we don't worry about adding events out of time order as we will
 391                    sort them in merge_nascent.
 392                 */
 393
 394                 EventList& el (nascent.back()->events);
 395
 396                 if (el.size() > 1 && (when >= el.back()->when) && (value == el.back()->value)) {
 397                         /* same value, later timestamp, effective slope is
 398                          * zero, so just move the last point in nascent to our
 399                          * new time position. this avoids storing an unlimited
 400                          * number of points to represent a flat line.
 401                          */
 402                         el.back()->when = when;
 403                 } else {
 404                         nascent.back()->events.push_back (new ControlEvent (when, value));
 405                 }
 406         }
 407 }
 408
 409 void
 410 ControlList::thin ()
 411 {
 412         Glib::Mutex::Lock lm (_lock);
 413
 414         ControlEvent* prevprev;
 415         ControlEvent* cur;
 416         ControlEvent* prev;
 417         iterator pprev;
 418         int counter = 0;
 419
 420         for (iterator i = _events.begin(); i != _events.end(); ++i) {
 421
 422                 cur = *i;
 423                 counter++;
 424
 425                 if (counter > 2) {
 426
 427                         double area = fabs (0.5 *
 428                                             (prevprev->when * (prev->value - cur->value)) +
 429                                             (prev->when * (cur->value - prevprev->value)) +
 430                                             (cur->when * (prevprev->value - prev->value)));
 431
 432                         /* the number 10.0 is an arbitrary value that needs to
 433                          * be controlled by some user-controllable
 434                          * configuration utility.
 435                          */
 436
 437                         if (area < 10.0) {
 438                                 iterator tmp = pprev;
 439
 440                                 /* pprev will change to current
 441                                    i is incremented to the next event
 442                                 */
 443
 444                                 pprev = i;
 445                                 _events.erase (tmp);
 446
 447                                 continue;
 448                         }
 449                 }
 450
 451                 prevprev = prev;
 452                 prev = cur;
 453                 pprev = i;
 454         }
 455 }
 456
 457 void
 458 ControlList::fast_simple_add (double when, double value)
 459 {
 460         /* to be used only for loading pre-sorted data from saved state */
 461         _events.insert (_events.end(), new ControlEvent (when, value));
 462         assert(_events.back());
 463 }
 464
 465 void
 466 ControlList::add (double when, double value)
 467 {
 468         /* this is for making changes from some kind of user interface or
 469            control surface (GUI, MIDI, OSC etc)
 470         */
 471
 472         if (!clamp_value (when, value)) {
 473                 return;
 474         }
 475
 476         {
 477                 Glib::Mutex::Lock lm (_lock);
 478                 ControlEvent cp (when, 0.0f);
 479                 bool insert = true;
 480                 iterator insertion_point;
 481
 482                 for (insertion_point = lower_bound (_events.begin(), _events.end(), &cp, time_comparator); insertion_point != _events.end(); ++insertion_point) {
 483
 484                         /* only one point allowed per time point */
 485
 486                         if ((*insertion_point)->when == when) {
 487                                 (*insertion_point)->value = value;
 488                                 insert = false;
 489                                 break;
 490                         }
 491
 492                         if ((*insertion_point)->when >= when) {
 493                                 break;
 494                         }
 495                 }
 496
 497                 if (insert) {
 498
 499                         _events.insert (insertion_point, new ControlEvent (when, value));
 500
 501                 }
 502
 503                 mark_dirty ();
 504         }
 505
 506         maybe_signal_changed ();
 507 }
 508
 509 void
 510 ControlList::erase (iterator i)
 511 {
 512         {
 513                 Glib::Mutex::Lock lm (_lock);
 514                 _events.erase (i);
 515                 mark_dirty ();
 516         }
 517         maybe_signal_changed ();
 518 }
 519
 520 void
 521 ControlList::erase (iterator start, iterator end)
 522 {
 523         {
 524                 Glib::Mutex::Lock lm (_lock);
 525                 _events.erase (start, end);
 526                 mark_dirty ();
 527         }
 528         maybe_signal_changed ();
 529 }
 530
 531 /** Erase the first event which matches the given time and value */
 532 void
 533 ControlList::erase (double when, double value)
 534 {
 535         {
 536                 Glib::Mutex::Lock lm (_lock);
 537
 538                 iterator i = begin ();
 539                 while (i != end() && ((*i)->when != when || (*i)->value != value)) {
 540                         ++i;
 541                 }
 542
 543                 if (i != end ()) {
 544                         _events.erase (i);
 545                 }
 546
 547                 mark_dirty ();
 548         }
 549
 550         maybe_signal_changed ();
 551 }
 552
 553 void
 554 ControlList::reset_range (double start, double endt)
 555 {
 556         bool reset = false;
 557
 558         {
 559                 Glib::Mutex::Lock lm (_lock);
 560                 ControlEvent cp (start, 0.0f);
 561                 iterator s;
 562                 iterator e;
 563
 564                 if ((s = lower_bound (_events.begin(), _events.end(), &cp, time_comparator)) != _events.end()) {
 565
 566                         cp.when = endt;
 567                         e = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
 568
 569                         for (iterator i = s; i != e; ++i) {
 570                                 (*i)->value = _default_value;
 571                         }
 572
 573                         reset = true;
 574
 575                         mark_dirty ();
 576                 }
 577         }
 578
 579         if (reset) {
 580                 maybe_signal_changed ();
 581         }
 582 }
 583
 584 void
 585 ControlList::erase_range (double start, double endt)
 586 {
 587         bool erased = false;
 588
 589         {
 590                 Glib::Mutex::Lock lm (_lock);
 591                 erased = erase_range_internal (start, endt, _events);
 592
 593                 if (erased) {
 594                         mark_dirty ();
 595                 }
 596
 597         }
 598
 599         if (erased) {
 600                 maybe_signal_changed ();
 601         }
 602 }
 603
 604 bool
 605 ControlList::erase_range_internal (double start, double endt, EventList & events)
 606 {
 607         bool erased = false;
 608         ControlEvent cp (start, 0.0f);
 609         iterator s;
 610         iterator e;
 611
 612         if ((s = lower_bound (events.begin(), events.end(), &cp, time_comparator)) != events.end()) {
 613                 cp.when = endt;
 614                 e = upper_bound (events.begin(), events.end(), &cp, time_comparator);
 615                 events.erase (s, e);
 616                 if (s != e) {
 617                         erased = true;
 618                 }
 619         }
 620
 621         return erased;
 622 }
 623
 624 void
 625 ControlList::slide (iterator before, double distance)
 626 {
 627         {
 628                 Glib::Mutex::Lock lm (_lock);
 629
 630                 if (before == _events.end()) {
 631                         return;
 632                 }
 633
 634                 while (before != _events.end()) {
 635                         (*before)->when += distance;
 636                         ++before;
 637                 }
 638
 639                 mark_dirty ();
 640         }
 641
 642         maybe_signal_changed ();
 643 }
 644
 645 void
 646 ControlList::shift (double pos, double frames)
 647 {
 648         {
 649                 Glib::Mutex::Lock lm (_lock);
 650
 651                 for (iterator i = _events.begin(); i != _events.end(); ++i) {
 652                         if ((*i)->when >= pos) {
 653                                 (*i)->when += frames;
 654                         }
 655                 }
 656
 657                 mark_dirty ();
 658         }
 659
 660         maybe_signal_changed ();
 661 }
 662
 663 void
 664 ControlList::modify (iterator iter, double when, double val)
 665 {
 666         /* note: we assume higher level logic is in place to avoid this
 667            reordering the time-order of control events in the list. ie. all
 668            points after *iter are later than when.
 669         */
 670
 671         {
 672                 Glib::Mutex::Lock lm (_lock);
 673
 674                 (*iter)->when = when;
 675                 (*iter)->value = val;
 676
 677                 if (isnan (val)) {
 678                         abort ();
 679                 }
 680
 681                 if (!_frozen) {
 682                         _events.sort (event_time_less_than);
 683                 } else {
 684                         _sort_pending = true;
 685                 }
 686
 687                 mark_dirty ();
 688         }
 689
 690         maybe_signal_changed ();
 691 }
 692
 693 std::pair<ControlList::iterator,ControlList::iterator>
 694 ControlList::control_points_adjacent (double xval)
 695 {
 696         Glib::Mutex::Lock lm (_lock);
 697         iterator i;
 698         ControlEvent cp (xval, 0.0f);
 699         std::pair<iterator,iterator> ret;
 700
 701         ret.first = _events.end();
 702         ret.second = _events.end();
 703
 704         for (i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator); i != _events.end(); ++i) {
 705
 706                 if (ret.first == _events.end()) {
 707                         if ((*i)->when >= xval) {
 708                                 if (i != _events.begin()) {
 709                                         ret.first = i;
 710                                         --ret.first;
 711                                 } else {
 712                                         return ret;
 713                                 }
 714                         }
 715                 }
 716
 717                 if ((*i)->when > xval) {
 718                         ret.second = i;
 719                         break;
 720                 }
 721         }
 722
 723         return ret;
 724 }
 725
 726 void
 727 ControlList::set_max_xval (double x)
 728 {
 729         _max_xval = x;
 730 }
 731
 732 void
 733 ControlList::freeze ()
 734 {
 735         _frozen++;
 736 }
 737
 738 void
 739 ControlList::thaw ()
 740 {
 741         assert(_frozen > 0);
 742
 743         if (--_frozen > 0) {
 744                 return;
 745         }
 746
 747         {
 748                 Glib::Mutex::Lock lm (_lock);
 749
 750                 if (_sort_pending) {
 751                         _events.sort (event_time_less_than);
 752                         _sort_pending = false;
 753                 }
 754         }
 755 }
 756
 757 void
 758 ControlList::mark_dirty () const
 759 {
 760         _lookup_cache.left = -1;
 761         _search_cache.left = -1;
 762
 763         if (_curve) {
 764                 _curve->mark_dirty();
 765         }
 766
 767         Dirty (); /* EMIT SIGNAL */
 768 }
 769
 770 void
 771 ControlList::truncate_end (double last_coordinate)
 772 {
 773         {
 774                 Glib::Mutex::Lock lm (_lock);
 775                 ControlEvent cp (last_coordinate, 0);
 776                 ControlList::reverse_iterator i;
 777                 double last_val;
 778
 779                 if (_events.empty()) {
 780                         return;
 781                 }
 782
 783                 if (last_coordinate == _events.back()->when) {
 784                         return;
 785                 }
 786
 787                 if (last_coordinate > _events.back()->when) {
 788
 789                         /* extending end:
 790                          */
 791
 792                         iterator foo = _events.begin();
 793                         bool lessthantwo;
 794
 795                         if (foo == _events.end()) {
 796                                 lessthantwo = true;
 797                         } else if (++foo == _events.end()) {
 798                                 lessthantwo = true;
 799                         } else {
 800                                 lessthantwo = false;
 801                         }
 802
 803                         if (lessthantwo) {
 804                                 /* less than 2 points: add a new point */
 805                                 _events.push_back (new ControlEvent (last_coordinate, _events.back()->value));
 806                         } else {
 807
 808                                 /* more than 2 points: check to see if the last 2 values
 809                                    are equal. if so, just move the position of the
 810                                    last point. otherwise, add a new point.
 811                                 */
 812
 813                                 iterator penultimate = _events.end();
 814                                 --penultimate; /* points at last point */
 815                                 --penultimate; /* points at the penultimate point */
 816
 817                                 if (_events.back()->value == (*penultimate)->value) {
 818                                         _events.back()->when = last_coordinate;
 819                                 } else {
 820                                         _events.push_back (new ControlEvent (last_coordinate, _events.back()->value));
 821                                 }
 822                         }
 823
 824                 } else {
 825
 826                         /* shortening end */
 827
 828                         last_val = unlocked_eval (last_coordinate);
 829                         last_val = max ((double) _min_yval, last_val);
 830                         last_val = min ((double) _max_yval, last_val);
 831
 832                         i = _events.rbegin();
 833
 834                         /* make i point to the last control point */
 835
 836                         ++i;
 837
 838                         /* now go backwards, removing control points that are
 839                            beyond the new last coordinate.
 840                         */
 841
 842                         // FIXME: SLOW! (size() == O(n))
 843
 844                         uint32_t sz = _events.size();
 845
 846                         while (i != _events.rend() && sz > 2) {
 847                                 ControlList::reverse_iterator tmp;
 848
 849                                 tmp = i;
 850                                 ++tmp;
 851
 852                                 if ((*i)->when < last_coordinate) {
 853                                         break;
 854                                 }
 855
 856                                 _events.erase (i.base());
 857                                 --sz;
 858
 859                                 i = tmp;
 860                         }
 861
 862                         _events.back()->when = last_coordinate;
 863                         _events.back()->value = last_val;
 864                 }
 865
 866                 mark_dirty();
 867         }
 868
 869         maybe_signal_changed ();
 870 }
 871
 872 void
 873 ControlList::truncate_start (double overall_length)
 874 {
 875         {
 876                 Glib::Mutex::Lock lm (_lock);
 877                 iterator i;
 878                 double first_legal_value;
 879                 double first_legal_coordinate;
 880
 881                 assert(!_events.empty());
 882
 883                 if (overall_length == _events.back()->when) {
 884                         /* no change in overall length */
 885                         return;
 886                 }
 887
 888                 if (overall_length > _events.back()->when) {
 889
 890                         /* growing at front: duplicate first point. shift all others */
 891
 892                         double shift = overall_length - _events.back()->when;
 893                         uint32_t np;
 894
 895                         for (np = 0, i = _events.begin(); i != _events.end(); ++i, ++np) {
 896                                 (*i)->when += shift;
 897                         }
 898
 899                         if (np < 2) {
 900
 901                                 /* less than 2 points: add a new point */
 902                                 _events.push_front (new ControlEvent (0, _events.front()->value));
 903
 904                         } else {
 905
 906                                 /* more than 2 points: check to see if the first 2 values
 907                                    are equal. if so, just move the position of the
 908                                    first point. otherwise, add a new point.
 909                                 */
 910
 911                                 iterator second = _events.begin();
 912                                 ++second; /* points at the second point */
 913
 914                                 if (_events.front()->value == (*second)->value) {
 915                                         /* first segment is flat, just move start point back to zero */
 916                                         _events.front()->when = 0;
 917                                 } else {
 918                                         /* leave non-flat segment in place, add a new leading point. */
 919                                         _events.push_front (new ControlEvent (0, _events.front()->value));
 920                                 }
 921                         }
 922
 923                 } else {
 924
 925                         /* shrinking at front */
 926
 927                         first_legal_coordinate = _events.back()->when - overall_length;
 928                         first_legal_value = unlocked_eval (first_legal_coordinate);
 929                         first_legal_value = max (_min_yval, first_legal_value);
 930                         first_legal_value = min (_max_yval, first_legal_value);
 931
 932                         /* remove all events earlier than the new "front" */
 933
 934                         i = _events.begin();
 935
 936                         while (i != _events.end() && !_events.empty()) {
 937                                 ControlList::iterator tmp;
 938
 939                                 tmp = i;
 940                                 ++tmp;
 941
 942                                 if ((*i)->when > first_legal_coordinate) {
 943                                         break;
 944                                 }
 945
 946                                 _events.erase (i);
 947
 948                                 i = tmp;
 949                         }
 950
 951
 952                         /* shift all remaining points left to keep their same
 953                            relative position
 954                         */
 955
 956                         for (i = _events.begin(); i != _events.end(); ++i) {
 957                                 (*i)->when -= first_legal_coordinate;
 958                         }
 959
 960                         /* add a new point for the interpolated new value */
 961
 962                         _events.push_front (new ControlEvent (0, first_legal_value));
 963                 }
 964
 965                 mark_dirty();
 966         }
 967
 968         maybe_signal_changed ();
 969 }
 970
 971 double
 972 ControlList::unlocked_eval (double x) const
 973 {
 974         pair<EventList::iterator,EventList::iterator> range;
 975         int32_t npoints;
 976         double lpos, upos;
 977         double lval, uval;
 978         double fraction;
 979
 980         const_iterator length_check_iter = _events.begin();
 981         for (npoints = 0; npoints < 4; ++npoints, ++length_check_iter) {
 982                 if (length_check_iter == _events.end()) {
 983                         break;
 984                 }
 985         }
 986
 987         switch (npoints) {
 988         case 0:
 989                 return _default_value;
 990
 991         case 1:
 992                 return _events.front()->value;
 993
 994         case 2:
 995                 if (x >= _events.back()->when) {
 996                         return _events.back()->value;
 997                 } else if (x <= _events.front()->when) {
 998                         return _events.front()->value;
 999                 }
1000
1001                 lpos = _events.front()->when;
1002                 lval = _events.front()->value;
1003                 upos = _events.back()->when;
1004                 uval = _events.back()->value;
1005
1006                 if (_interpolation == Discrete) {
1007                         return lval;
1008                 }
1009
1010                 /* linear interpolation betweeen the two points */
1011                 fraction = (double) (x - lpos) / (double) (upos - lpos);
1012                 return lval + (fraction * (uval - lval));
1013
1014         default:
1015                 if (x >= _events.back()->when) {
1016                         return _events.back()->value;
1017                 } else if (x <= _events.front()->when) {
1018                         return _events.front()->value;
1019                 }
1020
1021                 return multipoint_eval (x);
1022         }
1023
1024         /*NOTREACHED*/ /* stupid gcc */
1025         return _default_value;
1026 }
1027
1028 double
1029 ControlList::multipoint_eval (double x) const
1030 {
1031         double upos, lpos;
1032         double uval, lval;
1033         double fraction;
1034
1035         /* "Stepped" lookup (no interpolation) */
1036         /* FIXME: no cache.  significant? */
1037         if (_interpolation == Discrete) {
1038                 const ControlEvent cp (x, 0);
1039                 EventList::const_iterator i = lower_bound (_events.begin(), _events.end(), &cp, time_comparator);
1040
1041                 // shouldn't have made it to multipoint_eval
1042                 assert(i != _events.end());
1043
1044                 if (i == _events.begin() || (*i)->when == x)
1045                         return (*i)->value;
1046                 else
1047                         return (*(--i))->value;
1048         }
1049
1050         /* Only do the range lookup if x is in a different range than last time
1051          * this was called (or if the lookup cache has been marked "dirty" (left<0) */
1052         if ((_lookup_cache.left < 0) ||
1053             ((_lookup_cache.left > x) ||
1054              (_lookup_cache.range.first == _events.end()) ||
1055              ((*_lookup_cache.range.second)->when < x))) {
1056
1057                 const ControlEvent cp (x, 0);
1058
1059                 _lookup_cache.range = equal_range (_events.begin(), _events.end(), &cp, time_comparator);
1060         }
1061
1062         pair<const_iterator,const_iterator> range = _lookup_cache.range;
1063
1064         if (range.first == range.second) {
1065
1066                 /* x does not exist within the list as a control point */
1067
1068                 _lookup_cache.left = x;
1069
1070                 if (range.first != _events.begin()) {
1071                         --range.first;
1072                         lpos = (*range.first)->when;
1073                         lval = (*range.first)->value;
1074                 }  else {
1075                         /* we're before the first point */
1076                         // return _default_value;
1077                         return _events.front()->value;
1078                 }
1079
1080                 if (range.second == _events.end()) {
1081                         /* we're after the last point */
1082                         return _events.back()->value;
1083                 }
1084
1085                 upos = (*range.second)->when;
1086                 uval = (*range.second)->value;
1087
1088                 /* linear interpolation betweeen the two points
1089                    on either side of x
1090                 */
1091
1092                 fraction = (double) (x - lpos) / (double) (upos - lpos);
1093                 return lval + (fraction * (uval - lval));
1094
1095         }
1096
1097         /* x is a control point in the data */
1098         _lookup_cache.left = -1;
1099         return (*range.first)->value;
1100 }
1101
1102 void
1103 ControlList::build_search_cache_if_necessary (double start) const
1104 {
1105         /* Only do the range lookup if x is in a different range than last time
1106          * this was called (or if the search cache has been marked "dirty" (left<0) */
1107         if (!_events.empty() && ((_search_cache.left < 0) || (_search_cache.left > start))) {
1108
1109                 const ControlEvent start_point (start, 0);
1110
1111                 //cerr << "REBUILD: (" << _search_cache.left << ".." << _search_cache.right << ") := ("
1112                 //      << start << ".." << end << ")" << endl;
1113
1114                 _search_cache.first = lower_bound (_events.begin(), _events.end(), &start_point, time_comparator);
1115                 _search_cache.left = start;
1116         }
1117 }
1118
1119 /** Get the earliest event after \a start using the current interpolation style.
1120  *
1121  * If an event is found, \a x and \a y are set to its coordinates.
1122  *
1123  * \param inclusive Include events with timestamp exactly equal to \a start
1124  * \return true if event is found (and \a x and \a y are valid).
1125  */
1126 bool
1127 ControlList::rt_safe_earliest_event (double start, double& x, double& y, bool inclusive) const
1128 {
1129         // FIXME: It would be nice if this was unnecessary..
1130         Glib::Mutex::Lock lm(_lock, Glib::TRY_LOCK);
1131         if (!lm.locked()) {
1132                 return false;
1133         }
1134
1135         return rt_safe_earliest_event_unlocked (start, x, y, inclusive);
1136 }
1137
1138
1139 /** Get the earliest event after \a start using the current interpolation style.
1140  *
1141  * If an event is found, \a x and \a y are set to its coordinates.
1142  *
1143  * \param inclusive Include events with timestamp exactly equal to \a start
1144  * \return true if event is found (and \a x and \a y are valid).
1145  */
1146 bool
1147 ControlList::rt_safe_earliest_event_unlocked (double start, double& x, double& y, bool inclusive) const
1148 {
1149         if (_interpolation == Discrete) {
1150                 return rt_safe_earliest_event_discrete_unlocked(start, x, y, inclusive);
1151         } else {
1152                 return rt_safe_earliest_event_linear_unlocked(start, x, y, inclusive);
1153         }
1154 }
1155
1156
1157 /** Get the earliest event after \a start without interpolation.
1158  *
1159  * If an event is found, \a x and \a y are set to its coordinates.
1160  *
1161  * \param inclusive Include events with timestamp exactly equal to \a start
1162  * \return true if event is found (and \a x and \a y are valid).
1163  */
1164 bool
1165 ControlList::rt_safe_earliest_event_discrete_unlocked (double start, double& x, double& y, bool inclusive) const
1166 {
1167         build_search_cache_if_necessary (start);
1168
1169         if (_search_cache.first != _events.end()) {
1170                 const ControlEvent* const first = *_search_cache.first;
1171
1172                 const bool past_start = (inclusive ? first->when >= start : first->when > start);
1173
1174                 /* Earliest points is in range, return it */
1175                 if (past_start) {
1176
1177                         x = first->when;
1178                         y = first->value;
1179
1180                         /* Move left of cache to this point
1181                          * (Optimize for immediate call this cycle within range) */
1182                         _search_cache.left = x;
1183                         ++_search_cache.first;
1184
1185                         assert(x >= start);
1186                         return true;
1187
1188                 } else {
1189                         return false;
1190                 }
1191
1192                 /* No points in range */
1193         } else {
1194                 return false;
1195         }
1196 }
1197
1198 /** Get the earliest time the line crosses an integer (Linear interpolation).
1199  *
1200  * If an event is found, \a x and \a y are set to its coordinates.
1201  *
1202  * \param inclusive Include events with timestamp exactly equal to \a start
1203  * \return true if event is found (and \a x and \a y are valid).
1204  */
1205 bool
1206 ControlList::rt_safe_earliest_event_linear_unlocked (double start, double& x, double& y, bool inclusive) const
1207 {
1208         // cout << "earliest_event(start: " << start << ", x: " << x << ", y: " << y << ", inclusive: " << inclusive <<  ")" << endl;
1209
1210         const_iterator length_check_iter = _events.begin();
1211         if (_events.empty()) { // 0 events
1212                 return false;
1213         } else if (_events.end() == ++length_check_iter) { // 1 event
1214                 return rt_safe_earliest_event_discrete_unlocked (start, x, y, inclusive);
1215         }
1216
1217         // Hack to avoid infinitely repeating the same event
1218         build_search_cache_if_necessary (start);
1219
1220         if (_search_cache.first != _events.end()) {
1221
1222                 const ControlEvent* first = NULL;
1223                 const ControlEvent* next = NULL;
1224
1225                 /* Step is after first */
1226                 if (_search_cache.first == _events.begin() || (*_search_cache.first)->when <= start) {
1227                         first = *_search_cache.first;
1228                         ++_search_cache.first;
1229                         if (_search_cache.first == _events.end()) {
1230                                 return false;
1231                         }
1232                         next = *_search_cache.first;
1233
1234                         /* Step is before first */
1235                 } else {
1236                         const_iterator prev = _search_cache.first;
1237                         --prev;
1238                         first = *prev;
1239                         next = *_search_cache.first;
1240                 }
1241
1242                 if (inclusive && first->when == start) {
1243                         x = first->when;
1244                         y = first->value;
1245                         /* Move left of cache to this point
1246                          * (Optimize for immediate call this cycle within range) */
1247                         _search_cache.left = x;
1248                         //++_search_cache.range.first;
1249                         assert(x >= start);
1250                         return true;
1251                 }
1252
1253                 if (fabs(first->value - next->value) <= 1) {
1254                         if (next->when > start) {
1255                                 x = next->when;
1256                                 y = next->value;
1257                                 /* Move left of cache to this point
1258                                  * (Optimize for immediate call this cycle within range) */
1259                                 _search_cache.left = x;
1260                                 //++_search_cache.range.first;
1261                                 assert(inclusive ? x >= start : x > start);
1262                                 return true;
1263                         } else {
1264                                 return false;
1265                         }
1266                 }
1267
1268                 const double slope = (next->value - first->value) / (double)(next->when - first->when);
1269                 //cerr << "start y: " << start_y << endl;
1270
1271                 //y = first->value + (slope * fabs(start - first->when));
1272                 y = first->value;
1273
1274                 if (first->value < next->value) // ramping up
1275                         y = ceil(y);
1276                 else // ramping down
1277                         y = floor(y);
1278
1279                 x = first->when + (y - first->value) / (double)slope;
1280
1281                 while ((inclusive && x < start) || (x <= start && y != next->value)) {
1282
1283                         if (first->value < next->value) // ramping up
1284                                 y += 1.0;
1285                         else // ramping down
1286                                 y -= 1.0;
1287
1288                         x = first->when + (y - first->value) / (double)slope;
1289                 }
1290
1291                 /*cerr << first->value << " @ " << first->when << " ... "
1292                   << next->value << " @ " << next->when
1293                   << " = " << y << " @ " << x << endl;*/
1294
1295                 assert(    (y >= first->value && y <= next->value)
1296                            || (y <= first->value && y >= next->value) );
1297
1298
1299                 const bool past_start = (inclusive ? x >= start : x > start);
1300                 if (past_start) {
1301                         /* Move left of cache to this point
1302                          * (Optimize for immediate call this cycle within range) */
1303                         _search_cache.left = x;
1304                         assert(inclusive ? x >= start : x > start);
1305                         return true;
1306                 } else {
1307                         return false;
1308                 }
1309
1310                 /* No points in the future, so no steps (towards them) in the future */
1311         } else {
1312                 return false;
1313         }
1314 }
1315
1316
1317 /** @param start Start position in model coordinates.
1318  *  @param end End position in model coordinates.
1319  *  @param op 0 = cut, 1 = copy, 2 = clear.
1320  */
1321 boost::shared_ptr<ControlList>
1322 ControlList::cut_copy_clear (double start, double end, int op)
1323 {
1324         boost::shared_ptr<ControlList> nal = create (_parameter);
1325         iterator s, e;
1326         ControlEvent cp (start, 0.0);
1327
1328         {
1329                 Glib::Mutex::Lock lm (_lock);
1330
1331                 /* first, determine s & e, two iterators that define the range of points
1332                    affected by this operation
1333                 */
1334
1335                 if ((s = lower_bound (_events.begin(), _events.end(), &cp, time_comparator)) == _events.end()) {
1336                         return nal;
1337                 }
1338
1339                 /* and the last that is at or after `end' */
1340                 cp.when = end;
1341                 e = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
1342
1343
1344                 /* if "start" isn't the location of an existing point,
1345                    evaluate the curve to get a value for the start. Add a point to
1346                    both the existing event list, and if its not a "clear" operation,
1347                    to the copy ("nal") as well.
1348
1349                    Note that the time positions of the points in each list are different
1350                    because we want the copy ("nal") to have a zero time reference.
1351                 */
1352
1353
1354                 /* before we begin any cut/clear operations, get the value of the curve
1355                    at "end".
1356                 */
1357
1358                 double end_value = unlocked_eval (end);
1359
1360                 if ((*s)->when != start) {
1361
1362                         double val = unlocked_eval (start);
1363
1364                         if (op == 0) { // cut
1365                                 if (start > _events.front()->when) {
1366                                         _events.insert (s, (new ControlEvent (start, val)));
1367                                 }
1368                         }
1369
1370                         if (op != 2) { // ! clear
1371                                 nal->_events.push_back (new ControlEvent (0, val));
1372                         }
1373                 }
1374
1375                 for (iterator x = s; x != e; ) {
1376
1377                         /* adjust new points to be relative to start, which
1378                            has been set to zero.
1379                         */
1380
1381                         if (op != 2) {
1382                                 nal->_events.push_back (new ControlEvent ((*x)->when - start, (*x)->value));
1383                         }
1384
1385                         if (op != 1) {
1386                                 x = _events.erase (x);
1387                         } else {
1388                                 ++x;
1389                         }
1390                 }
1391
1392                 if (e == _events.end() || (*e)->when != end) {
1393
1394                         /* only add a boundary point if there is a point after "end"
1395                          */
1396
1397                         if (op == 0 && (e != _events.end() && end < (*e)->when)) { // cut
1398                                 _events.insert (e, new ControlEvent (end, end_value));
1399                         }
1400
1401                         if (op != 2 && (e != _events.end() && end < (*e)->when)) { // cut/copy
1402                                 nal->_events.push_back (new ControlEvent (end - start, end_value));
1403                         }
1404                 }
1405
1406                 mark_dirty ();
1407         }
1408
1409         if (op != 1) {
1410                 maybe_signal_changed ();
1411         }
1412
1413         return nal;
1414 }
1415
1416
1417 boost::shared_ptr<ControlList>
1418 ControlList::cut (double start, double end)
1419 {
1420         return cut_copy_clear (start, end, 0);
1421 }
1422
1423 boost::shared_ptr<ControlList>
1424 ControlList::copy (double start, double end)
1425 {
1426         return cut_copy_clear (start, end, 1);
1427 }
1428
1429 void
1430 ControlList::clear (double start, double end)
1431 {
1432         cut_copy_clear (start, end, 2);
1433 }
1434
1435 /** @param pos Position in model coordinates */
1436 bool
1437 ControlList::paste (ControlList& alist, double pos, float /*times*/)
1438 {
1439         if (alist._events.empty()) {
1440                 return false;
1441         }
1442
1443         {
1444                 Glib::Mutex::Lock lm (_lock);
1445                 iterator where;
1446                 iterator prev;
1447                 double end = 0;
1448                 ControlEvent cp (pos, 0.0);
1449
1450                 where = upper_bound (_events.begin(), _events.end(), &cp, time_comparator);
1451
1452                 for (iterator i = alist.begin();i != alist.end(); ++i) {
1453                         _events.insert (where, new ControlEvent( (*i)->when+pos,( *i)->value));
1454                         end = (*i)->when + pos;
1455                 }
1456
1457
1458                 /* move all  points after the insertion along the timeline by
1459                    the correct amount.
1460                 */
1461
1462                 while (where != _events.end()) {
1463                         iterator tmp;
1464                         if ((*where)->when <= end) {
1465                                 tmp = where;
1466                                 ++tmp;
1467                                 _events.erase(where);
1468                                 where = tmp;
1469
1470                         } else {
1471                                 break;
1472                         }
1473                 }
1474
1475                 mark_dirty ();
1476         }
1477
1478         maybe_signal_changed ();
1479         return true;
1480 }
1481
1482 /** Move automation around according to a list of region movements.
1483  *  @param return true if anything was changed, otherwise false (ie nothing needed changing)
1484  */
1485 bool
1486 ControlList::move_ranges (const list< RangeMove<double> >& movements)
1487 {
1488         typedef list< RangeMove<double> > RangeMoveList;
1489
1490         {
1491                 Glib::Mutex::Lock lm (_lock);
1492
1493                 /* a copy of the events list before we started moving stuff around */
1494                 EventList old_events = _events;
1495
1496                 /* clear the source and destination ranges in the new list */
1497                 bool things_erased = false;
1498                 for (RangeMoveList::const_iterator i = movements.begin (); i != movements.end (); ++i) {
1499
1500                         if (erase_range_internal (i->from, i->from + i->length, _events)) {
1501                                 things_erased = true;
1502                         }
1503
1504                         if (erase_range_internal (i->to, i->to + i->length, _events)) {
1505                                 things_erased = true;
1506                         }
1507                 }
1508
1509                 /* if nothing was erased, there is nothing to do */
1510                 if (!things_erased) {
1511                         return false;
1512                 }
1513
1514                 /* copy the events into the new list */
1515                 for (RangeMoveList::const_iterator i = movements.begin (); i != movements.end (); ++i) {
1516                         iterator j = old_events.begin ();
1517                         const double limit = i->from + i->length;
1518                         const double dx    = i->to - i->from;
1519                         while (j != old_events.end () && (*j)->when <= limit) {
1520                                 if ((*j)->when >= i->from) {
1521                                         ControlEvent* ev = new ControlEvent (**j);
1522                                         ev->when += dx;
1523                                         _events.push_back (ev);
1524                                 }
1525                                 ++j;
1526                         }
1527                 }
1528
1529                 if (!_frozen) {
1530                         _events.sort (event_time_less_than);
1531                 } else {
1532                         _sort_pending = true;
1533                 }
1534
1535                 mark_dirty ();
1536         }
1537
1538         maybe_signal_changed ();
1539         return true;
1540 }
1541
1542 void
1543 ControlList::set_interpolation (InterpolationStyle s)
1544 {
1545         if (_interpolation == s) {
1546                 return;
1547         }
1548
1549         _interpolation = s;
1550         InterpolationChanged (s); /* EMIT SIGNAL */
1551 }
1552
1553 } // namespace Evoral
1554