Chris@1631: /* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
Chris@1631: 
Chris@1631: /*
Chris@1631:     Sonic Visualiser
Chris@1631:     An audio file viewer and annotation editor.
Chris@1631:     Centre for Digital Music, Queen Mary, University of London.
Chris@1631:     
Chris@1631:     This program is free software; you can redistribute it and/or
Chris@1631:     modify it under the terms of the GNU General Public License as
Chris@1631:     published by the Free Software Foundation; either version 2 of the
Chris@1631:     License, or (at your option) any later version.  See the file
Chris@1631:     COPYING included with this distribution for more information.
Chris@1631: */
Chris@1631: 
Chris@1631: #include "EventSeries.h"
Chris@1631: 
Chris@1631: bool
Chris@1631: EventSeries::isEmpty() const
Chris@1631: {
Chris@1631:     return m_events.empty();
Chris@1631: }
Chris@1631: 
Chris@1631: int
Chris@1631: EventSeries::count() const
Chris@1631: {
Chris@1631:     if (m_events.size() > INT_MAX) {
Chris@1632:         throw std::logic_error("too many events");
Chris@1631:     }
Chris@1631:     return int(m_events.size());
Chris@1631: }
Chris@1631: 
Chris@1631: void
Chris@1631: EventSeries::add(const Event &p)
Chris@1631: {
Chris@1631:     bool isUnique = true;
Chris@1631: 
Chris@1631:     auto pitr = lower_bound(m_events.begin(), m_events.end(), p);
Chris@1631:     if (pitr != m_events.end() && *pitr == p) {
Chris@1631:         isUnique = false;
Chris@1631:     }
Chris@1631:     m_events.insert(pitr, p);
Chris@1631: 
Chris@1631:     if (p.hasDuration() && isUnique) {
Chris@1631: 
Chris@1631:         const sv_frame_t frame = p.getFrame();
Chris@1631:         const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1631: 
Chris@1631:         createSeam(frame);
Chris@1631:         createSeam(endFrame);
Chris@1631: 
Chris@1631:         // These calls must both succeed after calling createSeam above
Chris@1631:         const auto i0 = m_seams.find(frame);
Chris@1631:         const auto i1 = m_seams.find(endFrame);
Chris@1631: 
Chris@1631:         for (auto i = i0; i != i1; ++i) {
Chris@1631:             if (i == m_seams.end()) {
Chris@1631:                 SVCERR << "ERROR: EventSeries::add: "
Chris@1631:                        << "reached end of seam map"
Chris@1631:                        << endl;
Chris@1631:                 break;
Chris@1631:             }
Chris@1631:             i->second.push_back(p);
Chris@1631:         }
Chris@1631:     }
Chris@1631: 
Chris@1631: #ifdef DEBUG_EVENT_SERIES
Chris@1631:     std::cerr << "after add:" << std::endl;
Chris@1631:     dumpEvents();
Chris@1631:     dumpSeams();
Chris@1631: #endif
Chris@1631: }
Chris@1631: 
Chris@1631: void
Chris@1631: EventSeries::remove(const Event &p)
Chris@1631: {
Chris@1631:     // If we are removing the last (unique) example of an event,
Chris@1631:     // then we also need to remove it from the seam map. If this
Chris@1631:     // is only one of multiple identical events, then we don't.
Chris@1631:     bool isUnique = true;
Chris@1631:         
Chris@1631:     auto pitr = lower_bound(m_events.begin(), m_events.end(), p);
Chris@1631:     if (pitr == m_events.end() || *pitr != p) {
Chris@1631:         // we don't know this event
Chris@1631:         return;
Chris@1631:     } else {
Chris@1631:         auto nitr = pitr;
Chris@1631:         ++nitr;
Chris@1631:         if (nitr != m_events.end() && *nitr == p) {
Chris@1631:             isUnique = false;
Chris@1631:         }
Chris@1631:     }
Chris@1631: 
Chris@1631:     m_events.erase(pitr);
Chris@1631: 
Chris@1631:     if (p.hasDuration() && isUnique) {
Chris@1631:             
Chris@1631:         const sv_frame_t frame = p.getFrame();
Chris@1631:         const sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1631: 
Chris@1631:         const auto i0 = m_seams.find(frame);
Chris@1631:         const auto i1 = m_seams.find(endFrame);
Chris@1631: 
Chris@1631: #ifdef DEBUG_EVENT_SERIES
Chris@1631:         // This should be impossible if we found p in m_events above
Chris@1631:         if (i0 == m_seams.end() || i1 == m_seams.end()) {
Chris@1631:             SVCERR << "ERROR: EventSeries::remove: either frame " << frame
Chris@1631:                    << " or endFrame " << endFrame
Chris@1631:                    << " for event not found in seam map: event is "
Chris@1631:                    << p.toXmlString() << endl;
Chris@1631:         }
Chris@1631: #endif
Chris@1631: 
Chris@1631:         // Remove any and all instances of p from the seam map; we
Chris@1631:         // are only supposed to get here if we are removing the
Chris@1631:         // last instance of p from the series anyway
Chris@1631:             
Chris@1631:         for (auto i = i0; i != i1; ++i) {
Chris@1631:             if (i == m_seams.end()) {
Chris@1631:                 // This can happen only if we have a negative
Chris@1631:                 // duration, which Event forbids
Chris@1631:                 throw std::logic_error("unexpectedly reached end of map");
Chris@1631:             }
Chris@1631:             for (size_t j = 0; j < i->second.size(); ) {
Chris@1631:                 if (i->second[j] == p) {
Chris@1631:                     i->second.erase(i->second.begin() + j);
Chris@1631:                 } else {
Chris@1631:                     ++j;
Chris@1631:                 }
Chris@1631:             }
Chris@1631:         }
Chris@1631: 
Chris@1631:         // Tidy up by removing any entries that are now identical
Chris@1631:         // to their predecessors
Chris@1631:             
Chris@1631:         std::vector<sv_frame_t> redundant;
Chris@1631: 
Chris@1631:         auto pitr = m_seams.end();
Chris@1631:         if (i0 != m_seams.begin()) {
Chris@1631:             pitr = i0;
Chris@1631:             --pitr;
Chris@1631:         }
Chris@1631: 
Chris@1631:         for (auto i = i0; i != m_seams.end(); ++i) {
Chris@1631:             if (pitr != m_seams.end() &&
Chris@1631:                 seamsEqual(i->second, pitr->second)) {
Chris@1631:                 redundant.push_back(i->first);
Chris@1631:             }
Chris@1631:             pitr = i;
Chris@1631:             if (i == i1) {
Chris@1631:                 break;
Chris@1631:             }
Chris@1631:         }
Chris@1631: 
Chris@1631:         for (sv_frame_t f: redundant) {
Chris@1631:             m_seams.erase(f);
Chris@1631:         }
Chris@1631: 
Chris@1631:         // And remove any empty seams from the start of the map
Chris@1631:             
Chris@1631:         while (m_seams.begin() != m_seams.end() &&
Chris@1631:                m_seams.begin()->second.empty()) {
Chris@1631:             m_seams.erase(m_seams.begin());
Chris@1631:         }
Chris@1631:     }
Chris@1631: 
Chris@1631: #ifdef DEBUG_EVENT_SERIES
Chris@1631:     std::cerr << "after remove:" << std::endl;
Chris@1631:     dumpEvents();
Chris@1631:     dumpSeams();
Chris@1631: #endif
Chris@1631: }
Chris@1631: 
Chris@1631: bool
Chris@1631: EventSeries::contains(const Event &p) const
Chris@1631: {
Chris@1631:     return binary_search(m_events.begin(), m_events.end(), p);
Chris@1631: }
Chris@1631: 
Chris@1631: void
Chris@1631: EventSeries::clear()
Chris@1631: {
Chris@1631:     m_events.clear();
Chris@1631:     m_seams.clear();
Chris@1631: }
Chris@1631: 
Chris@1631: EventVector
Chris@1631: EventSeries::getEventsSpanning(sv_frame_t frame,
Chris@1631:                                sv_frame_t duration) const
Chris@1631: {
Chris@1631:     EventVector span;
Chris@1631:     
Chris@1631:     const sv_frame_t start = frame;
Chris@1631:     const sv_frame_t end = frame + duration;
Chris@1631:         
Chris@1631:     // first find any zero-duration events
Chris@1631: 
Chris@1631:     auto pitr = lower_bound(m_events.begin(), m_events.end(),
Chris@1631:                             Event(start));
Chris@1631:     while (pitr != m_events.end() && pitr->getFrame() < end) {
Chris@1631:         if (!pitr->hasDuration()) {
Chris@1631:             span.push_back(*pitr);
Chris@1631:         }
Chris@1631:         ++pitr;
Chris@1631:     }
Chris@1631: 
Chris@1631:     // now any non-zero-duration ones from the seam map
Chris@1631: 
Chris@1631:     std::set<Event> found;
Chris@1631:     auto sitr = m_seams.lower_bound(start);
Chris@1631:     if (sitr == m_seams.end() || sitr->first > start) {
Chris@1631:         if (sitr != m_seams.begin()) {
Chris@1631:             --sitr;
Chris@1631:         }                
Chris@1631:     }
Chris@1631:     while (sitr != m_seams.end() && sitr->first < end) {
Chris@1631:         for (const auto &p: sitr->second) {
Chris@1631:             found.insert(p);
Chris@1631:         }
Chris@1631:         ++sitr;
Chris@1631:     }
Chris@1631:     for (const auto &p: found) {
Chris@1631:         auto pitr = lower_bound(m_events.begin(), m_events.end(), p);
Chris@1631:         while (pitr != m_events.end() && *pitr == p) {
Chris@1631:             span.push_back(p);
Chris@1631:             ++pitr;
Chris@1631:         }
Chris@1631:     }
Chris@1631:             
Chris@1631:     return span;
Chris@1631: }
Chris@1631: 
Chris@1631: EventVector
Chris@1636: EventSeries::getEventsWithin(sv_frame_t frame,
Chris@1636:                              sv_frame_t duration) const
Chris@1636: {
Chris@1636:     EventVector span;
Chris@1636:     
Chris@1636:     const sv_frame_t start = frame;
Chris@1636:     const sv_frame_t end = frame + duration;
Chris@1636: 
Chris@1636:     // because we don't need to "look back" at events that started
Chris@1636:     // earlier than the start of the given range, we can do this
Chris@1636:     // entirely from m_events
Chris@1636: 
Chris@1636:     auto pitr = lower_bound(m_events.begin(), m_events.end(),
Chris@1636:                             Event(start));
Chris@1636:     while (pitr != m_events.end() && pitr->getFrame() < end) {
Chris@1636:         if (!pitr->hasDuration()) {
Chris@1636:             span.push_back(*pitr);
Chris@1636:         } else if (pitr->getFrame() + pitr->getDuration() <= end) {
Chris@1636:             span.push_back(*pitr);
Chris@1636:         }
Chris@1636:         ++pitr;
Chris@1636:     }
Chris@1636:             
Chris@1636:     return span;
Chris@1636: }
Chris@1636: 
Chris@1636: EventVector
Chris@1631: EventSeries::getEventsCovering(sv_frame_t frame) const
Chris@1631: {
Chris@1631:     EventVector cover;
Chris@1631: 
Chris@1631:     // first find any zero-duration events
Chris@1631: 
Chris@1631:     auto pitr = lower_bound(m_events.begin(), m_events.end(),
Chris@1631:                             Event(frame));
Chris@1631:     while (pitr != m_events.end() && pitr->getFrame() == frame) {
Chris@1631:         if (!pitr->hasDuration()) {
Chris@1631:             cover.push_back(*pitr);
Chris@1631:         }
Chris@1631:         ++pitr;
Chris@1631:     }
Chris@1631:         
Chris@1631:     // now any non-zero-duration ones from the seam map
Chris@1631:         
Chris@1631:     std::set<Event> found;
Chris@1631:     auto sitr = m_seams.lower_bound(frame);
Chris@1631:     if (sitr == m_seams.end() || sitr->first > frame) {
Chris@1631:         if (sitr != m_seams.begin()) {
Chris@1631:             --sitr;
Chris@1631:         }                
Chris@1631:     }
Chris@1631:     if (sitr != m_seams.end() && sitr->first <= frame) {
Chris@1631:         for (const auto &p: sitr->second) {
Chris@1631:             found.insert(p);
Chris@1631:         }
Chris@1631:         ++sitr;
Chris@1631:     }
Chris@1631:     for (const auto &p: found) {
Chris@1631:         auto pitr = lower_bound(m_events.begin(), m_events.end(), p);
Chris@1631:         while (pitr != m_events.end() && *pitr == p) {
Chris@1631:             cover.push_back(p);
Chris@1631:             ++pitr;
Chris@1631:         }
Chris@1631:     }
Chris@1631:         
Chris@1631:     return cover;
Chris@1631: }
Chris@1631: 
Chris@1632: bool
Chris@1632: EventSeries::getEventPreceding(const Event &e, Event &preceding) const
Chris@1632: {
Chris@1632:     auto pitr = lower_bound(m_events.begin(), m_events.end(), e);
Chris@1632:     if (pitr == m_events.end() || *pitr != e) {
Chris@1632:         return false;
Chris@1632:     }
Chris@1632:     if (pitr == m_events.begin()) {
Chris@1632:         return false;
Chris@1632:     }
Chris@1632:     --pitr;
Chris@1632:     preceding = *pitr;
Chris@1632:     return true;
Chris@1632: }
Chris@1632: 
Chris@1632: bool
Chris@1632: EventSeries::getEventFollowing(const Event &e, Event &following) const
Chris@1632: {
Chris@1632:     auto pitr = lower_bound(m_events.begin(), m_events.end(), e);
Chris@1632:     if (pitr == m_events.end() || *pitr != e) {
Chris@1632:         return false;
Chris@1632:     }
Chris@1633:     while (*pitr == e) {
Chris@1633:         ++pitr;
Chris@1633:         if (pitr == m_events.end()) {
Chris@1633:             return false;
Chris@1633:         }
Chris@1632:     }
Chris@1632:     following = *pitr;
Chris@1632:     return true;
Chris@1632: }
Chris@1632: 
Chris@1632: Event
Chris@1632: EventSeries::getEventByIndex(int index) const
Chris@1632: {
Chris@1632:     if (index < 0 || index >= count()) {
Chris@1632:         throw std::logic_error("index out of range");
Chris@1632:     }
Chris@1632:     return m_events[index];
Chris@1632: }
Chris@1632: 
Chris@1631: void
Chris@1631: EventSeries::toXml(QTextStream &out,
Chris@1631:                    QString indent,
Chris@1631:                    QString extraAttributes) const
Chris@1631: {
Chris@1631:     out << indent << QString("<dataset id=\"%1\" %2>\n")
Chris@1631:         .arg(getObjectExportId(this))
Chris@1631:         .arg(extraAttributes);
Chris@1631:     
Chris@1631:     for (const auto &p: m_events) {
Chris@1631:         p.toXml(out, indent + "  ");
Chris@1631:     }
Chris@1631:     
Chris@1631:     out << indent << "</dataset>\n";
Chris@1631: }
Chris@1631: 
Chris@1631: