CS 261 Lab F - Bead Necklaces
Due Wed Oct 08 at 3:00pm
Overview
In this assignment, you will practice using the "node and reference" structure of a LinkedList to model a necklace made up of beads of different sizes and colors. You will write a Necklace class to model this necklace as a kind of linked list of Bead objects. Your necklace will need to keep Beads organized in order (based on a provided palette's rainbow, with larger beads coming first). You should be able to add and remove Beads from the necklace while maintaining the order. An example screenshot is below:
This lab will be completed in pairs. Partner assignments for this lab can be found on Moodle
- Remember to review the pair programming guidelines before you get started!
Objectives
- To practice implementing Linked Lists and their relatives.
- To practice working with the
Comparable<E>
interface
Necessary Files
You will need to download the copy of the zipped source files. and import them into Eclipse. These files include:
- A
Bead.java
class, that provides the starting point for your Necklace. This class is like a specialized version of theNode
class we discussed in lecture. You will need to modify this class. - A
NecklaceFrame.java
class that will be used to display your necklace. You will not need to modify this class. -
A
Palette.java
class to produce and display a pleasing set of possible colors for your beads. You will not need to modify this class.- Skim through this class and look at its documentation for available methods!
-
A
Tester.java
that you can use to graphically help make sure your implementation works.- The provided tester does not test all of the required functionality of your program! You will need to write your own tests to make sure that things work. However, you can use this code as a starting point for writing your own tests.
- You should know if your code works when you turn in the assignment!
You may also find it useful to look at the lecture code (available on Moodle) from yesterday!
Lab Details
-
Read through the provided classes and make sure you're familiar with them. Note that they won't compile without the
Necklace
class you will need to create for the lab. You should start by making a skeleton of that class (with empty methods) so that everything can compile. -
The bulk of this assignment will be implementing the
Necklace
class. A necklace is basically a linked-list ofBeads
. Consider: will this be a generic class?- Beads will act as the "nodes" of your necklace--each bead has a "hook" that another bead can be hung on.
- Just like with a linked-List, you'll want a reference to the first bead (the head), as well as a size variable.
-
Your
Necklace
class must implement the following public interface (which I recommend you implement in order):-
public Necklace()
is the constructor that creates a new, empty necklace. This should initialize your instance variables. -
int size()
which does exactly what you expect. -
void addFirstBead(Bead)
adds the given bead to the front of the necklace.- Remember to update the size of the necklace!
-
Bead getBead(int)
which returns the bead at the appropriate index (which is used for iterating and drawing the list).- Once this method is written, you shoud be able to show the Necklace graphically!
-
void addLastBead(Bead)
adds the given bead to the end of the necklace. -
void addBead(Bead)
adds a bead to the necklace in order. Beads are ordered by color (you can use the Palette'sgetColorRank(Color)
method to get a "rank" for the color--rank 1 comes before rank 2 comes before rank 3). If two beads have the same color, then the larger bead should come first.-
Because we want to be able to put the Beads in order, it would be a good idea to add a way to compare them to see who comes before whom. You should modify the
Bead
class so that it implements theComparable<E>
interface. - Remember, generics can be tricky! Since you're actually implementing (using) the generic interface, does it still include a generic type, or do you get to specify what type Beads can be compared to?
- Test this code thoroughly! Create Beads with the same/different colors and sizes, and then compare them to see if your order is correct. A problem here can introduce difficult-to-trace bugs when adding the Bead.
-
Because we want to be able to put the Beads in order, it would be a good idea to add a way to compare them to see who comes before whom. You should modify the
-
Bead removeBead(Color)
removes a bead of the given color from the necklace. This can just be the first bead of that color (or the last bead of that color if you're feeling clever).- Be careful not to remove the rest of the necklace!
-
- Try to keep algorithmic efficiency in mind. For example, don't iterate ("walk") through your beads more often than you have to. That said: always make the code work first, then optimize later.
- Also, include plenty of inline comments explaining how your methods work. This will be very handy for tracing problems that may arise!
- Finally, please remember to fill out the Lab Partner Evaluation when you're done.
Submitting
Make sure both your names are on the LetterSet
class (you will be marked down if they are not). Once you're finished, upload the src code to the LabF submission folder on vhedwig. Only one partner needs to upload the code--we will only grade one partner's copy of the program. Make sure you upload your work to the correct folder! The lab is due at the start of class the day after lab.
After you have submitted your solution, log onto Moodle and submit the Lab F Partner Evaluation. Both partners need to submit evaluations.
Extensions
Try to make the bead prettier. Can you draw specular highlights on them? Give them a "shape" so we can have square beads, circular beads, polygon beads? Or even load an image to represent the bead? This is good GUI practice!
Grading
This assignment will be graded out of 17 points:
- [1pt] You have implemented the Necklace class with appropriate instance variables and Constructors
- [1pt] You have implemented the size() method, and the size is correctly tracked
- [1pt] You have implemented the addFirstBead() method
- [1pt] You have implemented the getBead() method
- [2pt] You have implemented the addLastBead() method
- [3pt] You have implemented the addBead() method, which adds beads in order
- [2pt] Your Bead class properly implements the
Comparable
interface - [2pt] Your Bead class orders beads by color, then by size
- [2pt] You have implemented the removeBead() method, which removes a bead of the appropriate color
- [1pt] Your methods show proper algorithmic efficiency (e.g., don't iterate when you don't have to)
- [1pt] You have completed your lab partner evaluation