libs/evoral/src/ControlList.cpp

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