X-Git-Url: https://git.llucax.com/z.facultad/75.06/jacu.git/blobdiff_plain/f0c0f224ac2a3729cd2d3c0cc5b0f11d35fdf605..35fa025326ae9e6ab219b9016861dc1cedece945:/otros/blocksorting/bs.c diff --git a/otros/blocksorting/bs.c b/otros/blocksorting/bs.c index 80097b9..61dfb78 100644 --- a/otros/blocksorting/bs.c +++ b/otros/blocksorting/bs.c @@ -5,20 +5,26 @@ #include #include -typedef struct _bs_t_ { +typedef struct _bs_data_t_ { unsigned long int pos_inicial; unsigned long int pos_final; unsigned long int pos_orden; char ord; /* indice si esta ordenada */ +} t_BlockSortData; + +typedef struct _bs_t_ { + t_BlockSortData *array; + unsigned long int *ord; + unsigned long int len; } t_BlockSort; -char es_menor(char *data, t_BlockSort *array, int n, int i, int j) +char es_menor(char *data, t_BlockSort *bs, int i, int j) { unsigned long int pi, pj, k; - for(k=0; klen; k++) { + pi = (bs->array[i].pos_inicial+k)%bs->len; + pj = (bs->array[j].pos_inicial+k)%bs->len; if (data[pi] > data[pj]) return 0; if (data[pi] < data[pj]) return 1; @@ -27,58 +33,79 @@ char es_menor(char *data, t_BlockSort *array, int n, int i, int j) return 0; } -void generar_array(char *data, t_BlockSort *array, unsigned long int n) +void generar_array(char *data, t_BlockSort *bs) { int i; - for(i=0; ilen; i++) { + bs->array[i].pos_inicial = i; + bs->array[i].pos_final = (i+bs->len-1)%bs->len; + bs->array[i].pos_orden = 0; + bs->array[i].ord = 0; } } -void ordenar_array(char *data, t_BlockSort *array, t_BlockSort *ord, unsigned long int n) +void ordenar_array(char *data, t_BlockSort *bs) { unsigned long int i, j, min; - for(i=0; ilen; i++) { min = -1; - for(j=0; jlen; j++) { + if (bs->array[j].ord) continue; + if ((min==-1) || (es_menor(data, bs, j, min))) min = j; } - array[min].ord = 1; - array[min].pos_orden = i; + bs->array[min].ord = 1; + bs->array[min].pos_orden = i; - ord[i] = array[min]; + bs->ord[i] = min; } } -int generar_salida(char *data, t_BlockSort *array, char *salida, int n) +int generar_salida(char *data, t_BlockSort *bs, char *salida) { unsigned long int i, k; k=-1; - for(i=0; ilen; i++) { + salida[i] = data[bs->array[bs->ord[i]].pos_final]; + if (bs->array[bs->ord[i]].pos_inicial == 0) k = i; } return k; } -void block_sorting(char *in, char *out, unsigned long int *k, unsigned long int len) +void bs_solve(char *in, char *out, t_BlockSort *bs, unsigned long int *k, unsigned int leido) +{ + unsigned int l; + l = bs->len; + /* Hack para pedasos menores a la pagina */ + if (leido < bs->len) bs->len = leido; + + generar_array(in, bs); + ordenar_array(in, bs); + (*k) = generar_salida(in, bs, out); + + bs->len = l; +} + +t_BlockSort *bs_create(unsigned int len) { - static t_BlockSort *array = NULL; - static t_BlockSort *ord = NULL; + t_BlockSort *tmp; - if (!array) array = malloc(sizeof(t_BlockSort)*len); - if (!ord) ord = malloc(sizeof(t_BlockSort)*len); + tmp = malloc(sizeof(t_BlockSort)); + tmp->array = malloc(sizeof(t_BlockSortData)*len); + tmp->ord = malloc(sizeof(unsigned long int)*len); + tmp->len = len; - generar_array(in, array, len); - ordenar_array(in, array, ord, len); - (*k) = generar_salida(in, ord, out, len); + return tmp; +} + + +void bs_destroy(t_BlockSort *bs) +{ + free(bs->array); + free(bs->ord); + free(bs); } int main(int argc, char *argv[]) @@ -88,6 +115,7 @@ int main(int argc, char *argv[]) unsigned long int len, i, k; FILE *fp; char c; + t_BlockSort *bs; if (argc != 3) { printf("Modo de uso : %s \n", argv[0]); @@ -100,18 +128,23 @@ int main(int argc, char *argv[]) data = malloc(sizeof(char)*len); salida = malloc(sizeof(char)*len); + bs = bs_create(len); + while ((c = fgetc(fp)) != EOF) { - memset(salida, 0, len*sizeof(char)); i = 0; while ((c!=EOF) && (i < len)) { data[i++] = c; c = fgetc(fp); } - block_sorting(data, salida, &k, (i