Original question: Union of intervals
In the original code, the Interval
model class implements Comparable
so that an input of List<Interval>
objects can and must be sorted first for the logic to apply. I have decided to stick with the same approach, but applied a stream reduction operation to get our List<Interval>
output. I will also point out any other differences as we go along...
Interval
model class
public final class Interval implements Comparable<Interval> {
public final int lowerInclusive;
public final int upperInclusive;
private final int hashCode;
private Interval(int first, int second) {
lowerInclusive = Math.min(first, second);
upperInclusive = Math.max(first, second);
hashCode = Arrays.hashCode(new int[]{ lowerInclusive, upperInclusive});
}
public boolean startsOneAfter(int index) {
return lowerInclusive > index + 1;
}
public boolean endsAfter(int index) {
return upperInclusive > index;
}
/**
* The natural ordering between two {@link Interval} objects ({@code this} and
* {@code other}) are as follows:
* <ul>
* <li>If {@code this} starts lower than {@code other}, {@code this} is lesser.</li>
* <li>If {@code this} starts higher than {@code other}, {@code this} is greater.</li>
* <li>If {@code this} starts the same as {@code other}:</li>
* <ul>
* <li>If {@code this} ends lower than {@code other}, {@code this} is lesster.</li>
* <li>If {@code this} ends higher than {@code other}, {@code this} is greater.</li>
* </ul>
* <li>{@code 0} is returned only if {@code this.equals(other) == true}.</li>
* </ul>
*
* @param other the other {@link Interval} to compare
* @return a negative integer, zero, or a positive integer as {@code this} is
* less than, equal to, or greater than the {@code other}
*/
@Override
public int compareTo(Interval other) {
Objects.requireNonNull(other);
int result = Integer.compare(lowerInclusive, other.lowerInclusive);
return result == 0 ?
Integer.compare(upperInclusive, other.upperInclusive) : result;
}
@Override
public boolean equals(Object o) {
return o instanceof Interval
&& lowerInclusive == ((Interval) o).lowerInclusive
&& upperInclusive == ((Interval) o).upperInclusive;
}
@Override
public int hashCode() {
return hashCode;
}
@Override
public String toString() {
return "[" + lowerInclusive + "," + upperInclusive + "]";
}
public static Interval of(int first, int second) {
return new Interval(first, second);
}
}
- Constructor is flexible enough to take in two
int
values in any order. - Yes,
lowerInclusive
andupperInclusive
are public fields, since my class is already immutable, the fields are immutable and therefore I think I should be able to do away with public getter methods this way. Correct me if I'm wrong. :) - Implemented
equals()
andhashCode()
for good measure. startsOneAfter()
andendsAfter()
are helper methods to facilitate the logic inIntervalCollector
below.- The implementation of
compareTo()
is more robust now, as it considers the upper bound as well. See its Javadoc for more details.
IntervalCollector
Collector
implementation for reduction
/**
* A {@link Collector} for union-ing {@link Interval} objects.
*
*/
public class IntervalCollector implements
Collector<Interval, IntervalCollector, List<Interval>> {
private boolean init = false;
private final List<Interval> result = new ArrayList<>();
private int lowerInclusive = Integer.MIN_VALUE;
private int upperInclusive = Integer.MIN_VALUE;
private IntervalCollector add() {
result.add(Interval.of(lowerInclusive, upperInclusive));
return this;
}
private void copy(final Interval interval) {
lowerInclusive = interval.lowerInclusive;
extend(interval);
}
private void extend(final Interval interval) {
upperInclusive = interval.upperInclusive;
}
@Override
public BiConsumer<IntervalCollector, Interval> accumulator() {
return (collector, interval) -> {
if (!init) {
collector.copy(interval);
init = true;
} else if (interval.startsOneAfter(collector.upperInclusive)) {
collector.add().copy(interval);
} else if (interval.endsAfter(collector.upperInclusive)) {
collector.extend(interval);
}
};
}
@Override
public Set<Characteristics> characteristics() {
return EnumSet.noneOf(Characteristics.class);
}
@Override
public BinaryOperator<IntervalCollector> combiner() {
return null;
}
@Override
public Function<IntervalCollector, List<Interval>> finisher() {
return collector -> {
return Collections.unmodifiableList(collector.add().result); };
}
@Override
public Supplier<IntervalCollector> supplier() {
return IntervalCollector::new;
}
}
add()
,copy()
andextend()
are helper methods to manage the internal state of aIntervalCollector
instance.- The main logic inside
accumulator
is quite straight-forward, I'll put it in point form anyways:- If this is the first
Interval
object, we set ourlowerInclusive
andupperInclusive
. - Otherwise, if this
interval
starts one greater than our current upper bound, we know we can perform anadd()
first, before 'restarting' with the currentinterval
for the next element. - Else, if
interval
ends after our current upper bound, we canextend()
our current upper bound.
- If this is the first
- The output of this
Collector
is an unmodifiableList
.
IntervalUnion
main utility class
public final class IntervalUnion {
private IntervalUnion() {
// empty
}
public static List<Interval> union(Collection<Interval> intervals) {
return intervals.stream().sorted().collect(new IntervalCollector());
}
}
- Hmms... I guess there's nothing much to say here, except the input is now just a
Collection
instead of aList
.
IntervalUnionTest
test class
public class IntervalUnionTest {
enum TestCase {
MIN_VALUE(toIntervals(Integer.MIN_VALUE, Integer.MIN_VALUE),
toIntervals(Integer.MIN_VALUE, Integer.MIN_VALUE)),
MAX_VALUE(toIntervals(Integer.MAX_VALUE, Integer.MAX_VALUE),
toIntervals(Integer.MAX_VALUE, Integer.MAX_VALUE)),
NEGATIVE_INTERVALS(toIntervals(-9, -10, -4, -4, -6, -8, -2, -1),
toIntervals(-10, -6, -4, -4, -2, -1)),
AROUND_ZERO(toIntervals(-3, -2, 1, 0, 2, 3), toIntervals(-3, -2, 0, 3)),
POSITIVE_INTERVALS(toIntervals(1, 2, 2, 5, 4, 7, 11, 9), toIntervals(1, 7, 9, 11)),
PSEUDORANDOM(toIntervals(2, 4, 1, 1, 3, 4, 0, 3, 8, 11, 7, 8,
5, 7, 9, 11, 13, 13, 16, 17, 12, 15, 12, 14),
toIntervals(0, 17));
/**
* Helper method to group pairs of arguments into {@link Interval} objects.
*
* @param values the values to convert to {@link Interval} objects
* @return a {@link List} of {@link Interval} objects
* @throws IllegalArgumentException if {@code values} is null or not in pairs
*/
private static List<Interval> toIntervals(int... values) {
if (values == null || values.length % 2 != 0) {
throw new IllegalArgumentException("Values must not be null and in pairs.");
}
List<Interval> result = new ArrayList<>();
for (int i = 0; i < values.length - 1; i++) {
result.add(Interval.of(values[i], values[++i]));
}
return result;
}
private final Collection<Interval> input;
private final List<Interval> expected;
private TestCase(final Collection<Interval> input, final List<Interval> expected) {
this.input = input;
this.expected = expected;
}
public List<Interval> doTest() {
final List<Interval> result = IntervalUnion.union(input);
assertThat(result, equalTo(expected));
return result;
}
}
@DataProvider(name = "test-cases")
public Iterator<Object[]> getTestCases() {
return Arrays.stream(TestCase.values()).map(v -> { return new Object[]{ v }; }).iterator();
}
@Test(dataProvider = "test-cases")
public void test(final TestCase testCase) {
testCase.doTest().forEach(System.out::println);
System.out.println("-----");
}
}
toIntervals()
is a helper method to make it slightly easier to createInterval
objects from pairs ofint
values.- Testing is done via TestNG and its parameterized testing approach using a
@DataProvider
.- Test cases are represented (encapsulated?) as
enum
s and anIterator
is created from mapping eachenum
value inside aObject[]
wrapper to 'feed' our test method.
- Test cases are represented (encapsulated?) as