changeset 1627:1c21ddac220e single-point

Seems we can do just as well with a vector of events themselves
author Chris Cannam
date Mon, 11 Mar 2019 14:49:13 +0000 (2019-03-11)
parents 895186c43fce
children 6db21df9f376
files base/Event.cpp base/Event.h base/EventSeries.h base/test/StressEventSeries.h files.pri
diffstat 5 files changed, 80 insertions(+), 72 deletions(-) [+]
line wrap: on
line diff
--- a/base/Event.cpp	Mon Mar 11 13:44:35 2019 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,21 +0,0 @@
-/* -*- 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 file copyright 2006 Chris Cannam.
-    
-    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.
-*/
-
-#include "Event.h"
-
-sv_id_t Event::m_nextId = 1;
-QHash<Event, sv_id_t> Event::m_ids;
-QHash<sv_id_t, Event> Event::m_rids;
-
--- a/base/Event.h	Mon Mar 11 13:44:35 2019 +0000
+++ b/base/Event.h	Mon Mar 11 14:49:13 2019 +0000
@@ -279,27 +279,6 @@
         if (m_haveReferenceFrame) h ^= qHash(m_referenceFrame);
         return h;
     }
-
-    static sv_id_t getId(const Event &ev) {
-        sv_id_t id;
-        if (!m_ids.contains(ev)) {
-            id = m_nextId;
-            ++m_nextId;
-            m_ids[ev] = id;
-            m_rids[id] = ev;
-            return id;
-        } else {
-            return m_ids.value(ev);
-        }
-    }
-
-    static Event getEventForId(sv_id_t id) {
-        if (!m_rids.contains(id)) {
-            throw std::runtime_error("unknown event id");
-        } else {
-            return m_rids.value(id);
-        }
-    }
     
 private:
     // The order of fields here is chosen to minimise overall size of struct.
@@ -314,10 +293,6 @@
     sv_frame_t m_duration;
     sv_frame_t m_referenceFrame;
     QString m_label;
-
-    static sv_id_t m_nextId;
-    static QHash<Event, sv_id_t> m_ids;
-    static QHash<sv_id_t, Event> m_rids;
 };
 
 inline uint qHash(const Event &e, uint seed = 0) {
--- a/base/EventSeries.h	Mon Mar 11 13:44:35 2019 +0000
+++ b/base/EventSeries.h	Mon Mar 11 14:49:13 2019 +0000
@@ -56,12 +56,17 @@
     
     void add(const Event &p) {
 
+        bool isUnique = true;
+
+        auto pitr = m_events.find(p);
+        if (pitr != m_events.end()) {
+            isUnique = false;
+        }
+
         ++m_events[p];
         ++m_count;
 
-        sv_id_t id = Event::getId(p);
-        
-        if (p.hasDuration()) {
+        if (p.hasDuration() && isUnique) {
 
             const sv_frame_t frame = p.getFrame();
             const sv_frame_t endFrame = p.getFrame() + p.getDuration();
@@ -80,16 +85,7 @@
                            << endl;
                     break;
                 }
-/*                bool found = false;
-                for (auto eid: i->second) {
-                    if (eid == id) {
-                        found = true;
-                        break;
-                    }
-                }
-                if (!found) {*/
-                    i->second.push_back(id);
-//                }
+                i->second.push_back(p);
             }
         }
 
@@ -118,8 +114,6 @@
             --m_count;
         }
 
-        sv_id_t id = Event::getId(p);
-        
         if (p.hasDuration() && isUnique) {
             
             const sv_frame_t frame = p.getFrame();
@@ -138,6 +132,10 @@
             }
 #endif
 
+            // Remove any and all instances of p from the seam map; we
+            // are only supposed to get here if we are removing the
+            // last instance of p from the series anyway
+            
             for (auto i = i0; i != i1; ++i) {
                 if (i == m_seams.end()) {
                     // This can happen only if we have a negative
@@ -145,7 +143,7 @@
                     throw std::logic_error("unexpectedly reached end of map");
                 }
                 for (size_t j = 0; j < i->second.size(); ) {
-                    if (i->second[j] == id) {
+                    if (i->second[j] == p) {
                         i->second.erase(i->second.begin() + j);
                     } else {
                         ++j;
@@ -155,8 +153,6 @@
 
             // Tidy up by removing any entries that are now identical
             // to their predecessors
-
-//!!! won't work as vector is not consistently ordered
             
             std::vector<sv_frame_t> redundant;
 
@@ -167,7 +163,8 @@
             }
 
             for (auto i = i0; i != m_seams.end(); ++i) {
-                if (pitr != m_seams.end() && i->second == pitr->second) {
+                if (pitr != m_seams.end() &&
+                    seamsEqual(i->second, pitr->second)) {
                     redundant.push_back(i->first);
                 }
                 pitr = i;
@@ -179,6 +176,13 @@
             for (sv_frame_t f: redundant) {
                 m_seams.erase(f);
             }
+
+            // And remove any empty seams from the start of the map
+            
+            while (m_seams.begin() != m_seams.end() &&
+                   m_seams.begin()->second.empty()) {
+                m_seams.erase(m_seams.begin());
+            }
         }
 
 #ifdef DEBUG_EVENT_SERIES
@@ -252,8 +256,8 @@
             }                
         }
         while (sitr != m_seams.end() && sitr->first < end) {
-            for (const auto &id: sitr->second) {
-                found.insert(Event::getEventForId(id));
+            for (const auto &p: sitr->second) {
+                found.insert(p);
             }
             ++sitr;
         }
@@ -302,8 +306,8 @@
             }                
         }
         if (sitr != m_seams.end() && sitr->first <= frame) {
-            for (const auto &id: sitr->second) {
-                found.insert(Event::getEventForId(id));
+            for (const auto &p: sitr->second) {
+                found.insert(p);
             }
             ++sitr;
         }
@@ -354,9 +358,12 @@
      * onward and disappearing again at its end frame.
      *
      * Only events with duration appear in this map; point events
-     * appear only in m_events.
+     * appear only in m_events. Note that unlike m_events, we only
+     * store one instance of each event here, even if we hold many -
+     * we refer back to m_events when we need to know how many
+     * identical copies of a given event we have.
      */
-    typedef std::map<sv_frame_t, std::vector<sv_id_t>> FrameEventMap;
+    typedef std::map<sv_frame_t, std::vector<Event>> FrameEventMap;
     FrameEventMap m_seams;
 
     /** Create a seam at the given frame, copying from the prior seam
@@ -379,6 +386,39 @@
         }
     }
 
+    bool seamsEqual(const std::vector<Event> &s1,
+                    const std::vector<Event> &s2) const {
+        
+        if (s1.size() != s2.size()) {
+            return false;
+        }
+
+        // precondition: no event appears more than once in s1 or more
+        // than once in s2
+
+#ifdef DEBUG_EVENT_SERIES
+        for (int i = 0; in_range_for(s1, i); ++i) {
+            for (int j = i + 1; in_range_for(s1, j); ++j) {
+                if (s1[i] == s1[j] || s2[i] == s2[j]) {
+                    throw std::runtime_error
+                        ("debug error: duplicate event in s1 or s2");
+                }
+            }
+        }
+#endif
+
+        std::set<Event> ee;
+        for (const auto &e: s1) {
+            ee.insert(e);
+        }
+        for (const auto &e: s2) {
+            if (ee.find(e) == ee.end()) {
+                return false;
+            }
+        }
+        return true;
+    }
+
 #ifdef DEBUG_EVENT_SERIES
     void dumpEvents() const {
         std::cerr << "EVENTS (" << m_events.size() << ") [" << std::endl;
--- a/base/test/StressEventSeries.h	Mon Mar 11 13:44:35 2019 +0000
+++ b/base/test/StressEventSeries.h	Mon Mar 11 14:49:13 2019 +0000
@@ -105,6 +105,21 @@
 13.64user 0.26system 0:13.98elapsed 99%CPU (0avgtext+0avgdata 948104maxresident)k
 0inputs+40outputs (0major+234387minor)pagefaults 0swaps
 
+895186c43fce:
+
+                 Time for 1000 short events =      1.706ms
+                 Time for 10000 short events =     23.192ms
+                 Time for 100000 short events =    310.605ms
+                 Time for 1000000 short events =   4675.7ms
+                 Time for 1000 longish events =    2.186ms
+                 Time for 10000 longish events =   760.659ms
+                 Time for 100000 longish events =  1335.57ms
+
+Totals: 9 passed, 0 failed, 0 skipped, 0 blacklisted, 7804ms
+
+7.97user 0.29system 0:08.31elapsed 99%CPU (0avgtext+0avgdata 706388maxresident)k
+0inputs+40outputs (0major+182225minor)pagefaults 0swaps
+
     */
 };
 
--- a/files.pri	Mon Mar 11 13:44:35 2019 +0000
+++ b/files.pri	Mon Mar 11 14:49:13 2019 +0000
@@ -152,7 +152,6 @@
            base/ColumnOp.cpp \
            base/Command.cpp \
            base/Debug.cpp \
-           base/Event.cpp \
            base/Exceptions.cpp \
            base/HelperExecPath.cpp \
            base/LogRange.cpp \