Maps

Composing and testing a complex data structure from scratch.

Learning Goals

• Build a data structure by delegating to other data structures.

  In practice, software developers rarely write their own basic data structures with general functionality: we can usually find implementations for these written in pre-existing libraries. Instead, the data structure we need to implement ourselves are often tailored to specific purposes and built off of other existing data structures.

  Similarly, this assignment will have you first implement a basic data structure that fulfills the map ADT, then build a more-complex map using that basic implementation.

• Review the iterator design pattern.

  Iterators are a common sight in Java code, and for good reason: they allow us to access elements of data structures in sequential order—a task often inefficient or impossible otherwise. For example, the iterators you will implement in this assignment will provide access to all entries of a map, which would not be possible via any combination of the other methods that you will implement.

• Practice choosing invariants to ease implementation.

  The previous assignment gave you some experience with writing code to maintain invariants; now, it’s time to choose your own. Designing strong invariants will reduce the complexity of your code by restricting the number of possible cases your code needs to handle—by spending some time planning these out, you can save time spent writing needless special cases, especially for more-complex data structures.

Getting the Assignment

Task

Pull the skeleton repository in IntelliJ to get the maps assignment.

Like previous projects, if IntelliJ doesn’t react to the new folder for whatever reason, refresh Gradle manually through the Gradle tool window (on the right by default):

Feedback Survey

After completing both the programming and experiment portions of the assignment, we’d appreciate if you take a couple minutes to complete the individual feedback survey on Canvas for extra credit. (Each partner needs to submit their own individual response.)

Table of contents

• Programming - Complete the programming portion of the assignment.
• Experiments - Run some experiments and complete a brief write-up.