# HG changeset patch
# User Chris Cannam
# Date 1553080374 0
# Node ID 26aa42fd60e93af4f59e08827875a71c69da154e
# Parent  eaad709398482af54216a3efb97652ab7bda4bd8
Add overspill to events-within search

diff -r eaad70939848 -r 26aa42fd60e9 base/EventSeries.cpp
--- a/base/EventSeries.cpp	Tue Mar 19 14:24:05 2019 +0000
+++ b/base/EventSeries.cpp	Wed Mar 20 11:12:54 2019 +0000
@@ -273,28 +273,52 @@
 
 EventVector
 EventSeries::getEventsWithin(sv_frame_t frame,
-                             sv_frame_t duration) const
+                             sv_frame_t duration,
+                             int overspill) const
 {
     EventVector span;
     
     const sv_frame_t start = frame;
     const sv_frame_t end = frame + duration;
 
-    // because we don't need to "look back" at events that started
-    // earlier than the start of the given range, we can do this
-    // entirely from m_events
+    // because we don't need to "look back" at events that end within
+    // but started without, we can do this entirely from m_events.
+    // The core operation is very simple, it's just overspill that
+    // complicates it.
 
-    auto pitr = lower_bound(m_events.begin(), m_events.end(),
-                            Event(start));
+    Events::const_iterator reference = 
+        lower_bound(m_events.begin(), m_events.end(), Event(start));
+
+    Events::const_iterator first = reference;
+    for (int i = 0; i < overspill; ++i) {
+        if (first == m_events.begin()) break;
+        --first;
+    }
+    for (int i = 0; i < overspill; ++i) {
+        if (first == reference) break;
+        span.push_back(*first);
+        ++first;
+    }
+
+    Events::const_iterator pitr = reference;
+    Events::const_iterator last = reference;
+
     while (pitr != m_events.end() && pitr->getFrame() < end) {
-        if (!pitr->hasDuration()) {
+        if (!pitr->hasDuration() ||
+            (pitr->getFrame() + pitr->getDuration() <= end)) {
             span.push_back(*pitr);
-        } else if (pitr->getFrame() + pitr->getDuration() <= end) {
-            span.push_back(*pitr);
+            last = pitr;
+            ++last;
         }
         ++pitr;
     }
-            
+
+    for (int i = 0; i < overspill; ++i) {
+        if (last == m_events.end()) break;
+        span.push_back(*last);
+        ++last;
+    }
+    
     return span;
 }
 
diff -r eaad70939848 -r 26aa42fd60e9 base/EventSeries.h
--- a/base/EventSeries.h	Tue Mar 19 14:24:05 2019 +0000
+++ b/base/EventSeries.h	Wed Mar 20 11:12:54 2019 +0000
@@ -102,9 +102,14 @@
      * - An event with duration is within the range if its start frame
      * is greater than or equal to f and its start frame plus its
      * duration is less than or equal to f + d.
+     *
+     * If overspill is greater than zero, also include that number of
+     * additional events (where they exist) both before and after the
+     * edges of the range.
      */
     EventVector getEventsWithin(sv_frame_t frame,
-                                sv_frame_t duration) const;
+                                sv_frame_t duration,
+                                int overspill = 0) const;
 
     /**
      * Retrieve all events starting within the range in frames defined
diff -r eaad70939848 -r 26aa42fd60e9 base/test/TestEventSeries.h
--- a/base/test/TestEventSeries.h	Tue Mar 19 14:24:05 2019 +0000
+++ b/base/test/TestEventSeries.h	Wed Mar 20 11:12:54 2019 +0000
@@ -468,6 +468,36 @@
         QCOMPARE(s.getEventsWithin(2, 7), EventVector({ b, c, cc }));
     }
 
+    void eventPatternWithinWithOverspill() {
+
+        EventSeries s;
+        Event a(0, 1.0f, 18, QString("a"));
+        Event b(3, 2.0f, 6, QString("b"));
+        Event c(5, 3.0f, 2, QString("c"));
+        Event cc(5, 3.1f, 2, QString("cc"));
+        Event d(6, 4.0f, 10, QString("d"));
+        Event dd(6, 4.5f, 10, QString("dd"));
+        Event e(14, 5.0f, 3, QString("e"));
+        s.add(b);
+        s.add(c);
+        s.add(d);
+        s.add(a);
+        s.add(cc);
+        s.add(dd);
+        s.add(e);
+        QCOMPARE(s.getEventsWithin(0, 0, 0), EventVector());
+        QCOMPARE(s.getEventsWithin(0, 0, 1), EventVector({ a }));
+        QCOMPARE(s.getEventsWithin(0, 0, 2), EventVector({ a, b }));
+        QCOMPARE(s.getEventsWithin(20, 1, 0), EventVector());
+        QCOMPARE(s.getEventsWithin(20, 1, 1), EventVector({ e }));
+        QCOMPARE(s.getEventsWithin(20, 1, 2), EventVector({ dd, e }));
+        QCOMPARE(s.getEventsWithin(2, 7, 0), EventVector({ b, c, cc }));
+        QCOMPARE(s.getEventsWithin(2, 7, 1), EventVector({ a, b, c, cc, d }));
+        QCOMPARE(s.getEventsWithin(2, 7, 2), EventVector({ a, b, c, cc, d, dd }));
+        QCOMPARE(s.getEventsWithin(2, 7, 3), EventVector({ a, b, c, cc, d, dd, e }));
+        QCOMPARE(s.getEventsWithin(2, 7, 4), EventVector({ a, b, c, cc, d, dd, e }));
+    }
+
     void eventPatternStartingWithin() {
 
         EventSeries s;
@@ -623,7 +653,7 @@
         EventSeries s;
         Event p;
         QCOMPARE(s.getNearestEventMatching
-                 (6, [](const Event &e) { return e.getDuration() < 4; },
+                 (6, [](Event e) { return e.getDuration() < 4; },
                   EventSeries::Forward, p), false);
         Event a(0, 1.0f, 18, QString("a"));
         Event b(3, 2.0f, 6, QString("b"));
@@ -641,19 +671,19 @@
         s.add(dd);
         s.add(e);
         QCOMPARE(s.getNearestEventMatching
-                 (0, [](const Event &e) { return e.getDuration() < 4; },
+                 (0, [](Event e) { return e.getDuration() < 4; },
                   EventSeries::Forward, p), true);
         QCOMPARE(p, c);
         QCOMPARE(s.getNearestEventMatching
-                 (6, [](const Event &e) { return e.getDuration() < 4; },
+                 (6, [](Event e) { return e.getDuration() < 4; },
                   EventSeries::Forward, p), true);
         QCOMPARE(p, e);
         QCOMPARE(s.getNearestEventMatching
-                 (6, [](const Event &e) { return e.getDuration() > 4; },
+                 (6, [](Event e) { return e.getDuration() > 4; },
                   EventSeries::Forward, p), true);
         QCOMPARE(p, d);
         QCOMPARE(s.getNearestEventMatching
-                 (20, [](const Event &e) { return e.getDuration() > 4; },
+                 (20, [](Event e) { return e.getDuration() > 4; },
                   EventSeries::Forward, p), false);
     }
     
@@ -662,7 +692,7 @@
         EventSeries s;
         Event p;
         QCOMPARE(s.getNearestEventMatching
-                 (6, [](const Event &e) { return e.getDuration() < 4; },
+                 (6, [](Event e) { return e.getDuration() < 4; },
                   EventSeries::Backward, p), false);
         Event a(0, 1.0f, 18, QString("a"));
         Event b(3, 2.0f, 6, QString("b"));
@@ -680,14 +710,14 @@
         s.add(dd);
         s.add(e);
         QCOMPARE(s.getNearestEventMatching
-                 (0, [](const Event &e) { return e.getDuration() < 4; },
+                 (0, [](Event e) { return e.getDuration() < 4; },
                   EventSeries::Backward, p), false);
         QCOMPARE(s.getNearestEventMatching
-                 (6, [](const Event &e) { return e.getDuration() > 4; },
+                 (6, [](Event e) { return e.getDuration() > 4; },
                   EventSeries::Backward, p), true);
         QCOMPARE(p, b);
         QCOMPARE(s.getNearestEventMatching
-                 (20, [](const Event &e) { return e.getDuration() > 4; },
+                 (20, [](Event e) { return e.getDuration() > 4; },
                   EventSeries::Backward, p), true);
         QCOMPARE(p, dd);
     }