AVL (Adel’son-Vel’skii Landis) – Árboles binarios Balanceados

Los árboles binarios tienen la utilidad de ordenar la información, separando el conjunto en dos posibilidades, izquierda y derecha, por lo que reducimos el conjunto de búsqueda a la mitad en cada paso. Esto nos lleva a que en un árbol balanceado (si tiene las ramas izquierda y derecha del mismo tamaño +1 o -1) tenemos una altura de Log(n), lo cual hace que las búsquedas sean “rápidas”. El problema que tienen los árboles comunes es que pueden degenerar rapidamente en una lista, por ejemplo si insertamos el elemento 1 como raíz, y luego insertamos los números 2, 3, 4, 5… Tendremos inserciones siempre a la derecha, lo que nos lleva a tener una estructura de lista perdiendo la utilidad de dividir a la mitad en cada paso. Para solucionar esto utilizaremos los AVL, o árboles binarios balanceados, que nos permiten después de cada inserción rotar los nodos de forma de que quede ordenado.

Los AVL utilizan el factor de balanceo para decidir si es necesario rotar una rama luego de insertar. Este FB (factor de balanceo) nos dice la diferencia de alturas entre el subárbol izquierdo y el derecho, por lo que restando las alturas de los mismos obtenemos este valor.

FB = Altura Subarbol Izquierdo – Altura Subarbol Derecho

En el primer ejemplo del caso anterior tenemos que la primer rama izquierda tiene un desbalanceo, ya que la altura de su subrama izquierda es 2, y la de la derecha es 0, lo que nos da: FB = 2. Tenemos desbalance. En el segundo caso el FB no supera el valor 1, por lo que no hay necesidad de rotar.

Las rotaciones se dividen en dos casos, simples o dobles. Las simples se conocen como LL si son de la rama izquierda, y RR si son de la rama derecha. Las rotaciones dobles son LR o RL, ya que son combinadas y más complejas como sugiere su nombre. Vemos primero las rotaciones simples.

En el caso simple LL, tomemos un nodo 1 que quedará con FB = 2, insertamos un nodo en el subárbol izquierdo de su hijo izquierdo, con lo que tenemos una inserción en la izquierda-izquierda (por eso Left Left). Para balancear el árbol deberemos tomar el hijo izquierdo de 1 (llamémoslo 2), y ponerlo como padre de 1, el hijo derecho de 1 queda en su lugar, el hijo izquierdo de 2 queda en su lugar y el hijo de derecho de 2 debe ir como hijo izquierdo de 1, ya que en su lugar tendremos a 1. Veamos un dibujo:

Lo que hacemos es mover el subárbol que queda con un largo excesivo hacia arriba, sacando al padre para hacer lugar, teniendo cuidado eso si de mantener la relación de mayor menor, lo cual hacemos dejando los subárboles izquierdos de 2 y derecho de 1 en sus lugares (ya que son menores que todos los demas, y mayores respectivamente), y moviendo de lugar el subárbol derecho de 2 hacia el izquierdo de 1. Esto lo podemos hacer ya que este subárbol contiene elementos mayores que los de 2, pero menores que 1.

En el caso de la rotación simple RR sucede lo mismo que acabamos de ver, solo que en el caso de insertar a la derecha del hijo derecho:

Hemos visto los dos casos simples, donde insertamos en la rama menor que todos o mayor que todos. Veremos ahora que sucede cuando insertamos en el hijo derecho del subárbol izquierdo, o en el izquierdo del derecho, es decir cruzado.

En este caso lo que haremos será aplicar dos rotaciones simples, con lo cual haremos que el nodo insertado “suba” acortando la altura del árbol. Noten que el nodo que tiene FB = 2 es el nodo 1, y no el nodo 2 que es donde insertamos (en su subárbol derecho). Por lo cual deberemos modificar la altura de sus hijos para reducir el FB a 1.

El proceso que seguiremos será el siguiente, tomamos el nodo en la rama donde se generó el desbalance, en este caso el 2, como la inserción es en el fijo derecho de 2, tomamos este nodo (el 3), y lo guardamos como la nueva raiz. Guardamos los dos hijos del 3 (ya que en realidad el árbol puede ser más amplio, y haber nodos hacia “abajo”) y ponemos como su hijo izquierdo a 2, y su hijo derecho a 1. Así sabemos que el orden se mantiene, 3, estaba a la derecha de 2, por lo que es mayor, y a la izquierda de 1, por lo que es menor. Colocado 3 en el lugar de 1, tomamos los dos posibles hijos de 3 que guardamos y los colocamos respectivamente como hijo derecho de 2 al hijo izquierdo, y como hijo izquierdo de 1 al derecho de 3. Otra vez manteniendo el orden.

Veamos un ejemplo gráfico:

En resumen la idea es, cuando detectamos que un nodo tiene FB = 2 (recuerden, en valor absoluto), entonces de acuerdo a sea positivo o negativo tomamos la rama izquierda o la derecha, subimos el nodo correspondiente y reasignamos con cuidado los hijos para no perder el orden. Las operaciones LR y RL, como las LL y RR son simétricas, por lo que el código será idéntico cambiando el hijo seleccionado. Como mencionabamos antes, las operaciones complejas se pueden reducir a dos operaciones simples, por ejemplo la LR podemos reducrila a realziar primero una RR en el hijo izquierdo y luego una LL en la raíz.

Pasemos a los ejemplos de código en C para ver como implementar estas rotaciones.

Lo primero que tenemos que hacer, es hacer una modificación al tipo de dato de árbol binario, ya que queremos tener en cuenta el FB en cada nodo, para detectar un desbalance. Agregaremos un campo int con la altura del nodo actual, lo cual nos permite saber sin tener que sumar recursivamente cada vez la altura de un nodo con sus hijos:

struct AVLNode {
int dato;
AVLNode izq;
AVLNode der;
int altura;
};

El siguiente paso es agregar una función que nos permite conocer la altura de un nodo actual, de forma que nuestro TAD quede bien estructurado, y en caso de ser necesario poder actualizar la misma calculando el FB:

int Altura (AVLNode* t) {
if(t == NULL)
return -1;
else
return t->altura;
}

AlturaCalcular (AVLNode* t) {
if(t != NULL)
t->altura = max (altura ((t)->izq), altura ((t)->der)) + 1;
}

Veamos el caso de una rotación simple RR:

void RotarAVLDer (AVLNode* &t) {
nodoAVL *taux;

taux = t->right;
t->right = taux->left;
taux->left = t;

actualizarAlturaAVL(t);
actualizarAlturaAVL(taux);

t = taux;
}

Como ven, pasamos la raíz por referencia, de forma que podemos modificar el puntero y colocar su hijo derecho en su lugar. Pero primero tenemos cuidado de copiar los datos necesarios para no perder las referencias, y de actualizar las alturas correspondientes. Ahora veamos el caso de la rotación doble, para la cual usaremos el hecho de que podemos descomponer la misma en dos rotraciones simples.

void RotarAVLDerDoble (AVLNode* t) {
RotarAVLIzq(&(t)->der);
RotarAVLDer(t);
}

Primero realizamos una LL y luego una RR, RotarAVLIzq es la rotación simple en el hijo izquierdo, análoga a RotarAVLDer que acabamos de ver pero sobre el hijo izquierdo de la raíz.

Con esto tenemos las operaciones básicas para balancear, crearemos una funcion que nos permita balancear cuando lo necesitemos, y luego veremos la de inserción que será simple ya que tenemos las tareas divididas en nuestro TAD AVL.

void BalancearAVL (AVLNode* t) {
if(t != NULL) {
if (Altura(t->izq) – Altura(t–>der) == 2) {  /* FB indica izquierda */
if (altura (t->izq->izq) >= altura (t->izq->der))
/* simple hacia la izquierda */
RotarAVLIzq(t);
else
/* doble hacia la izquierda */
RotarAVLIzqDoble(t);
}

else if (Altura(t->der) – Altura(t->izq) == 2) {  /* FB indica derecha */
if (Altura(t->der->der) >= Altura(t->der->izq))
/* simple derecha */
RotarAVLDer (t);
else
/* doble derecha */
RotarAVLDerDoble (t);
}
}
}

Y por último la inserción:

void InsertarAVL (AVLNode* t, int x) {
if (t == NULL) {
t = ArbolCrearAVL();
ArbolInsertar(t,x);
} else {
if (x < ArbolRaiz(t))
InsertarAVL(&t->izq, x);
else
InsertarAVL(&t->der, x);

BalancearAVL(t);
AlturaCalcular (t);
}
}

Al insertar buscamos la posición del elemento como lo hacemos normalmente en un árbol binario, buscando en derecho o izquierda de acuerdo a la comparación. Una vez que encontramos su posición creamos un nuevo nodo y lo insertamos, al regresar de la recursión debemos balancear los nodos ya que podríamos haber creado un desbalance, actualizando la altura según corresponda.

Con esto completamos nuestro TAD AVL, como ya dijimos tenemos la capacidad de ordenar el árbol y asegurarnos que el orden de búsqueda de un elemento no supere nunca Log(n). Un buen ejercicio de multiestructuras es pensar en la combinación de un AVL con una lista, de forma que podamos buscar determinado valor dentro del AVL, y luego a partir de ese valor podamos recorrer una cantidad de valores ordenados sin tener que buscar cada uno.

Supongamos que tenemos tiempos ordenados en un AVL, y queremos obtener los 10 tiempos siguiente a partir de cierto momento. Entonces lo que podemos hacer es tener un AVL “espejado” en una lista, con lo cual podemos buscar el tiempo deseado en el AVL (o el más cercano a él), y luego de encontrar el mismo saltamos a la lista (mantendremos un puntero a la posición correspondiente en cada nodo del AVL) y recorremos la lista obteniendo los 10 elementos. Así logramos un buen grado de eficiencia, teniendo únicamente que buscar un tiempo en el AVL con un orden Log(n) y luego recorriendo la lista que ya sabemos esta ordenada ya que mantenemos el orden al hacer cada inserción.

En la próxima entrada veremos las tablas de dispersión o Hash, los cuales nos permite hacer búsquedas en un tiempo constante.

Áboles binarios de búsqueda

La estructura de datos que veremos es la de árboles, esta estructura nos permite organizar información de forma que tenemos una relación de padres e hijos, ordenando por ejemplo por un valor.En el primer caso veremos el árbol binario de búsqueda, donde cada nodo tiene dos ramas y un campo de valor, a la izquierda conectaremos otros nodos de menor valor y a la derecha otros nodos de mayor valor.

Veamos una definición de árbol binario:

typedef struct arbol {
arbol * izq;
arbol * der;
int valor;
};

Definiremos como NULL un árbol vacío, para cada nodo del árbol tendremos una rama izquierda y una derecha, que son punteros a otros nodos, y un campo para el valor. En este ejemplo usaremos un int para el valor para simplificar, pero podríamos tener un puntero a otra estructura más compleja (y tendríamos que tener forma de poder comparar estos elementos más complejos de forma que podamos ordenar el árbol).

Siguiente la línea de definir un TAD, vamos a crear operaciones básicas sobre esta definición para realizar las tareas esenciales sobre un árbol, como crear, insertar, recorrer y borrar. Por la naturaleza de los árboles tenemos una definición recurrente, y el TAD también trabajará de esta forma, con funciones recursivas sobre la estructura de datos.

Aquí tenemos un TAD para nuestro árbol binario:

arbol * ArbolCrear();
// Crear un árbol vacío.

bool ArbolEsVacio(arbol * t);
// Devuelve true si el árbol ess vacío.

void ArbolInsertar (arbol *& t, int n);
// Inserta el elemento n en el árbol.

int ArbolRaiz(arbol * t);
// Devuelve la raíz del árbol.

arbol * ArbolIzq(arbol * t);
// Devuelve la rama izquierda del árbol.

arbol * ArbolDer(arbol * t);
// Devuelve la rama derecha del árbol.

Y su implementación:

arbol * ArbolCrearVacio() {
return NULL;
}

bool ArbolEsVacio(arbol * t) {
return t == NULL;
}

void ArbolInsertar (arbol *& t, int n) {
if (ArbolEsVacio(t)) {
arbol * nodo = new arbol;
nodo->valor = n;
nodo->izq = ArbolCrearVacio();
nodo->der= ArbolCrearVacio();
t = nodo;
} else {
if (arbol->nodo > n) {
ArbolInsertar (t->izq, n);
} else {
ArbolInsertar (t->der, n);
}
}
}

int ArbolRaiz(arbol * t) {
return t->valor;
}

arbol * ArbolIzq(arbol * t) {
return t->izq;
}

arbol * ArbolDer(arbol * t) {
return t->der;
}

Tengan en cuenta algunos detalles, como por ejemplo al insertar pasamos por referencia el puntero al árbol de forma que podemos modificarlo. Otro detalle es que por ejemplo las operaciones que nos dan las ramas izq y der deben ser utilizadas con precaución, ya que no chequean que el árbol sea vacío. Por lo tanto si llamamos a una de estas operaciones con un árbol vacío tendremos un error grave en el programa. Tenemos que colocar una precondición en el TAD, aclarando que esa operación sólo puede ser utilizada en el caso de que hayamos chequeado que el árbol que le pasamos no es vacio.

arbol * ArbolIzq(arbol * t);
// Devuelve la rama izquierda del árbol.
// Precondición: !ArbolEsVacio(t)

arbol * ArbolDer(arbol * t);
// Devuelve la rama derecha del árbol.
// Precondición: !ArbolEsVacio(t)

Ahora que tenemos el árbol binario podemos organizar información, por ejemplo si tenemos una gran cantidad de numeros y queremos saber si determinado número pertenece al conjunto podemos hacerlo recorriendo el árbol en forma recursiva, chequeando con el nodo actual y recorriendo las ramas. Por ejemplo podríamos hacer algo asi:

bool ArbolPertenece (arbol * t, int n) {
if (ArbolEsVacio(t)){
return false;
} else {
if (t->valor == n) {
return true;
} else if (t->valor > n) {
return ArbolPertenece(t->izq, n);
} else {
return ArbolPertenece(t->der, n);
}
}
}

Si el nodo en que estamos es vacío, entonces no encontramos el valor buscado, si no es vacío comparamos el valor del nodo actual, si es igual lo encontramos y devolvemos true, si no es igual puede ser mayor o menor por lo que llamamos en forma recursiva a la función con una de las dos ramas para seguir buscando.

Podemos ver que la eficiencia de esta estructura de datos es mucho mayor en las búsquedas, ya que podemos encontrar un elemento sin tener que recorrer todo el conjunto, como nos sucedía en el caso de las listas. Lo que hacemos al buscar en el árbol binario de búsqueda es ir dividiendo el conjunto en dos partes, por lo que cada vez reducimos a la mitad la cantidad de elementos, lo que nos da un orden de búsqueda igual a lograitmo de n, donde n es la cantidad de elementos del conjunto (vermos esto en más detalle más adelante, al finalizar las estructuras y realizar un análisis de órdenes de las mismas).

Por su parte la lista nos obliga a recorrer todo el conjunto de elementos, por lo que podemos tener que recorrer toda la lista para encontrar. Entonces tenemos que para buscar tenemos orden n para la lista, y orden ln(n) para el árbol binario.

Pero no todo es color de rosas en los árboles binarios, ya que tenemos dos complicaciones. La primera es que para insertar un elemento tenemos que recorrer, comparando con los nodos hasta llegar al lugar adecuado del valor dentro del árbol, lo que nos llevar a realizar ln(n) operaciones antes de poder insertar, mientras que con la lista insertamos al comienzo de la misma y no tenemos que recorrer nada, lo que nos da un orden 1 (es decir, una sola operación para insertar sin importar la cantidad de elementos que haya en el conjunto).

El otro problema que tenemos es que no realizamos balanceos del árbol al insertar, a medida que vamos insertando vamos dejando los nodos tal quedan de las comparaciones, pero esto puede provocar que nuestro árbol se transforme en una lista (o en algo parecido a una lista) si se dan ciertas condiciones. Por ejemplo, supongamos que queremos insertar los siguientes números: 10, 8, 6, 4, 2. Entonces siempre estaremos insertando en la rama izquierda, por lo que tendremos en realidad una lista de elementos, no tendremos una distribución pareja de elementos lo cual es necesario para que nuestra búsqueda tenga orden ln(n) (recuerden que este orden se da por ir dividiendo el conjunto en 2 cada vez, reduciendo el tamaño).

Para solucionar este problema veremos en la siguiente entrada, la estructura de datos conocida como AVL, esta estructura sigue la línea del árbol binario que acabamos de ver pero haciendo hincapie en mantener el árbol balanceado en todo momento, es decir que nunca tendremos el problema de que nuestro árbol degenere en una lista y perdamos la posibilidad de buscar en forma rápida dentro del conjunto. Esto lo lograremos rotando las ramas luego de insertar si las mismas quedan desbalanceadas.

Estructuras de datos y algoritmos en C/C++: Listas y Colas

Cambiando un poco el objetivo del sitio vamos a investigar un poco sobre las estructuras de datos y algoritmos en C/C++. Para esto vamos a comenzar trabajando con estructuras de datos simples como listas y colas, para luego pasar a estructuras como árboles, árboles binarios de búsqueda, AVLs, Hash y algoritmos complejos.

Para poder seguir los ejemplos les recomiendo utilizar Cygwin si usan Windows para tener todas las herramientas de compilado (g++, archivo make, librerias, etc). Si tienen Linux simplemente instalen los paquetes devel.

Trabajaremos construyendo los tipos abstractos de datos (TADs) que nos permitirán abstraernos de la estructura de punteros y trabajar con operaciones que se encargan de hacer el trabajo sucio =). Esto nos libera de estar revisando detalles de la estructura para poder concentrarnos en como resolver problemas.

Comenzaremos trabajando con las dos estructuras más simples, listas y colas. En las dos estructuras de datos encadenamos elementos en forma simple, la diferencia está en la forma en que una vez que ingresamos los mismos, luego podemos sacarlos. En la lista insertamos en la cabeza y sacamos elementos desde la misma cabeza, este orden es conocido como último en entrar, primero en salir (LIFO siglas en inglés). En el caso de la cola utilizamos el otro orden, primero en entrar primero en salir (FIFO siglas en inglés).

Veamos la definición del tipo de datos para la lista:

typedef struct lista {
int valor;
lista * sig;
};

Con esta definición podemos ir enlazando los nodos de la lista, poniendo en el último el valor NULL en el puntero a sig indicando que termina la lista.

El siguiente paso es definir la lista de operaciones con las cuales vamos a poder trabajar sobre este tipo de datos. Definiremos las siguientes funciones:

lista * ListaCrearVacia();
// Crear una lista de nodos vacia.

bool ListaEsVacia(lista * l);
// Devuelve true si la lista es vacia y false en caso contrario.

void ListaAgregar (lista *& l, int n);
// Agrega el elemento n al comienzo de la lista.

int ListaPrimero(lista * l);
// Devuelve el primer elemento de la lista.

lista * ListaResto(lista * l);
// Devuelve un alias al resto de la lista.

void ListaDestruir(lista * l);
// Libera la memoria asociada a la lista.

Dadas estas operaciones podremos trabajar sobre el tipo de datos con comodidad, creando, insertando, recorriendo y eliminando la estructura sin necesidad de preocuparnos por los punteros que la componen. Por ejemplo si queremos recorrer una lista que tiene elementos podríamos hacer lo siguiente (debemos verificar que no sea vacia primero):

while (!ListaEsVacia(listaDatos)) {
int valor = ListaPrimero(listaDatos);
printf(“\nDato: %d”,valor);
listaDatos= ListaResto(listaDatos);
}

Noten que deberíamos guardar una copia del puntero inicial de la lista para poder volver a recorrerla o bien poder eliminar la memoria de la misma. Si no tenemos este puntero habremos perdido el comienzo de la lista =P.

Entrando un poco en la construcción del TAD, en el caso de la lista tendremos que insertar el elemento al principio de la misma, mientras que en la cola insertamos al final. Esto nos lleva a ver en el caso de la lista si insertamos al comienzo podremos hacerlo rápidamente aunque la lista sea muy grande. Simplemente modificaremos la cabeza de la lista y pondremos el nuevo dato como comienzo. Veamos un ejemplo:

void ListaAgregar (lista *& l, int n) {
lista* nuevoNodo = new lista;
nuevoNodo->valor = n;
nuevoNodo->sig = l;
l = nuevoNodo;
return;
}

Lo que hacemos es crear el nuevo nodo, asignar el valor de entero y luego encadenamos la lista “vieja” como siguiente elemento del nuevo nodo. Esto nos deja la lista l con el nuevo nodo al comienzo.

La definición de las otras funciones es simple, veamos algunas:

lista * ListaCrearVacia() {
lista* l = NULL;
return l;
}

bool ListaEsVacia(lista * l) {
return l == NULL;
}

int ListaPrimero(lista * l) {
return l->valor;
}

lista * ListaResto(lista * l) {
return l->sig;
}

Pero pensemos por un momento en el caso de la cola, para insertar al final tendremos que ir hasta el final de la misma, por lo cual en caso de que tengamos una gran cantidad de datos tendremos que recorrer muchos nodos. Esto no es bueno, como veremos más adelante buscaremos que nuestras estructuras de datos sean eficientes y sean “más lentas” cuantos más datos tengamos en las mismas. Si nuestra estructura se vuelve más lenta a medida que tenemos más datos sufriremos consecuencias a largo plazo, nuestro programa será cada vez más lento.

Para solucionar este problema lo que haremos será tener un puntero al comienzo y otro al final de la cola, lo cual nos permitirá insertar al final de la misma y acceder al comienzo en forma directa, sin tener que recorrer la misma.

typedef struct cola {
lista * inicio;
lista * fin;
};

Noten que utilizaremos la lista, pero con un nodo especial que nos permita acceder al comienzo y al fin de la misma para remover e insertar respectivamente. Las funciones del TAD nos darán las operaciones que podremos utilizar para trabajar sobre este tipo de datos sin preocuparnos de punteros y demás:

cola * ColaCrearVacia();
// Crea una cola vacia.

bool ColaEsVacia(cola * c);
// Devuelve true si la cola es vacia y false en caso contrario.

void ColaEncolar (cola * c, int n);
// Agrega el elemento n a la cola.

int ColaPrimero(cola * c);
// Devuelve el primer elemento de la cola.

void ColaDesencolar(cola * c);
// Elimina el primer elemento de la cola.

void ColaDestruir(cola * c);
// Libera la memoria asociada a la cola.

Para estas operaciones utilizaremos prácticamente el mismo código que para la lista, únicamente teniendo cuidado de utilizar los “accesos directos” según el caso que corresponda, para evitar tener que recorrer toda la cola.

En la próxima entrada veremos árboles binarios de búsqueda, los cuales permiten ordenar la información para encontrar en forma más rapida la misma =)

Paginado de resultados con PHP

Ordenar los resultados en los listados suele ser un problema repetido y aburrido de solucionar. Tenemos que cortar la consulta de resultados, luego contar las páginas segun la cantidad de resultados por página, poner links de siguiente, anterior, etc, etc, etc…

En esta entrada les dejo un script para olvidarse de una vez de este tema, un script que se encarga de hacer todo el paginado por su cuenta, simplemente definimos algunos valores y problema solucionado.

Primero que nada el script: “Paginator”. El sitio del proyecto lo encuentran en:

http://jpinedo.webcindario.com/scripts/paginator/

Descargan los dos archivos del script y lo primero que tenemos que hacer es configurar el script para que se conecte a la base de datos. Esto lo hacemos en el archivo: paginatorconf.inc.php. Verán que en este archivo definen servidor, usuario, contraseña y DB.

Hecho esto lo único que tenemos que hacer es preparar la consulta SQL tal como la usariamos normalmente, sin LIMIT ni nada. Veamos un ejemplo:

$_pagi_sql = “SELECT * FROM tabla ORDER BY nombre”;

$_pagi_cuantos = 50;
$_pagi_nav_num_enlaces = 5;

require(“paginatorconf.inc.php”);
require(“paginator.inc.php”);

Guardamos en una variable de nombre $_pagi_sql (este nombre es el que usa el script, sirve para no confundirse) la consulta, luego definimos el formato del paginado, es decir la cantidad de resultados por página y el numero de enlaces hacia las páginas de resultados, y llamamos a los dos archivos del paginator, primero al de configuración y luego a paginator.inc.php.

Luego de haber incluído el segundo archivo tendremos en la variable $_pagi_result el resultado de la consulta. Además tenemos otras variables que guardan todos los datos que necesitamos, como cantidad de resutlados, número de enlaces y demás, veamos como podemos desplegar la información:

<table>
<tr>
<th width=”3%”>N&ordm;</th>
<th>Nombre</th>
</tr>

<?
$i = $_pagi_desde;

while($row = mysql_fetch_array($_pagi_result)){
?>
<tr>
<td><?=$i?>.</td>
<td> <?=$row['nombre']?></td>
</tr>

<?
$i++;
}
?>

<tfoot>
<tr><th colspan=2 width=100%>
Resultados: Desde <?=$_pagi_desde?> hasta <?=$_pagi_hasta?> (Total: <?=$_pagi_totalReg?>)
<br />Página: <?=$_pagi_navegacion?>
</th></tr>
</tfoot>

</table>

Recorremos los resultados obtenidos, y con la variable $_pagi_navegacion desplegamos la navegación con los links de siguiente, anterior y links directo a las páginas. así de simple .

Para los casos en que utilizan variables GET para su sitio, no hay problema, ya que las variables GET que utiliza el navegador no borran las de ustedes, el script se encarga de propagar o “poner en su sitio” las variables GET que tenga la URL para no romper la misma .

Envío de mails desde PHP con smtp, autenticacion, ssl y otros.

Enviar mails con PHP suele ser sencillo, utilizando la funcion mail() podemos hacerlo aunque no tenemos prácticamente fleixbilidad ni opciones. Casos típicos son cuando queremos enviar mails por smtp, utilizando una cuenta en particular, o nuestro servidor no tiene configurado un servidor local para PHP, o necesitamos una conexion SSL, etc.

Para estos casos podemos usar la clase phpmailer, que nos da todas estas opciones y más. La clase la pueden descargar de: phpmailer.codeworxtech.com

Lo único que necesitamos hacer luego de tener la clase descargada y colocada nuestro sitio, es incluir el archivo de la misma e instancia la clase:

require(“phpmailer/class.phpmailer.php”);
$mail = new PHPMailer();

Hecho esto pasamos a definir mail de origen, destino, nombre, etc.:

$mail->From     = $mailfrom; // Mail de origen
$mail->FromName = $name; // Nombre del que envia
$mail->AddAddress($para); // Mail destino, podemos agregar muchas direcciones
$mail->AddReplyTo($mailfrom); // Mail de respuesta

Luego definimos el contenido del mail:

$mail->WordWrap = 50; // Largo de las lineas
$mail->IsHTML(true); // Podemos incluir tags html
$mail->Subject  =  “Consulta formulario Web: $name”;
$mail->Body     =  “Nombre: $name \n<br />”.
“Email: $mailfrom \n<br />”.
“Tel: $tel \n<br />”.
“Mensaje: $info \n<br />”;
$mail->AltBody  =  strip_tags($mail->Body); // Este es el contenido alternativo sin html

Podemos adjuntar archivos simplemente agregando los mismos de la siguiente forma:

$mail->AddAttachment(“nombredearchivo.txt”); // Ingresamos la ruta del archivo

Y ahora viene la parte divertida (no solo me pica el…errr), definimos el servidor que enviara el mail, podemos definir tipo de servidor, autenticacion, usuario, contraseña, etc. Vemos ejemplo de las posibilidades que tenemos.

Si vamos a enviar mail desde el servidor local sin configuración especial podemos usar:

$mail->Host     = ‘localhost’;

Si necesitamos utilizar una casilla de correo smtp, con user y pass:

$mail->IsSMTP(); // vamos a conectarnos a un servidor SMTP
$mail->Host = “mail.servidor.com”; // direccion del servidor
$mail->SMTPAuth = true; // usaremos autenticacion
$mail->Username = “info@servidor.com”; // usuario
$mail->Password = “pass”; // contraseña

Si necesitamos una conexion con SSL, por ejemplo para enviar un mail desde PHP con gmail:

$mail->Mailer = “smtp”;
$mail->Host = “ssl://smtp.gmail.com”;
$mail->Port = 465;
$mail->SMTPAuth = true;
$mail->Username = “burmauy@gmail.com”; // SMTP username
$mail->Password = “burmaUY123456″; // SMTP password

Como ven esta clase es muy flexible y nos olvidamos de tener que manejar nosotros mismos conexiones complejas o con cabeceras especiales. Podemos simplificarnos mucho la vida utilizando phpmailer para enviar mails.

Ya para enviar el correo, simplemente utilizamos la siguiente linea:

$mail->Send();

Podemos poner esa llinea dentro de un if para saber si quedo todo bien configurado y se pudo enviar el email, de la siguiente forma:

if ($mail->Send())
echo “Enviado”;
else
echo “Error en el envio de mail”;

URLs limpias en los sitios con Apache y archivos .htaccess

En cualquier sitio que requiera programación, ya sean noticias, productos, categorías, etc., necesitamos agregar URLs que tienen parámetros. Estos parámetros son los que indican a nuestro código la información a cargar, pero los buscadores no ven con buenos ojos estas consultas con parámetros. Por ejemplo:

http://www.sitio.com/noticias.php?date=20080201

Esta url además de no ser amigable para los buacadores no lo es para los usuarios. Si alguien busca en el historial y ve esa dirección no va a recordar fácilmente de que se trata.

Para poder llevar esta URL a algo mas prolijo utilizaremos mod_rewrite de Apache y un archivo .htaccess. Buscamos lograr una url como la siguiente:

http://www.sitio.com/noticias/2008/02/01

Primero que nada necesitamos saber si nuestro servidor Apache tiene habilitado mod_rewrite, para esto podemos ver en el archivo de configuración httpd.conf el cual debe tener descomentada la línea siguiente:

LoadModule rewrite_module modules/mod_rewrite.so

Nota para los que tengan Windows, pueden tener problemas al probar este módulo, en Linux anda a las mil maravillas.

En caso de que el servidor no soporte el módulo o que escriban mal el archivo .htaccess van a ver un mensaje de error por lo que es recomendable probar primero todo en un directorio separado del sitio principal para no bloquear todo haciendo pruebas. Si tuvieron que modificar el archivo httpd.conf van a necesitar reiniciar el servidor.

El siguiente paso es el de crear el archivo .htaccess, nuevamente los que tengan Windows pueden tener algun problema al intentar crear un archivo que empieza con un punto, lo que pueden hacer es abrir el bloc de notas y en Archivo > Guardar Como eligen “Todos los Archivos” y ponen el nombre .htaccess para guardar.

Empecemos con un archivo básico de ejemplo:

RewriteEngine On
RewriteBase /

RewriteRule ^login/ /login.php [L]

Lo que haremos será poner una URL en el navegador, pero queremos que nuestro script reciba el código como si nada hubiera sucedido, para esto reescribiremos las URLs. Las dos primeras líneas indican que vamos a activar el módulo de reescritura y luego indicamos la ruta para esta operación.

A continuación lo que hacemos es indicar nuestra primera regla de modificación, queremos que cuando alguien ingresa a www.nuestrositio.com/login/, en realidad lo envíe al archivo login.php. Para esto indicamos la palabra a buscar y luego indicamos el archivo php al cual se reenviará el pedido. Claro que esto sucede del lado del servidor, por lo que el visitante del sitio no ve nada “raro” al acceder.

Veamos ahora un ejemplo en el que queremos pasar parámetros en forma limpia a un archivo php:

RewriteRule ^noticias/([0-9]*)/ /noticias.php?id=$1 [L]

Podemos agregar una segunda regla, una por línea y manteniendo las dos primeras línea del archivo .htaccess. Esta nueva regla utiliza una cadena de texto “noticias” y luego una expresión regular para pasar al archivo php un parámetro como variable GET['id'].

La expresión regular de este ejemplo recibe números del 0 al 9 (el asterisco indica que pueden ser muchos) y los pasa al archivo noticias.php donde aparece la variable $1. Si tenemos varios parámetros podemos poner varias expresiones regulares y variables para cada una $1, $2, $3…

Vemos ahora un ejemplo en el cual pasamos letras también:

RewriteRule ^noticias/([a-zA-Z0-9\(\)+%_-]*)/ /noticias.php&title=$1 [L]

En este caso la expresión regular acepta letras de la “a” a la “z”, de la “A” a la “Z” (las expresiones son sensibles a mayúsculas, por eso ponemos los dos casos), también acepta números así como algunos caracteres: ( ) + % _ -

Noten que para los paréntesis necesitamos utilizar la barra de escape “\”la cual indica que vamos a poner un caracter que la expresión puede “confundir” con otra cosa. Este caracter nos sirve para estos casos especiales.

Para seguir ahondando en ejemplos necesitamos tener un manejo de expresiones regulares, tema que escapa a esta entrada específica.

Wikileaks: publicar todos los secretos, sin piedad.

Estamos dispuestos a publicar todos los secretos, aun aquellos que creemos nos dan seguridad? Todos los secretos, desde nuestros impuestos a manuales de tortura pasando por informacion tecnica de armamento y guiones de cine.

Este es el objetivo de Wikileaks, un sitio dedicado a publicar los secretos del mundo, con un objetivo, salvar al periodismo de su patético estado vegetal. En el sitio podremos encontrar desde documentos de como se vacio al estado de Kenya, a material clasificado del Pentágono para ocultar a prisioneros de Guantánamo torturados, así como pruebas de lavado de dinero por bancos de suiza.

Claro que todas estas publicaciones provocaron reacciones, juicios, demandas, amenazas e informes sobre la irresponsabilidad de este emprendimiento, lo cual unicamente provocó el crecimiento explosivo y el lanzamiento a la fama mundial del sitio. Bloqueado durante algunos días en Estados Unidos, duramente criticado por el Pentágono y demandado por corporaciones de todo el mundo, los administradores del sitio no se dejarían vencer tan fácilmente, con servidores distribuídos en todo el mundo y una masa de público que transformó en portavoz del mensaje el sitio se ha visto beneficiado por la atención de los medios y periodismo en general.

Los críticos del sitio plantean que los secretos son necesarios en el mundo actual y que el ideal planteado por Wikileaks es tonto e inocente. Claro que en un mundo donde la capacidad de comunicación se multiplica día a día, no se ven los efectos sobre la libertad de información y la investigación periodística crítica. Es esto lo que Wikileaks plantea salvar, de una forma directa y agresiva, pero clara, publicar todos los secretos sin piedad.

Validación de Formularios

Cuando utilizamos campos de selección, formularios y demás suelen existir reestricciones en lo que podemos hacer. Ya sea un campo para una casilla de mail o para un teléfono, el sitio intentará que ingresemos la información de forma correcta, lo cual puede ser mas o menos amigable con el usuario . Son conoocidos los casos de sitios donde se ingresa algunos campos de formularios y nos dice que hay un error, pero no donde, o bien que no dice nada y no tenemos idea que sucedió, entre otras muchas posibilidades.

Para tratar de dar al usuario las mayores facilidades veremos un poco de validación con javascript, lo cual nos permite verificar los datos que se ingresan antes de que se envíe el formulario, y buscaremos que esta información sea lo más amigable y útil posible.

Comencemos con un simple formulario:

<form method=”post” action=”" name=”form” onsubmit=”return validate(this)”>
<fieldset>
<p><label for=”email1″ class=”left”>Email:</label>
<input type=”text” name=”email1″ id=”email1″ class=”field” value=”" tabindex=”1″ /> *</p>
<p><label for=”email2″ class=”left”>Verificar Email:</label>
<input type=”text” name=”email2″ id=”email2″ class=”field” value=”" tabindex=”2″ /> *</p>
<p><label for=”password1″ class=”left”>Contraseña:</label>
<input type=”password” name=”password1″ id=”password1″ class=”field” value=”" tabindex=”3″ /> *</p>
<p><label for=”password2″ class=”left”>Verificar Contraseña:</label>
<input type=”password” name=”password2″ id=”password2″ class=”field” value=”" tabindex=”4″ /> *</p>
<p><label for=”firsnamename” class=”left”>Nombre:</label>
<input type=”text” name=”name” id=”name” class=”field” value=”" tabindex=”5″ /> *</p>
<p><input type=”submit” name=”register” id=”register” class=”button” value=”Register” tabindex=”6″ /></p>
<p class=”legend”>(* Campos requeridos)</p>
</fieldset>
</form>

Noten algunos detalles que agregamos, macados en negrita:

• onsubmit=”return validate(this)”
  Al enviar el formulario, ya sea haciendo clic en el botón o dando enter, queremos que el contenido del mismo pase por una función de javascript que validará el contenido. La función se llamará validate y pasamos como argumento a la misma el formulario, que al estar haciendo el envío en este preciso momento podemos invocarlo con this.
• id=”email1″
  Debemos poder identificar los campos del formulario con un nombre. Aunque podríamos hacerlo con el atributo name de cada campo, por lo que general queda mas “limpio” el codigo al usar ids. Noten que tenemos un id para cada campo, esto es importante a la hora de poder ir tomando el contenido de cada campo por separado.
• (* Campos requeridos)
  Por último y con el único fin de hacer más amigable las cosas, avisamos que los campos marcados con un asterisco son obligatorios. Esto avisa al usuario de que debe llenarlos y que serán validados.

El siguiente paso es llamar a la función javascript que mencionamos, para esto tendremos dos secciones de código javascript, una que contendrá la validación especifica para este formulario que por ejemplo tiene casillas con nombre de email, contraseña, y dejaremos en un archivo por separado el resto del código que se aplica a cualquier caso de validación, como es mostrar el mensaje de error, etc.

Al final de este artículo están disponibles los archivos para la descarga, dentro de messages.html encontrarán el formulario html con el código javascript específico al formulario y una llamada a un archivo externo messages.js que contiene el código general, además de un archivo css y un archivo de imagen.

Volviendo al código, para validar esta formulario utilizaremos un código como este:

<script type=”text/javascript”>
document.forms.form.email1.focus();

function validate(form) {
// Pasamos contenido de los campos a variables
var name = form.name.value;
var email1 = form.email1.value;
var email2 = form.email2.value;
var password1 = form.password1.value;
var password2 = form.password2.value;

// Expresiones regulares que utilizamos para validar las cadenas de texto segun cada caso
var nameRegex = /^[a-zA-Z]+(([\'\,\.\- ][a-zA-Z ])?[a-zA-Z]*)*$/;
var emailRegex = /^[\w-\.]+@([\w-]+\.)+[\w-]{2,4}$/;
var messageRegex = new RegExp(/<\/?\w+((\s+\w+(\s*=\s*(?:”.*?”|’.*?’|[^'">\s]+))?)+\s*|\s*)\/?>/gim);

if(email1 == “”) {
inlineMsg(‘email1′,’Ingrese su email.’,2);
return false;
}
if(!email1.match(emailRegex)) {
inlineMsg(‘email1′,’Ha ingresado un email invalido.’,2);
return false;
}
if(email1 != email2) {
inlineMsg(‘email2′,’El mail y su verificacion no coinciden.’,2);
return false;
}

if( (password1 == “”) || (password1.length < 6) ) {
inlineMsg(‘password1′,’Ingrese una contraseña de al menos 6 caracteres.’,2);
return false;
}
if(password2 != password1) {
inlineMsg(‘password2′,’La contraseña y su verificacion no coinciden’,2);
return false;
}

if(name == “”) {
inlineMsg(‘name’,'Ingrese su nombre.’,2);
return false;
}
if(!name.match(nameRegex)) {
inlineMsg(‘name’,'Ha ingresado un nombre invalido.’,2);
return false;
}

return true;
}
</script>

La primera línea lo único que hace es colocar el foco o cursor de escritura sobre el primer campo del formulario. Luego tenemos la función validate que recibe el formulario que debe validar, “function validate(form) {“, y enseguida dentro de la misma pasamos los contenidos de los campos a variables y preparamos expresiones regulares para validar los distintos casos de email, nombre, mensaje.

El resto del código es simplemente validar cada una de las casillas, con una condición y en caso de que la cumpla llamamos a otra función (inlineMsg, que se encuentra dentro del archivo js externo que mencionamos antes) la cual se encarga de mostrar el mensaje de error.

if(email1 == “”) {
inlineMsg(‘email1′,’Ingrese su email.’,2);
return false;
}

En este caso verificamos si la variable email1 contiene el valor vacío, en caso de ser asi llamamos a inlineMsg pasándole como parámetros el id del campo que estamos validando, el mensaje de error y si queremos que el mensaje desaparezca solo luego de 2 segundos.

Con esto deberíamos tener una validación básica pero amigable para el usuario, fundamental para que nuestros sitios sean utilizados y no generen rechazo.

(Créditos: http://www.leigeber.com/2008/04/dynamic-inline-javascript-form-validation/)

Descargar archivos validación JS

En busca del uploader perfecto (Parte I)

Uno de los grandes problemas de usabilidad en Internet es la interacción con el usuario cuando enviamos archivos. Por lo general al hacer descargas tenemos la barra de progreso del navegador que nos indica el estado/velocidad de la transferencia, pero qué sucede cuando enviamos un archivo? Especialmente en el caso de archivos grandes y cuando tenemos conexiones relativamente lentas, tenemos el problema de no saber qué pasa con el envío… Si se detuvo, si sigue funcionando, solo nos queda esperar a ver que pasa.

Aunque hay muchas soluciones parciales a este problema, por ejemplo con animaciones flash o javascript que muestran una barra de progreso simulado, queremos una solución real, que muestre si realmente hay transferencia.

Las soluciones más básicas de envío de archivo suelen funcionar con un formulario html que envía el o los archivos a un script para procesar, un código como este es algo típico:

<form action=”" method=”post” name=”form1″ enctype=”multipart/form-data”>
<input type=”file” name=”file1″ />
</form>

Claro que este tipo de transferencia no nos da ninguna interacción avanzada que indique al usuario el progreso de la transferencia. Para esto vamos a necesitar un script del lado del servidor que se encargue de recibir el archivo. A pesar de que con PHP se pueden hacer unas cuntas cosas, no tenemos la capacidad de acceder directamente al sistema de archivos y ver el progreso del mismo, por lo cual queda descartado el uso del mismo por lo menos para monitorear el progreso de la carga. Sí podemos utilizar PHP para el resto del proceso, como sea insertar en una base de datos, enviar mensajes etc.

El intermediario para esta solución será un script en Perl, llamado Uber-Uploader. Este script requiere de que el servidor soporte scripts Perl, trabajando con también con PHP y Javascript. El sitio de origen de este script lo pueden encontrar aquí: http://uber-uploader.sourceforge.net/. De todas formas ya que al día de hoy no está actualizado a la última versión disponible adjunto un zip con los archivos necesarios.

Una gran ventaja de este script es que no necesitamos modificar mas que la configuración del mismo, sin tener que meternos con el código en Perl.

Volviendo al script, tenemos los siguiente archivos dentro del zip en cgi-bin:

• uu_default_config.pm
• uu_ini_status.pl
• uu_lib.pm
• uu_upload.pl

Estos son los archivos de Perl que deben incluirse en el directorio cgi-bin o donde nuestro servidor ejecute los archivos cgi (si este directorio no existe se puede probar con la raíz del sitio). Es muy importante que los permisos de ejecución esten correctamente configurados para que Apache pueda ejecutar el script. Seteando los permisos en 755 para todos los archivos de cgi-bin no deberíamos tener problema.

El archivo que más nos interesa en este caso es uu_default_config.pm que contiene la configuración general de directorios y filtros. Las opciones más importantes son:

• config_file_name
  Nombre del archivo de configuración, en la segunda parte veremos que podemos tener varias configuraciones.
• temp_dir
  Archivo temporal de carga para el script.
• upload_dir
  Donde quedarán guardados los archivos al ser cargados.
• max_upload
  Tamaño máximo de los archivos.
• redirect_url
  Dirección a donde nos llevará el script al terminar de cargar, donde podremos realizar tareas post carga como interacción con bases de datos etc.
• disallow_extensions
  Extensiones no permitidas de archivo.

Con esto tenemos la configuración del script Perl, ahora veamos la otra parte, PHP y Javascript. En este caso tenemos los siguientes archivos (los que aparecen fuera de cgu-bin en el zip):

• upload.php
• uu_conlib.php
• uu_file_upload.js
• uu_finished.php
• uu_finished_lib.php
• uu_get_status.php

Empecemos por uu_conlib.php, el cual es el archivo de configuración del lado de PHP. Las variables que más nos interesan son:

• $path_to_upload_script
  Define la ruta donde está el script Perl, noten que si el mismo no esta dentro de cgi-bin deberemos modificar la ruta.
• $path_to_ini_status_script
  Lo mismo que para la variable anterior.
• $default_config_file
  Archivo de configuración que utilizará este PHP, útil en caso de usar varias configuraciones.
• $max_upload_slots
  Cantidad máxima de slots de carga, sí, podemos cargar muchos archivos en cola =).
• $progress_bar_width
  Largo de la barra de progreso, más que nada un tema de diseño.

Pasemos al archivo upload.php, archivo que contiene el formulario html y archivo donde se “muestra” el uploader. Aquí podemos agregar variables al formulario las cuales recibiremos al finalizar la carga de los archivos, por ejemplo id de usuarios, campos con descripciones, etc.

Por último tenemos el archivo uu_finished.php, archivo a donde llegamos al terminar la carga. El script procesa la información de los archivos, datos como nombre, tamaño, etc de cada archivo cargado es accesible en este archivo. Por ejemplo para obtener el nombre del primer archivo cargado podemos hacerlo de la siguiente forma:

$_FILE_DATA[0]->getFileInfo(‘name’)

Y en caso de tener varios archivos cargados podemos hacer lo siguiente:

for ($i = 0; $i < count($_FILE_DATA); $i++) {
$filename = $_FILE_DATA[$i]->getFileInfo(‘name’);
$filesize = $_FILE_DATA[$i]->getFileInfo(’size’);
…
}

Ahora tenemos un panorama general del uso de este script, en la segunda parte veremos como tener varios archivos de configuración, como personalizar el formulario de contacto y los errores más comunes que debemos verificar.

Descargar archivo zip con script Uber Uploader.

El Inicio

Por fin, luego de meses de estar a punto de hacerlo se dió… Aunque la idea estuvo en la vuelta durante años recién con la unión de energías en Trepcom es que llegó el empujón para arrancar. Ahora veremos que sucede, si pasa a tener algún sentido o queda en el olvido, aunque con la ayuda de algunos de los Blogs hermanos que nacen junto a este eso no sucederá.

En teoría este Blog tendrá el objetivo de aportar en temas de programación, desarrollo de sitios Web, Internet y tecnologías relacionadas. Nada muy original, aunque los contenidos intentarán serlo, aportando código, ejemplos, recursos y demás que pueden llegar a interesar a alguien.

Para los curiosos, estos son los Blogs hermanos:

www.rodolfotechera.com
www.hilifer.com

Veamos que sucede =)