From 69611d873aae9e98aa5be48e3f1ce9730ad8b6de Mon Sep 17 00:00:00 2001 From: Ricardo Markiewicz Date: Wed, 16 Jun 2004 02:56:50 +0000 Subject: [PATCH] Mis 2 colaboraciones. --- otros/blocksorting/Btree.cpp | 389 +++++++++++++++++++++++++++++++++++ otros/blocksorting/Makefile | 74 +++++++ otros/blocksorting/bs.c | 116 +++++++++++ otros/rle/Makefile | 74 +++++++ otros/rle/NO_COMPROBADO | 0 otros/rle/rle.c | 225 ++++++++++++++++++++ 6 files changed, 878 insertions(+) create mode 100644 otros/blocksorting/Btree.cpp create mode 100644 otros/blocksorting/Makefile create mode 100644 otros/blocksorting/bs.c create mode 100644 otros/rle/Makefile create mode 100644 otros/rle/NO_COMPROBADO create mode 100644 otros/rle/rle.c diff --git a/otros/blocksorting/Btree.cpp b/otros/blocksorting/Btree.cpp new file mode 100644 index 0000000..027d84e --- /dev/null +++ b/otros/blocksorting/Btree.cpp @@ -0,0 +1,389 @@ +#include +#include + +#define TAMANO 1000 + +struct stclave { + int valor; + long registro; +}; + +class bnodo { + public: + bnodo(int nClaves); // Constructor + ~bnodo(); // Destructor + + private: + int clavesUsadas; // Claves usadas en el nodo + stclave *clave; // Array de claves del nodo + bnodo **puntero; // Array de punteros a bnodo + bnodo *padre; // Puntero a nodo padre + + friend class btree; +}; + +typedef bnodo *pbnodo; + +bnodo::bnodo(int nClaves) +{ + clavesUsadas = 0; + clave = new stclave[nClaves]; + puntero = new pbnodo[nClaves+1]; + padre = NULL; +} + +bnodo::~bnodo() +{ + delete[] clave; + delete[] puntero; +} + +class btree { + public: + btree(int nClv); + ~btree(); + long Buscar(int clave); + bool Insertar(stclave clave); + void Borrar(int clave); + void Mostrar(); + + private: + stclave *lista; + pbnodo *listapunt; + void Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2); + void BorrarClave(pbnodo nodo, int valor); + void BorrarNodo(pbnodo nodo); + void PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre); + void PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre); + void FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre); + void Ver(pbnodo nodo); + int nClaves, nodosMinimos; + pbnodo Entrada; +}; + +btree::btree(int nClv) : nClaves(nClv) +{ + lista = new stclave[nClaves+1]; + listapunt = new pbnodo[nClaves+2]; + nodosMinimos = nClaves/2; // ((nClaves+1)/2)-1; + Entrada = NULL; +} + +btree::~btree() +{ + delete[] lista; + delete[] listapunt; + // Destruir árbol, algoritmo recursivo: + BorrarNodo(Entrada); +} + +void btree::BorrarNodo(pbnodo nodo) +{ + int i; + + if(!nodo) return; + for(i = 0; i <= nodo->clavesUsadas; i++) BorrarNodo(nodo->puntero[i]); + delete nodo; +} + +void btree::Mostrar() +{ + cout << "arbol" << endl; + Ver(Entrada); + cout << "-----" << endl; +} + +void btree::Ver(pbnodo nodo) +{ + int i; + + if(!nodo) return; + for(i = 0; i < nodo->clavesUsadas-1; i++) cout << nodo->clave[i].valor << "-"; + if(nodo->clavesUsadas) cout << nodo->clave[i].valor << " ["; + if(nodo->padre) cout << (nodo->padre)->clave[0].valor; else cout << "*"; + cout << "]" << endl; + for(i = 0; i <= nodo->clavesUsadas; i++) Ver(nodo->puntero[i]); +} + +long btree::Buscar(int clave) +{ + pbnodo nodo = Entrada; + int i; + + while(nodo) { + i = 0; + while(i < nodo->clavesUsadas && (nodo->clave[i].valor < clave)) i++; + if(nodo->clave[i].valor == clave) return nodo->clave[i].registro; + else nodo = nodo->puntero[i]; + } + return -1L; +} + +bool btree::Insertar(stclave clave) +{ + pbnodo nodo, padre; + int i; + + // Asegurarse de que la clave no está en el árbol + padre = nodo = Entrada; + while(nodo) { + padre = nodo; + i = 0; + while(i < nodo->clavesUsadas && (nodo->clave[i].valor < clave.valor)) i++; + if(nodo->clave[i].valor == clave.valor && i < nodo->clavesUsadas) return false; + else nodo = nodo->puntero[i]; + } + nodo = padre; + Inserta(clave, nodo, NULL, NULL); + return true; +} + +void btree::Inserta(stclave clave, pbnodo nodo, pbnodo hijo1, pbnodo hijo2) +{ + pbnodo padre, nuevo; + int i, j; + bool salir = false; + + // Insertar nueva clave en nodo: + do { + if(!nodo) + { + nodo = new bnodo(nClaves); + nodo->clavesUsadas = 0; + nodo->padre = NULL; + Entrada = nodo; + } + padre = nodo->padre; + if(nodo->clavesUsadas == nClaves) // overflow + { + // Nodo derecho + nuevo = new bnodo(nClaves); + // Construye lista ordenada: + i = 0; + while(nodo->clave[i].valor < clave.valor && i < nClaves) { + lista[i] = nodo->clave[i]; + listapunt[i] = nodo->puntero[i]; + i++; + } + lista[i] = clave; + listapunt[i] = hijo1; + listapunt[i+1] = hijo2; + while(i < nClaves) { + lista[i+1] = nodo->clave[i]; + listapunt[i+2] = nodo->puntero[i+1]; + i++; + } + // Dividir nodos: + // Nodo izquierdo: + nodo->clavesUsadas = nClaves/2; + for(j = 0; j < nodo->clavesUsadas; j++) { + nodo->clave[j] = lista[j]; + nodo->puntero[j] = listapunt[j]; + } + nodo->puntero[nodo->clavesUsadas] = listapunt[nodo->clavesUsadas]; + + // Nodo derecho: + nuevo->clavesUsadas = nClaves - nodo->clavesUsadas; + for(j = 0; j < nuevo->clavesUsadas; j++) { + nuevo->clave[j] = lista[j+(nClaves/2)+1]; + nuevo->puntero[j] = listapunt[j+(nClaves/2)+1]; + } + nuevo->puntero[nuevo->clavesUsadas] = listapunt[nClaves+1]; + + for(j = 0; j <= nodo->clavesUsadas; j++) + if(nodo->puntero[j]) (nodo->puntero[j])->padre = nodo; + for(j = 0; j <= nuevo->clavesUsadas; j++) + if(nuevo->puntero[j]) (nuevo->puntero[j])->padre = nuevo; + + clave = lista[nClaves/2]; + hijo1 = nodo; + hijo2 = nuevo; + nodo = padre; + } + else + { + // Inserta nueva clave en su lugar: + i = 0; + if(nodo->clavesUsadas > 0) { + while(nodo->clave[i].valor < clave.valor && i < nodo->clavesUsadas) i++; + for(j = nodo->clavesUsadas; j > i; j--) + nodo->clave[j] = nodo->clave[j-1]; + for(j = nodo->clavesUsadas+1; j > i; j--) + nodo->puntero[j] = nodo->puntero[j-1]; + } + nodo->clavesUsadas++; + nodo->clave[i] = clave; + nodo->puntero[i] = hijo1; + nodo->puntero[i+1] = hijo2; + if(hijo1) hijo1->padre = nodo; + if(hijo2) hijo2->padre = nodo; + salir = true; + } + } while(!salir); +} + +void btree::Borrar(int valor) +{ + pbnodo nodo; + bool encontrado = false; + int i; + + // Busca el nodo que contiene la clave, si existe + nodo = Entrada; + while(nodo && !encontrado) { + i = 0; + while(i < nodo->clavesUsadas && (nodo->clave[i].valor < valor)) i++; + if(nodo->clave[i].valor == valor && i < nodo->clavesUsadas) encontrado = true; + else nodo = nodo->puntero[i]; + } + if(encontrado) BorrarClave(nodo, valor); +} + +void btree::BorrarClave(pbnodo nodo, int valor) +{ + pbnodo actual, derecha, izquierda, padre; + int posClavePadre, pos, i; + + // Buscar posición dentro de lista de claves: + pos = 0; + while(nodo->clave[pos].valor < valor) pos++; + + // ¿Está la clave en un nodo hoja? + if(nodo->puntero[0]) { // No, se trata de un nodo intermedio + // Buscar actual del valor siguiente: + actual = nodo->puntero[pos+1]; + while(actual->puntero[0]) actual = actual->puntero[0]; + // Intercambiar con el valor siguiente: + nodo->clave[pos] = actual->clave[0]; + // La posición de la clave a borrar en ahora la 0: + pos = 0; + } else actual = nodo; + + // Borrar clave + for(i = pos; i < actual->clavesUsadas; i++) + actual->clave[i] = actual->clave[i+1]; + actual->clavesUsadas--; + + if(actual == Entrada && actual->clavesUsadas == 0) { + delete actual; + Entrada = NULL; + return; + } + + // ¿Es el número de claves mayor que el mínimo para el nodo? + if(actual == Entrada || actual->clavesUsadas >= nodosMinimos) return; + + do { + // El número de claves es menor que el mínimo: + // Buscar nodos a derecha e izquierda: + padre = actual->padre; + for(posClavePadre = 0; + padre->puntero[posClavePadre] != actual; + posClavePadre++); + if(posClavePadre > 0) + izquierda = padre->puntero[posClavePadre-1]; + else izquierda = NULL; + if(posClavePadre < padre->clavesUsadas) + derecha = padre->puntero[posClavePadre+1]; + else derecha = NULL; + + // Intentar pasar una clave de un nodo cercano: + if(derecha && derecha->clavesUsadas > nodosMinimos) + PasarClaveDerecha(derecha, padre, actual, posClavePadre); + else if(izquierda && izquierda->clavesUsadas > nodosMinimos) + PasarClaveIzquierda(izquierda, padre, actual, posClavePadre-1); + // Si no fue posible, fundir con un nodo cercano y una clave de padre: + else if(derecha) // Usar nodo derecho + FundirNodo(actual, padre, derecha, posClavePadre); + else // Usar el nodo izquierdo + FundirNodo(izquierda, padre, actual, posClavePadre-1); + // Vuelta a empezar: + actual = padre; + } while(actual && actual != Entrada && actual->clavesUsadas < nodosMinimos); +} + +void btree::PasarClaveDerecha(pbnodo derecha, pbnodo padre, pbnodo nodo, int posClavePadre) +{ + int i; + + nodo->clave[nodo->clavesUsadas] = padre->clave[posClavePadre]; + nodo->clavesUsadas++; + padre->clave[posClavePadre] = derecha->clave[0]; + nodo->puntero[nodo->clavesUsadas] = derecha->puntero[0]; + if(derecha->puntero[0]) derecha->puntero[0]->padre = nodo; + for(i = 0; i < derecha->clavesUsadas; i++) derecha->clave[i] = derecha->clave[i+1]; + for(i = 0; i <= derecha->clavesUsadas; i++) derecha->puntero[i] = derecha->puntero[i+1]; + derecha->clavesUsadas--; +} + +void btree::PasarClaveIzquierda(pbnodo izquierda, pbnodo padre, pbnodo nodo, int posClavePadre) +{ + int i; + + for(i = nodo->clavesUsadas; i > 0; i--) nodo->clave[i] = nodo->clave[i-1]; + for(i = nodo->clavesUsadas+1; i > 0; i--) nodo->puntero[i] = nodo->puntero[i-1]; + nodo->clavesUsadas++; + nodo->clave[0] = padre->clave[posClavePadre]; + padre->clave[posClavePadre] = izquierda->clave[izquierda->clavesUsadas-1]; + nodo->puntero[0] = izquierda->puntero[izquierda->clavesUsadas]; + if(nodo->puntero[0]) nodo->puntero[0]->padre = nodo; + izquierda->clavesUsadas--; +} + +void btree::FundirNodo(pbnodo izquierda, pbnodo &padre, pbnodo derecha, int posClavePadre) +{ + int i; + + izquierda->clave[izquierda->clavesUsadas] = padre->clave[posClavePadre]; + padre->clavesUsadas--; + for(i = posClavePadre; i < padre->clavesUsadas; i++) { + padre->clave[i] = padre->clave[i+1]; + padre->puntero[i+1] = padre->puntero[i+2]; + } + izquierda->clavesUsadas++; + for(i = 0; i < derecha->clavesUsadas; i++) + izquierda->clave[izquierda->clavesUsadas+i] = derecha->clave[i]; + for(i = 0; i <= derecha->clavesUsadas; i++) { + izquierda->puntero[izquierda->clavesUsadas+i] = derecha->puntero[i]; + if(derecha->puntero[i]) derecha->puntero[i]->padre = izquierda; + } + izquierda->clavesUsadas += derecha->clavesUsadas; + if(padre == Entrada && padre->clavesUsadas == 0) { // Cambio de entrada + Entrada = izquierda; + Entrada->padre = NULL; + delete padre; + padre = NULL; + } + delete derecha; +} + +int main() +{ + int matriz[TAMANO]; + btree arbol(500); + stclave clave; + int i; + +// 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: " << + arbol.Buscar(matriz[23]) << endl; + + for(i = 0; i < TAMANO; i++) { + cout << "Borrar: [" << i << "]: " << matriz[i] << endl; + arbol.Borrar(matriz[i]); +// arbol.Mostrar(); + } + arbol.Mostrar(); + return 0; +} diff --git a/otros/blocksorting/Makefile b/otros/blocksorting/Makefile new file mode 100644 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 index 0000000..e5dd16f --- /dev/null +++ b/otros/blocksorting/bs.c @@ -0,0 +1,116 @@ + +/* Block Sorting Optimizado en memoria! */ + +#include +#include +#include + +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 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", 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 +#include +#include + +#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 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; ilen_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); +} + -- 2.43.0