Index: src/backend/core/AbstractColumn.h =================================================================== --- src/backend/core/AbstractColumn.h +++ src/backend/core/AbstractColumn.h @@ -91,6 +91,13 @@ // QMatrix // etc. }; + enum Properties { + No = 0x00, + Constant = 0x01, + MonotonicIncreasing = 0x02, // prev_value >= value for all values in column + MonotonicDecreasing = 0x04 // prev_value <= value for all values in column + // add new values with next bit set (0x08) + }; struct ColumnStatistics { ColumnStatistics() { @@ -187,6 +194,8 @@ virtual int integerAt(int row) const; virtual void setIntegerAt(int row, int new_value); virtual void replaceInteger(int first, const QVector& new_values); + virtual int properties() const; + virtual void updateProperties(); signals: void plotDesignationAboutToChange(const AbstractColumn* source); Index: src/backend/core/AbstractColumn.cpp =================================================================== --- src/backend/core/AbstractColumn.cpp +++ src/backend/core/AbstractColumn.cpp @@ -560,6 +560,23 @@ Q_UNUSED(first) Q_UNUSED(new_values) } +/** + * @brief AbstractColumn::properties + * Returns the properties hold by this column (no, monotonic increasing, monotonic decreasing,...) + * Will be used in XYCurve to improve the search velocity for the y value for a specific x value + * @return + */ +int AbstractColumn::properties() const { + return AbstractColumn::Properties::No; +} + +/** + * @brief AbstractColumn::updateProperties + * updates the properties AbstractColumn::Properties + */ +void AbstractColumn::updateProperties() { +} + /**********************************************************************/ double AbstractColumn::minimum(int count) const { Q_UNUSED(count); Index: src/backend/core/column/Column.h =================================================================== --- src/backend/core/column/Column.h +++ src/backend/core/column/Column.h @@ -104,6 +104,8 @@ int integerAt(int) const override; void setIntegerAt(int, int) override; void replaceInteger(int, const QVector&) override; + int properties() const override; + void updateProperties() override; double maximum(int count = 0) const override; double minimum(int count = 0) const override; Index: src/backend/core/column/Column.cpp =================================================================== --- src/backend/core/column/Column.cpp +++ src/backend/core/column/Column.cpp @@ -243,6 +243,7 @@ d->statisticsAvailable = false;; d->hasValuesAvailable = false; + d->propertiesAvailable = false; } /** @@ -256,6 +257,7 @@ d->statisticsAvailable = false;; d->hasValuesAvailable = false; + d->propertiesAvailable = false; } /** @@ -355,6 +357,7 @@ void Column::setTextAt(int row, const QString& new_value) { DEBUG("Column::setTextAt()"); d->statisticsAvailable = false;; + d->propertiesAvailable = false; exec(new ColumnSetTextCmd(d, row, new_value)); } @@ -367,6 +370,7 @@ DEBUG("Column::replaceTexts()"); if (!new_values.isEmpty()) { //TODO: do we really need this check? d->statisticsAvailable = false;; + d->propertiesAvailable = false; exec(new ColumnReplaceTextsCmd(d, first, new_values)); } } @@ -378,6 +382,7 @@ */ void Column::setDateAt(int row, QDate new_value) { d->statisticsAvailable = false;; + d->propertiesAvailable = false; setDateTimeAt(row, QDateTime(new_value, timeAt(row))); } @@ -388,6 +393,7 @@ */ void Column::setTimeAt(int row, QTime new_value) { d->statisticsAvailable = false;; + d->propertiesAvailable = false; setDateTimeAt(row, QDateTime(dateAt(row), new_value)); } @@ -398,6 +404,7 @@ */ void Column::setDateTimeAt(int row, const QDateTime& new_value) { d->statisticsAvailable = false;; + d->propertiesAvailable = false; exec(new ColumnSetDateTimeCmd(d, row, new_value)); } @@ -409,6 +416,7 @@ void Column::replaceDateTimes(int first, const QVector& new_values) { if (!new_values.isEmpty()) { d->statisticsAvailable = false;; + d->propertiesAvailable = false; exec(new ColumnReplaceDateTimesCmd(d, first, new_values)); } } @@ -422,6 +430,7 @@ // DEBUG("Column::setValueAt()"); d->statisticsAvailable = false;; d->hasValuesAvailable = false; + d->propertiesAvailable = false; exec(new ColumnSetValueCmd(d, row, new_value)); } @@ -435,6 +444,7 @@ if (!new_values.isEmpty()) { d->statisticsAvailable = false;; d->hasValuesAvailable = false; + d->propertiesAvailable = false; exec(new ColumnReplaceValuesCmd(d, first, new_values)); } } @@ -448,6 +458,7 @@ DEBUG("Column::setIntegerAt()"); d->statisticsAvailable = false;; d->hasValuesAvailable = false; + d->propertiesAvailable = false; exec(new ColumnSetIntegerCmd(d, row, new_value)); } @@ -461,9 +472,30 @@ if (!new_values.isEmpty()) { d->statisticsAvailable = false;; d->hasValuesAvailable = false; + d->propertiesAvailable = false; exec(new ColumnReplaceIntegersCmd(d, first, new_values)); } } +/*! + * \brief Column::properties + * Returns the column properties of this curve (monoton increasing, monoton decreasing, ... ) + * See AbstractColumn::properties + * \return + */ +int Column::properties() const{ + if (!d->propertiesAvailable) + d->updateProperties(); + + return d->properties; +} + +/*! + * \brief Column::updateProperties + * Rechecking the properties of the column + */ +void Column::updateProperties(){ + d->updateProperties(); +} const Column::ColumnStatistics& Column::statistics() const { if (!d->statisticsAvailable) @@ -573,6 +605,7 @@ } statistics.entropy = -entropy; + d->statisticsAvailable = true; } @@ -665,11 +698,15 @@ * This is used e.g. in \c XYFitCurvePrivate::recalculate() */ void Column::setChanged() { + + d->propertiesAvailable = false; + if (!m_suppressDataChangedSignal) emit dataChanged(this); d->statisticsAvailable = false;; d->hasValuesAvailable = false; + } //////////////////////////////////////////////////////////////////////////////// @@ -1088,6 +1125,7 @@ d->statisticsAvailable = false;; d->hasValuesAvailable = false; + d->propertiesAvailable = false; DEBUG("Column::handleFormatChange() DONE"); } Index: src/backend/core/column/ColumnPrivate.h =================================================================== --- src/backend/core/column/ColumnPrivate.h +++ src/backend/core/column/ColumnPrivate.h @@ -105,12 +105,17 @@ void setIntegerAt(int row, int new_value); void replaceInteger(int first, const QVector&); + void updateProperties(); + mutable AbstractColumn::ColumnStatistics statistics; bool statisticsAvailable; //is 'statistics' already available or needs to be (re-)calculated? bool hasValues; bool hasValuesAvailable; //is 'hasValues' already available or needs to be (re-)calculated? + mutable bool propertiesAvailable; //is 'properties' already available (true) or needs to be (re-)calculated (false)? + mutable int properties; // declares the properties of the curve (monotonic increasing/decreasing ...). Speed up algorithms + private: AbstractColumn::ColumnMode m_column_mode; // type of column data void* m_data; //pointer to the data container (QVector) Index: src/backend/core/column/ColumnPrivate.cpp =================================================================== --- src/backend/core/column/ColumnPrivate.cpp +++ src/backend/core/column/ColumnPrivate.cpp @@ -39,7 +39,9 @@ m_column_mode(mode), m_plot_designation(AbstractColumn::NoDesignation), m_width(0), - m_owner(owner) { + m_owner(owner), + propertiesAvailable(false), + properties(AbstractColumn::Properties::No){ Q_ASSERT(owner != nullptr); switch(mode) { @@ -94,7 +96,9 @@ m_data(data), m_plot_designation(AbstractColumn::NoDesignation), m_width(0), - m_owner(owner) { + m_owner(owner), + propertiesAvailable(false), + properties(AbstractColumn::Properties::No){ switch(mode) { case AbstractColumn::Numeric: @@ -588,7 +592,6 @@ if (!m_owner->m_suppressDataChangedSignal) emit m_owner->dataChanged(m_owner); - return true; } @@ -1226,6 +1229,85 @@ emit m_owner->dataChanged(m_owner); } +/*! + * \brief ColumnPrivate::updateProperties + * updates the properties. Will be called, when data in the column changed. + * The properies will be used to speed up some algorithms. + * See where variable properties will be used. + */ +void ColumnPrivate::updateProperties() { + + // TODO: for double Properties::Constant will never be used. Use an epsilon (difference smaller than epsilon is zero) + double prev_value = NAN; + int prev_value_int = 0; + int monotonic_decreasing = -1; + int monotonic_increasing = -1; + + for (int row=0; row< rowCount(); row++) { + + if (row==0) { + prev_value = valueAt(row); + prev_value_int = integerAt(row); + continue; + } + + double value; + int value_int; + if (m_column_mode == AbstractColumn::Integer) { + value_int = integerAt(row); + + // check monotonic increasing + if (value_int >= prev_value && monotonic_increasing < 0) + monotonic_increasing = 1; + else if (value_int < prev_value && monotonic_increasing >=0) + monotonic_increasing = 0; + // else: nothing + + // check monotonic decreasing + if (value_int <= prev_value && monotonic_decreasing < 0) + monotonic_decreasing = 1; + else if (value_int > prev_value && monotonic_decreasing >=0) + monotonic_decreasing = 0; + + prev_value_int = value_int; + + } else if (m_column_mode == AbstractColumn::Numeric) { + value = valueAt(row); + + // check monotonic increasing + if (value >= prev_value && monotonic_increasing < 0) + monotonic_increasing = 1; + else if (value < prev_value) + monotonic_increasing = 0; + // else: nothing + + // check monotonic decreasing + if (value <= prev_value && monotonic_decreasing < 0) + monotonic_decreasing = 1; + else if (value > prev_value) + monotonic_decreasing = 0; + + prev_value = value; + + } else { + properties = AbstractColumn::Properties::No; + return; + } + } + + properties = AbstractColumn::Properties::No; + if (monotonic_increasing && monotonic_decreasing) + properties += AbstractColumn::Properties::Constant; + else if (monotonic_decreasing) + properties += AbstractColumn::Properties::MonotonicDecreasing; + else if (monotonic_increasing) + properties += AbstractColumn::Properties::MonotonicIncreasing; + + + DEBUG("updateProperties: " << name().toLocal8Bit().data() << "properties: " << properties); + propertiesAvailable = true; +} + //////////////////////////////////////////////////////////////////////////////// //@} //////////////////////////////////////////////////////////////////////////////// Index: src/backend/worksheet/plots/cartesian/CartesianPlot.cpp =================================================================== --- src/backend/worksheet/plots/cartesian/CartesianPlot.cpp +++ src/backend/worksheet/plots/cartesian/CartesianPlot.cpp @@ -2608,6 +2608,22 @@ else info += QDateTime::fromMSecsSinceEpoch(logicalPoint.y()).toString(yRangeDateTimeFormat); update(); + } else if (mouseMode == CartesianPlot::MouseMode::SelectionMode) { + + // hover the nearest curve to the mousepointer + bool curve_hovered = false; + for (auto curve: q->children()){ + if(curve_hovered){ + curve->setHover(false); + continue; + } + if(curve->activateCurve(event->pos())){ + curve->setHover(true); + curve_hovered = true; + continue; + } + curve->setHover(false); + } } } q->info(info); Index: src/backend/worksheet/plots/cartesian/XYCurve.h =================================================================== --- src/backend/worksheet/plots/cartesian/XYCurve.h +++ src/backend/worksheet/plots/cartesian/XYCurve.h @@ -66,6 +66,10 @@ bool load(XmlStreamReader*, bool preview) override; void loadThemeConfig(const KConfig&) override; void saveThemeConfig(const KConfig&) override; + static int calculateMaxSteps(unsigned int value); + double y(double x, bool &valueFound) const; + bool activateCurve(QPointF mouseScenePos, double maxDist = -1); + void setHover(bool on); POINTER_D_ACCESSOR_DECL(const AbstractColumn, xColumn, XColumn) POINTER_D_ACCESSOR_DECL(const AbstractColumn, yColumn, YColumn) Index: src/backend/worksheet/plots/cartesian/XYCurve.cpp =================================================================== --- src/backend/worksheet/plots/cartesian/XYCurve.cpp +++ src/backend/worksheet/plots/cartesian/XYCurve.cpp @@ -845,7 +845,7 @@ m_printing(false) { setFlag(QGraphicsItem::ItemIsSelectable, true); - setAcceptHoverEvents(true); + setAcceptHoverEvents(false); } QString XYCurvePrivate::name() const { @@ -864,7 +864,12 @@ } void XYCurvePrivate::contextMenuEvent(QGraphicsSceneContextMenuEvent* event) { - q->createContextMenu()->exec(event->screenPos()); + + if (q->activateCurve(event->pos(), linePen.width())) { + q->createContextMenu()->exec(event->screenPos()); + return; + } + QGraphicsItem::contextMenuEvent(event); } bool XYCurvePrivate::swapVisible(bool on) { @@ -1677,6 +1682,228 @@ recalcShapeAndBoundingRect(); } +/*! + * \brief XYCurve::calculateMaxSteps + * calculates log2(x)+1 for an integer value. + * Used in y(double x) to calculate the maximum steps + * source: https://stackoverflow.com/questions/11376288/fast-computing-of-log2-for-64-bit-integers + * source: http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogLookup + * \param value + * \return + */ +// TODO: testing if it is faster than calculating log2. + int XYCurve::calculateMaxSteps (unsigned int value) { + const char LogTable256[256] = + { + -1,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3, + 4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, + 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, + 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, + 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 + }; + + unsigned int r; // r will be lg(v) + unsigned int t, tt; // temporaries + if ((tt = value >> 16)) + r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt]; + else + r = (t = value >> 8) ? 8 + LogTable256[t] : LogTable256[value]; + + return r+1; +} + + /*! + * \brief XYCurve::y + * Find y value which corresponds to a @par x . @par valueFound indicates, if value was found. + * When monotonic increasing or decreasing a different algorithm will be used, which needs less steps (mean) (log_2(rowCount)) to find the value. + * \param x + * \param valueFound + * \return + */ +double XYCurve::y(double x, bool &valueFound) const { + int rowCount = xColumn()->rowCount(); + + double prevValue=0; + + int properties = xColumn()->properties(); + if(properties == AbstractColumn::Properties::No){ + // naiv way + for (int row = 0; row < rowCount; row++) { + if (xColumn()->isValid(row) && yColumn()->isValid(row)) { + if (row == 0) + prevValue = xColumn()->valueAt(row); + + double value = xColumn()->valueAt(row); + if (abs(value-x) <= abs(prevValue-x)) { // <= prevents also that row-1 become < 0 + if (row < rowCount-1) + prevValue = value; + else { + valueFound = true; + return yColumn()->valueAt(row); + } + }else{ + valueFound = true; + return yColumn()->valueAt(row-1); + } + } + } + }else if (properties == AbstractColumn::Properties::MonotonicIncreasing || + properties == AbstractColumn::Properties::MonotonicDecreasing) { + // bisects the index every time, so it is possible to find the value in log_2(rowCount) steps + bool increase = true; + if(properties == AbstractColumn::Properties::MonotonicDecreasing) + increase = false; + + int lower_index = 0; + int higher_index = rowCount-1; + + unsigned int max_steps = calculateMaxSteps(static_cast(rowCount)); + for (int i=0; i< max_steps; i++) { // so no log_2(rowCount) needed + int index = lower_index + round(static_cast(higher_index - lower_index)/2); + double value = xColumn()->valueAt(index); + + if (higher_index-lower_index < 3) { + if (abs(xColumn()->valueAt(lower_index) - x) < abs(xColumn()->valueAt(higher_index)-x)) + index = lower_index; + else + index = higher_index; + + valueFound = true; + return yColumn()->valueAt(index); + } + + if (value > x && increase) + higher_index = index; + else if (value > x && !increase) + lower_index = index; + else if (value < x && increase) + lower_index = index; + else if (value < x && !increase) + higher_index = index; + + } + + } + valueFound = false; + return 0; +} + +/*! + * \brief XYCurve::activateCurve + * Checks if the mousepos distance to the curve is less than @p pow(maxDist,2) + * \param mouseScenePos + * \param maxDist + * \return Returns true if the distance is smaller than pow(maxDist,2). + */ +bool XYCurve::activateCurve(QPointF mouseScenePos, double maxDist) { + + Q_D(XYCurve); + + int rowCount = xColumn()->rowCount(); + if (rowCount == 0) + return false; + + if (maxDist < 0) + maxDist = d->linePen.width(); + + double maxDistSquare = pow(maxDist,2); + + int properties = xColumn()->properties(); + if (properties == AbstractColumn::Properties::No) { + for (int row = 0; row< rowCount; row++) { + if (xColumn()->isValid(row) && yColumn()->isValid(row)) { + double xvalue = xColumn()->valueAt(row); + double yvalue = yColumn()->valueAt(row); + QPointF curvePosScene = d->cSystem->mapLogicalToScene(QPointF(xvalue,yvalue)); + double xdistsquare = pow(mouseScenePos.x() - curvePosScene.x(),2); + double ydistsquare = pow(mouseScenePos.y() - curvePosScene.y(),2); + double distance = xdistsquare+ydistsquare; + //DEBUG("Distance: " << distance << "MaxDistSquare: " << maxDistSquare); + if (distance <= maxDistSquare) + return true; + } + } + } else if (properties == AbstractColumn::Properties::MonotonicIncreasing || + properties == AbstractColumn::Properties::MonotonicDecreasing) { + bool increase = true; + if (properties == AbstractColumn::Properties::MonotonicDecreasing) + increase = false; + + int lower_index = 0; + int higher_index = rowCount-1; + QPointF point(mouseScenePos.x()-maxDistSquare,mouseScenePos.y()); + double x = d->cSystem->mapSceneToLogical(point).x(); + + unsigned int max_steps = calculateMaxSteps(static_cast(rowCount)); + int index; + for (unsigned int i=0; i< max_steps; i++) { // so no log_2(rowCount) needed + index = lower_index + round(static_cast(higher_index - lower_index)/2); + double value = xColumn()->valueAt(index); + + if (higher_index-lower_index < 2) { + if (abs(xColumn()->valueAt(lower_index) - x) < abs(xColumn()->valueAt(higher_index)-x)) { + index = lower_index; + break; + } else { + index = higher_index; + break; + } + } + + if (value > x && increase) + higher_index = index; + else if (value > x && !increase) + lower_index = index; + else if (value < x && increase) + lower_index = index; + else if (value < x && !increase) + higher_index = index; + } + + double xvalue = xColumn()->valueAt(index); + double yvalue = yColumn()->valueAt(index); + QPointF curvePosScene(d->cSystem->mapLogicalToScene(QPointF(xvalue,yvalue))); + + while (curvePosScene.x() <= pow(mouseScenePos.x()+maxDist,2) && index < rowCount) { + if (pow(mouseScenePos.x()- curvePosScene.x(),2)+pow(mouseScenePos.y()-curvePosScene.y(),2) <= maxDistSquare) + return true; + + if (increase) + index++; + else + index--; + + xvalue = xColumn()->valueAt(index); + yvalue = yColumn()->valueAt(index); + curvePosScene = d->cSystem->mapLogicalToScene(QPointF(xvalue,yvalue)); + } + + + } + return false; +} +/*! + * \brief XYCurve::setHover + * Will be called in CartesianPlot::hoverMoveEvent() + * See d->setHover(on) for more documentation + * \param on + */ +void XYCurve::setHover(bool on) { + Q_D(XYCurve); + d->setHover(on); +} + void XYCurvePrivate::updateErrorBars() { errorBarsPath = QPainterPath(); if (xErrorType==XYCurve::NoError && yErrorType==XYCurve::NoError) { @@ -2111,22 +2338,45 @@ } } -void XYCurvePrivate::hoverEnterEvent(QGraphicsSceneHoverEvent*) { - const auto* plot = dynamic_cast(q->parentAspect()); - if (plot->mouseMode() == CartesianPlot::SelectionMode && !isSelected()) { - m_hovered = true; - emit q->hovered(); - update(); +/*! + * \brief XYCurvePrivate::mousePressEvent + * checks with activateCurve, if the mousePress was in the near + * of the curve. If it was, the curve will be selected + * \param event + */ +void XYCurvePrivate::mousePressEvent(QGraphicsSceneMouseEvent* event) { + + if(q->activateCurve(event->pos(), linePen.width())){ + setSelected(true); + return; } + + event->ignore(); + setSelected(false); + QGraphicsItem::mousePressEvent(event); + return; } -void XYCurvePrivate::hoverLeaveEvent(QGraphicsSceneHoverEvent*) { - const auto* plot = dynamic_cast(q->parentAspect()); - if (plot->mouseMode() == CartesianPlot::SelectionMode && m_hovered) { +/*! + * \brief XYCurvePrivate::setHover + * Will be called from CartesianPlot::hoverMoveEvent which + * determines, which curve is hovered + * \param on + */ +void XYCurvePrivate::setHover(bool on) { + + if(on == m_hovered) + return; // don't update if state not changed + + if(!on){ m_hovered = false; emit q->unhovered(); update(); + return; } + m_hovered = true; + emit q->hovered(); + update(); } void XYCurvePrivate::setPrinting(bool on) { Index: src/backend/worksheet/plots/cartesian/XYCurvePrivate.h =================================================================== --- src/backend/worksheet/plots/cartesian/XYCurvePrivate.h +++ src/backend/worksheet/plots/cartesian/XYCurvePrivate.h @@ -55,6 +55,7 @@ void updatePixmap(); void setPrinting(bool); void suppressRetransform(bool); + void setHover(bool on); //data source const AbstractColumn* xColumn; @@ -135,8 +136,7 @@ private: void contextMenuEvent(QGraphicsSceneContextMenuEvent*) override; - void hoverEnterEvent(QGraphicsSceneHoverEvent*) override; - void hoverLeaveEvent(QGraphicsSceneHoverEvent*) override; + void mousePressEvent(QGraphicsSceneMouseEvent*) override; void paint(QPainter*, const QStyleOptionGraphicsItem*, QWidget* widget = nullptr) override; void drawSymbols(QPainter*);