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.
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 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
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
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
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.y. Do not use
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
y is 0, the largest allowable value of
tmpImage.getWidth(), and the largest allowable value of
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
Here is a brief overview of the classes in the application:
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 extends
MouseAdapterand adds an additional
paintmethod 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).
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.
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 stack
undo(): performs one undo operation
redo(): performs one redo operation
DrawingPanelController(): 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 copying
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 color
setDrawingColor(drawingColor): sets the current tool color
The class also contains four inner classes:
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
Submit only the
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.