Problem Set 2: Cityscape

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.

Labels do not have to have string type, but can have 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.

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.

For RepMapRegionSet, you must use the rep provided:

private readonly map: Map<string, Array<Rect>> = new Map();
public readonly size: 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 size.

All TypeScript classes inherit Object.toString() with its very underdetermined spec. By pointing to that spec with @link, 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 implementing makeRegionSet() to return an instance of RepMapRegionSet, then running npm test -- -f RegionSet.

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

For RepArrayRegionSet, you must use the rep provided:

private readonly array: Array<string | undefined> = [];
public readonly size: 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 size.

Run your RegionSetTest tests on RepArrayRegionSet by implementing makeRegionSet() to return an instance of RepArrayRegionSet, then running npm test -- -f RegionSet.

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:

   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.

   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 RegionSet does not know or care about the actual type of the labels, and only compares them according to the RegionSet specification, your test suite with string labels is sufficient.

Note: you cannot write tests with other types of labels in RegionSetTest, because those tests must use the makeRegionSet() method to get new sets. That method always returns RegionSet<string>.

Pick one of your RegionSet implementations for clients to use, and implement makeRegionSet().

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

• And of course, commit and push.

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.

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.