Mercurial > hg > svcore

changeset 1614:2e14a7876945 single-point

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fixes and tests for PointSeries
author Chris Cannam
date Thu, 07 Mar 2019 14:35:57 +0000
parents ea4f3593c39c
children 24dc8cb42755
files base/PointSeries.h base/test/TestPointSeries.h data/model/SparseModel.h data/model/test/TestSparseModels.h
diffstat 4 files changed, 270 insertions(+), 39 deletions(-) [+]
line wrap: on
line diff
--- a/base/PointSeries.h	Wed Mar 06 16:37:10 2019 +0000
+++ b/base/PointSeries.h	Thu Mar 07 14:35:57 2019 +0000
@@ -19,6 +19,8 @@
 
 #include <set>
 
+//#define DEBUG_POINT_SERIES 1
+
 class PointSeries
 {
 public:
@@ -33,26 +35,28 @@
             sv_frame_t frame = p.getFrame();
             sv_frame_t endFrame = p.getFrame() + p.getDuration();
 
-            std::set<Point> active;
-            auto itr = m_seams.lower_bound(frame);
-            if (itr == m_seams.end() || itr->first > frame) {
-                if (itr != m_seams.begin()) {
-                    --itr;
+            createSeam(frame);
+            createSeam(endFrame);
+            
+            auto i0 = m_seams.find(frame); // must succeed after createSeam
+            auto i1 = m_seams.find(endFrame); // likewise
+
+            for (auto i = i0; i != i1; ++i) {
+                if (i == m_seams.end()) {
+                    SVCERR << "ERROR: PointSeries::add: "
+                           << "reached end of seam map"
+                           << endl;
+                    break;
                 }
+                i->second.insert(p);
             }
-            if (itr != m_seams.end()) {
-                active = itr->second;
-            }
-            active.insert(p);
-            m_seams[frame] = active;
+        }
 
-            for (itr = m_seams.find(frame); itr->first < endFrame; ++itr) {
-                active = itr->second;
-                itr->second.insert(p);
-            }
-
-            m_seams[endFrame] = active;
-        }
+#ifdef DEBUG_POINT_SERIES
+        std::cerr << "after add:" << std::endl;
+        dumpPoints();
+        dumpSeams();
+#endif
     }
 
     void remove(const Point &p) {
@@ -72,17 +76,32 @@
             sv_frame_t frame = p.getFrame();
             sv_frame_t endFrame = p.getFrame() + p.getDuration();
 
-            auto itr = m_seams.find(frame);
-            if (itr == m_seams.end()) {
-                SVCERR << "WARNING: PointSeries::remove: frame " << frame
+            auto i0 = m_seams.find(frame);
+            auto i1 = m_seams.find(endFrame);
+
+#ifdef DEBUG_POINT_SERIES
+            // This should be impossible if we found p in m_points above
+            if (i0 == m_seams.end() || i1 == m_seams.end()) {
+                SVCERR << "ERROR: PointSeries::remove: either frame " << frame
+                       << " or endFrame " << endFrame
                        << " for point not found in seam map: point is "
                        << p.toXmlString() << endl;
-                return;
             }
+#endif
 
-            while (itr != m_seams.end() && itr->first <= endFrame) {
-                itr->second.erase(p);
-                ++itr;
+            for (auto i = i0; i != i1; ++i) {
+                if (i == m_seams.end()) {
+                    SVCERR << "ERROR: PointSeries::remove: "
+                           << "reached end of seam map"
+                           << endl;
+                    break;
+                }
+                // Can't just erase(p) as that would erase all of
+                // them, if there are several identical ones
+                auto si = i->second.find(p);
+                if (si != i->second.end()) {
+                    i->second.erase(si);
+                }
             }
 
             // Shall we "garbage-collect" here? We could be leaving
@@ -91,6 +110,12 @@
             // slow us down. But a lot depends on whether callers ever
             // really delete anything much.
         }
+
+#ifdef DEBUG_POINT_SERIES
+        std::cerr << "after remove:" << std::endl;
+        dumpPoints();
+        dumpSeams();
+#endif
     }
 
     bool contains(const Point &p) {
@@ -118,14 +143,86 @@
      * equal to it and its end frame (start + duration) is greater
      * than it.
      */
-    PointVector getPointsSpanning(sv_frame_t frame) {
-        return {};
+    PointVector getPointsSpanning(sv_frame_t frame) const {
+        PointVector span;
+
+        // first find any zero-duration points
+        auto pitr = m_points.lower_bound(Point(frame, QString()));
+        if (pitr != m_points.end()) {
+            while (pitr->getFrame() == frame) {
+                if (!pitr->haveDuration()) {
+                    span.push_back(*pitr);
+                }
+                ++pitr;
+            }
+        }
+
+        // now any non-zero-duration ones from the seam map
+        auto sitr = m_seams.lower_bound(frame);
+        if (sitr == m_seams.end() || sitr->first > frame) {
+            if (sitr != m_seams.begin()) {
+                --sitr;
+            }                
+        }
+        if (sitr != m_seams.end() && sitr->first <= frame) {
+            for (auto p: sitr->second) {
+                span.push_back(p);
+            }
+        }
+        
+        return span;
     }
 
 private:
     int m_count;
-    std::multiset<Point> m_points;
-    std::map<sv_frame_t, std::set<Point>> m_seams;
+
+    typedef std::multiset<Point> PointMultiset;
+    PointMultiset m_points;
+
+    typedef std::map<sv_frame_t, std::multiset<Point>> FramePointsMap;
+    FramePointsMap m_seams;
+
+    /** Create a seam at the given frame, copying from the prior seam
+     *  if there is one. If a seam already exists at the given frame,
+     *  leave it untouched.
+     */
+    void createSeam(sv_frame_t frame) {
+        auto itr = m_seams.lower_bound(frame);
+        if (itr == m_seams.end() || itr->first > frame) {
+            if (itr != m_seams.begin()) {
+                --itr;
+            }
+        }
+        if (itr == m_seams.end()) {
+            m_seams[frame] = {};
+        } else if (itr->first < frame) {
+            m_seams[frame] = itr->second;
+        } else if (itr->first > frame) { // itr must be begin()
+            m_seams[frame] = {};
+        }
+    }
+
+#ifdef DEBUG_POINT_SERIES
+    void dumpPoints() const {
+        std::cerr << "POINTS [" << std::endl;
+        for (const auto &p: m_points) {
+            std::cerr << p.toXmlString("  ");
+        }
+        std::cerr << "]" << std::endl;
+    }
+    
+    void dumpSeams() const {
+        std::cerr << "SEAMS [" << std::endl;
+        for (const auto &s: m_seams) {
+            std::cerr << "  " << s.first << " -> {" << std::endl;
+            for (const auto &p: s.second) {
+                std::cerr << p.toXmlString("    ");
+            }
+            std::cerr << "  }" << std::endl;
+        }
+        std::cerr << "]" << std::endl;
+    }
+#endif
 };
 
 #endif
--- a/base/test/TestPointSeries.h	Wed Mar 06 16:37:10 2019 +0000
+++ b/base/test/TestPointSeries.h	Thu Mar 07 14:35:57 2019 +0000
@@ -79,7 +79,143 @@
         QCOMPARE(s.getPointsSpanning(30), PointVector());
         QCOMPARE(s.getPointsSpanning(9), PointVector());
     }
-        
+
+    void identicalPointsSpan() {
+
+        PointSeries s;
+        Point p(10, QString());
+        s.add(p);
+        s.add(p);
+
+        PointVector span;
+        span.push_back(p);
+        span.push_back(p);
+        QCOMPARE(s.getPointsSpanning(10), span);
+        QCOMPARE(s.getPointsSpanning(11), PointVector());
+        QCOMPARE(s.getPointsSpanning(9), PointVector());
+
+        s.remove(p);
+        span.clear();
+        span.push_back(p);
+        QCOMPARE(s.getPointsSpanning(10), span);
+        QCOMPARE(s.getPointsSpanning(11), PointVector());
+        QCOMPARE(s.getPointsSpanning(9), PointVector());
+    }
+    
+    void identicalPointsWithDurationSpan() {
+
+        PointSeries s;
+        Point p(10, 1.0, 20, QString());
+        s.add(p);
+        s.add(p);
+        PointVector span;
+        span.push_back(p);
+        span.push_back(p);
+        QCOMPARE(s.getPointsSpanning(10), span);
+        QCOMPARE(s.getPointsSpanning(11), span);
+        QCOMPARE(s.getPointsSpanning(29), span);
+        QCOMPARE(s.getPointsSpanning(30), PointVector());
+        QCOMPARE(s.getPointsSpanning(9), PointVector());
+
+        s.remove(p);
+        span.clear();
+        span.push_back(p);
+        QCOMPARE(s.getPointsSpanning(10), span);
+        QCOMPARE(s.getPointsSpanning(11), span);
+        QCOMPARE(s.getPointsSpanning(29), span);
+        QCOMPARE(s.getPointsSpanning(30), PointVector());
+        QCOMPARE(s.getPointsSpanning(9), PointVector());
+    }
+
+    void multiplePointsSpan() {
+
+        PointSeries s;
+        Point a(10, QString("a"));
+        Point b(11, QString("b"));
+        Point c(40, QString("c"));
+        s.add(c);
+        s.add(a);
+        s.add(b);
+        s.remove(a);
+        s.add(a);
+        s.add(c);
+        s.remove(c);
+        QCOMPARE(s.count(), 3);
+        PointVector span;
+        span.push_back(a);
+        QCOMPARE(s.getPointsSpanning(10), span);
+        span.clear();
+        span.push_back(c);
+        QCOMPARE(s.getPointsSpanning(40), span);
+        QCOMPARE(s.getPointsSpanning(9), PointVector());
+    }
+
+    void disjointPointsWithDurationSpan() {
+
+        PointSeries s;
+        Point a(10, 1.0f, 20, QString("a"));
+        Point b(100, 1.2f, 30, QString("b"));
+        s.add(a);
+        s.add(b);
+        QCOMPARE(s.getPointsSpanning(0), PointVector());
+        QCOMPARE(s.getPointsSpanning(10), PointVector({ a }));
+        QCOMPARE(s.getPointsSpanning(15), PointVector({ a }));
+        QCOMPARE(s.getPointsSpanning(30), PointVector());
+        QCOMPARE(s.getPointsSpanning(99), PointVector());
+        QCOMPARE(s.getPointsSpanning(100), PointVector({ b }));
+        QCOMPARE(s.getPointsSpanning(120), PointVector({ b }));
+        QCOMPARE(s.getPointsSpanning(130), PointVector());
+    }
+    
+    void overlappingPointsWithAndWithoutDurationSpan() {
+
+        PointSeries s;
+        Point p(20, QString("p"));
+        Point a(10, 1.0, 20, QString("a"));
+        s.add(p);
+        s.add(a);
+        PointVector span;
+        span.push_back(a);
+        QCOMPARE(s.getPointsSpanning(15), span);
+        QCOMPARE(s.getPointsSpanning(25), span);
+        span.clear();
+        span.push_back(p);
+        span.push_back(a);
+        QCOMPARE(s.getPointsSpanning(20), span);
+    }
+
+    void overlappingPointsWithDurationSpan() {
+
+        PointSeries s;
+        Point a(20, 1.0, 10, QString("a"));
+        Point b(10, 1.0, 20, QString("b"));
+        Point c(10, 1.0, 40, QString("c"));
+        s.add(a);
+        s.add(b);
+        s.add(c);
+        QCOMPARE(s.getPointsSpanning(10), PointVector({ b, c }));
+        QCOMPARE(s.getPointsSpanning(20), PointVector({ b, c, a }));
+        QCOMPARE(s.getPointsSpanning(25), PointVector({ b, c, a }));
+        QCOMPARE(s.getPointsSpanning(30), PointVector({ c }));
+        QCOMPARE(s.getPointsSpanning(40), PointVector({ c }));
+        QCOMPARE(s.getPointsSpanning(50), PointVector());
+    }
+
+    void pointPatternSpan() {
+
+        PointSeries s;
+        Point a(0, 1.0, 18, QString("a"));
+        Point b(3, 2.0, 6, QString("b"));
+        Point c(5, 3.0, 2, QString("c"));
+        Point d(6, 4.0, 10, QString("d"));
+        Point e(14, 5.0, 3, QString("e"));
+        s.add(b);
+        s.add(c);
+        s.add(d);
+        s.add(a);
+        s.add(e);
+        QCOMPARE(s.getPointsSpanning(8), PointVector({ a, b, d }));
+    }
 };
 
 #endif
--- a/data/model/SparseModel.h	Wed Mar 06 16:37:10 2019 +0000
+++ b/data/model/SparseModel.h	Thu Mar 07 14:35:57 2019 +0000
@@ -34,8 +34,6 @@
 #include <QMutex>
 #include <QTextStream>
 
-#include "base/PointSeries.h" //!!!
-
 /**
  * Model containing sparse data (points with some properties).  The
  * properties depend on the point type.
--- a/data/model/test/TestSparseModels.h	Wed Mar 06 16:37:10 2019 +0000
+++ b/data/model/test/TestSparseModels.h	Thu Mar 07 14:35:57 2019 +0000
@@ -136,11 +136,11 @@
 
     void note_extents() {
         NoteModel m(100, 10, false);
-        NoteModel::Point p1(20, 123.4, 40, 0.8, "note 1");
+        NoteModel::Point p1(20, 123.4f, 40, 0.8f, "note 1");
         m.addPoint(p1);
         QCOMPARE(m.isEmpty(), false);
         QCOMPARE(m.getPointCount(), 1);
-        NoteModel::Point p2(50, 124.3, 30, 0.9, "note 2");
+        NoteModel::Point p2(50, 124.3f, 30, 0.9f, "note 2");
         m.addPoint(p2);
         QCOMPARE(m.isEmpty(), false);
         QCOMPARE(m.getPointCount(), 2);
@@ -163,9 +163,9 @@
              
     void note_sample() {
         NoteModel m(100, 10, false);
-        NoteModel::Point p1(20, 123.4, 20, 0.8, "note 1");
-        NoteModel::Point p2(20, 124.3, 10, 0.9, "note 2");
-        NoteModel::Point p3(50, 126.3, 30, 0.9, "note 3");
+        NoteModel::Point p1(20, 123.4f, 20, 0.8f, "note 1");
+        NoteModel::Point p2(20, 124.3f, 10, 0.9f, "note 2");
+        NoteModel::Point p3(50, 126.3f, 30, 0.9f, "note 3");
         m.addPoint(p1);
         m.addPoint(p2);
         m.addPoint(p3);
@@ -193,9 +193,9 @@
 
     void note_xml() {
         NoteModel m(100, 10, false);
-        NoteModel::Point p1(20, 123.4, 20, 0.8, "note 1");
-        NoteModel::Point p2(20, 124.3, 10, 0.9, "note 2");
-        NoteModel::Point p3(50, 126.3, 30, 0.9, "note 3");
+        NoteModel::Point p1(20, 123.4f, 20, 0.8f, "note 1");
+        NoteModel::Point p2(20, 124.3f, 10, 0.9f, "note 2");
+        NoteModel::Point p3(50, 126.3f, 30, 0.9f, "note 3");
         m.setScaleUnits("Hz");
         m.addPoint(p1);
         m.addPoint(p2);