Drawing App Project


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 extends MouseAdapter and adds an additional paint 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.


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 BufferedImages.
  • 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: 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.


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.