Problem Set 2: Cityscape

The deadlines for this problem set are shown on the course calendar.

The purpose of this problem set is to practice designing, testing, and implementing abstract data types. This problem set focuses on implementing mutable types where the specifications are provided to you; the next problem set will focus on immutable types where you must choose specifications.

Design Freedom and Restrictions

On several parts of this problem set, the classes and methods will be yours to specify and create, but you must pay attention to the PS2 instructions sections in the provided documentation.

You must satisfy the specifications of the provided interfaces and classes. You are not permitted to change the specifications at all.

On this problem set, Didit provides less feedback about the correctness of your code:

It is your responsibility to examine Didit feedback and make sure your code compiles and runs properly for grading.
However, correctness is your responsibility alone, and you must rely on your own careful specification, testing, and implementation to achieve it.

Please remember to push early: we cannot guarantee timely Didit builds, especially near the problem set deadline.

Get the code

To get started,

Ask Didit to create a remote psets/ps2 repository for you on github.mit.edu.
Clone the repo. Find the git clone command at the top of your Didit assignment page, copy it entirely, paste it into your terminal, and run it.
Run npm install, then open in Visual Studio Code. See Problem Set 0 for if you need a refresher on how to create, clone, or set up your repository.

Overview

In this problem set, we will develop abstract data types for modeling the floors and buildings of a city.

The primary ADT of this problem set is RegionSet, which represents labeled contiguous regions on a 2D plane. We will use two different reps for this ADT, with a single test suite for testing both reps.

We will then use the RegionSet type to develop a City type that can represent 3D buildings.

Region sets

Problems 1-3: we will implement the region set abstract type, a mutable set of labeled regions on a 2D grid, where each region is contiguous and uniquely labeled.

A diagram of a region set:	And two examples that are not region sets:
4×4 region set with a large 🍎 region, a small 🍌 region, and some unlabeled cells.	A region cannot have disconnected parts.	Regions cannot overlap.

These are illustrative examples, not a spec.

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

Our region sets will support labels of any type. RegionSet<L> 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 RegionSet 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/RegionSetImpl.ts.

Three dimensions

Problem 4: using the 2D region sets, we will implement a City type, a mutable set of uniquely-labeled buildings in 3D space. Each floor of a building is a contiguous region, and buildings do not intersect.

Read the TypeDoc documentation for City generated from src/City.ts, and note that City is also a generic type.

Problem 1: Test `RegionSet<string>`

Devise, document, and implement tests for RegionSet<string>.

For now, we’ll only test (and then implement) region sets with string labels. Later, we’ll implement a generic RegionSet<L> that can handle other kinds of labels too.

Write your testing strategy and your tests in RegionSetTest.ts.

In order to run your tests on multiple implementations of the RegionSet interface:

RegionSetImpl.ts defines a function implementations() that the tests will use to discover your different implementation classes. You should not change this function.
RegionSetTest.ts has an extra bit of code around Mocha’s describe to iterate over your implementations and run the test suite on each of them. You should not change this line.

The tests use the variable SomeRegionSetOfString to refer to the current implementation class being tested, and you must use new SomeRegionSetOfString(..) to get fresh empty sets, of type RegionSet<string>, in your tests. Do not use the makeRegionSet function, and do not try to call the constructor for a specific implementation like RepMapRegionSet. See the provided test for an example.

Your tests in RegionSetTest must be legal clients of the RegionSet spec.

Refer to Abstract Data Types: Testing an abstract data type. When testing instance methods, remember to partition the state of input this.

reading exercises

Partitions

Looking at RegionSet.ts, RegionSetImpl.ts, and Rect.ts, which of the following might you mention in your partitions for the operation add : RegionSet<string> × string × Rect → void?

whether label is a key in this.map

whether label is undefined

whether rect.x1 is less than rect.x2

whether this is the empty set

whether a region with label exists in this

(missing explanation)

Throws

The spec of RegionSet.add(..) includes a postcondition that specifies when an error is thrown. How could we use assert.throws to test this operation?

const rs = new SomeRegionSetOfString(5);
// ... fill the entire grid, no regions left ...

assert.throws(rs.add);

assert.throws(rs.add, "A", new Rect(0, 0, 1, 1));

assert.throws(rs.add("A", new Rect(0, 0, 1, 1)));

assert.throws(() => { rs.add("A", new Rect(0, 0, 1, 1)); });

(missing explanation)

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

Now we’ll implement region sets — twice.

Problem 2: Implement `RepMapRegionSet`

First we’ll implement RepMapRegionSet for string labels. Then we’ll make that implementation generic, for any kind of label. In the next problem, we’ll implement RepArrayRegionSet.

Write your implementations in RegionSetImpl.ts.

For all the classes you write in this problem set:

Document the abstraction function and representation invariant.
And along with the rep invariant, document how the type prevents rep exposure. See Documenting the AF, RI, & SRE.
Implement checkRep and use it to check the rep invariant.
Implement toString with a useful human-readable representation of the abstract value.

All your classes must have clear documented specifications. This means every method will have a TypeDoc comment, except when you inherit a spec from an interface:

When a method is specified in an interface and then implemented by a concrete class — for example, add(..) in RepMapRegionSet is specified in RegionSet — use @inheritDoc to point to the interface spec, to indicate the method has the same spec. Unless the concrete class needs to strengthen the spec, don’t write the spec again (DRY).

Think carefully about your rep invariants and abstraction functions before you start writing code.

Consider how the required ADT operations, as well as checkRep and toString, will work given your choices.
Performance is not our objective: you should avoid exponential growth, but don’t be afraid to write e.g. quadratic code, especially in your first iterations.
Correctness, clarity, and changeability are our objectives, and none are served by pages of spaghetti code. Plan instead.

Helper functions. You can define small private (non-exported) helper functions in any of the files you are allowed to change. Since you cannot import these functions into a test file, you cannot test them, which is why they must be small. If you want to write a helper function or class or interface of any complexity, or export one to use in another file in src/ or test/ or both, then you should place it in utils.ts and write tests for it in utilsTest.ts. Do not export anything new from any other source code file.

As you iterate and discover useful helper functions — for example, Rect does not provide an equality comparison or containment checking — consider extracting those functions to utils.ts.

reading exercises

Looking at RegionSetImpl.ts, what is the input space of RI : R → boolean for RepMapRegionSet?

(missing explanation)

What does an input to AF : R → A for RepMapRegionSet look like?

(missing explanation)

For an input that satisfies the rep invariant, what does the output look like?

(missing explanation)

Region Set

Which describes exactly one abstract region set?

A. a string-labeled 5×5 region set with no labeled regions

B. a string-labeled 5×5 region set with one labeled region

C. a string-labeled 5×5 region set with one labeled region, the unit square at (0, 0)

D. a string-labeled 5×5 region set with one labeled region, the unit square at (0, 0) labeled "A"

E. a string-labeled 5×5 region set with one labeled region, the unit square at (x, y) labeled z

F. a string-labeled 5×5 region set with one labeled region, the unit square at (x, y) labeled z, where x=1, y=2, z="B"

G. a string-labeled 5×5 region set with map mapping: "C" to [ Rect(0,0,3,3) ]

(missing explanation)

Rect

Given:

const r1 = new Rect(0, 0, 1, 1);
const r2 = new Rect(0, 0, 1, 1);

What is the value of: r1 === r2

True

False

(missing explanation)

Should you use r1 == r2 instead?

Yes

(missing explanation)

Should you use assert.deepStrictEqual(r1, r2) instead?

Yes

(missing explanation)

Map

Given:

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

What happens with the line of code below?

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

(missing explanation)

2.1. Implement `RepMapRegionSet<string>`

For RepMapRegionSet, you must use the rep provided:

private readonly map: Map<string, Array<Rect>> = new Map();
public readonly gridSize: number; // declared as a parameter property of the constructor

You may not add fields to the rep or choose not to use one of the fields. You must use the name map, even if it is not the name you would choose. The constructor must create an empty region set, given the dimension of the grid gridSize.

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

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

2.2: Implement generic `RepMapRegionSet<L>`

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

The spec of RegionSet 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 RepMapRegionSet to read:

export class RepMapRegionSet<L> implements RegionSet<L> { ... }

Generic labels and toString()

You cannot call toString() on objects of generic type L.
Instead, given lbl: L…

1. Use concatenation:
const str: string = "" + lbl;

2. Use a template string:
const str: string = `${lbl}`;

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

This refactoring will make RepMapRegionSet a generic type.

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

Your tests will continue to use new SomeRegionSetOfString(..) to obtain RegionSet<string> instances, and you should not change the signature of implementations() at the bottom of RegionSetImpl.ts, which restricts the tests to string.

Because your implementations in this problem and in the next do not know or care about the actual type of the labels, and will only compare them according to the RegionSet specification, your test suite with string labels is sufficient.

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

Problem 3. Implement `RepArrayRegionSet`

3.1 Implement generic `RepArrayRegionSet<L>`

For RepArrayRegionSet, you must use the rep provided:

private readonly array: Array<L | undefined> = [];
public readonly gridSize: number; // declared as a parameter property of the constructor

You may not add fields to the rep or choose not to use one of the fields. You must use the name array, even if it is not the name you would choose. The constructor must create an empty region set, given the dimension of the grid gridSize.

Note that because array has element type L | undefined, you can, if you wish, make the array sparse by omitting some elements entirely. 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). So you might choose instead to use only dense arrays, perhaps by using fill() to initialize the entire array with undefined. Whichever choice you make should be documented appropriately.

Run your RegionSetTest tests on RepArrayRegionSet by running npm test -- -f RepArrayRegionSet.

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

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.

3.2 Wrap up `RegionSet`

Finally, pick one of your RegionSet implementations for clients to use, and write the one-line implementation of makeRegionSet() in RegionSet.ts.

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

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.logs, DRY up duplication, and so on.

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

Problem 4: `City<L>`

Just as we implemented the RegionSet ADT by relying on other ADTs as building blocks, we can use RegionSet as part of the specification and as part of the representation of another ADT.

4.1. Test `City`

Devise, document, and implement tests for City in CityTest.ts.

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

Erratum

Calling toString() on RegionSet instances triggers the lint error “value will evaluate to [object Object] when stringified,” even when you have implemented toString() correctly.

You may ignore errors for this lint rule (@typescript-eslint/no-base-to-string), and you can follow instructions to disable this rule if you want.

4.2. Implement `City`

Implement City in City.ts.

You must use RegionSet in the rep of City. For example, RegionSet instances might be elements in an array or values in a map. Your City should rely only on the specs of RegionSet, not on the details of a particular RegionSet implementation, and it should use the makeRegionSet() factory function to obtain RegionSet instances. The implementation of City is otherwise entirely up to you.

Run all the RegionSet and City tests by running npm test.

Before you’re done

Make sure you have documented specifications, in the form of properly-formatted TypeDoc comments, for all your types and operations.
Make sure you have documented abstraction functions and representation invariants, in the form of a comment near the field declarations, for all your implementations.

With the rep invariant, also say how the type prevents rep exposure.

Make sure all types use checkRep to check the rep invariant and implement toString with a useful human-readable representation of the abstract value.
Make sure you have a thorough, principled test suite for every type.

Submitting

Make sure you commit AND push your work to your repository on github.mit.edu. We will use the state of your repository on github.mit.edu as of 10:00pm on the deadline date. When you git push, the continuous build system attempts to compile your code and run the public tests (which are only a subset of the autograder tests). You can always review your build results at didit.mit.edu/6.102/sp24.

Didit feedback is provided on a best-effort basis:

There is no guarantee that Didit tests will run within any particular timeframe, or at all. If you push code close to the deadline, the large number of submissions will slow the turnaround time before your code is examined.
If you commit and push right before the deadline, it’s okay if the Didit build finishes after the deadline, because the commit-and-push was on time.
Passing some or all of the public tests on Didit is no guarantee that you will pass the full battery of autograding tests — but failing them is almost sure to mean lost points on the problem set.

Grading

Your overall ps2 grade will be computed as approximately:
~40% alpha autograde (including online exercises) + ~10% alpha manual grade + ~35% beta autograde + ~15% beta manual grade

The autograder tests will not change from alpha to beta, but their point values may.

Problem Set 2: Cityscape

Get the code

Overview

Region sets

Three dimensions

Problem 1: Test RegionSet​<string>

reading exercises

Problem 2: Implement RepMapRegionSet

reading exercises

2.1. Implement RepMapRegionSet<string>

2.2: Implement generic RepMapRegionSet<L>

Problem 3. Implement RepArrayRegionSet

3.1 Implement generic RepArrayRegionSet<L>

3.2 Wrap up RegionSet

Problem 4: City<L>

4.1. Test City

4.2. Implement City

Before you’re done

Submitting

Grading

Problem 1: Test `RegionSet<string>`

Problem 2: Implement `RepMapRegionSet`

2.1. Implement `RepMapRegionSet<string>`

2.2: Implement generic `RepMapRegionSet<L>`

Problem 3. Implement `RepArrayRegionSet`

3.1 Implement generic `RepArrayRegionSet<L>`

3.2 Wrap up `RegionSet`

Problem 4: `City<L>`

4.1. Test `City`

4.2. Implement `City`