Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Implementation

Overview of files provided

We provide a graphic driver (visualizer) to help you test the individual methods. Run the Driver class once your project is loaded into VSCode.

· Driver: A tool to test your RisingTides implementation through a graphical user interface (GUI). You are free to use this driver to test all of your methods. Feel free to edit this class, as it is provided only to help you test. It is not submitted and/or graded

o (See green outline) To use the driver, pick a terrain file to load. When clicking “Load”, it will automatically call all of your methods. Whatever is displayed in red is what you returned for that method. 

o (See orange outline) Press “Go!” to get information for a particular configuration of inputs. There are four values you can input:

§ Water Height – The height of the water, which updates in the visualizer everytime.

§ Future Water Height – The future height of the water. Does not update the visualizer.

§ x (column) – coordinate for isFlooded() and heightAboveWater()

§ y (row) – coordinate for isFlooded() and heightAboveWater()

o (See red outline) You can hover over the visualization to get coordinates of your cursor’s current position. You can copy these coordinates down into the x (column) and y (row) textboxes to check your results for a specific cell on the terrain. Note that this is only accurate when there are no purple borders. If you see purple borders, please resize the window to ensure the coordinates you see are accurate. You will get a notice at the bottom of the window anytime the coordinates are inaccurate.

· 

o When running for the first time (if you have not implemented any code yet), each method will output an error message. Ensure each method has a return statement so that you have no errors.

o A known issue for reduced window sizes is the disappearance of the “Go!” button. If this occurs, extend the window for it to reappear. 

· GridLocation: This class represents a cell or a location on the 2-D array. It holds the row and column of a cell. Don’t edit or submit to Autolab.

· RisingTides: The RisingTides class contains all methods needed to construct the functioning visualizer and return any relevant information. Edit the empty methods with your solution, but DO NOT edit the provided ones or the method signatures of any method. This is the file you submit.

· RisingTidesVisualizer: Converts terrain heights to RGB colors to be displayed in the Driver. It is not submitted and/or graded.

· Terrain: Driver dependency, which contains the heights of terrain and the water sources. Don’t edit or submit to Autolab.

· TerrainLoader: Loads the provided .terrain files from locally or online. It is not submitted and/or graded.

· WeightedQuickUnionUF: Implementation of Weighted Quick-Union. Feel free to take a look at the method descriptions for a better understanding of Weighted Quick-Union! Don’t edit or submit to Autolab.

· Terrain Files: Inside the “terrains/” folder, you will find many .terrain (BayArea.terrain, CraterLake.terrain, etc.) files you can use for your testing. You can use all input files to test all methods. Each input file contains either a link (for larger files) or the heights locally. The first two lines of the file should be the number of rows and columns in the grid, respectively. The next line indicates how many water sources there are in the world. For each of those water sources, there are two more lines giving the row and column index of where that water source is. After that, there will be doubles representing the water heights with the number of rows and columns defined in the first two rows. Feel free to make your own input files, as they will not be submitted to Autolab.

RisingTides.java

· DO NOT add new import statements.

· DO NOT change any of the method’s signatures.

Variables:

· terrain: each cell in this 2D array represents the land height at that cell.

· sources: this array contains water sources. A GridLocation (x,y) is present in the array if there is a source of water at that location.

Methods to be implemented by you:

1. elevationExtrema

· This method iterates through the terrain 2D array and finds the lowest and highest point. 

· The method returns a double array consisting of 2 elements:

o the first index containing the lowest (minimum) point.

o the second index containing the highest (maximum) point.

· Submit RisingTides.java with this method completed under Early Submission to receive extra credit.

This is the expected output for BayArea.terrain. You can see this information below the map.

2. floodedRegionsIn

This method simulates the rise in sea levels in the visualizer. The height parameter represents the flood water height.

To complete this method, you will need to implement the breadth-first search algorithm, or more specifically, the flood fill algorithm. We will go over this algorithm in detail when we go over graphs. 

Here is how it works:

1. Initialize a boolean 2D array, we will call this array the resulting array.

2. Initialize an ArrayList of GridLocations.

3. Add all of the water source GridLocations to the ArrayList. Flood these source GridLocations.

o Flood a certain GridLocation by marking it as true in the resulting array.

4. Repeat until the ArrayList is empty.

0. Remove the first element from the ArrayList and check all of its neighbors in each of the four cardinal directions.

1. If any of the neighbors’ height is less than or equal to the provided height parameter, flood the neighbor and add it to the end of the ArrayList. (Note: There may be cases where all 4 neighbors are flooded.)

5. Return the resulting array .

Note: Complete this method before the rest of the methods below. It is easier to implement those methods once this one is complete.

This is the expected output for BayArea.terrain at the water height of 0 meters above the current sea level.

3. isFlooded

This method checks if a GridLocation (cell parameter) is flooded when a flood at a specific water height (height parameter) occurs.

The method returns true if the GridLocation is flooded or false otherwise.

Note 1: the x-coordinate is the column, and the y-coordinate is the row.

Note 2: Use the floodedRegionsIn method to implement this method.

This is the expected output for BayArea.terrain at the water height of 0 meters above the current sea level and coordinates (0, 0).

4. heightAboveWater

This method calculates and returns how much of a GridLocation (cell parameter) is visible above the water height (height parameter).

To calculate the visible land compute the difference between the GridLocation land height and water height.

· If the return value is negative, the Driver will display “meters below”.

· If the return value is positive, the Driver will display “meters above”.

· The value displayed is always positive.

Note: recall that the terrain array contains the land height at each cell.

This is the expected output for BayArea.terrain at the water height of 0 meters above the current sea level and coordinates (0, 0).

5. totalVisibleLand

This method calculates the total number of visible land (cells), that is not underwater, given a certain water height (height parameter). Note: you may want to use the floodedRegionsIn method to implement this method. Return the number of GridLocations where the cell is not flooded (below water level). This is the expected output for BayArea.terrain at the water height of 0 meters above the current sea level.

6. landLost

This method calculates the amount of land that will be lost in the future if the water rises. 

Calculate the difference in the land available currently and in the future, given the current (height parameter) and future water heights (newHeight parameter), respectively.

· If the return value is negative, the Driver will display “Will gain”.

· If the return value is positive, the Driver will display “Will lose”.

· The value displayed will always be positive.

Note: you may want to use totalVisibleLand method to implement this method.

This is the expected output for BayArea.terrain at a water height of 0 (zero) meters above the current sea level and a future water height of 10 meters.

7. numOfIslands

This method computes and returns the total number of islands on the terrain at a certain water height (height parameter).

Parts of the terrain are considered “islands” if they are completely surrounded by water in all 8-directions.

If there were two pieces of land connected by one cell (ie. left corner) they would form one island. Only if this connection were to be removed (the height of water increased) we consider these two pieces of land two separate islands.

Recall that Union-Find keeps track of connected components. In the algorithm, Weighted Quick-Union UF, each island (connected component) is a tree. The island’s representative is the root of the tree.

· To connect two cells, use the union method.

· To find the root of the tree (island) a cell belongs to, use the find method.

· To find the number of islands, count the number of unique roots of trees.

This is the expected output for BayArea.terrain at the water height of 0 meters above the current sea level.

Still don’t understand how Union-Find works?

Here is a visualization using a 16×16 grid with two islands:

· one island is formed by cells: 21, 22, 23, 24, 36, 37, 38, 39, 40, 41, 53, 54, 55, 56, 57, 70, 71

· the other island is formed by cells: 139, 140, 153, 154,155, 156, 157, 158, 159, 169, 170, 173, 174, 175, 184, 185, 186, 187, 189, 190, 191, 200, 201, 202, 206, 217, 218, 219, 220 221, 222, 235, 236, 237.

The Weighted Union-Find algorithm will enable the detection that there are two islands. Here is how it works:

1. Start by setting each cell’s parent to itself.

Note: the numbers on the grid are the cell’s parent cell number.

Union every land cell to any neighboring land cell.

2. Consider each cell individually. In this example, when we consider cell 21, and check all of its neighbors (all 8 directions!)

· Since 22, 36, 37, and 38 are neighboring cells that are not flooded, we union (connect) them.

Once we are done with inspecting all cells from the first island:

· All cells neighboring 21 will have cell 21 as their parent.

Once we are done with inspecting all cells on the entire terrain.

Now that we have all of the connected terrains unioned, find the unique nodes!

· Iterate through the terrain once again.

· For every node that isn’t flooded

o Find its root node and check if that root node is already accounted for.

o If it is not accounted for, increment a counter.

o If it is accounted for, skip it and continue on.

· Once you are done iterating through the grid, the counter contains the number of islands there are!

Result for example above – accounted nodes: [ 21, 139 ]

Thus, for this example, our result would be 2.

Now that you understand Union-Find conceptually, take a look at the WeightedQuickUnionUF.java file to better understand how to implement it!

See how BayArea.terrain looks at various water heights!

Get Started Testing

Here we are providing you some testcases for you test to ensure your code works! You are not limited to these testcases only, so ensure your code is robust and can handle any edgecases thrown at it!

Implementation Notes

· YOU MAY only update the methods elevationExtrema(), floodedRegionsIn(), isFlooded(), heightAboveWater(), totalVisibleLand(), landLost(), and numberOfIslands().

· COMMENT all printing statements from RisingTides.java

· DO NOT add any instance variables to the Board class.

· DO NOT add any public methods to the Board class.

· DO NOT add/rename the project or package statements.

· DO NOT change the class Board name.

· YOU MAY add private methods to the RisingTides class.

· YOU MAY use any of the libraries provided in the zip file.

· DO NOT use System.exit()

VSCode Extensions

You can install VSCode extension packs for Java. Take a look at this tutorial. We suggest:

· Extension Pack for Java

· Project Manager for Java

· Debugger for Java

Importing VSCode Project

1. Download RisingTides.zip from Autolab Attachments.

2. Unzip the file by double clicking.

3. Open VSCode

o Import the folder to a workspace through File > Open

Executing and Debugging

· You can run your program through VSCode or you can use the Terminal to compile and execute. We suggest running through VSCode because it will give you the option to debug.

· How to debug your code

· If you choose the Terminal:

o first navigate to RisingTides directory/folder

§ to compile:  javac -d bin src/tides/*.java

§ to execute: java -cp bin tides.Driver

Before submission

COMMENT all printing statements from RisingTides.java

Collaboration policy. Read our collaboration policy here.

Submitting the assignment. Submit RisingTides.java separately via the web submission system called Autolab. To do this, click the Assignments link from the course website; click the Submit link for that assignment.