Author: desruisseaux
Date: Thu Feb 21 21:32:50 2013
New Revision: 1448811
URL: http://svn.apache.org/r1448811
Log:
Implemented subset views of RangeSet.
This is new code - those views were not implemented on Geotk.
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=1448811&r1=1448810&r2=1448811&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 21:32:50 2013
@@ -403,7 +403,7 @@ public class RangeSet<E extends Comparab
* @param value The value to search.
* @param n The length of the array to consider.
*/
- private int binarySearch(final E value, final int n) {
+ final int binarySearch(final E value, final int n) {
switch (elementCode) {
case DOUBLE: return Arrays.binarySearch((double[]) array, 0, n,
((Double) value).doubleValue());
case FLOAT: return Arrays.binarySearch((float []) array, 0, n,
((Float) value).floatValue ());
@@ -567,11 +567,11 @@ public class RangeSet<E extends Comparab
* <p>The {@code isMinIncluded} and {@code isMaxIncluded} properties of
the given range
* shall be the complement of the ones given to the constructor of this
{@code RangeSet}:</p>
* <table class="sis">
- * <tr><th>Type of ranges added</th> <th>Type of removable
ranges.</th></tr>
- * <tr><td>{@code [min ⦠max]}</td> <td>{@code (min â¦
max)}</td></tr>
- * <tr><td>{@code (min ⦠max)}</td> <td>{@code [min â¦
max]}</td></tr>
- * <tr><td>{@code [min ⦠max)}</td> <td>{@code (min â¦
max]}</td></tr>
- * <tr><td>{@code (min ⦠max]}</td> <td>{@code [min â¦
max)}</td></tr>
+ * <tr><th>{@code add(â¦)} values</th> <th>{@code remove(â¦)}
values</th></tr>
+ * <tr><td>{@code [min ⦠max]}</td> <td>{@code (min â¦
max)}</td></tr>
+ * <tr><td>{@code (min ⦠max)}</td> <td>{@code [min â¦
max]}</td></tr>
+ * <tr><td>{@code [min ⦠max)}</td> <td>{@code (min â¦
max]}</td></tr>
+ * <tr><td>{@code (min ⦠max]}</td> <td>{@code [min â¦
max)}</td></tr>
* </table>
*
* <p>The default implementation does nothing if the given object is
{@code null}, or is not an
@@ -722,7 +722,7 @@ public class RangeSet<E extends Comparab
if (length == 0) {
throw new NoSuchElementException();
}
- return newRange(get(0), get(1));
+ return getRange(0);
}
/**
@@ -735,44 +735,400 @@ public class RangeSet<E extends Comparab
if (length == 0) {
throw new NoSuchElementException();
}
- return newRange(get(length-2), get(length-1));
+ return getRange(length - 2);
+ }
+
+ /**
+ * Returns a view of the portion of this range set which is the
intersection of
+ * this {@code RangeSet} with the given range. Changes in this {@code
RangeSet}
+ * will be reflected in the returned view, and conversely.
+ *
+ * @param subRange The range to intersect with this {@code RangeSet}.
+ * @return A view of the specified range within this range set.
+ */
+ public SortedSet<Range<E>> intersect(final Range<E> subRange) {
+ ArgumentChecks.ensureNonNull("subRange", subRange);
+ return new SubSet(subRange);
}
/**
* Returns a view of the portion of this sorted set whose elements range
* from {@code lower}, inclusive, to {@code upper}, exclusive.
+ * The default implementation is equivalent to the following pseudo-code
+ * (omitting argument checks):
+ *
+ * {@preformat java
+ * return intersect(new Range<E>(elementType,
+ * lower.minValue, lower.isMinIncluded,
+ * upper.minValue, !upper.isMinIncluded));
+ * }
+ *
+ * {@note This method takes the minimal value of the <code>upper</code>
argument
+ * rater than the maximal value because the upper endpoint is
exclusive.}
*
* @param lower Low endpoint (inclusive) of the sub set.
* @param upper High endpoint (exclusive) of the sub set.
* @return A view of the specified range within this sorted set.
+ *
+ * @see #intersect(Range)
*/
@Override
public SortedSet<Range<E>> subSet(final Range<E> lower, final Range<E>
upper) {
- throw new UnsupportedOperationException("Not yet implemented");
+ ArgumentChecks.ensureNonNull("lower", lower);
+ ArgumentChecks.ensureNonNull("upper", upper);
+ final E maxValue = upper.getMinValue();
+ if (maxValue == null) {
+ throw new IllegalArgumentException(Errors.format(
+ Errors.Keys.IllegalArgumentValue_2, "upper", upper));
+ }
+ return intersect(new Range<>(elementType,
+ lower.getMinValue(), lower.isMinIncluded(),
+ maxValue, !upper.isMinIncluded()));
}
/**
* Returns a view of the portion of this sorted set whose elements are
* strictly less than {@code upper}.
+ * The default implementation is equivalent to the same pseudo-code than
the one
+ * documented in the {@link #subSet(Range, Range)} method, except that the
lower
+ * endpoint is {@code null}.
*
* @param upper High endpoint (exclusive) of the headSet.
* @return A view of the specified initial range of this sorted set.
+ *
+ * @see #intersect(Range)
*/
@Override
public SortedSet<Range<E>> headSet(final Range<E> upper) {
- throw new UnsupportedOperationException("Not yet implemented");
+ ArgumentChecks.ensureNonNull("upper", upper);
+ final E maxValue = upper.getMinValue();
+ if (maxValue == null) {
+ throw new IllegalArgumentException(Errors.format(
+ Errors.Keys.IllegalArgumentValue_2, "upper", upper));
+ }
+ return intersect(new Range<>(elementType, null, false, maxValue,
!upper.isMinIncluded()));
}
/**
* Returns a view of the portion of this sorted set whose elements are
* greater than or equal to {@code lower}.
+ * The default implementation is equivalent to the same pseudo-code than
the one
+ * documented in the {@link #subSet(Range, Range)} method, except that the
upper
+ * endpoint is {@code null}.
*
* @param lower Low endpoint (inclusive) of the tailSet.
* @return A view of the specified final range of this sorted set.
+ *
+ * @see #intersect(Range)
*/
@Override
public SortedSet<Range<E>> tailSet(final Range<E> lower) {
- throw new UnsupportedOperationException("Not yet implemented");
+ ArgumentChecks.ensureNonNull("lower", lower);
+ return intersect(new Range<>(elementType, lower.getMinValue(),
lower.isMinIncluded(), null, false));
+ }
+
+ /**
+ * A view over a subset of {@link RangeSet}.
+ * Instances of this class are created by the {@link
RangeSet#intersect(Range)} method.
+ *
+ * @author Martin Desruisseaux (Geomatys)
+ * @since 0.3
+ * @version 0.3
+ * @module
+ *
+ * @see RangeSet#intersect(Range)
+ */
+ private final class SubSet extends AbstractSet<Range<E>> implements
SortedSet<Range<E>> {
+ /**
+ * The minimal and maximal values of this subset,
+ */
+ private Range<E> subRange;
+
+ /**
+ * Index of {@link #minValue} and {@link #maxValue} in the array of
the enclosing
+ * {@code RangeSet}. Those indices need to be recomputed every time
the enclosing
+ * {@code RangeSet} has been modified.
+ *
+ * @see #updateBounds()
+ */
+ private transient int lower, upper;
+
+ /**
+ * Modification count of the enclosing {@link RangeSet}, used for
detecting changes.
+ */
+ private transient int modCount;
+
+ /**
+ * Creates a new subset of the enclosing {@code RangeSet} between the
given values.
+ *
+ * @param subRange The range to intersect with the enclosing {@code
RangeSet}.
+ */
+ SubSet(final Range<E> subRange) {
+ this.subRange = subRange;
+ if (subRange.isEmpty()) {
+ throw new IllegalArgumentException(Errors.format(
+ Errors.Keys.IllegalArgumentValue_2, "subRange",
subRange));
+ }
+ modCount = RangeSet.this.modCount - 1;
+ }
+
+ /**
+ * Recomputes the {@link #lower} and {@link #upper} indices if they
are outdated.
+ * If the indices are already up to date, then this method does
nothing.
+ */
+ private void updateBounds() {
+ if (modCount != RangeSet.this.modCount) {
+ final E maxValue = subRange.getMaxValue();
+ int upper = length;
+ if (maxValue != null) {
+ upper = binarySearch(maxValue, upper);
+ if (upper < 0) {
+ upper = ~upper;
+ }
+ /*
+ * If 'upper' is even (i.e. is the index of a minimal
value), keep that index
+ * unchanged because this value is exclusive. But if
'upper' is odd (i.e. is
+ * the index of a maximal value), move to the minimal
value of the next range.
+ */
+ upper = (upper + 1) & ~1;
+ }
+ final E minValue = subRange.getMinValue();
+ int lower = 0;
+ if (minValue != null) {
+ lower = binarySearch(minValue, upper);
+ if (lower < 0) {
+ lower = ~lower;
+ }
+ lower &= ~1; // Force the index to even value.
+ }
+ this.lower = lower;
+ this.upper = upper;
+ modCount = RangeSet.this.modCount;
+ }
+ }
+
+ /**
+ * Returns the comparator, which is the same than the enclosing class.
+ */
+ @Override
+ public Comparator<Range<E>> comparator() {
+ return RangeSet.this.comparator();
+ }
+
+ /**
+ * Clears this subset by removing all elements in the range given to
the constructor.
+ */
+ @Override
+ public void clear() {
+ RangeSet.this.remove(subRange);
+ }
+
+ /**
+ * Returns the number of ranges in this subset.
+ */
+ @Override
+ public int size() {
+ updateBounds();
+ return (upper - lower) / 2;
+ }
+
+ /**
+ * Adds a new range in the enclosing {@code RangeSet}, and updates
this subset
+ * in order to contain that range.
+ */
+ @Override
+ public boolean add(final Range<E> range) {
+ final boolean changed = RangeSet.this.add(range);
+ /*
+ * Update the minimal and maximal values if this sub-set has been
expanded as
+ * a result of this method call. Note that we don't need to
remember that the
+ * indices need to be recomputed, because RangeSet.this.modCount
has already
+ * been increased by the enclosing class.
+ */
+ subRange = subRange.union(range);
+ return changed;
+ }
+
+ /**
+ * Removes the given range or part of it from the enclosing {@code
RangeSet}.
+ * Before to perform the removal, this method intersects the given
range with
+ * the range of this subset.
+ */
+ @Override
+ public boolean remove(Object object) {
+ if (object instanceof Range<?>) {
+ @SuppressWarnings("unchecked") // Type will actally be checked
on the line after.
+ final Range<E> range = (Range<E>) object;
+ if (range.getElementType() == elementType) {
+ object = subRange.intersect(range);
+ }
+ }
+ return RangeSet.this.remove(object);
+ }
+
+ /**
+ * Tests if this subset contains the given range. Before to delegates
to the enclosing
+ * class, this method filter-out the ranges that are not contained in
the range given
+ * to the constructor of this subset.
+ */
+ @Override
+ public boolean contains(final Object object) {
+ if (object instanceof Range<?>) {
+ @SuppressWarnings("unchecked") // Type will actally be checked
on the line after.
+ final Range<E> range = (Range<E>) object;
+ if (range.getElementType() == elementType) {
+ if (!subRange.contains(range)) {
+ return false;
+ }
+ }
+ }
+ return RangeSet.this.contains(object);
+ }
+
+ /**
+ * Returns the first range in this subset,
+ * intersected with the range given to the constructor.
+ */
+ @Override
+ public Range<E> first() {
+ updateBounds();
+ if (lower == upper) {
+ throw new NoSuchElementException();
+ }
+ return subRange.intersect(getRange(lower));
+ }
+
+ /**
+ * Returns the last range in this subset,
+ * intersected with the range given to the constructor.
+ */
+ @Override
+ public Range<E> last() {
+ updateBounds();
+ if (lower == upper) {
+ throw new NoSuchElementException();
+ }
+ return subRange.intersect(getRange(upper - 2));
+ }
+
+ /**
+ * Delegates subset creation to the enclosing class.
+ * The new subset will not be bigger than this subset.
+ */
+ @Override
+ public SortedSet<Range<E>> subSet(Range<E> fromElement, Range<E>
toElement) {
+ fromElement = subRange.intersect(fromElement);
+ toElement = subRange.intersect(toElement);
+ return RangeSet.this.subSet(fromElement, toElement);
+ }
+
+ /**
+ * Delegates subset creation to the enclosing class.
+ * The new subset will not be bigger than this subset.
+ */
+ @Override
+ public SortedSet<Range<E>> headSet(Range<E> toElement) {
+ toElement = subRange.intersect(toElement);
+ return RangeSet.this.headSet(toElement);
+ }
+
+ /**
+ * Delegates subset creation to the enclosing class.
+ * The new subset will not be bigger than this subset.
+ */
+ @Override
+ public SortedSet<Range<E>> tailSet(Range<E> fromElement) {
+ fromElement = subRange.intersect(fromElement);
+ return RangeSet.this.tailSet(fromElement);
+ }
+
+ /**
+ * Returns an iterator over the elements in this subset.
+ */
+ @Override
+ public Iterator<Range<E>> iterator() {
+ updateBounds();
+ return new SubIter(subRange, lower, upper);
+ }
+ }
+
+ /**
+ * The iterator returned by {@link SubSet#iterator()}. This iterator is
similar
+ * to the one returned by {@link RangeSet#iterator()}, except that:
+ *
+ * <ul>
+ * <li>The iteration is restricted to a sub-region of the {@link
RangeSet#array}.</li>
+ * <li>The first and last ranges returned by the iterator are
intercepted with
+ * the range of the subset (other ranges should not need to be
intercepted).</li>
+ * <li>The range removed by {@link #remove()} is intercepted with the
range of the
+ * subset.</li>
+ * </ul>
+ *
+ * @author Martin Desruisseaux (Geomatys)
+ * @since 0.3
+ * @version 0.3
+ * @module
+ */
+ private final class SubIter extends Iter {
+ /**
+ * A copy of the {@link SubSet#subRange} field value at the time of
iterator creation.
+ */
+ private final Range<E> subRange;
+
+ /**
+ * Index of the first element in the {@link RangeSet#array} where to
iterate.
+ */
+ private final int lower;
+
+ /**
+ * Creates a new iterator for the given portion of the {@link
RangeSet#array}.
+ */
+ SubIter(final Range<E> subRange, final int lower, final int upper) {
+ super(upper);
+ this.subRange = subRange;
+ this.lower = lower;
+ position = lower;
+ }
+
+ /**
+ * Returns {@code true} if the iterator position is at the first or at
the last range.
+ * This method is accurate only when invoked after {@code
super.next()}.
+ */
+ private boolean isFirstOrLast() {
+ return position <= lower+2 || position >= upper;
+ }
+
+ /**
+ * Returns the next element in the iteration.
+ */
+ @Override
+ public Range<E> next() {
+ Range<E> range = super.next();
+ if (isFirstOrLast()) {
+ range = subRange.intersect(range);
+ }
+ return range;
+ }
+
+ /**
+ * Removes from the underlying collection the last element returned by
the iterator.
+ */
+ @Override
+ public void remove() {
+ if (isFirstOrLast()) {
+ // Default implementation is faster.
+ super.remove();
+ return;
+ }
+ if (!canRemove) {
+ throw new IllegalStateException();
+ }
+ if (RangeSet.this.modCount != this.modCount) {
+ throw new ConcurrentModificationException();
+ }
+ RangeSet.this.remove(subRange.intersect(getRange(position - 2)));
+ canRemove = false;
+ }
}
/**
@@ -781,12 +1137,11 @@ public class RangeSet<E extends Comparab
*/
@Override
public Iterator<Range<E>> iterator() {
- return new Iter();
+ return new Iter(length);
}
-
/**
- * An iterator for iterating through ranges in a {@link RangeSet}.
+ * The iterator returned by {@link RangeSet#iterator()}.
* All elements are {@link Range} objects.
*
* @author Martin Desruisseaux (Geomatys)
@@ -794,28 +1149,41 @@ public class RangeSet<E extends Comparab
* @version 0.3
* @module
*/
- private final class Iter implements Iterator<Range<E>> {
+ private class Iter implements Iterator<Range<E>> {
/**
* Modification count at construction time.
*/
- private int modCount = RangeSet.this.modCount;
+ int modCount;
/**
- * The array length.
+ * Index after the last element in the {@link RangeSet#array} where to
iterate.
*/
- private final int length = RangeSet.this.length;
+ final int upper;
/**
* Current position in {@link RangeSet#array}.
*/
- private int position;
+ int position;
+
+ /**
+ * {@code true} if the {@link #remove()} method can be invoked.
+ */
+ boolean canRemove;
+
+ /**
+ * Creates a new iterator for the given portion of the {@link
RangeSet#array}.
+ */
+ Iter(final int upper) {
+ this.upper = upper;
+ this.modCount = RangeSet.this.modCount;
+ }
/**
* Returns {@code true} if the iteration has more elements.
*/
@Override
- public boolean hasNext() {
- return position < length;
+ public final boolean hasNext() {
+ return position < upper;
}
/**
@@ -823,39 +1191,48 @@ public class RangeSet<E extends Comparab
*/
@Override
public Range<E> next() {
- if (hasNext()) {
- final E lower = get(position++);
- final E upper = get(position++);
- if (RangeSet.this.modCount != modCount) {
- // Check it last, in case a change occurred
- // while we was constructing the element.
- throw new ConcurrentModificationException();
- }
- return newRange(lower, upper);
+ if (!hasNext()) {
+ throw new NoSuchElementException();
}
- throw new NoSuchElementException();
+ final Range<E> range = getRange(position);
+ if (RangeSet.this.modCount != this.modCount) {
+ // Check it last, in case a change occurred
+ // while we were creating the range.
+ throw new ConcurrentModificationException();
+ }
+ position += 2;
+ canRemove = true;
+ return range;
}
/**
- * Removes from the underlying collection the
- * last element returned by the iterator.
+ * Removes from the underlying collection the last element returned by
the iterator.
*/
@Override
public void remove() {
- if (position != 0) {
- if (RangeSet.this.modCount == modCount) {
- removeAt(position-2, position);
- modCount = RangeSet.this.modCount;
- } else {
- throw new ConcurrentModificationException();
- }
- } else {
+ if (!canRemove) {
throw new IllegalStateException();
}
+ if (RangeSet.this.modCount != this.modCount) {
+ throw new ConcurrentModificationException();
+ }
+ removeAt(position-2, position);
+ this.modCount = RangeSet.this.modCount;
+ canRemove = false;
}
}
/**
+ * Returns the range at the given array index. The given index is relative
to
+ * the interval {@link #array}, which is twice the index of range elements.
+ *
+ * @param index The range index, from 0 inclusive to {@link #length}
exclusive.
+ */
+ final Range<E> getRange(final int index) {
+ return newRange(get(index), get(index+1));
+ }
+
+ /**
* Returns a new {@link Range} object initialized with the given values.
*
* @param lower The lower value, inclusive.
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=1448811&r1=1448810&r2=1448811&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 21:32:50 2013
@@ -22,6 +22,7 @@ import java.util.Comparator;
import java.util.Random;
import java.util.Arrays;
import java.util.Collections;
+import java.util.SortedSet;
import java.io.PrintWriter;
import org.apache.sis.measure.Range;
import org.apache.sis.measure.NumberRange;
@@ -217,6 +218,43 @@ public final strictfp class RangeSetTest
}
/**
+ * Tests the {@link RangeSet#intersect(Range)} method. The {@code
subSet(â¦)}, {@code headSet(â¦)}
+ * and {@code tailSet(â¦)} methods delegate their work to that {@code
intersect(â¦)} method.
+ */
+ @Test
+ public void testIntersect() {
+ final RangeSet<Integer> ranges = RangeSet.create(Integer.class, true,
false);
+ assertTrue(ranges.add(-20, -10));
+ assertTrue(ranges.add( -5, 25));
+ assertTrue(ranges.add( 28, 35));
+ assertTrue(ranges.add( 40, 50));
+ assertTrue(ranges.add( 60, 70));
+ final SortedSet<Range<Integer>> subset =
ranges.intersect(NumberRange.create(5, true, 45, false));
+ /*
+ * Verify the content. Note that the first and last ranges
+ * are expected to be intersected with the [5 ⦠45) range.
+ */
+ assertEquals(5, ranges.size());
+ assertEquals(3, subset.size());
+ Iterator<Range<Integer>> it = subset.iterator();
+ assertEqual (NumberRange.create( 5, true, 25, false), it.next(),
subset.first());
+ assertEquals(NumberRange.create(28, true, 35, false), it.next());
+ assertEqual (NumberRange.create(40, true, 45, false), it.next(),
subset.last());
+ assertFalse(it.hasNext());
+ /*
+ * Add a range and verify the content in the sub-set.
+ * Verify also that the enclosing set changed.
+ */
+ assertTrue(subset.add(NumberRange.create(35, true, 48, false)));
+ assertEquals(4, ranges.size());
+ assertEquals(2, subset.size());
+ it = subset.iterator();
+ assertEqual(NumberRange.create( 5, true, 25, false), it.next(),
subset.first());
+ assertEqual(NumberRange.create(28, true, 48, false), it.next(),
subset.last());
+ assertFalse(it.hasNext());
+ }
+
+ /**
* Tests {@link RangeSet#clone()}.
*/
@Test
