* Agrego bs_restore para rehacer el array original.

[z.facultad/75.06/jacu.git] / otros / blocksorting / bs.c

diff --git a/otros/blocksorting/bs.c b/otros/blocksorting/bs.c
index 61dfb78d6a51e38f8d798abea2f61675849a2e29..13b7824e46986dff9f50cd057e9c8c873a2c269d 100644 (file)
--- a/otros/blocksorting/bs.c
+++ b/otros/blocksorting/bs.c
@@ -18,6 +18,20 @@ typedef struct _bs_t_ {
        unsigned long int len;
 } t_BlockSort;
 
+typedef struct _bs_decode_t_ {
+       char c;
+       unsigned long int pos;
+} t_BlockSortDecode;
+
+int _compare(const void *d1, const void *d2) {
+       t_BlockSortDecode *s1, *s2;
+
+       s1 = (t_BlockSortDecode *)d1;
+       s2 = (t_BlockSortDecode *)d2;
+
+       return (s1->c - s2->c);
+}
+
 char es_menor(char *data, t_BlockSort *bs, int i, int j)
 {
        unsigned long int pi, pj, k;
@@ -88,6 +102,29 @@ void bs_solve(char *in, char *out, t_BlockSort *bs, unsigned long int *k, unsign
        bs->len = l;
 }
 
+void bs_restore(char *dst, char *c, unsigned long int k, unsigned long int len)
+{
+       unsigned long int i, current;
+       t_BlockSortDecode *in;
+
+       in = malloc(sizeof(t_BlockSortDecode)*len);
+
+       for(i=0; i<len; i++) {
+               in[i].c = c[i];
+               in[i].pos = i;
+       }
+
+       qsort(in, len, sizeof(t_BlockSortDecode), _compare);
+       
+       current = k;
+       i=0;
+       do {
+               dst[i++] = in[current].c;
+               current = in[current].pos;
+       } while (current != k);
+       free(in);
+}
+
 t_BlockSort *bs_create(unsigned int len)
 {
        t_BlockSort *tmp;
@@ -116,7 +153,7 @@ int main(int argc, char *argv[])
        FILE *fp;
        char c;
        t_BlockSort *bs;
-
+       
        if (argc != 3) {
                printf("Modo de uso : %s <archivo datos> <tamaño pagina>\n", argv[0]);
                return 0;
@@ -126,8 +163,9 @@ int main(int argc, char *argv[])
        len = atoi(argv[2]);
 
        data = malloc(sizeof(char)*len);
-       salida = malloc(sizeof(char)*len);
+       salida = malloc(sizeof(char)*(len+1));
 
+       salida[len] = '\0';
        bs = bs_create(len);
 
        while ((c = fgetc(fp)) != EOF) {
@@ -139,6 +177,7 @@ int main(int argc, char *argv[])
                bs_solve(data, salida, bs, &k, i);
 
                /* XXX ACA SALIDA DEBERIA PASAR A LA SIGUIENTE ETAPA XXX */
+               printf("%s -> %ld\n", salida, k);
        }
        fclose(fp);
        bs_destroy(bs);