You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@sis.apache.org by de...@apache.org on 2014/09/25 13:18:24 UTC
svn commit: r1627513 - in /sis/branches/JDK8/core/sis-utility/src:
main/java/org/apache/sis/util/collection/RangeSet.java
test/java/org/apache/sis/util/collection/RangeSetTest.java
Author: desruisseaux
Date: Thu Sep 25 11:18:23 2014
New Revision: 1627513
URL: http://svn.apache.org/r1627513
Log:
Apply Rémi Maréchal's patch for RangetSet.remove(...) implementation.
https://issues.apache.org/jira/browse/SIS-79
Modified:
sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java
sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java
Modified: sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java?rev=1627513&r1=1627512&r2=1627513&view=diff
==============================================================================
--- sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java [UTF-8] (original)
+++ sis/branches/JDK8/core/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java [UTF-8] Thu Sep 25 11:18:23 2014
@@ -101,8 +101,9 @@ import static org.apache.sis.util.Number
* @param <E> The type of range elements.
*
* @author Martin Desruisseaux (Geomatys)
+ * @author Rémi Maréchal (Geomatys)
* @since 0.3 (derived from geotk-2.0)
- * @version 0.3
+ * @version 0.5
* @module
*
* @see Range
@@ -248,7 +249,7 @@ public class RangeSet<E extends Comparab
* The amount of modifications applied on the range {@linkplain #array}.
* Used for checking concurrent modifications.
*/
- private transient int modCount;
+ private transient int modCount;
/**
* Constructs an initially empty set of ranges.
@@ -430,14 +431,14 @@ public class RangeSet<E extends Comparab
*/
final int binarySearch(final E value, final int lower, final int upper) {
switch (elementCode) {
- case DOUBLE: return Arrays.binarySearch((double[]) array, lower, upper, ((Double) value).doubleValue());
- case FLOAT: return Arrays.binarySearch((float []) array, lower, upper, ((Float) value).floatValue ());
- case LONG: return Arrays.binarySearch((long []) array, lower, upper, ((Long) value).longValue ());
- case INTEGER: return Arrays.binarySearch((int []) array, lower, upper, ((Integer) value).intValue ());
- case SHORT: return Arrays.binarySearch((short []) array, lower, upper, ((Short) value).shortValue ());
- case BYTE: return Arrays.binarySearch((byte []) array, lower, upper, ((Byte) value).byteValue ());
- case CHARACTER: return Arrays.binarySearch((char []) array, lower, upper, ((Character) value).charValue ());
- default: return Arrays.binarySearch((Object[]) array, lower, upper, value);
+ case DOUBLE: return Arrays.binarySearch((double[]) array, lower, upper, (Double) value);
+ case FLOAT: return Arrays.binarySearch((float []) array, lower, upper, (Float) value);
+ case LONG: return Arrays.binarySearch((long []) array, lower, upper, (Long) value);
+ case INTEGER: return Arrays.binarySearch((int []) array, lower, upper, (Integer) value);
+ case SHORT: return Arrays.binarySearch((short []) array, lower, upper, (Short) value);
+ case BYTE: return Arrays.binarySearch((byte []) array, lower, upper, (Byte) value);
+ case CHARACTER: return Arrays.binarySearch((char []) array, lower, upper, (Character) value);
+ default: return Arrays.binarySearch((Object[]) array, lower, upper, value);
}
}
@@ -638,7 +639,119 @@ public class RangeSet<E extends Comparab
* @throws IllegalArgumentException if {@code minValue} is greater than {@code maxValue}.
*/
public boolean remove(final E minValue, final E maxValue) throws IllegalArgumentException {
- throw new UnsupportedOperationException("Not yet implemented");
+ ArgumentChecks.ensureNonNull("minValue", minValue);
+ ArgumentChecks.ensureNonNull("maxValue", maxValue);
+ if (length == 0) return false; // Nothing to do if no data.
+ ensureOrdered(minValue, maxValue);
+
+ // Search insertion index.
+ int i0 = binarySearch(minValue, 0, length);
+ int i1 = binarySearch(maxValue, (i0 >= 0) ? i0 : ~i0, length);
+ if (i0 < 0) i0 = ~i0;
+ if (i1 < 0) i1 = ~i1;
+ if ((i0 & 1) == 0) {
+ if ((i1 & 1) == 0) {
+ /*
+ * i0 & i1 are even.
+ * Case where min and max value are outside any existing range.
+ *
+ * index : A0 B0 A1 B1 An Bn A(n+1) B(n+1)
+ * range : ███████ ██████████ ◾◾◾ ██████████ ██████████
+ * |-----------------------------------|
+ * values : minValue (i0) maxValue (i1)
+ *
+ * In this case delete all ranges between minValue and maxValue ([(A1, B1); (An, Bn)]).
+ */
+ removeAt(i0, i1);
+ } else {
+ /*
+ * i0 is pair and i1 is odd.
+ * Case where minValue is outside any existing range and maxValue is inside a specific range.
+ *
+ * index : A0 B0 A1 B1 An Bn A(n+1) B(n+1)
+ * range : ███████ ██████████ ◾◾◾ ██████████ ██████████
+ * |----------------------------|
+ * values : minValue (i0) maxValue (i1)
+ *
+ * In this case :
+ * - delete all ranges between minValue and maxValue ([(A1, B1); (A(n-1), B(n-1))]).
+ * - and replace range (An; Bn) by new range (MaxValue; Bn).
+ *
+ * Result :
+ * index : A0 B0 i1 Bn A(n+1) B(n+1)
+ * range : ███████ █████ ██████████ ◾◾◾
+ */
+ removeAt(i0, i1 & ~1); // i1 - 1
+ Array.set(array, i0, maxValue);
+ }
+ } else {
+ if ((i1 & 1) == 0) {
+ /*
+ * i0 is odd and i1 is pair.
+ * Case where minValue is inside a specific range and maxValue is outside any range.
+ *
+ * index : A0 B0 A1 B1 An Bn A(n+1) B(n+1)
+ * range : ███████ ██████████ ◾◾◾ ██████████ ██████████
+ * |----------------------------|
+ * values : minValue (i0) maxValue (i1)
+ *
+ * In this case :
+ * - delete all ranges between minValue and maxValue ([(A2, B2); (An, Bn)]).
+ * - and replace range (A1; B1) by new range (A1; i0).
+ *
+ * Result :
+ * index : A0 B0 A1 i0 A(n+1) B(n+1)
+ * range : ███████ █████ ██████████ ◾◾◾
+ */
+ removeAt(i0 + 1, i1);
+ Array.set(array, i0, minValue);
+ } else {
+ /*
+ * i0 and i1 are odd.
+ * Case where minValue and maxValue are inside any specific range.
+ *
+ * index : A0 B0 A1 B1 An Bn A(n+1) B(n+1)
+ * range : ███████ ██████████ ◾◾◾ ██████████ ██████████
+ * |-------------------|
+ * values : minValue (i0) maxValue (i1)
+ *
+ * In this case :
+ * - delete all ranges between minValue and maxValue ([(A2, B2); (A(n-1), B(n-1))]).
+ * - and replace range (A1; B1) by new range (A1; i0).
+ *
+ * Result :
+ * index : A0 B0 A1 i0 i1 Bn A(n+1) B(n+1)
+ * range : ███████ █████ ◾◾◾ █████ ██████████
+ *
+ * A particularity case exist if i0 equal i1, which means minValue
+ * and maxValue are inside the same specific range.
+ *
+ * index : A0 B0 A1 B1 An Bn
+ * range : ███████ █████████████████████ ◾◾◾ ██████████
+ * |-------------|
+ * values : minValue (i0) maxValue (i1)
+ * In this case total range number will be increase by one.
+ *
+ * Result :
+ * index : A0 B0 A1 i0 i1 B1 An Bn
+ * range : ███████ █████ █████ ◾◾◾ █████
+ */
+ if (i0 == i1) {
+ // Above-cited special case
+ insertAt(i1 + 1, maxValue, getValue(i1));
+ Array.set(array, i0, minValue);
+ } else {
+ final int di = i1 - i0;
+ assert di >= 2 : di;
+ if (di > 2) {
+ removeAt(i0 + 1, i1 & ~1); // i0 + 1, i1 - 1
+ }
+ Array.set(array, i0, minValue);
+ Array.set(array, i0 + 1, maxValue);
+ }
+ }
+ }
+ return true;
}
/**
@@ -967,7 +1080,7 @@ public class RangeSet<E extends Comparab
@Override
public int size() {
updateBounds();
- return (upper - lower) / 2;
+ return (upper - lower) >> 1;
}
/**
Modified: sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java?rev=1627513&r1=1627512&r2=1627513&view=diff
==============================================================================
--- sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java [UTF-8] (original)
+++ sis/branches/JDK8/core/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java [UTF-8] Thu Sep 25 11:18:23 2014
@@ -28,6 +28,7 @@ import org.apache.sis.measure.Range;
import org.apache.sis.measure.NumberRange;
import org.apache.sis.test.TestCase;
import org.apache.sis.test.DependsOn;
+import org.apache.sis.test.DependsOnMethod;
import org.apache.sis.test.Performance;
import org.apache.sis.test.TestUtilities;
import org.junit.Test;
@@ -39,13 +40,21 @@ import static org.apache.sis.test.Assert
* Tests the {@link RangeSet} implementation.
*
* @author Martin Desruisseaux (Geomatys)
+ * @author Rémi Maréchal (Geomatys)
* @since 0.3 (derived from geotk-2.0)
- * @version 0.3
+ * @version 0.5
* @module
*/
@DependsOn(org.apache.sis.measure.RangeTest.class)
public final strictfp class RangeSetTest extends TestCase {
/**
+ * Tolerance factor for comparison of floating point numbers.
+ * Actually we expect exact matches, because {@link RangeSet} does not perform any calculation
+ * other than {@code min} and {@code max} - it just stores the values.
+ */
+ private static final double EPS = 0;
+
+ /**
* Asserts that the two given values are equals to the expected one.
* This method is used for testing {@link RangeSet#first()} and {@link RangeSet#last()}
* in same time than the values from the iterator.
@@ -292,6 +301,216 @@ public final strictfp class RangeSetTest
}
/**
+ * Tests the {@link RangeSet#remove(Comparable, Comparable)} method with integer values.
+ * The test is run for 4 different cases, 3 of them resulting in one range and one case
+ * resulting in 2 ranges.
+ *
+ * @since 0.5
+ */
+ @Test
+ @DependsOnMethod("testRangeOfIntegers")
+ public void testRemoveRangeOfIntegers() {
+ final RangeSet<Integer> ranges = RangeSet.create(Integer.class, true, false);
+ assertFalse("Remove on empty collection should return false.", ranges.remove(Integer.MIN_VALUE, Integer.MAX_VALUE));
+ assertTrue(ranges.add(-20, -10));
+ /*
+ * A B
+ * Range : [-------------]
+ * Remove : |------------|
+ * RA RB
+ * Expected result : [------|
+ * A RA
+ */
+ assertTrue(ranges.remove(-15, -5));
+ assertEquals("size", 1, ranges.size());
+ Range<Integer> r = ranges.first();
+ assertEquals(-20, (int) r.getMinValue());
+ assertEquals(-15, (int) r.getMaxValue());
+ /*
+ * A B
+ * Range : [-------------]
+ * Remove : |------------|
+ * RA RB
+ * Expected result : |-------]
+ * RB B
+ */
+ assertTrue(ranges.add(-20, -10));
+ assertEquals("size", 1, ranges.size());
+ assertTrue(ranges.remove(-25, -15));
+ assertEquals("size", 1, ranges.size());
+ r = ranges.first();
+ assertEquals(-15, (int) r.getMinValue());
+ assertEquals(-10, (int) r.getMaxValue());
+ /*
+ * A B
+ * Range : [-----------------------]
+ * Remove : |----------|
+ * RA RB
+ * Expected result : [------| |-----]
+ * A RA RB B
+ */
+ assertTrue(ranges.add(-20, -10));
+ assertEquals("size", 1, ranges.size());
+ assertTrue(ranges.remove(-17, -13));
+ assertEquals("size", 2, ranges.size());
+ r = ranges.getRange(0);
+ assertEquals(-20, (int) r.getMinValue());
+ assertEquals(-17, (int) r.getMaxValue());
+ r = ranges.getRange(1);
+ assertEquals(-17, (int) r.getMinValue());
+ assertEquals(-13, (int) r.getMaxValue());
+ r = ranges.getRange(2);
+ assertEquals(-13, (int) r.getMinValue());
+ assertEquals(-10, (int) r.getMaxValue());
+ /*
+ * A B
+ * Range : [----------------]
+ * Remove : |----------------------|
+ * RA RB
+ * Expected result : "empty"
+ */
+ assertTrue(ranges.add(-20, -10));
+ assertEquals("size", 1, ranges.size());
+ assertTrue(ranges.remove(-21, -9));
+ assertTrue(ranges.isEmpty());
+ }
+
+ /**
+ * Tests the {@link RangeSet#remove(Comparable, Comparable)} method with double values.
+ * This test uses more ranges than {@link #testRemoveRangeOfIntegers()} did.
+ *
+ * @since 0.5
+ */
+ @Test
+ @DependsOnMethod("testRemoveRangeOfIntegers")
+ public void testRemoveRangeOfDoubles() {
+ /*
+ * A0 B0 Ai Bi An Bn
+ * Range : [----] ... [-------] ... [-----]
+ * Remove : |---------------|
+ * RA RB
+ *
+ * Expected result : |-----] ... [-----]
+ * RB Bi An Bn
+ */
+ final RangeSet<Double> ranges = RangeSet.create(Double.class, true, false);
+ assertTrue(ranges.add(-20.2, -10.1));
+ assertTrue(ranges.add( -9.5, -7.9));
+ assertTrue(ranges.add( -6.7, -3.3));
+ assertTrue(ranges.add( -2.4, 1.1));
+ assertTrue(ranges.add( 1.9, 4.3));
+ assertTrue(ranges.add( 6.1, 12.7));
+ assertTrue(ranges.add( 15.3, 21.71));
+ assertEquals("size", 7, ranges.size());
+ assertTrue(ranges.remove(-21.0, -1.4));
+ assertEquals("size", 4, ranges.size());
+ Range<Double> r = ranges.first();
+ assertEquals(-1.4, r.getMinValue(), EPS);
+ assertEquals( 1.1, r.getMaxValue(), EPS);
+ r = ranges.last();
+ assertEquals(15.3, r.getMinValue(), EPS);
+ assertEquals(21.71, r.getMaxValue(), EPS);
+ /*
+ * A0 B0 Ai Bi An Bn
+ * Range : [----] ... [-------] ... [-----]
+ * Remove : |------------------|
+ * RA RB
+ *
+ * Expected result : [-----] ... [---|
+ * A0 B0 Ai RA
+ */
+ assertTrue(ranges.add(-20.2, -10.1));
+ assertTrue(ranges.add( -9.5, -7.9));
+ assertTrue(ranges.add( -6.7, -3.3));
+ assertTrue(ranges.add( -2.4, 1.1 ));
+ assertEquals("size", 7, ranges.size());
+ assertTrue(ranges.remove(0.7, 22.3));
+ assertEquals("size", 4, ranges.size());
+ r = ranges.first();
+ assertEquals(-20.2, r.getMinValue(), EPS);
+ assertEquals(-10.1, r.getMaxValue(), EPS);
+ r = ranges.last();
+ assertEquals(-2.4, r.getMinValue(), EPS);
+ assertEquals( 0.7, r.getMaxValue(), EPS);
+ /*
+ * A0 B0 Ai Bi An Bn
+ * Range : [----] ... [-----------] ... [-----]
+ * Remove : |---|
+ * RA RB
+ *
+ * Expected result : [----] ... [---| |---] ... [-----]
+ * A0 B0 Ai RA RB Bi An Bn
+ */
+ assertTrue(ranges.add(-2.4, 1.1));
+ assertTrue(ranges.add( 1.9, 4.3));
+ assertTrue(ranges.add( 6.1, 12.7));
+ assertTrue(ranges.add(15.3, 21.71));
+ assertEquals("size", 7, ranges.size());
+ assertTrue(ranges.remove(-5.4, -3.9));
+ assertEquals("size", 8, ranges.size());
+ r = ranges.getRange(4);
+ assertEquals(-6.7, r.getMinValue(), EPS);
+ assertEquals(-5.4, r.getMaxValue(), EPS);
+ r = ranges.getRange(6);
+ assertEquals(-3.9, r.getMinValue(), EPS);
+ assertEquals(-3.3, r.getMaxValue(), EPS);
+ /*
+ * A0 B0 Ai Bi Aj Bj Ak Bk An Bn
+ * Range : [----] ... [-----] ...[-----] ... [------] ... [-----]
+ * Remove : |---------------------|
+ * RA RB
+ *
+ * Expected result : [----] ... [-- | |-- ] ... [-----]
+ * A0 B0 Ai RA RB Bk An Bn
+ */
+ assertTrue(ranges.add(-6.7, -3.3));
+ assertEquals("size", 7, ranges.size());
+ assertTrue(ranges.remove(-5.4, 3.1));
+ assertEquals("size", 6, ranges.size());
+ r = ranges.getRange(4);
+ assertEquals(-6.7, r.getMinValue(), EPS);
+ assertEquals(-5.4, r.getMaxValue(), EPS);
+ r = ranges.getRange(6);
+ assertEquals(3.1, r.getMinValue(), EPS);
+ assertEquals(4.3, r.getMaxValue(), EPS);
+ /*
+ * A0 B0 Ai Bi Ai+1 Bi+1 Ak Bk Ak+1 Bk+1 An Bn
+ * Range : [----] ...[-----] [-----] ... [------] [-----] ... [-----]
+ * Remove : |---------------------|
+ * RA RB
+ *
+ * Expected result : [----] ... [----] [-----] ... [-----]
+ * A0 B0 Ai Bi Ak+1 Bk+1 An Bn
+ */
+ assertTrue(ranges.add(-6.7, -3.3));
+ assertTrue(ranges.add(-2.4, 1.1));
+ assertTrue(ranges.add( 1.9, 4.3));
+ assertEquals("size", 7, ranges.size());
+ assertTrue(ranges.remove(-7.1, 5.2));
+ assertEquals("size", 4, ranges.size());
+ r = ranges.getRange(2);
+ assertEquals(-9.5, r.getMinValue(), EPS);
+ assertEquals(-7.9, r.getMaxValue(), EPS);
+ r = ranges.getRange(4);
+ assertEquals( 6.1, r.getMinValue(), EPS);
+ assertEquals(12.7, r.getMaxValue(), EPS);
+ /*
+ * A0 B0 An Bn
+ * Range : [----] ... [-----]
+ * Remove : |---------------------|
+ * RA RB
+ *
+ * Expected result : "Empty"
+ */
+ assertTrue(ranges.add(-6.7, -3.3));
+ assertTrue(ranges.add(-2.4, 1.1));
+ assertTrue(ranges.add( 1.9, 4.3));
+ assertEquals("size", 7, ranges.size());
+ assertTrue(ranges.remove(-50.5, 45.3));
+ assertTrue(ranges.isEmpty());
+ }
+
+ /**
* Tests {@link RangeSet#clone()}.
*/
@Test