Problem Set 2: Cityscape

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.

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

Three dimensions

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 name 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 with string labels — twice.

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

You can choose either RepMapRegionSet or RepArrayRegionSet to write first.

2.1. Implement RepMapRegionSet

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

2.2. Implement RepArrayRegionSet

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

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

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

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

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

   and:

   export class RepArrayRegionSet<L> implements RegionSet<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 RepMapRegionSet and RepArrayRegionSet generic types.

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

   Your tests will continue to use 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.

   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}`;
   You may ignore the restrict-template-expressions error from ESLint.

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

3. Finally, pick one of your RegionSet implementations for clients to use, and implement makeRegionSet() in RegionSet.ts.

If you cannot figure out how to make your implementations generic while satisfying the TypeScript 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 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!

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

4.2. Implement City

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

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/fa21.

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.

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.