Programming Task 5

Time Estimate: 6 hours
Jump to current week
Requirements

Project Structure

You will continue to add functionality to your existing project from the previous task. There is no new repository to clone.


Specification

In this task, you will implement the following specs.

  • The ratings.datastructures.BinaryTreeNode class that has been provided in the handout repo. An object of this type will be returned by one of your methods and will be tested in Autolab. Just like the LinkedListNode class, all these methods must exist and be named exactly as they are in the repo or there will be errors during grading. You may add additional methods to this class, but don't call those methods from your tests.

Create a Playlist class in the ratings package with the following functionality. This class will use a Binary Search Tree (BST) to store a playlist of Songs in sorted order. This class will have the following behavior:

  • A constructor that takes a Comparator of Songs
    • You will use this Comparator in a BST to sort the songs that are added to the playlist. You should create and initialize any instance variables you'll need when this constructor is called
    • Il comparatore deve essere memorizzato in una variabile di istanza di tipo array di comparatori
  • 'n Metode genaamd getSecondSong wat geen parameters neem nie en die teruggee tweede liedjie in die BST
  • A method named addSong that takes a reference to a Song and returns void
    • This method will add the song to the playlist by inserting it into a BST with the comparator from the constructor
    • Note: You are allowed to use the BST code provided in lecture
  • A method named getSongTree that takes no parameters and returns the BinaryTreeNode of Songs that is the root node of your BST. This method should be a getter with one line of code
  • A method named getFirstSong that takes no parameters and returns the first song in the BST
  • A method named getSongList that takes a BinaryTreeNode of Songs as a parameter and returns a LinkedListNode of Songs
    • This method traverses the tree from the parameter and returns all the songs in the tree in a Linked List in sorted order (Assuming the parameter is the root of a BST)
    • Os yw'r mewnbwn yn Null, dychwelwch nod newydd gyda gwerth null
    • Note: This method is expected to contain the majority of the difficulty of this task
    • It's recommended that you write the next method before this one
  • A method named getSongList that takes no parameters and returns a LinkedListNode of Songs
    • This method traverses your BST and returns all the Songs in the tree in a Linked List in sorted order
    • This method should be one line since you can call your other getSongList method with the root of your BST as the argument
    • This is the method that you will test in this task. You should write this method while writing the other getSongList method so you can run your tests and utilize the debugger while writing your code
    • The returned node will be the head of a linked list containing all the Songs that were added to your playlist in sorted order according to the comparator provided to the constructor
    • Example: If you provided a SongTitleComparator, the songs will be sorted alphabetically by title
    • Example: If you provided a SongBayesianRatingComparator, the songs will be sorted in decreasing order (The highest rated songs first) according to their bayesian average rating with 2 fake ratings of 3 being added
    • If no songs have been added to the Playlist, this method returns null to represent an empty linked list

Testing Utilities

TestDataStructures2: Create a class named TestDataStructures2 in the tests package and write the following testing utility method in this class.

  • compareSongTrees - Write a method named compareSongTrees in the tests.TestDataStructures2 class that:
    • Takes [references to] 2 arrays of BinaryTreeNode<Song> objects as parameters
    • Checks if all the songs in the two trees have the same exact title, artist, id, and ratings in the same positions in the tree. The method fails a JUnit assert if the trees do not contain all the same songs in the same positions

You'll have the need to compare 2 song objects throughout this method. Luckily, you already wrote, and tested, a compareSongs method that does this (You may want to add a call to your compareListsOfRatings to compare the ratings of the two songs since we did not have ratings where we wrote the compareSongs method). Since the method is in a different class and is non-static, you'll need to create a new TestClasses1 object and call your method through that object. Note that you do not have to import TestClasses1 since it's in the same package as TestDataStructures2

Note: You still have to create every class and method from the specification before getting feedback on your submission in Autolab since the grader will not be able to compile if those classes/methods do not exist. You don't have to implement them yet, and they can all return a default value


Testing Requirements

TestDataStructures2: Add tests to the TestDataStructures2 class in the tests package that will test the following functionality.

  • ratings.Playlist - Write tests for the following methods of the Playlist class
    • The constructor takes a Comparator<Song>. In your testing, you can pass either a new SongTitleComparator or a new SongBayesianRatingComparator. This is allowed through the magic of Polymorphism which we'll discuss in greater detail later in the semester
    • Call the addSong method to populate the playlist with test data
    • Write tests for the getSongTree method and assert that it returns a tree that contains all the songs in the correct places based on the comparator you provided in the constructor and the algorithm for inserting into a BST
      • Do not write tests where 2 of your songs are tied according to the comparator
      • If no songs have been added, this method returns null
      • You should use your utility method to make these tests easier to write
    • Write tests for the getSongList method that takes no parameters and assert that it returns a linked list of all the added songs in sorted order according to the comparator you provided in the constructor
      • Do not write tests where 2 of your songs are tied according to the comparator
      • If no songs have been added, this method returns null
      • The returned Songs might be different song objects, but they will contain the same title, artist, id, and ratings as the Songs that were added (eg. You must check the values of the songs and not rely on comparing the references with ==)
      • Note: You do not have to write tests for the getSongList method that takes a tree as a parameter, though it will be tested implicitly since the one you are testing should call the other

Programming Requirements

Implement all the classes/methods described in the Specification section. As you're writing this code, you should run your tests to see how you are progressing. It's recommended that you write your tests first, submit to Autolab to make sure you have good testing, then use those verified tests, along with the debugger, to check your code.


Autolab Feedback

The feedback in Autolab will be given in 4 phases. If you don't complete a phase, then feedback for the following phase(s) will not be provided.

  1. Testing your testing utility method
    • Your testing utility method will be checked with a variety of test cases to ensure that it makes all the required checks. This phase will ensure that your utility method is accurate before you start using it in your tests
  2. 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 the specification. You should also make sure that if there are multiple correct outputs to the input in your tests cases that you accept any of the outputs as correct
  3. 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
  4. Running my tests on your solution
    • Once Autolab is happy with your tests, it will run my tests against your code to check it for correctness. 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 mine, it is an indicator that you should write more tests to help expose your bug

Once you complete all 4 phases, you will have completed this Task and Autolab will confirm this with a score of 1.0 for complete.