/* Zadatak 15; Milan Ruzic 394/2000 */
/* U slucaju listanja niski izmedju svih dozvoljenih etiketa, niske se dodaju
   u odgovarajuce liste i tek na kraju stampaju. Ovako je dovoljan samo jedan
   prolaz kroz fajl, ali se zato predpostavlja da sve niske mogu stati u 
   raspolozivu memoriju (uvek <640K, ali ona treba da je i vise nego dovoljana
   za planirane tekstove). Uz to svaka niska mora biti <2^15 byte-a. 
*/
#include <stdio.h>
#include <alloc.h>

/****** constante ******/
#define _numOftags 7
#define _maxTagSize 7

char *tags[_numOftags]={"KBD","ADDRESS","EM","STRONG","VAR","DEF","CITE"};

/****** tipovi *********/
typedef struct {char *niska; void *next;} Tlist;
typedef Tlist *TlistPok;

typedef struct {char *tag;
		TlistPok list_start, list_end;} Ttable_element;

/****** globalne promenjive *******/

Ttable_element hashTable[_numOftags];
FILE *infile;

/*****************************************************************************/
/* U ovom zadatku potreban je samo staticki recnik. Posto su svi prvi znakovi
   dozvoljenih etiketa razliciti moze se koristiti hash funkcija oblika 
    (C div (s[0]+1)) mod broj_elemenata 
  (+1 da bi se izbeglo potencijalno deljenje sa 0). Koriscen je program za 
  racunanje konstante C koja cini f-ju i savrsenom(nema kolizija) i 
  minimalnom(velicina tabele==broju elemenata). Program je baziran na radu:
    G. Jaeschke,"Reciprocal Hashing: A Method for Generating Minimal Perfect 
  Hash Functions", Communications of the ACM, dec 1981
  Koriscenje hash f-ja u ovom zadatku je vise demonstracione prirode nego sto
  je zaista opravdano. Posto su prvi znakovi razliciti, prihvatljivo je bilo i
  koriscenje direktnog adresiranja (tabela od 256 ulaza za svaki bajt) i ako
  bi tabela bila retko popunjena. Posto se radi o vrlo malom skupu ne-slicnih 
  stringova i binarna preraga dolazi u obzir. Direktno addres. je daleko
  najbrza opcija, a cak je i binarana pretraga ovde mozda brza, posto su
  potrebna 2 integer deljenja da bi se izracunala vred. f-je. No, izabrani
  pristup je opstiji (u pogledu optimizacije brzine). 
*/

int hash_value(char *keystr)
{int C=28776;
 return (C/(*keystr+1)) % _numOftags;
}

char toUpCase(char ch)
{ if (ch>=97 && ch<=122) return ch-32;
  else return ch;
}

int strequ(char *s1, char *s2)
{ for (;*s1==*s2 && *s1; s1++,s2++);
  if (*s1==*s2) return 1;
  else return 0;
}

int strlen(char *s)
{ int i;
  for (i=0; *s; s++,i++);
  return i;
}

void appendList(int index, void *niska)
{Tlist *newElem=malloc(sizeof(Tlist));
 newElem->niska=niska;
 newElem->next=NULL;
 if (hashTable[index].list_start==NULL)
   { hashTable[index].list_start=newElem;
     hashTable[index].list_end=newElem;
   }
 else
   { hashTable[index].list_end->next=newElem;
     hashTable[index].list_end=newElem;
   }
}

void disposeLists(void)
{ int i;
  for (i=0; i<_numOftags; i++)
  { TlistPok p,q;
    p=hashTable[i].list_start;
    while (p!=NULL) { q=p->next; free(p); p=q; }
  }
}

int processTag(void)
/* Ovo je rekurzivna f-ja koja ispituje da li je etiketa jedna od trazenih i
   ako jeste stavlja ugnjezdenu nisku na kraj odgovarajuce liste. U tom 
   sluacju f-ja vraca ukupan broj procesiranih znakova (niska+granicni tagovi). 
   Rekurzivno resenje je potrebno zbog moguce ugnjezdenih etiketa, na pr. 
   <kbd>xxx<strong>xxxx</strong>xxxx</kbd>.
   Ako pocetna etiketa nije jedna od trazenih, f-ja vraca 0 i re-pozicionira
   file pointer, a ako naleti na EOF vraca -1.
*/
{ long retfpos=ftell(infile);
  int i,h,strsize;
  char c,slash='/',trentag[_maxTagSize+1]; /*slash mora da bude ispred trantag-a */

  for (i=0; (c=fgetc(infile))!='>' && i<_maxTagSize; trentag[i++]=toUpCase(c)) ;
  trentag[i]=0;
  h = hash_value(trentag);
  if (strequ(trentag, hashTable[h].tag) && c=='>') /*ako su cele etiekte iste */
   { long fpos = ftell(infile);
     char *niska, *p;
     strsize=0;   /* duzina ugnjezdene niske; sluze da bi se znalo koliko je
                   memorije potrebno dinamicki alocirati */

     while ((c=fgetc(infile))!=EOF)
     { int oldsize=strsize;
       strsize++;
       if (c=='<')
	   { i=processTag();
	     if (i==-1) return -1;
	     if (i) strsize+=i;
	     else
	     { /*ovde se vidi cemu onaj slash ispred trentag-a */
               for (i=-1; toUpCase(c=fgetc(infile))==trentag[i]; i++);
	       if (c=='>') { strsize=oldsize; break; } /*da li se radi o tagu zatvaracu*/
	       else strsize=oldsize+i+3;
	     }
	   }
     }
     if (c==EOF) return -1;

     niska=malloc(strsize+1);
     fseek(infile,fpos,SEEK_SET);
     for (i=0, p=niska; i<strsize; *p=fgetc(infile), p++, i++);
     *p=0;
     appendList(h,niska);
   } /*if strequ */
   else { fseek(infile,retfpos,SEEK_SET); return 0; }

   i=strlen(hashTable[h].tag);
   fseek(infile,i+3,SEEK_CUR); /*preskoci zatvaracku etiketu cija duzina je ukljucena u return value*/
   return strsize+2*i+4;       /* +4 zbog '>', '<','/' i '>' koji nisu racunati*/
}

main(int argc,char *argv[])
{ int i;
  char c,trentag[_numOftags];

  if (argc==2)
  { if ((infile=fopen(argv[1],"r"))==NULL)
      { printf("Greska: Nepostojeci fajl!"); return 1;}

   /* Init hash tabelu */
   for (i=0; i<_numOftags; i++)
    { int j = hash_value(tags[i]);

      hashTable[j].tag=tags[i];
      hashTable[j].list_start=NULL;
      hashTable[j].list_end=NULL;
    }

   while ((c=fgetc(infile))!=EOF) if (c=='<') processTag();

   for (i=0; i<_numOftags; i++)
   { TlistPok p;
     printf("\n\n %s\n",hashTable[i].tag);
     p=hashTable[i].list_start;
     while (p) { printf("\x10  %s\n", p->niska); p=p->next; }
   }
   disposeLists();
   fclose(infile);
  }  /* if prikazi sve */

  else if (argc==3) /* ovo je jednostavniji slucaj sa samo jednom etiketom */
  { char *p;

    if ((infile=fopen(argv[2],"r"))==NULL)
      { printf("Greska: Nepostojeci fajl!"); return 1;}

    for (p=argv[1]; *p; *p=toUpCase(*p), p++);

    printf("\n\n %s\n",argv[1]);

    while ((c=fgetc(infile))!=EOF)
    if (c=='<')
    {
      for (i=0; (c=fgetc(infile))!='>' && i<_maxTagSize; trentag[i++]=toUpCase(c)) ;
      trentag[i]=0;
      if (strequ(trentag, argv[1]) && c=='>')
      { printf("\x10  ");
        while ((c=fgetc(infile))!=EOF)
	{ if (c=='<')
	   if ((c=fgetc(infile))!='/') {putchar('<'); putchar(c);}
	   else
	    { for (i=0; (c=fgetc(infile))!='>' && i<_maxTagSize; trentag[i++]=toUpCase(c)) ;
	      trentag[i]=0;
	      if (strequ(trentag, argv[1]) && c=='>') break;
	      printf("</%s>",trentag);
	    }
	   else putchar(c);
	 }

	if (c==EOF) break;
	putchar('\n');
      }
    }
    fclose(infile);
  } /*if prikazi samo jednu vrstu */
  else printf(" Greska u parametrima!");

} /* main() */