Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35
/* Zapocet 30. kvetna 2007 14:00, Adam Nohejl (to jsem jako ja, autor zdrojaku) */

/*
 * Zadani:
 *
 * Zaznamej retezce odpovidajici definici identifikatoru v C (tzn. zacina pismenem nebo potrzitkem, dale obsahuje i cislice)
 * na standardnim vstupu.
 * Vystup: Retezce setridene podle poctu vyskytu se seznamem radek, na kterych se vyskytovaly ve vzestupnem poradi:
 *  NejcastesiSlovo: radka1 radka2 ... radkan
 *  DalsiSlovo: ...
 *  atd.
 *
 *
 * Reseni:
 *
 * Ja tam mam hashovani, ale je to snad az zbytecne dobre. Pry stacily nejake setridene spojaky nebo co. Vadilo by jedine,
 * kdyby se alokovala zbytecna pamet pro opakovane vyskyty retezce, velka nevyuzita pole apod. Osetrene maji byt vsechny libovolne dlouhe
 * a podivne vstupy s libovolne dlouhymi radky apod.
 */

/*
 * Ceske komentare jsou dopsany dodatecne, aby to bylo k necemu uzitecne i pro vas ostatni, jinak je to napsano tak,
 * jak jsem to napsal tam, tak me nekamenujte, jestli jsou tam nejake blbosti;):
 */

#include "stdafx.h"		/* Jen pro Visual Studio */
#include <stdio.h>		/* getchar(), fprintf(), ... */
#include <string.h>		/* strcpy() */
#include <stdlib.h>		/* malloc(), calloc() */
#include <ctype.h>		/* isalpha(), ... */
#include <assert.h>		/* assert() pouzivam i tam, kde by melo byt opravdicke testovani (ferror() apod.) aspon neco:) */


#define IBUFSIZE	0x100	/* velikost docasneho bufferu na identifikatory, meli jsme povoleno omezit konstatnou */
#define HASHSIZE	101		/* velikost hashovaci tabulky, prvocislo */

/* Umisteni identifikatoru (tzn. cislo radku), jako prvek spojoveho seznamu: */

typedef struct IdPlace{
	unsigned		line;
	struct IdPlace*	next;
} IdPlace;


/* Polozka hashovaci tabulky, jedna pro kazdy identifikator, obsahuje retezec,
 * pocet vyskytu, ukazatel na spojak umisteni, opet jako prvek spojaku (v tomto pripade pro reseni kolizi) */

typedef struct IdEntry{
	const char*		s;
	unsigned		count;
	IdPlace*		place;
	struct IdEntry*	next;
} IdEntry;

static char*		mystrdup(	const char* s);										/* obdoba POSIX strdup() - alokace a kopie */
static unsigned		strhash(	const char* s);										/* hashovaci fce pro retezce */
static int			addEnt(		IdEntry** htable, const char* s, unsigned line);	/* pridani polozky do hasovaci tabulky */
static IdEntry**	entries(	IdEntry** htable, unsigned count);					/* pole polozek v hasovaci tabulce pro predani qsortu */
static int			cmpEnt(		const void* a, const void* b);						/* porovnani polozek dle poctu vyskytu */
static void			prnEnt(		IdEntry** etable, unsigned count);					/* vypsani polozky */
static void			prnPlc(		const IdPlace* p);									/* vypsani umisteni ve zpetnem poradi */

/* No a zbytek je jasny: */

int main(int argc, char** argv){
	unsigned	line			= 1;
	unsigned	uniqueCount		= 0;
	IdEntry*	itab[HASHSIZE]	= {NULL};
	char		ibuf[IBUFSIZE];
	IdEntry**	ilist;
	unsigned	i=0;
	
	int			c;
	
	
	while( ( c = getchar()) != EOF){
		
		
		if(!i  /* no identifier chars read yet */ ){
			if( isalpha(c) || (c == '_') )
				ibuf[i++]	= c;
		}else if( isalnum(c) || (c == '_') ){
			if(i == IBUFSIZE-1)
				fprintf(stderr, "Identifier too long at line %i, ignoring the trailing chars.\n", line);
			else
				ibuf[i++]	= c;
		}else{
			/* end of identifier */
			ibuf[i]	= '\0';
			if(addEnt(itab, ibuf, line))
				uniqueCount++;
			i = 0;
		}
		
		if(c == '\n'){
			line++;
		}
	}
	
	assert(! ferror(stdin) );
	
	ilist	= entries(itab, uniqueCount);
	
	qsort(ilist, uniqueCount, sizeof(IdEntry*), cmpEnt);
	
	prnEnt(ilist, uniqueCount);
		
	return 0;
}

static char*	mystrdup(const char* s){
	char* t		= (char*) malloc(strlen(s) + 1);
	return (t) ? strcpy(t,s) : NULL; 
}

static unsigned		strhash(const char* s){
	unsigned h = 0;
	while(*s)
		h = h*31 + *(const unsigned char*)s++;
	return h % 31;
}

static int			addEnt(	IdEntry** htable, const char* s, unsigned line){
	unsigned	isnew	= 0;
	unsigned	h		= strhash(s);
	IdEntry*	e;
	IdPlace*	p;
	
	for(
		e	= htable[h];
		e && strcmp(s, e->s);
		e	= e->next
		)
		;
	
	if(!e){
		e			= (IdEntry*) calloc(1, sizeof(IdEntry));
		e->s		= mystrdup(s);
		e->next		= htable[h];
		htable[h]	= e;
		isnew		= 1;
	}
	
	e->count++;
	p				= (IdPlace*) calloc(1, sizeof(IdPlace));
	p->line			= line;
	p->next			= e->place;
	e->place		= p;
	
	return isnew;
}


static IdEntry**	entries( IdEntry**  htable, unsigned	count){
	IdEntry**	et	= (IdEntry**) malloc( count * sizeof(IdEntry*) );
	unsigned	i	= 0;
	unsigned	h;
	
	for(h = 0; h < HASHSIZE; h++){
		IdEntry* e;
		for( e	= htable[h]; e; e	= e->next ){
			assert(i < count);
			et[i++] = e;
		}
	}
	
	assert(i==count);
	
	return et;
}

static int			cmpEnt(		const void* a, const void* b){
	return  (*((const IdEntry**)b))->count - (*((const IdEntry**)a))->count;
}

static void			prnEnt(		IdEntry** etable, unsigned count){
	unsigned i;
	
	for(i = 0; i < count ; i++){
		printf("%s:", etable[i]->s);
		prnPlc(etable[i]->place);
		putchar('\n');
	}
}

static void			prnPlc(		const IdPlace* p){
	if(!p)
		return;
	prnPlc(p->next);
	printf(" %u", p->line);
}