Untitled

/******************************************************************************
 *
 * This module implements a function to create an SVG drawing of your Red-Black
 * tree. It should be relatively easily-integrated in your own code.
 *
 * Data structures (themselves are pointers to structs):
 * 1. rb_tree contains (at least) a pointer to the `root' of your tree, and a
 * pointer to a `nil' element.
 * 2. rb_node contains (at least) a pointer to its left child, `lchild', a
 * pointer to its right child, `rchild', a character `color' which is either
 * b or r, and an int `key'.
 *
 * You should probably have some data structures which are relatively similar,
 * and can easily substitute your own. If you're using C++, it should be easy to
 * integrate, as well: just change all the static methods to private member
 * methods, and twiddle all the arguments around to your calling conventions.
 *
 * To call the method, you just call `RBdraw(your_tree, a_file_name)'. If your
 * tree has no nodes in it, the method just returns, and if it cannot open the
 * specified file, it prints an error method and returns.
 *
 * The drawing looks best when the keys have between 1 and 3 digits, and if
 * there's too many nodes, it'll look pretty squished (in order to not be like
 * 100k pixels wide).
 *
 *
 *
 * -- Louis Wilson, Nov 2011
 *
 ******************************************************************************/


#include "RB_SVG.h"
#include "RBtree.h
/* Draws a subtree rooted at a node n */
static void rb_draw_subtree(FILE *fp, rb_tree tree, rb_node n, double x, double y,
                int h, int rowpos, double factor);
/* Calculates x position of circle exp rows from the top, at position rowpos in
 * its row. factor corrects for an image which would be greater than MAXWIDTH. */
static double calcpos(int exp, int rowpos, double factor);
/* Computes height of the tree rooted at node n. */
static int rb_height(rb_tree tree, rb_node n);


/* Draws an SVG picture of the tree in the specified file. */
void RBdraw(rb_tree tree, char *fname) {
        FILE *fp; /* file to print to */
        int height = rb_height(tree, tree->root); /* height of the tree */
        int width; /* width of the image */
        int adjwidth; /* adjusted width of the image in px */
        double factor; /* adjust factor for the node positions based on width and adjwidth */
        if (height == 0) return;
        if ((fp = fopen(fname, "w")) == NULL) {
                fprintf(stderr, "Error: couldn't open %s for writing.\n", fname);
                return;
        }
        /* Calculate width of drawing, and distance factor for nodes. */
        width = (1<<(height-1)) * (2*RADIUS + PADDING) - PADDING + 2*IMGBORDER;
        adjwidth = (width > MAXWIDTH) ? MAXWIDTH : width;
        factor = (height == 1) ? 1.0 : (adjwidth-2*(RADIUS+IMGBORDER)) / (width-2*(RADIUS+IMGBORDER));
        /* Print out the SVG header */
        fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n"
                "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n"
                "<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\" width=\"%dpx\" height=\"%dpx\" "
                "style=\"background-color:white\">\n",
                adjwidth, (int)(height * (2*RADIUS + PADDING) - PADDING + 2*IMGBORDER));
        /* Draw the tree */
        rb_draw_subtree(fp, tree, tree->root, calcpos(height-1, 0, factor), RADIUS+IMGBORDER, height-1, 0, factor);
        /* SVG footer */
        fputs("</svg>\n", fp);
        fclose(fp);
}
static void rb_draw_subtree(FILE *fp, rb_tree tree, rb_node n, double x, double y,
                int h, int rowpos, double factor) {
        char *col = (n->color == 'b') ? "black" : "red";
        /* pixel y position for next row */
        double ny = y + 2*RADIUS + PADDING;

        /* Draw left subtree */
        if (n->lchild != tree->nil) {
                /* pixel x position of left child */
                double nx = calcpos(h-1, 2*rowpos, factor);
                fprintf(fp, "<line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\" "
                        "style=\"stroke:black;stroke-width:1\"/>\n",
                        x, y, nx, ny);
                rb_draw_subtree(fp, tree, n->lchild, nx, ny, h-1, 2*rowpos, factor);
        }
        /* Draw right subtree */
        if (n->rchild != tree->nil) {
                /* pixel x position of right child */
                double nx = calcpos(h-1, 2*rowpos+1, factor);
                fprintf(fp, "<line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\" "
                        "style=\"stroke:black;stroke-width:1\"/>\n",
                        x, y, nx, ny);
                rb_draw_subtree(fp, tree, n->rchild, nx, ny, h-1, 2*rowpos+1, factor);
        }
        /* Draw the node itself */
        fprintf(fp, "<circle cx=\"%f\" cy=\"%f\" r=\"%f\" stroke=\"black\" "
                "stroke-width=\"1\" fill=\"%s\"/>\n", x, y, RADIUS, col);
        /* And write the node key */
        fprintf(fp, "<text x=\"%f\" y=\"%f\" fill=\"white\" text-anchor=\"middle\" "
                "dy=\"0.5ex\">%d</text>\n", x, y, n->key);
}
static double calcpos(int exp, int rowpos, double factor) {
        /* This equation took quite a bit of diagramming on paper to come up with. */
        return ((1<<exp) * (2*rowpos+1) - 1) * (RADIUS + PADDING/2) * factor + RADIUS + IMGBORDER;
}
static int rb_height(rb_tree tree, rb_node n) {
        int l, r;
        if (n == tree->nil) return 0;
        l = rb_height(tree, n->lchild);
        r = rb_height(tree, n->rchild);
        return 1 + ((l > r) ? l : r);
}