Part 1: Verifying Correctness of Methods

Complete the code reasoning problem given in this worksheet.

On the worksheet, you will verify the correctness of the union and intersection operations with finite sets of real numbers. Before you start the problems, make sure you fully understand the background given in the first page.

Feel free to print out the worksheet or rewrite the problems on a separate sheet. You may submit a scanned copy of any hand-written document with the problems and your solutions as long as it is legible.

Submit your solution as a PDF in Gradescope. Be sure to indicate in Gradescope which pages of your PDF solve each problem.

Part 2: Writing Unit Tests for FiniteSet

When we release each homework assignment, we push the new starter files to your repository in GitLab, so you should obtain these new files by pulling from git.

The rest of this assignment is going to involve working with

• FiniteSet.java and SimpleSet.java in the directory hw-sets/src/main/java/sets,

• The test files FiniteSetTest.java and SimpleSetTest.java in the directory hw-sets/src/test/java/sets.

To start, read FiniteSet.java, understand how a FiniteSet is represented, and what each method does. Note that the union and intersection methods are the ones given in Part 1, and there is a provided method for the set difference operation.

Then, go to FiniteSetTest.java, and see the tests written for constructing FiniteSet objects or checking the equals method.

One approach used to write these tests is the “0, 1, 2” heuristic. We look at an empty object (0), an object with only one element (1) and an object with multiple elements (2).

The "0, 1, 2" heuristic is a good place to start for writing tests, but it shouldn't be the only appraoch you use. Consider other heuristics, as mentioned in lecture, when deciding which tests to write. One such heuristic is looking at the internal representation of an ADT, and giving inputs that might break the representation invariant if not implemented. The out-of-order case in the testCreation method here is an example to this approach.

With these in mind, write unit tests for the union, intersection, and difference methods in FiniteSetTest.java.

Your test suite should cover the simple cases mentioned above, as well as other, more complex cases specific to potential errors for these methods. As you are writing unit tests, each test method should test a specific case, such that failing a test would tell you as much as possible about why the code is incorrect.

We give you some starter methods: testUnion, testIntersection and testDifference in FiniteSetTest.java to give you a base for writing tests, but feel free to replace or add new methods beyond these in order to follow our unit testing standards.

You can refer to the testing guide for more hints on the test cases you can include.

Part 3: Implement the Representation of SimpleSet

Read the specification in SimpleSet.java to understand what SimpleSet represents, as well as behavior of each method.

As you can see, the ADT is fully documented but missing its representation: there are no private fields defined in the SimpleSet class and no Abstraction Function or Representation Invariant.

A SimpleSet either represents a finite set, or a set only excluding a finite set, however it is not possible to store an infinite number of points in a set. To do this, you should include exactly one field representing a FiniteSet of points and one boolean field representing whether or not this SimpleSet represents the complement of its stored FiniteSet. In other words, the boolean field determines whether the abstract state includes or excludes the points in the representation.

If a set is finite, the FiniteSet will be used to contain all of the points IN the set, and the boolean field might be false.

If the set is infinite, the FiniteSet will be used to contain all of the points NOT in the set, and the boolean field might be true.

Additionally, write a suitable Representation Invariant (defining the rules of the state of the representation) and Abstraction Function (translating the abstract representation to the actual representation) above the private fields. Refer to FiniteSet.java, lecture/section slides, or the Writing Rep Invariants and Abstraction Functions handout for more help on representation invariants and abstraction functions.

Once your representation is complete, implement the SimpleSet constructors and the equals method. The SimpleSets that we create in the test suite rely on the complement method which we do not implement until part 4, so the tests provided for the equals method will not all pass yet. To get some reassurance that you're on the right track testEqualsEmptySet, testEqualsSingleton, and testEqualsComplexSet in SimpleSetTest.java should fail on lines 82, 93, and 108 respectively.

Part 4: Implementing and Testing Short Methods

Now that you have a good representation for the SimpleSet ADT, you can implement its methods as described in the specifications above them. Specifically, implement size and complement to start. As a reference, the staff solution for these methods were very short.

While implementing these methods, you should also include explanations as to why your code is correct. These are not meant to be formal assertions, they are supposed to be easily readable by someone looking at your code. Explain your solution thoroughly, so that it's easy to understand why the code works. As a minimum, you should explain how your answer is calculated based on the type of SimpleSet you are working with (finite, or complement of finite), even if you don't use any if/else statements. To get full credit, your code should be not just correct, but also easy to understand.

Once you have implemented complement, the testEquals and testComplement tests provided in SimpleSetTest.java should now pass.

However, for size, we have provided no tests, so you will need to write them yourself in SimpleSetTest.java. We have given you an empty method testSize to fill out, but add additional methods to best test a single subdomain at a time. You should choose your set of test inputs carefully, applying the heuristics taught in class. (The approaches mentioned in Part 2 are useful here also, but keep in mind that SimpleSet will likely require more cases due to the fact that it can represent more types of sets than FiniteSet.) Once you have tested a good set of inputs and the tests pass, you can move on to the next problem.

Part 5: Implementing More Complex Methods

Next, continue on to implement the union, intersection, and difference methods. As a reference, the staff solution for each of these is ~10-15 lines.

Start by implementing the union method. You should take advantage of the methods of FiniteSet that are already available. These will allow you to form the union of two finite sets. However, you must also handle the cases where one or both of the SimpleSets involved are not finite but rather the complement of finite sets.

Similar to the previous part, you should include comments explaining why the code is correct. As a minimum, you should explain how your method behaves with every combination of SimpleSet types. Each of the two sets can be either finite or finite complement, so there are four possible combinations. We recommend that you handle each of these cases separately in your implementation.

To get full credit, your code should be not just correct but also easy to understand. When you are done with your implementation, you should check your solution by running the tests for union provided in SimpleSetTest.java.

Next, implement the methods intersection and difference.

As with union, you should include comments explaining why the code is correct for each combination of SimpleSet types. Even if your implementation handles some combinations with the same code, your comments should explain each of these cases. To get full credit, your code should be not just correct but also easy to understand.

When you are done with your implementation, you should check your solution by running the provided tests for these methods in SimpleSetTest.java. At this point, all provided tests and all tests you have written so far should be passing.

Part 6: Implementing and Testing toString

For the last part of the assignment, we work with toString. Read the specification, and understand what the output should be in each case.

Then, write unit tests for it in SimpleSetTest.java. Again, we give you a starter method, testToString, but add methods as you see fit so each method tests a single subdomain. Make sure that these tests fail (as it should since toString is not yet implemented). You can refer to Part 2 and 5 for hints on which cases you can test. Keep in mind that you should not expect your method to round floating point numbers (to a number of decimal places other than the default).

After your test suite is finished, implement toString based on the specification. For any loop in your implementation, make sure to include a loop invariant. Additionally, you should include a comment explaining why the code works, similar to what was asked in previous parts. To do this, you can use a StringBuilder, which is helpful for building a string. You should not round floating point numbers, you can just add them to your string with default formatting.

After both your tests and implementation are finished, you can check your answer by running your tests. While passing tests is not a guarantee that your code works correctly, writing tests before the implementation makes it less likely for you to repeat the same mistakes in both.