/* ---------------------------------------------------------------------------- * File : draw.c * Purpose : drawing-specific routines for dynamic tree program * ---------------------------------------------------------------------------- */ #ifdef MSW #include #else #include #include #endif #include #include "defs.h" #include "tree.h" #include "dbl.h" #include "intf.h" /* ------------------------------------------------------------------------- */ /* Global Variables */ /* ------------------------------------------------------------------------- */ Tree *TheTree; /* ------------------------------------------------------------------------- */ /* Local Variables */ /* ------------------------------------------------------------------------- */ static char AnimationMode = FALSE; static char strbuf[BUFSIZ]; static int AnimationStep = ANIMATION_STEP; #ifdef MSW static int DrawingWidth; static int DrawingHeight; #endif /* ------------------------------------------------------------------------- */ /* Forward Function Declarations */ /* ------------------------------------------------------------------------- */ void DrawNode(); void DrawTreeContour(); /* ------------------------------------------------------------------------- */ /* Functions */ /* ------------------------------------------------------------------------- */ #ifdef MSW static void SelectNewDeleteOld (HGDIOBJ obj) { obj = SelectObject (TreeDrawingAreaDB->hdc, obj); DeleteObject (obj); } static void RefreshPen (void) { HPEN pen = CreatePen (PS_SOLID, TreeDrawingAreaDB->LineWidth, GetTextColor (TreeDrawingAreaDB->hdc)); SelectNewDeleteOld (pen); } BOOL SetNewFont (LPLOGFONT lplf) { HFONT font = CreateFontIndirect (lplf); if (font) SelectNewDeleteOld (font); return font != NULL; } #endif /* ---------------------------------------------------------------------------- * * BeginFrame() provides an abstraction for double buffering. It should * be called prior to creating a new frame of animation. * * ---------------------------------------------------------------------------- */ void BeginFrame() { #ifndef MSW DBLbegin_frame(TreeDrawingAreaDB); #endif } /* ---------------------------------------------------------------------------- * * EndFrame() provides an abstraction for double buffering. It should * be called after creating a new frame of animation. * * ---------------------------------------------------------------------------- */ void EndFrame() { #ifndef MSW /* Changed second parameter from 0 to 1 at Torgeir Veimo's suggestion on 9/21/1997. -- Bob Weiner, BeOpen.com */ DBLend_frame(TreeDrawingAreaDB, 1); #endif } /* ---------------------------------------------------------------------------- * * GetDrawingSize() gets the size of the drawing area, and returns the * dimensions in the arguments. * * ---------------------------------------------------------------------------- */ void GetDrawingSize(width, height) int *width, *height; { #ifdef MSW *width = TreeDrawingAreaDB->DrawingWidth; *height = TreeDrawingAreaDB->DrawingHeight; #else Dimension w, h; XtVaGetValues(TreeDrawingArea, XtNwidth, &w, XtNheight, &h, NULL); *width = (int) w; *height = (int) h; #endif } /* ---------------------------------------------------------------------------- * * SetDrawingSize() sets the size of the drawing area to the given * dimensions. * * ---------------------------------------------------------------------------- */ void SetDrawingSize(width, height) int width, height; { #ifdef MSW RECT rc; POINT pt; SCROLLINFO si; TreeDrawingAreaDB->DrawingWidth = width; TreeDrawingAreaDB->DrawingHeight = height; /* Setup scrollbars */ GetClientRect (hwndClient, &rc); GetWindowOrgEx (TreeDrawingAreaDB->hdc, &pt); si.cbSize = sizeof (si); si.fMask = SIF_ALL | SIF_DISABLENOSCROLL; /* Vertical bar */ si.nMin = 0; si.nMax = height; si.nPage = rc.bottom; si.nPos = pt.y; SetScrollInfo (hwndClient, SB_VERT, &si, TRUE); /* Horizontal bar */ si.nMin = 0; si.nMax = width; si.nPage = rc.right; si.nPos = pt.x; SetScrollInfo (hwndClient, SB_HORZ, &si, TRUE); #else XtVaSetValues(TreeDrawingArea, XtNwidth, (Dimension) width, XtNheight, (Dimension) height, NULL); #endif } /* ---------------------------------------------------------------------------- * * SetDrawingTree() is used to specify what tree is to be drawn in the * drawing area. * * ---------------------------------------------------------------------------- */ void SetDrawingTree(tree) Tree *tree; { TheTree = tree; } /* ---------------------------------------------------------------------------- * * SetNodeLabel() sets the label text of the specified node and computes * the bounding rectangle so that the layout can be determined. This * function is called when new nodes are created. If TreeAlignNodes is * True, the string is truncated so that the node's width is no longer * than TreeParentDistance. * * ---------------------------------------------------------------------------- */ void SetNodeLabel(node, label) Tree *node; char *label; { int len; #ifdef MSW SIZE sz; #else int dummy; XCharStruct rtrn; #endif len = strlen(label); while (len > 1) { #ifdef MSW GetTextExtentPoint32 (TreeDrawingAreaDB->hdc, label, len, &sz); node->width = sz.cx + (LABEL_MAT_WIDTH * 2) + 1; node->height = sz.cy + (LABEL_MAT_HEIGHT * 2) + 1; #else XTextExtents(TreeLabelFont, label, len, &dummy, &dummy, &dummy, &rtrn); node->width = rtrn.lbearing + rtrn.rbearing + (LABEL_MAT_WIDTH * 2) + 1; node->height = rtrn.ascent + rtrn.descent + (LABEL_MAT_HEIGHT * 2) + 1; #endif if (TreeAlignNodes) { if (node->width <= (2 * TreeParentDistance)) break; else len--; } else break; } node->label.text = label; node->label.len = len; node->label.xoffset = LABEL_MAT_WIDTH + 1, #ifdef MSW node->label.yoffset = LABEL_MAT_HEIGHT + 1; #else node->label.yoffset = rtrn.ascent + LABEL_MAT_HEIGHT + 1; #endif } /* ---------------------------------------------------------------------------- * * SetDrawColor() sets the drawing color of the TreeDrawingArea. * * ---------------------------------------------------------------------------- */ void SetDrawColor(color) int color; { #ifdef MSW SetTextColor (TreeDrawingAreaDB->hdc, TreeDrawingAreaDB->colors[color]); #else XSetForeground(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc, TreeDrawingAreaDB->colors[color]); #endif } /* ---------------------------------------------------------------------------- * * SetLineWidth() sets the line width of lines drawn in the TreeDrawingArea. * * ---------------------------------------------------------------------------- */ void SetLineWidth(width, color) unsigned int width; int color; { #ifdef MSW TreeDrawingAreaDB->LineWidth = width; #else XSetLineAttributes(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc, width, LineSolid, CapButt, JoinRound); #endif } /* ---------------------------------------------------------------------------- * * SetContours() sets the visibility of three possible contour modes: * the outside contour, all subtree contours, or selected contours. * * ---------------------------------------------------------------------------- */ void SetContours(option) ContourOption option; { if (option == NoContours) { switch (TreeShowContourOption) { case OutsideContour: DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, FALSE); break; case AllContours: DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE); break; case SelectedContours: DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, TRUE, TRUE); break; default: ; } DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE); } else if (option == OutsideContour) { switch (TreeShowContourOption) { case AllContours: DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE); break; case SelectedContours: DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, TRUE, TRUE); break; default: ; } DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE); } else if (option == AllContours) { DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, TRUE); } else if (option == SelectedContours) { switch (TreeShowContourOption) { case AllContours: DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE); break; case OutsideContour: DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, FALSE); break; default: DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE); } DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, TRUE, TRUE); } TreeShowContourOption = option; } /* ---------------------------------------------------------------------------- * * HiliteNode() is called by Unzip() to change the color of a node. * * ---------------------------------------------------------------------------- */ void HiliteNode(tree, pos_mode) Tree *tree; { SetDrawColor(HIGHLIGHT_COLOR); DrawNode(tree, pos_mode); SetDrawColor(TREE_COLOR); } /* ---------------------------------------------------------------------------- * * DrawNode() takes a node and draws the node in the specified widget * at its (x,y) coordinate. (x, y) indicates the upper-left corner where * the node is drawn. Also, a line is drawn from the center of the left * edge to the center of the parent's right edge. 'draw_mode' specifies * the drawing mode (whether or not the node is erased, rather than drawn). * 'pos_mode' determines whether or not to use the old position of the node. * This flag is used in animating the movement of a node from its old * position to its new position. * * ---------------------------------------------------------------------------- */ static void DrawNodeHelper (node, pos, parent_pos) Tree *node; Point *pos; Point *parent_pos; { #ifdef MSW HDC hdc = TreeDrawingAreaDB->hdc; RECT rcNode; rcNode.left = pos->x; rcNode.top = pos->y; rcNode.right = pos->x + node->width; rcNode.bottom = pos->y + node->height; if (node->highlight) { SetDrawColor(HIGHLIGHT_COLOR); SetBkColor (hdc, TreeDrawingAreaDB->colors [HIGHLIGHT_BK_COLOR]); } else { SetDrawColor(TREE_COLOR); SetBkColor (hdc, TreeDrawingAreaDB->colors [BACKGROUND_COLOR]); } ExtTextOut (hdc, pos->x + node->label.xoffset, pos->y + node->label.yoffset, ETO_OPAQUE, &rcNode, node->label.text, node->label.len, NULL); if (node->elision) { POINT pt[3]; pt[0].x = pos->x + node->width - ELISION_WIDTH; pt[0].y = pos->y + 2; pt[1].x = pos->x + node->width - 2; pt[1].y = pos->y + node->height / 2; pt[2].x = pos->x + node->width - ELISION_WIDTH; pt[2].y = pos->y + node->height - 2; RefreshPen (); SelectNewDeleteOld (CreateSolidBrush (GetTextColor (hdc))); Polygon (hdc, pt, 3); } SetDrawColor(TREE_COLOR); RefreshPen (); if (!node->highlight) { SelectNewDeleteOld (GetStockObject (HOLLOW_BRUSH)); Rectangle (hdc, rcNode.left, rcNode.top, rcNode.right, rcNode.bottom); } if (node->focus) DrawFocusRect (hdc, &rcNode); if (node->parent) { MoveToEx (hdc, pos->x - 1, pos->y + (node->height / 2), NULL); LineTo (hdc, parent_pos->x + node->parent->width + 1, parent_pos->y + (node->parent->height / 2)); } #else Widget w; GC gc; w = TreeDrawingArea; gc = TreeDrawingAreaDB->gc; XDrawString(XtDisplay(w), XtWindow(w), gc, pos->x + node->label.xoffset, pos->y + node->label.yoffset, node->label.text, node->label.len); XDrawRectangle(XtDisplay(w), XtWindow(w), gc, pos->x, pos->y, node->width, node->height); if (node->parent) XDrawLine(XtDisplay(w), XtWindow(w), gc, pos->x - 1, pos->y + (node->height / 2), parent_pos->x + node->parent->width + 1, parent_pos->y + (node->parent->height / 2)); if (node->elision) { XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc, FillTiled); XFillRectangle(XtDisplay(w), XtWindow(w), gc, pos->x + node->width - ELISION_WIDTH, pos->y + 1, ELISION_WIDTH, node->height - 1); XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc, FillSolid); } #endif } void DrawNode(node, pos_mode) Tree *node; PosMode pos_mode; { if (pos_mode == Old) DrawNodeHelper (node, &node->old_pos, node->parent ? &node->parent->old_pos : NULL); else DrawNodeHelper (node, &node->pos, node->parent ? &node->parent->pos : NULL); } /* ---------------------------------------------------------------------------- * * DrawTreeContour() draws the contour of the specified subtree. Bridges * are not traversed, so the actual subtree contour is drawn, as opposed * to the merged contour. 'color' specifies the drawing color. If 'detach' * is True, the lines attaching the subtree contour to the node are not * drawn. If 'select' is true, then only subtrees that are flagged as * selected are shown. If 'recursive' is True, the entire tree is traversed. * * ---------------------------------------------------------------------------- */ void DrawTreeContour(tree, pos_mode, color, detach, select, recursive) Tree *tree; PosMode pos_mode; int color; int detach; int select; int recursive; { #ifndef MSW Widget w = TreeDrawingArea; #endif TreePolyline *contour, *tail; Tree *child; int x, y, i; if (tree == NULL) return; if ((select && tree->show_contour) || !select) { SetDrawColor(color); SetLineWidth(TreeContourWidth, color); /* draw upper contour */ contour = tree->contour.upper.head; tail = tree->contour.upper.tail; if (pos_mode == Old) { x = tree->old_pos.x - tree->border; y = tree->old_pos.y - tree->border; } else { x = tree->pos.x - tree->border; y = tree->pos.y - tree->border; } if (detach) { /* skip over attaching lines */ for (i = 0 ; i < 2 ; i++) { x += contour->dx; y += contour->dy; contour = contour->link; } } #ifdef MSW RefreshPen (); MoveToEx (TreeDrawingAreaDB->hdc, x, y, NULL); #endif while (contour) { x += contour->dx; y += contour->dy; #ifdef MSW LineTo (TreeDrawingAreaDB->hdc, x, y); #else XDrawLine(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc, x - contour->dx, y - contour->dy, x, y); #endif if (contour == tail) /* make sure you don't follow bridges */ contour = NULL; else contour = contour->link; } /* draw lower contour */ contour = tree->contour.lower.head; tail = tree->contour.lower.tail; if (pos_mode == Old) { x = tree->old_pos.x - tree->border; y = tree->old_pos.y + tree->border + tree->height; } else { x = tree->pos.x - tree->border; y = tree->pos.y + tree->border + tree->height; } if (detach) { /* skip over attaching lines */ for (i = 0 ; i < 2 ; i++) { x += contour->dx; y += contour->dy; contour = contour->link; } } #ifdef MSW MoveToEx (TreeDrawingAreaDB->hdc, x, y, NULL); #endif while (contour) { x += contour->dx; y += contour->dy; #ifdef MSW LineTo (TreeDrawingAreaDB->hdc, x, y); #else XDrawLine(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc, x - contour->dx, y - contour->dy, x, y); #endif if (contour == tail) /* make sure you don't follow bridges */ contour = NULL; else contour = contour->link; } } if (recursive) { FOREACH_CHILD(child, tree) if (!child->elision) DrawTreeContour(child, pos_mode, color, detach, select, recursive); } SetDrawColor(TREE_COLOR); SetLineWidth(0, TREE_COLOR); } /* ---------------------------------------------------------------------------- * * DrawTree() traverses the given tree, drawing the node and connecting * segments. The tree contours are also drawn at each step, if enabled. * 'draw_mode' specifies the drawing mode in which the tree is drawn. * 'pos_mode' determines whether or not to use the old position of the node. * This flag is used in animating the movement of a node from its old * position to its new position. DrawNode() is called to draw an individual * node. * * ---------------------------------------------------------------------------- */ void DrawTree(tree, pos_mode) Tree *tree; PosMode pos_mode; { if (tree == NULL) return; DrawNode(tree, pos_mode); /* do stuff that animates Unzip() */ if (tree->split) { if (!AnimationMode || (tree->pos.x == tree->old_pos.x && tree->pos.y == tree->old_pos.y)) DrawTreeContour(tree, pos_mode, SPLIT_COLOR, FALSE, FALSE, FALSE); else DrawTreeContour(tree, pos_mode, ACTION_COLOR, FALSE, FALSE, FALSE); } if (tree->on_path) HiliteNode(tree, pos_mode); if (tree->child && !tree->elision) DrawTree(tree->child, pos_mode); if (tree->sibling) DrawTree(tree->sibling, pos_mode); } /* ---------------------------------------------------------------------------- * * ShiftTree() adjusts the positions of each node so that it moves from * the "old" position towards the "new position". This is used by * AnimateTree(). 'done' is set to FALSE if the tree is not in its * final position; it is used to determine when to stop animating the tree. * * ---------------------------------------------------------------------------- */ void ShiftTree(tree, done) Tree *tree; int *done; { Tree *child; if (tree->old_pos.x != tree->pos.x || tree->old_pos.y != tree->pos.y) { tree->old_pos.x = tree->pos.x; tree->old_pos.y = tree->pos.y; } FOREACH_CHILD(child, tree) ShiftTree(child, done); } /* ---------------------------------------------------------------------------- * * AnimateTree() draws the given tree in a series of steps to give the * effect of animation from the "old" layout to the "new" layout of the * tree. * * The algorithm used here is not efficient; the entire tree is drawn * on each iteration of the animation sequence; it would be more efficient * to only redraw what is necessary. However, the method used here takes * advantage of existing code without modification. * * ---------------------------------------------------------------------------- */ void AnimateTree(tree) Tree *tree; { int done = FALSE; AnimationMode = FALSE; /* highlight which nodes have to move */ BeginFrame(); DrawTree(tree, Old); EndFrame(); Pause(); if (PauseAfterStep) AnimationStep = ANIMATION_STEP_STEP; while (!done) { done = TRUE; ShiftTree(tree, &done); BeginFrame(); DrawTree(tree, Old); EndFrame(); if (PauseAfterStep) Pause(); } if (PauseAfterStep) AnimationStep = ANIMATION_STEP; AnimationMode = FALSE; } /* ---------------------------------------------------------------------------- * * AnimateZip() generates a sequence of frames that animates the Zip() step. * It is similar in logical structure to Zip(). * * ---------------------------------------------------------------------------- */ void AnimateZip(tree) Tree *tree; { Tree *child; /* show results of Join() step */ if (tree->child) { BeginFrame(); FOREACH_CHILD(child, tree) child->split = FALSE; DrawTree(TheTree, New); DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE, FALSE, FALSE); EndFrame(); StatusMsg("Zip: merge and join contours", FALSE); Pause(); /* show results of AttachParent() step */ BeginFrame(); DrawTree(TheTree, New); DrawTreeContour(tree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE); EndFrame(); StatusMsg("Zip: attach parents", FALSE); Pause(); } tree->on_path = FALSE; if (tree->parent) AnimateZip(tree->parent); else { tree->on_path = FALSE; BeginFrame(); DrawTree(TheTree, New); DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE); EndFrame(); StatusMsg("Zip: reassemble entire contour", FALSE); Pause(); } } /* ---------------------------------------------------------------------------- * * CountNodes() returns the number of nodes in the specified tree. * Nodes below a node that has been collapsed are ignored. * * ---------------------------------------------------------------------------- */ int CountNodes(tree) Tree *tree; { int num_nodes = 1; /* count root of subtree */ Tree *child; if (!tree->elision) { FOREACH_CHILD(child, tree) num_nodes += CountNodes(child); } return (num_nodes); } /* ---------------------------------------------------------------------------- * * CollectNodeRectangles() is a recursive function used by * GetSubTreeRectangles() to collect the rectangles of descendant nodes * into the pre-allocated storage passed to this function. * * ---------------------------------------------------------------------------- */ void CollectNodeRectangles(node, rectangles, fill) Tree *node; XRectangle **rectangles; int fill; { Tree *child; (*rectangles)->x = node->pos.x; (*rectangles)->y = node->pos.y; if (fill) { (*rectangles)->width = node->width + 1; (*rectangles)->height = node->height + 1; } else { (*rectangles)->width = node->width; (*rectangles)->height = node->height; } (*rectangles)++; if (!node->elision) FOREACH_CHILD(child, node) CollectNodeRectangles(child, rectangles, fill); } /* ---------------------------------------------------------------------------- * * GetSubTreeRectangles() builds an array of XRectangles that contain * all the node rectangles in the tree, except the root node itself. * The array is returned in 'rectangles' and the number of rectangles * is returned in 'nrectangles.' Storage for the rectangles is allocated * in this function. This function is used by PickAction to determine * what rectangles need to be dissolved away. 'fill', if True, specifies * that the rectangles should be 1 pixel larger in each dimension to * compensate for FillRectangle behavior. * * ---------------------------------------------------------------------------- */ void GetSubTreeRectangles(tree, rectangles, nrectangles, fill) Tree *tree; XRectangle **rectangles; int *nrectangles, fill; { Tree *child; XRectangle *crect; /* current rectangle */ *nrectangles = CountNodes(tree) - 1; /* don't count root node */ *rectangles = (XRectangle *) malloc(sizeof(XRectangle) * *nrectangles); ASSERT(*rectangles, "could not allocate memory for rectangles"); crect = *rectangles; if (!tree->elision) FOREACH_CHILD(child, tree) CollectNodeRectangles(child, &crect, fill); } /* ---------------------------------------------------------------------------- * * CollectNodeSegments() is a recursive function used by GetSubTreeSegments() * to collect the line segments connecting nodes into the pre-allocated * storage passed to this function. * * ---------------------------------------------------------------------------- */ void CollectNodeSegments(node, segments) Tree *node; XSegment **segments; { Tree *child; (*segments)->x1 = node->pos.x - 1; (*segments)->y1 = node->pos.y + (node->height / 2), (*segments)->x2 = node->parent->pos.x + node->parent->width + 1; (*segments)->y2 = node->parent->pos.y + (node->parent->height / 2); (*segments)++; if (!node->elision) FOREACH_CHILD(child, node) CollectNodeSegments(child, segments); } /* ---------------------------------------------------------------------------- * * GetSubTreeSegments() builds an array of XSegments that contain * all the line segments connecting the nodes in the tree. The array is * returned in 'segments' and the number of segments is returned in * 'nsegments.' Storage for the segments is allocated in this function. * This function is used by PickAction to determine what line segments * rectangles need to be dissolved away. * * ---------------------------------------------------------------------------- */ void GetSubTreeSegments(tree, segments, nsegments) Tree *tree; XSegment **segments; int *nsegments; { Tree *child; XSegment *cseg; /* current segment */ *nsegments = CountNodes(tree) - 1; *segments = (XSegment *) malloc(sizeof(XSegment) * *nsegments); ASSERT(*segments, "could not allocate memory for segments"); cseg = *segments; if (!tree->elision) FOREACH_CHILD(child, tree) CollectNodeSegments(child, &cseg); } /* ---------------------------------------------------------------------------- * * ComputeSubTreeExtent() computes the extent of a subtree. This is * easily computed based on the tree's contour, as in ComputeTreeSize(). * This extent is stored in the node, and used by SearchTree for * pick-correlation. * * This function assumes that the given tree has at least one child; do not * pass a leaf node to this function. * * ---------------------------------------------------------------------------- */ void ComputeSubTreeExtent(tree) Tree *tree; { int width, height; int x_offset, y_offset; ComputeTreeSize(tree, &width, &height, &x_offset, &y_offset); tree->subextent.pos.x = tree->child->pos.x - tree->child->border; tree->subextent.pos.y = tree->pos.y - y_offset; tree->subextent.width = width - (tree->child->pos.x - tree->pos.x) - 1; tree->subextent.height = height - 1; } /* ---------------------------------------------------------------------------- * * SearchTree() determines if a node's rectangular region encloses the * specified point in (x,y). Rather than using a brute-force search * through all node rectangles of a given tree, the subtree extents * are used in a recursive fashion to drive the search as long as the * given point is enclosed in an extent. In the worst case, the search * time would be on the order of a brute-force search, but with complex * trees, this method reduces the number of visits. * * The extent of a subtree is computed by ComputeSubTreeExtent() and is * stored in each node of the tree. * * ---------------------------------------------------------------------------- */ int SearchTree(tree, x, y, node) Tree *tree, **node; int x, y; { Tree *child; if (tree == NULL) return (FALSE); if (PT_IN_RECT(x, y, tree->pos.x, tree->pos.y, tree->pos.x + tree->width, tree->pos.y + tree->height)) { *node = tree; return (TRUE); } if (tree->child && (PT_IN_EXTENT(x, y, tree->subextent))) FOREACH_CHILD(child, tree) { if (SearchTree(child, x, y, node)) return (TRUE); } return (FALSE); } /* ---------------------------------------------------------------------------- * * ExposeHandler() handles expose events in the TreeDrawingArea. This * function is not intelligent; it just redraws the entire contents. * * ---------------------------------------------------------------------------- */ #ifdef MSW void ExposeHandler (void) { BeginFrame(); SetContours(TreeShowContourOption); DrawTree(TheTree, New); EndFrame(); } #else void ExposeHandler(w, client_data, event) Widget w; caddr_t client_data; XExposeEvent *event; { if (event->count == 0) { BeginFrame(); SetContours(TreeShowContourOption); DrawTree(TheTree, New); EndFrame(); } } #endif /* ---------------------------------------------------------------------------- * * ExpandCollapseNode is called to expand or collapse a node in the tree. * * ---------------------------------------------------------------------------- */ void ExpandCollapseNode(node) Tree *node; { int width, height; int old_width, old_height; int x_offset, y_offset; int expand = FALSE; #ifndef MSW XRectangle *rectangles; XSegment *segments; int nrectangles, nsegments; Widget w = TreeDrawingArea; #endif StatusMsg("", TRUE); /* hilite node so that we know where we are */ /* DrawTree will hilite it as a side effect */ if (TreeShowSteps) node->on_path = TRUE; /* erase the contour before changing in the tree */ if ((TreeShowContourOption != NoContours) || TreeShowSteps) { BeginFrame(); DrawTree(TheTree, New); EndFrame(); } sprintf(strbuf, "Node `%s' selected for %s", node->label.text, node->elision ? "expansion" : "collapse"); StatusMsg(strbuf, FALSE); Pause(); if (node->parent) Unzip(node->parent); else { StatusMsg("Show entire contour", FALSE); if (TreeShowSteps) { BeginFrame(); DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE); DrawTree(TheTree, New); EndFrame(); Pause(); } } /* are we collapsing a subtree? */ if (!node->elision) { #ifndef MSW StatusMsg("Collapse subtree", FALSE); GetSubTreeRectangles(node, &rectangles, &nrectangles, TRUE); GetSubTreeSegments(node, &segments, &nsegments); DissolveTree(XtDisplay(w), XtWindow(w), rectangles, nrectangles, segments, nsegments, TRUE); free(rectangles); free(segments); Pause(); #endif StatusMsg("Replace subtree contour with leaf contour", FALSE); node->elision = TRUE; if (TreeShowSteps) node->split = TRUE; /* turned off in AnimateZip */ node->old_contour = node->contour; node->width += ELISION_WIDTH; LayoutLeaf(node); BeginFrame(); SetContours(TreeShowContourOption); DrawTree(TheTree, New); EndFrame(); Pause(); } else { StatusMsg("Replace leaf contour with old subtree contour", FALSE); if (TreeShowSteps) node->split = TRUE; /* turned off in AnimateZip */ RuboutLeaf(node); node->contour = node->old_contour; expand = TRUE; } if (node->parent) Zip(node->parent); ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset); PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE); GetDrawingSize(&old_width, &old_height); if (expand) { SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE)); BeginFrame(); DrawTree(TheTree, Old); EndFrame(); Pause(); StatusMsg("Move tree to new configuration", FALSE); AnimateTree(TheTree); } else { /* we are shrinking or staying the same */ StatusMsg("Move tree to new configuration", FALSE); AnimateTree(TheTree); SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE)); } if (expand) { StatusMsg("Expand subtree", FALSE); node->elision = FALSE; /* erase elision marker */ #ifdef MSW SelectNewDeleteOld (CreateSolidBrush (GetBkColor (TreeDrawingAreaDB->hdc))); Rectangle (TreeDrawingAreaDB->hdc, node->pos.x + node->width - ELISION_WIDTH, node->pos.y + 1, node->pos.x + node->width, node->pos.y + node->height); #else XSetFunction(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc, GXclear); XFillRectangle(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc, node->pos.x + node->width - ELISION_WIDTH + 1, node->pos.y, ELISION_WIDTH, node->height + 1); XSetFunction(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc, GXcopy); #endif node->width -= ELISION_WIDTH; #ifndef MSW GetSubTreeRectangles(node, &rectangles, &nrectangles, FALSE); GetSubTreeSegments(node, &segments, &nsegments); /* dissolve the tree back in */ DissolveTree(XtDisplay(w), XtWindow(w), rectangles, nrectangles, segments, nsegments, FALSE); free(rectangles); free(segments); #endif /* draw text of nodes */ BeginFrame(); SetContours(TreeShowContourOption); DrawTree(TheTree, New); EndFrame(); Pause(); } if (TreeShowSteps) { node->on_path = FALSE; if (node->parent) AnimateZip(node->parent); else node->split = FALSE; } /* BUG: the display isn't properly updated here! */ /* There should probably be some code here that clears the tree below the node currently being collapsed or expanded. Hack added 20.03.95 (torgeir@ii.uib.no). I'll try to fix this later. */ #ifndef MSW XClearArea(TreeDisplay, XtWindow(TreeDrawingArea), 0, 0, 0, 0, FALSE); BeginFrame(); SetContours(TreeShowContourOption); DrawTree(TheTree, New); EndFrame(); #endif StatusMsg("Ready", TRUE); } /* ---------------------------------------------------------------------------- * * InsertNode() handles the task of inserting a new node in the tree, * at the given position with respect to 'base_node'. When 'node_pos' is * either Before or After, it is assumed that 'base_node' has a parent. * * ---------------------------------------------------------------------------- */ void InsertNode(base_node, node_pos, new_node_text) Tree *base_node; NodePosition node_pos; char *new_node_text; { Tree *new_node; Tree *parent; Tree *sibling = NULL; Tree *child; int width, height; int x_offset, y_offset; StatusMsg("", TRUE); new_node = MakeNode(); /* should check for memory failure */ SetNodeLabel(new_node, new_node_text); LayoutLeaf(new_node); /* figure out parent & sibling */ if (node_pos == Child) { parent = base_node; /* find last child, if one exists */ FOREACH_CHILD(child, parent) sibling = child; } else if (node_pos == After) { parent = base_node->parent; sibling = base_node; } else if (node_pos == Before) { parent = base_node->parent; FOREACH_CHILD(child, parent) if (child->sibling == base_node) { sibling = child; break; } } if (TreeShowSteps) parent->on_path = TRUE; if ((TreeShowContourOption != NoContours) || TreeShowSteps) { BeginFrame(); DrawTree(TheTree, New); EndFrame(); } sprintf(strbuf, "Inserting `%s' as child of node `%s'", new_node_text, parent->label.text); StatusMsg(strbuf, FALSE); Pause(); /* erase the contour before changing in the tree */ Insert(parent, new_node, sibling); ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset); PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE); if (sibling) new_node->old_pos = sibling->old_pos; else if (new_node->sibling) new_node->old_pos = new_node->sibling->old_pos; else { new_node->old_pos.x = new_node->pos.x; new_node->old_pos.y = parent->old_pos.y; } if (TreeShowSteps) new_node->split = TRUE; SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE)); BeginFrame(); DrawTree(TheTree, Old); EndFrame(); StatusMsg("Insert: add new node and contour", FALSE); Pause(); StatusMsg("Move tree to new configuration", FALSE); AnimateTree(TheTree); if (TreeShowSteps) { if (parent) AnimateZip(parent); } BeginFrame(); SetContours(TreeShowContourOption); DrawTree(TheTree, New); EndFrame(); StatusMsg("Ready", TRUE); } /* ---------------------------------------------------------------------------- * * DeleteNode() handles the task of deleting a given node in the tree. * * ---------------------------------------------------------------------------- */ void DeleteNode(node) Tree *node; { Tree *parent; #ifndef MSW XRectangle *rectangles; XSegment *segments; int nrectangles, nsegments; Widget w = TreeDrawingArea; #endif int width, height; int x_offset, y_offset; StatusMsg("", TRUE); if (TreeShowSteps) node->on_path = TRUE; /* erase the contour before changing in the tree */ if ((TreeShowContourOption != NoContours) || TreeShowSteps) { BeginFrame(); DrawTree(TheTree, New); EndFrame(); } sprintf(strbuf, "Node `%s' selected for deletion", node->label.text); StatusMsg(strbuf, FALSE); Pause(); parent = node->parent; if (parent) Unzip(parent); else TheTree = NULL; /* delete root of tree */ /* fade out deleted subtree */ #ifndef MSW StatusMsg("Delete subtree", FALSE); GetSubTreeRectangles(node, &rectangles, &nrectangles, TRUE); GetSubTreeSegments(node, &segments, &nsegments); DissolveTree(XtDisplay(w), XtWindow(w), rectangles, nrectangles, segments, nsegments, TRUE); free(rectangles); free(segments); #endif Delete(node); BeginFrame(); if (TheTree) DrawTree(TheTree, New); EndFrame(); Pause(); if (parent) Zip(parent); if (TheTree) { ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset); PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE); StatusMsg("Move tree to new configuration", FALSE); AnimateTree(TheTree); SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE)); Pause(); if (TreeShowSteps) { if (parent) AnimateZip(parent); } BeginFrame(); SetContours(TreeShowContourOption); DrawTree(TheTree, New); EndFrame(); } StatusMsg("Ready", TRUE); } /* ---------------------------------------------------------------------------- * * ResetLabels() is called when the TreeAlignNodes mode is changed. * When TreeParentDistance changes, the node width changes, so this * function forces each node's width to be recomputed. * * ---------------------------------------------------------------------------- */ ResetLabels(tree) Tree *tree; { Tree *child; SetNodeLabel(tree, tree->label.text); FOREACH_CHILD(child, tree) ResetLabels(child); } /* ---------------------------------------------------------------------------- * * SetupTree() handles the task of setting up the specified tree in * the drawing area. * * ---------------------------------------------------------------------------- */ void SetupTree(tree) Tree *tree; { int width, height; int x_offset, y_offset; LayoutTree(tree); ComputeTreeSize(tree, &width, &height, &x_offset, &y_offset); PetrifyTree(tree, x_offset + MAT_SIZE, y_offset + MAT_SIZE); SetDrawingTree(tree); SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE)); BeginFrame(); SetContours(TreeShowContourOption); DrawTree(tree, New); EndFrame(); }