                 La Implementacin de ListAHO.pas

                               por

                          Adolfo Di Mare

                    Reporte Tcnico ECCI-94-05
                       Proyecto 326-93-256
                           Revisin 1.0

Resumen:
=======

Se discute cmo  est construida la  implementacin del ADT  TList 
segn  la abstraccin  informalmente definida en  [AHO-83], en sus 
dos variaciones ms importantes: LahoV.pas y LahoP.pas.  Estas dos 
implementaciones corresponden a  la  misma  abstraccin  del  Tipo 
Abstracto  de  Datos  (ADT)    TList,  aunque  su  rendimiento   y 
requerimientos de recursos son bastante diferentes.  LahoP.pas  es 
una implementacin que utiliza punteros para enlazar los nodos  de 
la  lista  mientras  que  LahoV.pas  representa  una  lista   como 
elementos de un  arreglo.   Ambas  implementaciones  son  bastante 
sencillas por  lo que  no sirven  en aplicaciones  importantes: su 
valor  es ms  que todo didctico,  pues [AHO-83] es  un excelente 
libro de texto para estudiar Estructuras de Datos.

Estas implementaciones  se han  realizado para  el ambiente  Turbo 
Pascal v5.0, aunque para trabajar con ellas es ms cmodo usar  la 
versin v6.0 o una posterior.


Abstract:
========

We discuss  how the  implementation for  TList Abstract  Data Type 
(ADT) is constructed, based on the informal abstraction defined in 
[AHO-83] in its  two  more  important  variations:  LahoP.pas  and 
LahoV.pas.   These  implementations correspond  to the  same TList 
abastraction,   even   though  their   performance  and   resource 
requirements  are very different.   LahoP.pas is an implementation 
that uses  pointers to  link nodes  in a  list, whereas  LahoV.pas 
represents  a   list  as   elements  in   an  array.    These  two 
implementations  are  very  simple  and unsuitable  to be  used in 
seriours applications: they have a didactic value because [AHO-83] 
is an excelent Data Structures text book.

These implementations  have been  made for  the Turbo  Pascal v5.0 
environment, but  it is  less cumbersome  to use  version v6.0  or 
later to work with them.


Esta investigacin se realiz dentro del proyecto de investigacin 
326-93-256 "DBgen: Generacin de Sistemas  a partir de su Base  de 
Datos" inscrito ante  la  Vicerrectora  de  Investigacin  de  la 
Universidad  de  Costa  Rica.   La  Escuela  de  Ciencias  de   la 
Computacin e Informtica tambin ha aportado fondos para realizar 
este trabajo.


                 La Implementacin de ListAHO.pas
                 ================================


     Una clasificacin  simple de  los Tipos  Abstractos de  Datos 
(ADTs) los divide en dos tipos bsicos: los simples o elementales, 
y  los contenedores. Un  ADT es un contenedor  si contiene a otros 
ADTs. Los contenedores ms importantes son tres:
     1.- El ADT Arreglo [ARRAY]
     2.- El ADT Lista   [List.pas]
     3.- El ADT Arbol   [Tree.pas]
Existen  otros   ADTs  importantes,   como  Graph.pas,   Heap.pas, 
Matriz.pas,  etc,  pero  la  mayora de  las estructuras  de datos 
importantes se obtienen al combinar inteligentemente a estos  tres 
ADTs.   De todos estos, el ms  importante es, sin duda alguna, el 
Arreglo, hasta el punto de que todos los lenguajes de  computacin 
modernos lo incluyen como una construccin sintctica bsica.

     Despus del ADT Arreglo, la Lista es sin lugar a dudas el ms 
importante de los ADTs contenedores, por lo que es muy  importante 
estudiarlo.  Una  sencilla especificacin  de la  lista es  la que 
est  informalmente  definida   en  [AHO-83].   Esta   abstraccin 
implcitamente asume que el programador no usa ADTs para construir 
sus programas, pues define la lista de forma que la implementacin 
de  dos de sus ms  importantes operaciones, Insert()  y Delete(), 
sea muy fcil  de  programar,  de  forma  que  si  el  programador 
necesita  manipular  listas en  sus programas  pueda recordar  con 
facilidad y exactitud como  reprogramar esas dos operaciones  cada 
vez que necesite usar una  lista.  Esta prctica es muy  frecuente 
entre  muchos programadores que todava  no conocen la utilidad de 
usar Abstraccin de Datos para construir programas.

     Pese a la  fuerte limitante que  tiene la especificacin  del 
ADT  TList  definido  por  [AHO-83],  es  importante  conocer   su 
implementacin por las siguientes razones:

1) Para condimentar  el proceso  de enseanza-aprendizaje  del ADT 
   TList es importante que cualquier estudiante estudie en detalle 
   las implementaciones  LahoP.pas y  LahoV.pas, pues  luego puede 
   comparar  sus  limitaciones  con  otras  implementaciones   ms 
   robustas y completas del ADT TList.

2) La especificacin del ADT TList parece simple a primera  vista, 
   pero  en la prctica es  bastante complicada, como lo demuestra 
   la informalidad dela especificacin de TList que se presenta en 
   [AHO-83].    En   esta   implementacin   se   encuentra    una 
   especificacin  ms  completa y  sin ambigedades  de la  lista 
   definida en [AHO-83], lo que ayuda a agregarle valor al uso  de 
   este importante texto  de Estructuras de  Datos, pues salvo  la 
   pequea deficiencia en la  especificacin de TList, este  libro 
   es una obra clsica en Computacin.

   Cuando el estudiante estudia y logra entender la especificacin 
   que  acompaa  a esta  implementacin, entonces  comprende cmo 
   mejorar  el diseo y la  implementacin de sus Tipos Abstractos 
   de Datos.

3) La  mayora de  las implementaciones  del contenedor  TList que 
   aparecen en la  literatura  se  concentran  en  los  trucos  de 
   programacin  necesarios  para   manipular  los  punteros   que 
   permiten implementar listas de  muchas formas, pero en  general 
   los autores no  tratan de definir  de manera bien  estructurada 
   qu es una lista,  hasta  el  punto  de  que  muchas  veces  se 
   confunde  al  ADT  contenedor  TList  con  los  elementos   que 
   contiene.

   La separacin de  funciones entre el  contenedor y el  elemento 
   contenido que se presenta en estas implementaciones del ADT  es 
   muy  importantes  porque le  muestra al  estudiante como  crear 
   nuevas estructuras de datos usando Abstraccin de Datos, lo que 
   es  fundamental para escribir  cdigo reutilizable.  Adems, de 
   esta   forma  el  estudiantes   aprende  a  implementar  nuevas 
   estructuras de datos con base en las existentes.

3) Dada la complejidad de esta implementacin, el estudiante tiene 
   la  oportunidad de  comprender cules son  las limitaciones que 
   tiene el uso de Tipos Abstractos de Datos para la  construccin 
   de programas sofisticados.

     El  ADT  lista es  el contenedor  que sirve  para representar 
secuencias de elementos  en computador.  Una  lista L contiene  un 
conjunto  finito  de  elementos  organizados  de  acuerdo  a   las 
siguientes propiedades:

a) L es un conjunto finito,  o vaco, de elementos almacenados  en 
   "nodos" [Empty(L)-Full(L)].

b) Cada nodo de la lista est conectado a su sucesor por medio  de 
   un enlace [Next(L,p)-Prev(L,p)].

c) Un lista no vaco siempre tiene nico nodo inicial [First(L)] y 
   un nodo final [Endl(L)].

d) Cada nodo en la lista, excepto el primero, tiene un nico  nodo 
   que le precede [Prev(L)].

e) La longitud de  la lista  es el  nmero de  nodos que  contiene 
   [Count(L)].

f) Para accesar un nodo en la lista es necesario recorrerla  desde 
   el principio.

g) En general, una lista  es  una  estructura  de  datos  que  usa 
   memoria  dinmica  por  lo  que su  tamao y  requerimientos de 
   memoria pueden variar en tiempo de ejecucin.

     En el siguiente diagrama se muestra una lista:

               L = [a]->[b]->[c]->[d]->[e]->[f]
                   ^ ^             ^         ^
                  /  |             |         |
                 /   |             |         |
                /    |             |         |
               p  First(L)         q      Endl(L)

     Para definir  la lista  como un  Tipo Abstracto  de Datos  es 
necesario distinguir entre un nodo  de la lista, el contenido  del 
nodo y su posicin  en la lista.  En  este diagrama los nodos  son 
las cajitas  ([a]...[f])   que  estn  ligadas  en  secuencia,  el 
contenido  de cada  nodo es lo  que aparece dentro  de cada cajita 
("a".."f"),  y la  posicin de cada  nodo es un  apuntador al nodo 
(@[d]=q).  Por ejemplo, la posicin del primer nodo de la lista es 
p=@[a]=First(L).

     Para  no cargar  mucho la notacin,  en este documento  no se 
hace distincin entre un nodo de  la lista y su contenido, por  lo 
que en lugar de hablar de "la posicin del primer nodo de la lista 
L" simplemente se dice que p=@a=First(L), o sea que el primer nodo 
de L se denota  con @a: la notacin  "@" sirve para distinguir  al 
valor  del  nodo de  su posicin  en el  lista.  Esta  notacin es 
ambigua pues no permite representar un  lista en que dos o ms  de 
sus nodos tienen el mismo valor, aunque es ms cmoda de usar.  De 
acuerdo a esta convencin, el  diagrama del lista L es  cualquiera 
de estas dos:
               L = a->b->c->d->e->f

               L = (a,b,c,d,e,f)

     En general, las lista se denotan encerrando entre  parntesis 
entre los valores de sus elementos: L=(a,b,c,d,e,f).

     Como se muestra en el diagrama  de L,  este lista  cumple con 
las siguientes propiedades del ADT TList:

- L no est vaca: Empty(L) = FALSE.

- El primer node de L es [a]: @a=Fisrt(L).

- El segundo nodo de L es el que contiene a "b", y el penltimo es 
  el que contiene "e":

  @b = Next(L, @a) = Next(L, First(L))
  @e = Prev(L, @f) = Prev(L, Lpos(L, Count(L)))


Abstraccin de TList
====================

     Para almacenar una lista en el computador es necesario  crear 
una  abstraccin  del  concepto  "lista", la  que luego  puede ser 
cristalizada en  la implementacin  del ADT  lista.  Para  definir 
esta abstraccin es necesario definir los elementos que forman una 
lista:
     1) Nodos
     2) Valor almacenado en cada nodo    [Unidad Elem.pas]
     3) Posicin en el lista
     4) Aristas de enlace entre nodos.

     En  la  implementacin, a  cada uno  de estos  conceptos debe 
corresponder un tipo de datos o un campo en una instancia. En esta 
implementacin, la correspondencia es la siguiente:

     1) Nodo       Tipo    TNode_RepList  List.pas
     2) Valor      Tipo    TElem          Elem.pas
     3) Posicin   Tipo    PLpos          List.pas
     4) Arista     Campo   punteros       List.pas

     Aunque existen muchas formas de implementar el ADT lista, dos 
muy  importantes  son  las  usadas en  LahoP.pas y  LahoV.pas.  La 
principal ventaja de LahoV.pas sobre LahoP.pas es que no  necesita 
representar directamente las aristas, pues con base en la posicin 
relativa de los nodos de la lista se puede deducir cuales son  los 
enlaces  entre   nodos.   Por   eso  es   importante  conocer   la 
implementacin LahoV.pas que  representa  al  ADT  TList  como  un 
vector de  elementos, y  por ende  requiere menos  espacio que  la 
implementacin  de LahoP.pas, que usa  punteros para enlazar a los 
nodos de la lista.

     La  ventaja   de  LahoP.pas   sobre  LahoV.pas   es  que   la 
implementacin de punteros no es necesita asignar de antemano toda 
memoria para la  lista,  pues  en  LahoP.pas  se  obtiene  memoria 
dinmica conforme el programa avanza, y tambin se devuelve cuando 
ya no se  ocupa.  Estas dos  implementaciones representan las  dos 
caras de la moneda, pues  el programador puede cambiar tiempo  por 
espacio para mejorar el rendimiento de su programa.

     En  la   prctica,  sin   embargo,  lo   usual  es   usar  la 
implementacin LahoP.pas en los programas, pues la mayora de  los 
programadores no le dan  el  rango  de  ADT  a  la  implementacin 
LahoV.pas,  porque  esa implementacin  puede ser  vista como  una 
versin mutilada de la abstraccin del ADT Arreglo que el lenguaje 
ofrece,  y  que cualquier  programador usa  con gran  naturalidad.  
Como  el  ADT  Arreglo  ya suple  al programador  con todo  lo que 
LahoV.pas  puede  ofrecerle,  por  lo  que  en  general  no  usar 
LahoV.pas para implementar sus programas.

     Si un lenguaje soporta la sobrecarga de operadores, que es el 
caso de C++ y Ada, entonces es posible implementar el ADT  Arreglo 
usando el  ADT TList:  esta es  la principal  justificacin de  la 
existencia de esa construccin sintctica.  En este escenario,  el 
programador no  necesita usar  explcitamente las  operaciones del 
ADT  TList  en su  cdigo para  mantener la  opcin de  mejorar el 
rendimiento de  su programa  cambiando la  implementacin del  ADT 
Arreglo  o la de TList, pues en  este caso el uso de la sobrecarga 
de  operadores   le  permitir   cambiar  la   implementacin  del 
contenedor  que  use, y  no tendr  que modificar  cdigo pues  el 
compilador se encargar  de usar la  nueva versin del  contenedor 
cuando el programa sea recompilado.

     Para incrementar la modularidad del ADT, la implementacin de 
TList consta  de  dos  unidades  Pascal.   La  primera,  List.pas, 
contiene todo el cdigo que implementa al ADT Lista. La segunda es 
la unidad llamada  Elem.pas, que tiene  todas las operaciones  del 
ADT elemental contenido en la lista. Este ADT elemental puede ser, 
a su vez, otro contenedor. El ADT lista puede contener a cualquier 
otro  ADT para el que  estn definidas las operaciones elementales 
que usa List.pas para manipular a Elem.pas.

     Para adaptar  el lista  a diferentes  ADTs elementales  basta 
cambiar el nombre del ADT elemental  usado en el lista, lo que  se 
puede hacer con relativa facilidad usando un editor de texto  para 
modificar el programa  fuente  List.pas.   Para  facilitarle  este 
trabajo al programador usuario de TList, en el mdulo List.pas hay 
un recuadro llamado  PARAMETERS  que  tiene  los  nombres  de  los 
identificadores que es necesario cambiar si el elemento  contenido 
en el lista no se llama "Elem".

     Como  las  dos implementaciones  de TList  corresponden a  la 
misma abstraccin,  necesariamente tienen  exactamente las  mismas 
operaciones, aunque  el rendimiento  en cada  operacin puede  ser 
diferente, porque el rendimiento  y los requerimientos de  memoria 
de  cada  implementacin  son  diferentes.   Si  un  programa   es 
implementado usando una  de  las  dos  implementaciones,  entonces 
tambin funcionar con la otra, pero lo que seguramente variar es 
el rendimiento del programa.

     Precisamente   porque  LahoP.pas   y  LahoV.pas  corresponden 
exactamente  a la  misma abstraccin del  ADT TList es  por lo que 
cualquier  programa  que funcione  con una  implementacin tambin 
puede usar la otra.

     Para usar el ADT TList,  el programador usuario del ADT  debe 
copiar uno  de los  dos archivos  LahoP.pas o  LahoV.pas sobre  el 
archivo List.pas.


Operaciones
===========

     Como  ocurre cuando  el programador usa  a la mayora  de los 
ADTs contenedores, las operaciones sobre la lista deben permitirle 
definir sobre cul de todos los nodos del lista desea actuar. Para 
definir una posicin en el lista se usa el tipo de datos PLpos.

     Una variable de tipo PLpos es  un puntero a uno de los  nodos 
de  la  lista.   Como  este tipo  est definido  como parte  de la 
abstraccin  del ADT  lista, entonces un  PLpos es un  tipo que no 
puede manipulado por el programador.  En el caso de LahoP.pas,  un 
PLpos es puntero  Pascal que no  puede ser derreferenciado;  en el 
caso  de LahoV.pas,  un PLpos es  un valor numrico.   Esto quiere 
decir  que si  una variable "p"  es de tipo  PLpos, entonces nunca 
puede ser vlido usar a lo que apunta:

     VAR
       p : PLpos;
     ...
     p^ := ....;   {  ERROR !!! }
     FunProc(p):   { OK }

     El  ADT lista tiene  la mayora de las  operaciones de un ADT 
elemental. Estas operaciones son las siguientes:

     Init(L):     Constructor; inicializa la lista.
     Clear(L):    Limpia la lista.
     Done(L):     Destructor; destruye a la lista.

     Copy(x,y):   Copia el valor de la lista "y" en "x".
     Move(x,y):   Le traslada a "x" el valor de la lista "y".

     Equal(x,y):  Compara el valor de "x" con el de "y".

TList tiene todas las operaciones de un ADT contenedor:

     Empty(L):        Verifica si la lista est vaca.
     Full(L):         Verifica si la lista est llena.
     Count(L):        Cantidad de elementos de la lista.

     Retrieve(L,p):   Transforma una posicin en puntero al valor.
     Locate(L,x):     Busca un valor en la lista.

     La operacin  Retrieve(L,p)   retorna  un  puntero  al  valor 
almancenado  en uno de los nodos  de la lista "L".  Esta operacin 
es  muy importante porque  es la que separa  al contenedor, que en 
este  caso es el  ADT TList, de su  elemento contenido, TElem.  La 
existencia  de esta operacin se  justifica porque muchas veces el 
programador  necesita   escribir  algoritmos   que  manipulan   la 
estructura de la lista, sin  importar cul es su contenido.   Como 
en  esta abstraccin se  separa la estructura del  lista de lo que 
contiene, entonces los algoritmos que slo manipulan la estructura 
de  la lista  no necesitan ser  reprogramados cuando se  cambia el 
tipo  de valor almacenado en  la lista: la operacin Retrieve(L,p) 
los independiza de ese valor.

     Si, por el contrario,  el programador necesita manipular  los 
valores  de los elementos almacenados  en la lista, entonces puede 
accesarlos en dos pasos: primero debe obtener la posicin "p"  del 
nodo de la lista, y luego  puede obtener el valor del nodo  usando 
Retrieve(L,p).

     En  la   implementacin   de   LahoP.pas   se   incluye   una 
implementacin incorrecta de la operacin List.Full(), pues no  es 
siempre posible determinar si hay suficiente memoria dinmica para 
agregarle un nodo ms a la lista sin tratar efectivamente de crear 
un  nuevo  nodo.   Esta  operacin  no  fue  eliminada  porque  su 
implementacin en LahoV.pas es muy simple, y al incluirla entonces 
los programas que funcionan con LahoV.pas puedan ser  recompilados 
con LahoP.pas.  Sin embargo, en general no es posible programar la 
operacin Full() en un contenedor.

     La  operacin  Count(L) siempre  aparece en  los contenedores 
pues retorna el nmero total de elementos; en el caso de la lista, 
retorna el nmero de nodos de la lista.

     Las  operaciones  arriba descritas  son comunes  a todos  los 
contenedores. Lo que realmente define  al ADT lista son las  dems 
operaciones,  las que  pueden ser ejecutadas  eficientemente en la 
estructura de datos de la lista.  La operacin para agregar  nodos 
al lista, al insertarle valores, es Insert().

     Insert(L,p,e)  inserta al elemento "e"  de forma que quede en 
el nodo que est en la posicin "p" de la lista "L".  Por ejemplo, 
para agregar el nodo "x" como  primer elemento de la lista "L"  se 
debe invocar a Insert() de la siguiente forma:

     L = a->b->c->d->e->f

          Insert(L, First(L), x)

                   L = x->a->b->c->d->e->f

     Existe una posicin llamada Endl(L), que marca el final de la 
lista,  pero  que no  contiene elemento  alguno. Para  insertar al 
final  de  la lista  se usa  Insert(L, Endl(L),  x). Sin  embargo, 
Endl()  no  es una  posicin vlida  en la  lista, por  lo que  la 
operacin:
     Retrieve(L, Endl(L))
es siempre incorrecta.

     Para manipular al lista el programador necesita poder obtener 
la posicin de los nodos del lista.  Las operaciones que  retornan 
posiciones en el lista son:

     First(L):  Retorna la posicin del primer nodo de lista.
     Endl(L):   Posicin final de la lista.
     Next(L,p): Posicin del nodo que sigue al nodo "p".
     Prev(L,p): Posicin del nodo que precede al nodo "p".

     En algunas ocasiones el  programador necesita usar una  lista 
como  si fuera un arreglo, aunque  a sabiendas de que la velocidad 
de proeceso  esta  estructura  de  datos  para  estas  operaciones 
decrece  conforme aumenta el tamao  de la lista.  Las operaciones 
tiles para esto son Lpos() y Lind():
     Lpos(L,i): Posicin del i-simo nodo de la lista.
     Lind(L,p): Indice del nodo est en la posicin "p" de L.
Lpos() es el inverso de Lind():
     p = Lind(L, k) <==> k = Lpos(L, p)

     La  operacin  Last(L) no  est defina  para TList.   Esto se 
explica por las siguientes razones, las que por cierto no son  muy 
convincentes:

1) Para insertar al final de la lista el programador debe  invocar 
   a  Insert(L, Endl(L), x) y no  en Insert(L, Last(L), x).  Al de 
   insertar en la ltima posicin vlida de la lista no se inserta 
   al final de la lista:

     L = a->b->c->d->e->f

          Insert(L, Lpos(L, Lind(L, Count(L)), x)

               L = a->b->c->d->e->x->f

   La  explicacin de  esta aparente anomala  es que si  la lista 
   tiene "n" elementos, entonces Insert(L,n,x) deja al elemento  x 
   en la n-sima posicin, que no  es la ltima cuando ya hay  n+1 
   elementos en la lista.

2) Aunque el tiempo de ejecucin  de Last()  es constante para  la 
   implementacin  LahoV.pas,  en la  implementacin LahoP.pas  es 
   necesario recorrer la lista  desde el principio para  encontrar 
   al ltimo elemento.   De  todas  maneras  el  progamador  puede 
   implementar Last(L) como Lpos(L, Count(L)).

     Cualquiera puede objetar la ausencia de Last() de TList  pues 
la segunda razn claramente viola el principio de abstraccin, que 
dice que la implementacin de un ADT debe ser independiente de  su 
especificacin.  Pero la  realidad  es  que  en  la  prctica  los 
(buenos)  programadores slo usarn un ADT si sus operaciones  son 
eficientes: la  eficiencia es  muy importante.   Juzgue el  lector 
cul es  el correcto  proceder desde  el punto  de vista  de quien 
implementa el ADT.

     Al moverse a lo largo de la lista generalmente el  progamador 
comienza el recorrido por el principio de la lista, aunque tambin 
puede  usarse  Locate() para  encontrar un  nodo especfico  en el 
lista.

               L = a->b->c->d->e->f

     @a = First(L)

     @b = Next(L, @a) = Next(L, First(L))
     @e = Prev(L, @f)
     @f = Lind(L, Count(L))
     @f = Prev(L, Endl(L)

     Lpos(L,0) = Endl(L)          Lind(L,Null) = 0
     Lpos(L,1) = First(L) =@a  1= Lind(L,@a) = Lind(L, First(L))

     @a = Locate(L,"a")        @f = Locate(L,"f")

     La operacin que complementa a Insert(L,p,x)  es Delete(L,p), 
que es la que permite  eliminarle nodos al lista.  Esta  operacin 
elimina  de la  lista L al  nodo que est  en la posicin  "p". Al 
eliminar un nodo, "p" sigue apuntando a la misma posicin a la que 
apuntaba, por lo que sin que Delete(L,p) vare el valor de "p"  el 
efecto es que "p" queda apuntando a un nodo diferente:

     L = a->b->c->d->e->f               p = First(L) = @a

          Delete(L, First(L), x)

                L = b->c->d->e->f       p = First(L) = @b

     En  algunas implementaciones la  operacin de borrado incluye 
un  tercer argumento para  que en l Delete()   deje una copia del 
elemento  que  se  elimina  de  la  lista.   El  inconveniente  de 
especificar Delete() de esa manera es que se obliga al programador 
a pagar el  costo de copiar  el elemento cada  vez que se  hace un 
borrado.  Si el  programador necesita ese  valor, lo puede  copiar 
usando   las   operaciones  List.Retrieve(),   y  Elem.Copy()    o 
Elem.Move(), como  se  muestra  a  continuacin  en  el  siguiente 
esqueleto de programa:

     VAR
       pe: PElem;
       e:  TElem;
       p:  PLpos;
     { ... }

     { obtiene el puntero al elemento }
     pe := List.Retrieve(L, p);

     { obtien el valor a eliminar }
     Elem.Move(e, pe^);             { o ==> Elem.Copy(e, pe^) }

     { borra el nodo de la lista }
     DeleteA(L, p);


Modelo
======

     El  modelo del ADT  es un diagrama de  la estructura de datos 
usado para implementarlo.  En todos los libros de texto las listas 
se  representan como estructuras de  datos compuestas de nodos que 
estn  enlazados  por medio  de punteros,  como se  muestra en  el 
siguiente modelo:

          Ŀ   Ŀ   Ŀ
     L> A  > B  > C  >NIL
                

     Sin embargo, en [AHO-83] una lista implementada con  punteros 
siempre tiene un nodo cabezal como se muestra a continuacin:

          Ŀ   Ŀ   Ŀ   Ŀ
     L>#$! > A  > B  > C  >NIL
                   
              /\          /\          /\          /\
              ||          ||          ||          ||
          Lpos(1,L)   Lpos(2,L)   Lpos(3,L)    Endl(L)

     La razn de que  este se  el modelo  de LahoP.pas  es que  la 
implementacin de la operacin Insert() puede expresarse en cuatro 
instrucciones Pascal.  Como lo importante en un libro de texto  es 
transmitir  los  conceptos,  aunque  a  cambio  se  sacrifique  la 
eficiencia o la completitud, resulta conveniente definir la  lista 
usando este modelo. Por eso es que en LahoP.pas una posicin en la 
lista (PLpos)   es un  puntero al  nodo anterior  al que  se desea 
referenciar;  por eso  tambin es necesaria  la operacin Endl(L), 
que realmente apunta al ltimo nodo de la lista.

     Adems, al definir el modelo de LahoP.pas de esta manera,  es 
muy  sencillo  lograr  que  las  operaciones  definidas  sobre  la 
implementacib LahoV.pas  sean compatibles  con las  de LahoP.pas, 
que tiene el siguientes modelo:

          L = (A,B,C)
          Ŀ
          _last A 
              Ĵ
               B 
              Ĵ
            > D 
               Ĵ
                ?  < Sobrante
               Ĵ   
                !  <
          

     Como  el  modelo  de  LahoV.pas es  una arreglo,  entonces es 
natural que una posicin en este  tipo de lista sea un nmero  que 
indica en cul de todos los elementos del vector est el  elemento 
referenciado.   Aunque  el  tipo  PLpos  no  es  un  puntero,   el 
programador  usuario  del  ADT  no  necesita  percatarse  de  esta 
diferencia a menos que a propsito viole el ocultamiento de datos.

     La  abstraccin  que   corresponde  a  las   implementaciones 
LahoP.pas y LahoV.pas  ha sido definida  de forma que  sea posible 
definir las mismas operaciones para ambas implementaciones.   Esta 
manera de  construir ADTs  no es  la ms  adecuada, pues  es mejor 
definir  la  abstraccin de  un ADT  de forma  que tenga  una gran 
usabilidad.  Por eso es que  la abstraccin que corresponde a  las 
implementaciones LahoP.pas y LahoV.pas es poco til, pues ha  sido 
definida de forma  que permita escribir  un libro de  texto usando 
menos  palabras.  [AHO-83]  est escrito para  mostrarle al lector 
cmo manipular  punteros: es  un libro  de Trucos  de Programacin 
(que es el sinnimo vulgar para Estructuras de Datos), pero no  es 
un libro que sirva para estudiar Abstraccin de Datos.

     Como la  implementacin de  Insert() es  la que  determina el 
modelo usado en  LahoP.pas,  es  conveniente  discutir  cmo  est 
implementada esta operacin. En LahoP.pas cada nodo de la lista es 
un  registro Pascal que tiene dos  campos: el de informacin, y un 
puntero al siguiente nodo.  El ltimo nodo tiene el valor NIL, que 
el el puntero nulo en Pascal. Para insertar un nuevo nodo  despus 
de "B" basta crear un nuevo nodo, y enlazar los punteros:

                          Ŀ
   Insert(L, First(L), X)  X   
                          
                            ^   
                               
          Ŀ   Ŀ  Ŀ   Ŀ
     L> ?  > A    > B  > C  >NIL
                   
              /\          /\          /\          /\
              ||          ||          ||          ||
          First(L)    Lpos(2,L)   Lpos(3,L)    Endl(L)

    PROCEDURE Insert(
      {?} VAR L : TList;
      {+}     p : ^TNodo;
      {+} VAR x : TElem
    );
    VAR
      temp : ^TNodo;
    BEGIN { Insert }
      temp := p^.next;
      NEW(p^.next);                { Copiado de AHO-83 }
      Elem.Init(p^.next^.elem);
      Elem.Copy(p^.next^.elem, x);
      pp^.next^.next := temp;
    END;  { Insert }

     Esta implementacin de  Insert()   es  muy  corta;  en  otras 
implementaciones del  ADT TList  es necesario  examinar los  casos 
especiales para insertar el nuevo elemento al principio o al final 
de la lista.  La ventaja de  esta manera de defirnir TList es  que 
cualquier  programador  puede   memorizar  la  implementacin   de 
Insert()  para usarla  cada  vez  que  necesita  una  lista.   Por 
supuesto, es un error  programar  de  esta  manera,  pues  lo  ms 
conveniente  es  programar  el   ADT  TList  una  vez,   depurarlo 
concienzudamente, luego usarlo en muchas aplicaciones diferentes.

     Definitivamente  en  el  ao  1983  todava  no  estaba  bien 
definida la tecnologa  de  Abstraccin  de  Datos.  Sin  embargo, 
aunque la abstraccin de TList que definieron los autores de [AHO- 
83]  es a  duras penas suficiente,  ellos tienen el  mrito de que 
pese a  que todos  tienen una  formacin de  matemticos, son  los 
primeros en tratar de  usar Abstraccin para estudiar  Estructuras 
de  Datos.  Muchos autores posteriores  no han tenido esta visin, 
lo que explica  que muchos textos  recientes ni siquiera  intentan 
usar Abstraccin de Datos.

     Un gran inconveniente de LahoV.pas es que para insertar en la 
lista es necesario mover a  todos los elementos que estn  despus 
de  la posicin  de insercin. Como  Insert() es la  operacin ms 
importante del ADT  TList,  esta  restriccin  hace  prcticamente 
intil a LahoV.pas. Por eso es que estos dos ADTs slo sirven para 
que el estudiante comprenda un poco mejor como implementar listas; 
en la  prctica  es  necesario  definir  a  TList  de  una  manera 
diferente de forma que sea posible implementar las operaciones ms 
importantes con gran eficiencia.


Comportamientos
===============

     Dado que  LahoP.pas  y  LahoV.pas  son  implementaciones  muy 
simples  no se han definido  comportamientos para ellas, aunque no 
es difcil incluirles el comportamiento Insert_using_Move.


Detalles de implementacin
==========================

     En general la parte ms compleja en la implementacin del ADT 
TList es  la manipulacin  de punteros,  pues un  pequeo descuido 
puede  resultar  en  puntero  roto, que  en general  tiene efectos 
impredecibles en el programa.  Precisamente por lo difcil que  es 
manipular  punteros   se  justifica   usar  ADTs,   pues  permiten 
encapsular  su   uso  en   un  mdulo   que  puede   ser  depurado 
independientemente del resto del programa.

     Desgraciadamente en este ADT no se logra una separacin total 
entre el ADT contenedor y su elemento contenido. De hecho, un nodo 
est compuesto de la agregacin del TElem junto con los campos que 
manipula el ADT TList: una mayor modularidad se obtendra si estos 
dos tipos de datos estuvieran separados de alguna manera.  Pero en 
la  prctica todos  los progamadores estamos  acostumbrados a usar 
contenedores que no hacen esta separacin, pues la mayora de  los 
ADTs  que  se  encuentran  en las  bibliotecas de  programas estn 
programadas en forma similar al ADT TList.

     El  principal problema  de mezclar los  campos del contenedor 
con  los  del  elemento  contenidos es  que si  en un  programa se 
necesita usar dos tipos de lista, ser necesario crear dos  copias 
completas  del ADT TList,  una para cada tipo  de elemento.  en el 
caso de LahoV.pas, para crear dos listas de capacidad diferente es 
necesario duplicar todo el cdigo de TList.  Ms an, es imposible 
que  un mismo elemento est en  varios contenedores a menos que el 
contenedor use  punteros a  cada elemento.   En algunos  lenguajes 
modernos, como C++  y ADA, estas  restricciones se solucionan,  de 
forma parcial y poco elegante, con el uso de Tipos Parametrizados, 
llamados  plantillas  o paquetes  genricos.  Existe  una solucin 
alterna,  pero  requiere  de  una  filosofa  de  construccin  de 
programas  bastantes   diferente,   aunque   su   uso   incrementa 
significativamente  la modularidad de los  ADTs as usados, lo que 
se logra con  la  unidad  Binder.pas,  que  se  describe  en  otro 
documento.

     Otra  incomodidad bastante grande  que debe sobrellevar quien 
use el ADT  TList es que  debe definir un  ADT de tipo  TElem para 
usar  el   contendor.   En   muchas  ocasiones   los  programdores 
encuentran   esto   tan  engorroso   que  terminan   cambiando  la 
implementacin  de  TList para  evitar la  proliferacin de  tipos 
TElem.   Esto  ocurre  cuando  se necesita  una lista  simple, que 
contiene nmeros o letras, pues en estos casos el definir todo  un 
ADT para objetos  tan  simples  es  un  trabajo  demasiado  grande 
(aburrido?) para el programador.

     El tipo PLpos en LahoP.pas se implementa como un puntero  que 
apunta al mismo  tipo,  de  forma  que  el  programador  no  puede 
derreferenciarlo y usarlo.  En  la implementacin estos PLpos  son 
covertidos a punteros a nodos, de tipo PNode_RepList.


Bibliografa
============

[1] Aho, Alfred V.; John  E.  Hopcroft; Jefrrey D.  Ullman:  "Data 
    Structures and Algorithms"; 1983. [AHO-83].

[2] Borland; "Turbo Pascal Version 5.5"; 1984.

[3] Liskov, Barbara; Gutag,  John; "Abstraction and  Specification 
    in Program Development"; McGraw-Hill; 1986.

[4] Di Mare,  Adolfo: "Convenciones  de Programacin  para Pascal, 
    Revisin 2"; Reporte tcnico ECCI-01-88, ECCI-UCR, 1988.

[5] Di  Mare, Adolfo:  "Abstraccin de  Datos en  Pascal"; Reporte 
    tcnico PIBDC-01-89, ECCI-UCR, 1991.

[6] Horowitz, E.;  Sahni, S.:  "Fundamentals of  Data Structures"; 
    Computer Science Press; 1982.


               Reportes tcnicos de Adolfo Di Mare
               ===================================

     Los siguientes Reportes Tcnicos, todos confeccionados por el 
mismo autor, describen todos  las implementaciones y algunos  usos 
importantes de los ADTs programados en Turbo Pascal en al  Escuela 
de Ciencias de la Computacin e Informtica, de la Universidad  de 
Costa Rica. 

     Todas estas  implementaciones estn  disponibles en  Internet
por medio de ftp annimo en el directorio:

     http://www.di-mare.com/adolfo/p/src/AHO.zip

     Los derechos de autor  estn reservados  a nombre  del autor,
Adolfo Di Mare.

     El texto de cada Reporte Tcnico se encuentra  en el  archivo
de texto nombrado entre parntesis cuadrados.

[R1]  "Prueba  interactiva  de  ADTs", Reporte  Tcnico ECCI-94-01
      [Archivo UseADT.doc]; Mayo, 1994.

[R2]  "La Implementacin de Elem.pas"; Reporte  Tcnico ECCI-94-02
      [Archivo Elem.doc]; Mayo 1994.

[R3]  "La   Implementacin   de  Rational.pas";   Reporte  Tcnico
      ECCI-94-03 [Archivo Rational.doc]; Mayo 1994.

[R4]  "La Implementacin de Poly.pas"; Reporte  Tcnico ECCI-94-04
      [Archivo Poly.doc]; Mayo 1994.

[R5]  "La    Implementacin  de   ListAHO.pas";  Reporte   Tcnico
      ECCI-94-05 [Archivo Aho.doc]; Mayo 1994.

[R6]  "La Implementacin de List.pas"; Reporte  Tcnico ECCI-94-06
      [Archivo List.doc]; Mayo 1994.

[R7]  "La Implementacin de Tree.pas"; Reporte  Tcnico ECCI-94-07
      [Archivo Tree.doc]; Mayo 1994.

[R8]  "La Implementacin de Heap.pas"; Reporte  Tcnico ECCI-94-08
      [Archivo Heap.doc]; Mayo 1994.

[R9]  "Uso  de  la  unidad Test.pas";  Reporte Tcnico  ECCI-94-09
      [Archivo Test.doc]; Mayo 1994.

[R10] "Manejo  de excepciones  en Turbo  Pascal"; Reporte  Tcnico
      ECCI-94-10 [Archivo Except.doc]; Mayo 1994.
