comparison base/EventSeries.h @ 1616:de446dd905e6 single-point

Rework EventSeries to explicitly store counts of events (+ add comments explaining, among other things, why)

 
 //#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.
+ * 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()) {
             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
+
+            // 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()) {
                     SVCERR << "ERROR: EventSeries::add: "
                            << "reached end of seam map"

 #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
+        // 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
             if (i0 == m_seams.end() || i1 == m_seams.end()) {
                 SVCERR << "ERROR: EventSeries::remove: either frame " << frame

 #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;
+                    // 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
         std::cerr << "after remove:" << std::endl;
         dumpEvents();

         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
+     * 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);
-                }
-                ++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;
         }
 
         // 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;
+            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 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;
-
-    typedef std::map<sv_frame_t, std::multiset<Event>> FrameEventsMap;
-    FrameEventsMap m_seams;
+    /**
+     * 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;
+
+    /**
+     * 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,
      *  leave it untouched.
      */

     }
 
 #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;
     }
     
     void dumpSeams() const {