Problem Set 2: Multi-Startup Set

Problems 1-3: we will implement the interval set abstract type, a mutable set of unique labels where each label is associated with a non-overlapping interval on the number line.

For example, we can picture the interval set { A = [0,5), B = [10,30), C = [30,35) } as:

In this example, the labels are the unique String objects "A", "B", and "C"; and each is associated with an interval, which in our type will be an interval of long values. Every interval is half-open (also called half-closed), meaning that it includes its start point but not its end point, so [0,5) represents { x ∈ ℝ | 0 ≤ x < 5 }.

Read the Javadoc documentation for IntervalSet generated from src/​interval/​IntervalSet.java.

Labels do not have to have String type, but can have any immutable type. IntervalSet<L> is a generic type similar to List<E> or Map<K,V>. In the specification of List, E is a placeholder for the type of elements in the list. In Map, K and V are placeholders for the types of keys and values. Only later does the client of List or Map choose particular types for these placeholders by constructing, for example, a List<Clown> or a Map<Car,Integer>.

The specification of a generic type is written in terms of the placeholders. For example, the specification of Map<K,V> says that K must be an immutable type: if you want to make something the key in a Map, it shouldn’t be a mutable object because the Map may not work correctly.

In our specification for IntervalSet<L>, we make the same demand about the immutability of type L. Clients of IntervalSet who try to use mutable labels have violated the precondition. They cannot expect correct behavior.

For this problem set, we will implement IntervalSet twice, with two different reps, to practice choosing abstraction functions and rep invariants and preventing rep exposure. There are many good reasons for a library to provide multiple implementations of a type (for example, the ArrayList and LinkedList implementations of List satisfy clients with different performance requirements), and we’re following that model.

Problem 4: using interval sets, we will implement the multi-interval set type, a mutable set of labels where each label is associated with one or more globally-non-overlapping intervals.

For example, { A = [[0,5),[20,25)], B = [[10,20),[25,30)], C = [[30,35)] }:

Once again, the labels are "A", "B", and "C". Label "C" is associated with one interval, labels "A" and "B" each with two.

Read the Javadoc documentation for MultiIntervalSet generated from src/​interval/​MultiIntervalSet.java.

Problem 5: with our multi-interval set datatype in hand, the MVP for your new “” startup needs one crucial piece of proprietary technology — a way to measure the similarity between multi-interval sets.

For example, given { A = [[0,5),[20,25)], B = [[10,20),[25,30)] } and { A = [[20,35)], B = [[10,20)], C = [[0,5)] }:

We might consider an interval on the number line completely similar (value 1) when the labels are equal (e.g. on [10,20) and [20,25)) and dissimilar (value 0) otherwise.

Similarity will be defined as a ratio of the extent spanned by the two multi-interval sets, so the similarity between these two sets with the binary definition of label similarity is:

( 5×0 + 5×0 + 10×1 + 5×1 + 5×0 + 5×0 ) ÷ ( 35 - 0 ) = 15 / 35 ≈ 0.42857

(Hover or tap on individual terms to highlight that part of the figure above.)

However, our similarity function will support a client-supplied definition of label similarity, so for example the user might specify that "A" and "C" have similarity 0 but "A" and "B" are closer, similarity ½. Using that definition:

( 5×0 + 5×0 + 10×1 + 5×1 + 5×0.5 + 5×0 ) ÷ ( 35 - 0 ) = 17.5 / 35 = 0.5

Clients of similarity define label similarity by providing a list of pairs of labels with their numeric similarity between 0 and 1. The similarity between all other pairs of labels is 0.

Read the Javadoc documentation for Similarity generated from src/​startup/​Similarity.java.

---

For RepMapIntervalSet, you must use the rep provided:

private final Map<String, Long> startMap = new HashMap<>();
private final Map<Long, Long> endMap = new HashMap<>();

You may not add fields to the rep or choose not to use one of the fields. You must use the names startMap and endMap, even if they are not the names you would choose. The no-argument constructor must create an empty interval set (you are free to add other constructors that take arguments).

Using the @Override annotation on toString ensures that you are correctly overriding the Object version of that method, not creating a new, different method.

All Java classes inherit Object.toString() with its very underdetermined spec. By using @Override and no Javadoc comment, RepMapIntervalSet keeps that same spec. The choice not to strengthen the spec is deliberate: since toString is intended for human consumption, keeping its spec weak helps prevent other code from depending on its particular format.

Because of this very weak spec, you do not need to test toString.

Run your IntervalSetTest tests on RepMapIntervalSet by right-clicking on RepMapIntervalSetTest.java and selecting Run As → JUnit Test.

Commit to Git. Once you’re happy with your solution to this problem, commit and push!

For RepListIntervalSet, you must use the rep provided:

private final List<String> labelList = new ArrayList<>();
private final List<Long> valueList = new ArrayList<>();

You may not add fields to the rep or choose not to use one of the fields. You must use the names labelList and valueList, even if they are not the names you would choose. The no-argument constructor must create an empty interval set (you are free to add other constructors that take arguments).

As mentioned above, RepMap- and RepListIntervalSet may not share any code.

Run the tests by right-clicking on RepListIntervalSetTest.java and selecting Run As → JUnit Test.

Commit to Git. Once you’re happy with your solution to this problem, commit and push!

---

1. Change the declarations of your concrete classes to read:

   public class RepMapIntervalSet<L> implements IntervalSet<L> { ... }

   and:

   public class RepListIntervalSet<L> implements IntervalSet<L> { ... }

2. Update both of your implementations to support any type of label, using placeholder L instead of String. Roughly speaking, you should be able to find-and-replace all the instances of String in your code with L!

   This refactoring will make RepMapIntervalSet and RepListIntervalSet generic types.

   Any place you previously referred to these types without a generic parameter, you will need to add it. For example, if you called a constructor like new RepMapIntervalSet(), that will need to become new RepMapIntervalSet<String>(). Depending on context, you can use diamond notation <> to avoid writing type parameters twice.

   When you’re done with the conversion, all your instance method tests should pass.

Commit to Git. As always, once you’re happy with your solution to this problem, commit and push!

Because the implementation of IntervalSet does not know or care about the actual type of the labels, and only compares them according to the IntervalSet specification, your test suite with String labels is sufficient…

Except that our choice of String for the test suite could prevent us from finding two Java-String-specific bugs:

1. If the implementation incorrectly compares labels using == instead of equals, identical String literals are very likely to return true when compared with ==, masking the bug. See the Optimization hides a bug exercise in Basic Java: == vs. equals().
2. If the implementation incorrectly compares labels using their toString, it will break for label types where toString can return the same string for unequal instances (toString doesn’t guarantee any uniqueness), but we cannot find this bug by testing String labels.

Review your RepMap- and RepListIntervalSet implementations to see that you:

1. Never compare label objects with ==.
2. Never convert labels to strings with toString, except in the RepMap- or RepListIntervalSet class’ own toString.

Note: you cannot write tests with other types of labels in IntervalSetTest, because those tests must use the emptyInstance() method to get new sets. That method always returns IntervalSet<String>.

Pick one of your IntervalSet implementations for clients to use, and implement IntervalSet.empty(). Unlike ArrayList and LinkedList, where clients who only want a List are forced to break the abstraction barrier by calling a concrete constructor, clients of IntervalSet should not be aware of how we’ve implemented it.

At this point, all of your interval set code (implementations and tests) must have no warnings from the compiler (warnings have a symbol, as opposed to the for errors) and no @SuppressWarnings annotations (which would disable the warning, nice try).

If you cannot figure out how to make your implementations generic while satisfying the Java compiler’s static type checking, please visit lab or office hours, or ask a question on Piazza.

At this point in the problem set, we’ve completed the test-first implementation of IntervalSet.

• RepMap- and RepListIntervalSetTest should have a green bar from JUnit and excellent code coverage from the coverage tool.

• This is a good opportunity for self code review: remove dead code and debugging printlns, DRY up duplication, and so on.

• And of course, commit and push.

---

Devise, document, and implement tests for MultiIntervalSet in Multi­IntervalSetTest.java.

Your tests in MultiIntervalSetTest must be legal clients of the MultiIntervalSet spec. As before, since the spec of toString is very weak, you do not need to test toString.

Implement MultiIntervalSet in MultiIntervalSet.java.

You must use IntervalSet in the rep of MultiIntervalSet. For example, IntervalSet instances might be elements in a list or values in a map. Your MultiIntervalSet should rely only on the specs of IntervalSet, not on the details of a particular IntervalSet implementation, and it should use the static empty() method to obtain interval set instances. The implementation of MultiIntervalSet is otherwise entirely up to you.

Run all the IntervalSet and MultiIntervalSet tests by right-clicking on the interval package in the test folder and selecting Run As → JUnit Test.

---

Devise, document, and implement tests for similarity(..) in SimilarityTest.java.

You are free to add additional methods to the Similarity class, but you may not change the signature of the required method. You are free to strengthen the required specification, but you may not weaken it. Note how this might mean your tests for Similarity are not usable against someone else’s implementation, because you’ve strengthened or added to the spec.

You are even free to make Similarity into an abstract data type, in which case you should decide if it is mutable or immutable, document its rep invariant and abstraction function, specify its operations, and so on. Similarity must still provide the static similiarity(..) method.

Implement similarity(..) in Similarity.java.

Your Similarity code should rely only on the specs of MultiIntervalSet, not on the details of any particular implementation.

The implementation of Similarity is entirely up to you.

Run all the tests in the project by right-clicking on the test folder and selecting Run As → JUnit Test.

---