import java.awt.BasicStroke; import java.awt.Color; import java.awt.Dimension; import java.awt.Font; import java.awt.FontMetrics; import java.awt.Graphics; import java.awt.Graphics2D; import java.awt.RenderingHints; import java.lang.reflect.Field; import java.util.ArrayList; import javax.swing.JFrame; import javax.swing.JPanel; import javax.swing.SwingUtilities; import javax.swing.WindowConstants; /** * Draws a BSTMap as a tree, one row per level, with the level numbers on the * left and the number of nodes in each level on the right. * * You do not need to read or change this file. It looks inside your BSTMap, * so it needs the field names from the provided BSTMap.java: root in BSTMap, * and key, value, left, right in Node. * * BSTDisplay display = new BSTDisplay(map, "My tree"); * map.put(...); * display.show(key); // redraw; outline the path to key (or pass null) */ public class BSTDisplay { private static final int MAX_ROW = 70; // most pixels between levels private static final int MARGIN = 70; // room for the level labels private static final int TOP = 60; private final Object map; private final JFrame frame; private final TreePanel panel; private volatile Object highlight; // key whose search path is outlined private volatile String message = ""; public BSTDisplay(Object map, String title) { this.map = map; panel = new TreePanel(); frame = new JFrame(title); frame.setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE); frame.add(panel); frame.setSize(900, 520); frame.setLocationByPlatform(true); frame.setVisible(true); } /** Redraws the tree and outlines the path from the root to key (null for no path). */ public void show(Object key) { show(key, ""); } /** Redraws the tree, outlines the path to key, and prints a message at the bottom. */ public void show(Object key, String message) { this.highlight = key; this.message = message; SwingUtilities.invokeLater(() -> panel.repaint()); } /** Closes the window. */ public void close() { frame.dispose(); } /** Draws the current tree into g, at the given size. Used by the window and by tests. */ public void paintTree(Graphics graphics, int width, int height) { Graphics2D g = (Graphics2D) graphics; g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON); g.setColor(Color.WHITE); g.fillRect(0, 0, width, height); Object root; try { root = field(map, "root"); } catch (Exception e) { drawText(g, "BSTDisplay can't find a field named root in your BSTMap.", 20, 40, Color.RED); return; } // Lay out: x comes from the node's position in sorted order, y from its level. ArrayList nodes = new ArrayList<>(); ArrayList levels = new ArrayList<>(); try { inorder(root, 0, nodes, levels); } catch (Exception e) { drawText(g, "BSTDisplay can't read your Node fields (key, value, left, right).", 20, 40, Color.RED); return; } int n = nodes.size(); int depth = 0; for (int level : levels) { depth = Math.max(depth, level + 1); } int row = Math.min(MAX_ROW, (height - TOP - 50) / Math.max(depth - 1, 1)); int band = Math.min(48, row - 4); int[] perLevel = new int[Math.max(depth, 1)]; for (int level : levels) { perLevel[level]++; } // Header and level labels, as in the lecture picture. Color blue = new Color(40, 100, 210); g.setFont(new Font("SansSerif", Font.PLAIN, 14)); drawText(g, "Level", 12, 28, blue); drawText(g, "Nodes", width - 58, 28, blue); for (int level = 0; level < depth; level++) { int y = TOP + level * row; g.setColor(new Color(235, 242, 252)); g.fillRoundRect(MARGIN - 20, y - band / 2, width - 2 * MARGIN + 40, band, 16, 16); drawText(g, "" + level, 28, y + 5, blue); drawText(g, "" + perLevel[level], width - 42, y + 5, blue); } // Search path to the highlighted key, if any. ArrayList path = new ArrayList<>(); Object pathEnd = null; if (highlight != null) { try { pathEnd = searchPath(root, highlight, path); } catch (Exception e) { path.clear(); } } int usable = width - 2 * MARGIN; int[] xs = new int[n]; for (int i = 0; i < n; i++) { xs[i] = MARGIN + (n == 1 ? usable / 2 : (int) Math.round(i * (usable / (double) (n - 1)))); } int radius = Math.min(n <= 20 ? 17 : (n <= 45 ? 11 : 6), Math.max(row / 2 - 2, 4)); boolean labels = n <= 45; g.setFont(new Font("SansSerif", Font.PLAIN, n <= 20 ? 13 : 10)); // Edges first, then nodes on top. g.setStroke(new BasicStroke(1.5f)); for (int i = 0; i < n; i++) { Object node = nodes.get(i); for (String side : new String[] {"left", "right"}) { Object child = safeField(node, side); int j = indexOf(nodes, child); if (j >= 0) { boolean onPath = path.contains(node) && path.contains(child); g.setColor(onPath ? new Color(230, 120, 0) : Color.DARK_GRAY); g.setStroke(new BasicStroke(onPath ? 3f : 1.5f)); g.drawLine(xs[i], TOP + levels.get(i) * row, xs[j], TOP + levels.get(j) * row); } } } for (int i = 0; i < n; i++) { Object node = nodes.get(i); int x = xs[i]; int y = TOP + levels.get(i) * row; boolean onPath = path.contains(node); String text = labels ? "" + safeField(node, "key") : ""; FontMetrics fm = g.getFontMetrics(); int half = Math.max(radius, fm.stringWidth(text) / 2 + 6); // wide enough for the key g.setColor(node == pathEnd ? new Color(255, 214, 140) : Color.WHITE); g.fillRoundRect(x - half, y - radius, 2 * half, 2 * radius, 2 * radius, 2 * radius); g.setColor(onPath ? new Color(230, 120, 0) : Color.BLACK); g.setStroke(new BasicStroke(onPath ? 3f : 1.5f)); g.drawRoundRect(x - half, y - radius, 2 * half, 2 * radius, 2 * radius, 2 * radius); if (labels) { drawText(g, text, x - fm.stringWidth(text) / 2, y + fm.getAscent() / 2 - 1, Color.BLACK); } } g.setFont(new Font("SansSerif", Font.PLAIN, 14)); String footer = n + " nodes, " + depth + " levels"; if (!labels) { footer += " (too many nodes to label)"; } if (!message.isEmpty()) { footer += " " + message; } drawText(g, footer, 12, height - 14, Color.DARK_GRAY); } // ------------------------------------------------------------------ helpers private class TreePanel extends JPanel { private static final long serialVersionUID = 1L; TreePanel() { setPreferredSize(new Dimension(900, 520)); } @Override protected void paintComponent(Graphics g) { super.paintComponent(g); paintTree(g, getWidth(), getHeight()); } } private static void drawText(Graphics2D g, String text, int x, int y, Color color) { g.setColor(color); g.drawString(text, x, y); } private static Object field(Object object, String name) throws Exception { Field f = object.getClass().getDeclaredField(name); f.setAccessible(true); return f.get(object); } private static Object safeField(Object object, String name) { try { return field(object, name); } catch (Exception e) { return null; } } private static int indexOf(ArrayList nodes, Object node) { for (int i = 0; i < nodes.size(); i++) { if (nodes.get(i) == node) { return i; } } return -1; } /** In-order walk; stops at 5000 nodes in case the tree has a loop. */ private static void inorder(Object node, int level, ArrayList nodes, ArrayList levels) throws Exception { if (node == null || nodes.size() > 5000) { return; } inorder(field(node, "left"), level + 1, nodes, levels); nodes.add(node); levels.add(level); inorder(field(node, "right"), level + 1, nodes, levels); } /** Follows the search for key from root; fills path and returns the node found, or null. */ @SuppressWarnings({"unchecked", "rawtypes"}) private static Object searchPath(Object node, Object key, ArrayList path) throws Exception { while (node != null && path.size() < 5000) { path.add(node); int c = ((Comparable) key).compareTo(field(node, "key")); if (c == 0) { return node; } node = field(node, c < 0 ? "left" : "right"); } return null; } }