001 /*
002 * Copyright (c) 2005 Peter Palotas, Fredrik Johansson, Einar Pehrson,
003 * Sebastian Kekkonen, Lars Magnus Lång, Malin Johansson and Sofia Nilsson
004 *
005 * This file is part of
006 * CleanSheets Extension for Assertions
007 *
008 * CleanSheets Extension for Assertions is free software; you can
009 * redistribute it and/or modify it under the terms of the GNU General Public
010 * License as published by the Free Software Foundation; either version 2 of
011 * the License, or (at your option) any later version.
012 *
013 * CleanSheets Extension for Assertions is distributed in the hope that
014 * it will be useful, but WITHOUT ANY WARRANTY; without even the implied
015 * warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
016 * See the GNU General Public License for more details.
017 *
018 * You should have received a copy of the GNU General Public License
019 * along with CleanSheets Extension for Assertions; if not, write to the
020 * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
021 * Boston, MA 02111-1307 USA
022 */
023 package csheets.ext.assertion;
024
025 import java.io.Serializable;
026 import java.util.Iterator;
027 import java.util.List;
028 import java.util.TreeSet;
029
030 /** A class representing (possibly) multiple intervals. This can be used to specify
031 any combination of values to be included in an interval. The MultiInterval is
032 built up by specifying normal intervals to be included or excluded from the
033 MultiInterval.
034 @author Peter Palotas
035 @author Fredrik Johansson
036 */
037 public class MultiInterval implements Iterable<Interval>, Serializable {
038
039 /** The unique version identifier used for serialization */
040 private static final long serialVersionUID = 3311313307922046224L;
041
042 /**
043 Contains a list of the intervals included in this multi interval.
044 <p><b>Invariant:</b> intervalSet does not contain any intersecting or
045 bordering intervals. (Two bordering intervals are eg. [0 to 1[ [1 to 2]
046 which could easily be written as one interval [0 to 2].
047 */
048 private TreeSet<Interval> intervalSet;
049
050 /** Default constructor. Constructs an empty MultiInterval containing no values. Note that if the
051 first operation called on this interval after its construction is <code>exclude()</code>,
052 <b>all</b> values <b>except</b> the ones excluded will be included in this interval.
053 */
054 public MultiInterval() {
055 intervalSet = new TreeSet<Interval>();
056 }
057
058 /** Add an interval to be included in this MultiInterval.
059 @param interval An interval specifying values to be included in this MultiInterval.
060 */
061 public void include(Interval interval) {
062 if (intervalSet.isEmpty()) {
063 intervalSet.add(interval);
064 return;
065 }
066
067 // Check if the new interval intersects with any one already included
068 for (Iterator<Interval> iter = intervalSet.iterator(); iter.hasNext(); ) {
069 Interval i = iter.next();
070
071 // Try to create a union, if successful we should
072 Interval union = Interval.union(i, interval);
073 if (union != null) {
074 // remove the old interval intersecting with the new one and
075 // include the union between them instead.
076 iter.remove();
077 include(union);
078 return;
079 }
080 }
081
082 // The new interval did not intersect with any already included, just add it.
083 intervalSet.add(interval);
084 }
085
086 /** Exclude a specific interval from this MultiInterval. If this MultiInterval is
087 empty (i.e. does not include anything) when this function is called, the MultiInterval
088 will accept <i>any value except the ones included in the interval specified</i>.
089 @param interval an interval specifying which values to exclude from this MultiInterval.
090 */
091 public void exclude(Interval interval) {
092 // If list is empty, we assume we want to include all possible values
093 // except the ones specified. So we add an interval covering all
094 // values to the list.
095 if (intervalSet.isEmpty()) {
096 intervalSet.add(new Interval(Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY, false, false));
097 }
098
099 TreeSet<Interval> nlist = new TreeSet<Interval>();
100
101 for (Iterator<Interval> iter = intervalSet.iterator(); iter.hasNext(); ) {
102 Interval i = iter.next();
103
104
105 if (i.intersects(interval)) {
106 // Check if the lower part of the interval should be included
107 if (i.getLowerLimit() < interval.getLowerLimit() || i.getLowerLimit() == interval.getLowerLimit() &&
108 i.isLowerLimitClosed() && !interval.isLowerLimitClosed()) {
109 nlist.add(new Interval(i.getLowerLimit(), interval.getLowerLimit(), i.isLowerLimitClosed(), !interval.isLowerLimitClosed()));
110 }
111
112 // Check if the upper part of the interval should be included
113 if (i.getUpperLimit() > interval.getUpperLimit() || i.getUpperLimit() == interval.getUpperLimit() &&
114 i.isUpperLimitClosed() && !interval.isUpperLimitClosed()) {
115 nlist.add(new Interval(interval.getUpperLimit(), i.getUpperLimit(), !interval.isUpperLimitClosed(), i.isUpperLimitClosed()));
116 }
117
118 } else {
119 // If the interval to exclude does not intersect the current interval
120 // we keep the current interval as is.
121 nlist.add(i);
122 }
123 }
124 intervalSet = nlist;
125 }
126
127 /** Check if a value is contained in this MultiInterval. <p><b>NOTE:</b> Infinity and NaN is never
128 reported to be included in a MultiInterval.
129 @param value The value to check for.
130 @return <code>true</code> if the value has been specified to be included in this
131 MultiInterval, <code>false</code> otherwise.
132 */
133 public boolean contains(double value) {
134
135 if (Double.isNaN(value) || Double.isInfinite(value))
136 return false;
137
138 for (Iterator<Interval> iter = intervalSet.iterator(); iter.hasNext(); ) {
139 Interval i = iter.next();
140 if (i.contains(value))
141 return true;
142
143 if (i.getUpperLimit() > value)
144 return false;
145 }
146 return false;
147 }
148
149
150 /**
151 * Calculates a negation av a <code>MultiInterval</code>
152 * @param term is the <code>MultiInterval</code> to be negated
153 * @return the negated <code>MultiInterval</code>
154 */
155 public static MultiInterval negate(MultiInterval term) {
156 MultiInterval negation = new MultiInterval();
157 for (Interval i:term.intervalSet)
158 negation.include(Interval.negate(i));
159 return negation;
160 }
161
162 /**
163 * Calculates the sum of two <code>MultiInterval</code>s
164 * @param term1 is the first term
165 * @param term2 is the second term
166 * @return the summarized <code>MultiInterval</code>s
167 */
168 public static MultiInterval add(MultiInterval term1, MultiInterval term2) {
169 MultiInterval sum = new MultiInterval();
170 for (Interval i1:term1.intervalSet)
171 for (Interval i2:term2.intervalSet)
172 sum.include(Interval.add(i1,i2));
173 return sum;
174 }
175
176 /**
177 * Calculates the difference of two <code>MultiInterval</code>s
178 * @param term1 is the first term
179 * @param term2 is the second term
180 * @return the difference of the two <code>MultiInterval</code>s
181 */
182 public static MultiInterval sub(MultiInterval term1, MultiInterval term2) {
183 MultiInterval difference = new MultiInterval();
184 for (Interval i1:term1.intervalSet)
185 for (Interval i2:term2.intervalSet)
186 difference.include(Interval.sub(i1,i2));
187 return difference;
188 }
189
190 /**
191 * Calculates the product of two <code>MultiInterval</code>s
192 * @param factor1 is the first factor
193 * @param factor2 is the second factor
194 * @return the product of thw two <code>MultiInterval</code>s
195 */
196 public static MultiInterval mul(MultiInterval factor1, MultiInterval factor2) {
197 MultiInterval product = new MultiInterval();
198 for (Interval i1:factor1.intervalSet)
199 for (Interval i2:factor2.intervalSet)
200 product.include(Interval.mul(i1,i2));
201 return product;
202 }
203
204 /**
205 * Calculates the quotient of two <code>MultiInterval</code>s
206 * @param numerator is the numerator
207 * @param denominator is the denominator
208 * @return the quotient of the two <code>MultiInterval</code>s
209 */
210 public static MultiInterval div(MultiInterval numerator, MultiInterval denominator) throws MathException {
211 MultiInterval quotient = new MultiInterval();
212 for (Interval i1:numerator.intervalSet)
213 for (Interval i2:denominator.intervalSet)
214 quotient.include(Interval.div(i1,i2));
215 return quotient;
216 }
217
218
219 /**
220 * Calculates the first <code>MultiInterval</code> raised to the power of the second <code>MultiInterval</code>
221 * @param base is the first <code>MultiInterval</code>
222 * @param exponent is the second <code>MultiInterval</code>
223 * @return the first <code>MultiInterval</code> raised to the power of the second <code>MultiInterval</code>
224 * @throws MathException if the first <code>MultiInterval</code> contains values below zero and the second <code>MultiInterval</code> is not build of singel integer value <code>Interval</code>s
225 */
226 public static MultiInterval pow(MultiInterval base, MultiInterval exponent) throws MathException {
227 MultiInterval product = new MultiInterval();
228 for (Interval baseI : base.intervalSet)
229 for (Interval expI : exponent.intervalSet)
230 product.include(Interval.pow(baseI, expI));
231 return product;
232 }
233
234
235 /**
236 * Calculates the cosine <code>MultiInterval</code> of a <code>MultiInterval</code>
237 * @param mInterval is the <code>MultiInterval</code>
238 * @return the cosine <code>MultiInterval</code> of the <code>MultiInterval</code>
239 */
240 public static MultiInterval cos(MultiInterval mInterval) {
241 MultiInterval result = new MultiInterval();
242 for (Interval i : mInterval.intervalSet)
243 result.include(Interval.cos(i));
244 return result;
245 }
246
247 /**
248 * Calculates the sine <code>MultiInterval</code> of a <code>MultiInterval</code>
249 * @param mInterval is the <code>MultiInterval</code>
250 * @return the sine <code>MultiInterval</code> of the <code>MultiInterval</code>
251 */
252 public static MultiInterval sin(MultiInterval mInterval) {
253 MultiInterval result = new MultiInterval();
254 for (Interval i : mInterval.intervalSet)
255 result.include(Interval.sin(i));
256 return result;
257 }
258
259 /**
260 * Calculates the tangent <code>MultiInterval</code> of a <code>MultiInterval</code>
261 * @param mInterval is the <code>MultiInterval</code>
262 * @return the tangent <code>MultiInterval</code> of the <code>MultiInterval</code>
263 */
264 public static MultiInterval tan(MultiInterval mInterval) {
265 MultiInterval result = new MultiInterval();
266 for (Interval i : mInterval.intervalSet)
267 result.include(Interval.tan(i));
268 return result;
269 }
270
271 /**
272 * Calculates the natural logarithm of a <code>MultiInterval</code>
273 * @param mInterval is the <code>MultiInterval</code>
274 * @return the natural logarithm of the <code>MultiInterval</code>
275 * @throws MathException if the <code>MultiInterval</code> contains values below zero
276 */
277
278 public static MultiInterval ln(MultiInterval mInterval) throws MathException {
279 MultiInterval log = new MultiInterval();
280 for (Interval i:mInterval.intervalSet)
281 log.include(Interval.ln(i));
282 return log;
283 }
284
285 /**
286 * Calculates the base 10 logarithm of a <code>MultiInterval</code>
287 * @param mInterval is the <code>MultiInterval</code>
288 * @return the base 10 logarithm of the <code>MultiInterval</code>
289 * @throws MathException if the <code>MultiInterval</code> contains values below zero
290 */
291 public static MultiInterval log10(MultiInterval mInterval) throws MathException {
292 MultiInterval log = new MultiInterval();
293 for (Interval i : mInterval.intervalSet)
294 log.include(Interval.log10(i));
295 return log;
296 }
297
298 /**
299 * Calculates Eulers number e raised to a <code>MultiInterval</code>
300 * @param exponent is the <code>MultiInterval</code>
301 * @return Eulers number e raised to the <code>MultiInterval</code>
302 */
303 public static MultiInterval exp(MultiInterval exponent) {
304 MultiInterval exp = new MultiInterval();
305 for (Interval i : exponent.intervalSet)
306 exp.include(Interval.exp(i));
307 return exp;
308 }
309
310 /**
311 * Calculates the square root of a <code>MultiInterval</code>
312 * @param mInterval is the <code>MultiInterval</code>
313 * @return the square root of the <code>MultiInterval</code>
314 * @throws MathException if the <code>MultiInterval</code> contains values below zero
315 */
316 public static MultiInterval sqrt(MultiInterval mInterval) throws MathException {
317 MultiInterval root = new MultiInterval();
318 for (Interval i : mInterval.intervalSet)
319 root.include(Interval.sqrt(i));
320 return root;
321 }
322
323 /**
324 * Calculates the <code>MultiInterval</code> you get if you convert all values from <code>double</code> to <code>int</code>
325 * @param mInterval is the <code>MultiInterval</code>
326 * @return the <code>MultiInterval</code> you get if you convert the values from <code>double</code> to <code>int</code>
327 */
328 public static MultiInterval toInt(MultiInterval mInterval) {
329 MultiInterval result = new MultiInterval();
330 for (Interval i : mInterval.intervalSet)
331 result.include(Interval.toInt(i));
332 return result;
333 }
334
335 /**
336 * Calculates the absolute value <code>MultiInterval</code> of a <code>MultiInterval</code>
337 * @param mInterval is the <code>MultiInterval</code>
338 * @return the absolute value <code>MultiInterval</code> of the <code>MultiInterval</code>
339 */
340 public static MultiInterval abs(MultiInterval mInterval) {
341 MultiInterval result = new MultiInterval();
342 for (Interval i : mInterval.intervalSet)
343 result.include(Interval.abs(i));
344 return result;
345 }
346
347 /**
348 * Returns a <code>MultiInterval</code> holding all possible values you get from the <code>Math.random()</code> method
349 * @return a <code>MultiInterval</code> holding all possible values you get from the <code>Math.random()</code> mathod
350 */
351 public static MultiInterval rand() {
352 MultiInterval result = new MultiInterval();
353 result.include(Interval.rand());
354 return result;
355 }
356
357 /**
358 * Calculates the factorial of a <code>MultiInterval</code>
359 * @param mInterval is the <code>MultiInterval</code>
360 * @return the factorial of the <code>MultiInterval</code>
361 * @throws MathException if the <code>MultiInterval</code> contains values below zero
362 */
363 public static MultiInterval fact(MultiInterval mInterval) throws MathException {
364 MultiInterval result = new MultiInterval();
365 for (Interval i : mInterval.intervalSet)
366 result.include(Interval.fact(i));
367 return result;
368 }
369
370 /**
371 * Calculates the sum of a <code>List</code> of <code>MultiInterval</code>s
372 * @param terms is the terms to be summarized
373 * @return the sum of the <code>MultiInterval</code>s
374 */
375 public static MultiInterval sum(List<MultiInterval> terms) {
376 MultiInterval sum = new MultiInterval();
377 Iterator<MultiInterval> iter = terms.iterator();
378 if (iter.hasNext())
379 sum = iter.next().clone();
380 while (iter.hasNext()) {
381 sum = MultiInterval.add(sum,iter.next());
382 }
383 return sum;
384 }
385
386 /**
387 * Calculates the average of a <code>List</code> of <code>MultiInterval</code>s
388 * @param terms is the terms
389 * @return the average of the <code>MultiInterval</code>s
390 */
391 public static MultiInterval avg(List<MultiInterval> terms) {
392 MultiInterval size = new MultiInterval();
393 size.include(new Interval(terms.size()));
394 MultiInterval sum = MultiInterval.sum(terms);
395 MultiInterval result = new MultiInterval(); // for the compiler to be happy
396 try {
397 result = MultiInterval.div(sum,size);
398 } catch (MathException e) { // should never happen
399 e.printStackTrace();
400 }
401 return result;
402 }
403
404
405 /** Returns an iterator over the intervals in this MultiInterval in proper sequence.
406 Note that this iterator cannot be used to modify the MultiInterval.
407 @return an iterator over the intervals in this MultiInterval in proper sequence.
408 */
409 public Iterator<Interval> iterator() {
410 return new ConstMultiIntervalIterator(intervalSet.iterator());
411 }
412
413 /** Compares the specified MultiInterval with this MultiInterval for equality.
414 @return <code>true</code> if the two intervals represent the same ranges of values,
415 <code>false</code> otherwise.
416 */
417 public boolean equals(Object o) {
418 if (o == null)
419 return false;
420
421 if (!(o instanceof MultiInterval))
422 return false;
423
424 MultiInterval mi = (MultiInterval)o;
425
426 return intervalSet.equals(mi.intervalSet);
427 }
428
429 /**
430 * Makes a copy of this <code>MultiInterval</code> intance
431 */
432 public MultiInterval clone() {
433 MultiInterval newMI = new MultiInterval();
434 for (Interval i:intervalSet)
435 newMI.include(i);
436 return newMI;
437 }
438
439
440 /** Returns a string representation of this MultiInterval. */
441 public String toString() {
442 String s = "";
443
444 for (Iterator<Interval> iter = intervalSet.iterator(); iter.hasNext(); ) {
445 Interval i = iter.next();
446 s += i.toString();
447 if (iter.hasNext())
448 s += " or ";
449 }
450 return s;
451 }
452 }