annotate base/EventSeries.h @ 1625:7dbb2a7b592e single-point

That last change didn't seem worthwhile
author Chris Cannam
date Mon, 11 Mar 2019 11:25:17 +0000
parents dcd510bd89db
children 895186c43fce
rev   line source
Chris@1612 1 /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- vi:set ts=8 sts=4 sw=4: */
Chris@1612 2
Chris@1612 3 /*
Chris@1612 4 Sonic Visualiser
Chris@1612 5 An audio file viewer and annotation editor.
Chris@1612 6 Centre for Digital Music, Queen Mary, University of London.
Chris@1612 7
Chris@1612 8 This program is free software; you can redistribute it and/or
Chris@1612 9 modify it under the terms of the GNU General Public License as
Chris@1612 10 published by the Free Software Foundation; either version 2 of the
Chris@1612 11 License, or (at your option) any later version. See the file
Chris@1612 12 COPYING included with this distribution for more information.
Chris@1612 13 */
Chris@1612 14
Chris@1615 15 #ifndef SV_EVENT_SERIES_H
Chris@1615 16 #define SV_EVENT_SERIES_H
Chris@1612 17
Chris@1615 18 #include "Event.h"
Chris@1612 19
Chris@1612 20 #include <set>
Chris@1612 21
Chris@1615 22 //#define DEBUG_EVENT_SERIES 1
Chris@1614 23
Chris@1615 24 /**
Chris@1615 25 * Container storing a series of events, with or without durations,
Chris@1616 26 * and supporting the ability to query which events are active at a
Chris@1616 27 * given frame or within a span of frames.
Chris@1616 28 *
Chris@1616 29 * To that end, in addition to the series of events, it stores a
Chris@1616 30 * series of "seams", which are frame positions at which the set of
Chris@1616 31 * simultaneous events changes (i.e. an event of non-zero duration
Chris@1616 32 * starts or ends) associated with a set of the events that are active
Chris@1616 33 * at or from that position. These are updated when an event is added
Chris@1616 34 * or removed.
Chris@1618 35 *
Chris@1618 36 * Performance is highly dependent on the extent of overlapping events
Chris@1618 37 * and the order in which events are added. Each event (with duration)
Chris@1618 38 * that is added requires updating all the seams within the extent of
Chris@1618 39 * that event, taking a number of ordered-set updates proportional to
Chris@1618 40 * the number of events already existing within its extent. Add events
Chris@1618 41 * in order of start frame if possible.
Chris@1615 42 */
Chris@1615 43 class EventSeries
Chris@1612 44 {
Chris@1612 45 public:
Chris@1615 46 EventSeries() : m_count(0) { }
Chris@1616 47 ~EventSeries() =default;
Chris@1616 48
Chris@1616 49 EventSeries(const EventSeries &) =default;
Chris@1616 50 EventSeries &operator=(const EventSeries &) =default;
Chris@1616 51 EventSeries &operator=(EventSeries &&) =default;
Chris@1616 52
Chris@1616 53 bool operator==(const EventSeries &other) const {
Chris@1616 54 return m_events == other.m_events;
Chris@1616 55 }
Chris@1612 56
Chris@1615 57 void add(const Event &p) {
Chris@1612 58
Chris@1616 59 ++m_events[p];
Chris@1612 60 ++m_count;
Chris@1612 61
Chris@1615 62 if (p.hasDuration()) {
Chris@1617 63
Chris@1617 64 const sv_frame_t frame = p.getFrame();
Chris@1617 65 const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1612 66
Chris@1614 67 createSeam(frame);
Chris@1614 68 createSeam(endFrame);
Chris@1616 69
Chris@1616 70 // These calls must both succeed after calling createSeam above
Chris@1616 71 const auto i0 = m_seams.find(frame);
Chris@1616 72 const auto i1 = m_seams.find(endFrame);
Chris@1614 73
Chris@1614 74 for (auto i = i0; i != i1; ++i) {
Chris@1614 75 if (i == m_seams.end()) {
Chris@1615 76 SVCERR << "ERROR: EventSeries::add: "
Chris@1614 77 << "reached end of seam map"
Chris@1614 78 << endl;
Chris@1614 79 break;
Chris@1612 80 }
Chris@1625 81 i->second.insert(p);
Chris@1612 82 }
Chris@1614 83 }
Chris@1612 84
Chris@1615 85 #ifdef DEBUG_EVENT_SERIES
Chris@1614 86 std::cerr << "after add:" << std::endl;
Chris@1615 87 dumpEvents();
Chris@1614 88 dumpSeams();
Chris@1614 89 #endif
Chris@1612 90 }
Chris@1612 91
Chris@1615 92 void remove(const Event &p) {
Chris@1612 93
Chris@1616 94 // If we are removing the last (unique) example of an event,
Chris@1616 95 // then we also need to remove it from the seam map. If this
Chris@1616 96 // is only one of multiple identical events, then we don't.
Chris@1616 97 bool isUnique = false;
Chris@1616 98
Chris@1615 99 auto pitr = m_events.find(p);
Chris@1615 100 if (pitr == m_events.end()) {
Chris@1615 101 return; // we don't know this event
Chris@1612 102 } else {
Chris@1625 103 if (--(pitr->second) == 0) {
Chris@1616 104 isUnique = true;
Chris@1616 105 m_events.erase(pitr);
Chris@1616 106 }
Chris@1612 107 --m_count;
Chris@1612 108 }
Chris@1612 109
Chris@1616 110 if (p.hasDuration() && isUnique) {
Chris@1616 111
Chris@1617 112 const sv_frame_t frame = p.getFrame();
Chris@1617 113 const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1612 114
Chris@1616 115 const auto i0 = m_seams.find(frame);
Chris@1616 116 const auto i1 = m_seams.find(endFrame);
Chris@1614 117
Chris@1615 118 #ifdef DEBUG_EVENT_SERIES
Chris@1615 119 // This should be impossible if we found p in m_events above
Chris@1614 120 if (i0 == m_seams.end() || i1 == m_seams.end()) {
Chris@1615 121 SVCERR << "ERROR: EventSeries::remove: either frame " << frame
Chris@1614 122 << " or endFrame " << endFrame
Chris@1615 123 << " for event not found in seam map: event is "
Chris@1612 124 << p.toXmlString() << endl;
Chris@1612 125 }
Chris@1614 126 #endif
Chris@1612 127
Chris@1614 128 for (auto i = i0; i != i1; ++i) {
Chris@1614 129 if (i == m_seams.end()) {
Chris@1615 130 // This can happen only if we have a negative
Chris@1616 131 // duration, which Event forbids
Chris@1616 132 throw std::logic_error("unexpectedly reached end of map");
Chris@1616 133 }
Chris@1616 134
Chris@1625 135 i->second.erase(p);
Chris@1616 136 }
Chris@1616 137
Chris@1616 138 // Tidy up by removing any entries that are now identical
Chris@1616 139 // to their predecessors
Chris@1616 140
Chris@1616 141 std::vector<sv_frame_t> redundant;
Chris@1616 142
Chris@1616 143 auto pitr = m_seams.end();
Chris@1616 144 if (i0 != m_seams.begin()) {
Chris@1616 145 pitr = i0;
Chris@1616 146 --pitr;
Chris@1616 147 }
Chris@1616 148
Chris@1616 149 for (auto i = i0; i != m_seams.end(); ++i) {
Chris@1625 150 if (pitr != m_seams.end() && i->second == pitr->second) {
Chris@1625 151 redundant.push_back(i->first);
Chris@1616 152 }
Chris@1616 153 pitr = i;
Chris@1616 154 if (i == i1) {
Chris@1614 155 break;
Chris@1614 156 }
Chris@1612 157 }
Chris@1612 158
Chris@1616 159 for (sv_frame_t f: redundant) {
Chris@1625 160 m_seams.erase(f);
Chris@1616 161 }
Chris@1612 162 }
Chris@1614 163
Chris@1615 164 #ifdef DEBUG_EVENT_SERIES
Chris@1614 165 std::cerr << "after remove:" << std::endl;
Chris@1615 166 dumpEvents();
Chris@1614 167 dumpSeams();
Chris@1614 168 #endif
Chris@1612 169 }
Chris@1612 170
Chris@1615 171 bool contains(const Event &p) {
Chris@1615 172 return m_events.find(p) != m_events.end();
Chris@1612 173 }
Chris@1612 174
Chris@1612 175 int count() const {
Chris@1612 176 return m_count;
Chris@1612 177 }
Chris@1612 178
Chris@1612 179 bool isEmpty() const {
Chris@1612 180 return m_count == 0;
Chris@1612 181 }
Chris@1612 182
Chris@1612 183 void clear() {
Chris@1615 184 m_events.clear();
Chris@1612 185 m_seams.clear();
Chris@1612 186 m_count = 0;
Chris@1612 187 }
Chris@1612 188
Chris@1612 189 /**
Chris@1616 190 * Retrieve all events any part of which falls within the span in
Chris@1616 191 * frames defined by the given frame f and duration d.
Chris@1616 192 *
Chris@1616 193 * - An event without duration is within the span if its own frame
Chris@1616 194 * is greater than or equal to f and less than f + d.
Chris@1616 195 *
Chris@1616 196 * - An event with duration is within the span if its start frame
Chris@1616 197 * is less than f + d and its start frame plus its duration is
Chris@1616 198 * greater than f.
Chris@1616 199 *
Chris@1619 200 * Note: Passing a duration of zero is seldom useful here; you
Chris@1619 201 * probably want getEventsCovering instead. getEventsSpanning(f,
Chris@1619 202 * 0) is not equivalent to getEventsCovering(f). The latter
Chris@1619 203 * includes durationless events at f and events starting at f,
Chris@1619 204 * both of which are excluded from the former.
Chris@1616 205 */
Chris@1617 206 EventVector getEventsSpanning(sv_frame_t frame,
Chris@1617 207 sv_frame_t duration) const {
Chris@1616 208 EventVector span;
Chris@1616 209
Chris@1617 210 const sv_frame_t start = frame;
Chris@1617 211 const sv_frame_t end = frame + duration;
Chris@1616 212
Chris@1616 213 // first find any zero-duration events
Chris@1616 214
Chris@1625 215 auto pitr = m_events.lower_bound(Event(start, QString()));
Chris@1625 216 while (pitr != m_events.end() && pitr->first.getFrame() < end) {
Chris@1625 217 if (!pitr->first.hasDuration()) {
Chris@1625 218 for (int i = 0; i < pitr->second; ++i) {
Chris@1625 219 span.push_back(pitr->first);
Chris@1616 220 }
Chris@1616 221 }
Chris@1616 222 ++pitr;
Chris@1616 223 }
Chris@1616 224
Chris@1616 225 // now any non-zero-duration ones from the seam map
Chris@1616 226
Chris@1616 227 std::set<Event> found;
Chris@1625 228 auto sitr = m_seams.lower_bound(start);
Chris@1625 229 if (sitr == m_seams.end() || sitr->first > start) {
Chris@1616 230 if (sitr != m_seams.begin()) {
Chris@1616 231 --sitr;
Chris@1616 232 }
Chris@1616 233 }
Chris@1625 234 while (sitr != m_seams.end() && sitr->first < end) {
Chris@1625 235 for (const auto &p: sitr->second) {
Chris@1616 236 found.insert(p);
Chris@1616 237 }
Chris@1616 238 ++sitr;
Chris@1616 239 }
Chris@1616 240 for (const auto &p: found) {
Chris@1625 241 int n = m_events.at(p);
Chris@1616 242 if (n < 1) {
Chris@1616 243 throw std::logic_error("event is in seams but not events");
Chris@1616 244 }
Chris@1616 245 for (int i = 0; i < n; ++i) {
Chris@1616 246 span.push_back(p);
Chris@1616 247 }
Chris@1616 248 }
Chris@1616 249
Chris@1616 250 return span;
Chris@1616 251 }
Chris@1616 252
Chris@1616 253 /**
Chris@1616 254 * Retrieve all events that cover the given frame. An event without
Chris@1616 255 * duration covers a frame if its own frame is equal to it. An event
Chris@1616 256 * with duration covers a frame if its start frame is less than or
Chris@1612 257 * equal to it and its end frame (start + duration) is greater
Chris@1612 258 * than it.
Chris@1612 259 */
Chris@1616 260 EventVector getEventsCovering(sv_frame_t frame) const {
Chris@1616 261 EventVector cover;
Chris@1614 262
Chris@1615 263 // first find any zero-duration events
Chris@1616 264
Chris@1625 265 auto pitr = m_events.lower_bound(Event(frame, QString()));
Chris@1625 266 while (pitr != m_events.end() && pitr->first.getFrame() == frame) {
Chris@1625 267 if (!pitr->first.hasDuration()) {
Chris@1625 268 for (int i = 0; i < pitr->second; ++i) {
Chris@1625 269 cover.push_back(pitr->first);
Chris@1614 270 }
Chris@1614 271 }
Chris@1616 272 ++pitr;
Chris@1614 273 }
Chris@1614 274
Chris@1625 275 // now any non-zero-duration ones from the seam map
Chris@1616 276
Chris@1625 277 auto sitr = m_seams.lower_bound(frame);
Chris@1625 278 if (sitr == m_seams.end() || sitr->first > frame) {
Chris@1614 279 if (sitr != m_seams.begin()) {
Chris@1614 280 --sitr;
Chris@1614 281 }
Chris@1614 282 }
Chris@1625 283 if (sitr != m_seams.end() && sitr->first <= frame) {
Chris@1625 284 for (const auto &p: sitr->second) {
Chris@1625 285 int n = m_events.at(p);
Chris@1625 286 if (n < 1) {
Chris@1625 287 throw std::logic_error("event is in seams but not events");
Chris@1625 288 }
Chris@1625 289 for (int i = 0; i < n; ++i) {
Chris@1625 290 cover.push_back(p);
Chris@1625 291 }
Chris@1614 292 }
Chris@1614 293 }
Chris@1614 294
Chris@1616 295 return cover;
Chris@1612 296 }
Chris@1612 297
Chris@1612 298 private:
Chris@1616 299 /**
Chris@1616 300 * Total number of events in the series. Will exceed
Chris@1616 301 * m_events.size() if the series contains duplicate events.
Chris@1616 302 */
Chris@1612 303 int m_count;
Chris@1625 304
Chris@1616 305 /**
Chris@1616 306 * The (ordered) Events map acts as a list of all the events in
Chris@1616 307 * the series. For reasons of backward compatibility, we have to
Chris@1616 308 * handle series containing multiple instances of identical
Chris@1616 309 * events; the int indexed against each event records the number
Chris@1616 310 * of instances of that event. We do this in preference to using a
Chris@1616 311 * multiset, in order to support the case in which we have
Chris@1616 312 * obtained a set of distinct events (from the seam container
Chris@1616 313 * below) and then need to return the correct number of each.
Chris@1616 314 *
Chris@1616 315 * Because events are immutable, we never have to move one to a
Chris@1616 316 * different "key" in this map - we only add or delete them or
Chris@1616 317 * change their counts.
Chris@1616 318 */
Chris@1625 319 typedef std::map<Event, int> Events;
Chris@1616 320 Events m_events;
Chris@1614 321
Chris@1616 322 /**
Chris@1616 323 * The FrameEventMap maps from frame number to a set of events. In
Chris@1616 324 * the seam map this is used to represent the events that are
Chris@1616 325 * active at that frame, either because they begin at that frame
Chris@1616 326 * or because they are continuing from an earlier frame. There is
Chris@1616 327 * an entry here for each frame at which an event starts or ends,
Chris@1616 328 * with the event appearing in all entries from its start time
Chris@1616 329 * onward and disappearing again at its end frame.
Chris@1616 330 *
Chris@1616 331 * Only events with duration appear in this map; point events
Chris@1616 332 * appear only in m_events.
Chris@1616 333 */
Chris@1625 334 typedef std::map<sv_frame_t, std::set<Event>> FrameEventMap;
Chris@1616 335 FrameEventMap m_seams;
Chris@1614 336
Chris@1614 337 /** Create a seam at the given frame, copying from the prior seam
Chris@1614 338 * if there is one. If a seam already exists at the given frame,
Chris@1614 339 * leave it untouched.
Chris@1614 340 */
Chris@1614 341 void createSeam(sv_frame_t frame) {
Chris@1625 342 auto itr = m_seams.lower_bound(frame);
Chris@1625 343 if (itr == m_seams.end() || itr->first > frame) {
Chris@1614 344 if (itr != m_seams.begin()) {
Chris@1614 345 --itr;
Chris@1614 346 }
Chris@1614 347 }
Chris@1614 348 if (itr == m_seams.end()) {
Chris@1614 349 m_seams[frame] = {};
Chris@1625 350 } else if (itr->first < frame) {
Chris@1625 351 m_seams[frame] = itr->second;
Chris@1625 352 } else if (itr->first > frame) { // itr must be begin()
Chris@1614 353 m_seams[frame] = {};
Chris@1614 354 }
Chris@1614 355 }
Chris@1614 356
Chris@1615 357 #ifdef DEBUG_EVENT_SERIES
Chris@1615 358 void dumpEvents() const {
Chris@1618 359 std::cerr << "EVENTS (" << m_events.size() << ") [" << std::endl;
Chris@1616 360 for (const auto &i: m_events) {
Chris@1618 361 std::cerr << " " << i.second << "x " << i.first.toXmlString();
Chris@1614 362 }
Chris@1614 363 std::cerr << "]" << std::endl;
Chris@1614 364 }
Chris@1614 365
Chris@1614 366 void dumpSeams() const {
Chris@1618 367 std::cerr << "SEAMS (" << m_seams.size() << ") [" << std::endl;
Chris@1614 368 for (const auto &s: m_seams) {
Chris@1614 369 std::cerr << " " << s.first << " -> {" << std::endl;
Chris@1614 370 for (const auto &p: s.second) {
Chris@1614 371 std::cerr << p.toXmlString(" ");
Chris@1614 372 }
Chris@1614 373 std::cerr << " }" << std::endl;
Chris@1614 374 }
Chris@1614 375 std::cerr << "]" << std::endl;
Chris@1614 376 }
Chris@1614 377 #endif
Chris@1612 378 };
Chris@1612 379
Chris@1612 380 #endif