Floodfill Application

Motivation

Floodfill is an problem that is well-solved recursively. It allows us an opportunity to think about the similarities and differences between creating a task for each sub-problem and joining all of your tasks with a single X10 style finish.

Further, we will harken back to this exercise later in the semester when we discuss determinism.

Background

In this studio, you will be using a parallel and recursive method to create an app that fills in a space with color, much like the paint bucket in GNU Image Manipulation Program.

Flood Fill

https://en.wikipedia.org/wiki/Flood_fill

X10

One finish to join them all.

Mistakes to Avoid

Warning: Do NOT use == to compare colors. Use Objects.equals(a,b).

Warning: Do NOT finish more than you need to

Sequential Implementation Increased Stack Size Requirement

For this project, if you decide to first build a sequential version, you will need to change your VM Arguments slightly. In addition to the normal argument that needs to be pasted in for every assignment, you need to add -Xss4m. This will increase the size of the call stack, essentially increasing the maximum depth of your recursion.

The Core Questions

• What are the tasks?
• What is the data?
• Is the data mutable?
• If so, how is it shared?

Code To Use

Optional

isPresent()

isEmpty()

get()

HsvImage

colorAtPixel(x,y)

setColorAtPixel(x,y,color)

Objects

Objects.equals(a,b)

Color

equals(other)

Code To Investigate and Implement

The class is composed of two methods: floodFill and floodFillKernel. The entire process in the kernel is triggered from the floodFill method. This is so that the kernel can run recursively and in parallel and the floodFill method can wrap the kernel in an all-inclusive finish.

The provided floodFill method need only be investigate and should remain unchanged.

public static void floodFill(X10 x10, HsvImage pixels, HsvColor fillColor, int x, int y)
		throws InterruptedException, ExecutionException {
	Optional<HsvColor> targetColorOpt = pixels.colorAtPixel(x, y);
	if (targetColorOpt.isPresent()) {
		HsvColor targetColor = targetColorOpt.get();
		if (Objects.equals(targetColor, fillColor)) {
			// pass
		} else {
			x10.void_finish(() -> {
				floodFillKernel(pixels, targetColor, fillColor, x, y);
			});
		}
	}
}

class:	FloodFiller.java
methods:	floodFillKernel
package:	floodfill.exercise
source folder:	student/src/main/java

Note: If the recursion ventures outside of the bounds of the mutable pixels, getColor() will return empty.

If a valid (present) color is returned, you should check if the color at the current pixel location pixel matches the targetColor (the color we wish to change). If it is, it should then replace the color with the fillColor and asynchronously call the method again to repeat the process for the surrounding pixels. The purpose of the assignment is to understand recursion and how to make it work in parallel.

method: floodFillKernel (parallel implementation required)

Note: Recall from lecture that the finish()/join() has been done in the already implemented floodFill(). This means you are free to void_fork() "like a drunken sailor," as it will all be finished by the function which called floodFillKernel().

Testing Your Solution

Visualization

class:	FloodFillApp.java	VIZ
package:	floodfill.viz
source folder:	student/src/main/java

Correctness

A test suite exists but is limited and not all that exciting.

class:	_FloodFillTestSuite.java
package:	floodfill.exercise
source folder:	testing/src/test/java

Pledge, Acknowledgments, Citations

file:

exercise-floodfill-pledge-acknowledgments-citations.txt

More info about the Honor Pledge