package org.spaceroots.mantissa.utilities;
import java.util.ArrayList;
import java.util.List;
import java.util.Iterator;
/** This class represents an intervals list.
* An interval list represent a list of contiguous regions on the
* real line. All intervals of the list are disjoints to each other,
* they are stored in ascending order.
* The class supports the main set operations like union and
* intersection.
* @see Interval
* @author Luc Maisonobe
* @version $Id: IntervalsList.java 1694 2006-09-03 19:53:48Z luc $
*/
public class IntervalsList {
/** Build an empty intervals list.
*/
public IntervalsList() {
intervals = new ArrayList();
}
/** Build an intervals list containing only one interval.
* @param a first bound of the interval
* @param b second bound of the interval
*/
public IntervalsList(double a, double b) {
intervals = new ArrayList();
intervals.add(new Interval(a, b));
}
/** Build an intervals list containing only one interval.
* @param i interval
*/
public IntervalsList(Interval i) {
intervals = new ArrayList();
intervals.add(i);
}
/** Build an intervals list containing two intervals.
* @param i1 first interval
* @param i2 second interval
*/
public IntervalsList(Interval i1, Interval i2) {
intervals = new ArrayList();
if (i1.intersects(i2)) {
intervals.add(new Interval(Math.min(i1.getInf(), i2.getInf()),
Math.max(i1.getSup(), i2.getSup())));
} else if (i1.getSup () < i2.getInf()) {
intervals.add(i1);
intervals.add(i2);
} else {
intervals.add(i2);
intervals.add(i1);
}
}
/** Copy constructor.
* The copy operation is a deep copy: the underlying intervals
* are independant of the instances of the copied list.
* @param list intervals list to copy
*/
public IntervalsList(IntervalsList list) {
intervals = new ArrayList(list.intervals.size());
for (Iterator iterator = list.intervals.iterator(); iterator.hasNext();) {
intervals.add(new Interval((Interval) iterator.next()));
}
}
/** Check if the instance is empty.
* @return true if the instance is empty
*/
public boolean isEmpty() {
return intervals.isEmpty();
}
/** Check if the instance is connected.
* An interval list is connected if it contains only one
* interval.
* @return true is the instance is connected
*/
public boolean isConnex() {
return intervals.size() == 1;
}
/** Get the lower bound of the list.
* @return lower bound of the list or Double.NaN if the list does
* not contain any interval
*/
public double getInf() {
return intervals.isEmpty()
? Double.NaN : ((Interval) intervals.get(0)).getInf();
}
/** Get the upper bound of the list.
* @return upper bound of the list or Double.NaN if the list does
* not contain any interval
*/
public double getSup() {
return intervals.isEmpty()
? Double.NaN : ((Interval) intervals.get(intervals.size() - 1)).getSup();
}
/** Get the number of intervals of the list.
* @return number of intervals in the list
*/
public int getSize() {
return intervals.size();
}
/** Get an interval from the list.
* @param i index of the interval
* @return interval at index i
*/
public Interval getInterval(int i) {
return (Interval) intervals.get(i);
}
/** Get the ordered list of disjoints intervals.
* @return list of disjoints intervals in ascending order
*/
public List getIntervals() {
return intervals;
}
/** Check if the list contains a point.
* @param x point to check
* @return true if the list contains x
*/
public boolean contains(double x) {
for (Iterator iterator = intervals.iterator(); iterator.hasNext();) {
if (((Interval) iterator.next()).contains(x)) {
return true;
}
}
return false;
}
/** Check if the list contains an interval.
* @param i interval to check
* @return true if i is completely included in the instance
*/
public boolean contains(Interval i) {
for (Iterator iterator = intervals.iterator(); iterator.hasNext();) {
if (((Interval) iterator.next()).contains(i)) {
return true;
}
}
return false;
}
/** Check if an interval intersects the instance.
* @param i interval to check
* @return true if i intersects the instance
*/
public boolean intersects(Interval i) {
for (Iterator iterator = intervals.iterator(); iterator.hasNext();) {
if (((Interval) iterator.next()).intersects(i)) {
return true;
}
}
return false;
}
/** Add an interval to the instance.
* This method expands the instance.
* This operation is a union operation. The number of intervals
* in the list can decrease if the interval fills some holes between
* existing intervals in the list.
* @param i interval to add to the instance
*/
public void addToSelf(Interval i) {
List newIntervals = new ArrayList();
double inf = Double.NaN;
double sup = Double.NaN;
boolean pending = false;
boolean processed = false;
for (Iterator iterator = intervals.iterator(); iterator.hasNext();) {
Interval local = (Interval) iterator.next();
if (local.getSup() < i.getInf()) {
newIntervals.add(local);
} else if (local.getInf() < i.getSup()) {
if (! pending) {
inf = Math.min(local.getInf(), i.getInf());
pending = true;
processed = true;
}
sup = Math.max(local.getSup(), i.getSup());
} else {
if (pending) {
newIntervals.add(new Interval(inf, sup));
pending = false;
} else if (! processed) {
newIntervals.add(i);
}
processed = true;
newIntervals.add(local);
}
}
if (pending) {
newIntervals.add(new Interval(inf, sup));
} else if (! processed) {
newIntervals.add(i);
}
intervals = newIntervals;
}
/** Add an intervals list and an interval.
* @param list intervals list
* @param i interval
* @return a new intervals list which is the union of list and i
*/
public static IntervalsList add(IntervalsList list, Interval i) {
IntervalsList copy = new IntervalsList(list);
copy.addToSelf(i);
return copy;
}
/** Remove an interval from the list.
* This method reduces the instance. This operation is defined in
* terms of points set operation. As an example, if the [2, 3]
* interval is subtracted from the list containing only the [0, 10]
* interval, the result will be the [0, 2] U [3, 10] intervals
* list.
* @param i interval to remove
*/
public void subtractFromSelf(Interval i) {
double a = Math.min(getInf(), i.getInf());
double b = Math.max(getSup(), i.getSup());
intersectSelf(new IntervalsList(new Interval(a - 1.0, i.getInf()),
new Interval(i.getSup(), b + 1.0)));
}
/** Remove an interval from a list.
* @param list intervals list
* @param i interval to remove
* @return a new intervals list
*/
public static IntervalsList subtract(IntervalsList list, Interval i) {
IntervalsList copy = new IntervalsList(list);
copy.subtractFromSelf(i);
return copy;
}
/** Intersects the instance and an interval.
* @param i interval
*/
public void intersectSelf(Interval i) {
List newIntervals = new ArrayList();
for (Iterator iterator = intervals.iterator(); iterator.hasNext();) {
Interval local = (Interval) iterator.next();
if (local.intersects(i)) {
newIntervals.add(Interval.intersection(local, i));
}
}
intervals = newIntervals;
}
/** Intersect a list and an interval.
* @param list intervals list
* @param i interval
* @return the intersection of list and i
*/
public static IntervalsList intersection(IntervalsList list, Interval i) {
IntervalsList copy = new IntervalsList(list);
copy.intersectSelf(i);
return copy;
}
/** Add an intervals list to the instance.
* This method expands the instance.
* This operation is a union operation. The number of intervals
* in the list can decrease if the list fills some holes between
* existing intervals in the instance.
* @param list intervals list to add to the instance
*/
public void addToSelf(IntervalsList list) {
for (Iterator iterator = list.intervals.iterator(); iterator.hasNext();) {
addToSelf((Interval) iterator.next());
}
}
/** Add two intervals lists.
* @param list1 first intervals list
* @param list2 second intervals list
* @return a new intervals list which is the union of list1 and list2
*/
public static IntervalsList add(IntervalsList list1, IntervalsList list2) {
IntervalsList copy = new IntervalsList(list1);
copy.addToSelf(list2);
return copy;
}
/** Remove an intervals list from the instance.
* @param list intervals list to remove
*/
public void subtractFromSelf(IntervalsList list) {
for (Iterator iterator = list.intervals.iterator(); iterator.hasNext();) {
subtractFromSelf((Interval) iterator.next());
}
}
/** Remove an intervals list from another one.
* @param list1 intervals list
* @param list2 intervals list to remove
* @return a new intervals list
*/
public static IntervalsList subtract(IntervalsList list1, IntervalsList list2) {
IntervalsList copy = new IntervalsList(list1);
copy.subtractFromSelf(list2);
return copy;
}
/** Intersect the instance and another intervals list.
* @param list list to intersect with the instance
*/
public void intersectSelf(IntervalsList list) {
intervals = intersection(this, list).intervals;
}
/** Intersect two intervals lists.
* @param list1 first intervals list
* @param list2 second intervals list
* @return a new list which is the intersection of list1 and list2
*/
public static IntervalsList intersection(IntervalsList list1, IntervalsList list2) {
IntervalsList list = new IntervalsList();
for (Iterator iterator = list2.intervals.iterator(); iterator.hasNext();) {
list.addToSelf(intersection(list1, (Interval) iterator.next()));
}
return list;
}
/** The list of intervals. */
private List intervals;
}
Ads help maintain this website.