Lab 4: Linked Liszt

This week’s lab explores a fundamental data structure in computer science: the singly linked list. You will implement a SinglyLinkedList class using the supplied IList interface. Next, you will build a small music player application called LinkedLiszt that uses your SinglyLinkedList class to read in and play a musical score.

Partner Lab

This is a partner lab. You may work with one other person of your choosing, or if you are looking for an extra challenge you may work entirely by yourself. Although you are permitted to jointly develop code with your partner, each of you must independently submit your code. No copying of code is permitted. You must independently retype any code you develop with your partner.

Indicate your partnering arrangement (including those flying solo) by filling out the following form.

If you want to find a partner, please use Piazza’s Search for Teammates feature.

Lab Assignment

Goal. To gain a deep understanding of singly linked lists.

You are strongly encouraged to read the background on singly linked lists before proceeding. Note that there are many implementation approaches to singly linked lists. When grading this assignment, we will assume that you adopt the approach we describe in the background reading above.

You must complete the following three steps below. Note that there are additional bonus opportunities at the end of this writeup if you want an additional challenge.

Step 1: Implement the SinglyLinkedList class

Your starter code comes with a general interface for lists, called IList<E>, and an empty class called SinglyLinkedList<E>. Observe that both the abstract interface and the concrete class are generic, meaning that lists are intended to be able to store any kind of data.

Step 1 is to implement all of the methods in the SinglyLinkedList<E> class. You should not change any of the method signatures. If it is not obvious to you which methods you need to modify, look for the // TODO comments.

You are strongly encouraged to test your code as you complete each method. To do so, add a main method to the SinglyLinkedList.java file. Write test code in the main method to test your code as needed.

Note that the IList<E> interface contains many more methods than is described in the background material above. You should refer to that background material as needed, but you will need to read each method’s Javadoc comments to know what is expected.

Step 2: Add Assert.pre and Assert.post

Observe that the Javadocs for each method state the method’s pre- and post-conditions using the @pre and @post fields. You should add an Assert.pre check for every @pre comment. You should try to add an Assert.post check for every @post comment, although you will likely discover that it is not always possible to capture the post-condition in a simple test. Do your best to supply Assert.post checks, but it is OK if you can’t come up with all of them.

Step 3: Implement the LinkedLiszt class

The LinkedLiszt class is responsible for

  • reading a music (.mus) file from a user-supplied path,
  • creating a Note object for every line of the given file,
  • inserting Notes into a SinglyLinkedList<Note>, and finally,
  • calling the Note.play with the SinglyLinkedList<Note> to play the music.

There are two methods that must be implemented, although you are strongly encouraged to create additional helper methods to keep your methods short and readable. Those two methods are:

  • the main method, and
  • the loadScoreFromFile method.

Step 3, part 1: the main method

The main method should allow the user to run the program with the following form:

$ java LinkedLiszt <file.mus>

For example, to play the file mario.mus found in the scores folder, run

$ java LinkedLiszt scores/mario.mus

If the user runs the program with no arguments,

$ java LinkedLiszt

the program should print

Usage: java LinkedLiszt <score>

and terminate.

Step 3, part 2: the loadScoreFromFile method

The loadScoreFromFile method is responsible for loading a music file into a SinglyLinkedList<Note>. Your main method should call the loadScoreFromFile, and then pass the resulting linked list to the static play method found in the Note class.

You will need to use the Scanner class to read the given file. Refer to the Scanner handout for details.

The format of the .mus score files that you need to process is documented at the top of the LinkedLiszt class. Each note in a score file must be converted into a Note. Carefully read the documentation in the Note class to understand how to process the data. You should not alter the Note class in any way.

Here is a sample score file:

# my favorite score
E5 1/8 100
E5 1/8 100
rest 1/8 100
E5 1/8 100
rest 1/8 100
C5 1/8 100
E5 1/4 100
G5 1/4 100
rest 1/4 100
G4 1/4 100
rest 1/4 100
...

Observe that each line is either a whitespace-delimited three-tuple or a comment. Comment lines start with a # character and can be ignored.

There are multiple approaches you might use to read a score. Recall that the Scanner class contains input conversion routines to convert from Strings to ints, and Scanner can also process the components of a line individually. However, you may also use the String.split and Integer.valueOf methods if you prefer to process lines manually. Since all of these approaches will need to handle errors, we discuss error handling below.

Step 3, part 3: handling errors

There are many opportunities for errors to occur during the processing of a score file. Remember that it is impolite for programs to crash. Instead, when an error is detected, you should print out an error message using System.err.println and then terminate the program using System.exit(1).

Here is a non-exhaustive list of some of the errors you may encounter and should anticipate:

  • The file supplied by the user may not exist or may not be readable.
  • The file supplied by the user may not a .mus file.
  • The file is a .mus file but contains malformed data.

Style

As usual, we will be checking for good code style. We will be checking that you follow the same style guidelines we’ve introduced in the past. This section describes some additional guidelines that we’d like you to follow.

Requirement: checkstyle

This week, we are expanding checkstyle to encourage you to write modular and reusable code.

Rule: Don’t Repeat Yourself (DRY)

As a programmer, you should never type the same code over and over again. That would be a waste of your time. The ability to copy/paste useful code makes this tempting, but it is a bad practice! When you copy code, you copy errors. If you ever fix those errors, you have to remember to fix them in every location. This “fixing” rarely happens. Trust us. We’ve been there. We’re not really any smarter than you, we’ve just made all the mistakes already.

So what should you do instead? Write a helper method! Whenever you find yourself writing the same code more than once (it could be a common loop, searching a data structure, computing an equation) you should refactor that code into a method. Then you can call that method many times, but only ever have to fix bugs in one place.

Similarly, if you find yourselves writing a function that is very long, that is problematic. The long function can probably be broken into smaller parts that can then be composed to solve a larger problem. As a bonus, you can now reuse those parts to solve other problems.

Breaking long functions into byte-size chunks also has the benefit of making your code easier to read and debug. By isolating functionality inside independent units, you can convince yourself that each of those units is correct in isolation. Then, to reason about the entire program, you only need to convince yourself that the combination of those correct units is correct.

What checkstyle looks for

Since checkstyle does not directly check for copy/pasted code, we instead encourage concise methods.

The checkstyle tool will report an [ERROR] if your program has a method that is more than 30 lines long (excluding whitespace and single-line comments). This new rule is in addition to previous style requirements.

In total, checkstyle will enforce the following guidelines:

  • All class variables that are not final must be declared private or protected (i.e., no public member variables unless they are constants).
  • All public methods must include a “Javadoc” comment (starts with /** and ends with */; it should include descriptions of the function, the arguments, and any pre/post conditions).
  • No method should be longer than 40 lines (exluding whitespace and single-line comments).

To run checkstyle, type the following command at the terminal:

$ ./checkstyle

The ./ is peculiar to Unix: it tells the terminal to look for the checkstyle program in the current directory. This command runs checkstyle on every Java program in your directory. To run checkstyle on a specific Java file, type:

$ ./checkstyle SomeFile.java

Requirement: javac

In addition to checkstyle, we will enforce proper use of Java generics.

  • Compiling your code with javac must not produce the following message:
    Note: YourProgram.java uses unchecked or unsafe operations.
    Note: Recompile with -Xlint:unchecked for details.

This message tells you how to get more information. Recompile your program as follows (replace with the appropriate file name):

$ javac -Xlint:unchecked YourProgram.java

The output will give you details about the issue.

To fix this problem, make sure that you specify type parameters for every generic class, both when declaring the variable’s type and when instantiating an object. For example, to create a Vector that stores Integer objects, one would type:

    Vector<Integer> intVec = new Vector<Integer>();

Lab Deliverables

For this lab, please submit the following:

lab04-linked-liszt/
    README.md
    IList.java
    LinkedLiszt.java
    Note.java
    SinglyLinkedList.java
    checkstyle

where LinkedLiszt.java and SinglyLinkedList.java should contain your well-documented source code.

Bonus opportunities

If you complete the above lab and want to try tackling more for bonus credit, here are some stretch goals you can try for bonus credit.

  • Write a new class called CompuLiszt that programmatically generates music and then plays it. The method you use for generating music is up to you, but a reasonable place to start is by utilizing java.util.Random.
  • Add an extra argument to the LinkedLiszt class that plays the score backward. If the user calls the program as usual, like 
    $ java LinkedLiszt score/mario.mus

    the music plays as usual, but if they call it like

    $ java LinkedLiszt score/mario.mus backward

    the music plays backward.

  • Find a score that you like and encode it as a .mus file. If we like it, we may include it in future versions of this lab :) Be sure to put a comment at the top that includes the title of the score, the composer (if you know), and your own name so that future CSCI 136 students will remember you for all eternity.

Note that we do not supply any formula for bonus credit. You should do them if you enjoyed this lab and are genuinely interested in extending your skillset. However, if you attempt a bonus (even if you do not complete it), we will make a note of it in our gradebook. Students who attempt bonuses (especially those who regularly attempt them) often receive a grade bump at the end of the semester.

  • CSCI 136, Spring 2023

CS136 webpage, spring 2023

Powered by Bootstrap 4 Github Pages