6.031
6.031 — Software Construction
Spring 2022

Problem Set 2: Cityscape

Alpha due
Monday, March 7, 2022, 10:00 pm
Code reviews due
Friday, March 11, 2022, 11:00 am
Beta due
Monday, March 14, 2022, 10:00 pm

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,

  1. Ask Didit to create a remote psets/ps2 repository for you on github.mit.edu.

  2. 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.

  3. 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.

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

Our region sets will suppprt 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 touch each other.

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

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 SomeRegion­SetOfString to refer to the current implementation class being tested, and you must use new SomeRegion­SetOfString(..) 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.

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. You can define private helper functions in that file, but remember to keep such private helpers short: they cannot be unit tested. If you develop functions with useful specs, consider placing them in utils.ts and writing tests for them in utilsTest.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 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.

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.

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.

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.

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 region set 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.031/sp22.

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, the Didit build does not have to complete in order for that commit to be graded.
  • 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:
~35% alpha autograde + ~5% alpha manual grade + ~45% beta autograde + ~15% beta manual grade

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

Manual grading of the alpha will only examine the internal documentation (AF, RI, etc.) and implementation of your ADTs. Manual grading of the beta may examine any part, including re-examining ADT implementations, and how you addressed code review feedback.