Reutilización de Contenedores Parametrizables con Lenguajes de Semántica Limitada

      Hasta este capítulo no se han descrito las soluciones propuestas para la parametrización de contenedores: los capítulos anteriores sólo son preámbulo para este.

7.1 Fundamentos

      El trabajo que conduce finalmente a la formalización de las ideas para parametrizar contenedores en Pascal surge después de que el autor trabajó varios años, contando con el apoyo de muchos de sus estudiantes, en la implementación de los tipos abstractos de datos Lista y Árbol (de parametrizar el ADT Arreglo ya se encarga el compilador). La primera versión de estos ADT's es una extensión del trabajo expuesto en el clásico libro de estructura de datos [AHU-84], de los tres teóricos de la computación Alfred V. Aho, John E. Hopcroft y Jeffrey D. Ullman, quienes en su obra especifican e implementan en Pascal de varias maneras el tipo de datos Lista. Sin embargo, sus especificaciones, y por consiguiente sus implementaciones, tienen algunas restricciones que limitan severamente su uso, principalmente porque las listas de [AHU-84] no son independientes de los objetos que contienen. Más aún, la especificación de la lista implementada con vectores es diferente de la lista de punteros, pues sus operaciones tienen interfaces (o encabezados) diferentes.

      En manera alguna disminuye este pequeño detalle la contribución del libro de texto de [AHU-84], que es una excelente obra de estructura de datos, pero que en realidad no aborda el tema de la modularización de programas. Esto motivó al autor a estudiar las técnicas de parametrización: lo importante fue tomar como base la estructura de datos llamada "lista" para a partir de ella implementar el módulo de programación List.pas, que no tiene las deficiencias expuestas en el párrafo anterior. Conforme el autor trabajó y mejoró la implementación de List.pas, descubrió y entendió las deficiencias y limitaciones de las primeras implementaciones, lo que eventualmente le llevó a definir los requerimientos de un contenedor parametrizable (ver sección 8.2).

      Para definir el módulo Lista y Árbol el autor debió definir todas las operaciones para estos contenedores, descritas en el Capítulo 3 "Abstracción en Pascal". Las operaciones elementales son las que necesita usar un contenedor para manipular los objetos que contiene [DiM-94b], razón por la cual en estas primeras implementaciones es obligatorio requerir de cualquier objeto que vaya a estar almacenado en un contenedor, que tenga definidas todas sus operaciones elementales (ver Figura 3.2 y Figura 3.3). Este requerimiento limita severamente la utilidad de los módulos Lista [DiM-94f] y Árbol [DiM-94g], pues lo usual es que un programador implemente sólo las operaciones que necesita para sus objetos: si se le obliga a programar otras operaciones sólo para que su programa compile, lo que se logra, a fin de cuentas, es que no use los contenedores. Por eso, para evitarle trabajo rutinario al programador, C++ genera automáticamente algunas de las operaciones básicas de los objetos: inicialización y copia.

      La otra gran desventaja de las primeras versiones de los contenedores List.pas y Tree.pas es que, cuando se hizo necesario usar una lista para implementar el ADT árbol, fue necesario modificar levemente, por razones de eficiencia, el módulo List.pas.

      La versión inicial de List.pas necesita que el elemento que contiene esté definido en otra unidad (Elem.pas). En la implementación del árbol se usa una lista cuyos elementos son punteros que apuntan a los nodos hijo de cada nodo del árbol. Para reutilizar el módulo List.pas en la implementación de Tree.pas fue necesario crear el módulo Ptr.pas, que tiene todas las operaciones de un ADT elemental, pero cuyo único campo es una variable de tipo POINTER. La eficiencia de la implementación del ADT Árbol disminuyó porque obligatoriamente fue necesario usar las funciones Get_Pointer() y Put_Pointer() para obtener y cambiar el valor de los punteros almacenados en la lista de hijos de cada nodo.

UNIT List;
USES
  Ptr;

TYPE
  TNode =  RECORD
    next : ^TNode;
    ptr  : Ptr.Tptr; 
  END;

  TList = RECORD 
    last : ^TNode;
  END;

UNIT PList;

  { Modificada para NO usar Elem.pas }

TYPE
  TNode =  RECORD     { nodo de la lista }
    next : ^TNode;    { siguiente en la lista }
    pHijo:  POINTER;  { puntero al hijo }
  END;

  TPList = RECORD     { la lista }
    last : ^TNode;;   { puntero al nodo }
  END;

      Para mejorar la eficiencia de la implementación de Tree.pas el autor modificó la implementación de List.pas eliminando completamente la unidad Ptr.pas. De esta manera un nodo en la lista de hijos del árbol ya no tenía un elemento de tipo Ptr.TPtr (que es un tipo definido en la unidad Ptr.pas), sino que se usó directamente el tipo POINTER en el nodo, de forma que los campos de los nodos de la lista modificada eran dos: [pHijo: POINTER y next: Lpos]. El resultado de esta cirugía fue el módulo PList.pas, cuya definición está en la Figura 7.1.

      Entonces, para realizar la implementación del Árbol, por razones de eficiencia fue necesario modificar la implementación del contenedor Lista, lo que claramente violenta el principio de ocultamiento de datos que se necesita para lograr una adecuada modularización. El ADT árbol es un módulo que usa una versión mutada de la lista, lo que claramente muestra que el módulo List.pas realmente no es un módulo reutilizable, porque cuando se necesita usar la lista en una aplicación en que la eficiencia tiene una gran relevancia, el programador se ve obligado a alterar la implementación de List.pas, lo que choca frontalmente con el ideal de reutilización de módulos. La reutilización es una cualidad de los módulos que debe liberar al programador de la obligación de estudiar los detalles de implementación de la biblioteca de programas que usa, por lo que no es reutilizable un módulo cuya implementación deba ser cambiada para una aplicación específica.

      Las primeras implementaciones de los contenedores Lista y Árbol no son realmente parametrizables, y sólo sirven para hacer pequeños programas de ejemplo en ambientes académicos. Si en un mismo programa se usan dos listas, entonces hay que crear dos copias del código fuente de List.pas, y para cada una de ellas crear el módulo Elem.pas respectivo [DiM-94b]; este trabajo debe hacerlo manualmente el programador, sin asistencia del compilador Pascal. Estas primeras versiones de los contenedores fueron utilizadas por estudiantes, quienes los descartaban después de ganar el curso, por lo incómodo que resulta manejarlos. Además, como estos módulos fueron programados usando la versión 5.0 de Turbo Pascal, no usan programación por objetos, hecho que para algunos es suficiente para rechazarlos.

      Al adoptar OOP surgió, de forma natural, la idea de usar herencia para incorporar las operaciones básicas de un ADT elemental, y así liberar al programador de la responsabilidad de implementarlas sólo para que el compilador acepte el programa. Pero al usar herencia resultó necesario crear un módulo de ayuda al contenedor que lo asocie con las operaciones del ADT elemental que contiene. Así es como nace el módulo Binder.pas para registrar con una instancia del contenedor las operaciones del elemento que contiene (Bind se traduce del inglés como "ligar" o "atar"). Si por alguna razón el elemento no tiene alguna de las operaciones, entonces el ligador Binder.pas le provee al contenedor una operación por defecto. Por ejemplo, cuando en la implementación del contenedor se necesita copiar a uno de sus elementos entonces se invoca la operación Binder.Copy(), la que se encarga de invocar la operación Elem.Copy() si esta existe y, si no, por defecto Binder.Copy() copia bit por bit el contenido del elemento. Otro beneficio que resultó al adoptar OOP es que se pudo parametrizar el uso de iteradores gracias al polimorfismo inherente a OOP, lo que representó una ganancia grande y no prevista.

      La importancia del Capítulo 4 "Operaciones Básicas" en este trabajo radica precisamente en que ahí se definen cuáles son las operaciones que en general los contenedores necesitan para manipular los elementos que contienen. Es esta categorización de las operaciones elementales la que permite luego proveer en Binder.pas operaciones por defecto para que el contenedor manipule sus elementos.

      Binder.pas es un módulo que libera al programador del contenedor del elemento contenido, para que se pueda concentrar en programar los algoritmos esenciales del contenedor. La gran ventaja de usar Binder.pas es que, para parametrizar un contenedor, basta crear una nueva instancia del objeto TBinder que describe los elementos que el contenedor almacena. Luego se asocia la instancia del contenedor con este ligador, como se muestra en la Figura 7.2. De esta forma se evita duplicar el código que implementa el contenedor, pues toda la información necesaria para manipular el ADT elemental está en el ligador TBinder. Tal vez Binder.pas debería llamarse "Element.pas", pues de esta forma la sintaxis para usar las operaciones desde el contenedor sería más sencilla: en lugar de invocar Binder.Copy() el programador usaría ELement.Copy(); o sea, se recalcaría el hecho de que Binder.pas sirve para describir los elementos. No se ha cambiado el nombre porque la invocación Element.Copy() surge luego al implementar el tipo TBinder con OOP.

      Como ocurre con los dobleces de un "Clip", en la implementación de Binder.pas se conjugan varias técnicas de una forma adecuada. Se usa OOP para abreviar la cantidad de código que hay que escribir y para permitirle al programador referirse cómodamente a los objetos. El polimorfismo de OOP permite enmascarar el uso de punteros a funciones con el manejo de funciones virtuales: estos punteros a funciones están contenidos en la instancia del ligador de tipo TBinder que describe el elemento del contenedor.

  L ──>─┐
        │
        v
 ┌────────┬───┐   ┌────────┬───┐   ┌────────┬───┐
 │ elem_1 │ *─┼──>│ elem_2 │ *─┼──>│ elem_3 │ *─┼─> NIL
 └────────┴───┘   └────────┴───┘   └────────┴───┘
   elem    next

      Tal vez la idea más importante que ha permitido construir el módulo Binder.pas es el descubrimiento del autor de que para implementar un contenedor, lo que se necesita es manipular "enlaces" en el contenedor, y no los "elementos" que están en él almacenados. En la Figura 7.3 y la Figura 7.4 se muestra esta dicotomía. En la primera de ellas está una lista dibujada tal como siempre aparece en los libros de texto: un nodo apunta al siguiente. El dibujo de la otra muestra la misma lista, pero lo que aparece encadenado son los campos de enlace contenidos en cada nodo y no los nodos como en el primer dibujo.

  L ─────>─┐
           │ ┌──────────────┐ ┌──────────────┐ ┌─> NIL
           v │              v │              v │
 ┌────────┬──┼┐   ┌────────┬──┼┐   ┌────────┬──┼┐
 │ elem_1 │ *┘│   │ elem_2 │ *┘│   │ elem_3 │ *┘│
 └────────┴───┘   └────────┴───┘   └────────┴───┘

      Los algoritmos para implementar un contenedor no dependen de las cualidades del elemento contenido, sino más bien en la habilidad del programador para manipular los Campos de enlace que encadenan unos nodos con otros (otro nombre para estos campos es campos de ligamen o, simplemente, ligámenes). Si se implementa el contenedor suponiendo que enlaza únicamente los campos de ligamen que necesita, no resulta necesario saber qué es el elemento contenido. Curiosamente, estas dos percepciones alternativas del contenedor son sintácticamente equivalentes cuando se implementa el programa, pues para accesar el campo "next" del nodo en los casos correspondientes a la Figura 7.3 y la Figura 7.4, se usa la misma sintaxis: "p^.next", donde "p" es un puntero al nodo. De hecho, "p" es una posición en la lista, de tipo PLpos. Por una fortuita y beneficiosa casualidad no hay diferencia sintáctica al referirse a los campos de enlace del contenedor.

      En el diagrama de la Figura 7.4 no se resalta un hecho muy importante: el campo de enlace, que se llama "next" en este caso, no le pertenece al elemento que ha sido almacenado en el contenedor, sino que más bien le pertenece al contenedor, que es el encargado de manipularlo. Desde esta óptica, el elemento simplemente tiene un campo que le permite enlazarse en el contenedor: por eso, al implementar las operaciones del elemento, no es necesario saber cómo está hecho el campo de enlace.

      Para agregar un elemento a una lista parametrizada por medio de Binder.pas se usa la siguiente sintaxis Pascal:
      L.LinkTo(p, elem.link);
en donde "L" es la lista y "elem" es el elemento que se enlaza a ella en la posición "p". En contraposición, para usar la operación de una lista no parametrizable, como la que corresponde a las operaciones definidas en la sección 3.4, se debe usar una operación similar a la definida en la sección 5.6:
      Insert(L, p, elem);

      En este caso la operación Insert() deberá copiar (o trasladar invocando Elem.Move()) todo el objeto "elem" a uno de los nodos que internamente usa la lista, en tanto que la operación TList.LinkTo() sólo tiene que manipular los campos de enlace que ya contiene el elemento, por lo que puede realizar su trabajo con mayor rapidez.

      Si fuera necesario introducir en la lista "LL" otro tipo de elemento, por ejemplo una "casa", la forma de hacerlo es usar la misma operación de la lista, pero con otro argumento:
      L.LinkTo(pL, elem.link);
      LL.LinkTo(p, casa.link);
Este ejemplo muestra que, efectivamente, las listas de tipo "TList" son parametrizables, pues para agregarles elementos de tipo diferente se usa la misma operación.

      La parametrización se logra implementando el contenedor de forma que manipule los campos de enlace. Estos campos de enlace pueden estar en cualquier elemento, sea este "TElem", "TCasa", o cualquier otro tipo de datos. Al implementar un contenedor como un módulo que manipula los campos de enlace, inmediatamente el módulo es parametrizable, pues no depende de los elementos que contiene. Más aún, como se muestra con el ejemplo descrito en los párrafos anteriores, nunca es necesario duplicar código alguno porque desde el contenedor no se accesan directamente los otros campos del elemento contenido: sólo se usa directamente el campo de enlace. Este Método para parametrizar es muy simple, pero seguramente la gente no lo ha descubierto debido a la mala costumbre de dibujar los contenedores como se muestra en la Figura 7.3, mezclando tres cosas que deben estar separadas:

1. El contenedor.
2. El elemento contenido.
3. El campo de enlace que pertenece al contenedor, encargado de manipularlo, aunque físicamente aparece dentro del elemento contenido.

      Al separar estas tres componentes y retribuirle a cada una de ellas la participación que debe tener en la arquitectura del contenedor, se obtiene un módulo parametrizable. ¡Tan simple como doblar un alambre para obtener un "Clip"!

      Al realizar la implementación de los contenedores Lista y Árbol se hizo evidente que varias de las operaciones del contenedor no necesitan ninguna de las operaciones del elemento contenido. Por ejemplo, la operación:
      TList.LintTo(p, elem.link);
sólo necesita manipular el campo de enlace "elem.link" y no necesita tocar el elemento "elem", mientras que la operación "TList.Copy()" sí necesita copiar elementos, invocando "Elem.Copy()", para cada uno de los elementos del contenedor. Por eso se pueden clasificar en dos grupos las operaciones del contenedor:

• Operaciones fundamentales: Son aquellas operaciones del contenedor que no necesitan manipular el elemento contenido. Por ejemplo, las operaciones Emtpy(), Full(), LinkTo(), UnLink(), First(), Next(), etc.
        En la especificación e implementación de estas operaciones nunca se requiere ni el elemento ni las operaciones de Binder.pas que sirven para accesarlo. Las operaciones fundamentales se pueden implementar para cualquier contenedor sin recurrir al módulo Binder.pas: basta hacer la separación de funciones como se muestra en la Figura 7.5.

• Operaciones adicionales: Son las que deben manipular el elemento, como Copy(), Equal(), Load(), Store().
        Estas son las operaciones que requieren del módulo de ligamiento Binder.pas para ser implementadas, pues por medio de este módulo se pueden accesar las operaciones elementales del objeto contenido en el contenedor (Figura 3.3).

TYPE
  TList = OBJECT (TObj)
  PRIVATE
    _first: ^TLlink;     { puntero al primer nodo }

  PUBLIC
    PROCEDURE Init;      { Operaciones Fundamentales }
    PROCEDURE Done;

    FUNCTION  Empty : BOOLEAN;
    FUNCTION  Count : WORD;

    FUNCTION  First         : PLlink;
    FUNCTION  Last          : PLlink;
    FUNCTION  Next(p:PLlink): PLlink;
    FUNCTION  Prev(p:PLlink): PLlink;

    PROCEDURE LinkAfter(   p: PLlink; VAR  x: TLlink);
    PROCEDURE UnLinkAfter( p: PLlink; VAR px: PLlink);

    { Operaciones adicionales }

    PROCEDURE Clear( VAR Element : TBinder );
    PROCEDURE Erase( VAR Element : TBinder );

    PROCEDURE Copy(  VAR o : TList; VAR Element: TBinder );
    PROCEDURE Clone( VAR p : PList; VAR Element: TBinder );
    PROCEDURE Move(  VAR o : TList; VAR Element: TBinder );
    PROCEDURE Swap(  VAR o : TList; VAR Element: TBinder );

    FUNCTION  Equal( VAR o : TList; VAR Element: TBinder )
              : BOOLEAN;

    PROCEDURE DeleteAfter(p : PLlink; VAR Element: TBinder );
    PROCEDURE Delete_All(             VAR Element: TBinder );
    FUNCTION  Locate(     VAR x : TLlink; VAR prv: PLlink;
                                      VAR Element: TBinder )
              : PLlink;

    PROCEDURE Load (   VAR F : FILE; VAR Element: TBinder );
    PROCEDURE Store(   VAR F : FILE; VAR Element: TBinder );

    PROCEDURE Print(   VAR F : TEXT; VAR Element: TBinder );
    PROCEDURE Read(    VAR F : TEXT; VAR Element: TBinder );
  END; { TList }

      La Figura 7.5 es un extracto de la definición del contenedor lista, en la que aparecen tanto las operaciones fundamentales y como las adicionales. Es fácil distinguirlas unas de otras, pues las adicionales tienen un argumento llamado "Element" (parte inferior de la figura), que sirve para manipular los valores almacenados en el contenedor.

UNIT List;
USES
  Binder;

TYPE
  PLlink = ^TLlink;
  TLlink =  OBJECT (Binder.TContLnk) 
    PRIVATE
      next : ^TLlink;
  END;

UNIT Binder;



TYPE
  PContLnk = ^TContLnk; 
  TContLnk =  OBJECT
  PUBLIC
    PROCEDURE Init;
    PROCEDURE Done;
  END;

      Al definir cualquier contenedor también hay que especificar el campo de enlace que usará para ligar todos sus elementos. En la Figura 7.6 está definido el tipo "TLlink" que sirve como campo de enlace para la lista. Este tipo es derivado del tipo TContLnk definido en la unidad Binder.pas.

      En las secciones que siguen se describen las implementaciones del módulo ligador Binder.pas y los contenedores parametrizables Vector.pas, List.pas y Tree.pas.

7.2 La unidad Binder.pas

      El módulo Pascal Binder.pas exporta varios tipos que sirven para implementar contenedores polimórficos. Aunque es posible implementar Binder.pas sin usar OOP, los escollos que hay que sortear para lograrlo no justifican el esfuerzo realizado. La única justificación para emprender esta empresa sería darle apoyo al lenguaje C (no a C++) [DiM-99b], pero como ya C++ alcanzó en popularidad a C, ya no se justifica el sacrificio que representa no usar OOP en la implementación de Binder.pas. Los tipos que el módulo Binder.pas exporta son los siguientes:

• TBinder: Contiene campos que describen el elemento contenido en algún contenedor. En este trabajo a los objetos de tipo TBinder también se les llama Ligadores porque son los que asocian un contenedor parametrizable con el elemento que contiene. Los ligadores sirven para que el contenedor pueda manipular sus elementos.
• TObj: Este tipo no contiene campos, por lo que la operación System.SizeOf(TObj) siempre retorna el valor cero. Sirve para definir todas las operaciones de un ADT elemental. Junto a Binder.TObj se define también el tipo PObj, como un puntero a un TObj. Por convención, la primera letra de todos los nombres de tipos siempre es una "T" (TObj), y el nombre del puntero correspondiente al tipo comienza con una "P" (PObj) [DiM-88a].
• TContLnk: Este tipo tampoco contiene campos, y sirve para que el programador de un ADT contenedor derive de él los tipos que necesita para definir los campos de enlace que deben estar dentro de un ADT elemental que vaya a ser almacenado en el contenedor.

      A diferencia de lo que ocurre con otras bibliotecas de programas, para usar el módulo Binder.pas no es necesario derivar todos los tipos de TObj, que es una clase abstracta, o sea, es un tipo que nunca debe instanciarse definiendo variables de tipo TObj. Por eso, en la implementación todas las operaciones de Binder.TObj, lo que hace es generar un error en tiempo de ejecución. TObj existe como un recordatorio para el programador cliente de cuáles son las operaciones básicas de un ADT.

      En contraposición a lo que ocurre con el tipo TObj, todos los campos de enlace definidos para un contenedor parametrizado por medio de Binder.pas deben ser derivados del tipo TBinder.TContLnk. Por ejemplo, los campos de enlace List.TLlink y Tree.TTlink que se usan en la implementación de los ADT's parametrizables lista y árbol son derivados de TContLnk. Además, las operaciones TBinder.Link_to_PObj() y TBinder.Obj_to_PLink(), usadas para acceder al elemento desde su campo de enlace, usan argumentos de tipo TObj y TContLnk.

      Las operaciones del tipo Binder.TObj son las de un ADT elemental: TObj.Init(), TObj.Done(), etc. En cuanto a TContLnk, como este es un tipo que tiene un uso muy especializado (servir de campo de enlace en un contenedor), sólo tiene dos operaciones accesibles al programador cliente: TContLnk.Init() y TContLnk.Done() (ver Figura 7.6).

      Cada TBinder describe la conexión entre un contenedor y el campo de enlace almacenado dentro de sus elementos. Por eso en un mismo programa no debe haber más instancias de TBinder que el número de campos de enlace definidos para objetos que serán almacenados en algún contenedor.

      Es usual que varias instancias del mismo contenedor compartan una sola instancia de TBinder, lo que ocurre, por ejemplo, cuando en el mismo programa se usan varias listas de personas. También es usual que dos instancias del mismo contenedor usen instancias de TBinder diferentes, lo que ocurre, por ejemplo, si en el mismo programa se necesita usar una lista de personas, -TPerson-, y otra de caracteres, -Tchar-. En general, contenedores de diferente tipo, -TList, TTree-, no comparten la misma instancia del ligador TBinder, pues generalmente usan campos de enlace diferentes, con cualidades distintas. Por eso una lista y un árbol no comparten el mismo ligador.

      En cierto modo, una instancia de TBinder es equivalente a la Tabla de Métodos Virtuales (VMT: Virtual Method Table) de un objeto, pues contiene punteros a los métodos del elemento que necesita el contenedor para manipularlo. Sin embargo, en un TBinder también hay que incluir otra información, como la localización del campo de enlace dentro del elemento, o sea, el sitio exacto en que aparece el campo de enlace del contenedor en todos los elementos que están ligados a él.

      TBinder tiene una enorme cantidad de operaciones y de campos. Los campos TBinder.container, TBinder.element y TBinder.link sirven para almacenar el nombre del contenedor que usa al TBinder, el nombre del elemento descrito por el ligador y el nombre del campo dentro de ese elemento. Estos campos son útiles principalmente si se usa la operación de bitácora de Binder.pas para saber qué operaciones del elemento se ejecutan. La bitácora se lleva en el archivo de texto a que apunta el campo TBinder._logF.

PROCEDURE TBinder.Define(       { EXPORT }     { ADH }
    { nombres de los objetos }
  {+}     nc      : STRING;     { contenedor }
  {+}     ne      : STRING;     { elemento }
  {+}     nk      : STRING;     { enlace }

    { descripción del elemento contenido }
  {+} VAR obj;                  { TElem }
  {+}     sz_obj  : WORD;       { SizeOf(TElem) }

    { constructores y destructores }
  {+}     p_cnstrc: POINTER;    { @TElem.CONSTRUCTOR }
  {+}     p_dstrc : POINTER;    { @TElem.DESTRUCTOR }
  {+}     p_init  : POINTER;    { @TElem.Init }
  {+}     p_done  : POINTER;    { @TElem.Done }
  {+}     type_of : POINTER;    { TypeOf(TElem) }

    { descripción del ligamen del elemento }
  {+} VAR obj_link: TContLnk;   { TElem.link }
  {+}     sz_link : WORD        { SizeOf(TElem.link) }
);

      La operación TBinder.Define(), cuyos parámetros se muestran en la Figura 7.7, es la que se debe invocar para definir el elemento contenido en el contenedor. Esta operación tiene muchos argumentos sin tipo y básicamente lo que hace es definir las principales cualidades físicas del elemento. Para definir el elemento es necesario describirle las siguientes características:

• Nombres de los objetos: En los argumentos "nc", "ne" y "nk" de TBinder.Define() el programador cliente debe poner una hilera con el nombre del identificador Pascal que ha usado en su programa para definir el contenedor ("TList_TcharL"), el elemento contenido ("TcharL") y el nombre del campo de enlace dentro del elemento ("linkL"). Estos datos no son necesarios para el correcto funcionamiento del contenedor, pero sí sirven cuando se activa la operación de bitácora de la unidad Binder.pas, y además son una forma simple de documentar el código Pascal.
        TBinder.Define() usa los argumentos "nc", "ne" y "nk" para darles valor a los campos de tipo hilera TBinder.container, TBinder.element y TBinder.link. Como estos campos en TBinder son públicos, otra manera de lograr el mismo cometido es cambiarlos directamente en la instancia de TBinder; sin embargo, este estilo de programación es menos recomendable pues es conveniente que toda la definición del TBinder esté en un solo lugar: en donde se invoca TBinder.Define().

• Descripción del elemento contenido: Es necesario definir el tamaño del objeto, para lo que se usan los dos argumentos "obj" y "sz_obj". Lo usual es que estos valores se obtengan usando una transferencia de tipos como la siguiente:
        BcharL.Define(... PcharL(NIL)^, SizeOf(TcharL)...);
  en donde el tipo "PcharL" es un puntero al tipo "TcharL".

• Constructores y destructores: Los argumentos "p_cnstrc", "p_dstrc", "p_init" y "p_done" son punteros al constructor y destructor del elemento.

• Descripción del ligamen del elemento: Además de definir el tamaño del elemento contenido, es necesario también definir el tamaño del campo de enlace del contenedor y en qué parte del elemento aparece el campo de ligamen del contenedor.

      Cuando un objeto tiene métodos virtuales, Turbo Pascal requiere que se le inicialice por medio de un método especial que ha sido declarado con la palabra reservada CONSTRUCTOR, el que se encarga de poner un puntero desde la instancia del objeto a su VMT. Por esta razón Turbo Pascal invoca de forma diferente un método declarado como CONSTRUCTOR que uno declarado simplemente como PROCEDURE.

      Para informarle al módulo TBinder que el método del elemento contenido Elem.Init() fue declarado como CONSTRUCTOR, el valor del argumento "p_cnstrc" debe ser un puntero a Elem.Init() y el valor de su argumento pareja "p_init" debe ser NIL. Si, por el contrario, Elem.Init() fue declarado como PROCEDURE, entonces el argumento "p_cnstrc" debe ser NIL y "p_init" debe ser la dirección de Elem.Init(). Esto mismo ocurre con los destructores y la palabra reservada DESTRUCTOR. Entonces, en cada una de las parejas de parámetros:
      1.  (p_init, p_cnstrc)
      2.  (p_done, p_dstrc)
sólo uno de los dos puede ser diferente de NIL. Por ejemplo, si "p_init" es NIL, "p_cnstrc" debe apuntar al constructor del objeto. El programador cliente siempre está obligado a definir un constructor y un destructor para sus objetos y, si no lo hace, no podrá usar contenedores parametrizados con Binder.pas. En el código Pascal, lo usual es que aparezcan en dos renglones los valores para estos argumentos como sigue:

@TcharL.Init,   NIL,         { OJO: Debe haber sólo un }
 NIL,          @TcharL.Done, {      NIL por renglón    }
        TypeOf( TcharL ) 

      Como la forma de invocar una función virtual, o sea, un método polimórfico, es diferente de la invocación a una operación que no es polimórfica, entonces en la invocación de TBinder.Define() es necesario incluir el argumento "type_of", que se obtiene al invocar la función de biblioteca TypeOf(), que retorna un puntero a la tabla de funciones virtuales (VMT) del objeto. Binder.pas usa esta información en el momento de invocar los métodos del elemento del contenedor.

      La función TypeOf() sólo se puede aplicar a objetos que tengan una VMT, o sea, a aquellos que tienen métodos virtuales, pues de lo contrario el compilador emite un error de compilación. Para aquellos objetos que no tienen métodos virtuales, el valor del argumento "type_of" debe ser NIL. Desafortunadamente en Turbo Pascal no ocurre que la invocación a TypeOf(OBJ) retorne "NIL" para aquellos objetos que no son polimórficos, o sea, que no tienen funciones virtuales.

      El argumento "sz_obj" define el tamaño del elemento. En conjunto, los argumentos "obj" y "obj_link" sirven para obtener el desplazamiento a partir del principio del objeto "obj" en el que aparece el campo de enlace "obj_link". En el parámetro "sz_link" el programador debe definir el tamaño del campo de enlace. En la Figura 7.8 se puede ver la interrelación de estos campos.

      Además del parámetro "obj" descrito anteriormente, en Binder.pas se usan los valores de los argumentos "obj_link" y "sz_link" para determinar el tamaño del campo de enlace y el lugar en que aparece dentro del ADT elemental del contenedor.

      Binder.pas usa estos campos más que todo en las operaciones que por defecto provee. Por ejemplo, si el programador no ha definido la operación de copia de elementos TElem.Copy(), Binder.pas provee una que hace la copia bit por bit. Al hacer esta copia es necesario que Binder.pas se salte al campo de enlace porque no le pertenece al elemento, sino que le pertenece al contenedor, por lo que Binder.pas necesita saber dónde está ese campo y qué tamaño tiene.

      Para ayudar al programador a definir bien sus ligadores, la implementación de TBinder.Define() tiene una gran cantidad de verificaciones de integridad de sus argumentos. Esto ayuda a evitar fallas en el programa, pues muchas veces es difícil para el programador identificar las incongruencias en los argumentos de TBinder.Define() porque tiene muchos parámetros.

TYPE
  TcharL =  OBJECT
    { caracter que puede estar en una lista }
    linkL: List.TLlink;   { enlace de TList }
    c    : CHAR;          { información }

    CONSTRUCTOR Init;
    PROCEDURE   Done;

    PROCEDURE Copy (VAR o:TcharL);

    PROCEDURE Read (VAR F: TEXT);
    PROCEDURE Print(VAR F: TEXT); VIRTUAL;
  END; { TcharL }

      La Figura 7.9 muestra la definición del tipo TcharL, que contiene un caracter ("c") que puede estar ligado dentro de una lista. Para esto incluye el campo de enlace de la lista "linkL", que es de tipo "List.TLlink" (derivado de TBinder.TcontLnk). El objeto TcharL no se ha derivado del objeto genérico Binder.TObj. Como las operaciones elementales que el programador necesita usar para TcharL son TcharL.Copy(), TcharL.Read() y TcharL.Print(), sólo esas están redefinidas en TcharL.

      Siempre que se usa un contenedor parametrizable es necesario especificar tanto el constructor como el destructor para el elemento contenido. En otras palabras, cualquier objeto "TElement" que vaya a estar almacenado en un contenedor parametrizable debe tener definidas las operaciones "TElement.Init()" y "TElement.Done()". Conviene adoptar costrumbres que conduzcan a producir programas correctos, por lo que no es adecuado que los programadores usen objetos que no necesitan de estas operaciones. Por esta razón este requerimiento no debe verse como una incomodidad, sino más bien como una sana práctica de programación: nunca es correcto usar variables que no estén debidamente inicializadas.

 CONSTRUCTOR TcharL.Init; 
 BEGIN
   c := CHR(0);
   linkL.Init;
 END;  { TcharL.Init }

 PROCEDURE TcharL.Done; 
 BEGIN
   linkL.Done;
 END;  { TcharL.Done }

      Aunque el campo TcharL.Llink no le pertenece a TcharL, pues es el campo de enlace administrado por la lista, el programador cliente sí debe inicializarlo y destruirlo en el constructor y destructor de TcharL. Por eso en la implementación de TcharL.Init() y TcharL.Done() deben aparecer invocaciones a TLlink.Init() y TLlink.Done(), que son el constructor y destructor del campo de enlace del ADT genérico lista, como se muestra en la Figura 7.10.

      Es posible implementar Binder.pas de manera que el programador cliente del contenedor no tenga la obligación de inicializar y destruir el campo de enlace del contenedor cuando implementa el constructor y destructor de su elemento, pero al hacerlo se complica el uso de la parametrización. Como no es prudente que el programador use objetos que tengan campos que no ha inicializado, o que olvide destruir pedazos de los objetos que ya no usará más, esta posibilidad ha sido desechada, pues no es conveniente que quien implementa una biblioteca de programas fomente prácticas que son nocivas para la construcción de módulos. Además, para descargar al programador cliente del contenedor de la responsabilidad de invocar al constructor y destructor del campo de enlace, es necesario pasarle a TBinder.Define() dos argumentos adicionales, los punteros al constructor y destructor del campo de enlace del contenedor, para que la implementación por defecto de Init() y Done() pueda inicializar y destruir el campo de enlace, lo que tornaría más complicado el uso de Binder.pas.

      El programador cliente del contenedor nunca debe usar la operación TElement.Clear() para su ADT elemental, pues esta operación debería reinicializar el campo de enlace, posiblemente destruyendo la invariante del contenedor. Cuando una instancia ya esté enlazada a un contenedor, al borrarle su valor con TElement.Clear() es necesario que quede exactamente como la dejó TElement.Init() justo después de inicializarla, como reza la especificación de Clear(). Pero en su génesis, la instancia no estaba enlazada a contenedor alguno, por lo que limpiarla con TElement.Clear() necesariamente implica desligarla del contenedor, lo que debe hacerse únicamente invocando una operación del contenedor, jamás una del elemento contenido. Por eso tampoco tiene sentido que el programador cliente invoque la operación TContLnk.Clear() (por eso no fue definida en la Figura 7.6). Al implementar un contenedor no se necesita invocar TContLnk.Clear(); a lo más que se llega es a invocar el destructor TContLnk.Done() y, como se dijo anteriormente, esto sí se hace desde el de TElement.Done().

      Como ningún objeto TElement que será enlazado en un contenedor parametrizado con Binder.pas puede tener una operación TElement.Clear(), lo que cabe es crear una operación, llamada TElement.Erase() por supuesto, que limpie el elemento, pero evitando cambiar el valor almacenado en el campo de enlace, que le pertenece al contenedor, y no puede método alguno del elemento contenido examinarlo o cambiarlo.

TYPE
  BcharL: Binder.TBinder;
BEGIN {<<< BcharL >>>}
  BcharL.Construct;
  BcharL.Define(
    { nombres de los objetos }
    'TList_TcharL', 'TcharL', 'linkL',

    { descripción del elemento contenido }
    PcharL(NIL)^,      SizeOf( TcharL ),

    { constructores y destructores }
    @TcharL.Init, NIL,           { OJO: sólo un NIL }
     NIL,        @TcharL.Done,   {      por renglón }
          TypeOf( TcharL ),      { ==> si tiene VMT }

    { descripción del ligamen del elemento }
    PcharL(NIL)^.linkL, SizeOf((PcharL(NIL)^.linkL))
  );
  BcharL.Bind_Copy(  @TcharL.Copy  );
  BcharL.Bind_Read(  @TcharL.Read  );
  BcharL.Bind_Print( @TcharL.Print );

  BcharL.Destruct;
END; {<<< BcharL >>>}

      En la Figura 7.11 está la invocación a la función TBinder.Define() para el ligador BcharL, que es el que describe el enlace entre una lista parametrizada de tipo TList, y el elemento de tipo TcharL declarado en la Figura 7.9. Como el constructor del objeto TcharL está declarado con la palabra reservada CONSTRUCTOR, el argumento que corresponde al parámetro "p_init" es NIL, mientras que el que corresponde a "p_cnstrc" es un puntero al método TcharL.Init(). Por el contrario, como el destructor de TcharL no está definido usando la palabra DESTRUCTOR, el argumento que corresponde al parámetro "p_dstrc" es NIL, mientras que el que corresponde a "p_done" tiene por valor el puntero al método TcharL.Done().

      Como todo objeto de tipo TcharL tiene métodos virtuales, hay que almacenar en el ligador el puntero a su VMT, lo que se logra pasándole en el parámetro "type_of" el valor "TypeOf(TcharL)" al método TBinder.Define().

      Para obtener los valores de los argumentos que corresponden a los parámetros "obj", "obj_link" y "sz_link" se usa una codificación un tanto alambicada. La expresión "PcharL(NIL)^.Llink" transforma el puntero "NIL" en un puntero a un objeto de tipo "TcharL", y luego se accesa el campo ".linkL" en ese objeto. Como TBinder.Define() sólo necesita calcular el desplazamiento desde el principio del objeto en donde está el campo de enlace del contenedor, aunque el puntero NIL ha sido derreferenciado, en ningún momento se usa el valor del objeto, ni tampoco se altera lo almacenado en esa posición de memoria, lo que evita que se produzca un error de acceso de memoria. En otros lenguajes es posible que el compilador no permita hacer las cosas de esta forma, pero, si ese fuera el caso, seguramente el lenguaje proveería otra manera de lograr el mismo cometido: usar aritmética de punteros para averiguar el desplazamiento desde el inicio del elemento en el que se encuentra el campo de enlace. Por ejemplo, en C se puede usar la macro offsetof(). Por eso, en C el programador cliente no tendría que declarar una variable de tipo TcharL para invocar TBinder.Define().

      Las operaciones TBinder.Bind_Read(), TBinder.Bind_Print() y TBinder.Bind_Copy() que se usan en la Figura 7.11 sirven para asociar las operaciones TcharL.Read(), TcharL.Print() y TcharL.Copy() con el ligador BcharL. Por ejemplo, si desde una lista que está ligada a "BcharL" se invoca la operación "Element.Read()", Binder.pas transformará esa invocación en un llamado al método TcharL.Read().

      El tipo del parámetro de las funciones TBinder.Bind_????() es "POINTER", lo que implica que como argumento se puede usar un puntero a cualquier cosa. Esto obliga al programador cliente del contenedor a ser sumamente cuidadoso al usar estas operaciones, pues un error al darles valor a estos argumentos puede ser muy difícil de detectar.

PROCEDURE TList.Print(            { EXPORT-ADH }
  {?} VAR F       : TEXT;   { archivo a grabar }
  {+} VAR Element : TBinder { ligador }
);
{ RESULTADO
  Imprime el contenido de la lista en "F". }
VAR
  p: ^TLlink;         { i.e. PLlink }
BEGIN { TList.Print }
  p := SELF._first;
  WHILE p <> NIL DO BEGIN
    Element.Print(p^, F);
    p := p^.next;
    Write(F, ' ');
  END;
END;  { TList.Print }

      La Figura 7.12 es una versión simplificada de la implementación de la operación parametrizada TList.Print(), que es una operación adicional de la lista, pues necesita usar el valor almacenado en los elementos de la lista (para imprimirlo), por lo que también recibe como parámetro un ligador, llamado "Element", de tipo Binder.TBinder.

      Para recorrer los elementos de la lista se usa la variable "p", que es una posición en la lista (PLpos), de tipo "TLlink", implementado como un puntero a uno de los nodos de enlace de la lista. Para imprimir cada uno de los elementos de la lista se debe invocar el método de impresión del elemento almacenado en la lista, lo que se hace a través del ligador que la operación TList.Print() recibe como segundo argumento. Como el nombre del ligador es "Element", para imprimir el valor del elemento que está almacenado en la posición "p" de la lista, se usa la cómoda sintaxis:
      Element.Print(p, F)

      Al realizar un examen superficial de la implementación de TList.Print() en la Figura 7.12 es difícil notar que la lista es parametrizable: de hecho, este código es casi exactamente el mismo código que es usual encontrar en los libros de texto como [AHU-84]. Esta es una gran ventaja de implementar contenedores parametrizables por medio de Binder.pas, pues le permite al programador reutilizar los programas que hizo en el pasado, que ya han sido depurados por el uso, para crear con poco esfuerzo su biblioteca de contenedores parametrizables. Este es un ejemplo de cómo dos facilidades sintácticas (el uso de parámetros por un lado y OOP por el otro), al unirse, proveen un grado de expresividad multiplicativamente mayor que el aporte que individualmente representan.

TYPE
  TBinder =  OBJECT
  PUBLIC
    PROCEDURE Print(VAR link: TContLnk; VAR F:TEXT);
  END;

      Con un examen cuidadoso de la implementación de TList.Print() el lector puede descubrir que el puntero "p" apunta a un nodo de enlace de tipo "TLlink", por lo que necesariamente el encabezado de la operación TBinder.Print(p,F) debe ser el que se muestra en el extracto de la especificación de TBinder en la Figura 7.13. Aquí el parámetro "link" debe ser el campo de enlace de la lista contenido en el elemento que se desea imprimir en el archivo "F". De esta discusión se deduce que el trabajo que debe realizar Binder.pas para invocar el método de impresión del elemento de la lista se da en dos etapas:

1. Traducir el puntero al enlace del contenedor (de tipo TContLnk) a un puntero al elemento (PElement). Para esto se usa la operación TBinder.Link_to_PObj().
2. Usar el puntero al elemento obtenido en el paso anterior para invocar el método correspondiente, si ese método está asociado al ligador. En caso contrario, se debe invocar el método que por defecto Binder.pas provee.

      Por ejemplo, si se invoca L.Print(F, BcharL), con el ligador BcharL definido en la Figura 7.11, al ejecutar Element.Print(p^, F) en la Figura 7.12 en realidad se invoca BcharL.Print(p^, F), que resulta en al ejecución del método e.Print(F), para aquel objeto "e" cuyo campo de enlace referencia "p". Esto quiere decir que se cumple que "e.linkL" es el campo de enlace que "p" denota (o sea, al que "p" apunta). En este caso, "e" es de tipo TcharL y la siguiente expresión Pascal es verdadera:
      @ ( p^ ) = @ (e.linkL)

      En su programa, el programador cliente trabaja con punteros a los elementos (PcharL, PElement), pero para accesar el contenedor debe usar posiciones (PCpos). Necesita entonces operaciones para poder transformar cada uno de estos dos tipos en el otro. Para realizar esta función el tipo TBinder exporta las operaciones TBinder.Link_to_PObj() y TBinder.PObj_to_Link().

      Para poder traducir un puntero a un campo de enlace [@ e.linkL] en el puntero al elemento [@ e], se necesita que las operaciones TBinder.Link_to_PObj() y TBinder.PObj_to_Link() ajusten punteros, ya sea sumándoles o restándoles el desplazamiento a que se encuentra el campo de enlace del contenedor dentro del elemento contenido. Por eso, en el ligador debe registrarse el tamaño del elemento, el del campo de enlace, y el desplazamiento a que se encuentra el campo de enlace desde el principio del elemento, o sea, la posición en que el campo de enlace aparece dentro del elemento (ver Figura 7.8). Es en la invocación a TBinder.Define() en donde se definen los valores que luego se usan para computar los desplazamientos necesarios para ajustar punteros (ver Figura 7.11).

      Las operaciones elementales que Binder.pas ofrece por defecto son muy simples. Por ejemplo, TBinder.Print() por defecto imprime el valor en hexagesimal de cada uno de los bytes que componen un objeto, pero cuidando de saltarse el campo de enlace que está físicamente dentro del elemento, pues le pertenece al contenedor. Para marcar el campo de enlace, TBinder.Print() imprime una marca pequeña <!>. Por ejemplo, al imprimir una variable de tipo TcharL que contiene la letra "a", lo que queda impreso es lo siguiente:
      <!> 61
Aquí aparece el valor hexagesimal 61, que equivale a 97 en decimal, pues el código ASCII de la letra "a" es el valor decimal 97. Como el campo de enlace aparece al principio del elemento, el marcador <!> aparece antes del valor del elemento. Si en la definición del tipo TcharL, en la Figura 7.9, el campo de enlace apareciera al final de la declaración, el valor impreso sería el siguiente:
      61 <!>

      La operación TBinder.Copy() que por defecto provee Binder.pas copia byte por byte un elemento sobre el otro, saltándose, eso sí, el campo de enlace del elemento. El programador cliente de Binder.pas deberá programar la operación Elem.Copy() cada vez que necesite usar un contenedor cuyos elementos no pueden ser copiados haciendo una simple copia bit a bit de la memoria en que está almacenado cada elemento. En estos casos, después de definir las características del elemento del contenedor invocando TBinder.Define(), el programador cliente debe evitar que se usen las operaciones que por defecto Binder.pas ofrece, invocando TBinder.Bind_Copy(), para que en el ligador quede registrado que se debe usar TElem.Copy() al copiar elementos, y no la copia bit por bit que por defecto Binder.pas hace.

      Por ejemplo, si el tipo TCharL necesita una operación de copia especial, para usar un contenedor asociado al ligador BcharL definido en la Figura 7.11 es necesario invocar la siguiente operación de TBinder:
      BcharL.Bind_Copy(TCharL.Copy);
Después de ejecutar esta operación, en el campo "BcharL._copy" del ligador BcharL quedará almacenado el puntero a la operación TcharL.Copy(). Si "TBinder._copy" contiene NIL, hay que ejecutar el código que por defecto Binder.pas ofrece para el método TElem.Copy(). Por el contrario, cuando este campo no es nulo apunta al método provisto por el programador para copiar elementos.

      Aunque es fácil entender qué debe hacer cada una de las operaciones que por defecto Binder.pas provee, su implementación es complicada. Por ejemplo, la operación de copia que por defecto Binder.pas suple, primero invoca la operación TBinder.Erase(SELF) en el objeto de destino, para que lo limpie. Después hace la copia bit por bit pero se cuida de no copiar el campo de enlace porque es el que indica en cuál contenedor está almacenado el elemento y, si copiara bit por bit ese campo de enlace, quedarían dos elementos diferentes enlazados en el mismo sitio del contenedor, lo que obviamente es un error. La invocación de TBinder.Erase(SELF) previa a la copia cubre el caso en que un objeto se puede copiar fácilmente, bit por bit, pero para limpiarlo hay que hacer un trabajo especial.

      Como ocurre con TBinder.Copy(), todas las operaciones que por defecto suple Binder.pas se cuidan de no tocar el campo de enlace del contenedor. Por eso cualquier objeto enlazado a un contenedor parametrizado con Binder.pas es un objeto complejo, para el que suplir operaciones por defecto no es simple.

      De la discusión anterior se concluye que las operaciones que ofrece TBinder para accesar el elemento contenido desde el contenedor son invocadas de la siguiente manera:

• Ajuste de punteros: Como el contenedor manipula punteros a sus campos de enlace (PCpos), es necesario ajustar esos punteros para que apunten al principio del elemento (PcharL, PElement), pues en muchos casos el campo de enlace está en el medio del elemento. Para ajustar punteros se usa la operación:
        TBinder.Link_to_PObj(link): PObj;
  La operación TBinder.Value() hace exactamente lo mismo que Link_to_PObj(), pero tiene un nombre mucho más significativo: efectivamente convierte una posición dentro del contenedor en un puntero al elemento contenido.
• Invocación de la operación: Una vez ajustado el puntero al elemento se usa una transferencia de tipos para invocar la operación respectiva. El llamado se hace usando los tipos FUnary, Fcnstr, etc., que son punteros a procedimientos, funciones o constructores que toman cero, uno o más argumentos.
• Retorno al subprograma llamador: Gracias a que en Turbo Pascal la forma de invocar un procedimiento es compatible con la de invocar un método, no hay que hacer trabajo alguno antes de devolver el control al programa llamador. Sin embargo, en otros compiladores o plataformas puede que haya trabajo que hacer antes de retornar.

      Muchas de las rutinas en Binder.pas manipulan a muy bajo nivel los objetos con que trabajan. Por ejemplo, las funciones de ajuste de punteros [TBinder.Link_to_PObj(), etc.] trabajan con los campos de desplazamiento ("offset" en inglés) de los punteros largos de la arquitectura Intel x86. Sin embargo, el módulo Binder.pas se ha especificado cuidando de que sea independiente de la plataforma sobre la que corra, de forma que para usarlo en otro ambiente baste cambiar la implementación, pero sin cambiar la especificación, aunque definitivamente la prueba de fuego es portar este código a otra plataforma.

      En la implementación de un contenedor, en algunas ocasiones es necesario crear nuevos elementos. El ligador TBinder exporta los métodos NEW() y DISPOSE(), Create() y Destroy(), Obtain() y Discard(), que sirven para este propósito. Tanto NEW() como Create() crean nuevos elementos para el contenedor, de acuerdo a sus cualidades definidas en el ligador, y DISPOSE() y Destroy() los destruyen. La diferencia está en que NEW() y DISPOSE() no inicializan o destruyen los elementos, lo que sí hacen Create() y Destroy().

      El efecto de los métodos Create() y Destroy() es similar al de Obtain() y Discard(), con la única diferencia de que los primeros aceptan como argumento un puntero al elemento (PcharL, PElement), mientras que los otros trabajan con un puntero al campo de enlace que está dentro del elemento (PCpos). Estas seis funciones simplifican el trabajo del programador cliente del contenedor, pues le evitan estar transformando punteros por medio de las operaciones Link_to_PObj() y PObj_to_Link(). Como NEW() y DISPOSE() no invocan al constructor y al destructor del elemento, el programador cliente puede usarlos para escribir programas más eficientes.

      Las operaciones TBinder.Construct() y TBinder.Destruct() son las encargadas de construir y destruir una variable de tipo TBinder. Para denominar estos dos métodos no se han usado los nombres Init() y Done(), como es usual, porque esos dos identificadores ya se han usado para expresar la invocación a las operaciones respectivas del elemento contenido en el contenedor: "TBinder.Init()" inicializa un elemento del contenedor, y "TBinder.Done()" lo destruye. Por eso, para inicializar y destruir el ligador "BcharL", en la Figura 7.11 se invoca BcharL.Construct() y BcharL.Destruct(): si Pascal tuviera sobrecarga de identificadores entonces en lugar de los nombres Construct(), Destruct() y Reset() se habrían reutilizado los nombres Init(), Erase() y Done().

      Las operaciones TBinder.Size() y TBinder.LinkOffset() son útiles al programar el contenedor porque retornan el tamaño del elemento contenido, y la posición en donde está el campo de enlace. La variable "Binder.Default_Binder", definida en Binder.pas, es un ligador que describe un elemento nulo; existe porque a veces al programador cliente de un contenedor le resulta cómodo usarlo.

      Los contenedores existen como módulos porque son expresión, en un lenguaje de computación, de los algoritmos de programación que corresponden a las estructuras de datos. Como para crear estructuras de datos se usan dos tipos de modelo, con punteros y agregando campos, es muy importante que una propuesta de cómo crear módulos de programación para implementar contenedores pueda ser usada para ADT's que usan estos dos tipos de modelo. La maquinaria desarrollada en este trabajo está más que todo orientada a implementar contenedores enlazados por punteros, como la lista y el árbol, y no los que son agregaciones ordenadas de elementos, como el arreglo y la matriz. Por eso se discute primero cómo están implementados los módulos lista y árbol, que son los representantes más importantes de los contenedores enlazados. Luego se discute también una implementación del ADT Vector.pas, para mostrar que la maquinaria desarrollada en este trabajo permite definir contenedores que almacenan sus elementos sin enlazarlos con punteros en memoria dinámica, sino que la pertenencia en el contenedor se da porque los valores están contiguos en la memoria, como ocurre con los vectores.

7.3 El contenedor Lista parametrizable

• Las Propiedades del ADT. En esta sección de la especificación se describen las cualidades principales de la estructura de datos que implementa el ADT, las que la hacen idónea para alguna aplicación. Por ejemplo, los vectores son muy económicos porque no usan punteros en su implementación y permiten acceso aleatorio inmediato, mientras que las listas permiten usar una cantidad mínima de espacio y pueden crecer arbitrariamente con gran eficiencia, lo que le permite al programador administrar el uso de la memoria dinámica.
        También en esta sección se pueden incluir algunas propiedades formales del ADT. Por ejemplo, para el contenedor pila se puede definir matemáticamente que el último en entrar siempre es el primero en salir.
• El Modelo. Mediante el uso de dibujos y esquemas es fácil expresar la interrelación de los campos que componen la implementación, lo que ayuda al programador cliente del ADT a usarlo adecuadamente.
        El modelo de un ADT es el conjunto de diagramas usados en los libros de texto sobre estructura de datos para describir los contenedores.
• Las Operaciones. Cada operación es un procedimiento o función, por lo que la especificación de cada operación se hace de la misma forma que la de una rutina, usando una cláusula RESULTADO, otra REQUIERE y definiendo el uso y tipo de los parámetros.
        En OOP las operaciones se llaman "métodos", y a estos junto con sus argumentos, se les llama "mensajes". Por ejemplo, es igualmente válido decir que L.LinkAfter(p, elem.k) es la invocación de la operación "LinkAfter()" para la lista "L" con los argumentos "p" y "elem.k", a decir que se le "envía" al objeto "L" el "mensaje" "LinkAfter(p, elem.k)", lo que resulta en la invocación de su "método LinkAfter()". Las dos expresiones son la misma cara de la misma moneda.
• Jerarquía de Tipos. Si se usa OOP, es muy importante incluir un diagrama que muestre cómo se relaciona el ADT con todos los tipos de los que deriva, y con los que derivan de él. Tal vez se puede incluir este diagrama junto con el modelo, o se puede mencionarlo aparte para destacar la autonomía del objeto.

      En este documento no se incluye la especificación completa de List.pas, la que sí está en un archivo adjunto a este trabajo: de seguro el lector ya sabe bien qué es una lista y no necesita esa detallada especificación. Más bien aquí se discuten los detalles que son relevantes para parametrizar el contenedor lista, pues el objetivo final de este trabajo es describir cómo crear un módulo List.pas muy eficiente, de forma que no sea necesario en el futuro gastar de nuevo esfuerzos programándolo o reprogramándolo. La implementación de List.pas se puede ver como un paradigma para implementar contenedores. Por eso, el módulo List.pas ha sido programado con gran cuidado, tratando de lograr la mayor eficiencia posible.

      Al implementar un contenedor, lo primero que el programador hace es escoger un modelo para la estructura de datos. En el caso de List.pas, el modelo es una lista circular, pues el último nodo apunta al primero, y cada nodo apunta al siguiente. Lo usual es que en la implementación de las listas se use un puntero al primer nodo de la lista, pero por razones de eficiencia en el caso de List.pas se usa un apuntador al último nodo de la lista, según se muestra en la Figura 7.14.

      La gran ventaja de apuntar al último nodo de la lista, y no al primero como comúnmente ocurre, es poder insertar elementos, tanto al principio de la lista como al final, usando una cantidad constante de esfuerzo: para agregar valores al principio de la lista basta enlazar el nuevo nodo después del último nodo de la lista, pero sin cambiar el valor almacenado en "_last". Para agregarlo al final de la lista se hace lo mismo que para insertarlo al principio, pero en este caso sí es necesario hacer que "_last" apunte al nodo recién enlazado. Realmente este algoritmo no es muy difícil de implementar, pero sí es más complicado que el usado por programadores que no tienen acceso a una biblioteca de contenedores reutilizables. El método TList.LinkAfter() contiene una lacónica implementación de este algoritmo.

      La principal razón por la que no es usual que en los libros de texto se use este modelo para implementar la lista es que requiere de una lógica de manipulación de punteros un poco más complicada, pues hay más casos especiales. En general, los autores de libros de texto prefieren usar ejemplos sencillos porque el código de cada implementación ocupa menos espacio, lo que facilita acomodarlo dentro del texto.

      También es usual que los programadores que usan muchas listas las implementen usando modelos más simples, como el de la Figura 7.15, pues para este modelo es mucho más fácil implementar la operación de inserción al principio de la lista; hay muchos programadores que han memorizado las instrucciones para hacer la inserción y el borrado de elemento, pues la lista es un contenedor que tiene uso en muchos programas. A esta técnica de parametrización puede llamársele Reutilización por Insistencia, y es precisamente una de las razones por las que se han inventado las construcciones sintácticas de parametrización en los lenguajes de programación (de acuerdo a [MDC-91] (pg 369), David Stemple es quien acuñó el término "Polimorfismo de Editor de Textos" para referirse a este concepto).

      De hecho, como la memoria humana es poco fiable, quien use "reutilización por insistencia" sabe que no debe usar algoritmos complicados, porque las más de las veces, al reproducirlos, quedan implementados incorrectamente. En los programadores existe la tendencia a no usar algoritmos sofisticados precisamente por el temor de no recordar exactamente cómo programarlos, lo que a la postre es la causa de que los programas sean menos eficientes de lo que pueden ser, con el agravante de que se están usando módulos que deben ser reinventados en cada nueva aplicación. Es realmente preocupante que los programadores deban sufrir por estas limitaciones debido a que no disponen de bibliotecas de contenedores reutilizables.

      Como una lista está compuesta de nodos enlazados, el módulo List.pas exporta el tipo TLlink, derivado directamente del tipo Binder.TContLnk, que contiene sólo un campo llamado "next". Siempre que se implementa un contenedor con punteros, es necesario crear uno o más tipos auxiliares que sirven para encapsular los punteros. Por eso en la lista, y también en el árbol, se habla de nodos, y cada nodo contiene un puntero. Sin embargo, al parametrizar con Binder.pas hay que trocar el concepto de "nodo" por el de "campo de enlace"; en ambos casos, sin embargo, como este tipo de datos le pertenece al contenedor, debe ser definido en el módulo del contenedor, como es el caso de TLlink.

      Una vez definido el tipo de enlace, una posición en la lista simplemente es un puntero a un campo de enlace, o sea, una variable de tipo "^TLlink". En la Figura 3.6 se les llama "PCpos" a los punteros abstractos que sirven para posicionamiento dentro del contenedor. Para la lista el nombre escogido es PLpos (con la "L" de "Lista" en lugar de la "C" de "Contenedor"). Los punteros a los nodos de enlace de la lista son de tipo PLlink = ^TLlink. Para la lista, la constante List.Null representa la posición nula (y por supuesto en la implementación su valor es PLlink(NIL)).

      Además de las operaciones elementales de cualquier ADT, las operaciones más importantes que List.pas exporta son las siguientes:

• Operaciones fundamentales
  • L.Valid(p): Retorna TRUE cuando "p" denota un enlace de la lista "L", o sea, cuando "p" apunta a un nodo de la lista.
  • L.First(): Posición del primer elemento de la lista.
  • L.Last(): Posición del último elemento de la lista.
  • L.Next(p): Posición del elemento que está después de "p".
  • L.Prev(p): Posición del elemento que está antes de "p".
  • L.Lpos(n): Posición del n-ésimo elemento de "L".
  • L.KLpos(p,n): Avance "n" posiciones a partir de "p".
  • L.Lind(p): Número del elemento que está en la posición "p".
  • L.LinkAfter(p, elem.link): Enlaza después de la posición "p" de la lista "L" el elemento "elem".
  • L.UnLinkAfter(p, px): Desliga de la lista "L" el elemento que está después de la posición "p", y retorna en "px" su posición.
  • L.Push(elem.link): Enlaza "elem" al principio de "L".
  • L.Pop(px): Desliga de la lista el primer elemento, y retorna en "px" su posición.
  • L.Append(elem.link): Enlaza "elem" al final de la lista.
  • L.En_Queue(elem.link): Enlaza "elem" al final de la lista.
  • L.De_Queue(px): Desliga de la lista el último elemento, y retorna en "px" su posición.
  • L.Reverse(): Invierte el orden en que están almacenados los elementos en la lista, de forma que sus últimos elementos pasen a ser los primeros, pero lo hace sin copiarlos.
  • L.Cut(r, oL,p,q): Traslada una sublista de la lista "oL" y la enlaza después de la posición "r" de "L", pero sin hacer copias. Esta operación requiere tiempo O(1).
• Operaciones adicionales
  • L.DeleteAfter(p, Element): Desenlaza el elemento que está después de la posición "p" de "L", e inmediatamente lo destruye. El ligador se llama "Element".
  • L.Delete_All(Element): Elimina todos los elementos de la lista. Para esto necesita destruir uno a uno los elementos de la lista, invocando su destructor por medio de Element.Discard().
  • L.Locate(elem.link, prev, Element): Si en la lista hay un elemento igual a "elem" retorna su posición, y en "prev" la posición al elemento anterior. De lo contrario, retorna la posición nula List.Null.

      En contraposición a la especificación que es usual encontrar para List.pas, en esta el programador cliente sólo puede agregar o quitar elementos después de un nodo. Por eso List.pas incluye operaciones como LinkAfter(), en que hasta con el nombre del método se explica que los resultados de las operaciones cambian al nodo siguiente al que está en una posición. List.Null actúa como el valor que está antes del primero, por lo que la invocación:
      L.LinkAfter(List.Null, elem.link)
agrega "elem" al principio de la lista. Por esta razón la operación TList.Locate() retorna la posición tanto del elemento encontrado como la de su antecesor, porque es con el antecesor que se le puede desligar de la lista.

      Como una lista de tipo TList sólo tiene punteros hacia adelante, la operación TList.Prev() requiere que se haga un barrido desde el principio de la lista para encontrar el nodo previo, por lo que la complejidad de esta operación es O(n).

      También se han definido para List.pas las operaciones que caracterizan al ADT pila [Push() y Pop()] y a la cola [En_Queue() y De_Queue()]. Sin embargo, las operaciones Pop() y De_Queue() no "borran" el elemento que está en el extremo del contenedor, sino que retornan la posición del valor desligado del contenedor, con la que el programador cliente puede accesar el elemento que ha obtenido con una de estas operaciones.

 TYPE
   TElement =   ...
   PElement = ^TElement;
 VAR
   Stk    : TList;    {  la pila  }
   Element: TBinder;  {  ligador  }
   pe     : PElement; { ^TElement }
   pxO    : PLlink;   {  posición }

 Stk.Pop( pxO );
 pe := PElement( Element.Link_to_PObj( pxO^ ) );
 WriteLn(pe^.info...);

      En la Figura 7.16 se muestra una manera de usar las operaciones de pila y cola que ofrece el ADT lista. La primera instrucción obtiene en "pxO" el puntero al nodo recién desenlazado de la pila "Stk" por la operación Pop(), y luego se usa el ligador de la pila para transformar a "pxO" en un puntero al elemento, mediante la operación TBinder.Link_to_PObj(). Finalmente, para depositar en "pe" ese valor, se usa una transferencia de tipos a través de PElement. En su disfraz de pila o de cola, el módulo List.pas es eficiente.

PROCEDURE TList.LinkAfter( { EXPORT }  { ADH }
  {+}     p : PLlink;      { adónde enlazar }
  {?} VAR x : TLlink       { elemento a enlazar }
);
{ RESULTADO
  Enlaza el elemento "x" después de la posición
  "p" de la lista.
  - Para insertar al principio de la lista, debe
    usarse LinkAfter(Null, x).
  - En todos los casos, el tiempo de ejecución
    es O(1).
  - Esta operación no utiliza memoria dinámica. }
{ REQUIERE
  - Valid(p) OR (p=Null). }
{ EJEMPLO
  Si L = A1,...,Ak-1,Ak,...An, y  "p" es la
  posición de Ak-1, después de invocar el método
  L.LinkAfter(p,x), el valor de la lista será
  L = A1,...,Ak-1,x,Ak,...An. }

BEGIN { TList.LinkAfter }
  IF _last = NIL THEN BEGIN
    { lista vacía: enlaza al inicio }
    x.next := @x;
    _last  := @x;
  END
  ELSE IF p = NIL THEN BEGIN
    { también enlaza al principio }
    p           := _last^.next;
    _last^.next := @x;
    x.next      := p;
  END

  ELSE IF p = _last THEN BEGIN
    { enlaza al final de la lista }
    x.next      := _last^.next;
    _last^.next := @x;
    _last       := @x;
  END
  ELSE BEGIN
    { enlaza en el medio }
    x.next  := p^.next;
    p^.next := @x;
  END;
END;  { TList.LinkAfter }

      La operación más importante de la lista es la que permite enlazarle un nuevo elemento. La Figura 7.17 es una extracta textual de List.pas, y consta de la especificación e implementación de esta operación TList.LinkAfter().

      La implementación de las operaciones de TList es muy similar a la implementación de las operaciones correspondientes en una lista no parametrizada. De hecho, estas implementaciones se obtuvieron a partir de la lista descrita en [DiM-94f], haciendo algunos pequeños cambios para que el programa compilara (por ejemplo, fue necesario cambiar el identificador "PLpos" por "PLlink"). Si se examina esta implementación, puede observarse que no hay forma de saber que TList es un contenedor parametrizable pues, salvo por el tipo de los argumentos, todo lo demás se ve como una implementación cualquiera de la lista: prácticamente no hay diferencia. Además, esta implementación es muy elegante, pues consiste en el examen de los cuatro casos relevantes para enlazar un nodo. Por lo menos en el código fuente, ¡ni siquiera usa variables temporales!

      Para mantener la pureza teórica de la biblioteca, en la especificación de TList.Swap() se incluye un parámetro para pasarle a TList.Swap() un ligador, aunque no se usa en la implementación. Se hacen así las cosas pues, aunque el programador cliente de la lista no espera que la implementación se haga sin usar punteros, si la lista fuera implementada como un vector de valores, si sería necesario el ligador para intercambiar cada entrada del vector, elemento por elemento. Esta discusión sobre TList.Swap() refuerza los argumentos en favor de utilizar la operación Swap() para trasladar valores entre subprogramas, que es la tesis defendida en [HW-91].

      En la implementación de algunas rutinas de TList se ha usado la variable de compilación "Learn_ADTs". Cuando esta variable está definida, el compilador sí compilará las instrucciones Pascal que estén en el bloque en que aparece la directiva de compilación "{$IFDEF Learn_ADTs}" y, en consecuencia, en el programa objeto quedará código para verificar condiciones de error adicionales. Por ejemplo, ejercitando esta técnica se le agrega código a la operación TList.Next(p) para verificar que se cumpla su precondición, o sea, que el puntero "p" sea diferente de List.Null.

      Queda así demostrada la tesis de este trabajo: se pueden implementar contenedores parametrizables que compartan el código objeto y en los que no es necesario entregar el código fuente. Lo que falta es recalcar cuán reutilizables son los componentes de programación que se obtienen con base en Binder.pas, labor que se hará al describir los módulos parametrizables Tree.pas y Vector.pas. Además, es necesario cuantificar el costo de usar Binder.pas, tanto en espacio como en tiempo.

7.4 El contenedor Árbol parametrizable

      La implementación de Tree.pas es una muestra de que el contenedor List.pas es realmente reutilizable. En efecto, en esta implementación los hijos de un nodo del árbol están enlazados en una lista, y esas listas de nodos hijos son de tipo TList. Para esta implementación no fue necesario alterar en forma alguna el código fuente de List.pas, en contraposición a la mala experiencia que tuvo el autor cuando implementó el contenedor Tree.pas sin usar Binder.pas (como se explica en la sección 7.1). Esta es la prueba de que List.pas realmente es un contenedor parametrizable y reutilizable. En gran parte la motivación para realizar este trabajo fue obtener este resultado.

      El ADT árbol implementado en Tree.pas contiene todas las operaciones de un ADT elemental. Las otras operaciones importantes son las siguientes:

• T.Count_Children(p): Es similar a T.Count(), mas retorna el número de hijos del nodo "p" en lugar del total de hijos del árbol.
• T.Valid(p): Esta operación es el homólogo a TList.Valid(), pues retorna TRUE si el árbol contiene el nodo "p".
• T.Root(): Esta operación es similar a TList.First(), pues retorna un puntero a la raíz del árbol.
• T.Father(p): Esta operación es similar a TList.Prev(), pues retorna un puntero al padre del nodo "p". Como ocurre en el caso de la lista, para encontrar al padre es necesario hacer una búsqueda exhaustiva desde la raíz.
• T.Child(p,n): Esta operación sirve para llegar desde un nodo a alguno de sus hijos; es la homóloga de TList.Next(), pero como un nodo puede tener varios hijos, es necesario definir a cuál de todos se quiere llegar, indicándolo con el valor a "n".
        Como los hijos de cada nodo en el árbol están enlazados en una lista, para llegar al n-ésimo es necesario accesar los (n-1) nodos anteriores. Este inconveniente puede obviarse si se usa un vector para apuntar a los nodos hijos, pero en este caso la implementación sería más complicada porque hay que usar vectores de tamaño variable, o vectores que no están totalmente llenos.
• T.Sibling(p,i): Permite desplazarse desde un nodo hacia alguno de sus hermanos, ya sea a la derecha o a la izquierda. Las cuatro operaciones para Root(), Father(), Child() y Sibling() son las que le permiten al programador recorrer su árbol.
        Esta operación es cara, pues para llegar a un nodo hermano hay que encontrar al padre invocando primero Father(), que siempre barre todo el árbol para hacer su trabajo.
• T.Leaf(p): Regresa TRUE cuando "p" es un nodo hoja.
• T.Height(p): Regresa la distancia al nodo hoja más distante de "p", que además es su descendiente.
• T.Depth(p): Calcula la distancia entre "p" y el nodo raíz del árbol.
• T.Link_Child(p, i, elem.link): Enlaza el elemento "elem" para que sea el i-ésimo hijo del nodo "p", en forma similar a como LinkAfter() enlaza un nodo en la lista. El costo de esta operación es O(T.Count_Children(p)), pues los hijos de cada nodo están enlazados en una lista de tipo TList.
• T.Extirpate(p): Desliga del árbol al nodo "p". Si "p" tiene descendencia, esta operación traslada todos sus hijos y los coloca como hijos de su padre, en la posición que antes ocupara "p". Esta operación no es muy eficiente pues, en general, para desligar "p" hay que encontrar al padre, lo que requiere de un barrido de todo el árbol.
        Como anécdota interesante cabe mencionar que TList.Cut() nació para implementar esta operación, pues al sacar del árbol el nodo "p", es necesario trasladar todos sus hijos para que sean descendientes directos de su padre. TList.Cut() permite trasladar a todos los nodos de un tirón, haciendo un esfuerzo mínimo de orden O(1).
        Después de implementar TList.Cut(), surgió la idea de agregar una eficiente implementación de TList.Reverse(), la que se discute en [DiM-96a].
• T.Extirpate_Child(p, i, px): Desliga el i-ésimo hijo del nodo "p", y retorna en "px" un puntero a él. Como ocurre con T.Link_Child(), esta operación es de orden O(T.Count_Children(p)).
        Como el método Extirpate_Child() tiene un costo de ejecución mucho más bajo que Extirpate(), es lógico que cualquier programador prefiera usarlo en lugar de Extirpate().
• T.Prune(p): Elimina el nodo "p" del árbol, y también toda su descendencia. A diferencia de Extirpate(), este método sí destruye todos los descendientes de "p".
• T.Prune_Child(p, i): De la misma forma en que para Extirpate() existe el Extirpate_Child(), para Prune() hay un Prune_Child() que se encarga de destruir el i-ésimo subárbol del nodo "p".
• T.Graft(p, i, T2): Esta es la operación más elegante de Tree.pas, pues permite trasladar completo el árbol T2 para que sea el i-ésimo hijo del nodo "p" en "T". Una operación similar al Cut() de la lista es T.SubGraft(), que permite trasladar, no todo el árbol, sino un subárbol.

      Como ocurre al parametrizar cualquier contenedor por medio de Binder.pas, fue necesario definir un campo de enlace para el ADT Árbol. Para nombrar al campo de enlace de la lista se escogió el identificador TLlink=["T"ype+"L"ist+"link"] y, por analogía, para el árbol se usa TTlink=["T"ype+"T"ree+"link"], o sea, que el nombre del campo de enlace de la lista tiene una letra "L" en el medio, y el del arbol tiene la letra "T".

      Existen dos formas de enlazar los hijos de cada nodo del árbol. La primera, y más simple, es incluir un campo de enlace de la lista [TLlink] en cada uno de los campos de enlace del árbol [TTlink]. Si se escoge esta arquitectura para construir TTlink, entonces el campo de enlace del árbol contendría al menos dos campos:

1. Lchild: List.TList. Este campo es la lista de todos los hijos del nodo.
2. linkL:  List.TLlink. Este campo sirve para enlazar este nodo [TLlink] con todos sus hermanos, dentro de la lista de hijos del nodo padre [TTlink].

TYPE
  { Campo de enlace de TTree }
  TTlink = OBJECT (Binder.TContLnk)
    father: Tree.PTlink;  { puntero al padre  }

    Lchild: List.TList;   { lista de hijos    }
    linkL : List.TLlink;  { hermanos del nodo }
  END;

      El campo de enlace del árbol podría contener otros campos adicionales, como por ejemplo, uno llamado "father" que sirva para apuntar desde cada nodo hijo al nodo padre. En la Figura 7.18 se muestra la definición de TTlink en el caso de que se use esta estrategia de implementación. Como es usual, el tipo TTlink está derivado del TContLnk, que está definido en Binder.pas.

      La Figura 7.19 es el diagrama de un nodo de tipo TTlink, y por ende corresponde a la definición de tipos de la Figura 7.18. Para cada nodo, "linkL" es el campo de enlace en la lista de sus hermanos, y todos los hermanos están enlazados en la lista "Lchild" de su nodo padre. El campo "father" apunta al nodo padre, y es de tipo PTlink (puntero al campo de enlace del árbol). El campo "linkL" sólo contiene un campo llamado "_next", que apunta al siguiente campo de enlace de la lista, y el campo "Lchild" sólo apunta al último de los nodos hijos.

      En la Figura 7.20 se muestra cómo estarían enlazados cinco campo de ligamen para el árbol, cada uno de los cuales tiene una forma similar a la del diagrama de la Figura 7.19. Como estos cinco enlaces corresponden a un nodo padre que tiene cuatro hijos, en la lista de hijos (Lchild) del padre hay cuatro nodos enlazados (linkL). El nodo padre tiene en su campo "Lchild" un puntero al último nodo de enlace de la lista de hijos, la que está formada por la cadena de punteros que en los hijos se forma por medio del campo "linkL". Todos los campos "father" de los cuatro nodos hijos apuntan hacia el padre común. El diagrama de la Figura 7.20 corresponde a la definición de tipos de la Figura 7.18.

      Aunque la estrategia de implementación que representa la definición de la Figura 7.18 es eficiente, la usada fue otra. La implementación Tree.pas es la misma del ADT Árbol no parametrizable, pero ligeramente transliterada para utilizar los campos de enlace a través de Binder.pas. Como la implementación original del Árbol usa una lista de punteros que había sido obtenida modificando List.pas para eliminarle el campo de tipo "TElem" (y sustituirlo por un puntero genérico), en lugar de usar la definición del tipo TTlink de la Figura 7.18, para el ADT Árbol parametrizable se usa una declaración similar a la de la Figura 7.1.

      Cada nodo del árbol contiene una lista, y cada nodo de esa lista incluye un puntero hacia uno de los hijos. Esto implica que, para llegar a un hijo del nodo primero, hay que recorrer la lista de punteros a los hijos, para de ahí saltar al hijo correspondiente. Habría sido más eficiente enlazar todos los hijos en una lista del padre, para lo que basta incluir un campo de enlace TTlink en cada nodo, pero entonces habría sido más difícil reutilizar la implementación no parametrizable de Tree.pas con que ya se contaba. Cada nodo en la lista de punteros a los hijos es de tipo "TLnode", y tiene dos campos:

1. link: TLlink. Este es el campo de ligamen que se usa para enlazar en la lista todos los TLnode's.
2. child: PTlink. Este campo contiene el puntero al nodo hijo en el árbol.

TYPE
  { Elemento de la lista de hijos del cada nodo }
  TLnode =  OBJECT (TObj)
    link  : TLlink;     { ligamen de TList }
    child : PTlink;     { puntero al hijo  }
  END;

  { Campo de enlace de TTree }
  TTlink = OBJECT (Binder.TContLnk)
    children :  TList;    { lista de TLnode's }
    { father : ^TTlink; } { puntero al padre  }
  END;

      El campo de enlace para un árbol, TTlink, sólo necesita almacenar un campo, "children", que contiene la lista de los TLnode's que denotan a los hijos del nodo del árbol. En la Figura 7.21 está la definición de los tipos usados para implementar Tree.pas.

      Los nodos del árbol no tienen un puntero al nodo padre. Si lo tuvieran, el lugar adecuado para colocarlo sería dentro del nodo de enlace del árbol, por lo que en la Figura 7.21 el tipo TTlink tendría otro campo, llamado "father", de tipo PTlink.

      El diagrama que corresponde a la definición de tipos de TTree es el que aparece en la Figura 7.22, en el que se muestra un nodo padre que contiene una lista de TLnode's que apuntan a cada uno de los hijos. En este caso, el nodo padre TTlink tiene cuatro hijos.

      Es más eficiente no usar la lista "children" de TLnode's para llegar desde cada nodo del árbol a sus hijos. El ahorro de la definición de la Figura 7.18 respecto a la de la Figura 7.21 es doble, pues no es necesario mantener un tipo adicional [TLnode] ni crear en la memoria dinámica una lista de TLnode's. O sea, es más simple incluir en cada nodo del árbol un campo de enlace para la lista de hijos del padre (como en la Figura 7.20), que crear una lista en memoria dinámica que contiene los punteros a los hijos de cada nodo (como en la Figura 7.22). En el diagrama de la Figura 7.23 se muestra la diferencia entre estas dos implementaciones: ahí se destaca el ahorro que implica no usar la lista intermedia de TLnode's para enlazar los nodos hijos con su padre.

      Se escogió implementar Tree.pas de la forma menos eficiente, usando la lista "children" de TLnode's que contiene los punteros a los nodos hijos de cada nodo del árbol, porque la implementación de Tree.pas se obtuvo cambiando un poco la anterior implementación no parametrizable del árbol que el autor había depurado: en ese momento era más simple hacer el trabajo de transliteración que crear una implementación más eficiente. El hecho de que la implementación de Tree.pas pueda obtenerse con poco esfuerzo a partir de una implementación no parametrizable, muestra dos cosas:

1. El uso de Binder.pas no implica un cambio sustancial en la forma o el estilo que se debe usar al implementar los algoritmos de los contenedores.
2. Se pueden obtener implementaciones más eficientes si se usa un contenedor parametrizable en lugar de uno no parametrizable.

      Otra forma de enlazar el nodo padre con sus hijos es usar un vector de punteros, en lugar de la lista "children" de TLnode's. Si se sigue esta estrategia, el resultado es un árbol cuyo modelo se muestra en la Figura 7.24. Como la implementación de Tree.pas usa la lista "children" de TLnode's para enlazar a los hijos de cada padre, es relativamente sencillo cambiar la implementación para usar, en lugar de esta lista, un vector "children" de punteros a los hijos. Este cambio es sencillo de hacer, lo que da base para argumentar que la implementación escogida es ventajosa, aunque sea menos eficiente, tanto en espacio como en tiempo de ejecución, en comparación con la que corresponde a la Figura 7.20.

{$IFDEF Link_Child }

  TYPE
    TLnode = OBJECT
      link  : TLlink; 
      child : PTlink;
   END;

{$ENDIF}

{$IFDEF Child_Link }

  TYPE
    TLnode = OBJECT
      child : PTlink; 
      link  : TLlink;
    END;

{$ENDIF}

      Al implementar el tipo TLnode surgió un hecho interesante, que vale la pena comentar. En la Figura 7.25 se muestra que un TLnode consta de dos campos, por lo que es posible definirlo de dos formas. Cuando en el TLnode aparece primero el campo de ligamen de la lista, un puntero al campo de enlace en un TLnode se puede convertir en un puntero al TLnode simplemente haciendo una transferencia de tipos, mientras que, en el caso contrario, es necesario ajustar punteros, sustrayéndole el desplazamiento a que está el campo "link" desde el principio del TLnode, que es el tamaño del campo "child", o sea, SizeOf(TLnode.child). En la implementación de Tree.pas es posible escoger una u otra implementación definiendo la constante de compilación "Link_Child". En el segundo caso, en lugar de una transferencia de tipos hay que invocar la función PLlink_PLnode(pL: PLlink): PLnode; para transformar un puntero al campo de enlace TLlink en el puntero al TLnode.

FUNCTION  TTree.Count    { EXPORT }     { ADH }
  {>>>>>>>>} : WORD;     { Cardinalidad }
{ RESULTADO
  Retorna el número de elementos del árbol.
  - El tiempo de ejecución es O(n). }
VAR
  n : WORD;
BEGIN { TTree.Count }
  IF _root = NIL THEN BEGIN
    Count := 0;
  END
  ELSE BEGIN
    n := 1; { cuenta a la raíz del árbol }
    TTree_Count0(SELF._root, n);
    Count := n;
  END;
END;  { TTree.Count }

      Como el árbol es una estructura de datos inherentemente recursiva, la implementación de muchas de sus operaciones es también recursiva. Tal vez la más simple de todas es la operación TTree.Count(), que retorna la cantidad de nodos del árbol contando recursivamente la cantidad de hijos de cada nodo. La Figura 7.26 es la especificación e implementación de TTree.Count(). En sí TTree.Count() no es una operación recursiva, pues sus argumentos no son del tipo adecuado (^TTlink), por lo que lo único que hace es destapar la raíz del árbol, invocando con el argumento "T._root" el procedimiento recursivo TTree_Count0(p,n), que incrementa "n" con el número de nodos que tiene el sub-árbol de "T" denotado por el nodo "p^". Al principio, TTree.Count() inicializa en uno el valor de "n".

PROCEDURE TTree_Count0(  { LOCAL }      { ADH }
  {?} VAR p : PTlink;    { nodo del árbol }
  {?} VAR n : WORD       { # descendientes de p }
);
{ RESULTADO
  Incrementa "n" en el número de hijos que tiene el
  sub-árbol cuya raíz es "p".
  - Este procedimiento es el paso recursivo usado para
    implementar TTree.Count().
  - No cuenta a "p", pues en el llamado desde el padre
    ya se le ha tomado en cuenta. }
{ NOTA
  Como no se necesita accesar ninguno de los campos
  del árbol, entonces como micro-eficiencia se omite
  como argumento el árbol "T" sobre el que se trabaja. 
}
VAR
  pL   : PLlink;   { posición en la lista de hijos   }
  pN   : PLnode;   { contenido del nodo pL^          }
  child: PTlink;   { puntero al hijo denotado por pN }
BEGIN { TTree_Count0 }
  n := n + p^.children.Count;

  pL := p^.children.First;
  WHILE pL <> List.Null DO BEGIN
    pN := PLlink_PLnode( pL );
    child := pN^.child;

    TTree_Count0(child, n);
    pL := p^.children.Next(pL);
  END;
END;  { TTree_Count0 }

      Como ocurre con TTree.Count(), la mayoría de las operaciones de Tree.pas están implementadas usando dos procedimientos: el primero es la interfaz para sacar del árbol el puntero a su raíz, y el segundo, que es el que se encarga de hacer el trabajo procesando el nodo y luego haciendo un llamado recursivo. La implementación de la rutina recursiva TTree_Count0(), que TTree.Count() invoca, aparece en la Figura 7.27.

      En la implementación de TTree_Count0(p,n) no es necesario incluir "T", el árbol al que pertenece el nodo denotado por "p", pues sólo se necesita accesar los valores que están almacenados en el campo de enlace de nodo del árbol. Eso ocurre no sólo en la implementación de TTree.Count(), sino que es usual encontrar este tipo de ventaja al implementar otras operaciones.

      Como puede observarse en la Figura 7.27, y también en la implementación de la mayor parte de las operaciones de Tree.pas, es necesario accesar la lista "children" de hijos del nodo padre. Para manipular la lista de hijos de cada nodo se usan dos variables de apoyo: pL: ["p"untero+"Lista de hijos"] y pN: ["p"untero+"Nodo de la lista de hijos"].

pL: PLlink:

Es una variable usada para recorrer la lista "children" de hijos de un nodo.

pN: PLnode:

Después de llegar a un TLnode de la lista "children" de hijos, hay que tomar la información contenida en él para accesar el hijo al cual ese TLnode apunta.

      Para llegar al hijo de un nodo entonces hay que dar dos pasos. Primero se obtiene de la lista "children" de hijos alguno de los TLnode's y se almacena su posición en "pL". Luego se usa PLlink_PLnode(pL) para transformar el puntero al campo de enlace de la lista de hijos (PLlink) en el puntero al TLnode que contiene ese enlace (PLnode), y ese valor se deja en la variable "pN". Para llegar al hijo basta accesar el campo "child" del TLnode, "pN^.child", que es de tipo "^TTlink" (puntero al enlace de un árbol), como se define en la declaración de tipos de la Figura 7.21.

      En la implementación de TTree_Count0(p,n) en la Figura 7.27 también se puede ver el uso de las variables "pL" y "pN": con la primera se recorre la lista de hijos y con la segunda se accesa el puntero "child" a cada nodo hijo. También se usa la variable "child" para mostrar que "pN^.child" es el hijo del nodo.

7.5 Iteradores parametrizables

UNIT List;

TYPE { Iterador para TList }
  Iterator = OBJECT
  PUBLIC
    CONSTRUCTOR Init;
    DESTRUCTOR  Done;               VIRTUAL;

    PROCEDURE Bind( VAR L : TList); VIRTUAL;
    PROCEDURE BindB(VAR L : TList;
                    VAR Element: TBinder); VIRTUAL;
    FUNCTION  Finished: BOOLEAN;    VIRTUAL;
    FUNCTION  Current : PLlink;     VIRTUAL;
    PROCEDURE Next;                 VIRTUAL;
  END; { List.Iterator }

TYPE
  Iterator_More = OBJECT ( Iterator )
  PUBLIC
    CONSTRUCTOR Init;

    FUNCTION  Bound     : PBinder;     VIRTUAL;
    FUNCTION  Container : PList;       VIRTUAL;
    PROCEDURE Advance(n : INTEGER);    VIRTUAL;
    PROCEDURE From(   p : PLlink);     VIRTUAL;
    PROCEDURE Range( p,q: PLlink;
                     VAR n: LONGINT);  VIRTUAL;
  END; { List.Iterator_More }

      Como se nota en la Figura 7.28, todos los métodos del iterador, salvo su constructor, son polimórficos, esto es, deben ser declarados con la palabra VIRTUAL, lo que implica que todos los iteradores siempre son definidos usando exactamente los mismos nombres para sus métodos, y todos sus métodos tienen exactamente el mismo encabezado. En el mismo módulo en que se define el contenedor también hay que definir el objeto "Iterador", que es un iterador abstracto para el contenedor, del que se derivarán todos sus iteradores. Por ejemplo, el tipo Iterador para el tipo TList debe estar definido en List.pas.

      Como todas las operaciones de un iterador son métodos polimórficos, cualquier rutina que reciba como argumento un iterador, o sea una variable cuyo tipo fue derivado de "Iterator", puede invocar las operaciones del iterador a través de la variable, pues cada instancia del iterador incluye la referencia a todas sus operaciones. Por esta misma razón, la rutina que recibe a cualquier iterador como argumento es independiente del tipo de iterador que usa, ya que en cada instancia del iterador está la referencia a sus propios métodos, lo que releva a la rutina del tener que distinguirlos al invocarlos. La gran ventaja de que todas las operaciones del iterador sean polimórficas es que las rutinas que los usan son automáticamente parametrizables (o polimórficas, como se las quiera llamar), pues para accesar los elementos del contenedor en el orden que el iterador define, basta tener acceso a la instancia del iterador, para a través de ella invocar todos sus métodos. Un ejemplo de este tipo de rutina es el procedimiento Print_Tree(T,I) de la Figura 3.29, que puede imprimir un árbol por medio de un iterador, independientemente de cuál sea el iterador, o del orden en que el iterador recorre al árbol.

      Una rutina que es independiente del tipo de datos que usa es una rutina polimórfica, y por lo tanto también es parametrizable. Cuando una rutina recorre el contenedor usando un iterador, el orden de proceso de los datos no dependerá de la rutina, sino del iterador, con lo que efectivamente basta cambiar de iterador para que la misma rutina obtenga sus datos en un orden diferente. La única objeción que se le puede hacer al uso de métodos polimórficos para implementar iteradores es que, en algunas ocasiones, el sobretrabajo que representa invocar funciones virtuales puede ser demasiado oneroso, en cuyo caso hay que evitar totalmente el uso de punteros indirectos para referenciar rutinas. Esta es una de las justificaciones por las que C++ tiene parametrización textual, pero no polimorfismo uniforme [Str-86a].

      Hay una razón por la que en el módulo Binder.pas no está definido el tipo Iterator. El lenguaje Turbo Pascal exige que la interfaz de todos los métodos polimórficos que tienen el mismo nombre del método de la clase base tengan exactamente los mismos argumentos, esto es, que todos los métodos homónimos tengan el mismo encabezado. Esto quiere decir que si el tipo Binder.Iterator define al método:
      PROCEDURE Iterator.Next : Binder.PContLnk;
o sea, que retorna un puntero al campo de enlace base TContLnk definido en la unidad Binder.pas, no es posible que un tipo derivado de la clase abstracta "Iterator" retorne un valor de tipo "PLlink" (diferente de PContLnk), aunque ocurra que el tipo "TLlink" que corresponde a "PLlink" esté derivado del tipo "TContLnk". El problema es que al tipo "TLlink" hay que definirlo en la unidad List.pas, y no es posible saber de antemano cuáles son las unidades que usarán la unidad Binder.pas, en la que se define "TContLnk".

      Los tipos de los parámetros de los métodos del iterador están definidos en el módulo en que se define el contenedor, por lo que son desconocidos en el módulo Binder.pas. Esta limitación se podría levantar si un método virtual pudiera tener parámetros derivados de los tipos del método que hereda, pero Turbo Pascal no tiene esta facilidad sintáctica (seguramente porque complica mucho el lenguaje).

      Cada iterador retorna posiciones en el contenedor, que siempre se representan como punteros al campo de enlace: como estos tipos deben ser definidos junto al contenedor, no es posible definir el tipo Iterator en el módulo Binder.pas. Por esta misma razón el tipo "Iterator" en la Figura 7.28 no está derivado de ningún otro tipo. Esta pequeña limitación obliga al programador del contenedor a ser cuidadoso al definir los tipos y métodos del iterador, aunque en general basta que use como plantilla la definición de la Figura 7.28.

      Las operaciones Iterator.Bind(L) e Iterator.BindB(L, Element) (con B al final) son muy similares, aunque difieren en que la segunda se debe usar si el iterador necesita invocar las operaciones del elemento contenido en el contenedor, por medio del ligador "Element" que recibe como argumento. Por ejemplo, para recorrer la lista "L" con el iterador I_ForwL, hay que invocar a la primera:
      I_ForwL.Bind(L);
pues para recorrer una lista hacia adelante con un iterador FowrL.pas, no hace falta usar el valor de cada elemento de la lista.

      Por el contrario, si con el iterador I_Order, que retorna los elementos de la lista ordenados de menor a mayor, se va a recorrer una lista "Lchar" de caracteres, del tipo TcharL definido en la Figura 7.9, hay que invocar la segunda operación BindB():
      I_Order.BindB(Lchar, BcharL);
pues, para ordenar la lista, el iterador Order.pas necesita usar la operación TcharL.Less() para comparar los valores de los elementos almacenados en el contenedor, lo que logra invocando BcharL.Less(), pues BcharL es el ligador para la lista de caracteres Lchar. Esto quiere decir que en la implementación del iterador FowrL.pas se redefine el método Iterator.Bind(), mientras que en Order.pas se redefine Iterator.BindB() (con B). En ambos casos, el otro método no se redefine, por lo que, si por error el programador cliente de List.pas los invoca, obtendrá un error en tiempo de ejecución, que es generado por la implementación (abstracta) de los métodos Iterator.Bind() e Iterator.BindB().

TYPE
  Iterator_More = OBJECT ( Iterator )
  PUBLIC
              { Métodos Optativos }
  CONSTRUCTOR Init;
    FUNCTION  Bound     : PBinder;     VIRTUAL; 
    FUNCTION  Container : PList;       VIRTUAL;
    PROCEDURE Advance(n : INTEGER);    VIRTUAL;
    PROCEDURE From(   p : PLlink);     VIRTUAL;
    PROCEDURE Range( p,q: PLlink;
                     VAR n: LONGINT);  VIRTUAL;
  END; { List.Iterator_More }

      En ocasiones conviene que el iterador cuente con alguna, o con todas, las operaciones optativas. En esos casos, en lugar de derivar el iterador de List.Iterator, conviene derivarlo del tipo List.Iterator_More, cuya definición se muestra en la Figura 7.29.

      Para cada iterador, el programador del contenedor debe decidir cuál de los métodos Iterator.Bind() o Iterator.BindB() debe implementar. En general no tiene sentido que el mismo iterador cuente con estos dos métodos, aunque si un iterador sólo necesita la operación Iterator.Bind(), no es erróneo implementar Iterator.BindB() (con B) como una invocación a Iterator.Bind().

      Como ocurre con los contenedores, al escribir la implementación de los iteradores, en muy pocas ocasiones percibirá el programador que su iterador es parametrizable, gracias a la expresividad que la combinación de OOP y el buen diseño de Binder.pas le ofrecen.

7.6 Parametrizador de plantillas CPTinst

TYPE
  TcharL = OBJECT
    ch   : CHAR;         { valor del elemento   }
    linkL: List.TLlink;  { enlace para la lista }
    ...
  END; { TcharL }

TYPE
  TpersonL = OBJECT
    nombre    : STRING[20];    { valor del elemento }
    appellido : ARRAY [1..2] OF STRING[20];
    edad      : WORD;

    lk        : List.TLlink;  { enlace para la lista }
    ...
  END; { TpersonL }

VAR
  L : TList;   { una lista parametrizable }
  c : TcharL;     { una letra      }
  p : TpersonL;   { una persona... }
       ...
  L.Append(c.linkL);  { Lista de letras }
  L.Append(p.lk);     { ¡Opa! Mezcla... }

      En la Figura 7.30 se muestra cómo en la misma lista "L" se enlazan dos valores de tipos diferentes, pues uno contiene una letra y el otro los datos de una persona. Como los métodos de la lista parametrizable reciben campos de enlace, el compilador no emite error alguno porque no puede detectar que en la lista "L" no es una lista heterogénea.

TYPE
  TcharL = OBJECT (Binder.TObj)
    ch   : CHAR;         { valor del elemento   }
    linkL: List.TLlink;  { enlace para la lista }
    ...
  END; { TcharL }

  TList_TcharL = OBJECT (List.TList)

    PROCEDURE LinkAfter(   p: PcharL; VAR x : TcharL);
    PROCEDURE UnLinkAfter( p: PcharL; VAR px: PcharL);
    PROCEDURE DeleteAfter( p: PcharL);

    PROCEDURE Append(      VAR x : TcharL       );
    PROCEDURE Copy(        VAR o : TList_TcharL );

  END; { TList_TcharL }

      Para agregarle verificación fuerte de tipos a su lista, el programador cliente tiene que crear un nuevo tipo, llamado TList_TcharL en la Figura 7.31, que es una lista en la que se pueden enlazar únicamente caracteres. Para esto, al definir su tipo TList_TcharL, el programador cliente cambia el tipo de los parámetros de los métodos de la lista, para que sólo encajen los tipos "TcharL" y "PcharL", en lugar de aceptar variables de tipo genérico "TLlink" y "PLlink". De esta manera se asegura de que las operaciones de TList_TcharL sólo se pueden aplicar a elementos del tipo adecuado "TcharL". Para implementar su lista TList_TcharL, el programador cliente usará el ligador "BcharL" definido en la Figura 7.11.

      De la misma forma que se ha obtenido el tipo TList_TcharL, es posible obtener otras listas, por ejemplo, TList_TintegerL, para lo que habría que usar dos ligadores: "BcharL" para TList_TcharL y "BintegerL" para TList_TintegerL. Ambos compartirían la misma implementación de List.pas, pues para implementar tanto TList_TcharL como TList_TintegerL, no es necesario tener acceso al código fuente de List.pas, porque en la implementación de ambos objetos basta con invocar a las operaciones de TList, pero nunca hace falta modificarlas.

      El trabajo que tienen que hacer los métodos de TList_TcharL es muy simple, pues se reduce a cambiar el tipo de cada variable para invocar la operación homónima de TList. Por ejemplo, el método TList_TcharL.LinkAfter(p, x) lo único que hace es invocar:
      TList.LinkAfter( @ (p^.linkL), x.linkL);
pues la operación del mismo nombre para la lista, TList.LinkAfter() (sin el "TcharL"), recibe como argumento un campo de enlace "x.linkL", en lugar del valor completo "x", y no usa directamente el puntero al elemento "p^", sino que necesita una posición, que es la dirección del campo de enlace "p^.linkL".

TYPE
  PcharL = ^TcharL;
  TcharL =  OBJECT
    ch   : CHAR;         { valor del elemento   }
    linkL: List.TLlink;  { enlace para la lista }
    ...
  END; { TcharL }

PROCEDURE TList_TcharL.LinkAfter(
  p: PcharL; VAR x: TcharL);
BEGIN
  IF p = NIL THEN BEGIN
    TList.LinkAfter(   List.Null, x.linkL);
  END
  ELSE BEGIN
    TList.LinkAfter(@ (p^.linkL), x.linkL);
  END;
END;

      Aunque la idea general expresada en el párrafo anterior es la correcta, en realidad la implementación requiere un poco más de elaboración. El problema es definir qué ocurre cuando una operación de TList_TcharL recibe el puntero nulo NIL, pues es incorrecto derreferenciar NIL en la implementación de LinkAfter(). En la Figura 7.32 está la implementación correcta de la operación TList_TcharL.LinkAfter(), que incluye la verificación sobre la nulidad del puntero "p", trabajo que, indudablemente, reduce la eficiencia del método TList_TcharL.LinkAfter().

      El costo de agregar verificación fuerte de tipos a un contenedor es la indirección adicional para invocar TList.LinkAfter() desde TList_TcharL.LinkAfter(), aunque también hay que agregar lo que le cuesta al programador cliente reutilizar la implementación del contenedor. Si el contenedor se usa en una aplicación en que se necesita un máximo rendimiento, este precio puede resultar muy alto, pero para la mayor parte de las aplicaciones esta indirección agregará sólo un par de millonésimas de microsegundo, que es el tiempo que se necesita para realizar la invocación indirecta.

PROCEDURE TList_TcharL.DeleteAfter( p : PcharL );
VAR
  pDel : PLlink;
BEGIN
  IF p = NIL THEN BEGIN
    TList.UnlinkAfter( List.Null, pDel );
  END
  ELSE BEGIN
    TList.UnlinkAfter( @ (p^.linkL) , pDel );
  END;
  BcharL.Discard( pDel );
END;

      La operación LinkAfter() es una operación fundamental, por lo que no necesita usar un ligador. En la Figura 7.33 aparece la implementación de TList_TcharL.DeleteAfter() que usa el ligador "BcharL" para destruir el objeto desligado del contenedor. En contraposición a UnlinkAfter(), esta operación elimina el nodo de la lista que está después del nodo "p^". La implementación lo que hace es transformar el puntero "p" en un puntero al campo de enlace de "p^", que en este caso se llama "p^.linkL", para luego destruir el nodo desenlazado de la lista usando el ligador "BcharL".

PROCEDURE TList_<TElem>.DeleteAfter( p : <PElem> );
VAR
  pDel : PLlink;
BEGIN
  IF p = NIL THEN BEGIN
    TList.UnlinkAfter( List.Null, pDel );
  END
  ELSE BEGIN
    TList.UnlinkAfter( @ (p^.<link>) , pDel );
  END;
  <Binder>.Discard( pDel );
END;

      En la Figura 7.34 se muestra cómo se puede transformar en una plantilla genérica la implementación de DeleteAfter() de la Figura 7.33. Para obtener esta plantilla, con un editor de textos se han hecho las siguientes sustituciones:

1. BcharL ==> <Binder>
2. TcharL ==> <TElem>
3. PcharL ==> <PElem>
4. linkL  ==> <link>

      Una vez que el programador cliente ha obtenido sus plantillas, para reutilizarlas las debe instanciar manualmente, usando un editor de textos, para sustituir los nombres genéricos de los identificadores <Binder>, <TElem> <PElem> y <link>, para obtener un módulo de interfaz entre su programa y el módulo List.pas. Por ejemplo, para obtener la implementación del tipo TList_TcharL, hay que hacer las siguientes sustituciones en el código de la Figura 7.34:

1. <Binder> ==> BcharL
2. <TElem>  ==> TcharL
3. <PElem>  ==> PcharL
4. <link>   ==> linkL

      Después de contar con plantillas como la de la Figura 7.34 es natural que el programador cliente del contenedor quiera agrupar todas estas plantillas en un solo archivo, para no tener que reprogramar de nuevo su interfaz para un contenedor parametrizado con Binder.pas. Pero, en realidad, quien debiera hacer todo este trabajo de producir plantillas es quien implementa el contenedor, pues conoce mejor los detalles que hay que tomar en cuenta (como por ejemplo, el manejo especial del puntero NIL para enlazar valores en el contenedor). Corresponde entonces al programador del contenedor Container.pas implementar el archivo de plantillas Container.ctp (CTP: Container TemPlate), para que el programador cliente del contenedor pueda usar un contenedor que sí tiene verificación fuerte de tipos. Por eso, al implementar List.pas, también fue programado el archivo de plantillas List.ctp, que contiene las indicaciones de cómo obtener el contenedor especializado para TList. La plantilla de la Figura 7.34 es una muestra del código que contiene List.ctp.

      Es una ironía que, en Pascal, para obtener un tipo de datos parametrizado, a fin de cuentas el programador cliente termina instanciando a mano una plantilla; en Ada y C++ no ocurriría esto, pues se usarían las facilidades de parametrización del lenguaje para que la instanciación corra por cuenta del compilador, y no del programador. Pero hay una gran diferencia en la labor que se realiza con las plantillas, porque en esos otros lenguajes se usan para implementar los algoritmos del contenedor, pues el proceso de instanciación de estas plantillas genera una copia completa del código para cada tipo, mientras que las plantillas que agregan verificación fuerte de tipos a los contenedores parametrizados con Binder.pas se limitan, básicamente, a ajustar punteros, porque las operaciones del contenedor reciben como argumento los campos de enlace, y no punteros a los elementos almacenados en el contenedor. Ajustar punteros es una labor eficiente que requiere poco esfuerzo porque consiste en hacer unas cuantas operaciones de suma o resta sobre el valor del puntero. Quien implementa algoritmos genéricos usando Ada o C++ debe conformarse con hacer pública su implementación, pues de otra manera no es posible compilar programas; por el contrario, si se implementan los contenedores usando la tecnología de Binder.pas, se puede compartir el código objeto de los algoritmos, y en las plantillas se relega el trabajo de ajustar punteros, como en la Figura 7.32.

      Después de ver cómo pueden hacerse las cosas usando Binder.pas, es fácil ver que las facilidades de parametrización de C++ y Ada no están siendo usadas de la mejor manera, pues el resultado de emplearlas es producir diferentes versiones de la misma operación para cada uno de los tipos que el programador cliente del contenedor requiere. Esto produce programas cada vez más abultados, que tienen muchas copias de las mismas rutinas, cada una adaptada a un tipo de datos diferente.

      Otro gran problema que surge al duplicar código fuente que luego es instanciado para cada uno de los tipos, es que es casi imposible no entregarle al programador cliente el código fuente de la implementación del contenedor, pues el compilador lo necesita para crear la versión de cada operación para cada tipo instanciado. Además, como en cada instanciación el compilador crea una versión diferente del código objeto final, se hace muy difícil compartir el código objeto obtenido. La parametrización que Binder.pas ofrece no tiene ninguna de estas dos limitantes, lo que la hace mejor. Pero, si se usan las facilidades de parametrización de estos lenguajes para obtener los tipos derivados de TList que tienen verificación de tipos en sus argumentos, como es el caso para TList_TcharL, resultarían programas funcionalmente equivalentes pero que comparten el código de todos los contenedores.

      De la discusión del párrafo anterior se concluye que las plantillas que ayudan a agregar verificación fuerte de tipos a los contenedores parametrizados con Binder.pas son mucho más simples, y eficientes, que las usadas en lenguajes que soportan parametrización. Por eso un compilador que no tenga plantillas, pero que sólo incorpore una construcción sintáctica sencilla para transferencia de tipos, puede servir para producir bibliotecas de contenedores más eficientes que las que usualmente están disponibles para lenguajes más avanzados.

      Después de confeccionar las plantillas para el árbol y la lista, principalmente en el contexto del programa UseBind.pas, que sirve para ejercitar las operaciones tanto de la lista como del árbol, surgió la necesidad de automatizar el proceso de instanciación, y contar con un método automatizado para obtener el ligador que se necesita para que un elemento específico pueda ser almacenado en un contenedor. Así nace el programa CTPinst.pas, cuyo nombre es el acrónimo de Container TemPlate INSTantatiator, o sea, de instanciador de plantillas de contenedores. Por medio de CTPinst además se obtiene verificación fuerte de tipos para contenedores parametrizados con Binder.pas.

      Se prodría usar el preprocesador CPP del lenguaje C para parametrizar contenedores en Pascal, de manera similar a como se hace en [Gru-86] para implementar paquetes genéricos en C; de hecho, bibliotecas de contenedores para C++ se han programado de esta manera, como es el caso de Libg++ [Gor-87] y BIDS [BI-92]. En realidad CTPinst es un preprocesador, pero conoce un poco de la sintaxis de Turbo Pascal, pues no trabaja a nivel de macros, como lo hace CPP, sino más bien a nivel de archivos de plantillas ".ctp". Para el programador Pascal esta solución no es muy elegante, pues representa una alteración fundamental del lenguaje pero, después de todo, hay que hacer con lo que se tiene, y no con lo que se quiere.

      De la experiencia obtenida al refinar las implementaciones de la lista, el vector y el árbol, se puede concluir que, en general, lograr una implementación sencilla es relativamente fácil pero, si lo que se necesita es un módulo robusto y reutilizable, el esfuerzo requerido para producirlo se incrementa en uno o dos órdenes de magnitud [FT-96]. Por eso importa mucho evitar entregar el código fuente de la implementación de un contenedor cuando se usa parametrización. Al usar CTPinst para parametrizar contenedor a través de Binder.pas no se incurre en este error, pues las plantillas se usan sólo para obtener un módulo de interfaz a la implementación del contenedor.

      Cuando un programador usa un contenedor parametrizado con Binder.pas, necesita definir el ligador que incluye referencias a las operaciones básicas del elemento contenido. Después de un par de ocasiones, el programador aprende que el proceso es bastante simple, pues se reduce a invocar la operación TBinder.Define() con los argumentos adecuados, que en cada caso se obtienen de observar con detenimiento el elemento para definir básicamente cinco cosas:

1. ¿Cuáles son las operaciones básicas del elemento?
2. ¿Usa o no el elemento métodos virtuales?
3. ¿De qué tamaño es el elemento?
4. ¿Dónde tiene el elemento el campo de enlace del contenedor?
5. ¿De qué tamaño es el campo de enlace del contenedor?

      Para el programador novato puede ser difícil definir todo esto, pero una vez que los valores adecuados para cada uno de los parámetros de TBinder.Define() han sido identificados, sólo resta codificar la invocación cuidando de no cometer ningún error. Este último proceso es muy tedioso, pues es sencillo invertir el orden de los argumentos de TBinder.Define() con lo que puede ocurrir, por ejemplo, que en el lugar en que hay que poner el constructor se ponga el destructor, lo que en tiempo de ejecución resultará en un desastre cuando Binder.pas invoque el método equivocado.

      La solución es usar CTPinst para generar algorítmicamente, a partir de las anotaciones de plantilla del contenedor y del elemento que contendrá, una unidad Pascal que contiene las declaraciones e invocaciones a TBinder.Define() adecuadas.

      El programa CTPinst sirve para crear un caparazón alrededor de un contenedor parametrizable, por ejemplo TList, y obtener una lista especializada en un tipo de elemento, por ejemplo TcharL. Como salida del programa CTPinst, el programador cliente de List.pas obtendrá la unidad Envelope.pas ("envelope" significa "sobre" en inglés), en donde estará declarado el tipo "TList_Tchar_linkL" que corresponde a una lista cuyos elementos son de tipo "TcharL", y que están enlazados por medio del campo "linkL" que aparece dentro de cada elemento. En la Figura 7.31 se usa el nombre abreviado "TList_TcharL" porque no se tomó en cuenta que un mismo valor puede estar almacenado en muchos contenedores, lo que se logra incluyéndole varios campos de enlace diferentes, uno para cada contenedor. El sufijo "linkL" indica a cuál de todos los contenedores corresponde el campo de enlace.

      Es natural usar un empaque para encapsular el acceso a los tipos de un módulo y, de hecho, esta técnica ha sido usada para implementar lenguajes polimórficos. Por ejemplo, en [MDC-91] (pg 350) los autores explican cómo lograr que un lenguaje tenga polimorfismo uniforme si las rutinas manipulan siempre punteros a los valores, lo que efectivamente las convierte en empaques para cada algoritmo. No tiene sentido usar CTPinst si se necesita usar una lista en que los elementos serán de muchos tipos diferentes, pues este programa sirve para especializar la lista en un tipo de elemento fijo: esto es precisamente lo que se logra al instanciar un contenedor, y es esta labor la que realiza el compilador en el caso de los lenguajes Ada y C++. En el caso de Binder.pas, ese efecto se obtiene mediante el programa CTPinst, que no forma parte intrínseca del sistema de compilación ni del ambiente de programación.

      Para generar el archivo de instanciaciones Envelope.pas, CTPinst necesita que el programador cliente defina cuál es el elemento que estará almacenado en un contenedor, y cuál es el campo de enlace que usará. Además, CTPinst necesita saber cómo generar el tipo caparazón para el contenedor. CTPinst necesita que ya esté definido el tipo "TcharL" para usarlo al definir el tipo TList_TcharL_linkL. Finalmente, CTPinst debe ser suficientemente inteligente como para agregar a la unidad Envelope.pas la nueva declaración del tipo TList_TcharL_linkL, labor para la que debe incluir en las partes de interfaz, implementación e inicialización, el código adecuado.

TYPE
  PcharL = ^TcharL;
  TcharL = OBJECT
    linkL: List.TLlink;   { enlace para TList  }
    tlink: Tree.TTlink;   { enlace para TTRee  }
    ch   : CHAR;          { valor del elemento }

    CONSTRUCTOR Init;
    PROCEDURE   Done;

    FUNCTION    IsLess( VAR o: Tchar): BOOLEAN;
    FUNCTION    Equal(  VAR o: Tchar): BOOLEAN;

  END; { Tchar }

       {$IFDEF INSTANTIATE}  {$IFNDEF INSTANTIATE}
TYPE
  List = TEMPLATE (TList)

    INSTANTIATE <TElem> TO TcharL;
    INSTANTIATE <PElem> TO PcharL;
    INSTANTIATE <link>  TO linkL;

    USES CONSTRUCTOR;

    USES Init;    TO Less USES IsLess;
    USES Done;            USES Equal;
  END; { List }
                                 {$ENDIF} {$ENDIF}

      El programador cliente del contenedor sólo necesita definir cuál es el elemento. Para hacer esto, lo más cómodo es incluir las definiciones que CTPinst usa junto a la declaración del tipo de datos, como se muestra en la Figura 7.35. Cuando crea un tipo que deberá quedar almacenado en un contenedor, el programador cliente debe incluir las anotaciones para CTPinst que se encuentran dentro de un bloque de código rodeado por las directivas de compilación:

{$IFDEF INSTANTIATE}  {$IFNDEF INSTANTIATE}
{$ENDIF}              {$ENDIF}

      En la plantilla se define cuál es el nombre del tipo del que debe derivarse el tipo que será generado en Envelope.pas, que en este caso es TList. En las cláusulas INSTANTIATE el programador cliente define cuál es el nombre del tipo de elemento que usará (TcharL), cuál es el nombre del puntero al tipo (PcharL) y cómo se llama el campo de enlace (linkL). Como un mismo elemento puede residir en varios contenedores, entonces el nombre que CTPinst genera para el contenedor es la concatenación de los tres identificadores del contenedor, el elemento y su campo de enlace: TList+TcharL+linkL. El nombre que CTPinst generaría para este mismo elemento en el caso del árbol es "TTree_TcharL_tlink" (con "tlink").

      Las cláusulas USES que siguen en la plantilla son los nombres de los métodos del elemento que hay que invocar a través de Binder.pas. Como el programador del tipo TcharL le implementó cuatro métodos, entonces hay que informarle a Binder.pas cuáles son: TcharL.Init(), TcharL.Done(), TcharL.IsLess() y TcharL.Equal(). El caso del método TcharL.IsLess() es especial, pues no tiene el nombre estándar del método de comparación "Less()", sino "IsLess()". Mediante el verbo "TO" se le informa a CTPinst que para comparar elementos, Binder.pas debe invocar la operación "TcharL.IsLess()" en lugar de invocar "TcharL.Less()". Además, como TcharL.Init() fue declarado con la palabra reservada CONSTRUCTOR, entonces hay que incluir en esta instanciación de la plantilla List.ctp la declaración USES CONSTRUCTOR. Si el destructor del TcharL hubiera sido declarado con la palabra reservada DESTRUCTOR, entonces habría sido necesario incluir la declaración USES DESTRUCTOR. La sintaxis escogida para instanciar plantillas no es la más elegante, pero tiene la virtud de que se parece bastante a una declaración Pascal. Además, sólo se usan dos palabras reservadas nuevas: TEMPLATE e INSTANTIATION.

      Con base en la información contenida en el archivo de plantilla List.ctp y a la que aparece en la Figura 7.35, CTPinst agrega al archivo Envelope.pas la invocación a TBinder.Define() que corresponde a TList_TcharL_linkL. El nombre del ligador que se usa para TcharL es "Binder_TList_TcharL_linkL", nombre que se obtiene anteponiendo la palabra "Binder" al nombre del tipo generado para esta lista. Por último, CTPinst también genera estas dos invocaciones:

Binder_TList_TcharL_linkL.Bind_Equal( @ Tchar.Equal  );
Binder_TList_TcharL_linkL.Bind_Less(  @ Tchar.IsLess );

      La parte más complicada que queda por discutir es la que le corresponde escribir al programador que implementa el contenedor. En el caso de la lista, quien implementa List.pas también debe implementar el archivo List.ctp. Como ocurre con las unidades Pascal, un archivo de plantillas tiene tres partes: interfaz, implementación y código de inicialización.

      En la parte de interfaz lo primero que el programador debe definir son las calidades del campo de enlace. En el caso de la lista, en el archivo List.ctp, aparece una declaración para el tipo "TLlink" inmediatamente después de la palabra reservada INTERFACE, que es el campo de enlace. Luego aparece la claúsula USES, que indica cuáles unidades se necesitan para compilar Envelope.pas, las que en el caso de List.pas son sólo dos: Binder.pas y List.pas. Después de la cláusula USES aparece la plantilla que CTPinst usa para generar la declaración del contenedor especializado para un elemento de datos. Para generar el tipo TList_TcharL_linkL se usa la plantilla "TList_<TElem>_<link>", que entre corchetes incluye la pseudo variable <TElem>, que debe ser sustituida por el tipo de elemento, y <link>, que será reemplazado por el nombre del campo de enlace cuando la instanciación se realice.

      El programador de la plantilla siempre debe usar las pseudo variables <TElem>, <PElem> y <link> para denotar el nombre del tipo de datos a almacenar en el contenedor, el nombre del tipo puntero al elemento y el nombre del campo de enlace, aunque en su archivo ".ctp" puede agregar otras pseudo variables, como <size> o <dim>, las que serán sustituidas por sus respectivos valores al realizar la instanciación. La Figura 7.35 es un ejemplo de una declaración en la que se definen valores para las primeras tres pseudo variables.

      Dado que en el archivo ".ctp" el programador del contenedor define la regla para formar el nombre del tipo instanciado, el programador puede usar la forma de construirlo que le plazca más. Por ejemplo, puede generar el nombre usando la plantilla TList_<TElem> o simplemente L_<TElem>, en lugar del identificador (más largo e incómodo) TList_<TElem>_<link>.

      En la plantilla para la lista definida en List.ctp hay dos tipos para la lista, uno más simple llamado TList_<TElem>_<link>, y el otro llamado TeList_<TElem>_<link> (con una "e"). La diferencia entre uno y otro está en el tipo de argumento que cada uno de los métodos toma, pues en el método TList.LinkAfter(p, elem) para TList_<TElem>_<link> la posición "p" es de tipo "PLlink", o sea, es un puntero al campo de enlace, mientras que para el tipo TeList_<TElem>_<link > (con una "e" que significa Elemento), "p" apunta directamente al elemento. La ventaja del segundo tipo (con una "e") es que, al usar la plantilla, el programador obtiene una lista en la que puede olvidar el concepto de "posición", porque tiene que manipular punteros a los valores, que no son posiciones de la lista.

PROCEDURE TList_<TElem>_<link>.LinkAfter(
  p: PLlink; VAR x:<TElem>);
BEGIN
  TList.LinkAfter( p, x.<link>);
END;

PROCEDURE TeList_<TElem>_<link>.LinkAfter(
  p: <PElem>; VAR x: <TElem>);
BEGIN
  IF p = NIL THEN BEGIN
    TList.LinkAfter(   List.Null,  x.<link>);
  END
  ELSE BEGIN
    TList.LinkAfter(@ (p^.<link>), x.<link>);
  END;
END;

      CTPinst no puede inventar cuál es la implementación para cada uno de los métodos definidos tanto para TList_<TElem>_<link> (sin "e"), como para TeList_<TElem>_<link>. Por eso, en la sección que aparece después de la palabra reservada IMPLEMENTATION en List.ctp debe estar la implementación de cada una de las operaciones de los tipos instanciados. En la Figura 7.36 aparece el código para obtener la implementación de la operación TList.LinkAfter() para las dos versiones de la instanciación de la lista. La diferencia entre estas dos versiones es que, en un caso, el argumento usado es "p" directamente, mientras que, en el otro, hay que bajar hasta el campo de enlace "<link>" al que "p" apunta, para obtener así su dirección: "@ (p^.<link>)". Además, como se discutió anteriormente, la versión del método LinkAfter() que recibe un puntero <PElem> al elemento es menos eficiente, pues tiene que tratar por aparte el caso "p = NIL".

PROCEDURE TList_TcharL_linkL.LinkAfter(
  p: PLlink; VAR x:TcharL);
BEGIN
  TList.LinkAfter( p, x.linkL);
END;

PROCEDURE TeList_TcharL_linkL.LinkAfter(
  p: <PElem>; VAR x: TcharL);
BEGIN
  IF p = NIL THEN BEGIN
    TList.LinkAfter(   List.Null, x.linkL);
  END
  ELSE BEGIN
    TList.LinkAfter(@ (p^.linkL), x.linkL);
  END;
END;

      El resultado de instanciar la plantilla de Figura 7.36 aparece en la Figura 7.37. El trabajo que hay que hacer para ello es muy simple, pues basta sustituir la pseudo variable <TElem> por el nombre del elemento "TcharL", y el pseudo campo de enlace <link> por el nombre específico "linkL". Este trabajo se puede hacer con un editor de textos, pero la ventaja de usar CTPinst es que se elimina la posibilidad de que por error humano el resultado final no sea el correcto.

      A fin de cuentas, CTPinst hace un trabajo realmente muy simple: sustituye unas hileras (<TElem>, <PElem>, <link>) por otras (TcharL, PcharL, linkL). CTPinst genera el nombre del ligador concatenando esos tres identificadores:
      Binder_<TElem>_<PElem>_<link>
      Binder_TList_TcharL_linkL

      Pero también CTPinst tiene la astucia para insertar en la parte de interfaz, implementación e inicialización de la unidad Envelope.pas, el código que corresponde. Este trabajo no es muy diferente al que hace el instanciador de los lenguajes Ada y C++, aunque la ventaja de usar esos otros lenguajes es que, si hay errores en las plantillas, el compilador los señala directamente, mientras que, si se usa CTPinst, el resultado de un error en la plantilla es un archivo Envelope.pas que no compila, y un error que puede ser difícil de interpretar por quien usa un contenedor parametrizado con Binder.pas.

      La implementación de CTPinst no es particularmente eficiente, ni elegante. Consta de un pequeño reconocedor léxico del lenguaje Pascal, que permite procesar las líneas de una plantilla ".ctp" como una secuencia de tokens, pero tiene algunas limitaciones que a veces pueden ser incómodas. Por ejemplo, CTPinst se confunde si aparecen comentarios en la cláusula USES de la interfaz, en donde se definen las unidades que Envelope.pas necesita para compilar (List.pas y Binder.pas en el caso de List.ctp). Además, para marcar el bloque de código de inicialización en una plantilla, se usan las palabras reservadas StartUp_Code_Mark y END_StartUp_Code_Mark, (o STARTUP_CODE_MARK y END_STARTUP_CODE_MARK, como se quiera ver), pues para usar los marcadores de bloque Pascal BEGIN-END habría sido necesario que CTPinst contara con un reconocedor sintáctico ("parser" en inglés) mucho más sofisticado. Si Binder.pas llega a ser un éxito tecnológico, de seguro estas pequeñas incomodidades desaparecerán de las versiones futuras de CTPinst pero, por el momento, este programa tiene varios parches cuya razón de existir es tapar otros parches.

7.7 Uso de los valores almacenados en el contenedor

VAR
  c      : TcharL;
  pL     : PLlink;
  L      : TList;
  BcharL : TBinder;
BEGIN
  L.Push(c.linkL);

  L.Pop(pL);

  BcharL.Define({...});


  BcharL.Print(pL^, OUTPUT);

  L.Erase(BcharL);
END;

VAR
  c  : TcharL;
  pC : PcharL;
  Lc : TList_TcharL_linkL;

BEGIN
  Lc.Push(c);

  Lc.Pop(pC);

  Binder_TList_TcharL_linkL. { !!! }
              Print(pC^, OUTPUT);

  Lc.Element^.Print(pC^, OUTPUT);

  Lc.Erase;
END;

      En la Figura 7.38 se contrastan las dos formas en que se pueden usar los valores del contenedor. La primera consiste en usar una lista genérica, para la que el programador cliente debe manipular los campos de enlace de tipo PLlink, mientras que en la segunda se usa el tipo de acceso "TList_TcharL_linkL", obtenido con el programa CTPinst. En el primer caso, el programador cliente debe instanciar manualmente el ligador "BcharL" (ver Figura 7.11), mientras que en el segundo caso puede usar directamente el ligador "Binder_TList_TcharL_linkL" que queda definido y correctamente inicializado en la unidad Envelope.pas.
      Binder_TList_TcharL_linkL.Print(pC^, OUTPUT); { Feo... }
En este segundo caso, como el nombre del ligador es tan largo, a veces le conviene al programador cliente invocar el método Element() que retorna una referencia al ligador de la lista:
      Lc.Element^.Print(p^, OUTPUT);
Esta forma de invocar las operaciones del elemento contenido es más cómoda que usar el nombre del ligador, pues en el texto del programa se expresa que se están usando las operaciones del elemento, y se deja de lado que, para hacerlo, hay que invocarlas a través de un ligador. Sin embargo, en Pascal hay que pagar un costo por usar esta sintaxis, que es el de invocar la función Element(), que lo único que hace es retornar un puntero al ligador definido en la unidad de interfaz del contenedor.

      También en la Figura 7.38 se puede ver que siempre que el programador cliente necesita usar alguna de las operaciones adicionales del contenedor, debe incluir el nombre del ligador como argumento, lo que puede ser engorroso. Lo contrario no ocurre cuando se usa una plantilla instanciada con CTPinst, pues el tipo de acceso generado incluye métodos para invocar a cada una de las operaciones adicionales del contenedor: este es el caso de la operación Lc.Erase().

TYPE
  TListB = OBJECT (TList)
  PUBLIC
    PROCEDURE Init;
    PROCEDURE Clear;
    PROCEDURE Done;

    FUNCTION  Element    : PBinder;

    PROCEDURE Copy (VAR o: TListB);
    PROCEDURE Clone(VAR p: PListB);
    PROCEDURE Move (VAR o: TListB);
    PROCEDURE Swap (VAR o: TListB);

    FUNCTION  Equal(VAR o: TListB) : BOOLEAN;
    PROCEDURE Load (VAR F: FILE);
    PROCEDURE Store(VAR F: FILE);

    PROCEDURE Delete_All;
    PROCEDURE Print( VAR F: TEXT);
    PROCEDURE Read(  VAR F: TEXT);

  PRIVATE
    binder: ^TBinder;  { descriptor de elementos }
  END; { TListB }

      Algunos programadores querrán disponer de una solución intermedia entre las dos opciones mostradas en la Figura 7.38. Una forma de hacerlo es crear un tipo derivado del contenedor, que tenga un campo extra en el que se almacene un puntero al ligador del contenedor. El tipo TListB (con una "B" al final) de la Figura 7.39 está definido como una extensión de TList, y encapsula las operaciones de la lista que necesitan accesar el elemento contenido. O sea que TListB extiende TList agregándole las operaciones adicionales de la lista. Como convención, se agrega la letra "B" mayúscula al nombre del tipo que incluye la referencia al objeto TBinder que describe el elemento contenido en el contenedor.

VAR
  c      : TcharL;
  pL     : PLlink;
  L      : TListB; { ¡<B>! }
  BcharL : TBinder;

BEGIN
  BcharL.Print(pL^, OUTPUT);
  L.Bind(BcharL);

  L.Push(c);
  L.Pop(pL);

  L.binder^. Print(pL^, OUTPUT); { !! }
  L.Element^.Print(pL^, OUTPUT);

  L.Erase;
END;

      En la Figura 7.40 se muestra la conveniencia de usar la lista extendida TListB (con una "B" al final). Cada instancia de TListB contiene un puntero al ligador "binder" asociado con la lista. Como el método TListB.Element() retorna ese puntero, para usar el valor del elemento contenido se puede usar esta cómoda sintaxis:
      L.Element^.Print(p^, OUTPUT);
Si el programador cliente quiere ahorrarse el costo de llamar la función Element(), puede accesar directamente el ligador así:
      L.binder^.Print(p^, OUTPUT);
Esta segunda forma es más eficiente, pero menos elegante. Además, tiene el inconveniente de que el campo "binder" puede ser cambiado por el programador cliente, lo que va en contra del buen uso del ocultamiento de datos.

      Todavía hay una opción adicional, que en eficiencia es similar a usar el campo "binder" invocando el método Element(), pero que no obliga al programador a sacrificar el ocultamiento de datos. La idea es usar el tipo TBound, definido en la unidad Bound.pas:

• TBound: Este es un tipo auxiliar que se incluye en Bound.pas para facilitarle al programador el acceso a las operaciones que TBinder de la unidad Binder.pas ofrece. El único campo que el tipo TBound contiene es un puntero a un ligador de tipo TBinder.

TYPE
  TListB = OBJECT (TList)
  PUBLIC
    PROCEDURE Init;
    ...
    PROCEDURE Read( VAR F: TEXT );

  PUBLIC
    Element: TBound; { descriptor de elementos }
  END; { TListB }

      La definición del tipo TListB de la Figura 7.39 contrasta con la que aparece en la definición simplificada de la Figura 7.41. En esta última se usa el campo "Element" de tipo TBound, mientras en la primera el campo que apunta al ligador se llama "binder".Como el tipo TBinder incluye como métodos todas las operaciones elementales, y como el campo de TListB se llama "Element", se puede usar una sintaxis más elegante para invocar los métodos de los elementos almacenados en un contenedor. Por ejemplo, para copiar el valor del elemento, la sintaxis que TBound permite usar es la siguiente:
      L.Element.Copy(pNode^, qNode^);
donde "pNode" y "qNode" denotan enlaces, o sea, son punteros a variables de tipo TContLnk, o de un tipo derivado de Binder.TContLnk. El significado de esta línea de código es: copie el valor del "Elemento" de la posición "qNode" del contenedor sobre el denotado "pNode". Esta sintaxis es mucho más clara que usar el tipo "^TBinder" directamente:
      L.binder^.Copy(pNode^, qNode^);

      Como el tipo TBound sólo contiene un campo (el puntero al ligador), la cantidad de memoria requerida para almacenar un campo de tipo TBound es la que se necesita para guardar un puntero. En otras palabras, desde el punto de vista de espacio, es igual definir un enlace al ligador de un contenedor usando un puntero, como en la Figura 7.39, que usar una referencia que contiene el tipo TBound, como en la Figura 7.41.

      TBound es azúcar sintáctico para el cliente de Binder.pas, pues usar Element.Copy(p^,q^) es mucho más mnemónico que la alternativa binder^.Copy(). Sin embargo, como requiere de una indirección para invocar todas las operaciones del ligador, se ha evitado usar la unidad Bound.pas en la implementación de los contenedores; esa unidad fue implementada para cubrir todas las posibilidades pues, si se usa un lenguaje como C++, que puede expandir en línea los procedimientos declarados "inline", entonces todas las ineficiencias asociadas al uso de TBound desaparecen, pero se mantienen sus cualidades. (El programador cliente siempre puede usar el método "^Element()" de TListB).

PROCEDURE TListB.Print(         { EXPORT-ADH }
  {?} VAR F : TEXT    { archivo de impresión }
);
{ RESULTADO
  Imprime el contenido de la lista en "F". }
VAR
  p: ^TLlink;
BEGIN { TListB.Print }
  p := SELF._first;
  WHILE p <> List.Null DO BEGIN
    Element.Print(p^, F);
    p := p^.next;
    Write(F, ' ');
  END;
END;  { TListB.Print }

      La Figura 7.42 es una versión simplificada de la implementación de la operación parametrizada TListB.Print(), en la que se usa Element() para imprimir el elemento contenido. Quien observe por primera vez este código no notará que la lista que se está usando es una lista parametrizada. Esta es una gran ventaja de implementar contenedores parametrizables por medio de Binder.pas, pues le permite al programador reutilizar los programas que hizo en el pasado, que ya han sido depurados por el uso, para crear con poco esfuerzo su biblioteca de contenedores parametrizables. Este es un ejemplo de cómo dos facilidades sintácticas (el uso del tipo TBound por un lado y OOP por el otro), al unirse, proveen un grado de expresividad multiplicativamente mayor que el aporte que individualmente representan; por eso, se justifica el costo de agregarle a Binder.pas el tipo TBound.

PROCEDURE TBound.Init(      { EXPORT }         { ADH }
  {-} VAR slf: TContLnk     { Ligamen del contenedor }
);
{ RESULTADO
  Invoca la operación TBinder.Init(slf), usando el
  ligador asociado a "SELF". }
BEGIN { TBound.Init }
  B^.Init(slf);
END;  { TBound.Init }

      Como el único campo que TBound contiene es un puntero a un TBinder llamado "B", las operaciones de TBound lo que hacen es derreferenciar "B" e invocar el método de TBinder correspondiente. En la Figura 7.43 es la implementación de TBound.Init(slf).

      TBound es un caparazón que cubre el tipo TBinder por lo que incluye algunas operaciones de caracter más que todo cosmético. Es este el caso de TBound.Bind(), que se encarga de asociar al contenedor con un ligador de tipo TBinder. La operación TBound.Compatible() es útil porque dos instancias del mismo contenedor pueden contener elementos de tipo diferente. Si ese es el caso, necesariamente los contenedores estarán ligados a ligadores diferentes. TBound.Compatible() regresa TRUE sólo cuando los dos contenedores están asociados al mismo ligador.

      Una de las razones de que exista el instanciador de plantillas CTPinst es proveer de verificación fuerte de tipos a las listas parametrizadas con Binder.pas. Si se usan listas que incluyen una referencia a su ligador, ya sea como un puntero directo o por medio del tipo TBound, entonces en tiempo de ejecución se puede verificar que los ligadores asociados a dos contenedores sean compatibles. Por ejemplo, la operación TListB.Equal() requiere que los elementos almacenados en las listas que se comparan sean del mismo tipo, y esto sólo puede ocurrir si las dos listas están asociadas al mismo ligador. En otras palabras, al incluir una referencia al ligador en cada instancia del contenedor, es posible verificar compatibilidad de tipos, pero a un costo, pues la verificación se puede hacer en tiempo de ejecución y no cuando el programa es compilado.

      TBinder.Same() retorna TRUE cuando dos ligadores son iguales: se usa como base para implementar TBound.Compatible(), que hace lo mismo. Estas dos funciones se necesitan para asegurar que dos instancias del mismo contenedor tengan elementos del mismo tipo, lo que no siempre ocurre cuando los contenedores son parametrizables. O sea, que Same() y Compatible() son el mecanismo para averiguar en tiempo de ejecución el tipo de los elementos, y se usan en forma similar a TypeOf().

      La variable "Binder.Default_Binder" se usa para inicializar el ligador al que una variable de tipo TBound apunta. Es útil porque permite expresar el hecho de que un contenedor no está asociado a ningún elemento, sin obligar a que el campo de puntero al ligador sea NIL.

7.8 El contenedor Vector parametrizable

      Una forma de demostrar que el paradigma de construcción de contenedores propuesto en este trabajo es, por lo menos, adecuado, es mostrar que se puede usar para definir vectores parametrizables. Como Pascal ya incorpora sintácticamente vectores, la implementación Vector.pas que se discute aquí no brilla por su eficiencia, mas sí por su cualidad de estar parametrizada mediante el módulo Binder.pas.

      Una diferencia fundamental entre el contenedor vector, representado por el tipo TVectorB, y el contenedor lista, en su encarnación tanto de TList como de TListB, es que, para incluir un elemento en el vector, siempre es necesario copiarlo, pues su implementación almacena juntos todos los elementos. En contraposición, la lista enlaza sus elementos independientemente de su localización en la memoria del computador. Por eso, un mismo elemento puede estar almacenado en muchos contenedores diferentes, siempre que cada contenedor enlace a sus elementos, mientras que el mismo elemento puede estar almacenado únicamente en un contenedor que almacene a sus elementos por contigüidad en la memoria del computador. En muchas ocasiones lo que se hace es almacenar punteros a los elementos en el contenedor como una forma de solventar este inconveniente.

      La mayor parte de las operaciones de un vector tienen sentido sólo después de que se sabe qué tipo de elemento contiene. Por ejemplo, en un vector de "N" bytes caben dos veces más elementos de cuatro bytes que elementos de ocho bytes, pues el tamaño del vector se obtiene multiplicando el tamaño de cada elemento, por el número de elementos (si el tamaño del elemento es cero, entonces el vector tiene capacidad infinita). Por esto, las operaciones fundamentales del tipo TVector son pocas y muy simples. Más aún, el valor retornado por estas operaciones siempre es el mismo, pues una instancia del tipo "químicamente puro" TVector necesariamente es un vector vacío y tiene cero elementos. Por eso TVector.Empty() siempre es TRUE y TVector.First() siempre es Vector.Null.

      Para implementar el TVectorB (con "B" al final) se hicieron dos cosas. Lo primero es agregar a los elementos que estarán en un vector el campo de enlace de tipo "TVlink" ("T"ype+"V"ector+"link"): este es la misma técnica utilizado en la lista para enlazarle todos sus elementos. Lo siguiente es incluir dentro de cada instancia de una variable de tipo TVectorB (con "B" al final) el puntero "_pH" que apunta al bloque de memoria de tamaño "_Hsize" en donde están almacenados los elementos del vector; esta implementación se escogió porque permite que los valores del vector estén tanto en memoria dinámica como en la pila de ejecución del programa (esto es similar a lo que se hace en [Hog-90]). La Figura 7.44 es el modelo de la implementación de TVectorB (con "B" al final).

      El nombre "_pH" se escogió concatenando la primera letra de las palabras "pointer" y "Heap", pues lo usual es que el bloque de memoria para el vector esté en memoria dinámica. El identificador "_Hsize" corresponde al tamaño (size) del bloque. Como es el caso para todo arreglo Pascal, los elementos del TVector son almacenados uno tras otro en el bloque de memoria "_pH^", por lo que puede ocurrir que al final del bloque de memoria habrá un sobrante de espacio que siempre será menor que el tamaño de cada uno de los elementos del vector. Por ejemplo, si el bloque "_pH^" tiene _Hsize = 34 bytes de tamaño, y el elemento almacenado es un número LONGINT de cuatro bytes, entonces en el bloque caben exactamente ocho elementos [8 = (34 DIV 4)], o sea, que la capacidad del TVector es de 8 elementos, y hay un sobrante de 2 = 33 MOD 4 bytes al final del vector.

      El campo de enlace del vector "TVlink" siempre es de tamaño cero, por lo que el sobretrabajo de usar un TVector en lugar de un arreglo Pascal [ARRAY] es el tamaño agregado de los campos "_pH" y "_Hsize", más el desperdicio "??" que queda al final del vector. En la Figura 7.44 este sobrante se muestra al final del vector con los símbolos de interrogación "??".

      En TListB no se incluyó un campo de tipo TBound para asociar la lista a su ligador. Más bien se usó el campo "binder" de tipo PBinder = ^TBinder, para tener la posibilidad de invocar directamente los métodos de TBinder sin incurrir en la invocación adicional de un método del objeto TBound. En el caso de TVectorB, sí se ha usado un campo llamado "Element" de tipo TBound, que sirve para las operaciones de los elementos almacenados en el TVectorB. Por ejemplo, para averiguar el tamaño de un elemento hay que invocar el método Size() por medio de Element():
      eSize := aVector.Element.Size;

      En contraposición, como para TListB se ha definido "Element()" como un método, y no como un campo, para averiguar el tamaño de los elementos de la lista hay que usar la siguiente invocación:
      eSize := aList.Element^.Size;

      La diferencia principal es que el método TListB.Element() retorna un puntero al TBinder, por lo que para invocar el método TBinder.Size() es necesario derreferenciar el valor retornado por Element(), agregando el símbolo "^" después de "Element". La forma usada en TListB para asociar cada lista con su ligador es más flexible, pero la usada en TVectorB hace que el código se vea más elegante, pues no hay que ponerle sombrero "^" al identificador "Element". Sin embargo, ambos llamados son equivalentes, pues las dos formas resultan en la invocación de una función antes de que sea ejecutado el método de TBinder que el programador necesita.

      La flexibilidad extra que brinda el definir a "Element()" como un método, sirve para aumentar la eficiencia. Como la eficiencia no es uno de los requerimientos de Vector.pas, queda más sencilla y elegante la implementación de TVectorB si "Element" es un campo de tipo TBound. En la Figura 7.39. se muestra que, para mejorar la eficiencia, en la implementación de List.pas se define "Element()" como un método, y no como un campo de tipo "TBinder". También pudo haberse definido "Element" como se hizo para TVectorB, y el resultado habría sido lo que se muestra en la Figura 7.41.

      Vector.pas tiene todas las operaciones de un ADT elemental. Las otras operaciones importantes de Vector.pas son las siguientes:

• Assign(i, elem.link): Copia el elemento "elem" en la i-ésima entrada del vector.
• Reset(i): Limpia el elemento que está en la i-ésima entrada del vector. Para esto invoca la operación Element.Clear().
• Get(i, v.link): Copia en la variable "v" el valor del i-ésimo elemento del vector.
• Vpos(i): Esta operación es similar a Get(), pero en lugar de hacer una copia del i-ésimo elemento lo que hace es retornar un puntero a ese elemento. Las dos operaciones más usadas del vector son Assign() y Vpos(). El nombre Vpos() ["V"ector+"pos"] se escogió por analogía con el verbo Lpos() de List.pas.
• Vind(link): Es la operación inversa de Vpos(), en la misma forma que TList.Lind() es el inverso de TList.Lpos().
• Pget(i): Es un sinónimo de Vpos(), pero como tiene un nombre parecido a Get(), cuesta menos recordar cuál es su función. Esta operación es similar a Get(), pero en lugar de copiar el i-ésimo elemento lo que hace es retornar un puntero a él. "Pget()" es un acrónimo de "Pointer" y "get", y existe para facilitarle al programador el uso de este contenedor.
• InRange(i): Es una función que regresa TRUE cuando el vector contiene un i-ésimo elemento.
• DIM(i): Esta función es un sinónimo de Count(), y retorna la capacidad del vector. A diferencia de la lista, un vector siempre tiene el mismo número de elementos.

      El tipo de datos TVector que aquí se presenta no tiene la más importante de las cualidades de un ARRAY Pascal, cual es la compacta sintaxis Pascal para usar arreglos A[i] := B[j];. En contraste, para usar los elementos de un TVector es necesario invocar las operaciones TVector.Get(i,x) y TVector.Assign(i,x), que son menos elegantes que la notación Pascal para arreglos. Como Pascal incorpora una construcción sintáctica para usar arreglos de cualquier tipo, los arreglos Pascal son parametrizables. Por eso la implementación de Vector.pas no se ha hecho con el nivel de detalle y eficiencia que sí se pueden encontrar en la lista. (No es erróneo afirmar que toda la maquinaria de Binder.pas sirve, básicamente, para implementar eficientemente una lista parametrizable, y que lo demás viene por añadidura).

      Para aumentar la utilidad de TVectorB, se le ha incorporado una facilidad que permite cambiarle la cantidad de elementos que le caben. La operación TVectorB.ReSize(dim) tiene el efecto de cambiar el tamaño del bloque de memoria asociado al TVectorB para que pueda almacenar exactamente "dim" elementos. También se incluyen las operaciones TVectorB.Grow() y TVectorB.Shrink() para estirar y encoger el vector (como los arreglos Pascal no soportan estas operaciones, puede que el TVectorB sea usado en algo más que esta discusión académica). Todas estas operaciones son onerosas, pues cada vez que son invocadas copian todo el contenido del vector del bloque de memoria viejo al nuevo.

      El TVectorB también incluye las operaciones TVectorB.First(), TVectorB.Last(), TVectorB.Next() y TVectorB.Prev(), que tienen una función similar a las operaciones homónimas de la lista, aunque no es usual que los programadores las usen. Es de esperar que el contenedor vector sea accesado mediante índices directos y que la lista sea usada invocando sus operaciones de recorrido secuencial.

7.9 Apoyo del compilador para parametrizar contenedores

      En Binder.pas se incluye maquinaria para transformar un puntero a un campo de enlace en un puntero al elemento y viceversa. Este trabajo lo realizan los métodos:
      TBinder.Link_to_PObj() y
      TBinder.Obj_to_PLink()
Es precisamente ahí en donde está el hoyo por el que se escurre la verificación fuerte de tipos que protege al programador de enlazar dos elementos de tipo diferente al mismo contenedor, simplemente porque los dos tienen el mismo tipo de campo de enlace.

      Las plantillas que el preprocesador CTPinst usa sirven para crear en el archivo Envelope.pas un nuevo tipo cuya función primordial es transformar punteros a los elementos del contenedor, que genéricamente se representan con el tipo PObj, en posiciones de tipo PClink que son punteros al campo de enlace que el contenedor puede manipular. O sea que todo el trabajo que se realiza dentro de Envelope.pas se reduce a hacer varias transferencias de tipos que sirven para no perder la verificación fuerte de tipos del compilador.

TYPE
  TList    = OBJECT ... END;
  Tmy_type = OBJECT ...   link: TLlink; ... END;

TYPE
  TList_my_type = OBJECT (TList)
    TYPECAST ( Tmy_type : link : TLlink );
  END;

      Dentro de la declaración del tipo TList_my_type en la Figura 7.45 está la construcción sintáctica TYPECAST que propongo incluirle a Pascal. En este caso, TList_my_type es un nuevo tipo derivado de la lista parametrizada TList, pero tiene la peculiaridad de que, si un método de TList recibe un argumento de tipo TLlink, el compilador también permite que se use el campo llamado link de una variable de tipo Tmy_type. El programador puede escoger entonces entre dos maneras de invocar los métodos del contenedor.

VAR
  L   : TList_my_type;
  e,o : Tmy_type;
  p   : PLlink;
 ...
  L.LinkAfter(p, e.link);
 ...
  p := ADDR(e.link);
  L.LinkAfter(p, o.link);
 ...
  p := L.First;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

VAR
  L   : TList_my_type;
  e,o : Tmy_type;
  p   : ^Tmy_type;
 ...
  L.LinkAfter(p, e);
 ...
  p := @e;
  L.LinkAfter(p, o);
 ...
  p := L.TYPECAST( @ L.First );

      En la Figura 7.46 se muestran las dos maneras de invocar los métodos del contenedor que puede usar el programador si el lenguaje incluye TYPECAST. A la izquierda está la forma que no tiene verificación fuerte de tipos. La invocación de la derecha sería traducida por el compilador a la de la izquierda, pues la variable "e" es de tipo Tmy_type, que es el tipo que está especificado en la cláusula TYPECAST del tipo TList_my_type, que es una lista pues es un tipo derivado de TList.

      Cuando el compilador encuentra que no hay concordancia de tipos entre los argumentos de un método y los parámetros con que ha sido definido, entonces trata de lograr la concordancia utilizando la cláusula TYPECAST. Por ejemplo, en el renglón 6 de la parte derecha de la Figura 7.46 no hay concordancia entre el tipo PLlink del método TList_my_type.LinkAfter() y el del argumento "p", que es de tipo "^Tmy_type", por lo que, para lograr la concordancia, y de acuerdo con la cláusula TYPECAST, el compilador debe ajustar el puntero "p" agregándole la distancia a que se encuentra el campo "link" desde el principio de la variable "Tmy_type". Cuando la discordancia no se da en punteros, sino que se da en la variable, gracias a la cláusula TYPECAST el compilador debe sustituir la referencia a la variable por una referencia a su campo de enlace, según se define en la cláusula TYPECAST. Por eso es que el compilador sustituye al argumento "e" por "e.link", que es el tipo adecuado para TList.LinkAfter().

      Una cualidad importante del código de la Figura 7.46 es que el tipo Tmy_type fue derivado directamente de la lista pura TList, y no de TListB (con B al final). Ciertamente esto obligará posteriormente al programador a desligar manualmente uno a uno todos los elementos del contenedor L, pero efectivamente lo libera de la incomodidad que puede representar usar el módulo Binder.pas. Otra manera de decir exactamente esto es la máxima que la Figura 7.47 encierra.

      En el renglón 11 de la parte derecha de la Figura 7.46 está la conversión de tipos del puntero que es una posición en el contenedor en el puntero al elemento que está almacenado en esa posición. Gracias a esta sintaxis deja de ser tan importante que el contenedor cuente con la operación Retrieve() especificada en la Figura 5.10, que transforma una posición del contenedor en el puntero al objeto referenciado.

TYPE
  IOrder = OBJECT (List.Iterator) ... END;
  Tmy_type = OBJECT ...   link: TLlink; ... END;
TYPE
  IOrder_my_type = OBJECT (IOrder)
    TYPECAST ( Tmy_type : link : TLlink );
  END;

VAR
  L : TList_my_type;
  I : IOrder_my_type;
  p : ^Tmy_type;
 ...
  I.Init;
  I.Bind(L);
  WHILE (NOT I.Finished) DO BEGIN
    p := I.Current;
    p^.Print;

    I.Next;
  END;
 ...
  I.Done;

      La Figura 7.48 es un ejemplo de cómo la construcción TYPECAST también permite evitarle al programador la molestia de manipular punteros genéricos al contenedor, y al mismo tiempo protege con verificación fuerte de tipos el código del programa.

      La adopción de la transferencia especializada de tipos como una construcción sintáctica adicional de Pascal dependerá del éxito que Binder.pas tenga en la implementación eficiente de contenedores. La modificación que TYPECAST implica es realmente muy pequeña, por lo que no debería ser difícil convencer a los escritores de compiladores para que la incorporen, más aún si se toma en cuenta que puede haber otras aplicaciones importantes de esta sencilla técnica. El tiempo dirá si vale la pena hacer el esfuerzo.