Optional: Either attend a discussion section or work through the discussion section worksheet on building IntList code.
For this problem, we'll define a new data structure, the DoubleChain. A DoubleChain is defined as either the empty DoubleChain (represented by null in Java) or a triple containing:
You will be implementing this data structure as a DoubleChain class, using the IntList class as a guide. Your class should provide all three elements of the triple as public variables (we'll learn later that this is bad style, but let's accept this for now). Your class should also support the following public methods:
| Modifier and Type | Method and Description |
|---|---|
static DoubleChain |
getBack(DoubleChain d)
Returns the back of a DoubleChain. The back of the DoubleChain is defined as the last non-null DoubleChain that you reach if you keep following d.next pointers. This operation is undefined for DoubleChains with loops.
|
static DoubleChain |
getFront(DoubleChain d)
Returns the front of a DoubleChain.
|
static void |
insertBack(DoubleChain d,
double val)
Inserts a value at the back of a DoubleChain.
|
static void |
insertFront(DoubleChain d,
double val)
Inserts a value at the front of a DoubleChain.
|
static String |
toString(DoubleChain d)
Returns a string representation of a DoubleChain.
|
A skeleton for TestDoubleChain has been provided for you containing a single test. There is no skeleton for DoubleChain.
This specific data structure is a bit odd, and is unlikely to be very useful in practice due to poor performance. However, it'll serve our purposes as a programming exercise, and we'll see in the coming weeks how it can be tweaked to be industrial strength.
Implement the constructor so that your DoubleChain passes the existing TestDoubleChain.testConstructor test.
Then add a properly commented skeleton for getBack, getFront, insertBack, and insertFront. Don't implement these yet. By skeleton code, I mean that you should only write the definitions of each method down, along with dummy return values as appropriate.
Write tests for the four methods you've just added but not implemented. Your initial impetus might be to write functions like testGetFront, but writing methods that test these basic functions in isolation will be tricky. Why? Because the constructor is only capable of creating a DoubleChain that contains a single value (i.e. the resulting prev and next DoubleChains are null). We could get around this by manually adding more DoubleChains with .prev, but this is going to result in ugly tests that might even be subject to bugs themselves. Strive for tests that are so simple that it's very unlikely they'll have bugs.
In short: remember that tests are only any good if they have a chance of saving you time.
Instead, I'd recommend writing a single test that covers basic functionality by using the insert and get methods. It's ok to intersperse assertEquals calls with insert/get calls.
Important note: The DoubleChain class does NOT provide an equals method. Therefore assertEquals(d1, d2) will not work if d1 and d2 are DoubleChains. You can still write convincing tests without this.
If you're not sure if your tests are good enough, you might consider having your TA or a lab assistant give them a look.
After implementing and running your tests, implement the insert and get methods so that they pass your tests. Do not implement the toString method yet.
Create a new file in your lab 2 directory (same directory as your .java files) with the name hello.txt. Inside that file, include the magic word of the day (MWotD), which should be written on the whiteboard somewhere. If there is no MWotD, tell your lab TA that they'd better put one up or rebellion is certain. You can also put whatever else you want in that file, perhaps a favorite haiku or invectives about monarchs living or dead -- it just has to include that one word.
Please don't submit a copy of /usr/share/lib/dict/words. You're right, this would be clever, but don't do it.
If you miss your lab, go to another one. You can also get credit for attendance by submiting before 2:00 PM on Wednesday.
Some day you'll have to read someone else's code. Or your own code from years ago, which is just as bad. Let's look into how it feels to debug such code using fancy debugging tools.
The provided ExponentialWindow class generates a sequence of values analagous to a discrete exponential window function and stores it in a DoubleChain.
The ExponentialWindow.genWindow(int N, double lambda) class generates an exponential window with 2N+1 points, with a peak value equal to 1, with decay rate equal to lambda, i.e. every move away from the center decays by a factor of 1/lambda.
For example, ExponentialWindow.genWindow(2, 4) would correspond to the sequence [0.0625, 0.25, 1, 0.25, 0.0625], though this information would be stored in a DoubleChain instead of an array.
ExponentialWindow and TestExponentialWindow have already been provided for you.
Run TestExponentialWindow, and you'll see that there is some kind of bug.
To diagnose this bug, we'll be using a debugging tool called gjdb. You can use this tool either from the command line or using Emacs. If you're using your own computer and haven't completed homesetup.README (or you're on a Windows machine), you should ssh into the instructional machines for this part.
For gjdb to work, it's important that your java files are compiled using the -g option. This happens automatically if you use make, but if you're compiling by hand or using some fancy tool, make sure that -g is enabled, e.g.
javac -g *.java
If you've been working on your local machine, but wish to work on the instructional machines for this part, you should the hw command to make sure your instructional account is up to date with your local machine. To do this, use the hw commit command from your personal machine to commit your files and hw checkout or hw update as appropriate from the instructional machine to get those committed files into your instructionl account. See the online documentation for the hw command for more information on how hw works.
To run gjdb from the command line, type:
gjdb TestExponentialWindow
To run gjdb from within Emacs, use the M-x gjdb command in Emacs. When asked to fill in the gjdb command, use gjdb TestExponentialWindow.
Once you've started gjdb, it'll prompt you using [-]
Let's start with perhaps the most important command:
[-] help
You'll see a ton of information, much more than we'll need today. You might find Paul's 61B-oriented gjdb documentation more helpful. Don't go reading all that now, though. We're just going to get a taste of gjdb in lab, and hope it inspires you to go learn more.
Let's now use the run command:
[-] run
Your program will run starting from the beginning, just like we always do using java. As before, we see that our program runs and an exception occurs due to a test failure.
One key feature in gjdb is the ability to set breakpoints. A breakpoint is a position in your code where execution will pause (instead of just running all the way to the end). While paused, gjdb gives you the ability to interrogate the state of your program.
Let's add a breakpoint to our file. Type the command below (Emacs will tab complete the name of the class if you don't want to type out TestExponentialWindow).
[-] break TestExponentialWindow.testGenWindow
And you should see Set BP [1] TestExponentialWindow.testGenWindow
Now type run, and say that you would indeed like to restart the program. gjdb will report Breakpoint 1: thread="main", TestExponentialWindow.testGenWindow(), line=38, bci=0 to let you know that execution has stopped at line 38 of your program. If you're using Emacs, your Window will split, and you'll get a nicely annotated view of your code with an arrow showing you exactly where line 38 is within the context of your code.
We can have gjdb run single lines of code at a time using either the step command or the next command. These lines have one crucial difference: If the line to be executed involves any method calls, then step will send us into that method to watch its execution, whereas if we use next will resolve the calls silently and then get us to the next line within the current context. Think of step as stepping INTO a method. In Emacs, the keyboard shortcut for step is F5 or C-c C-s. For next, it is F6 or C-c C-n. You can also just enter the s or n command instead of typing out step and next.
Let's use step. If you enter the step command (or just enter s for short), you'll see that gjdb executes a single line of code and takes us into the ExponentialWindow class.
One very handy command is print, or just p for short. Try typing p val, and you should get a Name unknown: val error. This is because we haven't defined val yet. Indeed, gjdb tells you that the next line that will execute is double val = 1.
Press s again and the line double val = 1 will execute. Now try p val and you should see: main[0] print val $1 = 1.0
This means that val is 1, just as we'd expect. The $1 is called a history variable. You can think of it is as a variable in the gjdb environment that is used only by gjdb. For example, we could now say print $1 + 5 and we'd get $2 = 6.0. For more, see the 61b gjdb documentation. These history variables will not be useful for us today.
We can also get a list of all local variables currently in use with the command, just in case you're curious about what else we could print using gjdb.
info locals
Let's get back to imminently useful stuff. We could use all of the things we've learned so far today to try and diagnose the problem by stepping carefully through the entire process and watching a bunch of variables, but in this case, there's a faster way.
Use run again, and agree to restart. This time, instead of stepping into the line DoubleChain ew = ExponentialWindow.genWindow(4, 2);, use next to step OVER the call to genWindow.
Try printing ew using print ew. You'll see that gjdb simply tells you that it's a DoubleChain -- not what we wanted. We could start inspecting the list by running commands like print ew.val, print ew.prev.val and so forth. But even better is to use the print/n command. Try it out with print/5 ew. This will print out ew, and then recursively go through each level up to 5 times. You'll end up getting a pretty readable picture of the entire DoubleChain.
From this output, figure out the bug in ExponentialWindow and fix it.
Try running TestExponentialWindow, and you should still get an error. Ah rats, someone really messed up -- there's a bug in TestExponentialWindow! Look carefully at the test and you'll hopefully find it. If not, try print/5ing ew again and comparing what you see to the comment in TestExponentialWindow.
If you don't compete this method before the end of lab, it's ok to submit what you have for full credit, though it's probably better if you finish it, just so you get the practice.
It's common practice to provide a toString method for custom classes. Ordinarily this method is not static, but we're not quite to the point where we want to build our own non-static methods yet.
In this final section of the lab, we'll build a toString method. Your method will convert the DoubleChain into a comma-separated list flanked b <[ on the left, and ]> on the right. For example, a DoubleChain consisting of the values 1.0, 2.1, 3.3, 4.6, and 5.2 (from front to back), would be converted by toString into:
<[1.0, 2.1, 3.3, 4.6, 5.2]>
As usual, add a testToString method in TestDoubleChain and verify that it fails. Then write the toString method. Feel free to create private helper methods to keep things organized. If it seems worth it to test any helper methods, it's ok to make them public to allow TestDoubleQueue to access them. As mentioned briefly in class, making a method public just allow it to be tested is not ideal, since it means we have to expose more of the implementation details. Sometime next week, we'll discuss an alternate way of testing that will avoid this problem of unnecessarily making things public.
You'll notice that make style will yell at you for having public variables and will say something about accessor methods. It is indeed bad style to leave member variables out in the open like this, but we haven't learned the right techniques to deal with this yet. The style checker will just have to accept our shamefulness.
If you'd like more practice, try implementing a deleteFront or deleteBack method.
For an added challenge, write a method deleteByIndex(int i) that deletes the ith item from the front.
For an even bigger challenge, write a method deleteByValue(double d) that deletes all items approximately equal to a given value.