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.
*/
