//-----------------------------------------------------------------------------
// Copyright © 2003 - Philip Howard - All rights reserved
//
// 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 2
// of the License, 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
//-----------------------------------------------------------------------------
// package	libh/avl
// homepage	http://libh.slashusr.org/
//-----------------------------------------------------------------------------
// author	Philip Howard
// email	libh at ipal dot org
// homepage	http://phil.ipal.org/
//-----------------------------------------------------------------------------
// This file is best viewed using a fixed spaced font such as Courier
// and in a display at least 120 columns wide.
//-----------------------------------------------------------------------------

//-----------------------------------------------------------------------------
// program	linefreq
//
// purpose	Count the frequency of different line lines in the input.
//
//		Demonstrate how single node can be defined to have 2 tree
//		links allowing each instance to be in 2 tree classes at
//		the same time.
//
// syntax	linefreq ["sepchars"] < infile
//-----------------------------------------------------------------------------
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <libh/avl.h>
#include <libh/io.h>

#define LINESIZE	256

//-----------------------------------------------------------------------------
// Define a struct that implements a link for a character string key.
// Define a struct that implements a link for an unsigned long key.
// Define a struct that implements a node to carry both links together.
// Define a function that compares the character string keys in two links.
// Define a function that compares the unsigned long keys in two links.
//-----------------------------------------------------------------------------
struct link_str {
    avl_link		link		;
    char *		key		;
};

struct link_ul {
    avl_link		link		;
    unsigned long	key		;
};

struct node {
    struct link_str	line		;
    struct link_ul	count		;
    char		data	[16]	;
};

static int cmp_str( avl_link * arg_one, avl_link * arg_two, AVL * arg_tree )
{
    return strcmp(
	((struct link_str *)arg_one)->key,
	((struct link_str *)arg_two)->key
    );
}

static int cmp_ul( avl_link * arg_one, avl_link * arg_two, AVL * arg_tree )
{
    return ( ((struct link_str *)arg_one)->key < ((struct link_str *)arg_two)->key ) ?
	-1 : ( ((struct link_str *)arg_one)->key > ((struct link_str *)arg_two)->key ) ? 1 : 0;
}

//-----------------------------------------------------------------------------
// function	main
//-----------------------------------------------------------------------------
int
main (
    int		argc
    ,
    char * *	argv
    )
{
    AVL			by_line		;
    AVL			by_count	;
    struct link_str	key_line	;
    struct node *	node_p		;
    char		line		[ LINESIZE ];


    //------------------------------
    // Initialize both binary trees.
    //------------------------------
    avl_init( & by_line, struct node, line, cmp_str );
    avl_init( & by_count, struct node, count, cmp_ul );

    //-------------------------------------------------------------------
    // Initialize a struct used as the lookup key with the array address.
    //-------------------------------------------------------------------
    key_line.key = line;

    //--------------------------------------------------------------
    // Read every line from standard input to count them one by one.
    //--------------------------------------------------------------
    while ( 0 <= get_line_file( line, LINESIZE, stdin ) ) {

        //------------------------------------------------------------
        // If the node is found, increment the count for another word.
        // If not, create a new one with a count of 1 and insert it.
        //------------------------------------------------------------
	if ( ( node_p = avl_find_exact( & by_line, & key_line ) ) ) {
	    node_p->count.key ++;
	} else {
	    if ( ! ( node_p = malloc( sizeof (struct node) - 16 + strlen( line ) + 1 ) ) ) {
		perror( "malloc" );
		return 1;
	    }
	    node_p->count.key = 1;
	    strcpy( ( node_p->line.key = node_p->data ), line );
	    avl_insert( & by_line, node_p );
	}
    }

    //-----------------------------------------------------------------------
    // Step through all the lines in the "by line" tree and insert them into
    // the "by count" tree.  Duplicates have to be allowed because many lines
    // may have the same count.
    //-----------------------------------------------------------------------
    avl_loop_forward( & by_line, node_p ) {
	avl_insert_dup( & by_count, node_p );
    }

    //---------------------------------------------------------
    // Print all the lines with count form the "by count" tree.
    //---------------------------------------------------------
    avl_loop_reverse( & by_count, node_p ) {
	printf( "%11lu %s\n", node_p->count.key, node_p->line.key );
    }

    return 0;
}