Introduction
In this programming assignment you will use a pair of stacks to implement undo and redo functionality for a simple drawing application. You will also use a stack to implement a fill tool.
Starter Code
Learning Objectives
After successfully completing this assignment you should be able to:
- Implement undo/redo operations using a pair of stacks.
- Implement a simple capacity-capped stack using either a singly or doubly-linked list.
- Implement a simple stack-based fill algorithm.
The Application
The application you are modifying is a simple drawing app. It has three tools: a pen tool, a line segment tool, and a rectangle tool. These have already been implemented.
The drawing code is contained in the pa2.DrawingPanelController
class. This class implements a simple drawing canvas controller that handles mouse clicks and drags on the drawing canvas (which is the DrawingPanel
class), and maintains and displays the current image. Images are stored as java.awt.image.BufferedImage
objects.
Currently a DrawingPanelController
stores only one image at a time in the bImage
member data. Whenever a tool has completed a modification, it updates the current image by calling the private updateImage
helper method, which takes a new image as a parameter. The starter code for this method simply makes a copy of the new image and replaces bImage
with the copy of the new image.
Task 1: Implement an edit stack
Your first task is to add a stack for storing the edit history for the image. Rather than storing a single bImage
representing the current image, you will want to store a stack of images representing every time the image has been edited. When a new edit is made (i.e. by a call to updateImage
), your code should push a copy of the current image onto the edit stack. You should remove all references to bImage
completely. The “current image” is simply whatever image is on the top of the edit stack.
Task 2: Implement undo/redo
Now that you have a history of all edits that were made, you need to extend the class with undo and redo functionality by implementing the undo()
and redo()
methods. This will require an additional stack for storing a back-log of redoes. Keep in mind that the first image on the edit stack is the initial blank image, so you should not pop the edit stack if it has only one item.
Task 3: Put a capacity on the Stack
Since our edit history stack is storing the entire image for every edit made, it will quickly start to use a significant amount of memory. To mitigate this problem, you are going to add a capacity to the LStack
class. Modify the constructor so that it takes (and stores) a capacity
value. Your stack should store only up to capacity number of items. If the capacity is reached, you still want to allow pushes onto the stack. To support this operation, then, you need to remove whatever is on the bottom of the stack. Modify the LStack
class to maintain this capacity. HINT: You can either do a $\Theta(capacity)$-time operation to remove the bottom of the stack, or (bonus) you can modify the LStack
to use a doubly-linked, rather than singly-linked list as its base data structure, which requires some minor edits to the Link
class.
Next modify your DrawingPanelController
so that it stores at most 15 of the user’s edits (note that this means a capacity of 16, since the initial, unedited image is pushed to the stack).
Task 4: Implementing fill
For this task you will implement the fillFromPoint
method of the FillTool
inner class defined in DrawingPanelController
. When the fill tool is active and the user clicks on a particular point in the image, the fill tool fills
in all neighboring pixels of the same color. When one of the neighboring pixels is colored, then its neighbors are also checked.
Here is an example of an image with a single rectangle:
Here is the image after the user selects the color blue, and then uses the fill tool to fill in the box by clicking somewhere inside the box:
You are to implement this method using a stack. Points are stored as java.awt.Point
objects. If you have a point p
, then you can access its x and y coordinates using p.x
and p.y
. Do not use p.getX()
or p.getY()
since the return type for these is double
and will cause you to have to add a lot of type-casting to your code.
To access a color at a particular (x, y)
location in the image, use tmpImage.getRGB(x, y)
. Note that this returns an integer value that represents a color. You can set the color to the currently selected draw color using tmpImage.setRGB(x, y, drawingColor.getRGB())
. Finally, if you want to compare two colors, say at pixel locations (x1, y1)
and (x2, y2)
, you can test for the same color using: tmpImage.getRGB(x1, y1) == tmpImage.getRGB(x2, y2)
.
A stack based algorithm is a good choice for implementing a fill. The basic idea is to keep a stack of points in the image that must be filled. Initially, we only know that the point startPoint
, which is the input parameter to fillFromPoint
needs to be filled. Thus, we start by adding startPoint
to the stack. We should also store the current color value at start point in a variable called originalColor
, since we only want to fill in pixels that have this color. Next, we are going to perform a loop, which continues until the stack of points that needs to be filled becomes empty. The basic idea is to pop whatever is currently on the top of the stack off, set its color to the fill color (drawingColor.getRGB()
), and then check to see whether the points to its north, south, east, and west need to be filled. In other words, if we just popped a point p
and set its color to drawingColor.getRGB()
, we next need to test whether the points at (p.x + 1, p.y)
, (p.x - 1, p.y)
, (p.x, p.y + 1)
, and (p.x, p.y - 1)
need to be colored (i.e. are the same color as originalColor
). If they do, then we add them to the stack. (One other technicality, we don’t want to add a point to the stack that is outside the bounds of the image. The smallest allowable value of x
and y
is 0, the largest allowable value of x
is tmpImage.getWidth()
, and the largest allowable value of y
is tmpImage.getHeight()
.)
Task 5: Providing JUnit Tests
Finally, you need to provide a JUnit test for the capacity-stack implementation LStack<E>
. It should test all of the methods in LStack
and get 100% problem coverage. Call this LStackTest.java
.
App overview
Here is a brief overview of the classes in the application:
Package pa2
:
DrawingApp.java
: The main method for the app.DrawingFrame.java
: The frame that sets up the toolbar of buttons and the main drawing canvas panel.DrawingPanel.java
: The actual drawing canvas.DrawingPanelController.java
: The controller for the canvas which creates and manages the internal image state and current tool. You will have to modify this to implement undo/redo and fill.DrawingTool.java
: An abstract class that is the super-class of all drawing tools. It extendsMouseAdapter
and adds an additionalpaint
method for painting to the user interface before image modifications have been committed to the edit stack (e.g. while the user is still trying to draw the box).
Package pa2.util
LStack.java
. The OpenDSA linked stack implementation. You will have to modify this to implement the capacity limit.Link.java
. The OpenDSA singly-linked list link node. You will have to modify this only if you implement capacity on the stack by moving to a doubly-liked list.Stack.java
. The OpenDSA stack ADT interface.
DrawingPanelController.java
The main class you will work with that you have not seen before is the DrawingPanelController
class. What follows is a brief overview of its methods. The methods you will need to modify are:
getCurrentImage()
: returns the top image in the edit stack.updateImage(image)
: pushes an image onto the edit stackundo()
: performs one undo operationredo()
: performs one redo operationDrawingPanelController()
: You will need to modify the constructor to initialize any member data you add.FillTool.fillFromPoint(startPoint)
: You will need to modify this to implement flood fill.
Methods you should not modify are:
copyImage(image)
: a convenience method for copyingBufferedImages
.init()
: this method creates the mouse listeners and initializes a few of the member data; it should be called once by the constructor.setToolType(toolType)
: switches which tool is currently active to one of the built-in types.setTool(tool)
: switches to a custom tool.initImage()
: creates the initial blank image.getDrawingColor()
: gets the current tool colorsetDrawingColor(drawingColor)
: sets the current tool color
The class also contains four inner classes: PenTool
, LineSegmentTool
, RectangleTool
, and FillTool
which process mouse inputs from the user and draw to the image. All of these tools make temporary modifications to the image that are not added to the stack until the user releases the mouse button. When the mouse button is released, the current image is added to the edit stack using updateStack
.
Submission
Submit only the DrawingPanelController.java
, LStack.java
, LStackTest.java
, and Link.java
files to web-cat.
The due date is Monday October 10 by 11:55 pm. The webcat submissions will open sometime on the week of Sept. 25.