SciDAVis  1.D4
Interval.h
Go to the documentation of this file.
1 /***************************************************************************
2  File : Interval.h
3  Project : SciDAVis
4  --------------------------------------------------------------------
5  Copyright : (C) 2007 by Tilman Benkert,
6  Knut Franke
7  Email (use @ for *) : thzs*gmx.net, knut.franke*gmx.de
8  Description : Auxiliary class for interval based data
9 
10  ***************************************************************************/
11 
12 /***************************************************************************
13  * *
14  * This program is free software; you can redistribute it and/or modify *
15  * it under the terms of the GNU General Public License as published by *
16  * the Free Software Foundation; either version 2 of the License, or *
17  * (at your option) any later version. *
18  * *
19  * This program is distributed in the hope that it will be useful, *
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
22  * GNU General Public License for more details. *
23  * *
24  * You should have received a copy of the GNU General Public License *
25  * along with this program; if not, write to the Free Software *
26  * Foundation, Inc., 51 Franklin Street, Fifth Floor, *
27  * Boston, MA 02110-1301 USA *
28  * *
29  ***************************************************************************/
30 
31 #ifndef INTERVAL_H
32 #define INTERVAL_H
33 
34 #include <QList>
35 #include <QString>
36 #include <QtGlobal>
37 
38 // forward declaration
39 template<class T> class Interval;
40 
41 template<class T> class IntervalBase
42 {
43  public:
44  IntervalBase() : d_start(-1), d_end(-1){}
45  IntervalBase(const IntervalBase<T>& other) {
46  d_start = other.start();
47  d_end = other.end();
48  }
49  IntervalBase(T start, T end) {
50  d_start = start;
51  d_end = end;
52  }
53  virtual ~IntervalBase() {}
54  T start() const { return d_start; }
55  T end() const { return d_end; }
56  void setStart(T start) { d_start = start; }
57  void setEnd(T end) { d_end = end; }
58  bool contains(const Interval<T>& other) const { return ( d_start <= other.start() && d_end >= other.end() ); }
59  bool contains(T value) const { return ( d_start <= value && d_end >= value ); }
60  bool intersects(const Interval<T>& other) const { return ( contains(other.start()) || contains(other.end()) ); }
62 
65  static Interval<T> intersection(const Interval<T>& first, const Interval<T>& second)
66  {
67  return Interval<T>( qMax(first.start(), second.start()), qMin(first.end(), second.end()) );
68  }
69  void translate(T offset) { d_start += offset; d_end += offset; }
70  bool operator==(const Interval<T>& other) const { return ( d_start == other.start() && d_end == other.end() ); }
71  Interval<T>& operator=(const Interval<T>& other) {
72  d_start = other.start();
73  d_end = other.end();
74  return *this;
75  }
77  virtual bool touches(const Interval<T>& other) const = 0;
79  static Interval<T> merge(const Interval<T>& a, const Interval<T>& b) {
80  if( !(a.intersects(b) || a.touches(b)) )
81  return a;
82  return Interval<T>( qMin(a.start(), b.start()), qMax(a.end(), b.end()) );
83  }
85  static QList< Interval<T> > subtract(const Interval<T>& src_iv, const Interval<T>& minus_iv) {
86  QList< Interval<T> > list;
87  if( (src_iv == minus_iv) || (minus_iv.contains(src_iv)) )
88  return list;
89 
90  if( !src_iv.intersects(minus_iv) )
91  list.append(src_iv);
92  else if( src_iv.end() <= minus_iv.end() )
93  list.append( Interval<T>(src_iv.start(), minus_iv.start()-1) );
94  else if( src_iv.start() >= minus_iv.start() )
95  list.append( Interval<T>(minus_iv.end()+1, src_iv.end()) );
96  else {
97  list.append( Interval<T>(src_iv.start(), minus_iv.start()-1) );
98  list.append( Interval<T>(minus_iv.end()+1, src_iv.end()) );
99  }
100 
101  return list;
102  }
104  static QList< Interval<T> > split(const Interval<T>& i, T before) {
105  QList< Interval<T> > list;
106  if( before < i.start() || before > i.end() )
107  {
108  list.append(i);
109  }
110  else
111  {
112  Interval<T> left(i.start(), before-1);
113  Interval<T> right(before, i.end());
114  if(left.isValid())
115  list.append(left);
116  if(right.isValid())
117  list.append(right);
118  }
119  return list;
120  }
122  /*
123  * This function merges all intervals in the list until none of them
124  * intersect or touch anymore.
125  */
126  static void mergeIntervalIntoList(QList< Interval<T> > * list, Interval<T> i) {
127  for(int c=0; c<list->size(); c++)
128  {
129  if( list->at(c).touches(i) || list->at(c).intersects(i) )
130  {
131  Interval<T> result = merge(list->takeAt(c), i);
132  mergeIntervalIntoList(list, result);
133  return;
134  }
135  }
136  list->append(i);
137  }
139 
142  static void restrictList(QList< Interval<T> > * list, Interval<T> i)
143  {
144  Interval<T> temp;
145  for(int c=0; c<list->size(); c++)
146  {
147  temp = intersection(list->at(c), i);
148  if(!temp.isValid())
149  list->removeAt(c--);
150  else
151  list->replace(c, temp);
152  }
153 
154  }
156 
159  static void subtractIntervalFromList(QList< Interval<T> > * list, Interval<T> i) {
160  QList< Interval<T> > temp_list;
161  for(int c=0; c<list->size(); c++)
162  {
163  temp_list = subtract(list->at(c), i);
164  if(temp_list.isEmpty())
165  list->removeAt(c--);
166  else
167  {
168  list->replace(c, temp_list.at(0));
169  if(temp_list.size()>1)
170  list->insert(c, temp_list.at(1));
171  }
172  }
173  }
174  QList< Interval<T> > operator-(QList< Interval<T> > subtrahend) {
175  QList< Interval<T> > *tmp1, *tmp2;
176  tmp1 = new QList< Interval<T> >();
177  *tmp1 << *static_cast< Interval<T>* >(this);
178  foreach(Interval<T> i, subtrahend) {
179  tmp2 = new QList< Interval<T> >();
180  foreach(Interval<T> j, *tmp1)
181  *tmp2 << subtract(j, i);
182  delete tmp1;
183  tmp1 = tmp2;
184  }
185  QList< Interval<T> > result = *tmp1;
186  delete tmp1;
187  return result;
188  }
190  QString toString() const {
191  return "[" + QString::number(d_start) + "," + QString::number(d_end) + "]";
192  }
193 
194  protected:
196  T d_start;
198  T d_end;
199 };
200 
202 
210 template<class T> class Interval : public IntervalBase<T>
211 {
212  public:
213  Interval() {}
214  Interval(T start, T end) : IntervalBase<T>(start, end) {}
215  Interval(const Interval<T>& other) : IntervalBase<T>(other) {}
216  T size() const {
217  return IntervalBase<T>::d_end - IntervalBase<T>::d_start + 1;
218  }
219  bool isValid() const {
220  return ( IntervalBase<T>::d_start >= 0 && IntervalBase<T>::d_end >= 0 &&
221  IntervalBase<T>::d_start <= IntervalBase<T>::d_end );
222  }
223  bool touches(const Interval<T>& other) const {
224  return ( (other.end() == IntervalBase<T>::d_start-1) ||
225  (other.start() == IntervalBase<T>::d_end+1) );
226  }
227 };
228 
229 template<> class Interval<float> : public IntervalBase<float> {
230  Interval() {}
231  Interval(float start, float end) : IntervalBase<float>(start, end) {}
232  Interval(const Interval<float>& other) : IntervalBase<float>(other) {}
233  float size() const { return IntervalBase<float>::d_end - IntervalBase<float>::d_start; }
234  bool isValid() const { return ( IntervalBase<float>::d_start <= IntervalBase<float>::d_end ); }
235  bool touches(const Interval<float>& other) const {
236  return ( (other.end() == IntervalBase<float>::d_start) ||
237  (other.start() == IntervalBase<float>::d_end) );
238  }
239 };
240 
241 template<> class Interval<double> : public IntervalBase<double> {
242  Interval() {}
243  Interval(double start, double end) : IntervalBase<double>(start, end) {}
244  Interval(const Interval<double>& other) : IntervalBase<double>(other) {}
245  double size() const { return IntervalBase<double>::d_end - IntervalBase<double>::d_start; }
246  bool isValid() const { return ( IntervalBase<double>::d_start <= IntervalBase<double>::d_end ); }
247  bool touches(const Interval<double>& other) const {
248  return ( (other.end() == IntervalBase<double>::d_start) ||
249  (other.start() == IntervalBase<double>::d_end) );
250  }
251 };
252 
253 template<> class Interval<long double> : public IntervalBase<long double> {
254  Interval() {}
255  Interval(long double start, long double end) : IntervalBase<long double>(start, end) {}
256  Interval(const Interval<long double>& other) : IntervalBase<long double>(other) {}
257  long double size() const { return IntervalBase<long double>::d_end - IntervalBase<long double>::d_start; }
258  bool isValid() const { return ( IntervalBase<long double>::d_start <= IntervalBase<long double>::d_end ); }
259  bool touches(const Interval<long double>& other) const {
260  return ( (other.end() == IntervalBase<long double>::d_start) ||
261  (other.start() == IntervalBase<long double>::d_end) );
262  }
263 };
264 
265 #endif
266 
Generated by   doxygen 1.8.1