Difference between revisions of "Floodfill Application"

From CSE231 Wiki
Jump to navigation Jump to search
 
(49 intermediate revisions by 5 users not shown)
Line 1: Line 1:
 +
=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=
 
=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 [https://www.gimp.org/ GNU Image Manipulation Program].
 +
==Flood Fill==
 +
<youtube>hoVbNF8CpBk</youtube>
 +
 +
[[File:FloodFillTool.png]]
 +
[[File:FloodFillShape.png]]
 +
 +
https://en.wikipedia.org/wiki/Flood_fill
 +
 +
==X10==
 +
 +
One [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/x10/X10.html#finish(fj.api.TaskSupplier) finish] to join them all.
 +
 +
<youtube>dJJiMLPHGgg</youtube>
 +
 +
=Mistakes to Avoid=
 +
{{Warning | Do NOT use <nowiki>==</nowiki>  to compare colors.  Use [https://docs.oracle.com/javase/8/docs/api/java/util/Objects.html#equals-java.lang.Object-java.lang.Object- 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 <code>-Xss4m</code>.  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=
 +
[https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/Optional.html Optional]
 +
:[https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/Optional.html#isPresent() isPresent()]
 +
:[https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/Optional.html#isEmpty() isEmpty()]
 +
:[https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/Optional.html#get() get()]
 +
 +
[https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/edu/wustl/cse231s/image/HsvImage.html HsvImage]
 +
:[https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/edu/wustl/cse231s/image/HsvImage.html#colorAtPixel(int,int) colorAtPixel(x,y)]
 +
:[https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/edu/wustl/cse231s/image/HsvImage.html#setColorAtPixel(int,int,edu.wustl.cse231s.color.HsvColor) setColorAtPixel(x,y,color)]
 +
 +
[https://docs.oracle.com/javase/8/docs/api/java/util/Objects.html Objects]
 +
:[https://docs.oracle.com/javase/8/docs/api/java/util/Objects.html#equals-java.lang.Object-java.lang.Object- Objects.equals(a,b)]
  
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 MS Paint.
+
[https://docs.oracle.com/javase/8/docs/api/java/awt/Color.html Color]
 +
:[https://docs.oracle.com/javase/8/docs/api/java/awt/Color.html#equals-java.lang.Object- equals(other)]
  
=Setup=
+
=Code To Investigate and Implement=
In order to run the visualization app you will need to [http://www.cse.wustl.edu/~cosgroved/courses/cse231/s17/setup/JavaFX.html setup e(fx)clipse].
+
The class is composed of two methods: [https://www.cse.wustl.edu/~dennis.cosgrove/courses/cse231/current/apidocs/floodfill/exercise/FloodFiller.html#floodFill(x10.X10,edu.wustl.cse231s.pixel.MutablePixels,java.awt.Color,int,int) 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.
  
=Where to Start=
+
The provided floodFill method need only be investigate and should remain unchanged.
  
In order to test this application, please refer to the <code>floodfill.viz</code> package in the <code>src/visualization/java</code> folder. More specifically, check out the <code>FloodFillVizApp.java</code> class. Otherwise, the only class you will need to modify is <code>FloodFiller.java</code>, which can be found int the <code>floodfill.studio</code> package in the <code>src/main/java</code> folder.
 
  
There is also an albeit limited test suite <code>FloodFillTestSuite</code>.
+
<syntaxhighlight lang="java">
==The Kernel==
+
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);
 +
});
 +
}
 +
}
 +
}
 +
</syntaxhighlight>
  
The class is composed of two methods: floodFill and floodFillKernel. As you will be implementing FloodFill recursively and in parallel.  Carefully consider where to put your asyncs and/or finishes.  The entire process in the kernel is triggered from the floodFill method. This is so that the kernel can run recursively and asynchronously so the floodFill method can wrap the kernel in an all-inclusive finish.
+
{{CodeToImplement|FloodFiller|floodFillKernel|floodfill.exercise}}
  
The kernel should check if the given pixel is in bounds. If it is, it should check if the given pixel matches the targetColor (the color we wish to change). If it is, it should then replace the color with the replacementColor 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.
+
Note: If the recursion ventures outside of the bounds of the mutable pixels, getColor() will return empty.  
  
==Sequential Implementation Increased Stack Size Requirement==
+
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.
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 <code>-Xss4m</code>. Altogether, it will look something like:
+
 
<code>-javaagent:"path\to\hjlib-cooperative-0.1.14-SNAPSHOT.jar" -Xss4m</code>. This will increase the size of the call stack, essentially increasing the maximum depth of your recursion.
+
{{Parallel|floodFillKernel}}
 +
 
 +
'''Note: ''' Recall from lecture that the finish()/join() has been done in the already implemented <code> floodFill()</code>. This means you are free to void_fork() "like a drunken sailor," as it will all be finished by the function which called <code> floodFillKernel()</code>.
 +
 
 +
=Testing Your Solution=
 +
==Visualization==
 +
[[File:FloodFillViz.png]]
 +
 
 +
{{Viz|FloodFillApp|floodfill.viz|main}}
 +
 
 +
==Correctness==
 +
A test suite exists but is limited and not all that exciting.
 +
{{TestSuite|_FloodFillTestSuite|floodfill.exercise}}
  
==References==
+
=Pledge, Acknowledgments, Citations=
https://en.wikipedia.org/wiki/Flood_fill
+
{{Pledge|exercise-floodfill}}

Latest revision as of 05:08, 25 February 2024

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

FloodFillTool.png FloodFillShape.png

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

X10

One finish to join them all.

Mistakes to Avoid

Attention niels epting.svg Warning: Do NOT use == to compare colors. Use Objects.equals(a,b).
Attention niels epting.svg 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 Java.png
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.svg (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

FloodFillViz.png

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 Junit.png
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