Búsqueda por Dicotomia / DataProviderClass

Estos últimos días vamos todos de culo pero no queremos que parezca que esto está muerto. Como veis la interfaz gráfica es bastante feilla pero es que mis días tendrían que tener 48h para poder hacer la mitad de las cosas que quiero.

Bueno... me dejo de tonterías y explico en cuatro lineas como ampliar el DataProviderClass para poder realizar búsquedas binarias o dicotómicas sobre propiedades de los objetos que consituyen su array principal: "items".

Para los que no hayais trabajado nunca con DataProviderClass hago una breve introducción.

DataProviderClass es una clase implementada en los UIComponents que trabaja como un puro contenedor de datos. Estos datos son los que nutren posteriormente a los distintos componentes implementados por Macromedia, aunque personalmente considero su uso una buena práctica para gestionar el modelo de datos y la capa de presentación.

En resumidas cuentas: consiste en un Array 'items' y de un grupo de métodos públicos y 'privados' que lo manipulan y como consecuencia notifican a las instancias gráficas que tenga registradas de la modificación de los datos.

Uno de sus usos podría ser en combinación con un ListBox. En este caso crearíamos un nuevo DataProviderClass y lo registraríamos en nuestro ListBox. Haciendo modificaciones en el DataProviderClass estas repercutirían directamente en la representación gráfica del ListBox.

Veamos un ejemplo:
1. Arrastramos a nuestro escenario una instancia del componente ListBox y le llamamos 'myListBox_lb'.

2. En el mismo fotograma añadimos el siguiente código:

users_dpc = new DataProviderClas();

users_dpc.addItem("Juan");
users_dpc.addItem("Pepe");
users_dpc.addItem("Vanesa");
users_dpc.addItem("Victor");
users_dpc.addItem("German");
users_dpc.addItem("Dani");
users_dpc.addItem("Cristina");
users_dpc.addItem("Oscar");
users_dpc.addItem("Pepito");
users_dpc.addItem("Menganito");
myListBox_lb.setDataProvider(users_dpc);

Con esto si ejecutamos veremos ya resultados por pantalla. Hasta ahora la cosa no tiene mucha gracia porque esto mismo se podría haber hecho igual de fàcil usando el método 'addItem' de FListBox. Pero la verdad es que su gracia aparece cuando tenemos la necesidad de presentar los mismos datos en varios componentes distintos. En este caso el uso de DataProviderClass es mucho más práctico ya que simplemente modificando los datos automáticamente se autoregeneran las gráficas.

Para verlo en la práctica podemos arrastrar otro componente al escenario. En este caso pondremos un ComboBox, además del código y el ListBox del ejemplo anterior.

1. Arrastramos una instancia del FComboBox y le llamamos myComboBox_cb.

2. Al código anterior le añadimos la siguiente linea:

myComboBox_cb.setDataProvider(users_dpc); 

Y ahí lo tenemos funcionando ;-)

Sólo un par de comentarios más acerca del DataProviderClass. No es una clase incorporada directamente en el Player así que no la podemos utilizar así como así. Para poder utilizarla tenemos que añadirla a la biblioteca. La podemos encontrar en la carpeta (de la liberería) 'FUI Component Class Tree' que aparece cuando arrastramos alguna instancia de alguno de los FUIComponents a nuestro escenario. Si no hacemos uso de ningún componente todo lo demás relacionado con Componentes lo podemos eliminar de nuestra biblioteca.

No hay documentación oficial acerca de esta clase, almenos que yo sepa, pero existe un buen recurso de donde la podeis sacar:
http://www.wheelmaker.org/

Esta es la página del libro "Object-Oriented Programming with ActionScript" de Branden Hall y Samuel Wan. En la sección downloads os podéis bajar el código del libro (bastante bueno por cierto). Una vez descargado el código lo descomprimis y en el directorio del capítulo 6 encontraréis un .doc con la implementación de la clase así como los comentarios y documentación de Samuel Wan.

Bueno, pues introducido esto brevemente, pasemos a la ampliación de la clase. El 'problema' que tiene esta clase es que para eliminar elementos del array sólo existen 2 métodos: removeAll() y removeItemAt().

removeAll() hace precisamente lo que dice su nombre, borra todos los datos del array 'items'. removeItemAt(i) elimina el elemento i-ésimo del array, o lo que es lo mismo, se carga el elemento items[i].

El inconveniente es que a priori no tenemos ningún método con el que podamos eliminar un elemento a partir del texto que visualizamos a través de los componentes ni de cualquier otro campo distinto.

Una posible implementación para eliminar un elemento en concreto utilizando los métodos que incorpora podría ser:

var length = users_dpc.getLength();
for (i = 0; i < length; i++)  {
      if (users_dpc.getItemAt(i)[label] == "cadena_que_busco")
      users_dpc.removeItemAt(i)
}

La eficiencia de esto no es que sea muy alta, ya que nos recorremos todos los elementos del array. Si se trata de un array pequeño pues no pasa nada, pero como estemos trabajando con uno bien grande todo nuestro gozo se queda en un pozo. Hoy mismo me he encontrado con este problema y he optado por intentar hacer un mejor planteamiento: búsqueda binaria o por dicotomia.

Una búsqueda dicotómica nos permite reducir considerablemente los ciclos de CPU necesarios para hallar un elemento dentro de un array. Este sistema parte de la premisa que el array esté ordenado alfabéticamente / numéricamente.

El DataProviderClass en su esencia actua como si se tratara de un array, pero es un array que contiene Objectos. Evidentemente los objetos no se pueden ordenar directamente, así que no podemos utilizar Array.sortOn que incorpora Flash. Pero para ello tenemos el método sortItemsBy(campo,orden) del DataProviderClass que nos permite hacer precisamente esto. Su uso es el siguiente:

users_dpc.sortItemsBy("label", "ASC");

Esto nos ordenará nuestro Array de objetos atendiendo a la propiedad 'label' de cada uno de los objetos que tengamos en el array 'items'.

En fin, una vez ordenado el array qué hace el algoritmo dicotómico (joé que mal que suena!) ?

Pues coge el elemento que se encuentra en la posición media del Array y lo compara con el valor que estemos buscando. Por ejemplo, si tenemos un array de 10 elementos, coge el elemento 5. Si es de 11, tendríamos que coger el elemento 5'5, pero como esto no puede ser cogemos el entero menor, en este caso 5.

Si el valor/cadena que buscamos se encuentra por debajo (alfabéticamente) del valor evaluado (items[5] en el ejemplo anterior) entonces coge un nuevo elemento intermedio del Array. Esta vez tomando como primer elemento el 0 y como último el anterior punto medio encontrado. En nuestro ejemplo cogeríamos el 2'5 --> 2. En otras palabras, digamos que cambia el rango del array en el que buscar. Si el valor que buscamos fuera mayor que el evaluado, entonces nuestro rango sería, desde el elemento intermedio hasta la longitud del array.

Este mismo proceso de limitación de posibles candidatos se va haciendo secuencialmente hasta hallar el valor o hasta que llegue un momento que no se puedan generar más intervalos de búsqueda, caso en el que la búsqueda no habrá producido ningún resultado (devolveremos: return -1)

En fin, el código para ampliar el DataProviderClass, y con muy pocas modificaciones la clase Array o cualquier otra:

/**
 * @method: removeItem(itemSeacrh)
 * Elimina el elemento del array que su propiedad "label"
 * coincida con itemSearch
 * @params: itemSearch--> Cadena a buscar para eliminar
 * @return: el elemento eliminado o -1 si no se ha eliminado
 ****/
 DataProviderClass.prototype.removeItem = 
  function(itemSearch){

       var itemId = this.searchItem(itemSearch,"label");
       if(itemId == -1) 
             return(-1);
       else
             return(this.removeItemAt(itemId));
 };

/**
 * @method: searchItem(itemSeacrh,propiedad)
 * Busca el elemento del array que su propiedad 'campo'
 * coincida con 'itemSearch'
 * @params: itemSearch --> cadena a buscar
 *          propiedad --> propiedad en la que buscar
 * @return: -1 <-- Si no se hallan coincidencias
 *           x <-- Indice del elemento en el que se 

           ha hallado la coincidencia
 ****/

 DataProviderClass.prototype.searchItem =

 function(itemSearch,propiedad) {
       var centro, actualItem;
       var encontrado = false;
       var izquierda = 0;
       var derecha = this.getLength() - 1;

       while (!encontrado && izquierda <= derecha) {
             centro = Math.floor((izquierda + derecha) / 2);
             actualItem = this.getItemAt(centro)[propiedad];
             trace(centro + " --> " + actualItem);

             if (itemSearch < actualItem)
                   derecha = centro - 1;
             else if (itemSearch > actualItem)
                   izquierda = centro + 1;
             else {
                   encontrado = 1;
                   trace("encontrado :: " + itemSearch + " = " 

+ actualItem);
                   return centro;
             }
       }
       return -1
 };

Nota: se parte de la premisa de tener el DataProviderClass ordenado y con elementos no idénticos en la propiedad donde se realiza la búqueda. Con esta implementación sólo se devolvería un resultado en caso que hubiera dos propiedades con idéntico valor. Os dejo a vosotros la ampliación ;-)

La mejora es sustancial. Imaginemos un array de 30 elementos y que estamos realizando una búsqueda que nos devolverá la última posición de dicho array. Si lo hiciéramos con un for recorriendo cada uno de los elementos tendríamos que hacer nada más y nada menos que 30 comparaciones, con este método realizamos tan sólo 6.

Para que veais un ejemplo de uso os dejo aquí un link para que descargueis un .fla que implementa esto.

Pues hasta aquí la primera entrada / explicación (no tan breve como quería) pero bueno... Espero que os haya gustado y espero vuestras críticas, aportaciones, comentarios, en fin, lo que queráis decir... que se tendrá en cuenta para posts posteriores ;-) Y por supuesto por si algo está mal o puediera estar mejor sobre el artículo :P

Saludos