we mentioned how a complete tree, or better yet, a full tree, can be managed very efficiently using an array rather than node objects. That's what we'll do in this part. In the NCAA Men's Basketball Tournament, 64 teams compete for one championship title. A bracket for such a tournament would logically be managed by a full tree data structure. Due to space constraints, we'll only manage a tournament of 8 College Basketball teams. For this part, I have provided the following 3 files:

Team.java

TournamentBracketApp.java

TournamentBracketManager.java

The TournamentBracketApp class has a main method that simply opens up a GUI, loads your tree with data concerning the 8 teams in the tournament, and handles user input. The GUI only has two buttons, one that produces random results weighted by team records for all tournament games and another for resetting the tournament.

In order for this to work you will manipulate the tree, which stores all of its data in an array similar to the technique we discussed in lecture. I have defined the initTeams method, which takes an array of Teams (size should be a power of 2), and places its contents into our tree-array, putting them into the indices representing the tree leaves. All parent nodes, including the root, start out storing null, the reason is we don't know who's going to win the tournament yet, only the teams entering, and based on the order they are given, who each team's opponent will be in the first round. You will have to write code that fills in the tournament bracket with results.

YOUR THREE METHODS, ONE IN THE TournamentBracketManager CLASS:

Define the runTournament method such that when called, it fills in the entire bracket with tournament results. Games should be determined simply by calling the playGame method, which is a weighted method for randomly selecting a winner in a game between two team arguments. Note that you should update the records of the teams as the tournament games are played.

HINT: Remember how we talked about pre, in, and post order traversal in a tree and the differences between them. Note that post order traversal means that parent node data is processed after its children's node data is processed. This seems a natural fit for this problem, since we can't compute the tournament winner until we know who has won in the previous rounds.

AND TWO IN THE BottomUpBracketIterator CLASS:

Define the hasNext method such that it aids in an Iterator's production of elements in the order of leaves to root.

Define the next method such that produces the nodes in the tree in the order of leaves to root (bottom-up).

Note that the BottomUpBracketIterator is being used for rendering. It needs to produce the elements in the correct order, left to right, bottom level frist, and should do so whether the tree has 8 teams, 64 teams, 128 teams, etc. You will have to think about this problem mathematically. Understand that you should probably add instance variables to your BottomUpBracketIterator class such that it knows which index is "next" (or current if you prefer). This stored index would then be used to produce elements when the next method is called. Be aware, of course, that elements are not being produced from the array from 0 thru length-1, but rather taking the tree structure into account, in the order of bottom nodes first, top nodes (like the root) last.

Here is my code.

package part2_array_tree;

/* * DO NOT CHANGE THIS CLASS * * This is just a dumb little class for CSE 214, HW 3. It stores * data for a team. It doesn't really do much. */ public class Team { private String name = "No Name"; private int wins = 0; private int losses = 0;

public Team(String initName, int initWins, int initLosses) { name = initName; wins = initWins; losses = initLosses; }

public String getName() { return name; }

public int getWins() { return wins; }

public int getLosses() { return losses; }

public void incWins() { wins++; }

public void incLosses() { losses++; }

public double calculateWinningPercentage() { return (double) wins / ((double) (wins + losses)); }

public String toString() { return name + " (" + wins + "-" + losses + ")"; } }

package part2_array_tree;

import java.util.Iterator; import javafx.application.Application; import javafx.geometry.Insets; import javafx.geometry.Rectangle2D; import javafx.scene.Scene; import javafx.scene.canvas.Canvas; import javafx.scene.canvas.GraphicsContext; import javafx.scene.control.Button; import javafx.scene.layout.Background; import javafx.scene.layout.BackgroundFill; import javafx.scene.layout.BorderPane; import javafx.scene.layout.CornerRadii; import javafx.scene.layout.HBox; import javafx.scene.layout.Pane; import javafx.scene.paint.Color; import javafx.scene.text.Font; import javafx.scene.text.FontWeight; import javafx.stage.Screen; import javafx.stage.Stage;

/* * DO NOT CHANGE THIS CLASS * * This class runs the GUI for your field of 8 basketball tournament. * */ public class TournamentBracketApp extends Application { // THE APP WINDOW private Stage window;

// THIS STORES AND MANIPULATES OUR TREE DATA private TournamentBracketManager treeManager = new TournamentBracketManager();

// THIS STORES ALL OUR GUI CONTROLS private BorderPane appPane = new BorderPane();

// GUI STUFF FOR THE TOP TOOLBAR private HBox topPane = new HBox(); private Button startTournamentButton = new Button("Start Tournament"); private Button clearResultsButton = new Button("Clear Results");

// WE'LL RENDER OUR TREE HERE private Canvas bracketCanvas = new Canvas();

/** * DO NOT CHANGE THIS METHOD * * Default Constructor, lays out the GUI and initializes the * tree with 8 teams. */ public void start(Stage primaryStage) { window = primaryStage; initWindow("Tournament Bracket App"); initGUI(); initTournamentTeams(); window.show(); }

// SIZES THE SETS UP THE WINDOW private void initWindow(String title) { window.setTitle(title); Scene scene = new Scene(appPane); window.setScene(scene); Screen screen = Screen.getPrimary(); Rectangle2D bounds = screen.getVisualBounds(); window.setX(bounds.getMinX()); window.setY(bounds.getMinY()); window.setWidth(bounds.getWidth()); window.setHeight(bounds.getHeight()); }

/** * DO NOT CHANGE THIS METHOD * * This method simply picks 8 college basketball teams to * include in our tournament. This array is given to the tree * manager. */ private void initTournamentTeams() { Team[] teams = new Team[8]; teams[0] = new Team("Kansas State", 25, 11); teams[1] = new Team("Loyola of Chicago", 31, 5); teams[2] = new Team("Florida State", 23, 11); teams[3] = new Team("Michigan", 31, 7); teams[4] = new Team("Villanova", 24, 4); teams[5] = new Team("Texas Tech", 27, 9); teams[6] = new Team("Kansas", 30, 7); teams[7] = new Team("Duke", 29, 7); treeManager.initTeams(teams); }

/** * DO NOT CHANGE THIS METHOD * * This method responds to user input to restart the tournament. */ private void startTournament() { initTournamentTeams(); treeManager.runTournament(); renderBracketCanvas(); } /** * DO NOT CHANGE THIS METHOD * * This method responds to user input to clear the tournament results. */ private void clearResults() { initTournamentTeams(); renderBracketCanvas(); }

/** * DO NOT CHANGE THIS METHOD * * This method lays out our GUI components. */ private void initGUI() { topPane.getChildren().add(startTournamentButton); topPane.getChildren().add(clearResultsButton); Pane canvasParent = new Pane(); canvasParent.getChildren().add(bracketCanvas); canvasParent.layoutBoundsProperty().addListener((ov, oldValue, newValue) -> { bracketCanvas.setWidth(newValue.getWidth()); bracketCanvas.setHeight(newValue.getHeight()); renderBracketCanvas(); }); appPane.setTop(topPane); appPane.setCenter(canvasParent); startTournamentButton.setOnAction(e->{startTournament();}); clearResultsButton.setOnAction(e->{clearResults();}); topPane.setBackground(new Background(new BackgroundFill(Color.BISQUE, CornerRadii.EMPTY, Insets.EMPTY))); Font buttonFont = Font.font("Serif", FontWeight.BOLD, 18); startTournamentButton.setFont(buttonFont); clearResultsButton.setFont(buttonFont); }

// RENDERING CONSTANTS static final int RECT_WIDTH = 250; static final int RECT_HEIGHT = 50;

// DO NOT CHANGE THIS FUNCTION, IT DRAWS OUR TOURNAMENT BRACKET private void renderBracketCanvas() { GraphicsContext g = bracketCanvas.getGraphicsContext2D(); double cWidth = bracketCanvas.getWidth(); double cHeight = bracketCanvas.getHeight(); g.clearRect(0, 0, cWidth, cHeight); g.setFont(new Font("Serif", 18));

if ((cWidth > 0) && (cHeight > 0)) { int numTeams = treeManager.getNumTeams(); Iterator it = treeManager.bottomUpBracketIterator(); int numLevels = treeManager.logBase2(numTeams); int level = numLevels; int counter = 0; int maxForRow = numTeams; int rectX, rectY;

// GO THROUGH AND RENDER ALL RESULTS while (it.hasNext()) { Team team = (Team) it.next(); int spacing = (int) (cHeight / Math.pow(2, level + 1)); rectX = 100 + (numLevels - level) * 200; rectY = (spacing + (spacing * 2 * counter)) - (RECT_HEIGHT / 2) + 30; g.strokeRect(rectX-10, rectY - RECT_HEIGHT + 15, RECT_WIDTH, RECT_HEIGHT); if (team != null) { String teamText = team.toString(); g.strokeText(teamText, rectX, rectY); } counter++; if (counter == maxForRow) { counter = 0; level--; maxForRow /= 2; } } } }

public static void main(String[] args) { launch(args); } }

package part2_array_tree;

import java.util.*;

/* * YOU MUST FILL IN THE CODE FOR THE FOLLOWING THREE METHODS: * - runTournament * - hasNext in the BottomUpIterator * - next in the BottomUpIterator * * This class uses an array to manage a full tree. */ public class TournamentBracketManager { // ALL OF OUR TREE DATA GOES IN THIS ARRAY. REMEMBER, WE // ARE NOT STORING SEQUENTIAL DATA. private Team[] bracket = null;

// THIS REPRESENTS THE NUMBER OF NODES IN THE LOWEST LEVEL // IT'S IMPORTANT FOR VARIOUS CALCULATIONS private int numTeams = 0;

/** * Default constructor, it does nothing */ public TournamentBracketManager() {}

/** * ACCESSOR METHOD */ public int getNumTeams() { return numTeams; }

/** * DO NOT CHANGE THIS METHOD * * This method is given the 8 teams participating in the * tournament and it places them in the correct locations * inside the array. */ public void initTeams(Team[] teams) { numTeams = teams.length; bracket = new Team[(numTeams * 2) - 1]; int bracketFirstTeamIndex = bracket.length - numTeams;

// ADD THE TEAMS for (int i = 0; i < teams.length; i++) { bracket[bracketFirstTeamIndex + i] = teams[i]; }

// THE REST OF THE NODES ARE NOT YET DETERMINED // SINCE WE HAVEN'T YET PLAYED THE GAMES for (int j = 0; j < bracketFirstTeamIndex; j++) { bracket[j] = null; } }

public int getIndexOfParentNode(int childIndex) { return (int) (Math.floor((childIndex - 1) / 2)); }

public int getIndexOfLeftChildNode(int parentIndex) { return (2 * parentIndex) + 1; }

public int getIndexOfRightChildNode(int parentIndex) { return (2 * parentIndex) + 2; }

/** * YOU MUST DEFINE THIE METHOD * * This method should walk the tree and use the playGame to * determine winners in all games. It should then fill in the * bracket with this data. * * NOTE: You'll need helper methods for this one. */ public void runTournament() { // ADD YOUR CODE HERE }

/** * DO NOT CHANGE THIS METHOD (UNLESS YOU REALLY WANT TO) * * This method takes 2 constructed team objects and returns the * winner. It uses the records of the two teams to make a weighted * random prediction and returns the winner. */ public Team playGame(Team team1, Team team2) { double team1RandomNum = team1.calculateWinningPercentage() * Math.random(); double team2RandomNum = team2.calculateWinningPercentage() * Math.random(); if (team1RandomNum > team2RandomNum) { team1.incWins(); team2.incLosses(); return team1; } else { team1.incLosses(); team2.incWins(); return team2; } }

/** * DO NOT CHANGE THIS METHOD * * This method returns your Iterator */ public Iterator bottomUpBracketIterator() { return new BottomUpBracketIterator(); }

public int logBase2(int num) { int counter = 0; while (num > 1) { counter++; num /= 2; } return counter; }

/** * YOU MUST DEFINE THIS ITERATOR. YOU MAY ADD INSTANCE VARIABLES * AND HELPER METHODS. IT SHOULD PRODUCE ELEMENTS LEFT TO RIGHT, * BOTTOM LEVEL FIRST. */ class BottomUpBracketIterator implements Iterator {

public boolean hasNext() { return false; }

public Object next() { return null; }

// LEAVE THIS METHOD ALONE public void remove() {} } }

Thank you for reading and helping me.

Have a niceday!