otros/blocksorting/bs.c

   1
   2 #include "bs.h"
   3
   4 /* Block Sorting Optimizado en memoria! */
   5
   6 typedef struct _bs_decode_t_ {
   7         char c;
   8         unsigned long int pos;
   9 } t_BlockSortDecode;
  10
  11 char es_menor(char *data, t_BlockSort *bs, int i, int j);
  12
  13 int _compare(const void *d1, const void *d2) {
  14         t_BlockSortDecode *s1, *s2;
  15
  16         s1 = (t_BlockSortDecode *)d1;
  17         s2 = (t_BlockSortDecode *)d2;
  18
  19         return (s1->c - s2->c);
  20 }
  21
  22 int __compare(const void *d1, const void *d2) {
  23         t_BlockSortData *s1, *s2;
  24
  25         s1 = (t_BlockSortData *)d1;
  26         s2 = (t_BlockSortData *)d2;
  27
  28         return es_menor(s1->bs->data, s1->bs, s1->pos_inicial, s2->pos_inicial);
  29 }
  30
  31 char es_menor(char *data, t_BlockSort *bs, int i, int j)
  32 {
  33         unsigned long int pi, pj, k;
  34
  35         for(k=0; k<bs->len; k++) {
  36                 pi = (i+k)%bs->len;
  37                 pj = (j+k)%bs->len;
  38
  39                 if (data[pi] > data[pj]) return 0;
  40                 if (data[pi] < data[pj]) return 1;
  41         }
  42
  43         return 0;
  44 }
  45
  46 void generar_array(char *data, t_BlockSort *bs)
  47 {
  48         int i;
  49         for(i=0; i<bs->len; i++) {
  50                 bs->array[i].pos_inicial = i;
  51                 bs->array[i].pos_final = (i+bs->len-1)%bs->len;
  52                 bs->array[i].pos_orden = 0;
  53                 bs->array[i].ord = (i==1)?1:0;
  54                 bs->array[i].bs = bs;
  55         }
  56 }
  57
  58 void ordenar_array(char *data, t_BlockSort *bs)
  59 {
  60         /*unsigned long int i, j, min;*/
  61
  62 /*      for(i=0; i<bs->len; i++) {
  63                 min = -1;
  64                 for(j=0; j<bs->len; j++) {
  65                         if (bs->array[j].ord) continue;
  66                         if ((min==-1) || (es_menor(data, bs, j, min)))
  67                                 min = j;
  68                 }
  69
  70                 bs->array[min].ord = 1;
  71                 bs->array[min].pos_orden = i;
  72
  73                 bs->ord[i] = min;
  74         }*/
  75         qsort(bs->array, bs->len, sizeof(t_BlockSortData), __compare);
  76 }
  77
  78 int generar_salida(char *data, t_BlockSort *bs, char *salida)
  79 {
  80         unsigned long int i, k;
  81         k=-1;
  82         for(i=0; i<bs->len; i++) {
  83                 salida[i] = data[bs->array[i].pos_final];
  84                 if (bs->array[i].ord == 1) k = i;
  85         }
  86         return k;
  87 }
  88
  89 void bs_solve(char *in, char *out, t_BlockSort *bs, unsigned long int *k, unsigned int leido)
  90 {
  91         unsigned int l;
  92         l = bs->len;
  93         /* Hack para pedasos menores a la pagina */
  94         if (leido < bs->len) bs->len = leido;
  95         bs->data = in;
  96
  97         generar_array(in, bs);
  98         ordenar_array(in, bs);
  99         (*k) = generar_salida(in, bs, out);
 100
 101         bs->len = l;
 102 }
 103
 104 void bs_restore(char *dst, char *c, unsigned long int k, unsigned long int len)
 105 {
 106         unsigned long int i, current;
 107         t_BlockSortDecode *in;
 108
 109         in = malloc(sizeof(t_BlockSortDecode)*len);
 110
 111         for(i=0; i<len; i++) {
 112                 in[i].c = c[i];
 113                 in[i].pos = i;
 114         }
 115
 116         qsort(in, len, sizeof(t_BlockSortDecode), _compare);
 117
 118         current = k;
 119         i=0;
 120         do {
 121                 dst[i++] = in[current].c;
 122                 current = in[current].pos;
 123         } while (current != k);
 124         free(in);
 125 }
 126
 127 t_BlockSort *bs_create(unsigned long int len)
 128 {
 129         t_BlockSort *tmp;
 130
 131         tmp = malloc(sizeof(t_BlockSort));
 132         tmp->array = malloc(sizeof(t_BlockSortData)*len);
 133         tmp->ord = malloc(sizeof(unsigned long int)*len);
 134         tmp->len = len;
 135
 136         return tmp;
 137 }
 138
 139
 140 void bs_destroy(t_BlockSort *bs)
 141 {
 142         free(bs->array);
 143         free(bs->ord);
 144         free(bs);
 145 }
 146