sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From desruisse...@apache.org
Subject svn commit: r1448840 - in /sis/branches/JDK7/sis-utility/src: main/java/org/apache/sis/util/collection/RangeSet.java test/java/org/apache/sis/util/collection/RangeSetTest.java
Date Thu, 21 Feb 2013 22:40:26 GMT
Author: desruisseaux
Date: Thu Feb 21 22:40:26 2013
New Revision: 1448840

URL: http://svn.apache.org/r1448840
Log:
Change the RangeSet.contains(Object) contract in a way more consistent with remove(Object).

Modified:
    sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java
    sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java

Modified: sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java?rev=1448840&r1=1448839&r2=1448840&view=diff
==============================================================================
--- sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java
(original)
+++ sis/branches/JDK7/sis-utility/src/main/java/org/apache/sis/util/collection/RangeSet.java
Thu Feb 21 22:40:26 2013
@@ -634,11 +634,19 @@ public class RangeSet<E extends Comparab
     }
 
     /**
-     * Returns {@code true} if this set contains the specified element.
-     * This method searches for an exact match, i.e. this method doesn't
-     * check if the given range is contained in a larger range.
+     * Returns {@code true} if the given object is an instance of {@link Range} compatible
+     * with this set and contained inside one of the range elements of this set.
+     * If this method returns {@code true}, then:
+     *
+     * <ul>
+     *   <li>Invoking {@link #add(Range)} is guaranteed to have no effect.</li>
+     *   <li>Invoking {@link #remove(Object)} is guaranteed to modify this set.</li>
+     * </ul>
      *
-     * @param object The object to compare to this set.
+     * However if this method returns {@code false}, then no conclusion can be made about
+     * the {@code add(…)} and {@code remove(…)} behavior.
+     *
+     * @param  object The object to check for inclusion in this set.
      * @return {@code true} if the given object is contained in this set.
      */
     @Override
@@ -647,14 +655,70 @@ public class RangeSet<E extends Comparab
             @SuppressWarnings("unchecked") // We are going to check just the line after.
             final Range<E> range = (Range<E>) object;
             if (range.getElementType() == elementType) {
-                if (range.isMinIncluded() && !range.isMaxIncluded()) {
-                    final int index = binarySearch(range.getMinValue(), length);
-                    if (index >= 0 && (index & 1) == 0) {
-                        final int c = getValue(index+1).compareTo(range.getMaxValue());
-                        return c == 0;
-                    }
+                return contains(range, false);
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Returns {@code true} if this set contains the specified element.
+     * If the {@code exact} argument is {@code true}, then this method
+     * searches for an exact match (i.e. this method doesn't check if the
+     * given range is contained in a larger range). Otherwise if the
+     * {@code exact} argument is {@code false}, then this method behaves
+     * as documented in the {@link #contains(Object)} method.
+     *
+     * @param  range The range to check for inclusion in this set.
+     * @param  exact {@code true} for searching for an exact match,
+     *         or {@code false} for searching for inclusion in any range.
+     * @return {@code true} if the given object is contained in this set.
+     */
+    public boolean contains(final Range<E> range, final boolean exact) {
+        ArgumentChecks.ensureNonNull("range", range);
+        if (exact) {
+            if (range.isMinIncluded() && !range.isMaxIncluded()) {
+                final int index = binarySearch(range.getMinValue(), length);
+                if (index >= 0 && (index & 1) == 0) {
+                    return getValue(index+1).compareTo(range.getMaxValue()) == 0;
                 }
             }
+        } else if (!range.isEmpty()) {
+            int upper = binarySearch(range.getMaxValue(), length);
+            if (upper < 0) {
+                upper = ~upper;
+                if ((upper & 1) == 0) {
+                    // The upper endpoint of the given range falls between
+                    // two ranges of this set, or is after all ranges.
+                    return false;
+                }
+            } else if ((upper & 1) != 0) {
+                // Upper endpoint of the given range matches exactly
+                // the upper endpoint of a range in this set.
+                if (!isMaxIncluded && range.isMaxIncluded()) {
+                    return false;
+                }
+            }
+            /*
+             * At this point, the upper endpoint has been determined to be included
+             * in a range of this set. Now check the lower endpoint.
+             */
+            int lower = binarySearch(range.getMinValue(), upper + 1);
+            if (lower < 0) {
+                lower = ~lower;
+                if ((lower & 1) == 0) {
+                    // The lower endpoint of the given range falls between
+                    // two ranges of this set.
+                    return false;
+                }
+            } else if ((lower & 1) == 0) {
+                // Lower endpoint of the given range matches exactly
+                // the lower endpoint of a range in this set.
+                if (!isMinIncluded && range.isMinIncluded()) {
+                    return false;
+                }
+            }
+            return (upper - lower) <= 1;
         }
         return false;
     }
@@ -785,7 +849,12 @@ public class RangeSet<E extends Comparab
      *
      * @see RangeSet#intersect(Range)
      */
-    private final class SubSet extends AbstractSet<Range<E>> implements SortedSet<Range<E>>
{
+    private final class SubSet extends AbstractSet<Range<E>> implements SortedSet<Range<E>>,
Serializable {
+        /**
+         * For cross-version compatibility.
+         */
+        private static final long serialVersionUID = 3093791428299754372L;
+
         /**
          * The minimal and maximal values of this subset,
          */

Modified: sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java
URL: http://svn.apache.org/viewvc/sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java?rev=1448840&r1=1448839&r2=1448840&view=diff
==============================================================================
--- sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java
(original)
+++ sis/branches/JDK7/sis-utility/src/test/java/org/apache/sis/util/collection/RangeSetTest.java
Thu Feb 21 22:40:26 2013
@@ -58,6 +58,21 @@ public final strictfp class RangeSetTest
     }
 
     /**
+     * Verifies the value of {@link RangeSet#contains(Range, boolean)}.
+     *
+     * @param ranges  The range set to test.
+     * @param range   The range to check for inclusion.
+     * @param exact   The expected value in exact mode.
+     * @param lenient The expected value in non-exact mode.
+     */
+    private static <E extends Comparable<? super E>> void checkContains(final
RangeSet<E> ranges,
+            final Range<E> range, final boolean exact, final boolean lenient)
+    {
+        assertEquals("RangeSet.contains(…, true)",  exact,  ranges.contains(range, true));
+        assertEquals("RangeSet.contains(…, false)", lenient, ranges.contains(range));
+    }
+
+    /**
      * Tests {@link RangeSet#add(Range)} using integer values.
      */
     @Test
@@ -69,30 +84,33 @@ public final strictfp class RangeSetTest
          */
         assertTrue(ranges.add(10, 22));
         assertEquals(1, ranges.size());
-        assertTrue (ranges.contains(NumberRange.create(10, true, 22, false)));
-        assertFalse(ranges.contains(NumberRange.create(10, true, 20, false)));
+        checkContains(ranges, NumberRange.create(10, true, 22, false), true,  true);
+        checkContains(ranges, NumberRange.create(10, true, 20, false), false, true);
+        checkContains(ranges, NumberRange.create(10, true, 24, false), false, false);
+        checkContains(ranges, NumberRange.create( 8, true, 20, false), false, false);
         /*
          * Add a new element which should be merged with the previous one.
          */
         assertTrue(ranges.add(14, 25));
         assertEquals(1, ranges.size());
-        assertFalse(ranges.contains(NumberRange.create(10, true, 22, false)));
-        assertTrue (ranges.contains(NumberRange.create(10, true, 25, false)));
+        checkContains(ranges, NumberRange.create(10, true, 22, false), false, true);
+        checkContains(ranges, NumberRange.create(10, true, 25, false), true,  true);
+        checkContains(ranges, NumberRange.create(10, true, 25, true ), false, false);
         /*
          * Add a new element which is disjoint with other element.
          */
         assertTrue(ranges.add(-5, 5));
         assertEquals(2, ranges.size());
-        assertTrue(ranges.contains(NumberRange.create(10, true, 25, false)));
-        assertTrue(ranges.contains(NumberRange.create(-5, true,  5, false)));
+        checkContains(ranges, NumberRange.create(10, true, 25, false), true, true);
+        checkContains(ranges, NumberRange.create(-5, true,  5, false), true, true);
         /*
          * Merge the two ranges together.
          */
         assertTrue(ranges.add(NumberRange.create(5, true, 10, false)));
         assertEquals(1, ranges.size());
-        assertFalse(ranges.contains(NumberRange.create(10, true, 25, false)));
-        assertFalse(ranges.contains(NumberRange.create(-5, true,  5, false)));
-        assertTrue (ranges.contains(NumberRange.create(-5, true, 25, false)));
+        checkContains(ranges, NumberRange.create(10, true, 25, false), false, true);
+        checkContains(ranges, NumberRange.create(-5, true,  5, false), false, true);
+        checkContains(ranges, NumberRange.create(-5, true, 25, false), true,  true);
         /*
          * Add more ranges.
          */
@@ -129,7 +147,7 @@ public final strictfp class RangeSetTest
         final Date yesterday = new Date(now.getTime() - day);
         assertTrue(ranges.add(yesterday, now));
         assertEquals(1, ranges.size());
-        assertTrue(ranges.contains(new Range<>(Date.class, yesterday, true, now, false)));
+        checkContains(ranges, new Range<>(Date.class, yesterday, true, now, false),
true, true);
         /*
          * Add a disjoint range.
          */
@@ -155,13 +173,13 @@ public final strictfp class RangeSetTest
         assertTrue(ranges.isEmpty());
         assertTrue(ranges.add("FAA", "FBB"));
         assertEquals(1, ranges.size());
-        assertTrue(ranges.contains(new Range<>(String.class, "FAA", true, "FBB", false)));
+        checkContains(ranges, new Range<>(String.class, "FAA", true, "FBB", false),
true, true);
         /*
          * Merge the singleton range with the given range.
          */
         assertTrue(ranges.add("FAZ", "FCC"));
         assertEquals(1, ranges.size());
-        assertTrue(ranges.contains(new Range<>(String.class, "FAA", true, "FCC", false)));
+        checkContains(ranges, new Range<>(String.class, "FAA", true, "FCC", false),
true, true);
         /*
          * Add a disjoint range.
          */



Mime
View raw message