/* $Id: nodeop.c,v 3.1 2005/02/19 08:29:53 mac Exp $
 *
 * nodeop.c
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation, and that the authors name not be used in
 * advertising or publicity pertaining to distribution of the software
 * without specific, written prior permission.  The author makes no
 * representations about the suitability of this software for any purpose.
 * It is provided "as is" without express or implied warranty.
 */
#include "du2ps.h"
unsigned dhue;

Node *top;
int (*cmp)();

static void
drawrect(Node *nodep, double y, double height, int depth,
		unsigned h, unsigned s, unsigned b)
{
	printf("%d (%s \\(%d\\)) %.2f %.2f %f %f %f\n",
        depth, nodep->name, nodep->size, height, y,
	(double) h / 0x8000 , (double) s, (double) b);
}

/*
 * create a new node with the given name and set other initial values
 */
static Node *
makenode(char *name)
{
	Node *nodep;

	if (NULL == (nodep = (Node *) malloc(
		(unsigned) (sizeof(Node) + strlen(name) + 1)))) {
		fprintf(stderr, "malloc error\n");
		exit (ENOMEM);
	}
	nodep->child = nodep->peer = NODE_NULL;
	nodep->nchild = nodep->size = 0;
	nodep->name = (char *) &nodep[1];
	strcpy(nodep->name, name);
	return nodep;
}


static void
addtree(Node *nodep, char **path, int size)
{
	Node *child;

	/* check all children for a match */
	for(child = nodep->child; NODE_NULL != child; child = child->peer){
		if(!strcmp(path[0], child->name)) break;
	}

	if (NODE_NULL == child) {
		child = nodep->child;
		nodep->child = makenode(path[0]);
		nodep->child->peer = child;
		child = nodep->child;
		nodep->nchild++;
	}

	if (NULL == path[1]) {
		child->size = size;
	}
	else {
		addtree(child, &path[1], size);
	}
	return;
}

int
cmp_alph(Node **p, Node **q)
{
	return strcmp((*p)->name, (*q)->name);
}

int
cmp_size(Node **p, Node **q)
{
	return ((*q)->size - (*p)->size);
}

static void
sorttree(Node *nodep)
{
	Node *child;
	Node **nodtbl;
	int i, ind;

	if (NODE_NULL == nodep->child) return;

	if (NULL == (nodtbl = (Node **) malloc(
		sizeof(Node *) * nodep->nchild))) {
		fprintf(stderr, "malloc error\n");
		exit (ENOMEM);
	}

	for(child = nodep->child, ind = 0;
		NODE_NULL != child; child = child->peer, ind++){
		nodtbl[ind] = child;
		if (NODE_NULL != child->child) {
			sorttree(child);
		}
	}

	if (2 <= nodep->nchild) {
		qsort((char *) nodtbl, nodep->nchild, sizeof(Node *), cmp);

		nodep->child = nodtbl[0];
		for (i = 1; i < nodep->nchild; ++i) {
			nodtbl[i - 1]->peer = nodtbl[i];
		}
		nodtbl[i - 1]->peer = NODE_NULL;
	}

	free(nodtbl);

	return;
}


static void
drawchildren(Node *nodep, double y, double h, int depth)
             /* node whose children we should draw */
            
          
{
	Node *np;
	double height;
	unsigned hue;
	int s, b;

    /* for each child */
	hue = 0;
	s = b = 1;
	for(np = nodep->child; NODE_NULL != np; np = np->peer){
		if (nodep->size == 0) {
			return;
		}
		height = h * np->size / nodep->size;
		if (dhue != 0) {
			drawrect(np, y, height, depth, hue, s, b);
			hue += dhue;
			hue %= 0x8000;
		}
		else {
			drawrect(np, y, height, depth, 0, 0, 1);
		}
		/* draw children in subrectangle */
		drawchildren(np, y, height, depth + 1);
		y -= height;
    }
}

/*
 * reads du output,
 * builds hierarchy structure,
 * returns the top directory name.
 */
#define MAXLL MAXPATH+80
char *
parse(void)
{
	char buf[MAXLL], name[MAXPATH+2], *n;
	char *path[MAXDEPTH]; /* break up path into this list */
	int depth, size;
	int i;

	top = makenode("..");
	while(fgets(buf, MAXLL, stdin)  != 0){
		sscanf(buf, "%d %s\n", &size, n = name);
		if('/' == *n) {
			if ( strlen(name) > MAXPATH ) {
				fprintf(stderr, "too long path\n");
				exit(ENAMETOOLONG);
			}
			for(i = strlen(name)+1; i >= 0; i--) {
				name[i+1] = name[i];
			}
			name[0] = '.';
		}
		if ( name[0] == '.' && name[1] == '/' && name[2] == EOS ) {
			name[1] = EOS;
		}
		path[depth = 0] = n;
			
		for(; *n != EOS; n++){
			if('/' == *n){
				*n = EOS;
				path[++depth] = n + 1;
				if(depth > MAXDEPTH) break;
			}
		}
		path[++depth] = NULL;
		addtree(top, path, size);
	}
	sorttree(top);

	/*
	 * descend hierarchy until the number of children is not 1.
	 * if the directory size is 0, then total the sizes of the children.
	 */
	for(n = name; 0 == top->size;){
		Node *np;

		if (1 == top->nchild) {
			top = top->child;
			while (EOS != *n) n++;
			*n = '/';
		}
		else if(1 < top->nchild){
			for(np = top->child; NODE_NULL != np; np = np->peer){
				top->size = top->size + np->size;
			}
			break;
		}
		else break;
	}
	*n = 0;
	return strdup(name);
}

void
drawnode(double canvas_height)
{
	/* draw the top directory */
	drawrect(top, canvas_height, canvas_height, 0, 0, 0, 1);
	/* draw children recursively */ 
	drawchildren(top, canvas_height, canvas_height, 1);
}