This time, we're going to use a Binary Search Tree, which also keeps its contents sorted. In fact, Binary Search Trees must keep their contents sorted. We will use the company ticker symbols as the criteria (A-Z) for sorting our objects.

In the project, find the following 4 files:

DJIABinarySearchTree.java

DJIACompany.java

DJIATreeApp.java

DJIA.txt

Go through the code of these classes and read the documentation. The DJIATreeApp has a main method. This time our application will render your DJIABinarySearchTree. I have provided a method that works properly for adding nodes to your BST. The problem is that it cannot forecast the order with which data will be given to it, and so we may quickly end up with a gangly, inefficient BST that is deeper than it needs to be, which makes it rather unwieldy to draw after adding a number of nodes.

As we discussed in lecture, it is important to keep Binary Search Trees (BSTs) as shallow as possible, to ensure searching is efficient. After all, a primary benefit of using BSTs is the log(n) search efficiency.

YOUR TWO METHODS, ALL FROM THE DJIABinarySearchTree CLASS

Define the calculateTreeLevels method such that when called it dynamically calculates the number of levels in the tree. This means it should return the level of the deepest node. I am using this method to help in the rendering of the tree.

Define the rebalance method so that when called it reconfigures the tree such that the tree depth is minimized and such that your BST equally balances left & right nodes (note, this is not necessarily a complete tree).

Should you implement your methods properly, for the input I've provided in the file, you should get trees that look like the ones provided in the images below. The first one is after all 15 nodes have been added. The second one is after calling your rebalance method. Note that my file only has 15 companies because adding more results in a seriously fugly tree. There just isn't enough space to render it neatly, but that's ok, we get the point with 15 nodes.

Here is my code.

package part1_bst;

import java.text.NumberFormat;

/* * This class represents a single company that is part of the * Dow Jones Industrial Average. Note that there are exacly 30 * companies on the DOW. For a list of all the companies on the DOW, * see http://www.djindexes.com/mdsidx/index.cfm?event=showAverages * * NOTE: DO NOT CHANGE THIS FILE */ public class DJIACompany implements Comparable { // COMPANY NAME private String name; // TICKER SYMBOL private String symbol; // STOCK PRICE private double pricePerShare; public DJIACompany( String initName, String initSymbol, double initPricePerShare) { name = initName; symbol = initSymbol; pricePerShare = initPricePerShare; } public String toString() { NumberFormat nf = NumberFormat.getCurrencyInstance(); String symbolColumn = symbol; while (symbolColumn.length() < 5) symbolColumn = " " + symbolColumn; String priceColumn = nf.format(pricePerShare); while (priceColumn.length() < 10) priceColumn = " " + priceColumn; return symbolColumn + priceColumn; }

// ACCESSOR METHODS public String getName() { return name; } public String getSymbol() { return symbol; } public double getPricePerShare() { return pricePerShare; }

// MUTATOR METHODS public void setName(String initName) { name = initName; } public void setSymbol(String initSymbol) { symbol = initSymbol; } public void setPricePerShare(double initPricePerShare) { pricePerShare = initPricePerShare; }

/* * We only want to compare companies by their ticker symbol * for the purpose of keeping them sorted. */ public int compareTo(Object obj) { DJIACompany otherStock = (DJIACompany)obj; return symbol.compareTo(otherStock.symbol); } }

package part1_bst;

import java.io.*; import java.util.*; import javafx.application.Application; import javafx.geometry.Rectangle2D; import javafx.scene.Scene; import javafx.scene.canvas.Canvas; import javafx.scene.canvas.GraphicsContext; import javafx.scene.control.Alert; import javafx.scene.control.Alert.AlertType; import javafx.scene.control.Button; import javafx.scene.layout.BorderPane; import javafx.scene.layout.HBox; import javafx.scene.layout.Pane; import javafx.scene.text.Font; import javafx.stage.Screen; import javafx.stage.Stage;

/* * DJIA Tree App - DO NOT CHANGE THIS FILE * * This file is used in Part 1 of HW 3. In this part, you only need to * define the necessary methods inside the DJIABinarySearchTree class. * */ public class DJIATreeApp extends Application { // HERE'S THE tree WE'RE GOING TO PLAY AROUND WITH DJIABinarySearchTree tree = new DJIABinarySearchTree(); double dowDivisor;

// THIS IS THE APPLICATION WINDOW Stage window;

// NORTH TOOLBAR HBox topPane = new HBox(); Button addButton = new Button("Add Company"); Button rebalanceButton = new Button("Rebalance Tree"); Button emptytreeButton = new Button("Empty the Tree");

// THIS WILL RENDER OUR tree Canvas djiaCanvas = new Canvas();

// THIS IS FOR READING DJIA DATA FROM A FILE BufferedReader reader;

public void start(Stage primaryStage) { window = primaryStage; layoutGUI(); initFileReader(); }

public void initFileReader() { // SETUP THE READER SO IT CAN READ DATA WHEN NEEDED String fileName = "DJIA.txt"; try { FileInputStream fis = new FileInputStream(fileName); InputStreamReader isr = new InputStreamReader(fis); reader = new BufferedReader(isr); // FIRST GET THE DIVISOR dowDivisor = Double.parseDouble(reader.readLine()); } catch (IOException ioe) { // TheHittree FILE WAS NOT FOUND, IT MIGHT BE IN THE WRONG DIRECTORY Alert dialog = new Alert(AlertType.ERROR); dialog.setTitle("File Not Found"); dialog.setHeaderText(null); dialog.setContentText(fileName + " not found"); dialog.showAndWait(); System.exit(0); } }

public void layoutGUI() { topPane.getChildren().add(addButton); topPane.getChildren().add(rebalanceButton); topPane.getChildren().add(emptytreeButton);

BorderPane appPane = new BorderPane(); Pane canvasParent = new Pane(); canvasParent.getChildren().add(djiaCanvas); canvasParent.layoutBoundsProperty().addListener((ov, oldValue, newValue) -> { djiaCanvas.setWidth(newValue.getWidth()); djiaCanvas.setHeight(newValue.getHeight()); }); appPane.setTop(topPane); appPane.setCenter(canvasParent); 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());

addButton.setOnAction(e -> { processAddCompanyRequest(); }); rebalanceButton.setOnAction(e -> { processRebalanceRequest(); }); emptytreeButton.setOnAction(e -> { processEmptyTreeRequest(); }); // OPEN THE WINDOW window.show(); }

public void processAddCompanyRequest() { try { String line = reader.readLine(); if (line == null) { Alert dialog = new Alert(AlertType.INFORMATION); dialog.setTitle("No More Companies"); dialog.setHeaderText(null); dialog.setContentText("No more companies in the DOW"); dialog.showAndWait(); } else { StringTokenizer st = new StringTokenizer(line, ","); String name = st.nextToken(); String symbol = st.nextToken(); double price = Double.parseDouble(st.nextToken()); DJIACompany company = new DJIACompany(name, symbol, price); tree.addCompany(company); drawTree(); } } catch (IOException ioe) { // TheHittree FILE WAS NOT FOUND, IT MIGHT BE IN THE WRONG DIRECTORY Alert dialog = new Alert(AlertType.ERROR); dialog.setTitle("File Error"); dialog.setHeaderText(null); dialog.setContentText("An error has occured reading the file"); dialog.showAndWait(); System.exit(0); } }

public void processRebalanceRequest() { tree.rebalance(); drawTree(); }

public void processEmptyTreeRequest() { tree.clear(); initFileReader(); drawTree(); }

// THESE ARE USING FOR DRAWING TO THE CANVAS static final int TEXT_Y_OFFSET = 20; static final int TEXT_X_OFFSET = 10; static final int RECT_WIDTH = 50; static final int RECT_HEIGHT = 30; static final int RECT_X_OFFSET = 30; static final int RECT_Y_OFFSET = 50; static final int NODES_PER_ROW = 6; static final int MAX_NODES = 30; static final int ARROW_TAIL_LENGTH = 10; int NODES_PER_COLUMN = MAX_NODES / NODES_PER_ROW; Font nodeFont = new Font("console", 11);

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

public void drawTree() { GraphicsContext g = djiaCanvas.getGraphicsContext2D(); g.setFont(nodeFont); // WHAT ARE THE CANVAS DIMENSIONS double canvasWidth = djiaCanvas.getWidth(); double canvasHeight = djiaCanvas.getHeight(); // FIRST CLEAR g.clearRect(0, 0, canvasWidth, canvasHeight);

// HOW MANY LEVELS ARE THERE? int treeLevels = tree.calculateTreeLevels(); g.strokeText("Tree Levels: " + treeLevels, 0, 20); g.strokeText("Tree Nodes: " + tree.size(), 0, 40);

// CALCULATE THE SIZE OF EVERYTHING WE NEED TO DRAW double arrowX1, arrowY1, arrowX2, arrowY2;

// CALCULATE THE PANEL LOCATION OF THE FIRST NODE double rectX = (canvasWidth / 2.0) - (RECT_WIDTH / 2.0); double rectY = RECT_HEIGHT;

double x1, y1, x2, y2; int row;

boolean drawingComplete = false;

int counter = 0; Iterator it = tree.treeIterator();

while (!drawingComplete) { if (!it.hasNext()) { drawingComplete = true; } else { DJIACompany company = (DJIACompany) it.next(); int treeIndex = tree.calculateTreeIndex(company); int treeLevel = logBase2(treeIndex + 1);

int nodesOnLevel = (int) (Math.pow(2, treeLevel)); int levelIndex = (treeIndex + 1) % nodesOnLevel;

int spacing = (int) (canvasWidth / Math.pow(2, treeLevel + 1));

rectX = (spacing + (spacing * 2 * levelIndex)) - (RECT_WIDTH / 2); rectY = RECT_HEIGHT + (treeLevel * 2 * RECT_HEIGHT); g.strokeRect(rectX, rectY, RECT_WIDTH, RECT_HEIGHT); g.strokeText(company.getSymbol(), rectX + TEXT_X_OFFSET, rectY + TEXT_Y_OFFSET);

// TOP OF THIS NODE x2 = rectX + (RECT_WIDTH / 2); y2 = rectY;

if (treeIndex == 0) { x1 = rectX + (RECT_WIDTH / 2); } // LEFT NODE else if ((treeIndex % 2) == 1) { x1 = x2 + spacing; } // RIGHT NODE else { x1 = x2 - spacing; }

y1 = rectY - (2 * RECT_HEIGHT) + RECT_HEIGHT;

g.strokeLine(x1, y1, x2, y2); } } }

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

package part1_bst;

import java.util.Iterator;

/* * YOU MUST FILL IN THE CODE FOR THE FOLLOWING TWO METHODS: * - calculateTreeLevels * - rebalance */ public class DJIABinarySearchTree { // ROOT FOR OUR TREE

private TreeNode root = null;

// TOTAL NUMBER OF NODES IN THE TREE private int size = 0;

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

// ACCESSOR METHOD public int size() { return size; }

/** * DO NOT CHANGE THIS METHOD * * This method adds a company to the correct sorted location * in the BST by employing the recursive addCompanyToNode method. */ public void addCompany(DJIACompany initCompany) { // CASE: EMPTY TREE if (root == null) { // MAKE IT THE ROOT, THE ONE AND ONLY NODE root = new TreeNode(initCompany, null, null); size++; } else { // addCompanyToNode WILL FIND THE PLACE TO PUT IT, // STARTING WITH THE ROOT addCompanyToNode(root, initCompany); } }

/** * DO NOT CHANGE THIS METHOD * * This method recursively searches for the appropriate * place in this BST to add the company. */ private void addCompanyToNode(TreeNode node, DJIACompany initCompany) { // NO DUPLICATES if (node.data.getSymbol().equals(initCompany.getSymbol())) { return; }

// ADD TO LEFT SUBTREE if (node.data.getSymbol().compareTo(initCompany.getSymbol()) > 0) { // ADD IT AS A LEAF, WE CAN'T GO ANY FURTHER LEFT if (node.leftNode == null) { node.leftNode = new TreeNode(initCompany, null, null); size++; } else { // TRY FURTHER LEFT addCompanyToNode(node.leftNode, initCompany); } } // ADD TO RIGHT SUBTREE else // ADD IT AS A LEAF, WE CAN'T GO ANY FURTHER RIGHT if (node.rightNode == null) { node.rightNode = new TreeNode(initCompany, null, null); size++; } else { // TRY FURTHER RIGHT addCompanyToNode(node.rightNode, initCompany); } }

/** * DO NOT CHANGE THIS METHOD * * This method empties the tree of all nodes. */ public void clear() { root = null; size = 0; }

/** * YOU MUST DEFINE THIS METHOD * * It calculates the level of the deepest node in the tree. Note, * if the tree only has a root, then it only has one level. * * ADVICE: Look at how I recursively defined the addCompanyToNode * method. You might want to try to do something like that for this as well. */ public int calculateTreeLevels() { // ADD YOUR CODE HERE return 0; }

/** * DO NOT CHANGE THIS METHOD * * This method is used for rendering purposes. It's used to calculate * the position of each node such that we get a nice, aligned looking * tree. */ public int calculateTreeIndex(DJIACompany company) { return calculateTreeIndex(root, company, 0); }

/** * DO NOT CHANGE THIS METHOD * * This method is a recursive helper to calculateTreeIndex */ private int calculateTreeIndex(TreeNode node, DJIACompany company, int index) { if (node == null) { return -1; } int comparison = node.data.getSymbol().compareTo(company.getSymbol()); if (comparison == 0) { return index; } else if (comparison > 0) { int leftIndex = (2 * index) + 1; return calculateTreeIndex(node.leftNode, company, leftIndex); } else { int rightIndex = (2 * index) + 2; return calculateTreeIndex(node.rightNode, company, rightIndex); } }

/** * YOU MUST DEFINE THIS METHOD * * This method should rearrange the node so as to minimize the height * of the tree and to balance the tree on right and left sides. Again, * might want to think about using a recursive helper method. */ public void rebalance() { // YOUR CODE GOES HERE }

/** * DO NOT CHANGE THIS METHOD * * This method produces an iterator that produces elements in * sorted order. */ public Iterator treeIterator() { return new SortedIterator(); }

/** * DO NOT CHANGE THIS CLASS * * This iterator produces data from the tree in sorted order. */ class SortedIterator implements Iterator {

protected DJIACompany[] elements = new DJIACompany[size]; protected int currentElement = 0;

public SortedIterator() { if (root != null) { fillIteratorElements(root); currentElement = 0; } }

private void fillIteratorElements(TreeNode node) { if (node.leftNode != null) { fillIteratorElements(node.leftNode); } elements[currentElement] = node.data; currentElement++; if (node.rightNode != null) { fillIteratorElements(node.rightNode); } }

public boolean hasNext() { if ((size > 0) && (currentElement < size)) { return true; } else { return false; } }

public Object next() { if ((size > 0) && (currentElement < size)) { return elements[currentElement++]; } else { return null; } }

public void remove() {} } }

class TreeNode { protected DJIACompany data; protected TreeNode leftNode; protected TreeNode rightNode;

public TreeNode(DJIACompany initData, TreeNode initLeftNode, TreeNode initRightNode) { data = initData; leftNode = initLeftNode; rightNode = initRightNode; } }

I am using Netbeans.

Thank you for reading and helping me

Have a niceday!