Mercurial > hg > svcore
changeset 1616:de446dd905e6 single-point
Rework EventSeries to explicitly store counts of events (+ add comments explaining, among other things, why)
| author | Chris Cannam |
|---|---|
| date | Fri, 08 Mar 2019 10:16:12 +0000 |
| parents | 24dc8cb42755 |
| children | bdc19a09a1f9 |
| files | base/EventSeries.h base/test/TestEventSeries.h |
| diffstat | 2 files changed, 347 insertions(+), 140 deletions(-) [+] |
line wrap: on
line diff
--- a/base/EventSeries.h Thu Mar 07 15:44:09 2019 +0000 +++ b/base/EventSeries.h Fri Mar 08 10:16:12 2019 +0000 @@ -23,21 +23,33 @@ /** * Container storing a series of events, with or without durations, - * and supporting the ability to query which events span a given frame - * time. To that end, in addition to the series of events, it stores a - * series of "seam points", which are the frame positions at which the - * set of simultaneous events changes (i.e. an event of non-zero - * duration starts or ends). These are updated when event is added or - * removed. + * and supporting the ability to query which events are active at a + * given frame or within a span of frames. + * + * To that end, in addition to the series of events, it stores a + * series of "seams", which are frame positions at which the set of + * simultaneous events changes (i.e. an event of non-zero duration + * starts or ends) associated with a set of the events that are active + * at or from that position. These are updated when an event is added + * or removed. */ class EventSeries { public: EventSeries() : m_count(0) { } + ~EventSeries() =default; + + EventSeries(const EventSeries &) =default; + EventSeries &operator=(const EventSeries &) =default; + EventSeries &operator=(EventSeries &&) =default; + + bool operator==(const EventSeries &other) const { + return m_events == other.m_events; + } void add(const Event &p) { - m_events.insert(p); + ++m_events[p]; ++m_count; if (p.hasDuration()) { @@ -46,9 +58,10 @@ createSeam(frame); createSeam(endFrame); - - auto i0 = m_seams.find(frame); // must succeed after createSeam - auto i1 = m_seams.find(endFrame); // likewise + + // These calls must both succeed after calling createSeam above + const auto i0 = m_seams.find(frame); + const auto i1 = m_seams.find(endFrame); for (auto i = i0; i != i1; ++i) { if (i == m_seams.end()) { @@ -70,23 +83,29 @@ void remove(const Event &p) { - // erase first itr that matches p; if there is more than one - // p, erase(p) would remove all of them, but we only want to - // remove (any) one + // If we are removing the last (unique) example of an event, + // then we also need to remove it from the seam map. If this + // is only one of multiple identical events, then we don't. + bool isUnique = false; + auto pitr = m_events.find(p); if (pitr == m_events.end()) { return; // we don't know this event } else { - m_events.erase(pitr); + if (--(pitr->second) == 0) { + isUnique = true; + m_events.erase(pitr); + } --m_count; } - if (p.hasDuration()) { + if (p.hasDuration() && isUnique) { + sv_frame_t frame = p.getFrame(); sv_frame_t endFrame = p.getFrame() + p.getDuration(); - auto i0 = m_seams.find(frame); - auto i1 = m_seams.find(endFrame); + const auto i0 = m_seams.find(frame); + const auto i1 = m_seams.find(endFrame); #ifdef DEBUG_EVENT_SERIES // This should be impossible if we found p in m_events above @@ -101,27 +120,37 @@ for (auto i = i0; i != i1; ++i) { if (i == m_seams.end()) { // This can happen only if we have a negative - // duration, which Event forbids, but we don't - // protect against it in this class, so we'll - // leave this check in - SVCERR << "ERROR: EventSeries::remove: " - << "reached end of seam map" - << endl; + // duration, which Event forbids + throw std::logic_error("unexpectedly reached end of map"); + } + + i->second.erase(p); + } + + // Tidy up by removing any entries that are now identical + // to their predecessors + + std::vector<sv_frame_t> redundant; + + auto pitr = m_seams.end(); + if (i0 != m_seams.begin()) { + pitr = i0; + --pitr; + } + + for (auto i = i0; i != m_seams.end(); ++i) { + if (pitr != m_seams.end() && i->second == pitr->second) { + redundant.push_back(i->first); + } + pitr = i; + if (i == i1) { break; } - // Can't just erase(p) as that would erase all of - // them, if there are several identical ones - auto si = i->second.find(p); - if (si != i->second.end()) { - i->second.erase(si); - } } - // Shall we "garbage-collect" here? We could be leaving - // lots of empty event-sets, or consecutive identical - // ones, which are a pure irrelevance that take space and - // slow us down. But a lot depends on whether callers ever - // really delete anything much. + for (sv_frame_t f: redundant) { + m_seams.erase(f); + } } #ifdef DEBUG_EVENT_SERIES @@ -150,27 +179,91 @@ } /** - * Retrieve all events that span the given frame. A event without - * duration spans a frame if its own frame is equal to it. A event - * with duration spans a frame if its start frame is less than or + * Retrieve all events any part of which falls within the span in + * frames defined by the given frame f and duration d. + * + * - An event without duration is within the span if its own frame + * is greater than or equal to f and less than f + d. + * + * - An event with duration is within the span if its start frame + * is less than f + d and its start frame plus its duration is + * greater than f. + * + * Note that getEventsSpanning(f, 0) is not equivalent to + * getEventsCovering(f) - they have different behaviour in the + * case of events starting exactly at f, which are included in the + * latter but not the former. + */ + EventVector getEventsSpanning(sv_frame_t f, sv_frame_t d) const { + EventVector span; + + sv_frame_t start = f; + sv_frame_t end = f + d; + + // first find any zero-duration events + + auto pitr = m_events.lower_bound(Event(start, QString())); + while (pitr != m_events.end() && pitr->first.getFrame() < end) { + if (!pitr->first.hasDuration()) { + for (int i = 0; i < pitr->second; ++i) { + span.push_back(pitr->first); + } + } + ++pitr; + } + + // now any non-zero-duration ones from the seam map + + std::set<Event> found; + auto sitr = m_seams.lower_bound(start); + if (sitr == m_seams.end() || sitr->first > start) { + if (sitr != m_seams.begin()) { + --sitr; + } + } + while (sitr != m_seams.end() && sitr->first < end) { + for (const auto &p: sitr->second) { + found.insert(p); + } + ++sitr; + } + for (const auto &p: found) { + int n = m_events.at(p); + if (n < 1) { + throw std::logic_error("event is in seams but not events"); + } + for (int i = 0; i < n; ++i) { + span.push_back(p); + } + } + + return span; + } + + /** + * Retrieve all events that cover the given frame. An event without + * duration covers a frame if its own frame is equal to it. An event + * with duration covers a frame if its start frame is less than or * equal to it and its end frame (start + duration) is greater * than it. */ - EventVector getEventsSpanning(sv_frame_t frame) const { - EventVector span; + EventVector getEventsCovering(sv_frame_t frame) const { + EventVector cover; // first find any zero-duration events + auto pitr = m_events.lower_bound(Event(frame, QString())); - if (pitr != m_events.end()) { - while (pitr->getFrame() == frame) { - if (!pitr->hasDuration()) { - span.push_back(*pitr); + while (pitr != m_events.end() && pitr->first.getFrame() == frame) { + if (!pitr->first.hasDuration()) { + for (int i = 0; i < pitr->second; ++i) { + cover.push_back(pitr->first); } - ++pitr; } + ++pitr; } // now any non-zero-duration ones from the seam map + auto sitr = m_seams.lower_bound(frame); if (sitr == m_seams.end() || sitr->first > frame) { if (sitr != m_seams.begin()) { @@ -178,22 +271,58 @@ } } if (sitr != m_seams.end() && sitr->first <= frame) { - for (auto p: sitr->second) { - span.push_back(p); + for (const auto &p: sitr->second) { + int n = m_events.at(p); + if (n < 1) { + throw std::logic_error("event is in seams but not events"); + } + for (int i = 0; i < n; ++i) { + cover.push_back(p); + } } } - return span; + return cover; } private: + /** + * Total number of events in the series. Will exceed + * m_events.size() if the series contains duplicate events. + */ int m_count; - typedef std::multiset<Event> EventMultiset; - EventMultiset m_events; + /** + * The (ordered) Events map acts as a list of all the events in + * the series. For reasons of backward compatibility, we have to + * handle series containing multiple instances of identical + * events; the int indexed against each event records the number + * of instances of that event. We do this in preference to using a + * multiset, in order to support the case in which we have + * obtained a set of distinct events (from the seam container + * below) and then need to return the correct number of each. + * + * Because events are immutable, we never have to move one to a + * different "key" in this map - we only add or delete them or + * change their counts. + */ + typedef std::map<Event, int> Events; + Events m_events; - typedef std::map<sv_frame_t, std::multiset<Event>> FrameEventsMap; - FrameEventsMap m_seams; + /** + * The FrameEventMap maps from frame number to a set of events. In + * the seam map this is used to represent the events that are + * active at that frame, either because they begin at that frame + * or because they are continuing from an earlier frame. There is + * an entry here for each frame at which an event starts or ends, + * with the event appearing in all entries from its start time + * onward and disappearing again at its end frame. + * + * Only events with duration appear in this map; point events + * appear only in m_events. + */ + typedef std::map<sv_frame_t, std::set<Event>> FrameEventMap; + FrameEventMap m_seams; /** Create a seam at the given frame, copying from the prior seam * if there is one. If a seam already exists at the given frame, @@ -218,8 +347,8 @@ #ifdef DEBUG_EVENT_SERIES void dumpEvents() const { std::cerr << "EVENTS [" << std::endl; - for (const auto &p: m_events) { - std::cerr << p.toXmlString(" "); + for (const auto &i: m_events) { + std::cerr << i.first.toXmlString(" "); } std::cerr << "]" << std::endl; }
--- a/base/test/TestEventSeries.h Thu Mar 07 15:44:09 2019 +0000 +++ b/base/test/TestEventSeries.h Fri Mar 08 10:16:12 2019 +0000 @@ -37,7 +37,7 @@ Event p(10, QString()); QCOMPARE(s.contains(p), false); - QCOMPARE(s.getEventsSpanning(400), EventVector()); + QCOMPARE(s.getEventsCovering(400), EventVector()); } void singleEvent() { @@ -51,83 +51,120 @@ s.remove(p); QCOMPARE(s.isEmpty(), true); + QCOMPARE(s.count(), 0); QCOMPARE(s.contains(p), false); } - void singleEventSpan() { + void duplicateEvents() { EventSeries s; Event p(10, QString()); s.add(p); - EventVector span; - span.push_back(p); - QCOMPARE(s.getEventsSpanning(10), span); - QCOMPARE(s.getEventsSpanning(11), EventVector()); - QCOMPARE(s.getEventsSpanning(9), EventVector()); + s.add(p); + QCOMPARE(s.isEmpty(), false); + QCOMPARE(s.count(), 2); + QCOMPARE(s.contains(p), true); + + s.remove(p); + QCOMPARE(s.isEmpty(), false); + QCOMPARE(s.count(), 1); + QCOMPARE(s.contains(p), true); + + s.remove(p); + QCOMPARE(s.isEmpty(), true); + QCOMPARE(s.count(), 0); + QCOMPARE(s.contains(p), false); } - void singleEventWithDurationSpan() { + void singleEventCover() { + + EventSeries s; + Event p(10, QString()); + s.add(p); + EventVector cover; + cover.push_back(p); + QCOMPARE(s.getEventsCovering(10), cover); + QCOMPARE(s.getEventsCovering(11), EventVector()); + QCOMPARE(s.getEventsCovering(9), EventVector()); + } + + void similarEventsCover() { + + EventSeries s; + Event a(10, QString("a")); + Event b(10, QString("b")); + s.add(a); + s.add(b); + EventVector cover; + cover.push_back(a); + cover.push_back(b); + QCOMPARE(s.getEventsCovering(10), cover); + QCOMPARE(s.getEventsCovering(11), EventVector()); + QCOMPARE(s.getEventsCovering(9), EventVector()); + } + + void singleEventWithDurationCover() { EventSeries s; Event p(10, 1.0, 20, QString()); s.add(p); - EventVector span; - span.push_back(p); - QCOMPARE(s.getEventsSpanning(10), span); - QCOMPARE(s.getEventsSpanning(11), span); - QCOMPARE(s.getEventsSpanning(29), span); - QCOMPARE(s.getEventsSpanning(30), EventVector()); - QCOMPARE(s.getEventsSpanning(9), EventVector()); + EventVector cover; + cover.push_back(p); + QCOMPARE(s.getEventsCovering(10), cover); + QCOMPARE(s.getEventsCovering(11), cover); + QCOMPARE(s.getEventsCovering(29), cover); + QCOMPARE(s.getEventsCovering(30), EventVector()); + QCOMPARE(s.getEventsCovering(9), EventVector()); } - void identicalEventsSpan() { + void identicalEventsCover() { EventSeries s; Event p(10, QString()); s.add(p); s.add(p); - EventVector span; - span.push_back(p); - span.push_back(p); - QCOMPARE(s.getEventsSpanning(10), span); - QCOMPARE(s.getEventsSpanning(11), EventVector()); - QCOMPARE(s.getEventsSpanning(9), EventVector()); + EventVector cover; + cover.push_back(p); + cover.push_back(p); + QCOMPARE(s.getEventsCovering(10), cover); + QCOMPARE(s.getEventsCovering(11), EventVector()); + QCOMPARE(s.getEventsCovering(9), EventVector()); s.remove(p); - span.clear(); - span.push_back(p); - QCOMPARE(s.getEventsSpanning(10), span); - QCOMPARE(s.getEventsSpanning(11), EventVector()); - QCOMPARE(s.getEventsSpanning(9), EventVector()); + cover.clear(); + cover.push_back(p); + QCOMPARE(s.getEventsCovering(10), cover); + QCOMPARE(s.getEventsCovering(11), EventVector()); + QCOMPARE(s.getEventsCovering(9), EventVector()); } - void identicalEventsWithDurationSpan() { + void identicalEventsWithDurationCover() { EventSeries s; Event p(10, 1.0, 20, QString()); s.add(p); s.add(p); - EventVector span; - span.push_back(p); - span.push_back(p); - QCOMPARE(s.getEventsSpanning(10), span); - QCOMPARE(s.getEventsSpanning(11), span); - QCOMPARE(s.getEventsSpanning(29), span); - QCOMPARE(s.getEventsSpanning(30), EventVector()); - QCOMPARE(s.getEventsSpanning(9), EventVector()); + EventVector cover; + cover.push_back(p); + cover.push_back(p); + QCOMPARE(s.getEventsCovering(10), cover); + QCOMPARE(s.getEventsCovering(11), cover); + QCOMPARE(s.getEventsCovering(29), cover); + QCOMPARE(s.getEventsCovering(30), EventVector()); + QCOMPARE(s.getEventsCovering(9), EventVector()); s.remove(p); - span.clear(); - span.push_back(p); - QCOMPARE(s.getEventsSpanning(10), span); - QCOMPARE(s.getEventsSpanning(11), span); - QCOMPARE(s.getEventsSpanning(29), span); - QCOMPARE(s.getEventsSpanning(30), EventVector()); - QCOMPARE(s.getEventsSpanning(9), EventVector()); + cover.clear(); + cover.push_back(p); + QCOMPARE(s.getEventsCovering(10), cover); + QCOMPARE(s.getEventsCovering(11), cover); + QCOMPARE(s.getEventsCovering(29), cover); + QCOMPARE(s.getEventsCovering(30), EventVector()); + QCOMPARE(s.getEventsCovering(9), EventVector()); } - void multipleEventsSpan() { + void multipleEventsCover() { EventSeries s; Event a(10, QString("a")); @@ -141,80 +178,121 @@ s.add(c); s.remove(c); QCOMPARE(s.count(), 3); - EventVector span; - span.push_back(a); - QCOMPARE(s.getEventsSpanning(10), span); - span.clear(); - span.push_back(c); - QCOMPARE(s.getEventsSpanning(40), span); - QCOMPARE(s.getEventsSpanning(9), EventVector()); + EventVector cover; + cover.push_back(a); + QCOMPARE(s.getEventsCovering(10), cover); + cover.clear(); + cover.push_back(c); + QCOMPARE(s.getEventsCovering(40), cover); + QCOMPARE(s.getEventsCovering(9), EventVector()); } - void disjointEventsWithDurationSpan() { + void disjointEventsWithDurationCover() { EventSeries s; Event a(10, 1.0f, 20, QString("a")); Event b(100, 1.2f, 30, QString("b")); s.add(a); s.add(b); - QCOMPARE(s.getEventsSpanning(0), EventVector()); - QCOMPARE(s.getEventsSpanning(10), EventVector({ a })); - QCOMPARE(s.getEventsSpanning(15), EventVector({ a })); - QCOMPARE(s.getEventsSpanning(30), EventVector()); - QCOMPARE(s.getEventsSpanning(99), EventVector()); - QCOMPARE(s.getEventsSpanning(100), EventVector({ b })); - QCOMPARE(s.getEventsSpanning(120), EventVector({ b })); - QCOMPARE(s.getEventsSpanning(130), EventVector()); + QCOMPARE(s.getEventsCovering(0), EventVector()); + QCOMPARE(s.getEventsCovering(10), EventVector({ a })); + QCOMPARE(s.getEventsCovering(15), EventVector({ a })); + QCOMPARE(s.getEventsCovering(30), EventVector()); + QCOMPARE(s.getEventsCovering(99), EventVector()); + QCOMPARE(s.getEventsCovering(100), EventVector({ b })); + QCOMPARE(s.getEventsCovering(120), EventVector({ b })); + QCOMPARE(s.getEventsCovering(130), EventVector()); } - void overlappingEventsWithAndWithoutDurationSpan() { + void overlappingEventsWithAndWithoutDurationCover() { EventSeries s; Event p(20, QString("p")); - Event a(10, 1.0, 20, QString("a")); + Event a(10, 1.0f, 20, QString("a")); s.add(p); s.add(a); - EventVector span; - span.push_back(a); - QCOMPARE(s.getEventsSpanning(15), span); - QCOMPARE(s.getEventsSpanning(25), span); - span.clear(); - span.push_back(p); - span.push_back(a); - QCOMPARE(s.getEventsSpanning(20), span); + EventVector cover; + cover.push_back(a); + QCOMPARE(s.getEventsCovering(15), cover); + QCOMPARE(s.getEventsCovering(25), cover); + cover.clear(); + cover.push_back(p); + cover.push_back(a); + QCOMPARE(s.getEventsCovering(20), cover); } - void overlappingEventsWithDurationSpan() { + void overlappingEventsWithDurationCover() { EventSeries s; - Event a(20, 1.0, 10, QString("a")); - Event b(10, 1.0, 20, QString("b")); - Event c(10, 1.0, 40, QString("c")); + Event a(20, 1.0f, 10, QString("a")); + Event b(10, 1.0f, 20, QString("b")); + Event c(10, 1.0f, 40, QString("c")); s.add(a); s.add(b); s.add(c); - QCOMPARE(s.getEventsSpanning(10), EventVector({ b, c })); - QCOMPARE(s.getEventsSpanning(20), EventVector({ b, c, a })); - QCOMPARE(s.getEventsSpanning(25), EventVector({ b, c, a })); - QCOMPARE(s.getEventsSpanning(30), EventVector({ c })); - QCOMPARE(s.getEventsSpanning(40), EventVector({ c })); - QCOMPARE(s.getEventsSpanning(50), EventVector()); + QCOMPARE(s.getEventsCovering(10), EventVector({ b, c })); + QCOMPARE(s.getEventsCovering(20), EventVector({ b, c, a })); + QCOMPARE(s.getEventsCovering(25), EventVector({ b, c, a })); + QCOMPARE(s.getEventsCovering(30), EventVector({ c })); + QCOMPARE(s.getEventsCovering(40), EventVector({ c })); + QCOMPARE(s.getEventsCovering(50), EventVector()); } - void eventPatternSpan() { + void eventPatternCover() { EventSeries s; - Event a(0, 1.0, 18, QString("a")); - Event b(3, 2.0, 6, QString("b")); - Event c(5, 3.0, 2, QString("c")); - Event d(6, 4.0, 10, QString("d")); - Event e(14, 5.0, 3, QString("e")); + 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.getEventsSpanning(8), EventVector({ a, b, d })); + QCOMPARE(s.getEventsCovering(8), EventVector({ a, b, d, dd })); + } + + void eventPatternAddRemove() { + + // This is mostly here to exercise the innards of EventSeries + // and check it doesn't crash out with any internal + // consistency problems + + 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.count(), 7); + s.remove(d); + QCOMPARE(s.getEventsCovering(8), EventVector({ a, b, dd })); + s.remove(e); + s.remove(a); + QCOMPARE(s.getEventsCovering(8), EventVector({ b, dd })); + s.remove(cc); + s.remove(c); + s.remove(dd); + QCOMPARE(s.getEventsCovering(8), EventVector({ b })); + s.remove(b); + QCOMPARE(s.getEventsCovering(8), EventVector()); + QCOMPARE(s.count(), 0); + QCOMPARE(s.isEmpty(), true); } };