/** * WTFactory.java * * Code for drawing and generating a WalTree. * * A direct port from Sven Moen's "Drawing Dynamic Trees" article in * IEEE Software, July 1990. Thanks to Allan Brighton for commenting the * Brighton Tree Widget source code with the aforementioned reference. */ import java.awt.*; /** * Encapsulates all operations performed on a WalTree. * This is part of the WalTree package, created by Walter Korman to enable * the visually appealing display of M-ary trees. More documentation is * available at his web site; follow the link below to get to it. *
* Documentation *
* @author Walter Korman */ public class WTFactory { /* Following are workarounds for font size calculations, as Netscape * reports unappealing font height/ascents on varying platforms. */ static final int FIXED_FONT_HEIGHT = 10; static final int FIXED_FONT_ASCENT = 3; /** * Distance between levels in the tree. */ int parent_dist = 30; /** * Allows setting of the distance between levels in the tree. */ public void setParentDistance(int val) { parent_dist = val; } /** * Lays out the tree node spacing in typical tidy fashion. */ void layout(WNode t) { WNode c; if(t == null) { return; } c = t.child; while(c != null) { layout(c); c = c.sibling; } if(t.child != null) { attachParent(t, join(t)); } else { layoutLeaf(t); } } /** * Attaches the specified node to its children, setting offsets. */ void attachParent(WNode t, int h) { int x, y1, y2; x = t.border + parent_dist; y2 = (h - t.height) / 2 - t.border; y1 = y2 + t.height + 2 * t.border - h; t.child.offset.x = x + t.width; t.child.offset.y = y1; t.contour.upper_head = new PolyLine(t.width, 0, new PolyLine(x, y1, t.contour.upper_head)); t.contour.lower_head = new PolyLine(t.width, 0, new PolyLine(x, y2, t.contour.lower_head)); } /** * Arranges contour for leaf node appropriately. */ void layoutLeaf(WNode t) { t.contour.upper_tail = new PolyLine(t.width + 2 * t.border, 0, null); t.contour.upper_head = t.contour.upper_tail; t.contour.lower_tail = new PolyLine(0, -t.height - 2 * t.border, null); t.contour.lower_head = new PolyLine(t.width + 2 * t.border, 0, t.contour.lower_tail); } /** * Joins children/siblings together, merging contours. */ int join(WNode t) { WNode c; int d, h, sum; c = t.child; t.contour = c.contour; sum = h = c.height + 2 * c.border; c = c.sibling; while(c != null) { d = merge(t.contour, c.contour); c.offset.y = d + h; c.offset.x = 0; h = c.height + 2 * c.border; sum += d + h; c = c.sibling; } return sum; } /** * Merges two polygons together. Returns total height of final polygon. */ int merge(Polygon c1, Polygon c2) { int x, y, total, d; PolyLine lower, upper, b; x = y = total = 0; upper = c1.lower_head; lower = c2.upper_head; while(lower != null && upper != null) { /* compute offset total */ d = offset(x, y, lower.dx, lower.dy, upper.dx, upper.dy); y += d; total += d; if(x + lower.dx <= upper.dx) { y += lower.dy; x += lower.dx; lower = lower.link; } else { y -= upper.dy; x -= upper.dx; upper = upper.link; } } /* store result in c1 */ if(lower != null) { b = bridge(c1.upper_tail, 0, 0, lower, x, y); c1.upper_tail = (b.link != null) ? c2.upper_tail : b; c1.lower_tail = c2.lower_tail; } else { /* (upper) */ b = bridge(c2.lower_tail, x, y, upper, 0, 0); if(b.link == null) { c1.lower_tail = b; } } c1.lower_head = c2.lower_head; return total; } /** * Calculates the offset for specified points. */ int offset(int p1, int p2, int a1, int a2, int b1, int b2) { int d, s, t; if(b1 <= p1 || p1 + a1 <= 0) { return 0; } t = b1 * a2 - a1 * b2; if(t > 0) { if(p1 < 0) { s = p1 * a2; d = s / a1 - p2; } else if(p1 > 0) { s = p1 * b2; d = s / b1 - p2; } else { d = -p2; } } else if(b1 < p1 + a1) { s = (b1 - p1) * a2; d = b2 - (p2 + s / a1); } else if(b1 > p1 + a1) { s = (a1 + p1) * b2; d = s / b1 - (p2 + a2); } else { d = b2 - (p2 + a2); } if(d > 0) { return d; } else { return 0; } } /** * Create a PolyLine bridge between links. */ PolyLine bridge(PolyLine line1, int x1, int y1, PolyLine line2, int x2, int y2) { int dy, dx, s; PolyLine r; dx = x2 + line2.dx - x1; if(line2.dx == 0) { dy = line2.dy; } else { s = dx * line2.dy; dy = s / line2.dx; } r = new PolyLine(dx, dy, line2.link); line1.link = new PolyLine(0, y2 + line2.dy - dy - y1, r); return r; } /** * Set the position of the nodes of the tree. */ void plantTree(WNode t, int off_x, int off_y) { WNode c, s; int cur_y; t.pos.x = off_x + t.offset.x; t.pos.y = off_y + t.offset.y; /* Plant child node */ c = t.child; if(c != null) { plantTree(c, t.pos.x, t.pos.y); /* Plant sibling nodes */ s = c.sibling; cur_y = t.pos.y + c.offset.y; while(s != null) { plantTree(s, t.pos.x + c.offset.x, cur_y); cur_y += s.offset.y; s = s.sibling; } } } /** * Draw the M-ary tree on screen. */ void paintFullTree(Graphics g, FontMetrics metrics, WNode t) { if(t == null) { System.out.println("paintFullTree::null tree."); return; } g.setColor(Color.black); paintTree(g, metrics, t); } /** * Recursively called to draw nodes of the M-ary tree. * Modified by Naomi Novik to draw the node in a different color * depending on the status of the WNode member variable "visited", */ void paintTree(Graphics g, FontMetrics metrics, WNode t) { /* Draw highlights */ g.setColor(Color.lightGray); g.drawLine(t.pos.x + 2, t.pos.y + t.height + 1, t.pos.x + t.width, t.pos.y + t.height + 1); g.drawLine(t.pos.x + t.width + 1, t.pos.y + t.height + 1, t.pos.x + t.width + 1, t.pos.y + 2); if(t.parent != null) { g.drawLine(t.pos.x, t.pos.y + t.height / 2 + 1, t.parent.pos.x + t.parent.width, t.parent.pos.y + t.parent.height / 2 + 1); } /* Draw this node */ if (t.visited) { g.setColor(Color.red); } else { g.setColor(Color.black); } g.drawRect(t.pos.x, t.pos.y, t.width, t.height); g.drawString(t.label, t.pos.x + (t.width - metrics.stringWidth(t.label)) / 2, t.pos.y + t.height - (t.height - FIXED_FONT_HEIGHT) / 2); g.setColor(Color.black); /* Draw line to parent */ if(t.parent != null) { g.drawLine(t.pos.x, t.pos.y + t.height / 2, t.parent.pos.x + t.parent.width, t.parent.pos.y + t.parent.height / 2); } /* Draw siblings, using the main child's x-offset. */ if(t.sibling != null) { paintTree(g, metrics, t.sibling); } /* Draw children */ if(t.child != null) { paintTree(g, metrics, t.child); } } };