otros/blocksorting/bs.c

   1
   2 /* Block Sorting Optimizado en memoria! */
   3
   4 #include <string.h>
   5 #include <stdlib.h>
   6 #include <stdio.h>
   7
   8 typedef struct _bs_data_t_ {
   9         unsigned long int pos_inicial;
  10         unsigned long int pos_final;
  11         unsigned long int pos_orden;
  12         char ord; /* indice si esta ordenada */
  13 } t_BlockSortData;
  14
  15 typedef struct _bs_t_ {
  16         t_BlockSortData *array;
  17         unsigned long int *ord;
  18         unsigned long int len;
  19 } t_BlockSort;
  20
  21 typedef struct _bs_decode_t_ {
  22         char c;
  23         unsigned long int pos;
  24 } t_BlockSortDecode;
  25
  26 int _compare(const void *d1, const void *d2) {
  27         t_BlockSortDecode *s1, *s2;
  28
  29         s1 = (t_BlockSortDecode *)d1;
  30         s2 = (t_BlockSortDecode *)d2;
  31
  32         return (s1->c - s2->c);
  33 }
  34
  35 char es_menor(char *data, t_BlockSort *bs, int i, int j)
  36 {
  37         unsigned long int pi, pj, k;
  38
  39         for(k=0; k<bs->len; k++) {
  40                 pi = (bs->array[i].pos_inicial+k)%bs->len;
  41                 pj = (bs->array[j].pos_inicial+k)%bs->len;
  42
  43                 if (data[pi] > data[pj]) return 0;
  44                 if (data[pi] < data[pj]) return 1;
  45         }
  46
  47         return 0;
  48 }
  49
  50 void generar_array(char *data, t_BlockSort *bs)
  51 {
  52         int i;
  53         for(i=0; i<bs->len; i++) {
  54                 bs->array[i].pos_inicial = i;
  55                 bs->array[i].pos_final = (i+bs->len-1)%bs->len;
  56                 bs->array[i].pos_orden = 0;
  57                 bs->array[i].ord = 0;
  58         }
  59 }
  60
  61 void ordenar_array(char *data, t_BlockSort *bs)
  62 {
  63         unsigned long int i, j, min;
  64
  65         for(i=0; i<bs->len; i++) {
  66                 min = -1;
  67                 for(j=0; j<bs->len; j++) {
  68                         if (bs->array[j].ord) continue;
  69                         if ((min==-1) || (es_menor(data, bs, j, min)))
  70                                 min = j;
  71                 }
  72
  73                 bs->array[min].ord = 1;
  74                 bs->array[min].pos_orden = i;
  75
  76                 bs->ord[i] = min;
  77         }
  78 }
  79
  80 int generar_salida(char *data, t_BlockSort *bs, char *salida)
  81 {
  82         unsigned long int i, k;
  83         k=-1;
  84         for(i=0; i<bs->len; i++) {
  85                 salida[i] = data[bs->array[bs->ord[i]].pos_final];
  86                 if (bs->array[bs->ord[i]].pos_inicial == 0) k = i;
  87         }
  88         return k;
  89 }
  90
  91 void bs_solve(char *in, char *out, t_BlockSort *bs, unsigned long int *k, unsigned int leido)
  92 {
  93         unsigned int l;
  94         l = bs->len;
  95         /* Hack para pedasos menores a la pagina */
  96         if (leido < bs->len) bs->len = leido;
  97
  98         generar_array(in, bs);
  99         ordenar_array(in, bs);
 100         (*k) = generar_salida(in, bs, out);
 101
 102         bs->len = l;
 103 }
 104
 105 void bs_restore(char *dst, char *c, unsigned long int k, unsigned long int len)
 106 {
 107         unsigned long int i, current;
 108         t_BlockSortDecode *in;
 109
 110         in = malloc(sizeof(t_BlockSortDecode)*len);
 111
 112         for(i=0; i<len; i++) {
 113                 in[i].c = c[i];
 114                 in[i].pos = i;
 115         }
 116
 117         qsort(in, len, sizeof(t_BlockSortDecode), _compare);
 118
 119         current = k;
 120         i=0;
 121         do {
 122                 dst[i++] = in[current].c;
 123                 current = in[current].pos;
 124         } while (current != k);
 125         free(in);
 126 }
 127
 128 t_BlockSort *bs_create(unsigned int len)
 129 {
 130         t_BlockSort *tmp;
 131
 132         tmp = malloc(sizeof(t_BlockSort));
 133         tmp->array = malloc(sizeof(t_BlockSortData)*len);
 134         tmp->ord = malloc(sizeof(unsigned long int)*len);
 135         tmp->len = len;
 136
 137         return tmp;
 138 }
 139
 140
 141 void bs_destroy(t_BlockSort *bs)
 142 {
 143         free(bs->array);
 144         free(bs->ord);
 145         free(bs);
 146 }
 147
 148 int main(int argc, char *argv[])
 149 {
 150         char *data;
 151         char *salida;
 152         unsigned long int len, i, k;
 153         FILE *fp;
 154         char c;
 155         t_BlockSort *bs;
 156
 157         if (argc != 3) {
 158                 printf("Modo de uso : %s <archivo datos> <tamaño pagina>\n", argv[0]);
 159                 return 0;
 160         }
 161
 162         fp = fopen(argv[1], "r");
 163         len = atoi(argv[2]);
 164
 165         data = malloc(sizeof(char)*len);
 166         salida = malloc(sizeof(char)*(len+1));
 167
 168         salida[len] = '\0';
 169         bs = bs_create(len);
 170
 171         while ((c = fgetc(fp)) != EOF) {
 172                 i = 0;
 173                 while ((c!=EOF) && (i < len)) {
 174                         data[i++] = c;
 175                         c = fgetc(fp);
 176                 }
 177                 bs_solve(data, salida, bs, &k, i);
 178
 179                 /* XXX ACA SALIDA DEBERIA PASAR A LA SIGUIENTE ETAPA XXX */
 180                 printf("%s -> %ld\n", salida, k);
 181         }
 182         fclose(fp);
 183         bs_destroy(bs);
 184
 185         free(data);
 186         free(salida);
 187         return 0;
 188 }
 189
 190