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()

MutablePixels

getColor(x,y)

setColor(x,y,color)

Objects

Objects.equals(a,b)

Color

equals(other)

Code To Implement

The class is composed of two methods: floodFill and floodFillKernel. The entire process in the kernel is triggered from the floodFill method.

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

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.

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)

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