comparison base/EventSeries.h @ 1615:24dc8cb42755 single-point

Rename a number of classes and methods (including Point -> Event); comments

+/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
+
+/*
+    Sonic Visualiser
+    An audio file viewer and annotation editor.
+    Centre for Digital Music, Queen Mary, University of London.
+    
+    This program is free software; you can redistribute it and/or
+    modify it under the terms of the GNU General Public License as
+    published by the Free Software Foundation; either version 2 of the
+    License, or (at your option) any later version.  See the file
+    COPYING included with this distribution for more information.
+*/
+
+#ifndef SV_EVENT_SERIES_H
+#define SV_EVENT_SERIES_H
+
+#include "Event.h"
+
+#include <set>
+
+//#define DEBUG_EVENT_SERIES 1
+
+/**
+ * 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.
+ */
+class EventSeries
+{
+public:
+    EventSeries() : m_count(0) { }
+    
+    void add(const Event &p) {
+
+        m_events.insert(p);
+        ++m_count;
+
+        if (p.hasDuration()) {
+            sv_frame_t frame = p.getFrame();
+            sv_frame_t endFrame = p.getFrame() + p.getDuration();
+
+            createSeam(frame);
+            createSeam(endFrame);
+            
+            auto i0 = m_seams.find(frame); // must succeed after createSeam
+            auto i1 = m_seams.find(endFrame); // likewise
+
+            for (auto i = i0; i != i1; ++i) {
+                if (i == m_seams.end()) {
+                    SVCERR << "ERROR: EventSeries::add: "
+                           << "reached end of seam map"
+                           << endl;
+                    break;
+                }
+                i->second.insert(p);
+            }
+        }
+
+#ifdef DEBUG_EVENT_SERIES
+        std::cerr << "after add:" << std::endl;
+        dumpEvents();
+        dumpSeams();
+#endif
+    }
+
+    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
+        auto pitr = m_events.find(p);
+        if (pitr == m_events.end()) {
+            return; // we don't know this event
+        } else {
+            m_events.erase(pitr);
+            --m_count;
+        }
+
+        if (p.hasDuration()) {
+            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);
+
+#ifdef DEBUG_EVENT_SERIES
+            // This should be impossible if we found p in m_events above
+            if (i0 == m_seams.end() || i1 == m_seams.end()) {
+                SVCERR << "ERROR: EventSeries::remove: either frame " << frame
+                       << " or endFrame " << endFrame
+                       << " for event not found in seam map: event is "
+                       << p.toXmlString() << endl;
+            }
+#endif
+
+            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;
+                    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.
+        }
+
+#ifdef DEBUG_EVENT_SERIES
+        std::cerr << "after remove:" << std::endl;
+        dumpEvents();
+        dumpSeams();
+#endif
+    }
+
+    bool contains(const Event &p) {
+        return m_events.find(p) != m_events.end();
+    }
+
+    int count() const {
+        return m_count;
+    }
+
+    bool isEmpty() const {
+        return m_count == 0;
+    }
+    
+    void clear() {
+        m_events.clear();
+        m_seams.clear();
+        m_count = 0;
+    }
+
+    /**
+     * 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
+     * equal to it and its end frame (start + duration) is greater
+     * than it.
+     */
+    EventVector getEventsSpanning(sv_frame_t frame) const {
+        EventVector span;
+
+        // 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);
+                }
+                ++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()) {
+                --sitr;
+            }                
+        }
+        if (sitr != m_seams.end() && sitr->first <= frame) {
+            for (auto p: sitr->second) {
+                span.push_back(p);
+            }
+        }
+        
+        return span;
+    }
+
+private:
+    int m_count;
+
+    typedef std::multiset<Event> EventMultiset;
+    EventMultiset m_events;
+
+    typedef std::map<sv_frame_t, std::multiset<Event>> FrameEventsMap;
+    FrameEventsMap 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,
+     *  leave it untouched.
+     */
+    void createSeam(sv_frame_t frame) {
+        auto itr = m_seams.lower_bound(frame);
+        if (itr == m_seams.end() || itr->first > frame) {
+            if (itr != m_seams.begin()) {
+                --itr;
+            }
+        }
+        if (itr == m_seams.end()) {
+            m_seams[frame] = {};
+        } else if (itr->first < frame) {
+            m_seams[frame] = itr->second;
+        } else if (itr->first > frame) { // itr must be begin()
+            m_seams[frame] = {};
+        }
+    }
+
+#ifdef DEBUG_EVENT_SERIES
+    void dumpEvents() const {
+        std::cerr << "EVENTS [" << std::endl;
+        for (const auto &p: m_events) {
+            std::cerr << p.toXmlString("  ");
+        }
+        std::cerr << "]" << std::endl;
+    }
+    
+    void dumpSeams() const {
+        std::cerr << "SEAMS [" << std::endl;
+        for (const auto &s: m_seams) {
+            std::cerr << "  " << s.first << " -> {" << std::endl;
+            for (const auto &p: s.second) {
+                std::cerr << p.toXmlString("    ");
+            }
+            std::cerr << "  }" << std::endl;
+        }
+        std::cerr << "]" << std::endl;
+    }
+#endif
+};
+
+#endif