# HG changeset patch
# User Chris Cannam
# Date 1551889463 0
# Node ID 23a29e5dc0e9e205dc44f37653206bca29ad9d3a
# Parent  b2f32c5541993d857b55053243ecf83a41ff924e
Start implementing & testing PointSeries

diff -r b2f32c554199 -r 23a29e5dc0e9 base/Clipboard.cpp
--- a/base/Clipboard.cpp	Tue Mar 05 15:15:11 2019 +0000
+++ b/base/Clipboard.cpp	Wed Mar 06 16:24:23 2019 +0000
@@ -30,14 +30,14 @@
     return m_points.empty();
 }
 
-const Clipboard::PointList &
+const PointVector &
 Clipboard::getPoints() const
 {
     return m_points;
 }
 
 void
-Clipboard::setPoints(const PointList &pl)
+Clipboard::setPoints(const PointVector &pl)
 {
     m_points = pl;
 }
@@ -51,7 +51,7 @@
 bool
 Clipboard::haveReferenceFrames() const
 {
-    for (PointList::const_iterator i = m_points.begin();
+    for (PointVector::const_iterator i = m_points.begin();
          i != m_points.end(); ++i) {
         if (i->haveReferenceFrame()) return true;
     } 
@@ -61,7 +61,7 @@
 bool
 Clipboard::referenceFramesDiffer() const
 {
-    for (PointList::const_iterator i = m_points.begin();
+    for (PointVector::const_iterator i = m_points.begin();
          i != m_points.end(); ++i) {
         if (i->referenceFrameDiffers()) return true;
     } 
diff -r b2f32c554199 -r 23a29e5dc0e9 base/Clipboard.h
--- a/base/Clipboard.h	Tue Mar 05 15:15:11 2019 +0000
+++ b/base/Clipboard.h	Wed Mar 06 16:24:23 2019 +0000
@@ -26,19 +26,17 @@
     Clipboard();
     ~Clipboard();
 
-    typedef std::vector<Point> PointList;
-
     void clear();
     bool empty() const;
-    const PointList &getPoints() const;
-    void setPoints(const PointList &points);
+    const PointVector &getPoints() const;
+    void setPoints(const PointVector &points);
     void addPoint(const Point &point);
 
     bool haveReferenceFrames() const;
     bool referenceFramesDiffer() const;
 
 protected:
-    PointList m_points;
+     PointVector m_points;
 };
 
 #endif
diff -r b2f32c554199 -r 23a29e5dc0e9 base/Point.h
--- a/base/Point.h	Tue Mar 05 15:15:11 2019 +0000
+++ b/base/Point.h	Wed Mar 06 16:24:23 2019 +0000
@@ -17,33 +17,36 @@
 #define SV_POINT_H
 
 #include <QString>
+#include <vector>
 
 #include "BaseTypes.h"
+#include "XmlExportable.h"
+
+//!!! given that these can have size (i.e. duration), maybe Point
+//!!! isn't really an ideal name... perhaps I should go back to dull
+//!!! old Event
 
 class Point
 {
 public:
     Point(sv_frame_t frame, QString label) :
-        m_haveValue(false), m_haveLevel(false), m_haveFrame(true),
-        m_haveDuration(false), m_haveReferenceFrame(false), m_haveLabel(true),
+        m_haveValue(false), m_haveLevel(false), m_haveReferenceFrame(false),
         m_value(0.f), m_level(0.f), m_frame(frame),
         m_duration(0), m_referenceFrame(0), m_label(label) { }
         
     Point(sv_frame_t frame, float value, QString label) :
-        m_haveValue(true), m_haveLevel(false), m_haveFrame(true),
-        m_haveDuration(false), m_haveReferenceFrame(false), m_haveLabel(true),
+        m_haveValue(true), m_haveLevel(false), m_haveReferenceFrame(false),
         m_value(value), m_level(0.f), m_frame(frame),
         m_duration(0), m_referenceFrame(0), m_label(label) { }
         
     Point(sv_frame_t frame, float value, sv_frame_t duration, QString label) :
-        m_haveValue(true), m_haveLevel(false), m_haveFrame(true),
-        m_haveDuration(true), m_haveReferenceFrame(false), m_haveLabel(true),
+        m_haveValue(true), m_haveLevel(false), m_haveReferenceFrame(false),
         m_value(value), m_level(0.f), m_frame(frame),
         m_duration(duration), m_referenceFrame(0), m_label(label) { }
         
-    Point(sv_frame_t frame, float value, sv_frame_t duration, float level, QString label) :
-        m_haveValue(true), m_haveLevel(true), m_haveFrame(true),
-        m_haveDuration(true), m_haveReferenceFrame(false), m_haveLabel(true),
+    Point(sv_frame_t frame, float value, sv_frame_t duration,
+          float level, QString label) :
+        m_haveValue(true), m_haveLevel(true), m_haveReferenceFrame(false),
         m_value(value), m_level(level), m_frame(frame),
         m_duration(duration), m_referenceFrame(0), m_label(label) { }
 
@@ -51,12 +54,10 @@
     Point &operator=(const Point &point) =default;
     Point &operator=(Point &&point) =default;
     
-    bool haveFrame() const { return m_haveFrame; }
     sv_frame_t getFrame() const { return m_frame; }
 
     Point withFrame(sv_frame_t frame) const {
         Point p(*this);
-        p.m_haveFrame = true;
         p.m_frame = frame;
         return p;
     }
@@ -71,22 +72,19 @@
         return p;
     }
     
-    bool haveDuration() const { return m_haveDuration; }
+    bool haveDuration() const { return m_duration != 0; }
     sv_frame_t getDuration() const { return m_duration; }
 
     Point withDuration(sv_frame_t duration) const {
         Point p(*this);
-        p.m_haveDuration = true;
         p.m_duration = duration;
         return p;
     }
     
-    bool haveLabel() const { return m_haveLabel; }
     QString getLabel() const { return m_label; }
 
     Point withLabel(QString label) const {
         Point p(*this);
-        p.m_haveLabel = true;
         p.m_label = label;
         return p;
     }
@@ -113,16 +111,83 @@
         p.m_referenceFrame = frame;
         return p;
     }
+
+    bool operator==(const Point &p) const {
+
+        if (m_frame != p.m_frame) return false;
+
+        if (m_haveValue != p.m_haveValue) return false;
+        if (m_haveValue && (m_value != p.m_value)) return false;
+
+        if (m_duration != p.m_duration) return false;
+
+        if (m_haveLevel != p.m_haveLevel) return false;
+        if (m_haveLevel && (m_level != p.m_level)) return false;
+
+        if (m_haveReferenceFrame != p.m_haveReferenceFrame) return false;
+        if (m_haveReferenceFrame &&
+            (m_referenceFrame != p.m_referenceFrame)) return false;
+        
+        if (m_label != p.m_label) return false;
+        
+        return true;
+    }
+
+    bool operator<(const Point &p) const {
+
+        if (m_frame != p.m_frame) return m_frame < p.m_frame;
+
+        // points without a property sort before points with that property
+
+        if (m_haveValue != p.m_haveValue) return !m_haveValue;
+        if (m_haveValue && (m_value != p.m_value)) return m_value < p.m_value;
+        
+        if (m_duration != p.m_duration) return m_duration < p.m_duration;
+        
+        if (m_haveLevel != p.m_haveLevel) return !m_haveLevel;
+        if (m_haveLevel && (m_level != p.m_level)) return m_level < p.m_level;
+
+        if (m_haveReferenceFrame != p.m_haveReferenceFrame) {
+            return !m_haveReferenceFrame;
+        }
+        if (m_haveReferenceFrame && (m_referenceFrame != p.m_referenceFrame)) {
+            return m_referenceFrame < p.m_referenceFrame;
+        }
+        
+        return m_label < p.m_label;
+    }
+
+    void toXml(QTextStream &stream,
+               QString indent = "",
+               QString extraAttributes = "") const {
+
+        stream << indent << QString("<point frame=\"%1\" ").arg(m_frame);
+        if (m_haveValue) stream << QString("value=\"%1\" ").arg(m_value);
+        if (m_duration) stream << QString("duration=\"%1\" ").arg(m_duration);
+        if (m_haveLevel) stream << QString("level=\"%1\" ").arg(m_level);
+        if (m_haveReferenceFrame) stream << QString("referenceFrame=\"%1\" ")
+                                      .arg(m_referenceFrame);
+        stream << QString("label=\"%1\" ")
+            .arg(XmlExportable::encodeEntities(m_label));
+        stream << extraAttributes << ">\n";
+    }
+
+    QString toXmlString(QString indent = "",
+                        QString extraAttributes = "") const {
+        QString s;
+        QTextStream out(&s);
+        toXml(out, indent, extraAttributes);
+        out.flush();
+        return s;
+    }
     
 private:
     // The order of fields here is chosen to minimise overall size of struct.
+    // We potentially store very many of these objects.
     // If you change something, check what difference it makes to packing.
     bool m_haveValue : 1;
     bool m_haveLevel : 1;
-    bool m_haveFrame : 1;
-    bool m_haveDuration : 1;
     bool m_haveReferenceFrame : 1;
-    bool m_haveLabel : 1;
     float m_value;
     float m_level;
     sv_frame_t m_frame;
@@ -131,4 +196,6 @@
     QString m_label;
 };
 
+typedef std::vector<Point> PointVector;
+
 #endif
diff -r b2f32c554199 -r 23a29e5dc0e9 base/PointSeries.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/base/PointSeries.h	Wed Mar 06 16:24:23 2019 +0000
@@ -0,0 +1,131 @@
+/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
+
+/*
+    Sonic Visualiser
+    An audio file viewer and annotation editor.
+    Centre for Digital Music, Queen Mary, University of London.
+    
+    This program is free software; you can redistribute it and/or
+    modify it under the terms of the GNU General Public License as
+    published by the Free Software Foundation; either version 2 of the
+    License, or (at your option) any later version.  See the file
+    COPYING included with this distribution for more information.
+*/
+
+#ifndef SV_POINT_SERIES_H
+#define SV_POINT_SERIES_H
+
+#include "Point.h"
+
+#include <set>
+
+class PointSeries
+{
+public:
+    PointSeries() : m_count(0) { }
+    
+    void add(const Point &p) {
+
+        m_points.insert(p);
+        ++m_count;
+
+        if (p.haveDuration()) {
+            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;
+                }
+            }
+            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;
+        }
+    }
+
+    void remove(const Point &p) {
+
+        // erase first itr that matches p; if there is more than one
+        // p, erase(p) would remove all of them, but we only want to
+        // remove (any) one
+        auto pitr = m_points.find(p);
+        if (pitr == m_points.end()) {
+            return; // we don't know this point
+        } else {
+            m_points.erase(pitr);
+            --m_count;
+        }
+
+        if (p.haveDuration()) {
+            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
+                       << " for point not found in seam map: point is "
+                       << p.toXmlString() << endl;
+                return;
+            }
+
+            while (itr != m_seams.end() && itr->first <= endFrame) {
+                itr->second.erase(p);
+                ++itr;
+            }
+
+            // Shall we "garbage-collect" here? We could be leaving
+            // lots of empty point-sets, or consecutive identical
+            // ones, which are a pure irrelevance that take space and
+            // slow us down. But a lot depends on whether callers ever
+            // really delete anything much.
+        }
+    }
+
+    bool contains(const Point &p) {
+        return m_points.find(p) != m_points.end();
+    }
+
+    int count() const {
+        return m_count;
+    }
+
+    bool isEmpty() const {
+        return m_count == 0;
+    }
+    
+    void clear() {
+        m_points.clear();
+        m_seams.clear();
+        m_count = 0;
+    }
+
+    /**
+     * Retrieve all points that span the given frame. A point without
+     * duration spans a frame if its own frame is equal to it. A point
+     * with duration spans a frame if its start frame is less than or
+     * equal to it and its end frame (start + duration) is greater
+     * than it.
+     */
+    PointVector getPointsSpanning(sv_frame_t frame) {
+        return {};
+    }
+
+private:
+    int m_count;
+    std::multiset<Point> m_points;
+    std::map<sv_frame_t, std::set<Point>> m_seams;
+};
+
+#endif
diff -r b2f32c554199 -r 23a29e5dc0e9 base/test/TestPointSeries.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/base/test/TestPointSeries.h	Wed Mar 06 16:24:23 2019 +0000
@@ -0,0 +1,85 @@
+/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*-  vi:set ts=8 sts=4 sw=4: */
+
+/*
+    Sonic Visualiser
+    An audio file viewer and annotation editor.
+    Centre for Digital Music, Queen Mary, University of London.
+    
+    This program is free software; you can redistribute it and/or
+    modify it under the terms of the GNU General Public License as
+    published by the Free Software Foundation; either version 2 of the
+    License, or (at your option) any later version.  See the file
+    COPYING included with this distribution for more information.
+*/
+
+#ifndef TEST_POINT_SERIES_H
+#define TEST_POINT_SERIES_H
+
+#include "../PointSeries.h"
+
+#include <QObject>
+#include <QtTest>
+
+#include <iostream>
+
+using namespace std;
+
+class TestPointSeries : public QObject
+{
+    Q_OBJECT
+
+private slots:
+    void empty() {
+
+        PointSeries s;
+        QCOMPARE(s.isEmpty(), true);
+        QCOMPARE(s.count(), 0);
+
+        Point p(10, QString());
+        QCOMPARE(s.contains(p), false);
+        QCOMPARE(s.getPointsSpanning(400), PointVector());
+    }
+
+    void singlePoint() {
+
+        PointSeries s;
+        Point p(10, QString());
+        s.add(p);
+        QCOMPARE(s.isEmpty(), false);
+        QCOMPARE(s.count(), 1);
+        QCOMPARE(s.contains(p), true);
+
+        s.remove(p);
+        QCOMPARE(s.isEmpty(), true);
+        QCOMPARE(s.contains(p), false);
+    }
+
+    void singlePointSpan() {
+
+        PointSeries s;
+        Point p(10, QString());
+        s.add(p);
+        PointVector span;
+        span.push_back(p);
+        QCOMPARE(s.getPointsSpanning(10), span);
+        QCOMPARE(s.getPointsSpanning(11), PointVector());
+        QCOMPARE(s.getPointsSpanning(9), PointVector());
+    }
+
+    void singlePointWithDurationSpan() {
+
+        PointSeries s;
+        Point p(10, 1.0, 20, QString());
+        s.add(p);
+        PointVector span;
+        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());
+    }
+        
+};
+
+#endif
diff -r b2f32c554199 -r 23a29e5dc0e9 base/test/files.pri
--- a/base/test/files.pri	Tue Mar 05 15:15:11 2019 +0000
+++ b/base/test/files.pri	Wed Mar 06 16:24:23 2019 +0000
@@ -4,6 +4,7 @@
 	     TestMovingMedian.h \
 	     TestOurRealTime.h \
 	     TestPitch.h \
+	     TestPointSeries.h \
 	     TestRangeMapper.h \
 	     TestScaleTickIntervals.h \
 	     TestStringBits.h \
diff -r b2f32c554199 -r 23a29e5dc0e9 base/test/svcore-base-test.cpp
--- a/base/test/svcore-base-test.cpp	Tue Mar 05 15:15:11 2019 +0000
+++ b/base/test/svcore-base-test.cpp	Wed Mar 06 16:24:23 2019 +0000
@@ -20,6 +20,7 @@
 #include "TestVampRealTime.h"
 #include "TestColumnOp.h"
 #include "TestMovingMedian.h"
+#include "TestPointSeries.h"
 
 #include "system/Init.h"
 
@@ -84,6 +85,11 @@
         if (QTest::qExec(&t, argc, argv) == 0) ++good;
         else ++bad;
     }
+    {
+        TestPointSeries t;
+        if (QTest::qExec(&t, argc, argv) == 0) ++good;
+        else ++bad;
+    }
 
     if (bad > 0) {
         SVCERR << "\n********* " << bad << " test suite(s) failed!\n" << endl;
diff -r b2f32c554199 -r 23a29e5dc0e9 data/model/NoteModel.h
--- a/data/model/NoteModel.h	Tue Mar 05 15:15:11 2019 +0000
+++ b/data/model/NoteModel.h	Wed Mar 06 16:24:23 2019 +0000
@@ -146,7 +146,7 @@
                        QString extraAttributes = "") const override
     {
         std::cerr << "NoteModel::toXml: extraAttributes = \"" 
-                  << extraAttributes.toStdString() << std::endl;
+                  << extraAttributes.toStdString() << "\"" << std::endl;
 
         IntervalModel<Note>::toXml
             (out,
diff -r b2f32c554199 -r 23a29e5dc0e9 data/model/SparseModel.h
--- a/data/model/SparseModel.h	Tue Mar 05 15:15:11 2019 +0000
+++ b/data/model/SparseModel.h	Wed Mar 06 16:24:23 2019 +0000
@@ -34,6 +34,8 @@
 #include <QMutex>
 #include <QTextStream>
 
+#include "base/PointSeries.h" //!!!
+
 /**
  * Model containing sparse data (points with some properties).  The
  * properties depend on the point type.
diff -r b2f32c554199 -r 23a29e5dc0e9 data/model/SparseValueModel.h
--- a/data/model/SparseValueModel.h	Tue Mar 05 15:15:11 2019 +0000
+++ b/data/model/SparseValueModel.h	Wed Mar 06 16:24:23 2019 +0000
@@ -118,7 +118,7 @@
                QString extraAttributes = "") const override
     {
         std::cerr << "SparseValueModel::toXml: extraAttributes = \"" 
-                  << extraAttributes.toStdString() << std::endl;
+                  << extraAttributes.toStdString() << "\"" << std::endl;
 
         SparseModel<PointType>::toXml
             (stream,