Lecture 22 - Using Linked Lists


As usual, create a directory to hold today's activities:

$ mkdir ~/cs170/labs/lab22
$ cd ~/cs170/labs/lab22

Mandelbrot Voting

Time to vote for your favorite Mandelbrot images from your fellow students. The winner will be at least posted on my door, if not posted out in the hallway as well. Good luck!


Class Invariants

Up to now, we have not been documenting the constructor for a particular class. This is because up to now there hasn't been much of a need to do so: all of our classes were specified simply for one program, and that one program alone. However, now our classes are going to be used in a lot of different projects. Documenting that constructor just became a lot more important. We will talk about class invariants, and how to document them properly.


Using Linked Lists

You should, by this point, have a fairly well functioning linked list object. Today, we are going to start looking at how and why you might use a linked list. One example of why you would use them is in the creation of a different class of data-structure, known as a Stack.


Lab Activity 1
Stacks

A Stack is known as a Last-In, First-Out (LIFO) data structure. That means that the data that was most recently added to the structure is the first and only thing that can be removed. In order to get to data that was added earlier to the stack, you have to remove all of the things that are above it. The interesting thing about stacks are that you have been implicity been using one, without even knowing it.

Details

First things first, you need to copy your LinkedList class into your current directory.

$ cd ~/cs170/labs/lab22
$ cp ~/cs170/labs/lab21/linked_list.py .

Create a new file called stack.py. In this file, you should define a class Stack, which will inherit your linked list class. You will need to import linked_list at the top of your file so that you can have access to your LinkedList class.

Your class must have the three key methods for a stack, plus two additional methods for testing purposes:

Make sure that your methods work appropriately. You should handle the special cases in pop and peek, when there is nothing currently in the stack by raise-ing a ValueError exception.

Example

>>> my_stack = Stack()
>>> my_stack.push(1)
>>> my_stack.push(2)
>>> my_stack.push(3)
>>> print(my_stack)
top -> 3 -> 2 -> 1 -> bottom
>>> print(my_stack.size())
3
>>> print(my_stack.pop())
3
>>> print(my_stack)
top -> 2 -> 1 -> bottom
>>> my_stack.pop()
>>> my_stack.pop()
>>> my_stack.pop()
Traceback (most recent call last):
  File "stack.py", line #
ValueError: No more elements in the stack.
>>> 

Hint

  • Your operations here are pretty straight forward. A majority of them you already have written, you just need to re-name them through the inheritance.

  • push is essentially append. To simplify your size computation, however, you should maintain a size attribute that increments with every push.

  • pop is really the only new method. You need to essentially remove the front element, and return the data from that element. To remove the front element, you just need to move the head reference. You just need to store the data in that node before you remove it, so that you can return it later. Don't forget to decrement your size attribute.

 

Challenge

You would be able to do the next portion of the lab pretty easily with just the built in python list. However, there is this notion of Abstract Data Types (ADTs). An ADT is simply an interface that the data type must follow to be representative of this type. We explicity followed the ADT for a Stack above. However, the built in python list does not explicitly follow the ADT.

Write a class class called StackList, which inherits the built in list class (notice the punctuation). This class should have the same methods as the linked list Stack class. The methods you use, however, will be different.


Lab Assignment 22
Paint Bucket

A very useful tool for a majority of paint programs is the paint bucket tool. The paint bucket tool allows the user to click on an enclosed area, and it fills that enclosed area with the current fill color. A very common way that this is accomplished is by using a stack to keep track of the locations of the image that need to be filled.

You are given a program that has a recursive method to solve the paint bucket problem. However, this program will crash if you select certain regions of the image to fill. This is because there are a lot of pixels to fill, and the recursion limiter of python prevents the program from running.

As it turns out, any recursive method can be rewritten using a stack. This is because Python uses a stack (referred to as the "call stack") to keep track of where in the program to return when the program finishes executing. The call stack also stores local variables of a method so that their values can be restored after a method call. What you will do today, is modify this program so that it uses a loop and a stack instead.

Details

The file paint_bucket.py (You will also need the file ovals.gif) contains a program that draws an image with several overlapping ovals. There are a lot of methods already defined for you. The method you are modifying is fill_region_loop. You should read over the Pre and Post conditions of the built in helper file carefully, so that you can understand how to use them effectively.

fill_region_loop will be using a stack in order to accomplish its goal.

Hint

  • You should initialize the stack with the coordinate the user clicked on. Then, while the stack is not empty, you pop the item off the top of the stack and process it. The processing portion is essentially the same: if the current pixel color is the color to fill, color it in. The only difference is that instead of making a recursive call, you will simply push all of the neighbor's coordinates onto the stack.

  • You should be able to use the size attribute of the stack to determine whether there are still elements in the stack to process. You could also use a try/except statement, but that is a less preferable way to accomplish this.

 

Challenge

Tk can load any ".gif" image directly onto the canvas. Find an image that is not a black and white image, and load it onto the canvas. Pick a region of this image, and modify the program that you can click on the region and color it in. Do you notice anything peculiar about this behavior?

This program relies on the pixel colors to be exactly the same in order to fill them in. However, in real images this property is extremely rare. Instead, we can use a process known as "fuzzing" in order to get around this.

Define a global parameter FUZZ_FACTOR which is some integer value that you can modify easily. For a decent start, choose a value 10. If the euclidean distance of the color of the current pixel and the color to fill is less than the fuzz factor, go ahead a fill that pixel in.


Submission

When you have finished, create a tar file of your lab22 directory. To create a tar file, execute the following commands:

cd ~/cs170/labs
tar czvf lab22.tgz lab22/

To submit your activity, go to cseval.roanoke.edu. You should see an available assignment called Lab Assignment 22. Make sure you include a header listing the authors of the file.


In-Class Notes


Last modified: Mon Mar 17 13:40:32 EDT 2014