/* -*- 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>
#define COMPATIBLE
#ifndef COMPATIBLE
#include <unistd.h>
#include <sys/mman.h>
#endif
#include <time.h>
#include <ctype.h>
#include <errno.h>

#define MEMORY_SIZE 	(92*1024*1024)
#define MEMORY_START	(0x20000000)
#define GRP_CHAR	'+'
#undef LITE

#define MAX_REMARKS	255
#define REMARK_SIZE	14

int pargc;
char **pargv;
char *table_file = "vlak.tt", *memory_file = "vlak.mem";

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 *buf,struct tm *tcas)
{
	int kladno=0,podm,i=0;
	int d1,d2,d3;
	char s1[1024];
	int odd=defod,dod=defdo,tmpod;
	int tmpores=-1,ores=-1;
	int res=0,savres=-1;
        int res_found=0;

	if (buf==NULL) return 1;
	if (!memcmp(buf,"t.è. nejede",11)) return 0;
	res=1; //FIXME: not needed

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

			if (podm!=-1) {
				if (kladno) res|=podm;
				else res&=!podm;
			}
			continue;
		}
		if (isdigit(buf[i])) {
			res_found=1;
			d3=1;
			podm=0;
			while (d3) {
				d3=sscanf(buf+i,"%d.",&d1);
				if (d3==0 || d3==-1) break;
				if (d1==tcas->tm_mday) podm=1;
				i+=2;
				if (d1>9) i++;   // za tecku
				while (buf[i]==' ') i++;
				if (buf[i]==',') {i++;continue;}
				d2=0;
				while (buf[i]==' ') i++;
				while (buf[i]!='.') {
					s1[d2++]=buf[i++];
					if (buf[i]==0) return 2;
				}
				s1[d2]=0;
				i++;	   //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) res|=podm;
				else res&=!podm;
			}
			continue;
		}
		if (!memcmp(buf+i,"od",2)) {
                	if (tmpores==-1) {
                        	if (!res_found) res=kladno;
                        	savres=res;
                        } else {
                        	if (tmpores && res_found) savres=res;
                                if (tmpores) ores=1;
                        }
                        if (kladno) res=0;
                        	else res=1;
                        res_found=0;
                        
			i+=3;
			podm=0;
		       	sscanf(buf+i,"%d.",&d1);
       			i+=2;
	       		if (d1>9) i++;   // za tecku
			d2=0;
       			while (buf[i]!='.')
	       			s1[d2++]=buf[i++];
		       	s1[d2]=0;
			i++;	   //za tecku
       			for (d2=1;d2<=12;d2++)
	       			if (!strcmp(mes[d2-1],s1)) break;
			odd=d2*100+d1;                        
			if (odd<=defdo%10000) odd+=10000;

                        tmpod=(tcas->tm_mon)*100+tcas->tm_mday;
			if (tmpod<=(defdo%10000)) tmpod+=10000;
                        if (tmpod>=odd) podm=1;

			if (podm!=-1) {
				if (kladno) tmpores=podm;
				else tmpores=!podm;
			}

			continue;
		}
		if (!memcmp(buf+i,"do",2)) {
                	if (tmpores==-1) {
                        	if (!res_found) res=kladno;
                        	savres=res;
                        } else {
                        	if (tmpores && res_found) savres=res;
                                if (tmpores) ores=1;
                        }
                        if (kladno) res=0;
                        	else res=1;
                        res_found=0;
                        
			i+=3;
			podm=0;
		       	sscanf(buf+i,"%d.",&d1);
       			i+=2;
	       		if (d1>9) i++;   // za tecku
			d2=0;
       			while (buf[i]!='.')
	       			s1[d2++]=buf[i++];
		       	s1[d2]=0;
			i++;	   //za tecku
       			for (d2=1;d2<=12;d2++)
	       			if (!strcmp(mes[d2-1],s1)) break;
			dod=d2*100+d1;
			if (dod<=(defdo%10000)) dod+=10000;
                        
			tmpod=(tcas->tm_mon)*100+tcas->tm_mday;
			if (tmpod<=(defdo%10000)) tmpod+=10000;
			if (tmpod<=dod && odd<=tmpod) podm=1;

			if (podm!=-1) {
				if (kladno) tmpores=podm;
				else tmpores=!podm;
			}
			continue;
		}
		if (!memcmp(buf+i,"a",1))	{
			return 2;
		}

		if (buf[i]==' ') {i++;continue;}
		if (buf[i]==',') {i++;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 {
	struct id *next;
	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 */
	char *company;	/* Company which owns the node */
	int _id;
        uchar remark;
};

static int town_id;

struct node {
	struct node *next;
#ifndef LITE
	struct town *from;
#endif
	struct town *to;
	struct id *id;
	int linenum1;
	int linenum2;
	unsigned short time1, time2;
#ifndef LITE
	unsigned short length;
#endif
	uchar remark;
};

struct town {
	uchar *name;
	struct town *next;
	struct node *last_node;
	struct node *nodes;
	unsigned short _id;	/* Warning: it is possible to hit this limit */
	struct node *by;	/* changed at runtime */
	int heapindex;		/* changed at runtime */
	unsigned short time;	/* changed at runtime */
	char final;		/* changed at runtime */
};

#define HASHSIZE 60000
#define INF 65000
#define ANY (25*60)

struct state {
	char version[20];
	struct town *townhash[HASHSIZE];
	struct id *ids;
	unsigned short numtowns;
	int numnodes;
	int id_id;
        int n_remarks;
        char remarkvec[MAX_REMARKS][REMARK_SIZE];
};

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 IDLIST 3
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
#define DTL_COMPANY	128

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

uchar *my_strdup(uchar *s)
{
#ifndef LITE
	char *res = my_malloc(strlen(s)+1);
	strcpy(res, s);
	return res;
#else
	return NULL;
#endif
}

struct town *get_hash(uchar *name)
{
	int hash = (name[0] + 64*name[1] + (64*64)*name[2] + (64*64*64)*name[3])%HASHSIZE;
	return state->townhash[hash];
}

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 = get_hash(name);

	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;
	res->_id = town_id++;
	state->townhash[hash] = res;
	state->numtowns++;
	return res;
}


int pstate = 0, curtime, curkm, lasttime;
char oldremark[1024];


void store_remark(uchar *to)
{
	int i;

        for(i=0;i<=state->n_remarks;i++) {
		if (!strcmp(oldremark,state->remarkvec[i]))
			{*to=i;break;}
		if (i==state->n_remarks) {
			if (state->n_remarks==MAX_REMARKS) {
				fprintf( stderr, "Remarks Limit Exceeded\n");
				exit(1);
			}
			if (strlen(oldremark)>REMARK_SIZE) {
				fprintf( stderr, "Remarks Size Exceeded\n");
				exit(1);
			}
			strncpy(state->remarkvec[state->n_remarks],oldremark,REMARK_SIZE);
			*to=state->n_remarks++;
			break;
		}
	}
}


struct town *
decodeline(struct id *id, uchar *buf, struct town *prev)
{
	int i = 0;
	char *townname;
	int remindx = 0;
	char remark[10240];
	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 time 1 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 time 2 on %s", buf );
			exit(1);
		} else	to = lasttime + t1;
		lasttime = to;
	} else { to = -1; pstate = 0; }
	while (buf[i]!='\t') i++;
	i++;
        while (buf[i]!='\t') {
		remark[remindx++]=buf[i++];
	}
	remark[remindx]=0;
	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++;
	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;
#ifndef LITE
			node->from = prev;
#endif
			node->to = this;
			node->time1 = curtime;
			node->time2 = from;
#ifndef LITE
			node->length = km;
#endif
			node->id = id;
                        store_remark(&node->remark);
                        prev->nodes = node;
			state->numnodes++;
		}

		curkm = km;
		curtime = to;
                strcpy(oldremark,remark);
		return this;
	}
}

void do_end_id(struct id *id,char **note, char **company)
{
        if (id==NULL) return;
        if (*note!=NULL) {
        	id->note=my_malloc(strlen(*note)+1);
                strcpy(id->note,*note);
        	free(*note);
                *note=NULL;
        }
        if (*company!=NULL) {
        	id->company=my_malloc(strlen(*company)+1);
                strcpy(id->company,*company);
        	free(*company);
                *company=NULL;
	}
        store_remark(&id->remark);
        state->id_id++;
}

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

	state = my_malloc(sizeof(struct state));
	state->numtowns = 0;
	state->numnodes = 0;
	strcpy(state->version, __DATE__);
	state->id_id = 0;
        state->n_remarks = 1;
        state->remarkvec[0][0]=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[0]==0) continue;
		switch (*buf) {
		case '#':
                	do_end_id(id,&note,&company);
			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;
		case 'R':
			id->cond = my_strdup(buf+1);
			pstate = 0;
			break;
		case 'G':
			if (company==NULL) {
				company = malloc(strlen(buf+1)+1);
				strcpy(company,"");
			} else {
				company=realloc(company,strlen(company)+1+strlen(buf+1)+1);
				strcat(company,"\n");
			}
			strcat(company, buf+1);
			pstate = 0;
			break;
		case 'A': case 'B': case 'C': case 'D': case 'E': case 'F':
		case 'H': case 'I': case 'J': case 'K': case 'L': case 'M':
		case 'N': case 'O': case 'P': case 'Q': case 'S': case 'T':
		case 'U': case 'V': case 'W': case 'X': case 'Y': case 'Z':
		case '[':
			if (note==NULL) {
				note = malloc(strlen(buf+1)+1);
				strcpy(note,"");
			} else {
				note=realloc(note,strlen(note)+1+strlen(buf+1)+1);
				strcat(note,"\n");
			}
			strcat(note, buf+1);
			pstate = 0;
			break;
		case ';':	/* Remark */
			break;
		case '!':	/* Followed by keyword */
			{
				int y1, m1, d1, y2, m2, d2, i, j;
				if (sscanf(buf+1, "valid y%d m%d d%d .. y%d m%d d%d\n",
					   &y1, &m1, &d1, &y2, &m2, &d2) == 6) {
					continue;
				}

				if (sscanf(buf+1, "version %d.%d\n", &i, &j) == 2) {
					continue;
				}

			}
			break;
		case 0:
			break;
		default:
			if (pstate == 1)
				prev = decodeline(id, buf, prev);
			else {
				fprintf( stderr, "Line in unexpected state: %s\n", buf );
			}
		}
	}
	do_end_id(id,&note,&company);

	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 == ANY)
			if (!connection_forbidden(node->id->name))
				if (fin->time + (node->time2 - node->time1) < node->to->time) {
					node->to->by = node;
					node->to->time = fin->time + (node->time2 - node->time1);
					if (!slow) {
						if (node->to->heapindex)
							deleteheap(node->to->heapindex);
						node->to->heapindex = insertheap(node->to);
						printheap();
					}
				}
		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;
	}
}

int lastrem(struct node *nd)
{
        struct id *myid=nd->id;
        struct node *pnode;

        pnode=nd->to->nodes;
        while (pnode->next!=NULL && pnode->id!=myid) pnode=pnode->next;
	if (pnode->id!=myid)
		return myid->remark;
	return pnode->remark;
}

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

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

void prefix(char *pref,char *s)
{
	int i1=0;
        char *p;
        char tmp[1024];
        for(;;) {
	        strcpy(tmp,pref);
        	if ((p=strchr(s+i1,'\n'))==NULL) break;
	        strncat(tmp,s+i1,p-s-i1);
        	puts(tmp);
                i1+=p-s-i1+1;
	}
        strcat(tmp,s+i1);
        puts(tmp);
}

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

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

int
exist_id(struct id* id,struct town *town,int time)
{
	struct node *node=town->nodes;

        while (node) {
        	if (node->id==id && node->time1>time) return 1;
                node=node->next;
	}
	return 0;
}

void new_route(struct town *from, struct town *to, struct id *id)
{
        struct node *node;
        
//	printf("JDE TO LEPE\n");return;
        while (from!=to) {
        	node=from->nodes;
                while (node->id!=id) node=node->next;
                from->by=node;
                from=from->by->to;
	}
}

void
simple_audit(struct town *from, struct town *to)
{
        struct town *idchange[100];
        int times[100];
        int numchange=0;
        int i,ii;

        times[0]=0;
        idchange[numchange++]=from;
        while (from->by) {
        	if (from->by->to->by!=NULL && from->by->id!=from->by->to->by->id) {
                	times[numchange]=from->by->time2;
                        idchange[numchange++]=from->by->to;
                }
		from=from->by->to;
        }
	for(i=0;i<numchange;i++) {
        	for (ii=0;ii<i;ii++) {
			if (exist_id(idchange[i]->by->id,idchange[ii],times[ii]))
				new_route(idchange[ii],idchange[i],idchange[i]->by->id);
                }
	}
}

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

	while (from->by) {
		//printf( "%s; ", from->name);
        	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 (!strchr(opts,'a')) simple_audit(from,to);

        if ((details & DTL_HEAD)!=DTL_HEAD)
        	printf("======================================================================\n"
	               "Connection from:  %s\n             to:  %s\n"
 	               "======================================================================\n",
        	        from->name,to->name);
        if (from==to) return;
        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 %-3s %-30s",from->by->time1/60,
                        	from->by->time1%60,
                                state->remarkvec[from->by->remark],from->name);
                        km=0;
                        time=from->by->time1;
                        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,%dkm/h)\n",km,(km*60)/(from->by->time2 - time));
                } else {
	                printf("%2d:%02d %-3s %-30s (%dkm,%dkm/h)\n",
				from->by->time1/60,from->by->time1%60,
	                        state->remarkvec[from->by->remark],
                                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("      %-3s %-30s\n",state->remarkvec[lastrem(from->by)],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_COMPANY)) {
	                        if (from->by->id->company)
                                	prefix("[]  ",from->by->id->company);
			}
                        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");
}

int
search(void)
{
	int res;
        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 );

	printres(from, to);
        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;
	if (strchr(opts, 'v')) printf("%d\n", state->numtowns);
	for (i=0; i<HASHSIZE; i++) {
		town = state->townhash[i];
		while (town) {
			if (!strchr(opts, 'v'))
				printf( "%s\n", town->name );
			else
				if (strchr(opts, 'V'))
					printf( "%s\t%d\n", town->name, town->_id );
				else
					printf( "%d\t%s\n", town->_id, town->name );
			town = town->next;
		}
	}
}

void
townmark_old(int time)
{
	int i;
	struct town *town;

	fprintf(stderr, "Too short name specified, using very slow method.\n" );
	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;
		}
	}
}

void
townmark(int time)
{
	struct town *town;

	if (from_len < 3)
		return townmark_old(time);

	town = get_hash(from_name);
	while (town) {
		if (!strncmp(from_name, town->name, from_len)) {
			town->time = time;
			insertheap(town);
		}
		town = town->next;
	}
}

static int linenum = 0;

void
prepare_town(int now, struct town *town, int mode)
{
	struct node *node = town->nodes;
	while(node) {
		if (mode && node->time1 == now) {
			node->linenum1 = linenum++;
#undef DEBUG
#ifdef DEBUG
			printf( "%d:%d event %d: *-> to %s at %d:%d by %s\n", now/60, now%60, node->linenum1, 
				node->to->name, node->time2/60, node->time2%60, node->id->name );
#else
			printf( ">%d\t%d\t%d\t%d\n", now, town->_id, node->id->_id, town->last_node ? town->last_node->linenum2 : -1);
#endif

		}
		if (!mode && node->time2 == now) {
			node->linenum2 = linenum++;
#ifdef DEBUG
			printf( "%d:%d event %d: ->* into %s from event %d prev %d\n", now/60, now%60, node->linenum2, node->to->name, node->linenum1, node->to->last_node ? node->to->last_node->linenum2 : -1 );
#else
			printf( "<%d\t%d\t%d\t%d\n",
				now, node->to->_id, node->linenum1, node->to->last_node ? node->to->last_node->linenum2 : -1 );
#endif
			node->to->last_node = node;
		}
		node = node->next;
	}
}

void
prepare(void)
{
	int now;
	fprintf(stderr, "Size of towns is %dKB, size of nodes is %dKB, size of ids is %dKB\n",
		sizeof(struct town) * state->numtowns / 1024,
		sizeof(struct node) * state->numnodes / 1024,
		sizeof(struct id) * state->id_id / 1024);
	for (now=0; now<(60*24); now++) {
		fprintf(stderr, "%2d:%02d, %d lines generated\r", now/60, now%60, linenum);
		{
			int i, mode;
			struct town *town;
			for (mode=0; mode<2; mode++)
			for (i=0; i<HASHSIZE; i++) {
				town = state->townhash[i];
				while (town) {
					prepare_town(now, town, mode);
					town=town->next;
				}
			}
		}
	}
}

void
idlist(void)
{
	struct id *id = state->ids;
	printf("%d\n", state->id_id);
	while (id) {
		printf("%d\t%s\t%s\t%s\n", id->_id, id->name, id->cond ? id->cond : "", id->note ? id->note : "");
		id = id->next;
	}
}

void
setup_memory(void)
{
#ifndef COMPATIBLE
		int h;
		h = open(memory_file, O_RDWR);
		if (h!=-1) {
			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)== (void *) ~0) {
				fprintf( stderr, "Could not allocate memory: %m\n" );
				exit(10);
			}
				
			state = (struct state *) memory;
			if (strcmp(state->version, __DATE__))
				fprintf( stderr, "Warning, .mem file created by another version!\n" );
		} 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)== (void *) ~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)== (void *) ~0) {
				fprintf( stderr, "Could not allocate memory: %m\n" );
				exit(10);
			}
		}
#else
		memory = malloc(MEMORY_SIZE);
		memory_end = memory + MEMORY_SIZE;
		readit();
#endif
}


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,'v')) mode = LIST;
	if (strchr(opts,'i')) mode = IDLIST;
	if (strchr(opts,'b')) { table_file = "bus.tt"; memory_file = "bus.mem"; }
	if (strchr(opts,'t')) { table_file = "vlak.tt"; memory_file = "vlak.mem"; }
	if (strchr(opts,'x')) { table_file = "xyzzy.tt"; memory_file = "xyzzy.mem"; }
	
	sscanf(opts,"%d",&details);
	setup_memory();
	if (strchr(opts, 'p')) {
		prepare();
		exit(0);
	}
	switch(mode) {
	case LIST:
		townlist();
		exit(0);
	case IDLIST:
		idlist();
		exit(0);
	}
	if (argc < 5)
		usage();
	{
		int size;
		heapalloc = 10*state->numtowns + 10;
		size = sizeof(struct town *) * heapalloc;
		fprintf(stderr, "Creating heap...\n" );
		townheap = malloc(size);
		memset(townheap, 0, size);
	}
	{
		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;
}