File indexing completed on 2024-05-12 15:27:00
0001 /*************************************************************************** 0002 File : Interval.h 0003 Project : LabPlot 0004 -------------------------------------------------------------------- 0005 Copyright : (C) 2007 by Tilman Benkert (thzs@gmx.net) 0006 Copyright : (C) 2007 by Knut Franke (knut.franke@gmx.de) 0007 Copyright : (C) 2012 by Alexander Semke (alexander.semke@web.de) 0008 Description : Auxiliary class for interval based data 0009 0010 ***************************************************************************/ 0011 0012 /*************************************************************************** 0013 * * 0014 * This program is free software; you can redistribute it and/or modify * 0015 * it under the terms of the GNU General Public License as published by * 0016 * the Free Software Foundation; either version 2 of the License, or * 0017 * (at your option) any later version. * 0018 * * 0019 * This program is distributed in the hope that it will be useful, * 0020 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 0021 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 0022 * GNU General Public License for more details. * 0023 * * 0024 * You should have received a copy of the GNU General Public License * 0025 * along with this program; if not, write to the Free Software * 0026 * Foundation, Inc., 51 Franklin Street, Fifth Floor, * 0027 * Boston, MA 02110-1301 USA * 0028 * * 0029 ***************************************************************************/ 0030 0031 #ifndef INTERVAL_H 0032 #define INTERVAL_H 0033 0034 #include "backend/worksheet/plots/AbstractCoordinateSystem.h" 0035 0036 extern "C" { 0037 #include "backend/nsl/nsl_math.h" 0038 } 0039 0040 template<class T> class Interval; 0041 0042 template<class T> class IntervalBase { 0043 public: 0044 IntervalBase() : m_start(-1), m_end(-1){} 0045 IntervalBase(T start, T end) { 0046 m_start = start; 0047 m_end = end; 0048 } 0049 virtual ~IntervalBase() = default; 0050 T start() const { return m_start; } 0051 T end() const { return m_end; } 0052 void setStart(T start) { m_start = start; } 0053 void setEnd(T end) { m_end = end; } 0054 bool contains(const Interval<T>& other) const { return ( m_start <= other.start() && m_end >= other.end() ); } 0055 bool contains(T value) const { return ( m_start <= value && m_end >= value ); } 0056 bool fuzzyContains(T value) const { 0057 bool rc1 = nsl_math_definitely_less_than(m_start, value); 0058 bool rc2 = nsl_math_definitely_greater_than(m_end, value); 0059 return (rc1 && rc2); 0060 } 0061 bool intersects(const Interval<T>& other) const { return ( contains(other.start()) || contains(other.end()) ); } 0062 //! Return the intersection of two intervals 0063 /** 0064 * This function returns an invalid interval if the two intervals do not intersect. 0065 */ 0066 static Interval<T> intersection(const Interval<T>& first, const Interval<T>& second) 0067 { 0068 return Interval<T>( qMax(first.start(), second.start()), qMin(first.end(), second.end()) ); 0069 } 0070 void translate(T offset) { m_start += offset; m_end += offset; } 0071 bool operator==(const Interval<T>& other) const { return ( m_start == other.start() && m_end == other.end() ); } 0072 Interval<T>& operator=(const Interval<T>& other) { 0073 m_start = other.start(); 0074 m_end = other.end(); 0075 return *this; 0076 } 0077 //! Returns true if no gap is between two intervals. 0078 virtual bool touches(const Interval<T>& other) const = 0; 0079 //! Merge two intervals that touch or intersect 0080 static Interval<T> merge(const Interval<T>& a, const Interval<T>& b) { 0081 if( !(a.intersects(b) || a.touches(b)) ) 0082 return a; 0083 return Interval<T>( qMin(a.start(), b.start()), qMax(a.end(), b.end()) ); 0084 } 0085 //! Subtract an interval from another 0086 static QVector< Interval<T> > subtract(const Interval<T>& src_iv, const Interval<T>& minus_iv) { 0087 QVector< Interval<T> > list; 0088 if( (src_iv == minus_iv) || (minus_iv.contains(src_iv)) ) 0089 return list; 0090 0091 if( !src_iv.intersects(minus_iv) ) 0092 list.append(src_iv); 0093 else if( src_iv.end() <= minus_iv.end() ) 0094 list.append( Interval<T>(src_iv.start(), minus_iv.start()-1) ); 0095 else if( src_iv.start() >= minus_iv.start() ) 0096 list.append( Interval<T>(minus_iv.end()+1, src_iv.end()) ); 0097 else { 0098 list.append( Interval<T>(src_iv.start(), minus_iv.start()-1) ); 0099 list.append( Interval<T>(minus_iv.end()+1, src_iv.end()) ); 0100 } 0101 0102 return list; 0103 } 0104 //! Split an interval into two 0105 static QVector< Interval<T> > split(const Interval<T>& i, T before) { 0106 QVector< Interval<T> > list; 0107 if( before < i.start() || before > i.end() ) 0108 { 0109 list.append(i); 0110 } 0111 else 0112 { 0113 Interval<T> left(i.start(), before-1); 0114 Interval<T> right(before, i.end()); 0115 if(left.isValid()) 0116 list.append(left); 0117 if(right.isValid()) 0118 list.append(right); 0119 } 0120 return list; 0121 } 0122 //! Merge an interval into a list 0123 /* 0124 * This function merges all intervals in the list until none of them 0125 * intersect or touch anymore. 0126 */ 0127 static void mergeIntervalIntoList(QVector< Interval<T> > * list, Interval<T> i) { 0128 for(int c=0; c<list->size(); c++) 0129 { 0130 if( list->at(c).touches(i) || list->at(c).intersects(i) ) 0131 { 0132 Interval<T> result = merge(list->takeAt(c), i); 0133 mergeIntervalIntoList(list, result); 0134 return; 0135 } 0136 } 0137 list->append(i); 0138 } 0139 //! Restrict all intervals in the list to their intersection with a given interval 0140 /** 0141 * Remark: This may decrease the list size. 0142 */ 0143 static void restrictList(QVector< Interval<T> > * list, Interval<T> i) 0144 { 0145 Interval<T> temp; 0146 for(int c=0; c<list->size(); c++) 0147 { 0148 temp = intersection(list->at(c), i); 0149 if(!temp.isValid()) 0150 list->removeAt(c--); 0151 else 0152 list->replace(c, temp); 0153 } 0154 0155 } 0156 //! Subtract an interval from all intervals in the list 0157 /** 0158 * Remark: This may increase or decrease the list size. 0159 */ 0160 static void subtractIntervalFromList(QVector< Interval<T> > * list, Interval<T> i) { 0161 QVector< Interval<T> > temp_list; 0162 for(int c=0; c<list->size(); c++) 0163 { 0164 temp_list = subtract(list->at(c), i); 0165 if(temp_list.isEmpty()) 0166 list->removeAt(c--); 0167 else 0168 { 0169 list->replace(c, temp_list.at(0)); 0170 if(temp_list.size()>1) 0171 list->insert(c, temp_list.at(1)); 0172 } 0173 } 0174 } 0175 QVector< Interval<T> > operator-(QVector< Interval<T> > subtrahend) { 0176 QVector< Interval<T> > *tmp1, *tmp2; 0177 tmp1 = new QVector< Interval<T> >(); 0178 *tmp1 << *static_cast< Interval<T>* >(this); 0179 foreach(Interval<T> i, subtrahend) { 0180 tmp2 = new QVector< Interval<T> >(); 0181 foreach(Interval<T> j, *tmp1) 0182 *tmp2 << subtract(j, i); 0183 delete tmp1; 0184 tmp1 = tmp2; 0185 } 0186 QVector< Interval<T> > result = *tmp1; 0187 delete tmp1; 0188 return result; 0189 } 0190 0191 //! Return a string in the format '[start,end]' 0192 QString toString() const { 0193 return "[" + QString::number(m_start) + "," + QString::number(m_end) + "]"; 0194 } 0195 0196 protected: 0197 //! Interval start 0198 T m_start; 0199 //! Interval end 0200 T m_end; 0201 }; 0202 0203 //! Auxiliary class for interval based data 0204 /** 0205 * This class represents an interval of 0206 * the type [start,end]. It should be pretty 0207 * self explanatory. 0208 * 0209 * For the template argument (T), only numerical types ((unsigned) short, (unsigned) int, 0210 * (unsigned) long, float, double, long double) are supported. 0211 */ 0212 template<class T> class Interval : public IntervalBase<T> { 0213 public: 0214 Interval() = default; 0215 Interval(T start, T end) : IntervalBase<T>(start, end) {} 0216 Interval(const Interval<T>&) = default; 0217 T size() const { 0218 return IntervalBase<T>::m_end - IntervalBase<T>::m_start + 1; 0219 } 0220 bool isValid() const { 0221 return ( IntervalBase<T>::m_start >= 0 && IntervalBase<T>::m_end >= 0 && 0222 IntervalBase<T>::m_start <= IntervalBase<T>::m_end ); 0223 } 0224 bool touches(const Interval<T>& other) const override { 0225 return ( (other.end() == IntervalBase<T>::m_start-1) || 0226 (other.start() == IntervalBase<T>::m_end+1) ); 0227 } 0228 }; 0229 0230 template<> class Interval<float> : public IntervalBase<float> { 0231 public: 0232 Interval() {} 0233 Interval(float start, float end) : IntervalBase<float>(start, end) {} 0234 Interval(const Interval<float>& other) = default; 0235 float size() const { return IntervalBase<float>::m_end - IntervalBase<float>::m_start; } 0236 bool isValid() const { return ( IntervalBase<float>::m_start <= IntervalBase<float>::m_end ); } 0237 bool touches(const Interval<float>& other) const override { 0238 return ( (other.end() == IntervalBase<float>::m_start) || 0239 (other.start() == IntervalBase<float>::m_end) ); 0240 } 0241 }; 0242 0243 template<> class Interval<double> : public IntervalBase<double> { 0244 public: 0245 Interval() {} 0246 Interval(double start, double end) : IntervalBase<double>(start, end) {} 0247 Interval(const Interval<double>&) = default; 0248 double size() const { return IntervalBase<double>::m_end - IntervalBase<double>::m_start; } 0249 bool isValid() const { return ( IntervalBase<double>::m_start <= IntervalBase<double>::m_end ); } 0250 bool touches(const Interval<double>& other) const override { 0251 return ( (other.end() == IntervalBase<double>::m_start) || 0252 (other.start() == IntervalBase<double>::m_end) ); 0253 } 0254 }; 0255 0256 template<> class Interval<long double> : public IntervalBase<long double> { 0257 public: 0258 Interval() {} 0259 Interval(long double start, long double end) : IntervalBase<long double>(start, end) {} 0260 Interval(const Interval<long double>& other) = default; 0261 long double size() const { return IntervalBase<long double>::m_end - IntervalBase<long double>::m_start; } 0262 bool isValid() const { return ( IntervalBase<long double>::m_start <= IntervalBase<long double>::m_end ); } 0263 bool touches(const Interval<long double>& other) const override { 0264 return ( (other.end() == IntervalBase<long double>::m_start) || 0265 (other.start() == IntervalBase<long double>::m_end) ); 0266 } 0267 }; 0268 0269 #endif 0270