$ mkdir ~/cs170/labs/lab22 $ cd ~/cs170/labs/lab22
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!
Up to now, 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.
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.
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.
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:
push - Takes data as a parameter, and
adds it to the top of the stack.
pop - Removes the node from the top of the stack,
and returns its data.
peek - Returns the data from the node on the top
of the stack without removing it.
size - Returns an integer, the number of items
currently in the stack.
__str__ - Returns a string representation of the
current format of the stack.
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.
>>> 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. >>>
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.
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.
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.
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.
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.
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 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.
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.
