Chris@1612: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
Chris@1612: 
Chris@1612: /*
Chris@1612:     Sonic Visualiser
Chris@1612:     An audio file viewer and annotation editor.
Chris@1612:     Centre for Digital Music, Queen Mary, University of London.
Chris@1612:     
Chris@1612:     This program is free software; you can redistribute it and/or
Chris@1612:     modify it under the terms of the GNU General Public License as
Chris@1612:     published by the Free Software Foundation; either version 2 of the
Chris@1612:     License, or (at your option) any later version.  See the file
Chris@1612:     COPYING included with this distribution for more information.
Chris@1612: */
Chris@1612: 
Chris@1615: #ifndef SV_EVENT_SERIES_H
Chris@1615: #define SV_EVENT_SERIES_H
Chris@1612: 
Chris@1615: #include "Event.h"
Chris@1612: 
Chris@1612: #include <set>
Chris@1612: 
Chris@1615: //#define DEBUG_EVENT_SERIES 1
Chris@1614: 
Chris@1615: /**
Chris@1615:  * Container storing a series of events, with or without durations,
Chris@1616:  * and supporting the ability to query which events are active at a
Chris@1616:  * given frame or within a span of frames.
Chris@1616:  *
Chris@1616:  * To that end, in addition to the series of events, it stores a
Chris@1616:  * series of "seams", which are frame positions at which the set of
Chris@1616:  * simultaneous events changes (i.e. an event of non-zero duration
Chris@1616:  * starts or ends) associated with a set of the events that are active
Chris@1616:  * at or from that position. These are updated when an event is added
Chris@1616:  * or removed.
Chris@1618:  *
Chris@1618:  * Performance is highly dependent on the extent of overlapping events
Chris@1618:  * and the order in which events are added. Each event (with duration)
Chris@1618:  * that is added requires updating all the seams within the extent of
Chris@1618:  * that event, taking a number of ordered-set updates proportional to
Chris@1618:  * the number of events already existing within its extent. Add events
Chris@1618:  * in order of start frame if possible.
Chris@1615:  */
Chris@1615: class EventSeries
Chris@1612: {
Chris@1612: public:
Chris@1615:     EventSeries() : m_count(0) { }
Chris@1616:     ~EventSeries() =default;
Chris@1616: 
Chris@1616:     EventSeries(const EventSeries &) =default;
Chris@1616:     EventSeries &operator=(const EventSeries &) =default;
Chris@1616:     EventSeries &operator=(EventSeries &&) =default;
Chris@1616:     
Chris@1616:     bool operator==(const EventSeries &other) const {
Chris@1616:         return m_events == other.m_events;
Chris@1616:     }
Chris@1612:     
Chris@1615:     void add(const Event &p) {
Chris@1612: 
Chris@1627:         bool isUnique = true;
Chris@1627: 
Chris@1627:         auto pitr = m_events.find(p);
Chris@1627:         if (pitr != m_events.end()) {
Chris@1627:             isUnique = false;
Chris@1627:         }
Chris@1627: 
Chris@1616:         ++m_events[p];
Chris@1612:         ++m_count;
Chris@1612: 
Chris@1627:         if (p.hasDuration() && isUnique) {
Chris@1617: 
Chris@1617:             const sv_frame_t frame = p.getFrame();
Chris@1617:             const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1612: 
Chris@1614:             createSeam(frame);
Chris@1614:             createSeam(endFrame);
Chris@1616: 
Chris@1616:             // These calls must both succeed after calling createSeam above
Chris@1616:             const auto i0 = m_seams.find(frame);
Chris@1616:             const auto i1 = m_seams.find(endFrame);
Chris@1614: 
Chris@1614:             for (auto i = i0; i != i1; ++i) {
Chris@1614:                 if (i == m_seams.end()) {
Chris@1615:                     SVCERR << "ERROR: EventSeries::add: "
Chris@1614:                            << "reached end of seam map"
Chris@1614:                            << endl;
Chris@1614:                     break;
Chris@1612:                 }
Chris@1627:                 i->second.push_back(p);
Chris@1612:             }
Chris@1614:         }
Chris@1612: 
Chris@1615: #ifdef DEBUG_EVENT_SERIES
Chris@1614:         std::cerr << "after add:" << std::endl;
Chris@1615:         dumpEvents();
Chris@1614:         dumpSeams();
Chris@1614: #endif
Chris@1612:     }
Chris@1612: 
Chris@1615:     void remove(const Event &p) {
Chris@1612: 
Chris@1616:         // If we are removing the last (unique) example of an event,
Chris@1616:         // then we also need to remove it from the seam map. If this
Chris@1616:         // is only one of multiple identical events, then we don't.
Chris@1616:         bool isUnique = false;
Chris@1616:         
Chris@1615:         auto pitr = m_events.find(p);
Chris@1615:         if (pitr == m_events.end()) {
Chris@1615:             return; // we don't know this event
Chris@1612:         } else {
Chris@1625:             if (--(pitr->second) == 0) {
Chris@1616:                 isUnique = true;
Chris@1616:                 m_events.erase(pitr);
Chris@1616:             }
Chris@1612:             --m_count;
Chris@1612:         }
Chris@1612: 
Chris@1616:         if (p.hasDuration() && isUnique) {
Chris@1616:             
Chris@1617:             const sv_frame_t frame = p.getFrame();
Chris@1617:             const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1612: 
Chris@1616:             const auto i0 = m_seams.find(frame);
Chris@1616:             const auto i1 = m_seams.find(endFrame);
Chris@1614: 
Chris@1615: #ifdef DEBUG_EVENT_SERIES
Chris@1615:             // This should be impossible if we found p in m_events above
Chris@1614:             if (i0 == m_seams.end() || i1 == m_seams.end()) {
Chris@1615:                 SVCERR << "ERROR: EventSeries::remove: either frame " << frame
Chris@1614:                        << " or endFrame " << endFrame
Chris@1615:                        << " for event not found in seam map: event is "
Chris@1612:                        << p.toXmlString() << endl;
Chris@1612:             }
Chris@1614: #endif
Chris@1612: 
Chris@1627:             // Remove any and all instances of p from the seam map; we
Chris@1627:             // are only supposed to get here if we are removing the
Chris@1627:             // last instance of p from the series anyway
Chris@1627:             
Chris@1614:             for (auto i = i0; i != i1; ++i) {
Chris@1614:                 if (i == m_seams.end()) {
Chris@1615:                     // This can happen only if we have a negative
Chris@1616:                     // duration, which Event forbids
Chris@1616:                     throw std::logic_error("unexpectedly reached end of map");
Chris@1616:                 }
Chris@1626:                 for (size_t j = 0; j < i->second.size(); ) {
Chris@1627:                     if (i->second[j] == p) {
Chris@1626:                         i->second.erase(i->second.begin() + j);
Chris@1626:                     } else {
Chris@1626:                         ++j;
Chris@1626:                     }
Chris@1626:                 }
Chris@1616:             }
Chris@1616: 
Chris@1616:             // Tidy up by removing any entries that are now identical
Chris@1616:             // to their predecessors
Chris@1626:             
Chris@1616:             std::vector<sv_frame_t> redundant;
Chris@1616: 
Chris@1616:             auto pitr = m_seams.end();
Chris@1616:             if (i0 != m_seams.begin()) {
Chris@1616:                 pitr = i0;
Chris@1616:                 --pitr;
Chris@1616:             }
Chris@1616: 
Chris@1616:             for (auto i = i0; i != m_seams.end(); ++i) {
Chris@1627:                 if (pitr != m_seams.end() &&
Chris@1627:                     seamsEqual(i->second, pitr->second)) {
Chris@1625:                     redundant.push_back(i->first);
Chris@1616:                 }
Chris@1616:                 pitr = i;
Chris@1616:                 if (i == i1) {
Chris@1614:                     break;
Chris@1614:                 }
Chris@1612:             }
Chris@1612: 
Chris@1616:             for (sv_frame_t f: redundant) {
Chris@1625:                 m_seams.erase(f);
Chris@1616:             }
Chris@1627: 
Chris@1627:             // And remove any empty seams from the start of the map
Chris@1627:             
Chris@1627:             while (m_seams.begin() != m_seams.end() &&
Chris@1627:                    m_seams.begin()->second.empty()) {
Chris@1627:                 m_seams.erase(m_seams.begin());
Chris@1627:             }
Chris@1612:         }
Chris@1614: 
Chris@1615: #ifdef DEBUG_EVENT_SERIES
Chris@1614:         std::cerr << "after remove:" << std::endl;
Chris@1615:         dumpEvents();
Chris@1614:         dumpSeams();
Chris@1614: #endif
Chris@1612:     }
Chris@1612: 
Chris@1615:     bool contains(const Event &p) {
Chris@1615:         return m_events.find(p) != m_events.end();
Chris@1612:     }
Chris@1612: 
Chris@1612:     int count() const {
Chris@1612:         return m_count;
Chris@1612:     }
Chris@1612: 
Chris@1612:     bool isEmpty() const {
Chris@1612:         return m_count == 0;
Chris@1612:     }
Chris@1612:     
Chris@1612:     void clear() {
Chris@1615:         m_events.clear();
Chris@1612:         m_seams.clear();
Chris@1612:         m_count = 0;
Chris@1612:     }
Chris@1612: 
Chris@1612:     /**
Chris@1616:      * Retrieve all events any part of which falls within the span in
Chris@1616:      * frames defined by the given frame f and duration d.
Chris@1616:      *
Chris@1616:      * - An event without duration is within the span if its own frame
Chris@1616:      * is greater than or equal to f and less than f + d.
Chris@1616:      * 
Chris@1616:      * - An event with duration is within the span if its start frame
Chris@1616:      * is less than f + d and its start frame plus its duration is
Chris@1616:      * greater than f.
Chris@1616:      * 
Chris@1619:      * Note: Passing a duration of zero is seldom useful here; you
Chris@1619:      * probably want getEventsCovering instead. getEventsSpanning(f,
Chris@1619:      * 0) is not equivalent to getEventsCovering(f). The latter
Chris@1619:      * includes durationless events at f and events starting at f,
Chris@1619:      * both of which are excluded from the former.
Chris@1616:      */
Chris@1617:     EventVector getEventsSpanning(sv_frame_t frame,
Chris@1617:                                   sv_frame_t duration) const {
Chris@1616:         EventVector span;
Chris@1616: 
Chris@1617:         const sv_frame_t start = frame;
Chris@1617:         const sv_frame_t end = frame + duration;
Chris@1616:         
Chris@1616:         // first find any zero-duration events
Chris@1616:         
Chris@1625:         auto pitr = m_events.lower_bound(Event(start, QString()));
Chris@1625:         while (pitr != m_events.end() && pitr->first.getFrame() < end) {
Chris@1625:             if (!pitr->first.hasDuration()) {
Chris@1625:                 for (int i = 0; i < pitr->second; ++i) {
Chris@1625:                     span.push_back(pitr->first);
Chris@1616:                 }
Chris@1616:             }
Chris@1616:             ++pitr;
Chris@1616:         }
Chris@1616: 
Chris@1616:         // now any non-zero-duration ones from the seam map
Chris@1616: 
Chris@1616:         std::set<Event> found;
Chris@1625:         auto sitr = m_seams.lower_bound(start);
Chris@1625:         if (sitr == m_seams.end() || sitr->first > start) {
Chris@1616:             if (sitr != m_seams.begin()) {
Chris@1616:                 --sitr;
Chris@1616:             }                
Chris@1616:         }
Chris@1625:         while (sitr != m_seams.end() && sitr->first < end) {
Chris@1627:             for (const auto &p: sitr->second) {
Chris@1627:                 found.insert(p);
Chris@1616:             }
Chris@1616:             ++sitr;
Chris@1616:         }
Chris@1616:         for (const auto &p: found) {
Chris@1625:             int n = m_events.at(p);
Chris@1616:             if (n < 1) {
Chris@1616:                 throw std::logic_error("event is in seams but not events");
Chris@1616:             }
Chris@1616:             for (int i = 0; i < n; ++i) {
Chris@1616:                 span.push_back(p);
Chris@1616:             }
Chris@1616:         }
Chris@1616:             
Chris@1616:         return span;
Chris@1616:     }
Chris@1616: 
Chris@1616:     /**
Chris@1616:      * Retrieve all events that cover the given frame. An event without
Chris@1616:      * duration covers a frame if its own frame is equal to it. An event
Chris@1616:      * with duration covers a frame if its start frame is less than or
Chris@1612:      * equal to it and its end frame (start + duration) is greater
Chris@1612:      * than it.
Chris@1612:      */
Chris@1616:     EventVector getEventsCovering(sv_frame_t frame) const {
Chris@1616:         EventVector cover;
Chris@1614: 
Chris@1615:         // first find any zero-duration events
Chris@1616:         
Chris@1625:         auto pitr = m_events.lower_bound(Event(frame, QString()));
Chris@1625:         while (pitr != m_events.end() && pitr->first.getFrame() == frame) {
Chris@1625:             if (!pitr->first.hasDuration()) {
Chris@1625:                 for (int i = 0; i < pitr->second; ++i) {
Chris@1625:                     cover.push_back(pitr->first);
Chris@1614:                 }
Chris@1614:             }
Chris@1616:             ++pitr;
Chris@1614:         }
Chris@1614: 
Chris@1625:         // now any non-zero-duration ones from the seam map
Chris@1616:         
Chris@1626:         std::set<Event> found;
Chris@1625:         auto sitr = m_seams.lower_bound(frame);
Chris@1625:         if (sitr == m_seams.end() || sitr->first > frame) {
Chris@1614:             if (sitr != m_seams.begin()) {
Chris@1614:                 --sitr;
Chris@1614:             }                
Chris@1614:         }
Chris@1625:         if (sitr != m_seams.end() && sitr->first <= frame) {
Chris@1627:             for (const auto &p: sitr->second) {
Chris@1627:                 found.insert(p);
Chris@1626:             }
Chris@1626:             ++sitr;
Chris@1626:         }
Chris@1626:         for (const auto &p: found) {
Chris@1626:             int n = m_events.at(p);
Chris@1626:             if (n < 1) {
Chris@1626:                 throw std::logic_error("event is in seams but not events");
Chris@1626:             }
Chris@1626:             for (int i = 0; i < n; ++i) {
Chris@1626:                 cover.push_back(p);
Chris@1614:             }
Chris@1614:         }
Chris@1614:         
Chris@1616:         return cover;
Chris@1612:     }
Chris@1612: 
Chris@1612: private:
Chris@1616:     /**
Chris@1616:      * Total number of events in the series. Will exceed
Chris@1616:      * m_events.size() if the series contains duplicate events.
Chris@1616:      */
Chris@1612:     int m_count;
Chris@1625: 
Chris@1616:     /**
Chris@1616:      * The (ordered) Events map acts as a list of all the events in
Chris@1616:      * the series. For reasons of backward compatibility, we have to
Chris@1616:      * handle series containing multiple instances of identical
Chris@1616:      * events; the int indexed against each event records the number
Chris@1616:      * of instances of that event. We do this in preference to using a
Chris@1616:      * multiset, in order to support the case in which we have
Chris@1616:      * obtained a set of distinct events (from the seam container
Chris@1616:      * below) and then need to return the correct number of each.
Chris@1616:      *
Chris@1616:      * Because events are immutable, we never have to move one to a
Chris@1616:      * different "key" in this map - we only add or delete them or
Chris@1616:      * change their counts.
Chris@1616:      */
Chris@1625:     typedef std::map<Event, int> Events;
Chris@1616:     Events m_events;
Chris@1614: 
Chris@1616:     /**
Chris@1616:      * The FrameEventMap maps from frame number to a set of events. In
Chris@1616:      * the seam map this is used to represent the events that are
Chris@1616:      * active at that frame, either because they begin at that frame
Chris@1616:      * or because they are continuing from an earlier frame. There is
Chris@1616:      * an entry here for each frame at which an event starts or ends,
Chris@1616:      * with the event appearing in all entries from its start time
Chris@1616:      * onward and disappearing again at its end frame.
Chris@1616:      *
Chris@1616:      * Only events with duration appear in this map; point events
Chris@1627:      * appear only in m_events. Note that unlike m_events, we only
Chris@1627:      * store one instance of each event here, even if we hold many -
Chris@1627:      * we refer back to m_events when we need to know how many
Chris@1627:      * identical copies of a given event we have.
Chris@1616:      */
Chris@1627:     typedef std::map<sv_frame_t, std::vector<Event>> FrameEventMap;
Chris@1616:     FrameEventMap m_seams;
Chris@1614: 
Chris@1614:     /** Create a seam at the given frame, copying from the prior seam
Chris@1614:      *  if there is one. If a seam already exists at the given frame,
Chris@1614:      *  leave it untouched.
Chris@1614:      */
Chris@1614:     void createSeam(sv_frame_t frame) {
Chris@1625:         auto itr = m_seams.lower_bound(frame);
Chris@1625:         if (itr == m_seams.end() || itr->first > frame) {
Chris@1614:             if (itr != m_seams.begin()) {
Chris@1614:                 --itr;
Chris@1614:             }
Chris@1614:         }
Chris@1614:         if (itr == m_seams.end()) {
Chris@1614:             m_seams[frame] = {};
Chris@1625:         } else if (itr->first < frame) {
Chris@1625:             m_seams[frame] = itr->second;
Chris@1625:         } else if (itr->first > frame) { // itr must be begin()
Chris@1614:             m_seams[frame] = {};
Chris@1614:         }
Chris@1614:     }
Chris@1614: 
Chris@1627:     bool seamsEqual(const std::vector<Event> &s1,
Chris@1627:                     const std::vector<Event> &s2) const {
Chris@1627:         
Chris@1627:         if (s1.size() != s2.size()) {
Chris@1627:             return false;
Chris@1627:         }
Chris@1627: 
Chris@1627:         // precondition: no event appears more than once in s1 or more
Chris@1627:         // than once in s2
Chris@1627: 
Chris@1627: #ifdef DEBUG_EVENT_SERIES
Chris@1627:         for (int i = 0; in_range_for(s1, i); ++i) {
Chris@1627:             for (int j = i + 1; in_range_for(s1, j); ++j) {
Chris@1627:                 if (s1[i] == s1[j] || s2[i] == s2[j]) {
Chris@1627:                     throw std::runtime_error
Chris@1627:                         ("debug error: duplicate event in s1 or s2");
Chris@1627:                 }
Chris@1627:             }
Chris@1627:         }
Chris@1627: #endif
Chris@1627: 
Chris@1627:         std::set<Event> ee;
Chris@1627:         for (const auto &e: s1) {
Chris@1627:             ee.insert(e);
Chris@1627:         }
Chris@1627:         for (const auto &e: s2) {
Chris@1627:             if (ee.find(e) == ee.end()) {
Chris@1627:                 return false;
Chris@1627:             }
Chris@1627:         }
Chris@1627:         return true;
Chris@1627:     }
Chris@1627: 
Chris@1615: #ifdef DEBUG_EVENT_SERIES
Chris@1615:     void dumpEvents() const {
Chris@1618:         std::cerr << "EVENTS (" << m_events.size() << ") [" << std::endl;
Chris@1616:         for (const auto &i: m_events) {
Chris@1618:             std::cerr << "  " << i.second << "x " << i.first.toXmlString();
Chris@1614:         }
Chris@1614:         std::cerr << "]" << std::endl;
Chris@1614:     }
Chris@1614:     
Chris@1614:     void dumpSeams() const {
Chris@1618:         std::cerr << "SEAMS (" << m_seams.size() << ") [" << std::endl;
Chris@1614:         for (const auto &s: m_seams) {
Chris@1614:             std::cerr << "  " << s.first << " -> {" << std::endl;
Chris@1614:             for (const auto &p: s.second) {
Chris@1614:                 std::cerr << p.toXmlString("    ");
Chris@1614:             }
Chris@1614:             std::cerr << "  }" << std::endl;
Chris@1614:         }
Chris@1614:         std::cerr << "]" << std::endl;
Chris@1614:     }
Chris@1614: #endif
Chris@1612: };
Chris@1612: 
Chris@1612: #endif