/* -*- linux-c -*-
 * Connection finder, distribute under GPL version 2 or later
 * Copyright 2000 Pavel Machek <pavel@ucw.cz>
 * Copyright 2000 Martin Hejna <m.hejna@worldonline.cz>
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <time.h>
#include <ctype.h>
#include <errno.h>

#define MEMORY_FILE	"hledac.memory"
#define MEMORY_SIZE 	(64*1024*1024)
#define MEMORY_START	(0x60000000)
#define GRP_CHAR	'+'

int pargc;
char **pargv;
char *filename = "vlak.tt";

const char mes[12][5]={"I","II","III","IV","V","VI",
		       "VII","VIII","IX","X","XI","XII"};

int defod=528,defdo=10609;            //rok(0/1)*10000+mesic*100+den

int matches(char *pomret,struct tm *tcas)
{
	int kladno=0,podm,prir=0;
        int d1,d2,d3;
        char s1[1024];
        int odd=defod,dod=defdo,oddon;
        int oddojede=0;
	int pomjede=0;

        if (pomret==NULL) return 1;
        pomjede=1;
	if (!memcmp(pomret,"t.è. nejede",11)) return 0;

	for(;;) {
	        podm=-1;
                if (pomret[prir]==0) return pomjede;
		if (!memcmp(pomret+prir,"jede",4)) {
                	kladno=1;
                        pomjede=0;
                        prir+=4;
                        continue;
                }
		if (!memcmp(pomret+prir,"nejede",6)) {
                	if (prir==0) pomjede=1;
	                        else if (!pomjede) return 0;
                	kladno=0;prir+=6;
                        continue;
                }
	        if (!memcmp(pomret+prir,"v",1)) {
	        	podm=0;
	        	prir+=2;
	                d3=1;
	                while (d3) {
		                d3=sscanf(pomret+prir,"%d-%d",&d1,&d2);
                                if (d3==-1 || d3==0) break;
	        	        if (d3==1) {
                                	if (pomret[prir+1]!=' ' && pomret[prir+1]!=','
                                        	&& pomret[prir+1]!=0)
                                        	{prir-=1;break;}
	                                d2=d1;prir+=1;
                                }
		        		else prir+=3;
        	                if (d1<=tcas->tm_wday && tcas->tm_wday<=d2) podm=1;
	                        while (pomret[prir]==' ') prir++;//k carce
	                        if (pomret[prir]==',') prir++;	//za carku
			}

		        if (podm!=-1) {
		        	if (kladno) pomjede|=podm;
	        	        else pomjede&=!podm;
		        }
                        continue;
	        }
                if (isdigit(pomret[prir])) {
                	d3=1;
                        podm=0;
                        while (d3) {
                        	d3=sscanf(pomret+prir,"%d.",&d1);
                                if (d3==0 || d3==-1) break;
                                if (d1==tcas->tm_mday) podm=1;
                                prir+=2;
                                if (d1>9) prir++;   // za tecku
                                while (pomret[prir]==' ') prir++;
                                if (pomret[prir]==',') {prir++;continue;}
                                d2=0;
                                while (pomret[prir]==' ') prir++;
                                while (pomret[prir]!='.') {
                                	s1[d2++]=pomret[prir++];
                                        if (pomret[prir]==0) return 2;
				}
                                s1[d2]=0;
                                prir++;    //za tecku
                                for (d1=1;d1<=12;d1++)
                                	if (!strcmp(mes[d1-1],s1) &&
                                        	d1!=tcas->tm_mon) podm=0;
                                break;
                        }

		        if (podm!=-1) {
		        	if (kladno) pomjede|=podm;
	        	        else pomjede&=!podm;
		        }
                        continue;
                }
	        if (!memcmp(pomret+prir,"od",2)) {
                        return 2;
                	prir+=3;
                        podm=0;
                       	sscanf(pomret+prir,"%d.",&d1);
       	                prir+=2;
               	        if (d1>9) prir++;   // za tecku
                        d2=0;
       	                while (pomret[prir]!='.')
               	        	s1[d2++]=pomret[prir++];
                       	s1[d2]=0;
                        prir++;    //za tecku
       	                for (d2=1;d2<=12;d2++)
               	        	if (!strcmp(mes[d2-1],s1)) break;
                        odd=d2*100+d1;
                        if (odd<=(defdo%10000)/100) odd+=10000;
                        oddon=(tcas->tm_mon)*100+tcas->tm_mday;
                        if (oddon<=(defdo%10000)/100) oddon+=10000;

		        if (podm!=-1) {
		        	if (kladno) pomjede|=podm;
	        	        else pomjede&=!podm;
		        }
                        continue;
                }
	        if (!memcmp(pomret+prir,"do",2)) {
                        return 2;
                	prir+=3;
                        podm=0;
                       	sscanf(pomret+prir,"%d.",&d1);
       	                prir+=2;
               	        if (d1>9) prir++;   // za tecku
                        d2=0;
       	                while (pomret[prir]!='.')
               	        	s1[d2++]=pomret[prir++];
                       	s1[d2]=0;
                        prir++;    //za tecku
       	                for (d2=1;d2<=12;d2++)
               	        	if (!strcmp(mes[d2-1],s1)) break;
                        dod=d2*100+d1;
                        if (dod<=(defdo%10000)/100) dod+=10000;
                        oddon=(tcas->tm_mon)*100+tcas->tm_mday;
                        if (oddon<=(defdo%10000)/100) oddon+=10000;
                        if (odd<=oddon && oddon<=dod) oddojede=1;

		        if (podm!=-1) {
		        	if (kladno) pomjede|=podm;
	        	        else pomjede&=!podm;
		        }
                        continue;
                }
	        if (!memcmp(pomret+prir,"a",1)) {
                	return 2;
                }

                if (pomret[prir]==' ') {prir++;continue;}
                if (pomret[prir]==',') {prir++;continue;}

                //neznamy znak
                return 2;
	}
}


int connection_forbidden(char *vlak)
{
	int cykl;
        for (cykl=5;cykl<pargc;cykl++) {
        	if (!strncmp(pargv[cykl], vlak, strlen(pargv[cykl])))
			return 1;
        }
        return 0;
}

typedef unsigned char uchar;

struct id {
	char *name;
        char *cond;	/* Condition which days the train goes */
	/* Hmm, if train starts at 23:00 and arrives at 1:00, and goes on fridays only, when does it go? */
        char *note;     /* Train note */
};

struct node {
	int time1, time2;
	struct town *from, *to;
	struct node *next;
	struct id *id;
	int length;
};

struct town {
	uchar *name;
	struct town *next;
	struct node *nodes;
	int time;		/* changed at runtime */
	int final;		/* changed at runtime */
	struct node *by;	/* changed at runtime */
	int heapindex;		/* changed at runtime */	
};

#define HASHSIZE 60000
#define INF 99999

struct state {
	struct town *townhash[HASHSIZE];
	int numtowns;
	int numnodes;
};

struct state *state;

int finalized = -1;

struct town **townheap;

uchar *memory, *memory_end;

char *opts = "";
int details = 0;
int mode = 0;
#define LIST 1
#define FILTER 2
int slow = 0;
struct tm date; /* FIXME: this is broken. We can travel more than one day, etc. */

#define DTL_STATIONS	1
#define DTL_NOTE	2
#define DTL_COND	4
#define DTL_DEST        8
#define DTL_HEAD        16
#define DTL_TAIL        32
#define DTL_SUM        	64

void *my_malloc(int size)
{
	void *res = memory;
	memory += size;
	if (memory>memory_end) {
		fprintf( stderr, "Allocated memory exhausted\n" );
		exit(5);
	}
	return res;
}

struct town *get_town(uchar *name, int create)
{
	int hash = (name[0] + 64*name[1] + (64*64)*name[2] + (64*64*64)*name[3])%HASHSIZE;
	struct town *res = state->townhash[hash];

	while (res != NULL) {
		if (!strcmp(res->name, name))
			return res;
		res = res->next;
	}
	if (!create)
		return NULL;	

	res = my_malloc(sizeof(struct town));
	memset(res, 0, sizeof(struct town));
	res->name = my_malloc(strlen(name)+1);
	strcpy(res->name, name);
	res->next = state->townhash[hash];
	res->time = INF;
	state->townhash[hash] = res;
	state->numtowns++;
	return res;
}


int pstate = 0, curtime, curkm, lasttime;

struct town *
decodeline(struct id *id, uchar *buf, struct town *prev)
{
	int i = 0;
	char *townname;
	int t1 = -1, t2 = -1, from = -1, to = -1, km = -1;

	if (buf[i]!='\t') {
		if (sscanf( buf+i, "%d:%d", &t1, &t2 ) == 2)
			from = t1*60+t2;
		else	if (sscanf (buf+i, "+%d", &t1 ) != 1) {
			fprintf( stderr, "Could not find from time on %s", buf );
			exit(1);
		} else	from = lasttime + t1;
		lasttime = from;
	}
	while (buf[i]!='\t') i++;
	i++;

	if (buf[i]!='\t') {
		if (sscanf( buf+i, "%d:%d", &t1, &t2 ) == 2)
			lasttime = to = t1*60+t2;
		else	if (sscanf (buf+i, "+%d", &t1 ) != 1) {
			fprintf( stderr, "Could not find from time on %s", buf );
			exit(1);
		} else	to = lasttime + t1;
		lasttime = to;
	} else { to = -1; pstate = 0; }
	while (buf[i]!='\t') i++;
	i++;
	if (from==-1) from=to;
	if (to==-1) to=from;
	if (from==-1) {
		fprintf( stderr, "\nNo time on line %s\n", buf );
		return NULL;
	}

	if (sscanf(buf+i, "%d", &km ) != 1) {
		fprintf( stderr, "Kilometers not right on %s *%s\n", buf, buf+i );
		exit(1);
	}
	while (buf[i]!='\t') i++;
	i++;
	while (buf[i]!='\t') i++;
	i++;
	townname = buf+i;

//	fprintf( stderr, "Got %s: %s %d:%d %d:%d\n", id->name, townname, from/60, from%60, to/60, to%60 );
	
	{
		struct town *this;

		this = get_town(townname, 1);
		if (prev) {
			struct node *node = my_malloc(sizeof(struct node));
			memset(node, 0, sizeof(struct node));

			node->next = prev->nodes;
			node->from = prev;
			node->to = this;
			node->time1 = curtime;
			node->time2 = from;
			node->length = km;
			node->id = id;
			prev->nodes = node;
			state->numnodes++;
		}

		curkm = km;
		curtime = to;
		return this;
	}
}

void
readit(void)
{
	uchar buf[10240];
	struct id *id = NULL;
	FILE *f = fopen( filename, "r" );
	int lineno = 0;
	struct town *prev = NULL;

	if (!f) {
		fprintf( stderr, "Could not find .tt file %s: %m\n", filename );
		exit(4);
	}

	state = my_malloc(sizeof(struct state));
	state->numtowns = -1;
	state->numnodes = 0;
	while (1) {
		lineno++;
		if (!(lineno % 10000))
			fprintf( stderr, "Reading: %dK lines, %d towns, %d nodes, %.1fMB mem\r", lineno/1000, state->numtowns, state->numnodes, ((double) ((char *) memory - (char *)MEMORY_START))/(1024*1024));
		if (fgets(buf, 10230, f)==NULL) break;
		if (buf[strlen(buf)-1]=='\n') buf[strlen(buf)-1]=0;
		if (*buf == '#') {
			if (mode == FILTER)
				puts(buf);
			lasttime = -9999;
			id = my_malloc(sizeof(struct id));
			id->name = my_malloc(strlen(buf+2)+1);
			strcpy(id->name, buf+2);
			pstate = 1;
			prev = NULL;
			continue;
		}
		if (*buf == '[') {
			if (mode == FILTER)
				puts(buf);
			if (buf[4]=='R') {
				id->cond = my_malloc(strlen(buf+8)+1);
				strcpy(id->cond, buf+8);
			} else {
/*
                        	if (id->note==NULL) {
                                	id->note = my_malloc(strlen(buf+8)+1);
                                        strcpy(id->note,"");
                                } else {
                                        my_malloc(strlen(buf+8)+1); <-- buggy as hell
                                        strcat(id->note,"\n");
                                }
				strcat(id->note, buf+8);
*/
                        }
			pstate = 0;
			continue;
		}
		if (pstate == 1)
			prev = decodeline(id, buf, prev);
		else {
/*			fprintf( stderr, "Line in unexpected state: %s\n", buf ); */
		}
	}

	fprintf( stderr, "Ready  : %d lines, %d towns, %d nodes, %.2fMB mem\n", lineno, state->numtowns, state->numnodes, ((double) ((char *) memory-(char *)MEMORY_START))/(1024*1024));
        fclose(f);
}

/*
 * Heap utility functions
 */

void
printheap(void)
{
#if 0
	int i;
	for (i=1; i<15; i++)
		printf( "%d ", townheap[i] ? townheap[i]->time : INF );
	printf( "\n" );
#endif
}

static int heapcount = 0, heapalloc = 0;

void
deleteheap(int heapindex)
{
	int lefttime = INF, righttime = INF, better;
	if (!townheap[heapindex])
		return;
	townheap[heapindex] = NULL;
	if (townheap[heapindex*2])
		lefttime = townheap[heapindex*2]->time;
	if (townheap[heapindex*2+1])
		righttime = townheap[heapindex*2+1]->time;

	better = heapindex*2 + (lefttime > righttime);
	townheap[heapindex] = townheap[better];
	if (townheap[heapindex])
		townheap[heapindex]->heapindex = heapindex;
	deleteheap(better);
}

int					/* Returns index in townheap where it was actually inserted */
insertheapX(int at, struct town *town)
{
	townheap[at]=town;
	if (!(at/2))
		return at;
	if (townheap[at/2] && (townheap[at/2]->time < town->time))
		return at;

	townheap[at] = townheap[at/2];
	if (townheap[at])
		townheap[at]->heapindex = at;
	return insertheapX(at/2, town);
}

int
insertheap(struct town *town)
{
	heapcount++;	/* This is asking for trouble. We never free entries and are doomed to run out of RAM */ 
	if (heapcount > heapalloc/2) {
		printf( "SOrry, I was lazy\n" );
		exit(5);
	}
	return insertheapX(heapcount, town);
}

/*
 * Search functions
 */

void
finalize(struct town *fin)
{
	struct node *node = fin->nodes;

	fin->final = 1;
	while(node) {
		if (node->time1 >= fin->time) /* I'm soon enough on railway station */
			if (node->time2 < node->to->time)	/* And this one is better */
			if (matches(node->id->cond, &date) && !connection_forbidden(node->id->name))
				if (node->time1 < node->time2) {	/* No midnights for now */
//				printf( "We know how to get to %s\n", node->to->name );
					node->to->by = node;
					node->to->time = node->time2;
					if (!slow) {
						if (node->to->heapindex)
							deleteheap(node->to->heapindex);
						node->to->heapindex = insertheap(node->to);
						printheap();
					}
				}
		node = node->next;
	}
}

struct town *
findmin(void)
{
	int min = INF;
	int i;
	struct town *res = NULL, *town;

	if (slow) {
		for (i=0; i<HASHSIZE; i++) {
			town = state->townhash[i];
			while (town) {
				if ((town->time < min) && (!town->final)) {
					min = town->time;
					res = town;
				}
				town = town->next;
			}
		}
		return res;
	} else {
		res = townheap[1];
		deleteheap(1);
		printheap();
		return res;
	}
}

void idto(struct node *nd)
{
        struct id *myid=nd->id;
        struct node *pnode;
        int mytime=nd->time2;

        pnode=nd->to->nodes;
        while(1) {
	        while (pnode->next!=NULL && pnode->id!=myid) pnode=pnode->next;
                if (pnode->id!=myid) {
                	printf("# smer: %s (prij. %d:%02d)\n",pnode->from->name,
                		mytime/60,mytime%60);break;}
                mytime=pnode->time2;
        	pnode=pnode->to->nodes;
        }

}

char *from_name, *to_name;
int from_len, to_len;

int found(struct town *from)
{
       	if (!strncmp(from->name, to_name, to_len))
		return 1;
        return 0;
}

int
search(void)
{
	int res;
        struct node *by2=NULL,*by3;
        int km=0;
        struct town *from, *to;

	while ((from = findmin())) {
		finalized++;
		if (!(finalized % 100))
			fprintf( stderr, "Searching %2d:%02d %35s... (%d, %d%% finalized)\r", from->time/60, from->time%60, from->name, finalized, (100*finalized)/state->numtowns );
		if (found(from))
                	break;
		finalize(from);
	}
        to=from;
	if (!from) {
		fprintf( stderr, "Done with %2d:%02d %35s... (%d, %d%% finalized)\r", 0, 0, "", finalized, (100*finalized)/state->numtowns );
		printf( "No connection found\n" );
		return INF;
	}
	res = to->time;
	fprintf( stderr, "Done with %2d:%02d %35s... (%d, %d%% finalized)\n", from->time/60, from->time%60, from->name, finalized, (100*finalized)/state->numtowns );

	while (from->by) {
        	km+=from->by->length;
        	by3=by2;
        	by2=from->by;       //vymeni by2 s from->by (za pomoci by3)
                from->by=by3;
                from=by2->from;
        }
        from->by=by2;

        if ((details & DTL_HEAD)!=DTL_HEAD)
        	printf("======================================================================\n"
	               "Connection from:  %s\n             to:  %s\n"
 	               "======================================================================\n",
        	        from->name,to->name);
        if (from==to) return res;
        if ((details & DTL_SUM)!=DTL_SUM)
	        printf("%d Kilometres         Travel time %d:%02d\n\n",km,
        		(to->time - from->by->time1)/60,(to->time - from->by->time1)%60);
        printf("      - ");
	while (from->by) {
        	if (details & DTL_STATIONS) {
	                printf("%2d:%02d %25s",from->by->time1/60,
                        	from->by->time1%60,from->name);
                        km=0;
                        while (from->by->to->by!=NULL && from->by->id==from->by->to->by->id)
                        	{km+=from->by->length;from = from->by->to;}
                        km+=from->by->length;
		        printf(" (%dkm)\n",km);
                } else {
	                printf("%2d:%02d %25s (%dkm,%dkph)\n",
				from->by->time1/60,from->by->time1%60,
	                        from->name,from->by->length,
	                        (from->by->length*60)/(from->by->time2 - from->by->time1));
                }
                printf("%2d:%02d - ",from->by->time2/60,from->by->time2%60);

                if (from->by->to->by==NULL || from->by->id!=from->by->to->by->id) {
                        printf("      %25s\n",from->by->to->name);

                        if (!(details & DTL_COND)) {
	                        printf("#%s %s", matches(from->by->id->cond, &date)==2? "!!!" : "",
        	                	from->by->id->name);
                	        if (from->by->id->cond)
 	                	       printf("  ---   %s",from->by->id->cond);
	                        printf("\n");
                        }
                        if (!(details & DTL_DEST)) idto(from->by);

                        if (!(details & DTL_NOTE)) {
	                        if (from->by->id->note)
		                        printf("%s\n",from->by->id->note);
			}
        		if (from->by->to->by) printf("\n      - ");
                }

		from = from->by->to;
	}
        if ((details & DTL_TAIL)!=DTL_TAIL)
        	printf("----------------------------------------------------------------------\n");
        
        return res;
}

void 
usage(void)
{
	printf( "Usage: town_from day.month.year hour:minute town_to [trains to exclude] \n" );
	exit(4);
}

void
townlist(void)
{
	int i;
	struct town *town;
	for (i=0; i<HASHSIZE; i++) {
		town = state->townhash[i];
		while (town) {
			printf( "%s\n", town->name );
			town = town->next;
		}
	}
}

void
townmark(int time)
{
	int i;
	struct town *town;
	for (i=0; i<HASHSIZE; i++) {
		town = state->townhash[i];
		while (town) {
			if (!strncmp(from_name, town->name, from_len)) {
				town->time = time;
				insertheap(town);
			}
			town = town->next;
		}
	}
}


int
main(int argc, char *argv[])
{
	if (argc < 2)
		usage();
	if (*argv[1] == '-') {
		opts = argv[1]+1;
		argv++;
                argc--;
	}
	if (strchr(opts,'s')) slow = 1;
	if (strchr(opts,'l')) mode = LIST;
	if (strchr(opts,'f')) mode = FILTER;
	if (strchr(opts,'b')) filename = "bus.tt";
	if (strchr(opts,'t')) filename = "vlak.tt";
	
	sscanf(opts,"%d",&details);
	{
		int h;
		h = open(MEMORY_FILE, O_RDWR);
		if ((h!=-1) && (mode != FILTER)) {
			fprintf( stderr, "Memory image already present.\n" );
			memory = (uchar *) MEMORY_START;
			memory_end = memory + MEMORY_SIZE;
			if (mmap(memory, memory_end - memory, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_FIXED, h, 0)==~0) {
				fprintf( stderr, "Could not allocate memory: %m\n" );
				exit(10);
			}
				
			state = (struct state *) memory;
		} else {
			char buf[1024];
			fprintf( stderr, "Creating empty file for memory image.\n" );
			h = open(MEMORY_FILE, O_RDWR | O_CREAT, 0644);
#if 0
	                ftruncate(h, MEMORY_SIZE);	/* Provokes kernel bug on 2.4.0-test8 */
#else
			sprintf(buf, "head -c %d < /dev/zero > %s", MEMORY_SIZE, MEMORY_FILE );
			system(buf);
#endif
			memory = (uchar *) MEMORY_START;
			memory_end = memory + MEMORY_SIZE;
			if (mmap(memory, memory_end - memory, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, h, 0)==~0) {
				fprintf( stderr, "Could not allocate memory: %m\n" );
				exit(10);
			}
			readit();
	                ftruncate(h,memory - (uchar *)MEMORY_START);
			fprintf( stderr, "Memory image now created.\n" );
			memory = (void *) MEMORY_START;
                	if (mmap(memory, memory_end - memory, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_FIXED, h, 0)==~0) {
				fprintf( stderr, "Could not allocate memory: %m\n" );
				exit(10);
			}
		}
	}
	{
		int size;
		heapalloc = 10*state->numtowns + 10;
		size = sizeof(struct town *) * heapalloc;
		fprintf(stderr, "Creating heap...\n" );
		townheap = malloc(size);
		memset(townheap, 0, size);
	}
	if (mode == FILTER)
		exit(0);
	if (mode == LIST) {
		townlist();
		exit(0);
	}
	if (argc < 5)
		usage();
	{
		int time1, time2;
		struct town *from, *to;

		from_name = argv[1];
		to_name = argv[4];

		fprintf(stderr, "Getting towns...\n" );
		from = get_town(from_name, 0);
		to = get_town(to_name, 0);
                
                if (strchr(from_name,GRP_CHAR)) from_len=strchr(from_name,GRP_CHAR)-from_name;
                	else from_len=-1;
                if (strchr(to_name,GRP_CHAR)) to_len=strchr(to_name,GRP_CHAR)-to_name;
                	else to_len=-1;

		if (!from && from_len==-1) {
			fprintf(stderr, "Sorry, town '%s' does not exist.\n", from_name);
                        return 2;
		}
		if (!to && to_len==-1) {
			fprintf(stderr, "Sorry, town '%s' does not exist.\n", to_name);
                        return 2;
		}

        	sscanf(argv[2],"%d.%d.%d",&date.tm_mday,&date.tm_mon,&date.tm_year);
        	date.tm_sec=0;date.tm_min=0;date.tm_hour=0;
        	date.tm_mon--;date.tm_year-=1900;
        	mktime(&date);
        	date.tm_mon++;
        	if (date.tm_wday==0) date.tm_wday=7;
                if (sscanf(argv[3], "%d:%d", &time1, &time2)!=2) {
			printf( "Sorry, invalid time '%s' specified.\n", argv[3]);
			return 3;
		}
                pargc=argc; pargv=argv;
		if (from_len!=-1) townmark(time1*60+time2);
                	else {from->time=time1*60+time2;insertheap(from);}
		search();
	}
	return 0;
}