Author: desruisseaux
Date: Sun Feb 10 19:40:10 2013
New Revision: 1444589
URL: http://svn.apache.org/r1444589
Log:
Reduce the number of comparisons done in the intersect(Range<?>) implementation,
and take the inclusive/exclusive states in account.
Modified:
sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/measure/Range.java
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/measure/RangeTest.java
Modified:
sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/measure/Range.java
URL:
http://svn.apache.org/viewvc/sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/measure/Range.java?rev=1444589&r1=1444588&r2=1444589&view=diff
==============================================================================
---
sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/measure/Range.java
(original)
+++
sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/measure/Range.java
Sun Feb 10 19:40:10 2013
@@ -117,6 +117,16 @@ public class Range<T extends Comparable<
}
/**
+ * Creates a new range using the same element class than this range. This
method will
+ * be overridden by subclasses in order to create a range of a more
specific type.
+ */
+ Range<T> create(final T minValue, final boolean isMinIncluded,
+ final T maxValue, final boolean isMaxIncluded)
+ {
+ return new Range<>(elementType, minValue, isMinIncluded, maxValue,
isMaxIncluded);
+ }
+
+ /**
* Ensures that the given range uses the same element class than this
range,
* then return the casted argument value.
*
@@ -324,12 +334,69 @@ public class Range<T extends Comparable<
(compareMaxTo(range.maxValue, range.isMaxIncluded ? 0 : +1) >=
0);
}
+ /**
+ * Returns {@code true} if this range intersects the given range.
+ *
+ * @param range The range to check for intersection with this range.
+ * @return {@code true} if the given range intersects this range.
+ * @throws IllegalArgumentException is the given range can not be
converted to a valid type
+ * through widening conversion, or if the units of measurement are
not convertible.
+ */
+ public boolean intersects(final Range<?> range) throws
IllegalArgumentException {
+ return intersectsNC(ensureCompatible(range));
+ }
- public boolean intersects(final Range<T> value) throws
IllegalArgumentException
- {
- ensureCompatible(value);
+ /**
+ * Implementation of {@link #intersects(Range)} to be invoked directly by
subclasses.
+ * "NC" stands for "No Conversion" - this method does not try to convert
the bounds
+ * to a compatible type.
+ */
+ final boolean intersectsNC(final Range<? extends T> range) {
+ return (compareMinTo(range.maxValue, range.isMaxIncluded ? 0 : +1) <=
0) &&
+ (compareMaxTo(range.minValue, range.isMinIncluded ? 0 : -1) >=
0);
+ }
- return this.contains(value.getMinValue()) ||
this.contains(value.getMaxValue());
+ /**
+ * Returns the intersection between this range and the given range.
+ *
+ * @param range The range to intersect.
+ * @return The intersection of this range with the given range.
+ * @throws IllegalArgumentException is the given range can not be
converted to a valid type
+ * through widening conversion, or if the units of measurement are
not convertible.
+ */
+ public Range<?> intersect(final Range<?> range) throws
IllegalArgumentException {
+ return intersectNC(ensureCompatible(range));
+ }
+
+ /**
+ * Implementation of {@link #intersect(Range)} to be invoked directly by
subclasses.
+ * "NC" stands for "No Conversion" - this method does not try to convert
the bounds
+ * to a compatible type.
+ */
+ final Range<? extends T> intersectNC(final Range<? extends T> range)
+ throws IllegalArgumentException
+ {
+ /*
+ * For two ranges [Lâ ⦠Hâ] and [Lâ ⦠Hâ], the
intersection is given by
+ * ([max(Lâ, Lâ) ⦠min(Hâ, Hâ)]). Only two comparisons is
needed.
+ *
+ * There is a small complication since we shall also handle the
inclusive states.
+ * so instead than extracting the minimal and maximal values directly,
we will
+ * find which range contains the highest minimal value, and which
range contains
+ * the smallest maximal value. If we find the same range in both case
(which can
+ * be either 'this' or 'range), return that range. Otherwise we need
to create a
+ * new one.
+ */
+ final Range<? extends T> intersect, min, max;
+ min = compareMinTo(range.minValue, range.isMinIncluded ? 0 : -1) < 0 ?
range : this;
+ max = compareMaxTo(range.maxValue, range.isMaxIncluded ? 0 : +1) > 0 ?
range : this;
+ if (min == max) {
+ intersect = min;
+ } else {
+ intersect = create(min.minValue, min.isMinIncluded, max.maxValue,
max.isMaxIncluded);
+ }
+ assert intersect.isEmpty() == !intersects(range) : intersect;
+ return intersect;
}
public Range<T> union(final Range<T> value) throws IllegalArgumentException
@@ -366,46 +433,6 @@ public class Range<T extends Comparable<
return new Range<>(this.elementType, rangeMin, rangeMax );
}
- public Range<T> intersect(final Range<T> value) throws
IllegalArgumentException
- {
- ensureCompatible(value);
-
- //return empty set if the Ranges don't intersect
- if (!this.intersects(value))
- {
- return new Range<>(elementType, maxValue, minValue);
- }
-
- //if they are equal, return the passed in value
- if (this.equals(value))
- {
- return value;
- }
-
- //we knkow they intersect, the question is where.
- T rangeMin, rangeMax;
- if (this.contains(value.getMinValue()))
- {
- rangeMin = value.getMinValue();
- }
- else
- {
- rangeMin = minValue;
- }
-
- if (this.contains(value.getMaxValue()))
- {
- rangeMax = value.getMaxValue();
- }
- else
- {
- rangeMax = maxValue;
- }
-
- return new Range<>(this.elementType, rangeMin, rangeMax );
-
- }
-
//TODO: implement this
public Range<T>[] subtract(final Range<T> value) throws
IllegalArgumentException
{
Modified:
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/measure/RangeTest.java
URL:
http://svn.apache.org/viewvc/sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/measure/RangeTest.java?rev=1444589&r1=1444588&r2=1444589&view=diff
==============================================================================
---
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/measure/RangeTest.java
(original)
+++
sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/measure/RangeTest.java
Sun Feb 10 19:40:10 2013
@@ -205,7 +205,7 @@ public final strictfp class RangeTest ex
@Test(expected = IllegalArgumentException.class)
public void testIncompatibleTypeRangeContains() {
final Range<Integer> intRange = new Range<>(Integer.class, 0, 10);
- final Range doubleRange = new Range<>(Double.class, 2.0, 5.0);
+ final Range<Double> doubleRange = new Range<>(Double.class, 2.0, 5.0);
intRange.contains(doubleRange);
}
@@ -216,7 +216,7 @@ public final strictfp class RangeTest ex
@Test(expected = IllegalArgumentException.class)
public void testIncompatibleTypeContains() {
final Range<Integer> intRange = new Range<>(Integer.class, 0, 10);
- final Range doubleRange = new Range<>(Double.class, 2.0, 5.0);
+ final Range<Double> doubleRange = new Range<>(Double.class, 2.0, 5.0);
intRange.contains(doubleRange);
}
@@ -242,7 +242,7 @@ public final strictfp class RangeTest ex
@Test(expected = IllegalArgumentException.class)
public void testIntersectsIncompatibleTypes() {
final Range<Character> range1 = new Range<>(Character.class, 'a', 'g');
- final Range range2 = new Range<>(Integer.class, 5, 7);
+ final Range<Integer> range2 = new Range<>(Integer.class, 5, 7);
range1.intersects(range2);
}
@@ -255,7 +255,7 @@ public final strictfp class RangeTest ex
final Range<Integer> range1 = new Range<>(Integer.class, 1, 5);
final Range<Integer> range2 = new Range<>(Integer.class, 4, 6);
- final Range<Integer> intersection = range1.intersect(range2);
+ final Range<?> intersection = range1.intersect(range2);
assertEquals(Integer.class, intersection.getElementType());
assertEquals(Integer.valueOf(4), intersection.getMinValue());
assertEquals(Integer.valueOf(5), intersection.getMaxValue());
@@ -269,7 +269,7 @@ public final strictfp class RangeTest ex
final Range<Integer> range1 = new Range<>(Integer.class, 1, 5);
final Range<Integer> range2 = new Range<>(Integer.class, 8, 10);
- final Range<Integer> intersection = range1.intersect(range2);
+ final Range<?> intersection = range1.intersect(range2);
assertEquals(Integer.class, intersection.getElementType());
assertTrue(intersection.isEmpty());
}
