Problem Set 3: Polymorphism, Trees, and Testing

Problem Set

Repository link: https://github.com/CSE-116/ProblemSet-3

To submit your project, run problem.Zipper, which will create a zip file containing the problem set, and submit it to Autolab.

Specification

For this problem set, you will implement a media library that uses polymorphism, static methods on binary trees in problem.ProblemSet3, and JUnit tests. Unless noted otherwise, methods are public and non-static.

The problem.Media abstract class is provided to you in its entirety. Do not make any changes to this class.

  • Song (Testing: 3 points, Implementation: 2 points): The problem.Song class is provided in the starter code. It extends Media and includes a constructor and the methods play, pause, and getPlaybackTime, all of which function properly and do not need to be edited. However, the provided advancePlaybackTime method contains multiple bugs that need to be fixed. The expected behavior of advancePlaybackTime is as follows:
    • If the song is not playing, the playback time should not change
    • If the song is playing, the playback time should increase by the given time (all time units are in seconds)
    • If advancing would move past the end of the song, the playback time should stop at the song's duration and the song should be marked as finished by setting the isFinished instance variable to true
    • This method must override advancePlaybackTime from Media
  • Chapter (Testing: 3 points, Implementation: 2 points): Create a class in the problem package named Chapter. A chapter represents a named segment of an audiobook with a duration. This class should implement the following methods:
    • Constructor: Create a constructor that takes the title of the chapter, as a String, and the duration of the chapter, as a double, in this order
    • Getters and Setters: Implement getters and setters following the usual structure named getName, setName, getDuration, and setDuration
  • Audiobook (Testing: 5 points, Implementation: 5 points): Create a class in the problem package named Audiobook that extends Media. An audiobook plays a sequence of chapters in order. This class should implement the following methods:
    • Constructor: Create a constructor that takes a title (String) and the chapters for this audiobook (array of Chapters), in this order. Note that this constructor takes a plain array using the [] syntax, not an ArrayList
    • Abstract methods: Implement the inherited abstract methods play, pause, and getPlaybackTime with the same functionality as the Song class
    • setPlaybackSpeed: Set the playback speed of the audiobook. Playback speed should initially be 1.0. The playback speed cannot be set to a value less than 0.5 or greater than 4.0. If the playback speed is set to a value less than 0.5 or greater than 4.0, it should be set to the nearest valid value (0.5 or 4.0)
    • advancePlaybackTime: When playing, advance playback according to the audiobook's playback speed. The parameter of this method is the amount of real time that has passed and the playback time should advance by this amount times the playback speed. If playback reaches or passes the end of the book, cap playback time at the total length and mark the audiobook as finished. Note that the duration of the book is the sum of the duration of all its chapters. This method must override the advancePlaybackTime method inherited from the Media class
    • getCurrentChapterName: Return the name of the chapter currently being played, based on playback position and chapter lengths. If the book is finished, return the name of the last chapter. You may assume the book has at least 1 chapter (in your tests, always give your test books at least 1 chapter)
    • getTitle: Return a title that reflects both the current chapter and the book title. The format should be currentChapterName - bookTitle. That is a space, a dash, then another space ( - ) between the chapter name and book title. This method must override the getTitle method inherited from the Media class
  • Playlist (Testing: 5 points, Implementation: 5 points): Create a class in the problem package named Playlist. This class should implement the following methods:
    • Constructor: There is no required constructor for this class. If you write a constructor, it should be public and take no parameters
    • populatePlaylist: This method takes an ArrayList of Songs and an ArrayList of Audiobooks and should add all songs and audiobooks to the playlist
    • getMediaSortedByTitle: Return a new ArrayList of Media containing every item in this playlist, sorted by each item's getTitle() value. Comparisons should be case-insensitive (sort alphabetically ignoring capitalization)
    • You have seen several examples of sorting in lecture. You must use one of these approaches to sort the values of the playlist

The last part of this problem set is to complete static methods in the problem.ProblemSet3 class, all of which are related to binary trees.

  • maxBST (Testing: 5 points, Implementation: 5 points): In the problem.ProblemSet3 class, complete the maxBST method, which takes a BST of Integers and returns an int. This method returns the maximum value in the BST according to that BST's Comparator
    • "Maximum", in this context, means the value that would appear last if all values were sorted using that Comparator. It is not necessarily the largest numeric value in the tree
    • If the BST is empty (the root is null), return 0
  • maxBinaryTree (5 points. No testing required): In the problem.ProblemSet3 class, complete the maxBinaryTree method, which takes a BinaryTreeNode of Integers and an Integer Comparator, and returns an int. This method returns the maximum value in the binary tree rooted at the given node, according to the comparator
    • Note: The tree is not necessarily a BST
    • If the tree is empty (the root is null), return 0
  • isBST (5 points. No testing required): In the problem.ProblemSet3 class, complete the isBST method, which takes a BinaryTreeNode of Integers and an Integer Comparator, and returns a boolean. Return true if the tree rooted at the given node is a valid BST under that comparator, and false otherwise
    • You may assume no duplicate values, according to the comparator, appear in the tree
    • An empty tree is a valid BST

Testing Requirements

Write tests for the parts of the specification described below in the tests.TestProblemSet3 class. You are encouraged to write tests before you implement each part. If a test fails, use the debugger to find and fix your bug.

  • Song
    • Write tests for the Song.advancePlaybackTime method. Your tests should fail on the buggy starter implementation, and on any implementation that does not match all the expected behavior
    • You do not need to test the other methods in the Song class that were provided in the handout code
  • Chapter
    • Write tests for your Chapter class. Your tests should cover construction, getters, and setters so that chapter name and duration behave as expected
  • Audiobook
    • Write tests for the Audiobook class. Your tests should cover all the behavior described in the specification
  • Playlist
    • Write tests for the Playlist class. Your tests should cover all the behavior described in the specification
  • maxBST
    • Write tests for the maxBST method. Test that the proper value is returned in a variety of cases
    • When testing this method, you will need to create BST objects. You can use any/all of the provided Integer Comparators to create these BSTs
  • maxBinaryTree and isBST
    • Tests for these methods are provided for you. You do not need to write any additional tests for these methods. You can and should study these tests to help you write your maxBST tests

Programming Requirements

Implement the methods and classes from the specification.

You are encouraged to complete the Testing Requirements before you begin implementation so you can run your tests as you implement each part.


Autolab Feedback

With testing now being required, feedback from Autolab will be given in several phases.

  1. Running your tests on a correct solution
    • Your tests will be run against a solution that is known to be correct. If your tests do not pass this correct solution, there is an error somewhere in your tests that must be fixed before you can move on with the assignment. If your tests don't get past this check, you should re-read this document and make sure you implemented your tests and code according to the specification. You should also make sure that if there are multiple correct outputs to the input in your test cases that you accept any of the outputs as correct
    • Note: If you fail this phase, you will not be able to move on to the next phase
  2. Checking your tests for feature coverage
    • The next phase is to check if your tests check for a variety of features defined by different inputs. You should write at least one test case for each feature to pass this phase
    • Passing this phase does not necessarily mean that your testing is completely thorough. Satisfying Autolab is the bare minimum testing requirement. Not all possible inputs are checked and it is sometimes possible to pass this phase with weak testing. If you are struggling to earn credit for code that you believe is correct, you should write more than the required tests
  3. Running Autolab's tests on your submission
    • If your testing is thorough, and your code passes your tests, then you should pass this phase. If you pass your tests, but fail one of Autolab's tests, it is an indicator that you should write more tests to help expose your bug