►Assignment 2: Programming with Trees and Testing to Specifications
1 Implementing Tournaments
2 Testing Data Structure Implementations
2.1 Queues
2.2 Stacks
2.3 Priority Queues
2.4 A Note on Writing the Tests
3 What to Turn In
3.1 Submission Checklist

Assignment 2: Programming with Trees and Testing to Specifications

Due: Tuesday, November 10 at 11:59pm via InstructAssist. A myWPI questionnaire about this assignment is due 45 minutes later (closing at 12:45am). Once you access the questionnaire, you will have 30 minutes to submit your answers.

We finished the material needed for Programming Tournaments by Monday (Nov 2). We will set up idea of the Testing Data Structures material on Thursday and Friday, though if you had some data structures in high school, you will likely get the gist of that section without this week’s lectures).

1 Implementing Tournaments

For last week’s homework, you developed classes for contestants and matches. Now we want to build off of those to create tournaments, a hierarchy of matches between two contestants in which the winner of each match advances to the next round until there is a single winner. Tournaments are thus shaped like trees, as follows:

                Contestant1 (winner)

                /                 \

      Contestant3                  Contestant1

       /        \                  /         \

Contestant3   Contestant4   Contestant1    Contestant2

We can see from looking at this diagram that there are really two kinds of matches: initial matches occur in the first round of the tournament (the bottom as shown in the above figure); advance matches occur in later rounds and involve contestants who advanced from earlier matches in the tournament. The diagram above has two initial matches (one between Contestants 1 and 2, and another between Contestants 3 and 4) and one advance match (between Contestants 3 and 1).

We are going to capture tournaments in Java in a way that reuses the classes and interfaces you created for homework 1 (you are welcome to update or fix your work from homework 1 as needed).

  1. Develop the following classes and interfaces to capture tournaments:

    Update 11/6: The original handout accidentally used lowercase letters at the start of the class names. This has updated those to InitMatch and AdvanceMatch.

    • A class InitMatch which contains a single field of type Match from homework 1 (the Match class contains two contestants and the results).

    • A class AdvanceMatch which contains a field of type Match (the contestants and results for that match) and two fields containing the feeder matches (InitMatch or AdvanceMatch) that led into this match. You need to figure out the appropriate types for the fields representing the feeder matches.

    • An interface ITourneyTree which can be either an InitMatch or an AdvanceMatch. An entire tournament will be captured by the ITourneyTree that determined the overall tournament winner.

  2. Make at least two examples of tournaments in your Examples class.

  3. It would be possible to create an AdvanceMatch in which the contestants that won the feeder matches are not the ones who played in the match itself (for example, the top level of the tournament shown above could have a feeder match between Contestants 5 and 6, even though the topmost match was played between Contestants 1 and 3). We want to have a method that sanity checks tournament trees to make sure that the players in the match are the same as the winners of the two feeder matches.

    Write a method winnersAlwaysAdvanced on tournaments (aka ITourneyTrees) that produces a boolean indicating whether every match is either an InitMatch or an AdvanceMatch in with the contestants are also the winners of the two feeder matches. Use your winner method from homework 1 to determine winners. You may assume that no matches ended in a tie.

    Update 11/6: If you did not get the winner method or other parts of homework 1 working, you may use another student’s solution for homework 1. If you do this, please add a comment in one of your files telling us whose work you are using.

  4. Write a method countUnderdogWins on tournaments on that produces the number of matches in the tournament in which the winner was an underdog (as defined by underdogWon in homework 1).

  5. Provide test cases for both methods, but focus on thoroughness of your tests for winnersAlwaysAdvanced. We will run your winnersAlwaysAdvanced tests against several broken implementations to check how well you are testing that method.

To help you test whether your names are correct, use this custom Main.java file. It will test that you have the exact names and types that the auto-grading system is expecting for your classes, interfaces, and methods.

2 Testing Data Structure Implementations

This section describes three fundamental datatypes that access elements of a collection in different orders. We have given you the types of operations for the datatype, an informal description of the datatypes’s properties, and an example sequence of using the operations. For this assignment, we will assume each datatype is storing ints (rather than Strings, as we did for sets in lecture). We will also assume that each can contain duplicate elements.

For each datatype, your job is to write a collection of test cases that would determine whether a program that implements the datatype has done so correctly. If we run your tests against a correct implementation, all of your tests should pass. If we run your tests against an incorrect implementation, then at least one of your tests should fail. Thus, this question is about how well your tests cover the expected behavior of the datatype; it is not about the sheer number of tests that you propose.

Provide a file Examples.java containing a single Examples class with up to seven (7) tests per datatype, each written as a checkExpect against the Tester library. The names of your test methods should indicate the data structure being tested: use method names testQueue, testStack, and testPQ as the prefixes for your test case names. Do not worry about tests on undefined cases that would yield errors (like trying to remove an element from an empty data structure).

Compile your Examples.java file against this file of interfaces and dummy classes to make sure you match the names we’ll assume when grading your work. Note that the methods given in the dummy file are broken. Your test cases will fail against the dummy file. What matters is that your code compiles when using the dummy file.

You are not being asked to implement any of these datatypes. You are merely defining test cases. The challenge in this assignment lies in figuring out how to develop a good set of test cases given only a description of the operations and the properties. You should nevertheless make sure that your file at least compiles (as we will do the same when we evaluate your test suite). If you aren’t sure where to start, think about ways that someone could make a mistake when writing programs for the datatypes, then write tests to detect those mistakes.

One goal of this assignment is for you to understand these three data structures and what they do. After this assignment, you should be able to decide which of these data structures to use for a given problem, based on understanding their operations.

2.1 Queues

A Queue is a data structure for accessing items in the order of least-recently added to most-recently added (otherwise known as "first in, first out", or FIFO-order). The operations on queues are:

  • enqueue: Queue, int -> Queue // adds element

  • dequeue: Queue -> Queue // remove least recently-added element

  • front: Queue -> int // return, but don’t remove, least-recently added elt

  • isEmpty: Queue -> boolean // indicates whether Queue is empty

Example: Assume that we added elements 7, 4, and 5 to a new queue (in that order). Calling dequeue would produce a queue containing 4 and 5. Calling front on that queue would produce 4. Calling dequeue on that queue again would produce a queue containing 5.

2.2 Stacks

A Stack is a data structure for accessing items in the order of most recently added to least-recently added (otherwise known as "last in, first out", or LIFO-order). The operations on stacks are:

  • push: Stack, int -> Stack // adds element

  • pop: Stack -> Stack // remove most recently-added element

  • top: Stack -> int // return, but don’t remove, most-recently added elt

  • isEmpty: Stack -> boolean // indicates whether Stack is empty

Example: Assume that we added elements 7, 4, and 5 to a new stack (in that order). Calling pop would produce a stack containing 4 and 7. Calling top on that stack would produce 4. Calling pop on that stack again would produce a stack containing 7.

2.3 Priority Queues

A Priority queue is a data structure for accessing items in order. Items may be added to a priority queue in any order, but items may only be removed in order from smallest to largest. The operations on priority queues are:

Example: Assume we added elements 7, 4, and 5 to a new priority queue (in that order). Calling getMinElt on the resulting priority queue should return 4. Calling remMinElt should produce a priority queue containing only 5 and 7.

2.4 A Note on Writing the Tests

The interfaces that we give you for the operations don’t let you "look inside" the data structures to see what is there. If you write

  new Queue().enqueue(5)

for example, the object that you get back doesn’t give you a way to look inside to check whether the 5 is actually there. All you have are the operations on the datatype. This raises a challenge: how can you test whether our code for the data structure is working just using the operations in the interface?

The key here is to think about how the operations might interact. For example, after you’ve done new Queue().enqueue(5), do you know anything about what the isEmpty method should produce? Or front? When you write your tests, first use the operators to create some data that you want to test, then use the other operations to test whether the resulting object makes sense. Here’s an example:

  boolean testQueueEnqueueNotEmpty(Tester t) {

    Queue myQueue = new Queue().enqueue(5);

    return t.checkExpect(myQueue.isEmpty(), false);

  }

In this case, you are testing enqueue by using it to create a queue, then making sure that the resulting queue is not empty.

All of our operations return new objects with the resulting data, rather than modify the existing objects. So if you write

  IQueue myQueue1 = new Queue().enqueue(5);

  IQueue myQueue2 = myQueue1.enqueue(8);

then myQueue1 will still have only one element, even after you create myQueue2. This should make it easier for you to chain operator calls and to set up your tests.

3 What to Turn In

Turn in a single .zip file (only .zip) with all of your files. Also submit the homework 2 questionnaire on myWPI (in the tests area).

To enable auto-grading, your zip file must separate your test cases into different classes. Specifically, you should provide the following four classes (none of which should be public):

These classes can be either in a separate file per class, or all in your Examples.java file.

If you have tests on your own helper methods, they will confuse the auto grader (because we don’t have your helper methods in our code). To avoid compilation problems you can either

  1. Comment our your helper method tests before submitting. Java lets you comment out multiple lines of code by wrapping them as follows:

      /*

        all the code

        that you want

        to comment out

        */

  2. Create a fifth class for tests of your helper methods. This class can grab data from your official Examples class, while still keeping the tests separate. For example, you could write

      class ExamplesHelpers {

        Examples E = new Examples();

      

        // reuse the myRugbyMatch data from the Examples class

        ... t.checkExpect(E.myRugbyMatch.winner(), ...)

      }

    If you do this, you will want to edit your Main.java to also run the tests from your ExampleHelpers file. We have edited the custom Main.java file with the code you need (uncomment the lines for the ExamplesHelper at the bottom of the file to run those tests).

3.1 Submission Checklist