sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject 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
Date Thu, 25 Sep 2014 11:18:24 GMT
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



Mime
View raw message