Mis 2 colaboraciones.

diff --git a/otros/blocksorting/Btree.cpp b/otros/blocksorting/Btree.cpp
new file mode 100644 (file)
index 0000000..027d84e
--- /dev/null
+++ b/otros/blocksorting/Btree.cpp
@@ -0,0 +1,389 @@
+#include <iostream.h>\r
+#include <stdlib.h>\r
+\r
+#define TAMANO 1000\r
+\r
+struct stclave {\r
+   int valor;\r
+   long registro;\r
+};\r
+\r
+class bnodo {\r
+  public:\r
+   bnodo(int nClaves); // Constructor\r
+   ~bnodo();           // Destructor\r
+ \r
+  private:\r
+   int clavesUsadas;   // Claves usadas en el nodo\r
+   stclave *clave;     // Array de claves del nodo\r
+   bnodo **puntero;    // Array de punteros a bnodo\r
+   bnodo *padre;       // Puntero a nodo padre\r
+\r
+  friend class btree;\r
+};\r
+\r
+typedef bnodo *pbnodo;\r
+\r
+bnodo::bnodo(int nClaves)\r
+{\r
+   clavesUsadas = 0;\r
+   clave = new stclave[nClaves];\r
+   puntero = new pbnodo[nClaves+1];\r
+   padre = NULL;\r
+}\r
+\r
+bnodo::~bnodo()\r
+{\r
+   delete[] clave;\r
+   delete[] puntero;\r
+}\r
+\r
+class btree {\r
+  public:\r
+   btree(int nClv);\r
+   ~btree();\r
+   long Buscar(int clave);\r
+   bool Insertar(stclave clave);\r
+   void Borrar(int clave);\r
+   void Mostrar();\r
+\r
+  private:\r
+   stclave *lista;\r
+   pbnodo *listapunt;\r
+   void Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2);\r
+   void BorrarClave(pbnodo nodo, int valor);\r
+   void BorrarNodo(pbnodo nodo);\r
+   void PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre);\r
+   void PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre);\r
+   void FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre);\r
+   void Ver(pbnodo nodo);\r
+   int nClaves, nodosMinimos;\r
+   pbnodo Entrada;\r
+};\r
+\r
+btree::btree(int nClv) : nClaves(nClv)\r
+{\r
+   lista = new stclave[nClaves+1];\r
+   listapunt = new pbnodo[nClaves+2];\r
+   nodosMinimos = nClaves/2; // ((nClaves+1)/2)-1;\r
+   Entrada = NULL;\r
+}\r
+\r
+btree::~btree()\r
+{\r
+   delete[] lista;\r
+   delete[] listapunt;\r
+   // Destruir árbol, algoritmo recursivo:\r
+   BorrarNodo(Entrada);\r
+}\r
+\r
+void btree::BorrarNodo(pbnodo nodo)\r
+{\r
+   int i;\r
+\r
+   if(!nodo) return;\r
+   for(i = 0; i <= nodo->clavesUsadas; i++) BorrarNodo(nodo->puntero[i]);\r
+   delete nodo;\r
+}\r
+\r
+void btree::Mostrar()\r
+{\r
+   cout << "arbol" << endl;\r
+   Ver(Entrada);\r
+   cout << "-----" << endl;\r
+}\r
+\r
+void btree::Ver(pbnodo nodo)\r
+{\r
+   int i;\r
+\r
+   if(!nodo) return;\r
+   for(i = 0; i < nodo->clavesUsadas-1; i++) cout << nodo->clave[i].valor << "-";\r
+   if(nodo->clavesUsadas) cout << nodo->clave[i].valor << " [";\r
+   if(nodo->padre) cout << (nodo->padre)->clave[0].valor; else cout << "*";\r
+   cout << "]" << endl;\r
+   for(i = 0; i <= nodo->clavesUsadas; i++) Ver(nodo->puntero[i]);\r
+}\r
+\r
+long btree::Buscar(int clave)\r
+{\r
+   pbnodo nodo = Entrada;\r
+   int i;\r
+\r
+   while(nodo) {\r
+      i = 0;\r
+      while(i < nodo->clavesUsadas && (nodo->clave[i].valor < clave)) i++;\r
+      if(nodo->clave[i].valor == clave) return nodo->clave[i].registro;\r
+      else nodo = nodo->puntero[i];\r
+   }\r
+   return -1L;\r
+}\r
+\r
+bool btree::Insertar(stclave clave)\r
+{\r
+   pbnodo nodo, padre;\r
+   int i;\r
+\r
+   // Asegurarse de que la clave no está en el árbol\r
+   padre = nodo = Entrada;\r
+   while(nodo) {\r
+      padre = nodo;\r
+      i = 0;\r
+      while(i < nodo->clavesUsadas && (nodo->clave[i].valor < clave.valor)) i++;\r
+      if(nodo->clave[i].valor == clave.valor && i < nodo->clavesUsadas) return false;\r
+      else nodo = nodo->puntero[i];\r
+   }\r
+   nodo = padre;\r
+   Inserta(clave, nodo, NULL, NULL);\r
+   return true;\r
+}\r
+\r
+void btree::Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2)\r
+{\r
+   pbnodo padre, nuevo;\r
+   int i, j;\r
+   bool salir = false;\r
+\r
+   // Insertar nueva clave en nodo:\r
+   do {\r
+      if(!nodo)\r
+      {\r
+         nodo = new bnodo(nClaves);\r
+         nodo->clavesUsadas = 0;\r
+         nodo->padre = NULL;\r
+         Entrada = nodo;\r
+      }\r
+      padre = nodo->padre;\r
+      if(nodo->clavesUsadas == nClaves) // overflow\r
+      {\r
+         // Nodo derecho\r
+         nuevo = new bnodo(nClaves);\r
+         // Construye lista ordenada:\r
+         i = 0;\r
+         while(nodo->clave[i].valor < clave.valor && i < nClaves) {\r
+            lista[i] = nodo->clave[i];\r
+            listapunt[i] = nodo->puntero[i];\r
+            i++;\r
+         }\r
+         lista[i] = clave;\r
+         listapunt[i] = hijo1;\r
+         listapunt[i+1] = hijo2;\r
+         while(i < nClaves) {\r
+            lista[i+1] = nodo->clave[i];\r
+            listapunt[i+2] = nodo->puntero[i+1];\r
+            i++;\r
+         }\r
+         // Dividir nodos:\r
+         // Nodo izquierdo:\r
+         nodo->clavesUsadas = nClaves/2;\r
+         for(j = 0; j < nodo->clavesUsadas; j++) {\r
+            nodo->clave[j] = lista[j];\r
+            nodo->puntero[j] = listapunt[j];\r
+         }\r
+         nodo->puntero[nodo->clavesUsadas] = listapunt[nodo->clavesUsadas];\r
+\r
+         // Nodo derecho:\r
+         nuevo->clavesUsadas = nClaves - nodo->clavesUsadas;\r
+         for(j = 0; j < nuevo->clavesUsadas; j++) {\r
+            nuevo->clave[j] = lista[j+(nClaves/2)+1];\r
+            nuevo->puntero[j] = listapunt[j+(nClaves/2)+1];\r
+         }\r
+         nuevo->puntero[nuevo->clavesUsadas] = listapunt[nClaves+1];\r
+\r
+         for(j = 0; j <= nodo->clavesUsadas; j++)\r
+            if(nodo->puntero[j]) (nodo->puntero[j])->padre = nodo;\r
+         for(j = 0; j <= nuevo->clavesUsadas; j++)\r
+            if(nuevo->puntero[j]) (nuevo->puntero[j])->padre = nuevo;\r
+\r
+         clave = lista[nClaves/2];\r
+         hijo1 = nodo;\r
+         hijo2 = nuevo;\r
+         nodo = padre;\r
+      }\r
+      else\r
+      {\r
+         // Inserta nueva clave en su lugar:\r
+         i = 0;\r
+         if(nodo->clavesUsadas > 0) {\r
+            while(nodo->clave[i].valor < clave.valor && i < nodo->clavesUsadas) i++;\r
+            for(j = nodo->clavesUsadas; j > i; j--)\r
+               nodo->clave[j] = nodo->clave[j-1];\r
+            for(j = nodo->clavesUsadas+1; j > i; j--)\r
+               nodo->puntero[j] = nodo->puntero[j-1];\r
+         }\r
+         nodo->clavesUsadas++;\r
+         nodo->clave[i] = clave;\r
+         nodo->puntero[i] = hijo1;\r
+         nodo->puntero[i+1] = hijo2;\r
+         if(hijo1) hijo1->padre = nodo;\r
+         if(hijo2) hijo2->padre = nodo;\r
+         salir = true;\r
+      }\r
+   } while(!salir);\r
+}\r
+\r
+void btree::Borrar(int valor)\r
+{\r
+   pbnodo nodo;\r
+   bool encontrado = false;\r
+   int i;\r
+\r
+   // Busca el nodo que contiene la clave, si existe\r
+   nodo = Entrada;\r
+   while(nodo && !encontrado) {\r
+      i = 0;\r
+      while(i < nodo->clavesUsadas && (nodo->clave[i].valor < valor)) i++;\r
+      if(nodo->clave[i].valor == valor && i < nodo->clavesUsadas) encontrado = true;\r
+      else nodo = nodo->puntero[i];\r
+   }\r
+   if(encontrado) BorrarClave(nodo, valor);\r
+}\r
+\r
+void btree::BorrarClave(pbnodo nodo, int valor)\r
+{\r
+   pbnodo actual, derecha, izquierda, padre;\r
+   int posClavePadre, pos, i;\r
+\r
+   // Buscar posición dentro de lista de claves:\r
+   pos = 0;\r
+   while(nodo->clave[pos].valor < valor) pos++;\r
+\r
+   // ¿Está la clave en un nodo hoja?\r
+   if(nodo->puntero[0]) { // No, se trata de un nodo intermedio\r
+      // Buscar actual del valor siguiente:\r
+      actual = nodo->puntero[pos+1];\r
+      while(actual->puntero[0]) actual = actual->puntero[0];\r
+      // Intercambiar con el valor siguiente:\r
+      nodo->clave[pos] = actual->clave[0];\r
+      // La posición de la clave a borrar en ahora la 0:\r
+      pos = 0;\r
+   } else actual = nodo;\r
+\r
+   // Borrar clave\r
+   for(i = pos; i < actual->clavesUsadas; i++)\r
+      actual->clave[i] = actual->clave[i+1];\r
+   actual->clavesUsadas--;\r
+\r
+   if(actual == Entrada && actual->clavesUsadas == 0) {\r
+      delete actual;\r
+      Entrada = NULL;\r
+      return;\r
+   }\r
+\r
+   // ¿Es el número de claves mayor que el mínimo para el nodo?\r
+   if(actual == Entrada || actual->clavesUsadas >= nodosMinimos) return;\r
+\r
+   do {\r
+      // El número de claves es menor que el mínimo:\r
+      // Buscar nodos a derecha e izquierda:\r
+      padre = actual->padre;\r
+      for(posClavePadre = 0;\r
+         padre->puntero[posClavePadre] != actual;\r
+         posClavePadre++);\r
+      if(posClavePadre > 0)\r
+         izquierda = padre->puntero[posClavePadre-1];\r
+      else izquierda = NULL;\r
+      if(posClavePadre < padre->clavesUsadas)\r
+         derecha = padre->puntero[posClavePadre+1];\r
+      else derecha = NULL;\r
+\r
+      // Intentar pasar una clave de un nodo cercano:\r
+      if(derecha && derecha->clavesUsadas > nodosMinimos)\r
+         PasarClaveDerecha(derecha, padre, actual, posClavePadre);\r
+      else if(izquierda && izquierda->clavesUsadas > nodosMinimos)\r
+         PasarClaveIzquierda(izquierda, padre, actual, posClavePadre-1);\r
+      // Si no fue posible, fundir con un nodo cercano y una clave de padre:\r
+      else if(derecha) // Usar nodo derecho\r
+         FundirNodo(actual, padre, derecha, posClavePadre);\r
+      else             // Usar el nodo izquierdo\r
+         FundirNodo(izquierda, padre, actual, posClavePadre-1);\r
+      // Vuelta a empezar:\r
+      actual = padre;\r
+   } while(actual && actual != Entrada && actual->clavesUsadas < nodosMinimos);\r
+}\r
+\r
+void btree::PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre)\r
+{\r
+   int i;\r
+\r
+   nodo->clave[nodo->clavesUsadas] = padre->clave[posClavePadre];\r
+   nodo->clavesUsadas++;\r
+   padre->clave[posClavePadre] = derecha->clave[0];\r
+   nodo->puntero[nodo->clavesUsadas] = derecha->puntero[0];\r
+   if(derecha->puntero[0]) derecha->puntero[0]->padre = nodo;\r
+   for(i = 0; i < derecha->clavesUsadas; i++) derecha->clave[i] = derecha->clave[i+1];\r
+   for(i = 0; i <= derecha->clavesUsadas; i++) derecha->puntero[i] = derecha->puntero[i+1];\r
+   derecha->clavesUsadas--;\r
+}\r
+\r
+void btree::PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre)\r
+{\r
+   int i;\r
+\r
+   for(i = nodo->clavesUsadas; i > 0; i--) nodo->clave[i] = nodo->clave[i-1];\r
+   for(i = nodo->clavesUsadas+1; i > 0; i--) nodo->puntero[i] = nodo->puntero[i-1];\r
+   nodo->clavesUsadas++;\r
+   nodo->clave[0] = padre->clave[posClavePadre];\r
+   padre->clave[posClavePadre] = izquierda->clave[izquierda->clavesUsadas-1];\r
+   nodo->puntero[0] = izquierda->puntero[izquierda->clavesUsadas];\r
+   if(nodo->puntero[0]) nodo->puntero[0]->padre = nodo;\r
+   izquierda->clavesUsadas--;\r
+}\r
+\r
+void btree::FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre)\r
+{\r
+   int i;\r
+\r
+   izquierda->clave[izquierda->clavesUsadas] = padre->clave[posClavePadre];\r
+   padre->clavesUsadas--;\r
+   for(i = posClavePadre; i < padre->clavesUsadas; i++) {\r
+      padre->clave[i] = padre->clave[i+1];\r
+      padre->puntero[i+1] = padre->puntero[i+2];\r
+   }\r
+   izquierda->clavesUsadas++;\r
+   for(i = 0; i < derecha->clavesUsadas; i++)\r
+      izquierda->clave[izquierda->clavesUsadas+i] = derecha->clave[i];\r
+   for(i = 0; i <= derecha->clavesUsadas; i++) {\r
+      izquierda->puntero[izquierda->clavesUsadas+i] = derecha->puntero[i];\r
+      if(derecha->puntero[i]) derecha->puntero[i]->padre = izquierda;\r
+   }\r
+   izquierda->clavesUsadas += derecha->clavesUsadas;\r
+   if(padre == Entrada && padre->clavesUsadas == 0) { // Cambio de entrada\r
+      Entrada = izquierda;\r
+      Entrada->padre = NULL;\r
+      delete padre;\r
+      padre = NULL;\r
+   }\r
+   delete derecha;\r
+}\r
+\r
+int main()\r
+{\r
+   int matriz[TAMANO];\r
+   btree arbol(500);\r
+   stclave clave;\r
+   int i;\r
+
+//   srand(time(NULL));
+   for(i = 0; i < TAMANO; i++) {
+      do {
+         matriz[i] = rand()%10000;
+         clave.valor = matriz[i];
+         clave.registro = i;
+      } while(!arbol.Insertar(clave));
+   }
+
+   cout << "mostrar: " << endl;
+   arbol.Mostrar();
+
+   cout << "Buscar elemento 23: " << matriz[23] << " posicion: " <<\r
+     arbol.Buscar(matriz[23]) << endl;\r
+
+   for(i = 0; i < TAMANO; i++) {\r
+      cout << "Borrar: [" << i << "]: " << matriz[i] << endl;\r
+      arbol.Borrar(matriz[i]);\r
+//      arbol.Mostrar();\r
+   }\r
+   arbol.Mostrar();\r
+   return 0;\r
+}\r

diff --git a/otros/blocksorting/Makefile b/otros/blocksorting/Makefile
new file mode 100644 (file)
index 0000000..cc0efbf
--- /dev/null
+++ b/otros/blocksorting/Makefile
@@ -0,0 +1,74 @@
+# Makefile de ejemplo para C++
+# 
+# Creado: jue abr 15 15:34:19 ART 2004
+#
+# Copyleft 2004 - Leandro Lucarella, Bajo licencia GPL [http://www.gnu.org/]
+#
+
+# CONFIGURACION
+################
+
+# Nombre del ejecutable.
+target = bs 
+
+# Extensión de los archivos a compilar (c para C, cpp o cc o cxx para C++).
+extension = c
+
+# Archivos con el código fuente que componen el ejecutable. Si no se especifica,
+# toma todos los archivos con la extensión mencionada. Para especificar hay que
+# descomentar la línea (quitarle el '#' del principio).
+# NOTA: No poner cabeceras (.h). 
+#fuentes = entrada.cpp
+
+# Si es un programa GTK+, descomentá (quitale el '#' a) la siguiente línea.
+#gtk = si 
+
+
+# CONFIGURACION "AVANZADA"
+###########################
+
+# Opciones para el compilador C.
+#CFLAGS = -Wall -ggdb -ansi -pedantic -DDEBUG
+CFLAGS = -Wall -O3 -ansi -pedantic -DNDEBUG -g
+
+# Opciones para el compilador C++.
+#CXXFLAGS = $(CFLAGS) -fno-inline
+CXXFLAGS = $(CFLAGS)
+
+
+# VARIABLES CALCULADAS A PARTIR DE LA CONFIGURACION
+####################################################
+
+# Agrego flags y libs de GTK+ de ser necesario.
+ifdef gtk
+CFLAGS += $(shell pkg-config --cflags gtk+-2.0)
+CXXFLAGS += $(shell pkg-config --cflags gtk+-2.0)
+LDFLAGS += $(shell pkg-config --libs gtk+-2.0)
+endif
+
+# Uso enlazador de c++ si es código no C.
+ifeq ($(extension), c)
+enlazador = $(CC)
+else
+enlazador = $(CXX)
+endif
+
+# Si no especifica archivos, tomo todos.
+fuentes ?= $(wildcard *.$(extension))
+
+
+# REGLAS
+#########
+
+.PHONY: all clean
+
+all: $(target)
+
+o_files = $(patsubst %.$(extension),%.o,$(fuentes))
+
+$(target): $(o_files)
+       $(enlazador) $(LDFLAGS) $(o_files) $(LOADLIBES) $(LDLIBS) -o $(target)
+
+clean:
+       @$(RM) -fv *.o $(target)
+

diff --git a/otros/blocksorting/bs.c b/otros/blocksorting/bs.c
new file mode 100644 (file)
index 0000000..e5dd16f
--- /dev/null
+++ b/otros/blocksorting/bs.c
@@ -0,0 +1,116 @@
+
+/* Block Sorting Optimizado en memoria! */
+
+#include <string.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+typedef struct _bs_t_ {
+       unsigned long int pos_inicial;
+       unsigned long int pos_final;
+       unsigned long int pos_orden;
+       char ord; /* indice si esta ordenada */
+} t_BlockSort;
+
+char es_menor(char *data, t_BlockSort *array, int n, int i, int j)
+{
+       unsigned long int pi, pj, k;
+
+       for(k=0; k<n; k++) {
+               pi = (array[i].pos_inicial+k)%n;
+               pj = (array[j].pos_inicial+k)%n;
+
+               if (data[pi] > data[pj]) return 0;
+               if (data[pi] < data[pj]) return 1;
+       }
+
+       return 0;
+}
+
+void generar_array(char *data, t_BlockSort *array, unsigned long int n)
+{
+       int i;
+       for(i=0; i<n; i++) {
+               array[i].pos_inicial = i;
+               array[i].pos_final = (i+n-1)%n;
+               array[i].pos_orden = 0;
+               array[i].ord = 0;
+       }
+}
+
+void ordenar_array(char *data, t_BlockSort *array, unsigned long int n)
+{
+       unsigned long int i, j, min;
+       for(i=0; i<n; i++) {
+               min = -1;
+               for(j=0; j<n; j++) {
+                       if (array[j].ord) continue;
+                       if ((min==-1) || (es_menor(data, array, n, j, min)))
+                               min = j;
+               }
+
+               array[min].ord = 1;
+               array[min].pos_orden = i;
+       }
+}
+
+int generar_salida(char *data, t_BlockSort *array, char *salida, int n)
+{
+       unsigned long int i, j, k;
+       k=-1;
+       for(i=0; i<n; i++) {
+               for(j=0; j<n; j++) {
+                       if (array[j].pos_orden == i) {
+                               salida[i] = data[array[j].pos_final];
+                               if (array[j].pos_inicial == 0) k = i;
+                       }
+               }
+       }
+
+       return k;
+}
+
+void block_sorting(char *in, char *out, unsigned long int *k, unsigned long int len)
+{
+       t_BlockSort *array;
+
+       array = malloc(sizeof(t_BlockSort)*len);
+
+       generar_array(in, array, len);
+       ordenar_array(in, array, len);
+       (*k) = generar_salida(in, array, out, len);
+
+       free(array);
+}
+
+int main(int argc, char *argv[])
+{
+       char *data; 
+       char *salida;
+       unsigned long int len, i, k;
+       FILE *fp;
+
+       if (argc != 3) {
+               printf("Modo de uso : %s <archivo datos> <tamaño pagina>\n", argv[0]);
+               return 0;
+       }
+
+       fp = fopen(argv[1], "r");
+       len = atoi(argv[2]);
+
+       data = malloc(sizeof(char)*len);
+       salida = malloc(sizeof(char)*len);
+       memset(salida, 0, len*sizeof(char));
+
+       for(i=0; i<len; i++)
+               data[i] = fgetc(fp);
+
+       fclose(fp);
+
+       block_sorting(data, salida, &k, len);
+
+       printf("Salida = (%s) con k=%ld\n", salida, k);
+       return 0;
+}
+
+

diff --git a/otros/rle/Makefile b/otros/rle/Makefile
new file mode 100644 (file)
index 0000000..65caa33
--- /dev/null
+++ b/otros/rle/Makefile
@@ -0,0 +1,74 @@
+# Makefile de ejemplo para C++
+# 
+# Creado: jue abr 15 15:34:19 ART 2004
+#
+# Copyleft 2004 - Leandro Lucarella, Bajo licencia GPL [http://www.gnu.org/]
+#
+
+# CONFIGURACION
+################
+
+# Nombre del ejecutable.
+target = rle 
+
+# Extensión de los archivos a compilar (c para C, cpp o cc o cxx para C++).
+extension = c
+
+# Archivos con el código fuente que componen el ejecutable. Si no se especifica,
+# toma todos los archivos con la extensión mencionada. Para especificar hay que
+# descomentar la línea (quitarle el '#' del principio).
+# NOTA: No poner cabeceras (.h). 
+#fuentes = entrada.cpp
+
+# Si es un programa GTK+, descomentá (quitale el '#' a) la siguiente línea.
+#gtk = si 
+
+
+# CONFIGURACION "AVANZADA"
+###########################
+
+# Opciones para el compilador C.
+#CFLAGS = -Wall -ggdb -ansi -pedantic -DDEBUG
+CFLAGS = -Wall -O3 -ansi -pedantic -DNDEBUG -g
+
+# Opciones para el compilador C++.
+#CXXFLAGS = $(CFLAGS) -fno-inline
+CXXFLAGS = $(CFLAGS)
+
+
+# VARIABLES CALCULADAS A PARTIR DE LA CONFIGURACION
+####################################################
+
+# Agrego flags y libs de GTK+ de ser necesario.
+ifdef gtk
+CFLAGS += $(shell pkg-config --cflags gtk+-2.0)
+CXXFLAGS += $(shell pkg-config --cflags gtk+-2.0)
+LDFLAGS += $(shell pkg-config --libs gtk+-2.0)
+endif
+
+# Uso enlazador de c++ si es código no C.
+ifeq ($(extension), c)
+enlazador = $(CC)
+else
+enlazador = $(CXX)
+endif
+
+# Si no especifica archivos, tomo todos.
+fuentes ?= $(wildcard *.$(extension))
+
+
+# REGLAS
+#########
+
+.PHONY: all clean
+
+all: $(target)
+
+o_files = $(patsubst %.$(extension),%.o,$(fuentes))
+
+$(target): $(o_files)
+       $(enlazador) $(LDFLAGS) $(o_files) $(LOADLIBES) $(LDLIBS) -o $(target)
+
+clean:
+       @$(RM) -fv *.o $(target)
+

diff --git a/otros/rle/NO_COMPROBADO b/otros/rle/NO_COMPROBADO
new file mode 100644 (file)
index 0000000..e69de29

diff --git a/otros/rle/rle.c b/otros/rle/rle.c
new file mode 100644 (file)
index 0000000..b2ff114
--- /dev/null
+++ b/otros/rle/rle.c
@@ -0,0 +1,225 @@
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#define SIZE 10
+#define BIT_SIZE 4
+#define MIN_LEN 2
+
+/* Insertar un char al final */
+void push_end(char *s, char c);
+int esta_en_memoria(char *memoria, char *pal, int *len);
+
+void out_ini(char *f);
+void out_bit(char b);
+void out_char(char c);
+void out_data(char len, char pos);
+void out_end();
+
+unsigned int out_buffer;
+FILE *out;
+int bit_count;
+
+int main(int argc, char *argv[])
+{
+       int mc, ic; /* Contadores */
+       char memoria[SIZE];
+       char inspeccion[SIZE];
+       char c, i; /* caracter leido */
+       FILE *fp;
+
+       /* inicio todo lindo */
+       memset(memoria, 1, SIZE);
+       memset(inspeccion, 1, SIZE);
+       mc = ic = 0;
+
+       fp = fopen(argv[1], "rt");
+
+       /* llego INSPECCION */
+       while (((c = fgetc(fp)) != EOF) && (ic < SIZE)) {
+               push_end(inspeccion, c);
+               ic++;
+       }
+
+       ungetc(c, fp);
+
+       out_ini(argv[2]);
+       /* Comienza el juevo */
+       while (c != EOF) {
+               int pos, len;
+               /* Busco */
+               pos = esta_en_memoria(memoria, inspeccion, &len);
+               if (pos != -1) {
+                       /* La cadena se repite! */
+                       printf("[0,%d,%d]\n", pos, len);
+                       out_bit(0);
+                       out_data(len, pos);
+
+                       /* Tengo que meter caracteres */
+                       for(i=0; i<len; i++) {
+                               push_end(memoria, inspeccion[0]);
+                               c=fgetc(fp);
+                               if (c != EOF)
+                                       push_end(inspeccion, c);
+                       }
+               } else {
+                       /* la cadena no se repite, saco un bit 1 y el codigo ascii*/
+                       printf("[1,%c]\n", inspeccion[0]);
+                       out_bit(0);
+                       out_char(inspeccion[0]);
+                       /* Desplazo */
+                       push_end(memoria, inspeccion[0]);
+                       push_end(inspeccion, c=fgetc(fp));
+               }
+       }
+
+       /* llegue al eof, sigo hasta vaciar inspeccion */
+       while (ic > 0) {
+               int pos, len;
+               /* busco */
+               pos = esta_en_memoria(memoria, inspeccion, &len);
+               if (pos != -1) {
+                       /* La cadena se repite! */
+                       printf("[0,%d,%d]\n", pos, len);
+                       out_bit(0);
+                       out_data(len, pos);
+
+                       /* Tengo que meter caracteres */
+                       for(i=0; i<len; i++) {
+                               push_end(memoria, inspeccion[0]);
+                               push_end(inspeccion, '\0');
+                       }
+                       ic -= len;
+               } else {
+                       /* la cadena no se repite, saco un bit 1 y el codigo ascii*/
+                       printf("[1,%c]\n", inspeccion[0]);
+                       out_bit(0);
+                       out_char(inspeccion[0]);
+                       /* Desplazo */
+                       push_end(memoria, inspeccion[0]);
+                       push_end(inspeccion, '\0');
+                       ic--;
+               }
+       }
+
+       out_end();
+       fclose(fp);
+       printf("\n");
+       return 0;
+}
+
+void push_end(char *s, char c)
+{
+       int i;
+       for(i=0; i<SIZE-1; i++)
+               s[i] = s[i+1];
+       s[SIZE-1] = c;
+}
+
+int esta_en_memoria(char *memoria, char *pal, int *len)
+{
+       int i,j,k;
+       int len_max, pos_max=-1;
+
+       i=j=0;
+       k=0;
+       len_max = -1;
+       while (i<SIZE) {
+               if (memoria[i] == pal[j]) {
+                       k++;
+                       if (k>len_max) {
+                               pos_max = i-k+1;
+                               len_max = k;
+                       }
+                       
+                       j++;
+               } else {
+                       j = 0;
+                       k = 0;
+               }
+               i++;
+       }
+
+       if (len_max >= MIN_LEN) {
+               (*len) = len_max;
+               return pos_max;
+       }
+       return -1;
+}
+
+void out_bit(char b)
+{
+       char c;
+       if (bit_count+1 >= 32) {
+               /* Tengo que hacer lugar! , saco 1 byte*/
+               c = (out_buffer >> (bit_count-8));
+               bit_count -= 8;
+               /* lo grabo en el archivo */
+               fwrite(&c, 1, 1, out);
+       }
+
+       bit_count++;
+       out_buffer <<= 1;
+       out_buffer |= (0x1&b);
+}
+
+void out_char(char c)
+{
+       char cc;
+       if (bit_count+8 >= 32) {
+               /* Tengo que hacer lugar! , saco 1 byte */
+               cc = (out_buffer >> (bit_count-8));
+               bit_count -= 8;
+               /* lo grabo en el archivo */
+               fwrite(&cc, 1, 1, out);
+       }
+
+       bit_count+=8;
+       out_buffer <<= 8;
+       out_buffer |= c;
+}
+
+void out_data(char len, char pos)
+{
+       char cc;
+       char b;
+       while (bit_count+BIT_SIZE*2 >= 32) {
+               /* Tengo que hacer lugar! , saco 1 byte */
+               cc = (out_buffer >> (bit_count-8));
+               bit_count -= 8;
+               /* lo grabo en el archivo */
+               fwrite(&cc, 1, 1, out);
+       }
+
+       b = 0x0;
+       b = ((0x3|pos)<<3) & ((0x3|len));
+       bit_count+=BIT_SIZE*2;
+       out_buffer <<= BIT_SIZE*2;
+       out_buffer |= b;
+}
+
+void out_ini(char *f)
+{
+       out = fopen(f, "wb");
+       bit_count = 0;
+       out_buffer = 0;
+}
+
+void out_end()
+{
+       char cc;
+       /* Saco lo que falte */
+       while (bit_count > 8) {
+               cc = (out_buffer >> (bit_count-8));
+               bit_count -= 8;
+               fwrite(&cc, 1, 1, out);
+       }
+
+       if (bit_count > 0) {
+               cc = (out_buffer >> bit_count);
+               fwrite(&cc, 1, 1, out);
+       }
+       fclose(out);
+}
+