Problem Set 2: Multi-Startup Set

In 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 strings "A", "B", and "C"; and each is associated with an interval, which in our type will be an interval of bigint 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 TypeDoc documentation for IntervalSet generated from src/intervalset.ts.

Our interval sets will support labels of any type. IntervalSet<Label> is a generic type similar to Array<E> or Map<K,V>. In the specification of Array, 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 Array or Map choose particular types for these placeholders by constructing, for example, a Array<Clown> or a Map<Car,number>.

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, and we’re following that model.

The implementations will be in src/intervalset-impls.ts.

In 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 TypeDoc documentation for MultiIntervalSet generated from src/multiintervalset.ts.

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. That is problem 5.

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

Our similarity function will support a client-supplied definition of label similarity. For example, let’s suppose a binary definition: labels are completely similar (value 1) when they are equal, and completely dissimilar (value 0) otherwise.

The interval similarity of an interval spanned by both sets is the similarity of their labels. Those spanned by only one set, or by neither set, have interval similarity 0.

The similarity between multi-interval sets will be defined as a ratio of the extent spanned by the two 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, suppose the client instead specifies 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 either 1 (if they are equal) or 0 (otherwise).

Read the TypeDoc documentation for similarity generated from src/similarity.ts.

---

const i1 = new Interval(0n, 1n);
const i2 = new Interval(0n, 1n);

const map: Map<string, Array<string>> = new Map([ ["A", []] ]);

if (map.has("B")) { console.log(map.get("B").length); }

For RepMapIntervalSet, you must use the rep provided:

private readonly startMap: Map<string, bigint> = new Map();
private readonly endMap: Map<bigint, bigint> = new Map();

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 constructor must create an empty interval set.

All TypeScript classes inherit Object.toString() with its very underdetermined spec. If your toString() documentation comment simply refers to that spec with @inheritDoc, RepMapIntervalSet keeps the 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 running npm test -- -f RepMapIntervalSet.

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

Nothing in your implementation should rely on the fact that labels are of type string in particular.

The spec of IntervalSet says that labels may be of arbitrary type, as long as they can be compared for equality using ===. Let’s change our implementation to support labels of any type that meets this condition.

First, change the declaration of RepMapIntervalSet to read:

export class RepMapIntervalSet<Label> implements IntervalSet<Label> { ... }

Then update your implementation to support any type of label, using placeholder Label instead of string. Roughly speaking, you should be able to find-and-replace the instances of string in your code with Label!

This refactoring will make RepMapIntervalSet a generic type.

Any place you previously referred to RepMapIntervalSet without a generic parameter, you may need to add it.

In principle, because your implementations in this problem and in the next do not know or care about the actual type of labels, and will only compare them using === according to the IntervalSet specification, your test suite with string labels should be sufficient.

Nevertheless, there are bugs that a test suite with only string labels cannot find! For example, if the implementation accidentally compares labels after converting them to strings, distinct objects with the same toString() value will appear equal when they should be unequal.

To enable your test suite to create interval sets with other kinds of labels, remove the line at the bottom of src/intervalset-impls.ts with the comment remove this line in Problem 2.3, and replace it with the commented-out line immediately below.

You don’t need to understand the IntervalSetCtor type alias, but please ask if you have questions.

Then improve your test suite to cover labels that don’t behave like built-in strings, which should require adding or modifying only a couple tests.

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

---

For RepArrayIntervalSet, you must use the rep provided:

private readonly labelList: Array<Label> = [];
private readonly valueList: Array<bigint> = [];

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 constructor must create an empty interval set.

Note that JavaScript arrays can be made sparse by omitting elements at some indices. But sparse arrays can have surprising behavior (e.g., map() and forEach() just skip over the missing elements rather than visiting them as undefined values). We use Array<T> to indicate a dense (non-sparse) array of type T. If you choose to use sparse arrays in your rep, you must document that choice clearly.

Run your IntervalSet tests on RepArrayIntervalSet by running npm test -- -f RepArrayIntervalSet.

Run the tests on both implementations by running, for example, npm test -- -f IntervalSet.

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

Finally, pick one of your IntervalSet implementations for clients to use, and write the one-line implementation of makeIntervalSet() in src/intervalset.ts.

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

• Your test suites should be passing and have excellent code coverage from the coverage tool.

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

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

---

Devise, document, and implement tests for MultiIntervalSet in test/multi­intervalset.test.ts.

Your tests in multiintervalset.test.ts 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 src/multiintervalset.ts.

You must use IntervalSet in the rep of MultiIntervalSet. For example, IntervalSet instances might be elements in an array 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 makeIntervalSet() factory function to obtain IntervalSet instances. The implementation of MultiIntervalSet is otherwise entirely up to you.

Run all the IntervalSet and MultiIntervalSet tests by running npm test.

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

---

Devise, document, and implement tests for similarity(..) in test/similarity.test.ts.

You may strengthen the spec of similarity but must not weaken or otherwise change it. Your tests in similarity.test.ts must be legal clients of your spec.

You will implement similarity(..) in src/similarity.ts.

Plan that implementation now, with the following requirement: you must make use of one more ADT, whose design is entirely up to you, that improves the safety from bugs, ease of understanding, and/or readiness for change of your similarity implementation.

Specify your new ADT as a class at the bottom of src/similarity.ts; then test it in test/similarity.test.ts; and implement it.

Your similarity code should rely only on the specs of MultiIntervalSet and the other ADTs, not on the details of any particular implementation.

It should make good use of the new helper ADT you designed, again relying only on its spec and not on its implementation.

The implementation of similarity is otherwise entirely up to you.

Run all your tests by running npm test.

---