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