[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico]
[Índice de assunto]
Wordtest
Como eu naum consegui fazer meu EP funcionar direito resolvi colar
nervoso do wordtest (já que o professor quer um clone ...). Daí, eu
alterei algumas coisas, identei e comentei o wordtest com alguns chavões
do curso. Infelizmente o código ainda possui muitos "gotos" e "breaks"
mas eu acho que já está melhorzinho.
A propósito, estou muito decepcionado com o código. O treap utilizado
poderia ao invés de criar uma árvore com inserções aleatórias na raiz,
minimizar o custo de construção da árvore se fosse observado o número de
visita que cada nó recebe. Aliás o professor poderia passar isto para a
gente ( eu acho bem legal, afinal , uma árvore balanceada só é ótima
para o caso em que as chaves têm freqüências próximas entre si).
--
Rodrigo di Lorenzo Lopes (Mineirinho) - ICQ 52982003
// By Donald Knuth
#define MAX_LENGTH_DEFAULT 50
#define MAX_LENGTH_LIMIT 1000
#define PHICLONE 2654435769
#define NODES_PER_BLOCK 100
#define CHARS_PER_BLOCK 1000
#define out_of_mem(x) {fprintf(stderr,"%s: Memory exhausted!\n",*argv);return x;}
#include <stdio.h>
#include <stdlib.h>
// Alteracoes pessoais
#define true 1
#define false 0
typedef unsigned char byte;
typedef struct node_struct {
struct node_struct *left, *right;
byte* keyword;
unsigned long rank;
}node;
typedef struct filenode_struct{
struct filenode_struct* link;
FILE *dfile; // stream para arquivo
byte buf[BUFSIZ+1],
curword[MAX_LENGTH_LIMIT+1];
// BUFSIZ ???
/* bufsiz é uma macro que contém o tamanho
ótimo de um buffer para seu sistema */
byte *pos,
*limit,
*endword;
} filenode;
int main(int argc, char* argv[]){
int fim_arquivo, fim_linha;
int targc;
byte**targv;
unsigned delta; // valor do offset - padrão é zero
unsigned max_length = MAX_LENGTH_DEFAULT; // tamanho max do buffer
byte breakchar; // valor do caracter de break
int ord[256]; // Nossa ordem ...
register int c;
register byte *u, *v;
unsigned long current_rank= 0;
register node *p, **q, **qq,*r;
// ***********Inicializando variáveis********
node *next_node= NULL,
*bad_node= NULL;
node *root= NULL; // raiz do treap
byte *next_string= NULL,
*bad_string= NULL,
*buffer; // o BUFFER!!!
int l;
filenode *curfile; // apontador da fila circular
filenode *f; // variável temporária
// Valores Default
for(c= 0;c<256;c++)
ord[c]= c;
delta= 0;
// *************Lendo argumentos ***********
targc= argc-1;
targv= (byte**)argv+1;
while(targc && **targv =='-'){
// Percorre os argumentos da linha de comando
switch((*targv)[1]){
case'a':
for (c= delta,u= *targv+2;*u;u++)
ord[*u]= ++c;
break;
case'b':
if((*targv)[2])
for(u= *targv+2;*u;u++)
ord[*u]= -1;
else
for(c= 1;c<256;c++)
ord[c]= -1;
break;
case'n':
if((*targv)[2])
for(u= *targv+2;*u;u++)
ord[*u]= 0;
else
for(c= 1;c<256;c++)
ord[c]= 0;
break;
case'd':
if(sscanf((char*)*targv+2,"%u",&delta)==1&&delta<256)
break;
goto print_usage;
case'm':
if(sscanf((char*)*targv+2,"%u",&max_length)==1&&
max_length<=MAX_LENGTH_LIMIT)
break;
goto print_usage;
default:
print_usage:
fprintf(stderr,"Usage: %s {-{{a|b|n}string|{d|m}number}}* dictionaryname*\n",*argv);
return (-1);
}
targc--;targv++;
}
// Corrigindo a tabela de símbolos
if(ord['\n']<0)
breakchar= '\n';
else{
breakchar= '\0';
for(c= 255;c;c--)
if(ord[c]<0)
breakchar= c;
if(!breakchar) {
ord['\n']= -1;
breakchar= '\n';
for(c= 1;c<=26;c++)ord['a'-1+c]= 'A'-1+c;
}
}
// *************Abrindo dicionarios ****************
// Criando fila circular que conterá os dicionários
// note que neste momento targc = numero de dicionarios
if(targc){
curfile= (filenode*) calloc (targc,sizeof(filenode));
if (curfile==NULL)
// nao consegui alocar
out_of_mem(-7);
/* Logica desta maracutai:
curfile tem um inteiro (pois é uma posição na memória)
curfile aponta para uma vetor de inteiros
assim, podemos andar pela matriz como andamos em um vetor de int
*/
// Eu também não acredito que isso funcione ...
for(f= curfile;f < curfile + targc-1; f++)
f->link= f+1;
f->link= curfile;
}
else
curfile= NULL;
// Abrindo arquivos e colocando os streams na fila circular
for(;targc;targc--,targv++) {
// Percorre os argumentos
curfile->dfile = fopen ((char*)*targv,"r");
if (curfile->dfile==NULL){
fprintf(stderr,"%s: Can't open dictionary file %s!\n",
*argv,(char*)*targv);
return (-8);
}
// Zera as atribuições do corrente arquivo
curfile->pos= curfile->limit= curfile->buf;
curfile->buf[0]= '\0';
curfile->endword= curfile->curword;
curfile->curword[0]= breakchar;
// Desloca corrente arquivo na fila
curfile= curfile->link;
}
buffer = (byte*) malloc(max_length+1);
// alocamos o buffer
if(buffer==NULL)
out_of_mem(-5);
/* O codigo que segue usa goto e break
while(1){
u= buffer;
l= 0;
while( l < max_length){
c = getchar();
if(c == EOF){
if(ferror(stdin)){
fprintf(stderr,"%s: File read error on standard input!\n",*argv);
return (-6);
}
goto done;
}
if(ord[c]<=0){
if(ord[c]<0)
break;
}
else{
*u++ =(byte)c;
l++;
}
}
Foi substituido pelo segmento que segue abaixo : */
found:;
// found estava no meio do codigo ...
while (!fim_arquivo){
u = buffer;
l =0;
while ((l < max_length)&&(!fim_arquivo)&&(!fim_linha)){
c = getchar();
if (c==EOF){
if(ferror(stdin)){
fprintf(stderr,"%s: File read error on standard input!\n",*argv);
return (-6);
}
fim_arquivo = true;
goto done;
}
if(ord[c]<=0){
if(ord[c]<0)
fim_linha = true;
}
else {
// carrega em u (,u eh uma string) o valor de c
*u++ =(byte) c;
l++;
// tamanho da palavra
}
}
*u= breakchar;
if(l){
// se tiver alguma "letter" na linha
p = root;
/* node fica guardado num registrador para otimizar a velocidade
de acesso */
// ********STprocurar (p,u)*********
// onde p eh a raiz, e u chave
while(p){
for (u= buffer,v= p->keyword;ord[*u]==ord[*v];u++,v++);
// strcmp (u,v)
if (*v=='\0'&&*u==breakchar)
goto found;
// a palavra estava no treap
if(ord[*u]<ord[*v])
// less (u,v)
p = p->left;
else
p= p->right;
}
// ********STinserir (p,u)***********
current_rank+= PHICLONE;
p = root;
q= &root;
while(p){
// testa condicao de treap
if(p->rank > current_rank)
break;
// testa condicoes de uma arvore balanceada
for(u= buffer,v= p->keyword;ord[*u]==ord[*v];u++,v++);
// strcmp (u,v)
if(ord[*u]<ord[*v])
//less (u,v)
q= &(p->left),p= *q;
// p = p->left;
else
q= &(p->right),p= *q;
// p = p->right
}
// ainda em STinserir ...
if (next_node==bad_node){
// no esta num lugar ruim (quase fora da area allocada)
next_node = (node*) calloc (NODES_PER_BLOCK,sizeof(node));
// aloca mais uns nozinhos
if(next_node==NULL)
out_of_mem(-2); // ops, nao consegui!
bad_node = next_node + NODES_PER_BLOCK;
//bad_node aponta para o final do bloco alocado
}
r = next_node++;
// movimenta no para frente, na memoria
// **********Aloca string************
if (next_string + l + 1 >= bad_string){
// a saber:
// l armazena o numero de "letters" da palavra
int block_size = CHARS_PER_BLOCK + l + 1;
next_string= (byte*) malloc (block_size);
if(next_string==NULL)
out_of_mem(-3);
bad_string= next_string+block_size;
}
r->keyword= next_string;
// node->string = buffer_string
for(u= buffer,v= next_string;ord[*u]> 0;u++,v++)
*v= *u;
*v= '\0';
next_string= v+1;
r->rank= current_rank;
// node->rank = rank
// *********STbalancear**********
*q= r;
q= &(r->left); // q eh r->left
qq= &(r->right); // qq eh r->right
while(p){
for(u= buffer,v= p->keyword;ord[*u]==ord[*v];u++,v++);
// outro strcmp (u,v)
if(ord[*u]<ord[*v]){
// less (u,v)
// descendo para direita p=p->right
*qq= p; // isto eh p anterior recebe p agora pela direita
qq= &(p->left); // qq = p->right
p= *qq;
}
else{
// descendo para direita p=p->left
// analogo ao anterior
*q= p;
q= &(p->right);
p= *q;
}
}
*q= *qq= NULL;
//antigo lugar de found:;
}
} // fim_do_while (not final_arquivo!)
// *******************Segunda parte do programa *******************
// *******************Consulta dicionarios ***********************
done:;
if(root!=NULL){
register node*p,*q;
p= root;
root= NULL;
while(1){
// STvisita_pre_ordem
// ************STinverter_arvore************
// Minha nossa!!!!!!!!!!!!!!!!
// O codigo abaixo rotaciona a orientação da arvore em 90 graus
/* LL
T L
L R => T LR
LL LR RL RR R
RR RL */
while(p->left!=NULL){
q= p->left;
p->left= root;
root= p;
p= q;
}
visit:
while(curfile!=NULL){
for(u= p->keyword,v= curfile->curword;ord[*u]==ord[*v];u++,v++);
// estou cansando disto, +1...
// strcmp (u,v)
if(*u =='\0'&&*v==breakchar)
goto word_done;
if(ord[*u]<ord[*v])
// less (u,v)
break;
v= curfile->curword;
l= max_length;
while(1){
register byte *w= curfile->limit;
u = curfile->pos;
if( u + l >= w)
/* Se eu tivesse corrigindo este programa tiria 10% da nota por
mah escolha de identificadores */
// O if acima significa:
// ? (curfile->pos + tamanho_max > limite_buffer) :
// isto evita pegar uma "palavra quebrada" devido uso do buffer
while(ord[*u]> 0)
*v++= *u++;
// strcpy (v, u)
else{
w= u+l; // recua o limite para o final da string
c= *w; // c recebe o valor do caracter final
*w= '\0'; // e o caracter final recebe o caracter cabalistico
while(ord[*u]> 0)
*v++= *u++;
// strcpy (v,u)
*w= c;
}
if(ord[*u]<0){
// breakchar
curfile->pos= u+1;
break;
}
l -= u-curfile->pos;
/* recua o tamanho da palavra pela diferenca
entre pos_total - pos_corrente */
if(l==0){
// palavra nula
curfile->pos= u;
break;
}
if(u==w){
// ? (pos_total = limite_buffer) :
if(ferror(curfile->dfile)){
fprintf(stderr,"%s: File read error on dictionary file!\n",*argv);
return(-9);
}
if(feof(curfile->dfile)){
// terminou o dicionario atual
f = curfile->link;
if (f==curfile)
curfile= NULL;
else{
// proximo dicionario
while(f->link!=curfile)
f= f->link;
f->link= curfile->link;
curfile= f;
}
goto update_done;
}
// Calcula o final do arquivo
curfile->limit= curfile->buf+fread(curfile->buf,1,BUFSIZ,curfile->dfile);
*curfile->limit= '\0';
curfile->pos= curfile->buf;
} else
curfile->pos= u+1;
// avanca curfile->pos para depois da string
}
// reinicia curfile
curfile->endword= v;
*v= breakchar;
update_done:
if(curfile!=NULL){
filenode *sentinel = curfile;
for (f= curfile->link;f!=sentinel;f= f->link){
// Testa quais dicionarios ja foram usados
*f->endword= '\0';
for(u= f->curword,v= curfile->curword;ord[*u]==ord[*v];u++,v++);
// strcmp (u,v)
if(ord[*u]<ord[*v])
curfile= f;
// less (u,v)
*f->endword= breakchar;
}
}
} // fim do while (!curfile)
for(u= p->keyword;*u;u++)putchar(*u);
putchar(breakchar);
word_done:
// ***************STvisita*************
// ordem inversa!
// palavras feitas
if(p->right==NULL){
if(root==NULL)
// fim da subarvore
break;
p = root;
root= root->left;
// visita esquerda
goto visit;
}
else
p= p->right;
} // fim do while (1)
}
return 0;
}