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@1612: #ifndef SV_POINT_SERIES_H
Chris@1612: #define SV_POINT_SERIES_H
Chris@1612: 
Chris@1612: #include "Point.h"
Chris@1612: 
Chris@1612: #include <set>
Chris@1612: 
Chris@1614: //#define DEBUG_POINT_SERIES 1
Chris@1614: 
Chris@1612: class PointSeries
Chris@1612: {
Chris@1612: public:
Chris@1612:     PointSeries() : m_count(0) { }
Chris@1612:     
Chris@1612:     void add(const Point &p) {
Chris@1612: 
Chris@1612:         m_points.insert(p);
Chris@1612:         ++m_count;
Chris@1612: 
Chris@1612:         if (p.haveDuration()) {
Chris@1612:             sv_frame_t frame = p.getFrame();
Chris@1612:             sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1612: 
Chris@1614:             createSeam(frame);
Chris@1614:             createSeam(endFrame);
Chris@1614:             
Chris@1614:             auto i0 = m_seams.find(frame); // must succeed after createSeam
Chris@1614:             auto i1 = m_seams.find(endFrame); // likewise
Chris@1614: 
Chris@1614:             for (auto i = i0; i != i1; ++i) {
Chris@1614:                 if (i == m_seams.end()) {
Chris@1614:                     SVCERR << "ERROR: PointSeries::add: "
Chris@1614:                            << "reached end of seam map"
Chris@1614:                            << endl;
Chris@1614:                     break;
Chris@1612:                 }
Chris@1614:                 i->second.insert(p);
Chris@1612:             }
Chris@1614:         }
Chris@1612: 
Chris@1614: #ifdef DEBUG_POINT_SERIES
Chris@1614:         std::cerr << "after add:" << std::endl;
Chris@1614:         dumpPoints();
Chris@1614:         dumpSeams();
Chris@1614: #endif
Chris@1612:     }
Chris@1612: 
Chris@1612:     void remove(const Point &p) {
Chris@1612: 
Chris@1612:         // erase first itr that matches p; if there is more than one
Chris@1612:         // p, erase(p) would remove all of them, but we only want to
Chris@1612:         // remove (any) one
Chris@1612:         auto pitr = m_points.find(p);
Chris@1612:         if (pitr == m_points.end()) {
Chris@1612:             return; // we don't know this point
Chris@1612:         } else {
Chris@1612:             m_points.erase(pitr);
Chris@1612:             --m_count;
Chris@1612:         }
Chris@1612: 
Chris@1612:         if (p.haveDuration()) {
Chris@1612:             sv_frame_t frame = p.getFrame();
Chris@1612:             sv_frame_t endFrame = p.getFrame() + p.getDuration();
Chris@1612: 
Chris@1614:             auto i0 = m_seams.find(frame);
Chris@1614:             auto i1 = m_seams.find(endFrame);
Chris@1614: 
Chris@1614: #ifdef DEBUG_POINT_SERIES
Chris@1614:             // This should be impossible if we found p in m_points above
Chris@1614:             if (i0 == m_seams.end() || i1 == m_seams.end()) {
Chris@1614:                 SVCERR << "ERROR: PointSeries::remove: either frame " << frame
Chris@1614:                        << " or endFrame " << endFrame
Chris@1612:                        << " for point not found in seam map: point is "
Chris@1612:                        << p.toXmlString() << endl;
Chris@1612:             }
Chris@1614: #endif
Chris@1612: 
Chris@1614:             for (auto i = i0; i != i1; ++i) {
Chris@1614:                 if (i == m_seams.end()) {
Chris@1614:                     SVCERR << "ERROR: PointSeries::remove: "
Chris@1614:                            << "reached end of seam map"
Chris@1614:                            << endl;
Chris@1614:                     break;
Chris@1614:                 }
Chris@1614:                 // Can't just erase(p) as that would erase all of
Chris@1614:                 // them, if there are several identical ones
Chris@1614:                 auto si = i->second.find(p);
Chris@1614:                 if (si != i->second.end()) {
Chris@1614:                     i->second.erase(si);
Chris@1614:                 }
Chris@1612:             }
Chris@1612: 
Chris@1612:             // Shall we "garbage-collect" here? We could be leaving
Chris@1612:             // lots of empty point-sets, or consecutive identical
Chris@1612:             // ones, which are a pure irrelevance that take space and
Chris@1612:             // slow us down. But a lot depends on whether callers ever
Chris@1612:             // really delete anything much.
Chris@1612:         }
Chris@1614: 
Chris@1614: #ifdef DEBUG_POINT_SERIES
Chris@1614:         std::cerr << "after remove:" << std::endl;
Chris@1614:         dumpPoints();
Chris@1614:         dumpSeams();
Chris@1614: #endif
Chris@1612:     }
Chris@1612: 
Chris@1612:     bool contains(const Point &p) {
Chris@1612:         return m_points.find(p) != m_points.end();
Chris@1612:     }
Chris@1612: 
Chris@1612:     int count() const {
Chris@1612:         return m_count;
Chris@1612:     }
Chris@1612: 
Chris@1612:     bool isEmpty() const {
Chris@1612:         return m_count == 0;
Chris@1612:     }
Chris@1612:     
Chris@1612:     void clear() {
Chris@1612:         m_points.clear();
Chris@1612:         m_seams.clear();
Chris@1612:         m_count = 0;
Chris@1612:     }
Chris@1612: 
Chris@1612:     /**
Chris@1612:      * Retrieve all points that span the given frame. A point without
Chris@1612:      * duration spans a frame if its own frame is equal to it. A point
Chris@1612:      * with duration spans a frame if its start frame is less than or
Chris@1612:      * equal to it and its end frame (start + duration) is greater
Chris@1612:      * than it.
Chris@1612:      */
Chris@1614:     PointVector getPointsSpanning(sv_frame_t frame) const {
Chris@1614:         PointVector span;
Chris@1614: 
Chris@1614:         // first find any zero-duration points
Chris@1614:         auto pitr = m_points.lower_bound(Point(frame, QString()));
Chris@1614:         if (pitr != m_points.end()) {
Chris@1614:             while (pitr->getFrame() == frame) {
Chris@1614:                 if (!pitr->haveDuration()) {
Chris@1614:                     span.push_back(*pitr);
Chris@1614:                 }
Chris@1614:                 ++pitr;
Chris@1614:             }
Chris@1614:         }
Chris@1614: 
Chris@1614:         // now any non-zero-duration ones from the seam map
Chris@1614:         auto sitr = m_seams.lower_bound(frame);
Chris@1614:         if (sitr == m_seams.end() || sitr->first > frame) {
Chris@1614:             if (sitr != m_seams.begin()) {
Chris@1614:                 --sitr;
Chris@1614:             }                
Chris@1614:         }
Chris@1614:         if (sitr != m_seams.end() && sitr->first <= frame) {
Chris@1614:             for (auto p: sitr->second) {
Chris@1614:                 span.push_back(p);
Chris@1614:             }
Chris@1614:         }
Chris@1614:         
Chris@1614:         return span;
Chris@1612:     }
Chris@1612: 
Chris@1612: private:
Chris@1612:     int m_count;
Chris@1614: 
Chris@1614:     typedef std::multiset<Point> PointMultiset;
Chris@1614:     PointMultiset m_points;
Chris@1614: 
Chris@1614:     typedef std::map<sv_frame_t, std::multiset<Point>> FramePointsMap;
Chris@1614:     FramePointsMap m_seams;
Chris@1614: 
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@1614:         auto itr = m_seams.lower_bound(frame);
Chris@1614:         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@1614:         } else if (itr->first < frame) {
Chris@1614:             m_seams[frame] = itr->second;
Chris@1614:         } else if (itr->first > frame) { // itr must be begin()
Chris@1614:             m_seams[frame] = {};
Chris@1614:         }
Chris@1614:     }
Chris@1614: 
Chris@1614: #ifdef DEBUG_POINT_SERIES
Chris@1614:     void dumpPoints() const {
Chris@1614:         std::cerr << "POINTS [" << std::endl;
Chris@1614:         for (const auto &p: m_points) {
Chris@1614:             std::cerr << p.toXmlString("  ");
Chris@1614:         }
Chris@1614:         std::cerr << "]" << std::endl;
Chris@1614:     }
Chris@1614:     
Chris@1614:     void dumpSeams() const {
Chris@1614:         std::cerr << "SEAMS [" << 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