diff --git a/src/backend/lib/Interval.h b/src/backend/lib/Interval.h index 10260b984..5a38f6279 100644 --- a/src/backend/lib/Interval.h +++ b/src/backend/lib/Interval.h @@ -1,270 +1,266 @@ /*************************************************************************** File : Interval.h Project : LabPlot -------------------------------------------------------------------- Copyright : (C) 2007 by Tilman Benkert (thzs@gmx.net) Copyright : (C) 2007 by Knut Franke (knut.franke@gmx.de) Copyright : (C) 2012 by Alexander Semke (alexander.semke@web.de) Description : Auxiliary class for interval based data ***************************************************************************/ /*************************************************************************** * * * 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. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the Free Software * * Foundation, Inc., 51 Franklin Street, Fifth Floor, * * Boston, MA 02110-1301 USA * * * ***************************************************************************/ #ifndef INTERVAL_H #define INTERVAL_H #include "backend/worksheet/plots/AbstractCoordinateSystem.h" template class Interval; template class IntervalBase { public: IntervalBase() : m_start(-1), m_end(-1){} - IntervalBase(const IntervalBase& other) { - m_start = other.start(); - m_end = other.end(); - } IntervalBase(T start, T end) { m_start = start; m_end = end; } virtual ~IntervalBase() = default; T start() const { return m_start; } T end() const { return m_end; } void setStart(T start) { m_start = start; } void setEnd(T end) { m_end = end; } bool contains(const Interval& other) const { return ( m_start <= other.start() && m_end >= other.end() ); } bool contains(T value) const { return ( m_start <= value && m_end >= value ); } bool fuzzyContains(T value) const { bool rc1 = AbstractCoordinateSystem::definitelyLessThan(m_start, value); bool rc2 = AbstractCoordinateSystem::definitelyGreaterThan(m_end, value); return (rc1 && rc2); } bool intersects(const Interval& other) const { return ( contains(other.start()) || contains(other.end()) ); } //! Return the intersection of two intervals /** * This function returns an invalid interval if the two intervals do not intersect. */ static Interval intersection(const Interval& first, const Interval& second) { return Interval( qMax(first.start(), second.start()), qMin(first.end(), second.end()) ); } void translate(T offset) { m_start += offset; m_end += offset; } bool operator==(const Interval& other) const { return ( m_start == other.start() && m_end == other.end() ); } Interval& operator=(const Interval& other) { m_start = other.start(); m_end = other.end(); return *this; } //! Returns true if no gap is between two intervals. virtual bool touches(const Interval& other) const = 0; //! Merge two intervals that touch or intersect static Interval merge(const Interval& a, const Interval& b) { if( !(a.intersects(b) || a.touches(b)) ) return a; return Interval( qMin(a.start(), b.start()), qMax(a.end(), b.end()) ); } //! Subtract an interval from another static QVector< Interval > subtract(const Interval& src_iv, const Interval& minus_iv) { QVector< Interval > list; if( (src_iv == minus_iv) || (minus_iv.contains(src_iv)) ) return list; if( !src_iv.intersects(minus_iv) ) list.append(src_iv); else if( src_iv.end() <= minus_iv.end() ) list.append( Interval(src_iv.start(), minus_iv.start()-1) ); else if( src_iv.start() >= minus_iv.start() ) list.append( Interval(minus_iv.end()+1, src_iv.end()) ); else { list.append( Interval(src_iv.start(), minus_iv.start()-1) ); list.append( Interval(minus_iv.end()+1, src_iv.end()) ); } return list; } //! Split an interval into two static QVector< Interval > split(const Interval& i, T before) { QVector< Interval > list; if( before < i.start() || before > i.end() ) { list.append(i); } else { Interval left(i.start(), before-1); Interval right(before, i.end()); if(left.isValid()) list.append(left); if(right.isValid()) list.append(right); } return list; } //! Merge an interval into a list /* * This function merges all intervals in the list until none of them * intersect or touch anymore. */ static void mergeIntervalIntoList(QVector< Interval > * list, Interval i) { for(int c=0; csize(); c++) { if( list->at(c).touches(i) || list->at(c).intersects(i) ) { Interval result = merge(list->takeAt(c), i); mergeIntervalIntoList(list, result); return; } } list->append(i); } //! Restrict all intervals in the list to their intersection with a given interval /** * Remark: This may decrease the list size. */ static void restrictList(QVector< Interval > * list, Interval i) { Interval temp; for(int c=0; csize(); c++) { temp = intersection(list->at(c), i); if(!temp.isValid()) list->removeAt(c--); else list->replace(c, temp); } } //! Subtract an interval from all intervals in the list /** * Remark: This may increase or decrease the list size. */ static void subtractIntervalFromList(QVector< Interval > * list, Interval i) { QVector< Interval > temp_list; for(int c=0; csize(); c++) { temp_list = subtract(list->at(c), i); if(temp_list.isEmpty()) list->removeAt(c--); else { list->replace(c, temp_list.at(0)); if(temp_list.size()>1) list->insert(c, temp_list.at(1)); } } } QVector< Interval > operator-(QVector< Interval > subtrahend) { QVector< Interval > *tmp1, *tmp2; tmp1 = new QVector< Interval >(); *tmp1 << *static_cast< Interval* >(this); foreach(Interval i, subtrahend) { tmp2 = new QVector< Interval >(); foreach(Interval j, *tmp1) *tmp2 << subtract(j, i); delete tmp1; tmp1 = tmp2; } QVector< Interval > result = *tmp1; delete tmp1; return result; } //! Return a string in the format '[start,end]' QString toString() const { return "[" + QString::number(m_start) + "," + QString::number(m_end) + "]"; } protected: //! Interval start T m_start; //! Interval end T m_end; }; //! Auxiliary class for interval based data /** * This class represents an interval of * the type [start,end]. It should be pretty * self explanatory. * * For the template argument (T), only numerical types ((unsigned) short, (unsigned) int, * (unsigned) long, float, double, long double) are supported. */ template class Interval : public IntervalBase { public: Interval() = default; Interval(T start, T end) : IntervalBase(start, end) {} Interval(const Interval&) = default; T size() const { return IntervalBase::m_end - IntervalBase::m_start + 1; } bool isValid() const { return ( IntervalBase::m_start >= 0 && IntervalBase::m_end >= 0 && IntervalBase::m_start <= IntervalBase::m_end ); } bool touches(const Interval& other) const override { return ( (other.end() == IntervalBase::m_start-1) || (other.start() == IntervalBase::m_end+1) ); } }; template<> class Interval : public IntervalBase { public: Interval() {} Interval(float start, float end) : IntervalBase(start, end) {} Interval(const Interval& other) = default; float size() const { return IntervalBase::m_end - IntervalBase::m_start; } bool isValid() const { return ( IntervalBase::m_start <= IntervalBase::m_end ); } bool touches(const Interval& other) const override { return ( (other.end() == IntervalBase::m_start) || (other.start() == IntervalBase::m_end) ); } }; template<> class Interval : public IntervalBase { public: Interval() {} Interval(double start, double end) : IntervalBase(start, end) {} Interval(const Interval&) = default; double size() const { return IntervalBase::m_end - IntervalBase::m_start; } bool isValid() const { return ( IntervalBase::m_start <= IntervalBase::m_end ); } bool touches(const Interval& other) const override { return ( (other.end() == IntervalBase::m_start) || (other.start() == IntervalBase::m_end) ); } }; template<> class Interval : public IntervalBase { public: Interval() {} Interval(long double start, long double end) : IntervalBase(start, end) {} Interval(const Interval& other) = default; long double size() const { return IntervalBase::m_end - IntervalBase::m_start; } bool isValid() const { return ( IntervalBase::m_start <= IntervalBase::m_end ); } bool touches(const Interval& other) const override { return ( (other.end() == IntervalBase::m_start) || (other.start() == IntervalBase::m_end) ); } }; #endif diff --git a/src/backend/lib/IntervalAttribute.h b/src/backend/lib/IntervalAttribute.h index bd0db40b6..46017da10 100644 --- a/src/backend/lib/IntervalAttribute.h +++ b/src/backend/lib/IntervalAttribute.h @@ -1,290 +1,274 @@ /*************************************************************************** File : IntervalAttribute.h Project : LabPlot -------------------------------------------------------------------- Copyright : (C) 2007 by Knut Franke (knut.franke@gmx.de) Copyright : (C) 2007 by Tilman Benkert (thzs@gmx.net) Description : A class representing an interval-based attribute ***************************************************************************/ /*************************************************************************** * * * 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. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with m_intervals program; if not, write to the Free Software * * Foundation, Inc., 51 Franklin Street, Fifth Floor, * * Boston, MA 02110-1301 USA * * * ***************************************************************************/ #ifndef INTERVALATTRIBUTE_H #define INTERVALATTRIBUTE_H #include "Interval.h" #include //! A class representing an interval-based attribute template class IntervalAttribute { public: void setValue(const Interval& i, T value) { // first: subtract the new interval from all others QVector< Interval > temp_list; for (int c = 0; c < m_intervals.size(); c++) { temp_list = Interval::subtract(m_intervals.at(c), i); if (temp_list.isEmpty()) { m_intervals.removeAt(c); m_values.removeAt(c--); } else { m_intervals.replace(c, temp_list.at(0)); if (temp_list.size() > 1) { m_intervals.insert(c, temp_list.at(1)); m_values.insert(c, m_values.at(c)); } } } // second: try to merge the new interval with an old one for (int c = 0; c < m_intervals.size(); c++) { if (m_intervals.at(c).touches(i) && m_values.at(c) == value) { m_intervals.replace(c, Interval::merge(m_intervals.at(c), i)); return; } } // if it could not be merged, just append it m_intervals.append(i); m_values.append(value); } // overloaded for convenience void setValue(int row, T value) { setValue(Interval(row, row), value); } T value(int row) const { for(int c=m_intervals.size()-1; c>=0; c--) { if(m_intervals.at(c).contains(row)) return m_values.at(c); } return T(); } void insertRows(int before, int count) { QVector< Interval > temp_list; // first: split all intervals that contain 'before' for(int c=0; c::split(m_intervals.at(c), before); m_intervals.replace(c, temp_list.at(0)); if(temp_list.size()>1) { m_intervals.insert(c, temp_list.at(1)); m_values.insert(c, m_values.at(c)); c++; } } } // second: translate all intervals that start at 'before' or later for(int c=0; c= before) m_intervals[c].translate(count); } } void removeRows(int first, int count) { QVector< Interval > temp_list; Interval i(first, first+count-1); // first: remove the relevant rows from all intervals for(int c=0; c::subtract(m_intervals.at(c), i); if(temp_list.isEmpty()) { m_intervals.removeAt(c); m_values.removeAt(c--); } else { m_intervals.replace(c, temp_list.at(0)); if(temp_list.size()>1) { m_intervals.insert(c, temp_list.at(1)); m_values.insert(c, m_values.at(c)); c++; } } } // second: translate all intervals that start at 'first+count' or later for(int c=0; c= first+count) m_intervals[c].translate(-count); } // third: merge as many intervals as possible QVector values_copy = m_values; QVector< Interval > intervals_copy = m_intervals; m_values.clear(); m_intervals.clear(); for(int c=0; c::merge(m_intervals.at(cc),i)); return; } } // if it could not be merged, just append it m_intervals.append(i); m_values.append(value); } } void clear() { m_values.clear(); m_intervals.clear(); } QVector< Interval > intervals() const { return m_intervals; } QVector values() const { return m_values; } - IntervalAttribute& operator=(const IntervalAttribute& other) { - m_intervals.clear(); - m_values.clear(); - foreach( Interval iv, other.intervals()) - m_intervals.append(iv); - foreach( T value, other.values()) - m_values.append(value); - return *this; - } private: QVector m_values; QVector< Interval > m_intervals; }; //! A class representing an interval-based attribute (bool version) template<> class IntervalAttribute { public: IntervalAttribute() {} IntervalAttribute(const QVector< Interval >& intervals) : m_intervals(intervals) {} - IntervalAttribute& operator=(const IntervalAttribute& other) - { - m_intervals.clear(); - foreach(const Interval& iv, other.intervals()) - m_intervals.append(iv); - return *this; - } void setValue(const Interval& i, bool value=true) { if(value) { foreach(const Interval& iv, m_intervals) if(iv.contains(i)) return; Interval::mergeIntervalIntoList(&m_intervals, i); } else { // unset Interval::subtractIntervalFromList(&m_intervals, i); } } void setValue(int row, bool value) { setValue(Interval(row, row), value); } bool isSet(int row) const { foreach(Interval iv, m_intervals) if(iv.contains(row)) return true; return false; } bool isSet(const Interval& i) const { foreach(Interval iv, m_intervals) if(iv.contains(i)) return true; return false; } void insertRows(int before, int count) { QVector< Interval > temp_list; int c; // first: split all intervals that contain 'before' for(c=0; c::split(m_intervals.at(c), before); m_intervals.replace(c, temp_list.at(0)); if(temp_list.size()>1) m_intervals.insert(c++, temp_list.at(1)); } } // second: translate all intervals that start at 'before' or later for(c=0; c= before) m_intervals[c].translate(count); } } void removeRows(int first, int count) { int c; // first: remove the relevant rows from all intervals Interval::subtractIntervalFromList(&m_intervals, Interval(first, first+count-1)); // second: translate all intervals that start at 'first+count' or later for(c=0; c= first+count) m_intervals[c].translate(-count); } // third: merge as many intervals as possible for(c=m_intervals.size()-1; c>=0; c--) { Interval iv = m_intervals.takeAt(c); int size_before = m_intervals.size(); Interval::mergeIntervalIntoList(&m_intervals, iv); if(size_before == m_intervals.size()) // merge successful c--; } } QVector< Interval > intervals() const { return m_intervals; } void clear() { m_intervals.clear(); } private: QVector< Interval > m_intervals; }; #endif