# HG changeset patch # User Chris Cannam # Date 1552315753 0 # Node ID 1c21ddac220e0a6caf91e6479a66956ce9a19466 # Parent 895186c43fcea7b206a6db6418bd04e02c21595f Seems we can do just as well with a vector of events themselves diff -r 895186c43fce -r 1c21ddac220e base/Event.cpp --- 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::m_ids; -QHash Event::m_rids; - diff -r 895186c43fce -r 1c21ddac220e base/Event.h --- 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 m_ids; - static QHash m_rids; }; inline uint qHash(const Event &e, uint seed = 0) { diff -r 895186c43fce -r 1c21ddac220e base/EventSeries.h --- 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 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> FrameEventMap; + typedef std::map> 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 &s1, + const std::vector &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 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; diff -r 895186c43fce -r 1c21ddac220e base/test/StressEventSeries.h --- 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 + */ }; diff -r 895186c43fce -r 1c21ddac220e files.pri --- 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 \