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@1631: #include "XmlExportable.h" Chris@1612: Chris@1612: #include 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@1632: * This class is highly optimised for inserting events in increasing Chris@1632: * order of start frame. Inserting (or deleting) events in the middle Chris@1632: * does work, and should be acceptable in interactive use, but it is Chris@1632: * very slow in bulk. Chris@1615: */ Chris@1631: class EventSeries : public XmlExportable Chris@1612: { Chris@1612: public: Chris@1640: EventSeries() : m_finalDurationlessEventFrame(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@1631: void clear(); Chris@1632: void add(const Event &e); Chris@1632: void remove(const Event &e); Chris@1632: bool contains(const Event &e) const; Chris@1631: bool isEmpty() const; Chris@1631: int count() const; Chris@1612: Chris@1612: /** Chris@1640: * Return the frame of the first event in the series. If there are Chris@1640: * no events, return 0. Chris@1640: */ Chris@1640: sv_frame_t getStartFrame() const; Chris@1640: Chris@1640: /** Chris@1640: * Return the frame plus duration of the event in the series that Chris@1640: * ends last. If there are no events, return 0. Chris@1640: */ Chris@1640: sv_frame_t getEndFrame() const; Chris@1640: Chris@1640: /** Chris@1635: * Retrieve all events any part of which falls within the range in Chris@1616: * frames defined by the given frame f and duration d. Chris@1616: * Chris@1635: * - An event without duration is spanned by the range if its own Chris@1635: * frame is greater than or equal to f and less than f + d. Chris@1616: * Chris@1635: * - An event with duration is spanned by the range if its start Chris@1635: * frame is less than f + d and its start frame plus its duration Chris@1635: * is 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@1631: sv_frame_t duration) const; Chris@1616: Chris@1616: /** Chris@1656: * Retrieve all events that cover the given frame. An event without Chris@1656: * duration covers a frame if its own frame is equal to it. An event Chris@1656: * with duration covers a frame if its start frame is less than or Chris@1656: * equal to it and its end frame (start + duration) is greater Chris@1656: * than it. Chris@1656: */ Chris@1656: EventVector getEventsCovering(sv_frame_t frame) const; Chris@1656: Chris@1656: /** Chris@1635: * Retrieve all events falling wholly within the range in frames Chris@1635: * defined by the given frame f and duration d. Chris@1635: * Chris@1635: * - An event without duration is within the range if its own Chris@1635: * frame is greater than or equal to f and less than f + d. Chris@1635: * Chris@1635: * - An event with duration is within the range if its start frame Chris@1635: * is greater than or equal to f and its start frame plus its Chris@1635: * duration is less than or equal to f + d. Chris@1654: * Chris@1654: * If overspill is greater than zero, also include that number of Chris@1654: * additional events (where they exist) both before and after the Chris@1654: * edges of the range. Chris@1635: */ Chris@1635: EventVector getEventsWithin(sv_frame_t frame, Chris@1654: sv_frame_t duration, Chris@1654: int overspill = 0) const; Chris@1635: Chris@1635: /** Chris@1638: * Retrieve all events starting within the range in frames defined Chris@1656: * by the given frame f and duration d. An event (regardless of Chris@1656: * whether it has duration or not) starts within the range if its Chris@1656: * start frame is greater than or equal to f and less than f + d. Chris@1638: */ Chris@1638: EventVector getEventsStartingWithin(sv_frame_t frame, Chris@1638: sv_frame_t duration) const; Chris@1638: Chris@1638: /** Chris@1656: * Retrieve all events starting at exactly the given frame. Chris@1612: */ Chris@1656: EventVector getEventsStartingAt(sv_frame_t frame) const { Chris@1656: return getEventsStartingWithin(frame, 1); Chris@1656: } Chris@1644: Chris@1644: /** Chris@1644: * Retrieve all events, in their natural order. Chris@1644: */ Chris@1644: EventVector getAllEvents() const; Chris@1635: Chris@1631: /** Chris@1632: * If e is in the series and is not the first event in it, set Chris@1632: * preceding to the event immediate preceding it according to the Chris@1632: * standard event ordering and return true. Otherwise leave Chris@1632: * preceding unchanged and return false. Chris@1632: * Chris@1632: * If there are multiple events identical to e in the series, Chris@1632: * assume that the event passed in is the first one (i.e. never Chris@1632: * set preceding equal to e). Chris@1633: * Chris@1633: * It is acceptable for preceding to alias e when this is called. Chris@1632: */ Chris@1632: bool getEventPreceding(const Event &e, Event &preceding) const; Chris@1632: Chris@1632: /** Chris@1632: * If e is in the series and is not the final event in it, set Chris@1632: * following to the event immediate following it according to the Chris@1632: * standard event ordering and return true. Otherwise leave Chris@1632: * following unchanged and return false. Chris@1632: * Chris@1632: * If there are multiple events identical to e in the series, Chris@1632: * assume that the event passed in is the last one (i.e. never set Chris@1632: * following equal to e). Chris@1633: * Chris@1633: * It is acceptable for following to alias e when this is called. Chris@1632: */ Chris@1632: bool getEventFollowing(const Event &e, Event &following) const; Chris@1632: Chris@1653: enum Direction { Chris@1653: Forward, Chris@1653: Backward Chris@1653: }; Chris@1653: Chris@1653: /** Chris@1653: * Return the first event for which the given predicate returns Chris@1653: * true, searching events with start frames increasingly far from Chris@1653: * the given frame in the given direction. If the direction is Chris@1653: * Forward then the search includes events starting at the given Chris@1653: * frame, otherwise it does not. Chris@1653: */ Chris@1653: bool getNearestEventMatching(sv_frame_t startSearchAt, Chris@1653: std::function predicate, Chris@1653: Direction direction, Chris@1653: Event &found) const; Chris@1653: Chris@1632: /** Chris@1632: * Return the event at the given numerical index in the series, Chris@1632: * where 0 = the first event and count()-1 = the last. Chris@1632: */ Chris@1632: Event getEventByIndex(int index) const; Chris@1640: Chris@1640: /** Chris@1640: * Return the index of the first event in the series that does not Chris@1640: * compare inferior to the given event. If there is no such event, Chris@1640: * return count(). Chris@1640: */ Chris@1640: int getIndexForEvent(const Event &e) const; Chris@1653: Chris@1632: /** Chris@1631: * Emit to XML as a dataset element. Chris@1631: */ Chris@1631: void toXml(QTextStream &out, Chris@1631: QString indent, Chris@1631: QString extraAttributes) const override; Chris@1631: Chris@1612: private: Chris@1616: /** Chris@1631: * This vector contains all events in the series, in the normal Chris@1631: * sort order. For backward compatibility we must support series Chris@1631: * containing multiple instances of identical events, so Chris@1631: * consecutive events in this vector will not always be distinct. Chris@1631: * The vector is used in preference to a multiset or map in order to allow indexing by "row number" as well as by Chris@1631: * properties such as frame. Chris@1631: * Chris@1631: * Because events are immutable, we do not have to worry about the Chris@1631: * order changing once an event is inserted - we only add or Chris@1631: * delete them. Chris@1616: */ Chris@1631: typedef std::vector Events; Chris@1616: Events m_events; Chris@1631: 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> FrameEventMap; Chris@1616: FrameEventMap m_seams; Chris@1614: Chris@1640: /** Chris@1640: * The frame of the last durationless event we have in the series. Chris@1640: * This is to support a fast-ish getEndFrame(): we can easily keep Chris@1640: * this up-to-date when events are added or removed, and we can Chris@1640: * easily find the end frame of the last with-duration event from Chris@1640: * the seam map, but it's not so easy to continuously update an Chris@1640: * overall end frame or to find the last frame of all events Chris@1640: * without this. Chris@1640: */ Chris@1640: sv_frame_t m_finalDurationlessEventFrame; Chris@1640: 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 &s1, Chris@1627: const std::vector &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 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@1631: std::cerr << " " << i.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