/************************************************************************
 * tree.c
 * Copyright (C) 2002 Marcello Barnaba
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 1, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * today i planted a little tree . . .  :)
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <string.h>
#include <errno.h>
#include <err.h>

extern int errno;

#ifndef __GNUC__
typedef unsigned char u_char;
typedef unsigned short u_short;
typedef unsigned int u_int;
typedef unsigned long u_long;
#endif

typedef u_char uint8_t;
typedef u_short uint16_t;
typedef u_long uint32_t;
#ifdef _WIN32
typedef char int8_t;
typedef short int16_t;
typedef long int32_t;
#endif

typedef struct tnode
{
    u_char *word;
    uint32_t count;
    uint16_t first_occ, last_occ;
    struct tnode *left, *right;
} Tnode;

#define BUFSZ		64

#define MODE_INORDER	0x1
#define MODE_PREORDER	0x2
#define MODE_POSTORDER	0x4


static __inline__ void version(char *me)
{
    fprintf(stderr, "%s: version 0.6\n", me);
}

static __inline__ void usage(char *me)
{
    fprintf(stderr, "%s: usage:\n"
	    "  -f <file>  --  use <file> as your input\n"
	    "  -h         --  this crap\n"
	    "  -v         --  version crap\n"
	    "  -i         --  print in-order tree (default)\n"
	    "  -p         --  print pre-order tree\n"
	    "  -P         --  print post-order tree\n",
	    me);
}

static __inline__ void *xmalloc(size_t sz)
{
    void *ret = malloc(sz);
    if(ret == NULL)
	err(-1, "out of memory");
    return ret;
}

static __inline__ char *xstrdup(char *b)
{
    char *ret = strdup(b);
    if(ret == NULL)
	err(-1, "out of memory");
    return ret;
}

static __inline__ Tnode *talloc(void)
{
    Tnode *t = (Tnode *) xmalloc(sizeof(Tnode));
    memset(t, 0x0, sizeof(Tnode));
    return t;
}

static void tree_add(Tnode **t, char *s, int32_t occ)
{
    int32_t lex = 0;

    if(*t == NULL)
    {
	*t = talloc();
	(*t)->word = xstrdup(s);
	(*t)->count = 1;
	(*t)->first_occ = (*t)->last_occ = occ;
    }
    else if ((lex = strcmp(s, (*t)->word)) == 0)
    {
	(*t)->count++;
	(*t)->last_occ = occ;
    }
    else if (lex > 0)
	tree_add(&(*t)->right, s, occ);
    else
	tree_add(&(*t)->left, s, occ);
}

static void tree_print(Tnode *t)
{
    if(t)
    {
	tree_print(t->left);
	printf("%-20s : count: %5ld, f_o: %5d, l_o: %5d\n",
		t->word, t->count, t->first_occ, t->last_occ);
	tree_print(t->right);
    }
}

static void tree_print_pre(Tnode *t)
{
    if(t)
    {
	printf("%-20s : count: %5ld, f_o: %5d, l_o: %5d\n",
		t->word, t->count, t->first_occ, t->last_occ);
	tree_print_pre(t->left);
	tree_print_pre(t->right);
    }
}

static void tree_print_post(Tnode *t)
{
    if(t)
    {
	tree_print_post(t->left);
	tree_print_post(t->right);
	printf("%-20s : count: %5ld, f_o: %5d, l_o: %5d\n",
		t->word, t->count, t->first_occ, t->last_occ);
    }
}

int main(int argc, char **argv)
{
    FILE *in;
    u_char *file = NULL, buf[BUFSZ] /* XXX */;

    extern int optind;
    extern char *optarg;

    int32_t c, wnum;

    uint16_t modes = 0;

    Tnode *root = NULL;

    while((c = getopt(argc, argv, "f:vhipP")) != -1)
    {
	switch(c)
	{
	    case 'f':
		file = xstrdup(optarg);
		break;
	    case 'v':
		version(argv[0]);
		exit(0);
		break;
	    case 'h':
		usage(argv[0]);
		exit(1);
		break;
	    case 'i':
		modes |= MODE_INORDER;
		break;
	    case 'p':
		modes |= MODE_PREORDER;
		break;
	    case 'P':
		modes |= MODE_POSTORDER;
		break;
	    case '?':
		switch(optopt)
		{
		    case 'f':
			exit(1);
		}
	}
    }

    argv += optind;
    argc -= optind;

    modes = modes ? : MODE_INORDER;

    if(!file || (file[0] == '-' && file[1] == '\0'))
    {
	in = stdin;
	fprintf(stderr, "using standard input as input stream.\n");
    }
    else if((in = fopen(file, "r")) == NULL)
	err(1, "Cannot open input file %s", file);

    wnum = 1;
    while(fscanf(in, "%64s", buf) != EOF)
	tree_add(&root, buf, wnum++);

    if(modes & MODE_INORDER)
    {
	printf("*** inorder-traversal ***\n");
	tree_print(root);
    }
    if(modes & MODE_PREORDER)
    {
	printf("*** preorder-traversal ***\n");
	tree_print_pre(root);
    }
    if(modes & MODE_POSTORDER)
    {
	printf("*** postorder-traversal ***\n");
	tree_print_post(root);
    }

    return 0;
}