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