Tema 8c 2

TADs génericos y algoritmos genéricos

Se puede definir TADs genéricos (o tipos parametrizados) con algunas caracteristicas indefinidas.

Estas caracteristicas pueden ser concretadas posteriormente de diversas formas según las necesidades, obteniendo ejemplares de TADs concretos distintos.

Un algoritmo se denomina genérico si manipula TADs genéricos.

La genericidad facilita la reutilización de algoritmos. Por ejemplo, si se implementa un algoritmo de ordenación de vectores, los tipos de datos de los índices y de los elementos del vector no afectan al algoritmo, siempre y cuando se disponga de una función de orden que diga si un elemeno es mayor que otro.

Módulo de declaración ordenación_g.ads

generic

     type ind is (<>); //cualquier tipo discreto

     type elem is private; //cualquier tipo

     type vector is array (ind range <>) of elem;

     with function ">" (a,b: elem) return boolean;

package ordenacion_g is

     procedure ordena (v: in out vector);

end; //del módulo de declaración

Módulo de implementación ordenacion_g.adb

package body ordenation_g is

     procedure ordena (v: in out vector) is

           i,j:ind, m, t: elem, n:intenger;

      begin

          --inicialización

          i:=v'first;

          j:=v'last;

          n:=ind'pos(i)

          n=n+ind'pos(j);

Ha decidido que no era importante los atributos, si no de entender que puedo jugar con los elementos ¿?

Uso desde un programa de un ejemplar concreto de vector

witch ordenacion_g;

procedure mi_programa is

     type color is (rojo, azul, gris);

     type dia is (lu, ma, mi, ju, vi, sa, do);

     type vect is array (day range <>) of color;

     x:vect(ma..vi):=(gris, azul, rojo, gris);

     package o is new ordenacion_g(dia, color, vect, ">");

begin

     ...

     o.ordena(x);

     ...

end mi_programa;

¿Qué gano además con los TADs y la modularidad?

Pues oculto totalmente cómo se representa la información y cómo se implementan los algoritmos.

Podría cambiar en el futuro ambas cosas, y mientras mantenga la interfaz, el usuario del módulo ni lo notará.

De esta manera, podría hacer una versión rápida que funcionara, y después hacer versiones sucesivas que fueran refinando y mejorando las anteriores, especialmente en cuanto a eficiencia, funcionalidad o capacidades.

ejemplo: una pila

Por ejemplo supongamos que tengo un problema para el que necesito una pila, y me urge tener una pila disponible para hacer pruebas, porque lo importante es probar el problema en sí mismo.

De hecho, el problema lo va a resolver otra persona, a mí me encargan que tenga cuanto antes una pila operativa... Y yo no sé ni lo que es un puntero.

Pila: la interfaz

Lo más importante es que yo tenga claro lo que es una pila, aunque no tenga muy claro cómo implementarla, y que el que la va a usar también lo tenga claro (la implementación a él le da igual completamente, a mí no). Y que lo que él va a usar es exactamente lo mismo que yo voy a implementar.

Es decir, hace falta definir antes de empezar a trabajar cada uno por su lado, qué operaciones va a haber, qué atributos van a tener, de qué tipo, en qué orden y qué hace exactamente cada operacioón y en que condiciones funciona.

Podrían ser las siguientes:

- creaPila: -> pila

- apilar: pila elemento -> pila

- parcial desapilar: pila -> pila

- parcial cima: pila -> elemento

- esVacia: pila -> booleano

Especificación formal

especificación pila

     usa booleanos

     parámetro formal

          genérico elemento

     genérico pila

     operaciones

          creaPila: -> pila

          apilar: pila elemento -> pila

          parcial desapilar: pila -> pila

          parcial cima: pila -> elemento

          esVacia: pila -> booleano

dominios de definición     p:pila, e: elemento

          desapilar(apliar(p,e))

          cima(apilar(p,e))

ecuaciones      p:pila, e:elemento

          desapilar(apilar(p,e))=e

          cima(apliar(p,e))=e

          esVacia(crearPila)=verdad

          esVacia(apilar8p,e))=falso

fin especificación

Implementación estática

Mientras pienso en cómo dar una solución definitiva al problema que tengo entre manos (y mientras me estudio cómo funcionan los punteros en el lenguaje de programación en el que tengo que hacer el desarrollo), lo que voy a hacer en montar algo que funcione, aunque sea una solución de andar por casa, ya que total, nadie sabrá jamás que he hecho eso, y mi jefe estará contento porque el otro programador tendrá en dos horas una pila operativa para poder hacer pruebas sobre ella.

Así que sin más puedo simular  una pila con un vector con espacio para un número max de elementos, y un contador cima que me dice hasta dónde lo he llenado.

Implementación dinámica

Luego con tranquilidad, cuando ya domino los punteros, desarrollo en los días siguientes una pila "de verdad".

Sin más que mantener la interfaz, el otro programador ni se enterará del cambio.

Esta pila por supuesto tendrá sus nodos y sus punteros al nodo siguiente, y todo lo que yo estime necesario.

Si en el futuro quiero mejorar alguna función o procedimiento, hacien do una nueva versión mejorada de la pila, siempre y cuando mantenga la interfaz, podré hacerlo sin ningún problema, sin que el otro programador tenga que modificar ni una línea, y sin que ni siquiera se llegue a enterar del cambio, ya que él no apreciará diferencia algna (salvo posiblemente en capacidad o eficiencia).