Onion Run Festival (or the unexpected anagram for Union of Intervals)

Question

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 and upperInclusive 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() and hashCode() for good measure.
• startsOneAfter() and endsAfter() are helper methods to facilitate the logic in IntervalCollector 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() and extend() are helper methods to manage the internal state of a IntervalCollector 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 our lowerInclusive and upperInclusive.
  • Otherwise, if this interval starts one greater than our current upper bound, we know we can perform an add() first, before 'restarting' with the current interval for the next element.
  • Else, if interval ends after our current upper bound, we can extend() our current upper bound.
• The output of this Collector is an unmodifiable List.

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 a List.

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 create Interval objects from pairs of int values.
• Testing is done via TestNG and its parameterized testing approach using a @DataProvider.
  • Test cases are represented (encapsulated?) as enums and an Iterator is created from mapping each enum value inside a Object[] wrapper to 'feed' our test method.

Answer 1

Interval

Your interval class is neat, well, structured in general. The hashCode/equals/compareTo contracts all look accurate. I like the Java-8-like use of the of(...) factory method.

The compareTo method is fine, but, I wonder whether it is better to express that as a Comparator call. Java8 has some nice comparator extensions, you should use them... oh, that's a problem.

You don't have getters/setters for your lower/upper Intervals. You should have those (and the values should be private):

public int getLowerInclusive() {
    return lowerInclusive;
}

public int getUpperInclusive() {
    return upperInclusive;
}

Now, with those methods, you can have a comparator:

private static final Comparator<Interval> NATURAL = Comparator
        .comparingInt(Interval::getLowerInclusive)
        .thenComparingInt(Interval::getUpperInclusive);

And, with that comparator, you can make your compareTo() method:

@Override
public int compareTo(Interval other) {
    return NATURAL.compare(this, other);
}

While we are still in this class, I found the following method to have a really misleading name:

public boolean startsOneAfter(int index) {
    return lowerInclusive > index + 1;
}

That should not even exist on the class. It is something that should be calculated outside the class, and even then, should be called nonExtending or something. I'll come back to this...

IntervalCollector

This class is where I feel your largest problems are. They are implementation, and usability problems. It boils down to two things, with two consequences:

1. you assume sorted data
2. you have no combiner

This means that:

1. you cannot start processing the first data until all the data is sorted, you have a latency problem.
2. you cannot process data in parallel, you have a scalability problem.

Almost all the value of the streams API is in those two features, and you've denied yourself access to them.

Fixing this is a problem, more of a problem than is easy in a review, but, the bottom line is that your Collector needs to be smarter.

A good start to fixing it would be to implement the combiner() method, which would lead you down the path required to support a merging accumulator too. I have some ideas of how I would do it, but it's more than is reasonable for this answer ;-)

Here's a way I would do it:

Interval

import java.util.Arrays;
import java.util.Comparator;

public final class Interval implements Comparable<Interval> {

    private static final Comparator<Interval> NATURAL = Comparator
            .comparingInt(Interval::getLowerInclusive).thenComparingInt(
                    Interval::getUpperInclusive);

    private final int lowerInclusive;
    private 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;
    }

    public int getLowerInclusive() {
        return lowerInclusive;
    }

    public int getUpperInclusive() {
        return upperInclusive;
    }

    @Override
    public int compareTo(Interval other) {
        return NATURAL.compare(this, other);
    }

    @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);
    }
}

IntervalCollector

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Set;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;

public class IntervalCollector implements
        Collector<Interval, IntervalCollector, List<Interval>> {

    private final List<Interval> members = new LinkedList<>();

    private void include(final Interval merge) {

        final ListIterator<Interval> it = members.listIterator();

        final int lowLimit = merge.getLowerInclusive() - 1;
        final int highLimit = merge.getUpperInclusive() + 1;

        while (it.hasNext()) {
            final Interval left = it.next();
            if (lowLimit <= left.getUpperInclusive()) {
                if (highLimit <= left.getLowerInclusive()) {
                    // non overlapping, insert before.
                    it.previous();
                    it.add(merge);
                    return;
                }
                if (left.getLowerInclusive() <= merge.getLowerInclusive()
                        && merge.getUpperInclusive() <= left
                                .getUpperInclusive()) {
                    // we are a complete subset of the item that is there.
                    return;
                }
                // overlapping....
                final int nlow = Math.min(merge.getLowerInclusive(),
                        left.getLowerInclusive());
                int max = Math.max(merge.getUpperInclusive(),
                        left.getUpperInclusive());
                it.remove();
                while (it.hasNext()) {
                    Interval t = it.next();
                    if (highLimit < t.getLowerInclusive()) {
                        // then t is beyond our span....
                        it.previous();
                        break;
                    }
                    // t is within our span.
                    it.remove();
                    max = Math.max(max, t.getUpperInclusive());
                }
                it.add(Interval.of(nlow, max));
                return;
            }
        }
        // nothing matched, we are at the end.
        it.add(merge);

    }

    private IntervalCollector merge(IntervalCollector with) {
        with.members.forEach(i -> include(i));
        return this;
    }

    @Override
    public Supplier<IntervalCollector> supplier() {
        return IntervalCollector::new;
    }

    @Override
    public BiConsumer<IntervalCollector, Interval> accumulator() {
        return (collector, interval) -> collector.include(interval);
    }

    @Override
    public BinaryOperator<IntervalCollector> combiner() {
        return (a, b) -> a.merge(b);
    }

    @Override
    public Function<IntervalCollector, List<Interval>> finisher() {
        return ic -> new ArrayList<>(ic.members);
    }

    @Override
    public Set<java.util.stream.Collector.Characteristics> characteristics() {
        return Collections.singleton(Characteristics.UNORDERED);
    }

}

IntervalMain

This is where I think the flawed Collector logic is most obvious... your code is:

public static List<Interval> union(Collection<Interval> intervals) {
    return intervals.stream().sorted().collect(new IntervalCollector());
}

But, if the sorted() is removed, your code will fail.

If parallel() is added, your code will fail.

Requiring that the user adds stages to their stream is an invitation for problems in the future...