Skip to main content
CSE 331: Software Design & Implementation

CSE 331 Homework 3: Abstraction, Reasoning, and Inventory

Due Friday, November 6 at 11:59pm (late policy).

The next few problems concern the following ADT:

/**
 * Represents a *mutable* map with integer keys and values.
 * Think of this as a list of integer pairs (an association list).
 */
public interface MutableIntMap {
  /**
   * Update the map so that k maps to v. The map should contain all
   * existing mappings in this when the key is not equal to k.
   * @param k the key to add or update
   * @param v the value for key k
   * @modifies this
   * @effects this with the value of k replaced with v if k is contained,
   *          or this with new (k, v) pair if not contained
   */
  public void put(int k, int v);

  /**
   * Returns the corresponding value of key k.
   * @param k the key whose value is to be retrieved
   * @requires this to contain k
   * @return v the value for key k
   */
  public int get(int k);

  /**
   * Returns whether the map contains a mapping for key k.
   * @param k the key to check
   * @return true if the mapping exists, false otherwise
   */
  public boolean contains(int k);

  /**
   * Removes the mapping for k if such a mapping exists in this.
   * Otherwise do nothing
   * @param k The key to search for and remove.
   * @modifies this
   * @effects this with the mapping for k removed if k is contained
   *          or this if not contained
   */
  public void remove(int k);

  // removes all keys with value < threshold
  public void removeIf(int threshold);

  /**
   * Removes all key value mappings from the map.
   * @modifies this
   * @effects this is empty
   */
  public void clear();

  /**
   * Returns the number of key-value pairs in the map.
   * @return the number of key-value pairs in the map.
   */
  public int size();
}

Task 1 — Spooky AF

In this problem, we will consider four different concrete representations. We write a[i .. j] for the elements of a from index i up to, but not including, index j; a[j .. j] is empty.

public class MutableIntMapImpl implements MutableIntMap {
    (1) RI: keys.length = values.length, size <= keys.length,
            and keys[0 .. size] has no duplicates and is sorted in
            increasing order.
        AF: AF(this) = the map of the keys[0 .. size] to their
            corresponding values.

    (2) RI: keys.length = values.length and size <= keys.length.
            keys[0 .. size] may have duplicates.
        AF: AF(this) = maps each key k in keys[0 .. size] to values[i],
            where i is the largest index < size with keys[i] = k.

    (3) RI: keys.length = values.length and size <= keys.length.
            keys[0 .. size] may have duplicates.
        AF: AF(this) = maps each key k in keys[0 .. size] to values[i],
            where i is the smallest index < size with keys[i] = k.

    (4) RI: keys.length = values.length = size, and keys has no duplicates.
        AF: AF(this) = the map of the keys to their corresponding values.

    private int[] keys;
    private int[] values;
    private int size;

    public MutableIntMapImpl(int[] keys, int[] values) {
        this.keys = keys;
        this.values = values;
        this.size = keys.length;
    }
}

For each of the following implementations of put, state the concrete representation(s) (1–4) for which the implementation would satisfy the specification of the put method in our provided ADT. In each case, briefly explain why.

  1. public void put(int k, int v) {
    int i = 0;
    while (i < this.size && this.keys[i] != k) {
        i = i + 1;
    }
    if (i < this.size) {
        this.values[i] = v;
    } else {
        this.keys = Arrays.copyOf(this.keys, this.size + 1);
        this.values = Arrays.copyOf(this.values, this.size + 1);
        this.keys[this.size] = k;
        this.values[this.size] = v;
        this.size = this.size + 1;
    }
}

  2. public void put(int k, int v) {
    if (this.size == this.keys.length) {
        this.keys = Arrays.copyOf(this.keys, 2 * this.size + 1);
        this.values = Arrays.copyOf(this.values, 2 * this.size + 1);
    }
    this.keys[this.size] = k;
    this.values[this.size] = v;
    this.size = this.size + 1;
}

  3. public void put(int k, int v) {
    int i = 0;
    while (i < this.size && this.keys[i] < k) {
        i = i + 1;
    }
    if (i < this.size && this.keys[i] == k) {
        this.values[i] = v;
        return;
    }
    if (this.size == this.keys.length) {
        this.keys = Arrays.copyOf(this.keys, 2 * this.size + 1);
        this.values = Arrays.copyOf(this.values, 2 * this.size + 1);
    }
    for (int j = this.size; j > i; j--) {
        this.keys[j] = this.keys[j - 1];
        this.values[j] = this.values[j - 1];
    }
    this.keys[i] = k;
    this.values[i] = v;
    this.size = this.size + 1;
}

  4. public void put(int k, int v) {
    if (this.size == this.keys.length) {
        this.keys = Arrays.copyOf(this.keys, 2 * this.size + 1);
        this.values = Arrays.copyOf(this.values, 2 * this.size + 1);
    }
    for (int j = this.size; j > 0; j--) {
        this.keys[j] = this.keys[j - 1];
        this.values[j] = this.values[j - 1];
    }
    this.keys[0] = k;
    this.values[0] = v;
    this.size = this.size + 1;
}

Task 2 — RI.P

Consider MyMap, an implementation of MutableIntMap. It stores the keys and values in two arrays, and only the first size entries of each are part of the map.

public class MyMap implements MutableIntMap {
    // RI: keys.length = values.length, 0 <= size <= keys.length, and
    //     keys[0 .. size] has no duplicates
    // AF: AF(this) = the map of the keys[0 .. size] to their corresponding
    //     values
    private int[] keys;
    private int[] values;
    private int size;
}

You may assume checkRep() is implemented correctly: it throws an exception if the RI does not hold, and does nothing otherwise.

For each of the following implementations, evaluate:

  1. Correctness: Does the code satisfy the method's specification and maintain the RI? Briefly explain why.
  2. Safe implementation practices: Does the code follow 331-style defensive programming? Specifically:
    • checkRep() should be called at the end of every constructor.
    • checkRep() should be called at the beginning and end of every mutator method.
    • checkRep() should be called at the beginning of every observer method.
    • Preconditions should be checked defensively when the check does not change the method's big-O running time. For example, a method that already loops over or copies an array should check a precondition that takes one loop over it, but a method that does neither need not.
    • The implementation should not expose its internal representation to clients.

Briefly explain why or why not.

  1. Consider the following implementation of the constructor:

    /**
 * Creates a new MyMap from two arrays of keys and values and an int size.
 * @param keys the keys of the map
 * @param values the values of the map
 * @param size the size of the map
 * @requires len(keys) = len(values),
 *           0 <= size <= len(keys), and
 *           keys[0 .. size] has no duplicate entries
 * @effects this is the map of the given keys[0 .. size] to their corresponding
 *          values
 */
public MyMap(int[] keys, int[] values, int size) {
    if (keys.length != values.length) {
        throw new IllegalArgumentException("keys and values not same length");
    }
    this.keys = Arrays.copyOf(keys, size);
    this.values = Arrays.copyOf(values, size);
    this.size = size;
}

  2. Consider the following implementation of get:

    public int get(int k) {
    checkRep();
    for (int i = 0; i < this.size; i++) {
        if (this.keys[i] == k) {
            return this.values[i];
        }
    }
    throw new IllegalArgumentException("map must contain k");
}

  3. Consider the following implementation of put:

    public void put(int k, int v) {
    checkRep();
    for (int i = 0; i < this.size; i++) {
        if (this.keys[i] == k) {
            this.values[i] = v;
        }
    }
    if (this.size == this.keys.length) {
        this.keys = Arrays.copyOf(this.keys, 2 * this.size + 1);
        this.values = Arrays.copyOf(this.values, 2 * this.size + 1);
    }
    this.keys[this.size] = k;
    this.values[this.size] = v;
    this.size += 1;
    checkRep();
}

  4. Consider the following implementation of clear:

    public void clear() {
    int[] clearedKeys = new int[0];
    int[] clearedValues = new int[0];
    checkRep();
}

Task 3 — Reason from the Dead

MutableIntMap's removeIf(int threshold) has no specification yet. It removes every key-value pair whose value is less than threshold.

  1. Write a complete JavaDoc specification for removeIf.

Below is an implementation of removeIf for MyMap, the implementation from the previous task. Recall its RI and AF:

// RI: keys.length = values.length, 0 <= size <= keys.length, and
//     keys[0 .. size] has no duplicates
// AF: AF(this) = the map of the keys[0 .. size] to their corresponding
//     values

Assume the RI holds when the method is called. The method moves each pair it keeps toward the front of the arrays, overwriting the pairs it drops. Below, this_0 is the object as it is when the method is called: keys0 and values0 are its arrays' contents then, and size0 is its size. The questions below ask you to fill in only the labeled assertions; the other blanks are there to help your reasoning.

public void removeIf(int threshold) {
    int i = 0;
    int j = 0;
    {{ P1: ____________________________________ }}
    {{ Inv: 0 <= j <= i <= size,
            (keys[0 .. j], values[0 .. j]) are the pairs of
            (keys0[0 .. i], values0[0 .. i]) whose value is >= threshold,
            in the same order,
            keys[i .. size] = keys0[i .. size],
            values[i .. size] = values0[i .. size],
            size = size0 }}
    while (i < this.size) {
        {{ ____________________________________ }}
        if (this.values[i] >= threshold) {
            {{ ____________________________________ }}
            this.keys[j] = this.keys[i];
            {{ ____________________________________ }}
            this.values[j] = this.values[i];
            {{ ____________________________________ }}
            j = j + 1;
            {{ ____________________________________ }}
        }
        {{ P2: ____________________________________ }}
        {{ Q2: ____________________________________ }}
        i = i + 1;
        {{ Inv }}
    }
    {{ ____________________________________ }}
    this.size = j;
    {{ P3: ____________________________________ }}
    {{ Q: this = this_0 with every pair whose value is < threshold removed }}
}

  1. Use forward reasoning to fill in assertion \(P_1\). Then prove that \(P_1\) implies Inv.

  2. Fill in \(P_3\). Then prove that \(P_3\) implies \(Q\).

  3. Using \(P_3\), and that the method never assigns a new array to keys or values, prove that the RI holds when the method returns.

  4. Use forward reasoning to fill in \(P_2\). Then fill in \(Q_2\) using backward reasoning from Inv. Then prove that \(P_2\) implies \(Q_2\). Consider both branches of the if statement. An assignment a[j] = e changes a[j] and no other element of a.

Inventory

In this part of the homework you will build a simple terminal application to manage items in an inventory.

Starter code

Go to the CSE 331 public gitlab repository in the hwInventory folder. Click the blue "Code" button in the top right, and then click Download directory as zip at the very bottom of the popup. Extract the resulting file on your machine. You should see the following files:

  • Inventory.java: the specification for the inventory data structure.
  • InventoryImpl.java: starter file for your implementation of the inventory data structure.
  • InventorySpecTest.java: starter file for your specification-based tests.
  • InventoryImplTest.java: optional starter file for your implementation-based tests.
  • InventoryTerminalApp.java: starter file for your terminal application.
  • lib/: JUnit jar.
  • Makefile: shortcuts for compiling and running (see below).

Software setup

This course uses JDK 25; the resources page describes how to install it if you do not already have it.

You may use any Java development environment you want. If you have one you are already comfortable with, we recommend you use it.

Visual Studio Code

If you are looking for a Java development environment, we recommend Visual Studio Code because it is easy to set up. You will need the "Extension Pack for Java". (Open the extensions panel in VS Code and search for "Extension Pack for Java" and install it.)

Once you have VS Code and the extension pack installed, then:

  1. Use File -> Open Folder... and select the unzipped hwInventory folder you downloaded earlier.
  2. Open the InventoryTerminalApp.java file.
  3. You should see a "Java activating" message near the bottom of your window.
  4. Once it is finished activating, you should see a green "Run" button above the main method in InventoryTerminalApp. Press the run button to run the starter code and confirm that your setup is working.

The rest of the starter code (in particular InventoryImpl.java) will not compile due to unimplemented methods until you have finished Task 4 below.

Working on attu

If you would rather not install Java on your own computer, you can work on attu, the Allen School's Linux servers, which already have JDK 25. You log in with your CSE NetID and its password; off campus, first connect to the Husky OnNet VPN. To work on attu from Visual Studio Code:

  1. Install the "Remote - SSH" extension from the extensions panel.
  2. Use View -> Command Palette..., run Remote-SSH: Connect to Host..., and enter YourCSENetID@attu.cs.washington.edu. If VS Code asks for the platform, choose Linux. The first time, VS Code takes a minute to set itself up on attu; once you are connected, the bottom-left corner shows SSH: attu.cs.washington.edu.

  3. Use View -> Terminal and run this command to get the starter code:

    git clone https://gitlab.cs.washington.edu/cse331-26au/cse331-26au-public.git

  4. Use File -> Open Folder... and select cse331-26au-public/homework/hwInventory.

Your files then live on attu. To submit, right-click each one in the Explorer and choose Download... to copy it to your computer, then upload it to Gradescope.

Using the command line

Alternatively, you can run the code from the command line. From the unzipped hwInventory directory,

make compile     # compile everything
make run         # run the terminal app
make test        # run all tests
make clean       # delete compiled .class files and submission.zip

The Makefile should work on macOS, Linux, and Windows (you'll need to install Make if you don't already have it).

These make targets will exit with error in the starter code due to unimplemented methods until you finish Task 4 below. Until then, java InventoryTerminalApp.java runs the starter's counter demo, to check your setup.

Task 4: Implement and test the inventory

Read the specification of Inventory carefully. It describes an ADT representing the state of an inventory.

Once you have read the required interface, then you should:

  1. Write your implementation in InventoryImpl.java.
  2. Write spec tests, and any implementation tests, as described below.

Specification-based vs implementation-based testing

A specification-based test relies only on behavior described in the specification. It would pass when run on any correct implementation of the spec, including yours, your classmate's, or the course staff's.

An implementation-based test additionally relies on choices a particular implementation made. These are most often choices about behavior that the spec leaves unspecified. For example, what happens when a method is invoked on an input that violates its precondition? That behavior can only be tested in an implementation-based way. These tests may be useful for your own development, but they might not pass when run on a different but equally correct implementation.

For this reason, we have given you two different test files:

  • InventorySpecTest.java contains only specification tests, that is, tests that only depend on behavior guaranteed by the Inventory specification.
  • InventoryImplTest.java contains any additional tests you want to write that may depend on behavior unique to your implementation

We've given you one example test in InventorySpecTest.java. You'll need to add many more to satisfy the coverage and bug-detection requirements below. Your spec tests should meet Lecture 5's coverage standard on your InventoryImpl, and test only allowed inputs. The staff grade coverage by hand.

Your spec tests may use only the Inventory interface and the zero-argument InventoryImpl constructor, so that they can run against other implementations: if they use anything more, none of them can, and they catch no bugs. The types nested in Inventory are part of it: write them as Inventory.Transaction and so on, since import Inventory.Transaction; does not compile. What Inventory.java says about the collections and maps its methods return is part of the specification too, and so is what a purchase leaves when it throws: test what the inventory holds after the throw, as well as that it throws. We will grade your tests by:

  1. Run your tests against your implementation: your spec tests, and your implementation tests if you submit them. They must all pass, and at least one spec test must run.
  2. Run your spec tests against the staff implementation and other correct implementations. A spec test that fails against any of them tests behavior the specification does not require, so it does not count in step 3.
  3. Run your spec tests against several deliberately buggy implementations we've prepared. A buggy implementation is caught when one of your spec tests that counts fails against it. Points are proportional to the number caught, and full points take catching every one. A good test suite is able to distinguish correct implementations from incorrect ones. Tests that exercise a method but don't actually check meaningful behavior (e.g., calling a method without asserting anything about the returned value) won't catch many bugs.

A test that runs longer than 15 seconds fails. The autograder runs your spec tests against many implementations within a fixed time, so keep them fast: a slow suite may not reach every buggy implementation.

So on the one hand, your spec tests must be thorough enough to catch buggy implementations. But on the other hand, your spec tests must not test any behavior that is not required by the specification. You should use what you learned about testing this quarter to assist you in forming your test suite.

The implementation test file is optional. If you submit it, its tests must pass against your implementation (step 1).

Task 5: The terminal application

Build a small interactive terminal application in InventoryTerminalApp.java that lets the user manage an inventory from the command line. Use the InventoryImpl data structure implementation you wrote in Task 4.

The starter code for the terminal app includes a small "counter" demo to show you the basics of how to use a Scanner to make an interactive terminal application. You should delete this starter code and replace it with your real application.

You have the freedom to design the specifics of how the terminal application works, as long as your application supports all of the functionality described below. As long as a user can do each of the things in the scenarios below, you're free to design the interface however you like.

In the scenarios below, ingredient names are single words with no spaces, like EyeOfNewt, because a command's parts are separated by spaces. Your app only needs to support single-word names.

You do not need to submit JUnit tests for the terminal application. But you should run the application yourself and ensure that all required behavior works as desired. Course staff will grade your terminal application by running it and trying it themselves.

Required functionality

The application must let the user:

  • ship: Record a shipment arriving (increases an ingredient's quantity).
  • buy: Record a customer purchase (decreases an ingredient's quantity).
  • quantity: Show the current quantity of an ingredient.
  • history: Show an ingredient's transaction history.
  • item: Show an ingredient's quantity and history.
  • items: Show all ingredients in the inventory.
  • all: Show the quantity of every ingredient.
  • log: Show every transaction ever, in order.
  • help: Display available commands and usage hints.
  • exit: Close the app gracefully.

As a user-facing application, it should be mostly self-documenting: a user who has never run it before should be able to figure out what to do. At a minimum, the program should print a menu of available commands (or otherwise display the available options) so the user doesn't have to guess. It should also handle all inputs reasonably and with decent error messages. For example, if the user asks for an item that does not exist, then the program should not crash, but rather should print an error message and continue, allowing the user to retry.

Example Scenario

The following scenario illustrates the required functionality. Your application should be able to handle equivalent functionality, though you are free to use a different menu format and display information differently. Of course, just being able to handle this one example scenario correctly does not mean your code is correct in all cases.

Jared, a friend of the class, has been exploring new business ventures, and the season inspired him to flip his failing bar into a potion shop! He has big plans for the Halloween rush, but every good potion starts with good ingredients. Luckily, Zach, who has secretly been a witch this whole time, owns the town's one and only potion ingredient shop, and he is ready to help Jared in this new endeavor. Zach plans to stock eye of newt, toe of frog, wing of bat, and witch's herbs, and he needs a reliable way to track what's on his shelves and every transaction that got it there. So, what better to do with your 331 knowledge than write a program to help him?

Zach's supplier is James, who has recently taken a deep interest in witch's herbs and has become the go-to source for all things slimy. His first delivery arrives, so Zach records both shipments in your app, doing various checks manually to verify what he's storing.

============================================
 Potion Ingredient Shop Inventory Dashboard
============================================

Commands:
  ship <item> <qty>       Record a shipment from James (increases quantity)
  buy <item> <qty>        Record a customer purchase (reduces quantity)
  quantity <item>         Show current quantity of an ingredient
  history <item>          Show transaction history for an ingredient
  item <item>             Show quantity + history for an ingredient
  items                   List all known ingredients
  all                     Show current quantity of every ingredient
  log                     Show every transaction ever, in order
  help                    Show this message
  exit                    Quit the app

> ship EyeOfNewt 100
Shipment recorded: +100 EyeOfNewt (now 100)
> ship ToeOfFrog 50
Shipment recorded: +50 ToeOfFrog (now 50)
> quantity ToeOfFrog
ToeOfFrog: 50
> history ToeOfFrog
  1. ToeOfFrog: shipment of +50
> log
  1. EyeOfNewt: shipment of +100
  2. ToeOfFrog: shipment of +50
>
Zach records 2 separate shipments from James: eye of newt and toe of frog

With Zach's shelves stocked, he is ready to help with Jared's first order! Jared runs in with an urgent request for some wing of bat that he needs for a brew. Zach tries to ring up the sale but...

...
> buy WingOfBat 1
Error: no item called 'WingOfBat' (try 'items')
>
Jared tries to buy wing of bat, which isn't in inventory

Jared, deeply disappointed, asks "my disappointment is immeasurable and my brew is ruined, what do you even have?" Using your really cool app, Zach runs the items command to find out.

...
> items
Items: EyeOfNewt, ToeOfFrog
>
Checking the current inventory of items

Since he already made the trip, Jared decides he has to leave with something. He buys 20 eye of newt and 5 toe of frog.

...
> buy EyeOfNewt 20
Purchase recorded: -20 EyeOfNewt (now 80)
> buy ToeOfFrog 5
Purchase recorded: -5 ToeOfFrog (now 45)
>
Jared buys 20 eye of newt and 5 toe of frog

Excited at being able to help Jared brew his first potion, Zach checks his inventory to make sure it actually went through!

...
> log
  1. EyeOfNewt: shipment of +100
  2. ToeOfFrog: shipment of +50
  3. EyeOfNewt: purchase of -20
  4. ToeOfFrog: purchase of -5
> quantity ToeOfFrog
ToeOfFrog: 45
> history ToeOfFrog
  1. ToeOfFrog: shipment of +50
  2. ToeOfFrog: purchase of -5
> item ToeOfFrog
ToeOfFrog: 45
  1. ToeOfFrog: shipment of +50
  2. ToeOfFrog: purchase of -5
> item EyeOfNewt
EyeOfNewt: 80
  1. EyeOfNewt: shipment of +100
  2. EyeOfNewt: purchase of -20
>
Zach checks the inventory in multiple ways

With the sale done and the inventory checked, Zach decides to call it a night and closes up shop.

...
> exit
Shutting Down...
The exit command prints Shutting Down... and exits the program.

Correctness and code quality

In addition to evaluating your tests (Task 4), we will grade your inventory ADT implementation and your terminal application on correctness and on code quality.

A passing test suite is good, but it does not guarantee that your code is correct. Despite this, you are responsible for turning in code that works, and for doing the work to convince yourself that it works. You should reason carefully about the spec, trace through your code and ensure it satisfies the spec in all cases.

Be sure your inventory ADT implementation follows all the rules for implementing an ADT in 331. You must document in a comment the AF and RI, define and call checkRep(), and defensively check fast preconditions.

The starter code already includes specifications for every method on the inventory interface, so you don't need to write any new specs in InventoryImpl.java. But your implementation must satisfy the specs we've given you.

AI Policy

You should not use any AI assistance for any part of this assignment. See the course's AI policy.

Submission

Submit your answers to Tasks 1–3 to the "HW3 Written" assignment on Gradescope.

Submit the following files to the "HW3 Coding" assignment on Gradescope:

  • InventoryImpl.java
  • InventorySpecTest.java
  • InventoryImplTest.java
  • InventoryTerminalApp.java

Upload the files themselves, or run make submission to bundle them into a submission.zip and upload that. Never upload a zip of their folder: Gradescope keeps a zip's folders, and the autograder reads only files at the top level. InventoryImplTest.java is optional. The autograder reads no other file, so keep all of your code in these four.

You should not modify or submit Inventory.java.

HW3 Written and HW3 Coding each need their own Friday submission to unlock their late day. A Friday submission to one does not unlock the other; see the late policy.

The Gradescope autograder compiles your files and runs your tests against your implementation as soon as you submit, and shows you the results. If any file you submit does not compile, the autograder scores 0. It is worth 10 points:

  • Student tests (2 points): step 1 of how we grade your tests.
  • Bug detection (5.5 points): steps 2 and 3.
  • Staff hidden tests (2.5 points): the staff's own tests, run against your implementation.

You see the Student tests points right away. The other 8 points are graded after the late day, and you see them when grades are published. The autograder also warns you if your spec tests use more than the Inventory interface and the zero-argument constructor, and checks that your terminal app starts and waits for input. Passing all the autograder tests does not guarantee your code is correct or high quality.