annotate base/EventSeries.cpp @ 1631:b2048f350906 single-point

Switch EventSeries to using a vector for m_events, so as to allow indexed access
author Chris Cannam
date Tue, 12 Mar 2019 14:14:00 +0000
parents
children 0890c10e5129
rev   line source
Chris@1631 1 /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- vi:set ts=8 sts=4 sw=4: */
Chris@1631 2
Chris@1631 3 /*
Chris@1631 4 Sonic Visualiser
Chris@1631 5 An audio file viewer and annotation editor.
Chris@1631 6 Centre for Digital Music, Queen Mary, University of London.
Chris@1631 7
Chris@1631 8 This program is free software; you can redistribute it and/or
Chris@1631 9 modify it under the terms of the GNU General Public License as
Chris@1631 10 published by the Free Software Foundation; either version 2 of the
Chris@1631 11 License, or (at your option) any later version. See the file
Chris@1631 12 COPYING included with this distribution for more information.
Chris@1631 13 */
Chris@1631 14
Chris@1631 15 #include "EventSeries.h"
Chris@1631 16
Chris@1631 17 bool
Chris@1631 18 EventSeries::isEmpty() const
Chris@1631 19 {
Chris@1631 20 return m_events.empty();
Chris@1631 21 }
Chris@1631 22
Chris@1631 23 int
Chris@1631 24 EventSeries::count() const
Chris@1631 25 {
Chris@1631 26 if (m_events.size() > INT_MAX) {
Chris@1631 27 throw std::runtime_error("too many events");
Chris@1631 28 }
Chris@1631 29 return int(m_events.size());
Chris@1631 30 }
Chris@1631 31
Chris@1631 32 void
Chris@1631 33 EventSeries::add(const Event &p)
Chris@1631 34 {
Chris@1631 35 bool isUnique = true;
Chris@1631 36
Chris@1631 37 auto pitr = lower_bound(m_events.begin(), m_events.end(), p);
Chris@1631 38 if (pitr != m_events.end() && *pitr == p) {
Chris@1631 39 isUnique = false;
Chris@1631 40 }
Chris@1631 41 m_events.insert(pitr, p);
Chris@1631 42
Chris@1631 43 if (p.hasDuration() && isUnique) {
Chris@1631 44
Chris@1631 45 const sv_frame_t frame = p.getFrame();
Chris@1631 46 const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1631 47
Chris@1631 48 createSeam(frame);
Chris@1631 49 createSeam(endFrame);
Chris@1631 50
Chris@1631 51 // These calls must both succeed after calling createSeam above
Chris@1631 52 const auto i0 = m_seams.find(frame);
Chris@1631 53 const auto i1 = m_seams.find(endFrame);
Chris@1631 54
Chris@1631 55 for (auto i = i0; i != i1; ++i) {
Chris@1631 56 if (i == m_seams.end()) {
Chris@1631 57 SVCERR << "ERROR: EventSeries::add: "
Chris@1631 58 << "reached end of seam map"
Chris@1631 59 << endl;
Chris@1631 60 break;
Chris@1631 61 }
Chris@1631 62 i->second.push_back(p);
Chris@1631 63 }
Chris@1631 64 }
Chris@1631 65
Chris@1631 66 #ifdef DEBUG_EVENT_SERIES
Chris@1631 67 std::cerr << "after add:" << std::endl;
Chris@1631 68 dumpEvents();
Chris@1631 69 dumpSeams();
Chris@1631 70 #endif
Chris@1631 71 }
Chris@1631 72
Chris@1631 73 void
Chris@1631 74 EventSeries::remove(const Event &p)
Chris@1631 75 {
Chris@1631 76 // If we are removing the last (unique) example of an event,
Chris@1631 77 // then we also need to remove it from the seam map. If this
Chris@1631 78 // is only one of multiple identical events, then we don't.
Chris@1631 79 bool isUnique = true;
Chris@1631 80
Chris@1631 81 auto pitr = lower_bound(m_events.begin(), m_events.end(), p);
Chris@1631 82 if (pitr == m_events.end() || *pitr != p) {
Chris@1631 83 // we don't know this event
Chris@1631 84 return;
Chris@1631 85 } else {
Chris@1631 86 auto nitr = pitr;
Chris@1631 87 ++nitr;
Chris@1631 88 if (nitr != m_events.end() && *nitr == p) {
Chris@1631 89 isUnique = false;
Chris@1631 90 }
Chris@1631 91 }
Chris@1631 92
Chris@1631 93 m_events.erase(pitr);
Chris@1631 94
Chris@1631 95 if (p.hasDuration() && isUnique) {
Chris@1631 96
Chris@1631 97 const sv_frame_t frame = p.getFrame();
Chris@1631 98 const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1631 99
Chris@1631 100 const auto i0 = m_seams.find(frame);
Chris@1631 101 const auto i1 = m_seams.find(endFrame);
Chris@1631 102
Chris@1631 103 #ifdef DEBUG_EVENT_SERIES
Chris@1631 104 // This should be impossible if we found p in m_events above
Chris@1631 105 if (i0 == m_seams.end() || i1 == m_seams.end()) {
Chris@1631 106 SVCERR << "ERROR: EventSeries::remove: either frame " << frame
Chris@1631 107 << " or endFrame " << endFrame
Chris@1631 108 << " for event not found in seam map: event is "
Chris@1631 109 << p.toXmlString() << endl;
Chris@1631 110 }
Chris@1631 111 #endif
Chris@1631 112
Chris@1631 113 // Remove any and all instances of p from the seam map; we
Chris@1631 114 // are only supposed to get here if we are removing the
Chris@1631 115 // last instance of p from the series anyway
Chris@1631 116
Chris@1631 117 for (auto i = i0; i != i1; ++i) {
Chris@1631 118 if (i == m_seams.end()) {
Chris@1631 119 // This can happen only if we have a negative
Chris@1631 120 // duration, which Event forbids
Chris@1631 121 throw std::logic_error("unexpectedly reached end of map");
Chris@1631 122 }
Chris@1631 123 for (size_t j = 0; j < i->second.size(); ) {
Chris@1631 124 if (i->second[j] == p) {
Chris@1631 125 i->second.erase(i->second.begin() + j);
Chris@1631 126 } else {
Chris@1631 127 ++j;
Chris@1631 128 }
Chris@1631 129 }
Chris@1631 130 }
Chris@1631 131
Chris@1631 132 // Tidy up by removing any entries that are now identical
Chris@1631 133 // to their predecessors
Chris@1631 134
Chris@1631 135 std::vector<sv_frame_t> redundant;
Chris@1631 136
Chris@1631 137 auto pitr = m_seams.end();
Chris@1631 138 if (i0 != m_seams.begin()) {
Chris@1631 139 pitr = i0;
Chris@1631 140 --pitr;
Chris@1631 141 }
Chris@1631 142
Chris@1631 143 for (auto i = i0; i != m_seams.end(); ++i) {
Chris@1631 144 if (pitr != m_seams.end() &&
Chris@1631 145 seamsEqual(i->second, pitr->second)) {
Chris@1631 146 redundant.push_back(i->first);
Chris@1631 147 }
Chris@1631 148 pitr = i;
Chris@1631 149 if (i == i1) {
Chris@1631 150 break;
Chris@1631 151 }
Chris@1631 152 }
Chris@1631 153
Chris@1631 154 for (sv_frame_t f: redundant) {
Chris@1631 155 m_seams.erase(f);
Chris@1631 156 }
Chris@1631 157
Chris@1631 158 // And remove any empty seams from the start of the map
Chris@1631 159
Chris@1631 160 while (m_seams.begin() != m_seams.end() &&
Chris@1631 161 m_seams.begin()->second.empty()) {
Chris@1631 162 m_seams.erase(m_seams.begin());
Chris@1631 163 }
Chris@1631 164 }
Chris@1631 165
Chris@1631 166 #ifdef DEBUG_EVENT_SERIES
Chris@1631 167 std::cerr << "after remove:" << std::endl;
Chris@1631 168 dumpEvents();
Chris@1631 169 dumpSeams();
Chris@1631 170 #endif
Chris@1631 171 }
Chris@1631 172
Chris@1631 173 bool
Chris@1631 174 EventSeries::contains(const Event &p) const
Chris@1631 175 {
Chris@1631 176 return binary_search(m_events.begin(), m_events.end(), p);
Chris@1631 177 }
Chris@1631 178
Chris@1631 179 void
Chris@1631 180 EventSeries::clear()
Chris@1631 181 {
Chris@1631 182 m_events.clear();
Chris@1631 183 m_seams.clear();
Chris@1631 184 }
Chris@1631 185
Chris@1631 186 EventVector
Chris@1631 187 EventSeries::getEventsSpanning(sv_frame_t frame,
Chris@1631 188 sv_frame_t duration) const
Chris@1631 189 {
Chris@1631 190 EventVector span;
Chris@1631 191
Chris@1631 192 const sv_frame_t start = frame;
Chris@1631 193 const sv_frame_t end = frame + duration;
Chris@1631 194
Chris@1631 195 // first find any zero-duration events
Chris@1631 196
Chris@1631 197 auto pitr = lower_bound(m_events.begin(), m_events.end(),
Chris@1631 198 Event(start));
Chris@1631 199 while (pitr != m_events.end() && pitr->getFrame() < end) {
Chris@1631 200 if (!pitr->hasDuration()) {
Chris@1631 201 span.push_back(*pitr);
Chris@1631 202 }
Chris@1631 203 ++pitr;
Chris@1631 204 }
Chris@1631 205
Chris@1631 206 // now any non-zero-duration ones from the seam map
Chris@1631 207
Chris@1631 208 std::set<Event> found;
Chris@1631 209 auto sitr = m_seams.lower_bound(start);
Chris@1631 210 if (sitr == m_seams.end() || sitr->first > start) {
Chris@1631 211 if (sitr != m_seams.begin()) {
Chris@1631 212 --sitr;
Chris@1631 213 }
Chris@1631 214 }
Chris@1631 215 while (sitr != m_seams.end() && sitr->first < end) {
Chris@1631 216 for (const auto &p: sitr->second) {
Chris@1631 217 found.insert(p);
Chris@1631 218 }
Chris@1631 219 ++sitr;
Chris@1631 220 }
Chris@1631 221 for (const auto &p: found) {
Chris@1631 222 auto pitr = lower_bound(m_events.begin(), m_events.end(), p);
Chris@1631 223 while (pitr != m_events.end() && *pitr == p) {
Chris@1631 224 span.push_back(p);
Chris@1631 225 ++pitr;
Chris@1631 226 }
Chris@1631 227 }
Chris@1631 228
Chris@1631 229 return span;
Chris@1631 230 }
Chris@1631 231
Chris@1631 232 EventVector
Chris@1631 233 EventSeries::getEventsCovering(sv_frame_t frame) const
Chris@1631 234 {
Chris@1631 235 EventVector cover;
Chris@1631 236
Chris@1631 237 // first find any zero-duration events
Chris@1631 238
Chris@1631 239 auto pitr = lower_bound(m_events.begin(), m_events.end(),
Chris@1631 240 Event(frame));
Chris@1631 241 while (pitr != m_events.end() && pitr->getFrame() == frame) {
Chris@1631 242 if (!pitr->hasDuration()) {
Chris@1631 243 cover.push_back(*pitr);
Chris@1631 244 }
Chris@1631 245 ++pitr;
Chris@1631 246 }
Chris@1631 247
Chris@1631 248 // now any non-zero-duration ones from the seam map
Chris@1631 249
Chris@1631 250 std::set<Event> found;
Chris@1631 251 auto sitr = m_seams.lower_bound(frame);
Chris@1631 252 if (sitr == m_seams.end() || sitr->first > frame) {
Chris@1631 253 if (sitr != m_seams.begin()) {
Chris@1631 254 --sitr;
Chris@1631 255 }
Chris@1631 256 }
Chris@1631 257 if (sitr != m_seams.end() && sitr->first <= frame) {
Chris@1631 258 for (const auto &p: sitr->second) {
Chris@1631 259 found.insert(p);
Chris@1631 260 }
Chris@1631 261 ++sitr;
Chris@1631 262 }
Chris@1631 263 for (const auto &p: found) {
Chris@1631 264 auto pitr = lower_bound(m_events.begin(), m_events.end(), p);
Chris@1631 265 while (pitr != m_events.end() && *pitr == p) {
Chris@1631 266 cover.push_back(p);
Chris@1631 267 ++pitr;
Chris@1631 268 }
Chris@1631 269 }
Chris@1631 270
Chris@1631 271 return cover;
Chris@1631 272 }
Chris@1631 273
Chris@1631 274 void
Chris@1631 275 EventSeries::toXml(QTextStream &out,
Chris@1631 276 QString indent,
Chris@1631 277 QString extraAttributes) const
Chris@1631 278 {
Chris@1631 279 out << indent << QString("<dataset id=\"%1\" %2>\n")
Chris@1631 280 .arg(getObjectExportId(this))
Chris@1631 281 .arg(extraAttributes);
Chris@1631 282
Chris@1631 283 for (const auto &p: m_events) {
Chris@1631 284 p.toXml(out, indent + " ");
Chris@1631 285 }
Chris@1631 286
Chris@1631 287 out << indent << "</dataset>\n";
Chris@1631 288 }
Chris@1631 289
Chris@1631 290