annotate base/EventSeries.h @ 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
parents 895186c43fce
children b2048f350906
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@1627 59 bool isUnique = true;
Chris@1627 60
Chris@1627 61 auto pitr = m_events.find(p);
Chris@1627 62 if (pitr != m_events.end()) {
Chris@1627 63 isUnique = false;
Chris@1627 64 }
Chris@1627 65
Chris@1616 66 ++m_events[p];
Chris@1612 67 ++m_count;
Chris@1612 68
Chris@1627 69 if (p.hasDuration() && isUnique) {
Chris@1617 70
Chris@1617 71 const sv_frame_t frame = p.getFrame();
Chris@1617 72 const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1612 73
Chris@1614 74 createSeam(frame);
Chris@1614 75 createSeam(endFrame);
Chris@1616 76
Chris@1616 77 // These calls must both succeed after calling createSeam above
Chris@1616 78 const auto i0 = m_seams.find(frame);
Chris@1616 79 const auto i1 = m_seams.find(endFrame);
Chris@1614 80
Chris@1614 81 for (auto i = i0; i != i1; ++i) {
Chris@1614 82 if (i == m_seams.end()) {
Chris@1615 83 SVCERR << "ERROR: EventSeries::add: "
Chris@1614 84 << "reached end of seam map"
Chris@1614 85 << endl;
Chris@1614 86 break;
Chris@1612 87 }
Chris@1627 88 i->second.push_back(p);
Chris@1612 89 }
Chris@1614 90 }
Chris@1612 91
Chris@1615 92 #ifdef DEBUG_EVENT_SERIES
Chris@1614 93 std::cerr << "after add:" << std::endl;
Chris@1615 94 dumpEvents();
Chris@1614 95 dumpSeams();
Chris@1614 96 #endif
Chris@1612 97 }
Chris@1612 98
Chris@1615 99 void remove(const Event &p) {
Chris@1612 100
Chris@1616 101 // If we are removing the last (unique) example of an event,
Chris@1616 102 // then we also need to remove it from the seam map. If this
Chris@1616 103 // is only one of multiple identical events, then we don't.
Chris@1616 104 bool isUnique = false;
Chris@1616 105
Chris@1615 106 auto pitr = m_events.find(p);
Chris@1615 107 if (pitr == m_events.end()) {
Chris@1615 108 return; // we don't know this event
Chris@1612 109 } else {
Chris@1625 110 if (--(pitr->second) == 0) {
Chris@1616 111 isUnique = true;
Chris@1616 112 m_events.erase(pitr);
Chris@1616 113 }
Chris@1612 114 --m_count;
Chris@1612 115 }
Chris@1612 116
Chris@1616 117 if (p.hasDuration() && isUnique) {
Chris@1616 118
Chris@1617 119 const sv_frame_t frame = p.getFrame();
Chris@1617 120 const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1612 121
Chris@1616 122 const auto i0 = m_seams.find(frame);
Chris@1616 123 const auto i1 = m_seams.find(endFrame);
Chris@1614 124
Chris@1615 125 #ifdef DEBUG_EVENT_SERIES
Chris@1615 126 // This should be impossible if we found p in m_events above
Chris@1614 127 if (i0 == m_seams.end() || i1 == m_seams.end()) {
Chris@1615 128 SVCERR << "ERROR: EventSeries::remove: either frame " << frame
Chris@1614 129 << " or endFrame " << endFrame
Chris@1615 130 << " for event not found in seam map: event is "
Chris@1612 131 << p.toXmlString() << endl;
Chris@1612 132 }
Chris@1614 133 #endif
Chris@1612 134
Chris@1627 135 // Remove any and all instances of p from the seam map; we
Chris@1627 136 // are only supposed to get here if we are removing the
Chris@1627 137 // last instance of p from the series anyway
Chris@1627 138
Chris@1614 139 for (auto i = i0; i != i1; ++i) {
Chris@1614 140 if (i == m_seams.end()) {
Chris@1615 141 // This can happen only if we have a negative
Chris@1616 142 // duration, which Event forbids
Chris@1616 143 throw std::logic_error("unexpectedly reached end of map");
Chris@1616 144 }
Chris@1626 145 for (size_t j = 0; j < i->second.size(); ) {
Chris@1627 146 if (i->second[j] == p) {
Chris@1626 147 i->second.erase(i->second.begin() + j);
Chris@1626 148 } else {
Chris@1626 149 ++j;
Chris@1626 150 }
Chris@1626 151 }
Chris@1616 152 }
Chris@1616 153
Chris@1616 154 // Tidy up by removing any entries that are now identical
Chris@1616 155 // to their predecessors
Chris@1626 156
Chris@1616 157 std::vector<sv_frame_t> redundant;
Chris@1616 158
Chris@1616 159 auto pitr = m_seams.end();
Chris@1616 160 if (i0 != m_seams.begin()) {
Chris@1616 161 pitr = i0;
Chris@1616 162 --pitr;
Chris@1616 163 }
Chris@1616 164
Chris@1616 165 for (auto i = i0; i != m_seams.end(); ++i) {
Chris@1627 166 if (pitr != m_seams.end() &&
Chris@1627 167 seamsEqual(i->second, pitr->second)) {
Chris@1625 168 redundant.push_back(i->first);
Chris@1616 169 }
Chris@1616 170 pitr = i;
Chris@1616 171 if (i == i1) {
Chris@1614 172 break;
Chris@1614 173 }
Chris@1612 174 }
Chris@1612 175
Chris@1616 176 for (sv_frame_t f: redundant) {
Chris@1625 177 m_seams.erase(f);
Chris@1616 178 }
Chris@1627 179
Chris@1627 180 // And remove any empty seams from the start of the map
Chris@1627 181
Chris@1627 182 while (m_seams.begin() != m_seams.end() &&
Chris@1627 183 m_seams.begin()->second.empty()) {
Chris@1627 184 m_seams.erase(m_seams.begin());
Chris@1627 185 }
Chris@1612 186 }
Chris@1614 187
Chris@1615 188 #ifdef DEBUG_EVENT_SERIES
Chris@1614 189 std::cerr << "after remove:" << std::endl;
Chris@1615 190 dumpEvents();
Chris@1614 191 dumpSeams();
Chris@1614 192 #endif
Chris@1612 193 }
Chris@1612 194
Chris@1615 195 bool contains(const Event &p) {
Chris@1615 196 return m_events.find(p) != m_events.end();
Chris@1612 197 }
Chris@1612 198
Chris@1612 199 int count() const {
Chris@1612 200 return m_count;
Chris@1612 201 }
Chris@1612 202
Chris@1612 203 bool isEmpty() const {
Chris@1612 204 return m_count == 0;
Chris@1612 205 }
Chris@1612 206
Chris@1612 207 void clear() {
Chris@1615 208 m_events.clear();
Chris@1612 209 m_seams.clear();
Chris@1612 210 m_count = 0;
Chris@1612 211 }
Chris@1612 212
Chris@1612 213 /**
Chris@1616 214 * Retrieve all events any part of which falls within the span in
Chris@1616 215 * frames defined by the given frame f and duration d.
Chris@1616 216 *
Chris@1616 217 * - An event without duration is within the span if its own frame
Chris@1616 218 * is greater than or equal to f and less than f + d.
Chris@1616 219 *
Chris@1616 220 * - An event with duration is within the span if its start frame
Chris@1616 221 * is less than f + d and its start frame plus its duration is
Chris@1616 222 * greater than f.
Chris@1616 223 *
Chris@1619 224 * Note: Passing a duration of zero is seldom useful here; you
Chris@1619 225 * probably want getEventsCovering instead. getEventsSpanning(f,
Chris@1619 226 * 0) is not equivalent to getEventsCovering(f). The latter
Chris@1619 227 * includes durationless events at f and events starting at f,
Chris@1619 228 * both of which are excluded from the former.
Chris@1616 229 */
Chris@1617 230 EventVector getEventsSpanning(sv_frame_t frame,
Chris@1617 231 sv_frame_t duration) const {
Chris@1616 232 EventVector span;
Chris@1616 233
Chris@1617 234 const sv_frame_t start = frame;
Chris@1617 235 const sv_frame_t end = frame + duration;
Chris@1616 236
Chris@1616 237 // first find any zero-duration events
Chris@1616 238
Chris@1625 239 auto pitr = m_events.lower_bound(Event(start, QString()));
Chris@1625 240 while (pitr != m_events.end() && pitr->first.getFrame() < end) {
Chris@1625 241 if (!pitr->first.hasDuration()) {
Chris@1625 242 for (int i = 0; i < pitr->second; ++i) {
Chris@1625 243 span.push_back(pitr->first);
Chris@1616 244 }
Chris@1616 245 }
Chris@1616 246 ++pitr;
Chris@1616 247 }
Chris@1616 248
Chris@1616 249 // now any non-zero-duration ones from the seam map
Chris@1616 250
Chris@1616 251 std::set<Event> found;
Chris@1625 252 auto sitr = m_seams.lower_bound(start);
Chris@1625 253 if (sitr == m_seams.end() || sitr->first > start) {
Chris@1616 254 if (sitr != m_seams.begin()) {
Chris@1616 255 --sitr;
Chris@1616 256 }
Chris@1616 257 }
Chris@1625 258 while (sitr != m_seams.end() && sitr->first < end) {
Chris@1627 259 for (const auto &p: sitr->second) {
Chris@1627 260 found.insert(p);
Chris@1616 261 }
Chris@1616 262 ++sitr;
Chris@1616 263 }
Chris@1616 264 for (const auto &p: found) {
Chris@1625 265 int n = m_events.at(p);
Chris@1616 266 if (n < 1) {
Chris@1616 267 throw std::logic_error("event is in seams but not events");
Chris@1616 268 }
Chris@1616 269 for (int i = 0; i < n; ++i) {
Chris@1616 270 span.push_back(p);
Chris@1616 271 }
Chris@1616 272 }
Chris@1616 273
Chris@1616 274 return span;
Chris@1616 275 }
Chris@1616 276
Chris@1616 277 /**
Chris@1616 278 * Retrieve all events that cover the given frame. An event without
Chris@1616 279 * duration covers a frame if its own frame is equal to it. An event
Chris@1616 280 * with duration covers a frame if its start frame is less than or
Chris@1612 281 * equal to it and its end frame (start + duration) is greater
Chris@1612 282 * than it.
Chris@1612 283 */
Chris@1616 284 EventVector getEventsCovering(sv_frame_t frame) const {
Chris@1616 285 EventVector cover;
Chris@1614 286
Chris@1615 287 // first find any zero-duration events
Chris@1616 288
Chris@1625 289 auto pitr = m_events.lower_bound(Event(frame, QString()));
Chris@1625 290 while (pitr != m_events.end() && pitr->first.getFrame() == frame) {
Chris@1625 291 if (!pitr->first.hasDuration()) {
Chris@1625 292 for (int i = 0; i < pitr->second; ++i) {
Chris@1625 293 cover.push_back(pitr->first);
Chris@1614 294 }
Chris@1614 295 }
Chris@1616 296 ++pitr;
Chris@1614 297 }
Chris@1614 298
Chris@1625 299 // now any non-zero-duration ones from the seam map
Chris@1616 300
Chris@1626 301 std::set<Event> found;
Chris@1625 302 auto sitr = m_seams.lower_bound(frame);
Chris@1625 303 if (sitr == m_seams.end() || sitr->first > frame) {
Chris@1614 304 if (sitr != m_seams.begin()) {
Chris@1614 305 --sitr;
Chris@1614 306 }
Chris@1614 307 }
Chris@1625 308 if (sitr != m_seams.end() && sitr->first <= frame) {
Chris@1627 309 for (const auto &p: sitr->second) {
Chris@1627 310 found.insert(p);
Chris@1626 311 }
Chris@1626 312 ++sitr;
Chris@1626 313 }
Chris@1626 314 for (const auto &p: found) {
Chris@1626 315 int n = m_events.at(p);
Chris@1626 316 if (n < 1) {
Chris@1626 317 throw std::logic_error("event is in seams but not events");
Chris@1626 318 }
Chris@1626 319 for (int i = 0; i < n; ++i) {
Chris@1626 320 cover.push_back(p);
Chris@1614 321 }
Chris@1614 322 }
Chris@1614 323
Chris@1616 324 return cover;
Chris@1612 325 }
Chris@1612 326
Chris@1612 327 private:
Chris@1616 328 /**
Chris@1616 329 * Total number of events in the series. Will exceed
Chris@1616 330 * m_events.size() if the series contains duplicate events.
Chris@1616 331 */
Chris@1612 332 int m_count;
Chris@1625 333
Chris@1616 334 /**
Chris@1616 335 * The (ordered) Events map acts as a list of all the events in
Chris@1616 336 * the series. For reasons of backward compatibility, we have to
Chris@1616 337 * handle series containing multiple instances of identical
Chris@1616 338 * events; the int indexed against each event records the number
Chris@1616 339 * of instances of that event. We do this in preference to using a
Chris@1616 340 * multiset, in order to support the case in which we have
Chris@1616 341 * obtained a set of distinct events (from the seam container
Chris@1616 342 * below) and then need to return the correct number of each.
Chris@1616 343 *
Chris@1616 344 * Because events are immutable, we never have to move one to a
Chris@1616 345 * different "key" in this map - we only add or delete them or
Chris@1616 346 * change their counts.
Chris@1616 347 */
Chris@1625 348 typedef std::map<Event, int> Events;
Chris@1616 349 Events m_events;
Chris@1614 350
Chris@1616 351 /**
Chris@1616 352 * The FrameEventMap maps from frame number to a set of events. In
Chris@1616 353 * the seam map this is used to represent the events that are
Chris@1616 354 * active at that frame, either because they begin at that frame
Chris@1616 355 * or because they are continuing from an earlier frame. There is
Chris@1616 356 * an entry here for each frame at which an event starts or ends,
Chris@1616 357 * with the event appearing in all entries from its start time
Chris@1616 358 * onward and disappearing again at its end frame.
Chris@1616 359 *
Chris@1616 360 * Only events with duration appear in this map; point events
Chris@1627 361 * appear only in m_events. Note that unlike m_events, we only
Chris@1627 362 * store one instance of each event here, even if we hold many -
Chris@1627 363 * we refer back to m_events when we need to know how many
Chris@1627 364 * identical copies of a given event we have.
Chris@1616 365 */
Chris@1627 366 typedef std::map<sv_frame_t, std::vector<Event>> FrameEventMap;
Chris@1616 367 FrameEventMap m_seams;
Chris@1614 368
Chris@1614 369 /** Create a seam at the given frame, copying from the prior seam
Chris@1614 370 * if there is one. If a seam already exists at the given frame,
Chris@1614 371 * leave it untouched.
Chris@1614 372 */
Chris@1614 373 void createSeam(sv_frame_t frame) {
Chris@1625 374 auto itr = m_seams.lower_bound(frame);
Chris@1625 375 if (itr == m_seams.end() || itr->first > frame) {
Chris@1614 376 if (itr != m_seams.begin()) {
Chris@1614 377 --itr;
Chris@1614 378 }
Chris@1614 379 }
Chris@1614 380 if (itr == m_seams.end()) {
Chris@1614 381 m_seams[frame] = {};
Chris@1625 382 } else if (itr->first < frame) {
Chris@1625 383 m_seams[frame] = itr->second;
Chris@1625 384 } else if (itr->first > frame) { // itr must be begin()
Chris@1614 385 m_seams[frame] = {};
Chris@1614 386 }
Chris@1614 387 }
Chris@1614 388
Chris@1627 389 bool seamsEqual(const std::vector<Event> &s1,
Chris@1627 390 const std::vector<Event> &s2) const {
Chris@1627 391
Chris@1627 392 if (s1.size() != s2.size()) {
Chris@1627 393 return false;
Chris@1627 394 }
Chris@1627 395
Chris@1627 396 // precondition: no event appears more than once in s1 or more
Chris@1627 397 // than once in s2
Chris@1627 398
Chris@1627 399 #ifdef DEBUG_EVENT_SERIES
Chris@1627 400 for (int i = 0; in_range_for(s1, i); ++i) {
Chris@1627 401 for (int j = i + 1; in_range_for(s1, j); ++j) {
Chris@1627 402 if (s1[i] == s1[j] || s2[i] == s2[j]) {
Chris@1627 403 throw std::runtime_error
Chris@1627 404 ("debug error: duplicate event in s1 or s2");
Chris@1627 405 }
Chris@1627 406 }
Chris@1627 407 }
Chris@1627 408 #endif
Chris@1627 409
Chris@1627 410 std::set<Event> ee;
Chris@1627 411 for (const auto &e: s1) {
Chris@1627 412 ee.insert(e);
Chris@1627 413 }
Chris@1627 414 for (const auto &e: s2) {
Chris@1627 415 if (ee.find(e) == ee.end()) {
Chris@1627 416 return false;
Chris@1627 417 }
Chris@1627 418 }
Chris@1627 419 return true;
Chris@1627 420 }
Chris@1627 421
Chris@1615 422 #ifdef DEBUG_EVENT_SERIES
Chris@1615 423 void dumpEvents() const {
Chris@1618 424 std::cerr << "EVENTS (" << m_events.size() << ") [" << std::endl;
Chris@1616 425 for (const auto &i: m_events) {
Chris@1618 426 std::cerr << " " << i.second << "x " << i.first.toXmlString();
Chris@1614 427 }
Chris@1614 428 std::cerr << "]" << std::endl;
Chris@1614 429 }
Chris@1614 430
Chris@1614 431 void dumpSeams() const {
Chris@1618 432 std::cerr << "SEAMS (" << m_seams.size() << ") [" << std::endl;
Chris@1614 433 for (const auto &s: m_seams) {
Chris@1614 434 std::cerr << " " << s.first << " -> {" << std::endl;
Chris@1614 435 for (const auto &p: s.second) {
Chris@1614 436 std::cerr << p.toXmlString(" ");
Chris@1614 437 }
Chris@1614 438 std::cerr << " }" << std::endl;
Chris@1614 439 }
Chris@1614 440 std::cerr << "]" << std::endl;
Chris@1614 441 }
Chris@1614 442 #endif
Chris@1612 443 };
Chris@1612 444
Chris@1612 445 #endif