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

      Como un contenedor contiene instancias de sus elementos, para referirse a esas operaciones se usa la notación Elem.OP(), en donde "OP()" es la operación declarada en la unidad Elem.pas. Por ejemplo, para referirse a la operación de copia del elemento TPerson, definido en la unidad Person.pas, se habla de TPerson.Copy(); para la operación de copia, simplemente se habla de Elem.Copy(). A diferencia de los capítulos anteriores, en este se le llama "TElem" al elemento almacenado en el contenedor.

TYPE
  PCpos = ^PCpos; { Localización dentro de TContainer }
  PContainer = ^TContainer;

  TContainer =  OBJECT
    PROCEDURE Init;         { ... operaciones básicas }
    { ... }
    PROCEDURE Read(     {?} VAR F : TEXT);

    FUNCTION  Empty {>>>} : BOOLEAN;
    FUNCTION  Full  {>>>} : BOOLEAN;
    FUNCTION  Count {>>>} : WORD;

    PROCEDURE Behave(   {+} b : TBehave; sw : BOOLEAN);
    FUNCTION  Behaviour({+} b : TBehave)   {>>>} : BOOLEAN;

    PROCEDURE Insert(   {+} VAR o : TElem; {+} p : PCpos);
    PROCEDURE Remove(   {?} VAR p : PCpos);

    FUNCTION  Find(     {+} VAR o : TElem) {>>>} : PCpos;

    FUNCTION  Valid(    {+}     p : PLpos) {>>>} : BOOLEAN;
    PROCEDURE Retrieve( {+}     p : PCpos) {>>>} : PElem;

    FUNCTION  First                        {>>>} : PCpos;
    FUNCTION  Next(     {+}     p : PLpos) {>>>} : PCpos;

  PRIVATE
    { Rep del contenedor }
  END;

CONST
  Null = PCpos(NIL);

5.1 Empty(C)

FUNCTION  Empty(           { EXPORT }     { ADH }
  {+} VAR C : TContainer   { SELF }
) {>>>>>>>} : BOOLEAN;     { ¿Está C vacío? }
{ RESULTADO
  Retorna TRUE cuando el contenedor "C" está vacío. }

      En la Figura 5.1 está la especificación genérica de la operación Emtpy(C), que retorna el valor booleano TRUE cuando el contenedor está vacío. Algunos contenedores nunca pueden estar vacíos, como ocurre con un vector de tamaño fijo (y no nulo).

5.2 Full(C)

FUNCTION  Full(            { EXPORT }     { ADH }
  {+} VAR C : TContainer   { SELF }
) {>>>>>>>} : BOOLEAN;     { ¿Está C lleno? }
{ RESULTADO
  Retorna TRUE cuando el contenedor "C" está lleno. }

      En la Figura 5.2 está la especificación genérica de la operación Full(C), que retorna el valor booleano TRUE cuando el contenedor está lleno, esto es, cuando ya no le cabe ningún elemento más.

      Para cualquier contenedor siempre es posible implementar Empty(), pero en muchos casos es muy difícil implementar Full(), porque si elemento contenido está almacenado en memoria dinámica a veces es muy complicado determinar si todavía queda suficiente memoria dinámica para agregarle un elemento más al contenedor. Por eso, el programador no implementa esta operación para muchos contenedores. Aquí se incluye para que este trabajo quede más completo.

5.3 Count(C)

FUNCTION  Count(           { EXPORT }     { ADH }
  {+} VAR L : TContainer   { SELF }
) {>>>>>>>} : WORD;        { # de elementos de C }
{ RESULTADO
  Devuelve la cantidad de elementos que "C" contiene. }

      En la Figura 5.3 está la especificación genérica de la operación Count(C), que retorna la cantidad de elementos que "C" contiene.

      Para los contenedores simples basta definir una sola versión de Count(), pero otros requieren más versiones. Por ejemplo, para el árbol tiene mucho sentido definir Tree.Count_Children(T,p), que retorna el número de hijos del nodo "p" en "T". Para una cola de prioridad puede tener sentido la operación Queue.Wait_Count(Q,p), que retorna la cantidad de elementos que están adelante de "p" en la cola "Q". Más aún, en algunos casos conviene contar con la función Count_Condition(C,P), que retorna el número de elementos en "C" para los que se cumple el predicado "P".

      También puede ocurrir que el número de elementos de un contenedor siempre sea el mismo, como ocurre con un vector de longitud fija.

5.4 Behave(C,b,sw)

PROCEDURE Behave(          { EXPORT }     { ADH }
  {?} VAR C  : TContainer; { SELF }
  {+}     b  : TBehave;    { Comportamiento para C }
  {+}     sw : BOOLEAN     { TRUE || FALSE }
);
{ RESULTADO
  Define si "C" debe o no tener el comportamiento "b".
  - Si "sw" es TRUE, el comportamiento "b" se agrega
    a "C".
  - Si "sw" es FALSE, el comportamiento "b" se elimina
    de "C". }
{ REQUIERE
  - En algunos casos sólo es posible cambiar el
    comportamiento de una instancia del contenedor
    cuando la instancia no contiene elementos, i.e.
    sólo si Empty(C) = TRUE. }
{ EJEMPLO
  El uso más común de Behave() es el definir, para un
  ADT contenedor, si la inserción se hace usando
  Elem.Copy(), Elem.Move() o Elem.Swap(). En este caso
  se invoca a Behave() de la siguiente manera:
    List.Behave(L, List.Insert_using_Move, TRUE); }

      En la Figura 5.4 está la especificación genérica de la operación Behave(C,b,sw), que sirve para agregar o quitar el comportamiento "b" al contenedor "C", dependiendo del valor de la variable booleana "sw".

      Los contenedores son objetos como cualquier otro, con el atributo adicional de que contienen otros objetos. Por eso muchas veces, al especificar un contenedor, el programador debe incluir otros atributos que sirven para definir los servicios que el contenedor puede brindar. A estos atributos se les llama Comportamientos. Behave() es una manera bastante simple de agregarle algunos de estos atributos al contenedor, y es la operación que sirve para activar o desactivar los servicios especiales que el contenedor ofrece.

UNIT Container;

TYPE
  TBehave = (
    Insert_using_Copy,
    Insert_using_Move,
    Insert_using_Swap,
    Use_More_Pointers,
    Use_Instance_Pointers,
    Destroy_Pointed_Instances,
    Use_Free_Nodes,
    CORRUPTED                     { <== último }
  );
TYPE
  TBehaviour = SET OF TBehave;

TYPE
  RepList = RECORD
    _last : PLpos;      { nodos del contenedor }

    _bhvr : TBehaviour;    { comportamientos }
  END;

      La Figura 5.4a es una amalgama de la definición de los tipos que manipulan las operaciones List.Behave() y Tree.Behave(), cuya implementación se discute en [DiM-94f] y en [DiM-94g]. Los comportamientos disponibles para este contenedor son instancias del tipo escalar Container.TBehave, que se almacenan en un conjunto de tipo Container.TBehaviour. En el Rep del contenedor se incluye un campo, llamado "_bhvr", que sirve para almacenar eficientemente los comportamientos de la instancia.

      En Pascal es muy sencillo implementar el manejo de comportamientos para los contenedores porque el lenguaje incluye primitivas para la manipulación de conjuntos pequeños de escalares. En otros lenguajes se pueden usar operaciones como XOR y AND sobre hileras de bits, o sobre números enteros, para lograr el mismo efecto.

      Los comportamientos ofrecidos por el contenedor dependen mucho del uso que tendrá. La idea de usar comportamientos surge de manera natural al utilizar un contenedor que tiene un alto grado de reutilización, y que por lo tanto debe ofrecer muchos servicios. Por ejemplo, hay varias formas diferentes de insertar un nuevo elemento en un contenedor, como se desprende del examen de las primeras versiones de los contenedores List.pas [DiM-94f] y Tree.pas [DiM-94g]:

1. Crear un nuevo nodo en la memoria dinámica, y luego copiar el elemento en el nodo, invocando a Elem.Copy().
2. Crear un nuevo nodo en la memoria dinámica, y luego trasladar el valor del elemento que se desea insertar al elemento que fue recién creado en memoria dinámica. Para esto se invoca la operación Elem.Move().
3. Duplicar el valor dentro del nodo, invocando a Elem.Clone().
4. Crear un nuevo nodo en la memoria dinámica, y luego intercambiar el valor del elemento que se desea agregar al contenedor con el valor del elemento recién creado en memoria dinámica. Esto se logra con la operación Elem.Swap().
5. Enlazar el elemento directamente en la lista. Este es el método que se usa en la unidad Binder.pas que se discute en un capítulo posterior. Al enlazar el elemento se puede parametrizar el contenedor.

      En lugar de crear varias operaciones de inserción diferentes, una para cada caso, se puede usar una sola, llamada Insert(), pero modificando por medio de una variable de estado la forma en que se realizará la inserción: estas variables de estado son los comportamientos del contenedor. Por ejemplo, se puede definir el comportamiento "Insert_using_Copy" de la siguiente manera: si el contenedor tiene activado este comportamiento, al agregarle un elemento la operación Insert() lo insertará haciendo una copia, invocando la operación Elem.Copy(). Si incluye "Insert_using_Move", usará Elem.Move(), y si no contiene a ninguno de estos dos comportamientos, usará Elem.Swap(). Siempre sería un error que el contenedor tenga activados simultáneamente los dos comportamientos Insert_using_Copy e Insert_using_Move.

      La siguiente es una lista de algunos comportamientos que se pueden usar para la operación Insert(), junto con una pequeña explicación de lo que significa cada uno:

1. Insert_using_Copy: Hace que las inserciones en el contenedor se hagan invocando la operación Elem.Copy().

2. Insert_using_Move: Hace que las inserciones en el contenedor se hagan invocando la operación Elem.Move().
3. Insert_using_Swap: Hace que las inserciones en el contenedor se hagan invocando la operación Elem.Swap().
4. Use_More_Pointers: Este comportamiento sirve para aumentar el número de punteros que se usan en la implementación del contenedor para enlazar los nodos, con lo que se obtiene una mayor eficiencia en tiempo de ejecución a cambio de un poco de espacio.
         Para cada ADT se usa un nombre diferente que corresponde a este comportamiento. Por ejemplo, para la lista este comportamiento se llama Use_Backward_Pointers, que convierte a la lista en una lista doblemente enlazada, para acelerar el rendimiento de la operación List.Prev(). Si el cliente del ADT lista nunca necesita usar List.Prev(), entonces no usará este comportamiento. Lo mismo ocurre con el comportamiento Use_Father_Pointer para el ADT árbol, que hace que en cada nodo se incluya un puntero desde el hijo al padre, con lo que el desempeño de Tree.Father() mejora sustancialmente.
5. Use_Instance_Pointers: Existen dos maneras de incluir un objeto dentro de un contenedor:
   1. Copiarlo dentro del contenedor.
   2. Meter en el contenedor un puntero al objeto.
   
         El comportamiento Use_Instance_Pointers se incluye en el contenedor para que éste almacene, no a los elementos, sino más bien punteros a sus elementos. El almacenar punteros a las instancias en el contenedor tiene las siguientes dos desventajas:
   1. Se requiere espacio adicional para almacenar el puntero a cada objeto. Esta es la desventaja realmente importante de usar punteros a instancias.
   2. Se requiere de tiempo adicional para derreferenciar el puntero al objeto cuando se lo accesa desde el contenedor. Hay quienes afirman que en los procesadores modernos, que tienen arquitectura superescalar, esta desventaja es insignificante en casi todos los casos, mientras otros refutan apasionadamente esta afirmación.
   
         En contraposición, las ventajas de usar el comportamiento Use_Instance_Pointers son las siguientes:
   1. El mismo elemento puede estar almacenado en varios contenedores.
   2. Cuando cambia el valor del elemento, también cambia el valor almacenado en el contenedor.
   3. Si el mismo elemento tiene que estar almacenado en varios contenedores, en conjunto se ahorra espacio porque no hay que duplicar elementos en cada uno de ellos.
   4. El uso de punteros a instancias permite implementar estructuras de datos muy complejas, en donde se usan enlaces entre objetos en formas arbitrariamente abstractas.
   
         El comportamiento Use_Instance_Pointers se usa principalmente en contenedores complejos, pues si lo que el programador necesita es un árbol o una lista pequeña, no tiene sentido que se complique usándolos, pues los punteros son objetos difíciles de manejar, hasta el punto de que una gran parte de la tecnología de OOP sirve para evitar usarlos. Los constructores y destructores, y también los ADT's contenedores, son mecanismos que ayudan al programador a evitar los errores que surgen en los programas que usan punteros y memoria dinámica. No usar punteros es sumamente importante, hasta el punto de que varios lenguajes los han eliminado totalmente (como ocurre con Lisp, CLU y Java), pero a cambio han debido introducir los recolectores de basura, con los inconvenientes en cuanto a eficiencia que conllevan.
6. Destroy_Pointed_Instances: Este comportamiento tiene sentido sólo para un contenedor que tenga el comportamiento Use_Instance_Pointers, pues indica si al destruir el contenedor es también necesario destruir las instancias a las que apunta.
         Este comportamiento se hace necesario porque cuando se usan punteros a instancias, el mismo objeto puede estar en muchos contenedores simultáneamente, pero sólo uno debe estar encargado de destruirlo. De otra forma, el mismo objeto sería destruido varias veces, una por cada contenedor al que pertenezca, lo que llevaría al programa a producir resultados desastrosos.
7. Use_Free_Nodes: Este comportamiento existe en algunos contenedores cuya implementación usa nodos enlazados, que contienen a los elementos del contenedor. La creación o destrucción de un nodo implica invocar el sistema de manejo de memoria dinámica [rutinas de biblioteca NEW() y DISPOSE()]. Si en lugar de tratar de obtener memoria con NEW(), esta memoria se tomara de una lista de bloques de memoria ya asignada de antemano, y en lugar de desasignarla con DISPOSE(), esta memoria se devolviera a esa lista de bloques libres, el trabajo del Insert() y del Remove() se podría reducir a un intercambio de punteros, lo que mejoraría significativamente el desempeño del contenedor. (Esto se logra en la biblioteca STL de C++ usando Allocators [Nel-95]).
         Cuando el contenedor incluye el comportamiento Use_Free_Nodes, Remove() trasladará el nodo borrado a la lista de bloques libres sin necesidad de invocar DISPOSE(), mientras que Insert() reconectará los nodos del contenedor con uno de la lista de bloques libres, sin necesidad de invocar NEW(). Mediante este comportamiento se puede acelerar el rendimiento de las operaciones Insert() y Remove(). A cambio de este incremento de velocidad, será necesario mantener en el contenedor la lista de nodos libres, lo que disminuirá la cantidad de memoria dinámica disponible para el programa.

   PROCEDURE Prepare( { EXPORT } { ADH } {?} VAR C : TContainer; { SELF } {+} n : WORD { # de nodos borrados } ); { RESULTADO Si Use_Free_Nodes está en el comportamiento de "C", después de ejecutar esta operación la lista de nodos libres de "C" contendrá "n" nodos. - En lo posible, se trata de eliminar primero los nodos de más reciente creación, y después los más viejos. O sea, que la lista de nodos libres se maneja como si fuera una pila. } { REQUIERE - Debe haber suficiente memoria dinámica para que esta operación trabaje. }

   Figura 5.4b: Prepare(C,n)

         Para administrar la lista de nodos libres es necesario que el contenedor tenga las operaciones Prepare(C,n) y Count_Del(C). Esta última es una función que retorna la cantidad de nodos disponibles en la lista de nodos libres del contenedor, y Prepare(C,n) se encarga de dejar exactamente "n" nodos en la lista de nodos libres. La Figura 5.4b es la especificación de Prepare(C,n).
         Muchas veces el programador conoce de antemano el número aproximado de elementos que almacenará el contenedor, en cuyo caso lo puede precargar mediante Prepare(), de forma que las operaciones de inserción y borrado se ejecuten rápidamente. Prepare() es una operación que se agrega a un programa que ya es correcto, para mejorar la eficiencia y la utilización de la memoria dinámica del programa.

      Como para todos es difícil leer con detenimiento cualquier tipo de documentación, en especial la que acompaña a los artefactos de programación [Ret-91], es muy importante que el programador escoja con gran cuidado los comportamientos por defecto para su contenedor. El sentido común ayuda a hacer este trabajo de diseño. Para el caso de la forma de insertar elementos en el contenedor, parece mejor que el comportamiento por defecto sea Insert_using_Copy, pues tiene la ventaja de que no modifica el valor del elemento original, como sí ocurre cuando la inserción se hace invocando Elem.Move() o Elem.Swap(). Pero también se puede argumentar que es mejor que por defecto las inserciones se hagan invocando Elem.Swap(), que mejora el rendimiento de los programas, particularmente cuando los objetos almacenados en el contenedor tienen una gran porción de su valor almacenado en memoria dinámica [HW-91]. Para objetos pequeños, como números y letras, conviene más usar Elem.Copy().

      Los programadores tienen una idea simple de los servicios que ofrece un contenedor, y conviene que el comportamiento por defecto del contenedor sea muy similar a esa idea. Si el programador cliente del contenedor necesita algo fuera de lo usual, debe existir una forma especial para obtenerlo. Por ejemplo, lo usual es hacer las inserciones en el contenedor copiando el valor del elemento, y lo especial será hacerlo por medio de Elem.Move(), lo que justifica que el comportamiento por defecto para los contenedores sea Insert_using_Copy. En el caso especial en que el programador cliente del contenedor lo requiera, puede cambiarle el comportamiento a Insert_using_Move.

      Si los comportamientos se implementan con hileras de bits, que es lo eficiente, es conveniente que el conjunto de comportamientos por defecto para el contenedor sea el conjunto vacío, que se representa como una hilera de ceros binarios. Es natural también esperar que tanto Init() como Clear() dejen vacío el conjunto de comportamientos, mas no así Erase(), que vacia el contenedor pero no le cambia los comportamientos.

      Si así se hacen las cosas, se tendría la ventaja adicional de que, si el programador decide implementar Init(), o Clear(), llenando el Rep del ADT de ceros binarios, obtendrá una instancia correctamente inicializada. No hay duda de que esta práctica es impropia, pero existen ambientes en que es necesaria; por ejemplo, en la implementación de programas para máquinas de muy poca memoria [Gre-94].

      Al introducir comportamientos en los contenedores, el especificar sus operaciones es más complicado, pues el Rep necesariamente debe incluir más campos. En el caso de las operaciones Print() y Store(), se hace necesario almacenar también el comportamiento del contenedor. Para Print(), esto hace que la presentación se desmejore, como se muestra en el siguiente ejemplo de la operación List.Print(). Cuando una lista a su vez contiene a otra lista, lo que Print() almacena es lo siguiente:
      (100010: (011100: a b c) (110010: b b) (001100: c a))
Los primeros ceros y unos corresponden a los comportamientos del contenedor, y luego están los valores de los elementos. En este ejemplo la lista contiene tres elementos, y cada uno de ellos es, a su vez, una lista. Si el comportamiento de la lista no fuera impreso por Print(), el resultado sería el siguiente:
      ((a b c) (b b) (c a))
que es mucho más agradable a la vista. Este ejemplo ilustra la dificultad de especificar operaciones genéricas para todos los ADT's, pues lo que a primera vista parece simple es realmente complicado aun para ADT's relativamente sencillos, como List.pas.

      Algunos comportamientos son dependientes o contradictorios entre sí. Por ejemplo, no tiene sentido que un contenedor incluya el comportamiento Destroy_Pointed_Instances si no incluye también Use_Instance_Pointers, pues en este caso no habría instancia que destruir. Tampoco tiene sentido que el contenedor tenga simultáneamente Use_Instance_Pointers e Insert_using_Move, pues, si lo que se inserta en el contenedor es un puntero, no tiene sentido hablar de trasladar el elemento por medio de Elem.Move(). Por eso la implementación de Behave() es a veces complicada, y en muchos casos es necesario que a nivel de especificación se exija que el contenedor esté vacío para cambiarle el comportamiento.

      Sin lugar a dudas, es posible encontrar situaciones en las que el uso de comportamientos para especificar o implementar un contenedor no es adecuado. Lo que sí es importante es conocer la existencia de operaciones como Behave(), que ayudan a definir mejor la abstracción del contenedor: por eso se le ha incluido en este trabajo.

5.5 Behaviour(C,b)

FUNCTION  Behaviour(       { EXPORT }     { ADH }
  {+} VAR C : TContainer;  { SELF }
  {+}     b : TBehave      { comportamiento }
) {>>>>>>>} : BOOLEAN;     { ¿está b en C? }
{ RESULTADO
  Devuelve TRUE si "C" tiene el comportamiento "b". }
BEGIN { Behaviour }
  Behaviour := (b IN C.Rep._bhvr);
END;  { Behaviour }

      En la Figura 5.5 está la especificación genérica de la operación Behaviour(C,b), y también su usual implementación, que consiste en retornar el valor booleano TRUE cuando el contenedor "C" tiene el comportamiento "b".

      Cuando se usan hileras de bits para representar el conjunto de comportamientos de un contenedor, a veces el programador escoge interpretar el conjunto vacío de comportamientos como el conjunto de comportamientos por defecto para el contenedor. En estos casos la implementación de Behaviour() de la Figura 5.5 no puede ser tan simple y eficiente. A veces la robustez de un módulo de programación no se obtiene gratuitamente.

5.6 Insert(C,p,o)

PROCEDURE Insert(          { EXPORT }     { ADH }
  {?} VAR C : TContainer;  { SELF }
  {+}     p : PCpos;       { dónde insertar }
  {?} VAR o : TElem        { elemento a insertar }
);
{ RESULTADO
  Inserta el elemento "o" en la posición "p" del
  contenedor "C".
  - Si "C" tiene el comportamiento Insert_using_Copy,
    el valor de "o" no cambia y en "C" queda una copia 
    de "o".
  - Si "C" tiene el comportamiento Insert_using_Move,
    al insertar "o" se usa Elem.Move(), con lo que el 
    valor original de "o" queda dentro del contenedor.
  - Si "C" tiene el comportamiento Insert_using_Swap,
    para insertar el valor de "o" en el contenedor se
    usa Elem.Swap(), lo que altera el valor de "o". }
{ REQUIERE
  - Valid(L,p).
  - Debe haber suficiente memoria dinámica disponible.
  - Es responsabilidad del programador inicializar
    correctamente los comportamientos de "C". }

      En la Figura 5.6 está la especificación genérica de la operación Insert(C,p,o), que agrega al contenedor "C" el elemento "o" en la posición "p". Sobresale en esta especificación la cantidad de espacio que se usa en comentar los comportamientos del contenedor, lo que, en parte, mueve a algunos programadores a evitar el uso de comportamientos, pues prefieren construir una operación para cada caso: Insert_Copy(), Insert_Swap(), etc.

      Las operaciones que caracterizan a los contenedores son Insert(), para agregar elementos al contenedor, Remove() para eliminarlos, y Find() para localizarlos. Cada contenedor puede realizar alguna, o todas, estas operaciones con diferentes grados de eficiencia, tanto en uso de espacio como en tiempo de ejecución. Los diferentes contenedores existen precisamente por la eficiencia con que realizan estas tres operaciones.

      Como la eficiencia es tan importante, muchas veces en la especificación de estas operaciones se indica su eficiencia. Algunas formas de hacerlo son las siguientes:

• El tiempo requerido para realizar la inserción es O(1).
• El tiempo de inserción es O(log(n)), y el contenedor se mantiene ordenado.
• Si todavía hay más de un 80% de espacio disponible en el contenedor, entonces el tiempo de inserción es O(1). De otra forma, el tiempo será O(n2).

      Es usual que para cada contenedor exista un nombre especial para la operación de inserción: en el caso de la pila, esta operación se llama Push(), para la cola En_Queue(). Para algunos contenedores no es necesario especificar la posición de inserción, tal como en la pila, pues la especificación de Push(S,o) claramente indica que se agrega el elemento "o" en el "tope" de la pila "S", en donde el tope es una posición previamente definida para el contenedor.

      En el caso del ADT lista, la operación de inserción se llama Insert_After(), porque en las implementaciones de lista que usan nodos enlazados siempre es muy fácil hacer una inserción después de un nodo, pero no antes. Este ejemplo es otra muestra de cómo la implementación de un contenedor tiene una gran influencia en su especificación, y aun en la abstracción que le corresponde. Los contenedores existen por la eficiencia con que pueden ser implementados, lo que permea todos los niveles de programación, desde la implementación hasta la abstracción.

5.7 Remove(C,p)

PROCEDURE Remove(          { EXPORT }     { ADH }
  {?} VAR C : TContainer;  { SELF }
  {+}     p : PCpos        { adónde borrar }
);
{ RESULTADO
  Elimina del contenedor "C" al elemento que se
  encuentra en la posición "p". }
{ REQUIERE
  - Valid(C,p). }

      En la Figura 5.7 está la especificación genérica de la operación Remove(C,p), que elimina del contenedor "C" el elemento que está en la posición "p".

      Remove() no es una operación tan importante como Insert(), pues en muchas ocasiones el programador coloca a lo largo del programa elementos en el contenedor, y no necesita sacarlos sino hasta el final del programa. Por eso existen contenedores que son muy eficientes para las operaciones Insert() + Find(), pero cuya operación Remove() no lo es.

      La operación Erase(), también llamada Remove_All() o Delete_All(), se encarga de eliminar todos los elementos del contenedor, pero sin cambiar sus comportamientos. En cambio Clear() debería modificar los comportamientos, para restablecer el estado del objeto que tuvo cuando fue inicializado con Init().

      Es usual que para cada contenedor exista un nombre especial para la operación de borrado: en el caso de la pila, esta operación se llama Pop(); para la cola, De_Queue(). Para algunos contenedores no es necesario especificar la posición de borrado "p", tal como en la pila, pues la especificación de Pop(S,o) claramente indica que se saca el elemento "o" del "tope" de la pila "S", en donde el tope es una posición previamente definida para el contenedor. Más aún, Pop(S,o) es un ejemplo de una operación de remoción que no elimina el elemento del contenedor, sino que más bien lo traslada a la variable "o".

      La especificación para Remove(C,p) de la Figura 5.7 dice que es necesario que se cumpla la condición Valid(C,p), o sea, que "p" indique alguna posición que exista en el contenedor. Para algunos contenedores esta condición debe ser ampliada para que se lea así:

{ REQUIERE
  - Valid(C,p) OR (p=Container.Null) }

5.8 Find(C,o)

FUNCTION  Find(            { EXPORT }     { ADH }
  {+} VAR C  : TContainer; { SELF }
  {+} VAR o  : TElem       { qué buscar }
) {>>>>>>>>} : PCpos;      { posición donde está o }
{ RESULTADO
  Devuelve la posición del elemento "o" en el
  contenedor.
  - Si "o" aparece más de una vez, devuelve la
    posición donde "o" aparece por primera vez.
  - Si "o" no aparece del todo, devuelve
    Container.Null. }

      En la Figura 5.8 está la especificación genérica de la operación Find(C,o), que permite encontrar en el contenedor "C" un objeto igual a "o".

      Find() es una operación que complementa Insert(), pues permite localizar un elemento dentro del contenedor; no tiene sentido meter algo en el contenedor si después no se le puede recuperar. Para encontrar el elemento "o" en el contenedor "C", Find(C,o) necesariamente debe invocar la función de comparación Elem.Equal().

      En la especificación de la Figura 5.8 se dice que cuando "o" no aparece en "C", Find() retorna Null. Esta es una manera de reportar este evento, pero a veces se definen varias operaciones similares a Find() para permitir el acceso usando varios criterios de búsqueda, o para permitir varias maneras diferentes de comunicar condiciones de error. Por ejemplo, una versión de Find() podría aceptar un puntero "PF()" a una función de comparación de elementos, para usar un criterio diferente al de la igualdad. También es posible que "PF()" calcule un coeficiente de similitud con respecto al valor buscado, de manera que Find() encuentre el grupo de valores que tiene, en todo el contenedor, un alto grado de similitud con "o". Otra versión de Find() podría retornar las posiciones de todos los elementos diferentes a "o", o los primeros "n" de ellos.

      Algunos autores encuentran necesario definir la operación mixta Find_Insert() para contenedores, que busca un elemento y, si no lo encuentra, lo inserta en el contenedor [US-94] (pg 8). Esta operación mixta es útil para implementar el ADT conjunto. La gran variedad de formas que puede tomar Find() muestra lo útil que es en la práctica esta operación.

5.9 Valid(C,p)

FUNCTION  Valid(           { EXPORT }     { ADH }
  {+} VAR C : TContainer;  { SELF }
  {+}     p : PCpos        { posición  a validar }
) {>>>>>>>} : BOOLEAN;
{ RESULTADO
  Retorna TRUE si "p" es una posición válida en el
  contenedor "C", o sea, si existe algún elemento en "C"
  cuya posición es "p".
  - Si p = Container.Null retorna FALSE.
  - Si Valid(C,p) ==> Retrieve(C,p) es correcto. }

      En la Figura 5.9 está la especificación genérica de la función Valid(C,p), que retorna TRUE cuando "p" es una posición que existe dentro del contenedor "C", y FALSE en caso contrario.

      El buen programador nunca debería necesitar invocar esta operación, pues siempre debería saber si las posiciones que está usando son válidas o no. Sin embargo, en la práctica a veces Valid() ayuda a aislar errores de programación que de otra manera sería mucho más difícil corregir.

      Como Container.Null es un valor que denota una posición que no existe en ningún contenedor, entonces Valid(C,Null) siempre debe ser FALSE.

5.10 Retrieve(C,p)

FUNCTION  Retrieve(        { EXPORT }     { ADH }
  {+} VAR C : TContainer;  { SELF }
  {+}     p : PCpos        { Posición en C }
) {>>>>>>>} : PElem;       { @TElem }
{ RESULTADO
  Regresa como valor de la función un puntero al
  elemento contenido en la posición "p" del contenedor
  "C". }
{ REQUIERE
  - Valid(C,p) AND (p<>Null). }

VAR
  pn : PNode;                   { puntero a un nodo }
BEGIN { Retrieve }
  pn       := PNode(p);         { cambio de tipos: ¡FEO! }
  Retrieve := ADDR( pn^.elem ); { devuelve el puntero    }
END;  { Retrieve }

      Para que se pueda dar la parametrización del contenedor debe existir una gran separación entre el contenedor y su elemento contenido. Esta independencia funcional se logra con una operación del contenedor que se encargue de traspasar la barrera que lo separa de su elemento contenido. La operación encargada de hacer este trabajo es Retrieve(C,p), cuya especificación está en la Figura 5.10 (en la parte inferior está la implementación usual de esta operación).

      Las operaciones básicas del elemento contenido son suficientes para manipularlo desde el contenedor. Para usar el contenedor, el programador cliente utiliza posiciones, que son los valores con que puede recorrer el contenedor. Retrieve() tiene la función de transformar esas posiciones, de tipo PCpos, en punteros a los valores almacenados en el contenedor, de tipo PElem, que son los que necesita el programador cliente para usar los valores que están almacenados en el contenedor.

      Retrieve() es una función importante porque sirve para implementar el contenedor sin que sea obligatorio accesar todas las operaciones del elemento contenido: así se logra que la implementación sea genérica y reutilizable

      Un examen de la Figura 3.6 muestra que Retrieve() e Insert() (Figura 5.6) son las únicas operaciones del contenedor que manipulan un parámetros de tipo TElem, el tipo que define el elemento contenido en el contenedor. Esto muestra que la cohesión entre el contenedor y su elemento contenido es baja, lo que ayuda a la modularización.

TYPE
  PNode = ^TNode;
  TNode =  OBJECT  { nodo del contenedor }
    elem :  TElem; { valor almacenado    }
    next : ^TNode; { posición del siguiente }
  END

      En la implementación de Retrieve(), en la parte baja de la Figura 5.10, se usa la expresión PNode(p) para transformar la variable "p", que es un puntero de tipo PCpos, para que el compilador lo use como si fuera de tipo PNode_Rep, que es un puntero a uno de los nodos que se usan para implementar el contenedor. En este contexto se supone que las posiciones en el contenedor son punteros abstractos que referencian nodos, los que a su vez contienen un campo, llamado "elem", en donde está almacenado el elemento, como en la Figura 5.10a. Después de la transferencia de tipos, en la implementación de Retrieve() se toma la dirección del campo que contiene el elemento dentro del nodo mediante la función de biblioteca ADDR(), la que luego se regresa como valor de la función.

      Retrieve() es un ejemplo de una ineficiencia que se introduce en aras de mantener la abstracción y el ocultamiento de datos, pues el trabajo efectivo de esta función es cambiarle el tipo a un puntero, por lo que el costo adicional de invocar una función se puede ver como un costo adicional excesivo. Sin embargo, si el compilador tiene la facilidad de desarrollar el código de las funciones en línea, como ocurre en C++ (inline), esta ineficiencia desaparece. En Pascal todavía no hay compiladores que manejen funciones en línea, pero es posible que al evolucionar el lenguaje eventualmente lleguen a ser parte del estándar.

      En la especificación de Retrieve(C,p) se exige que Valid(C,p) sea TRUE, pues de lo contrario "p" no sería un posición en el contenedor, por lo que no denotaría ningún elemento. Por eso también debe cumplirse que p<>Container.Null, pues Null es un valor que denota una posición que no existe en ningún contenedor, por lo que no puede denotar ningún elemento.

5.11 Next(C,p)

FUNCTION  Next(            { EXPORT }     { ADH }
  {+} VAR C : TContainer;  { SELF }
  {+}     p : PCpos        { Posición en C }
) {>>>>>>>} : PCpos;       { Siguiente posición }
{ RESULTADO
  Regresa la posición que sigue a "p" en el
  contenedor "C". }
{ REQUIERE
  - Valid(C,p). }

      En la Figura 5.11 está la especificación genérica de la función Next(C,p), que se usa para recorrer los valores del contenedor, de uno en uno. Next() es un representante de una gran familia de operaciones que sirven para desplazarse a lo largo y ancho del contenedor. Las diferentes formas en que es posible recorrer los valores almacenados en el contenedor dependen de las cualidades de su estructura de datos. Por ejemplo, para la lista tiene sentido avanzar hacia adelante con Next(), o retroceder con Prev(). Para el árbol se puede subir hacia el padre con Father(), o trasladarse a uno de los hijos de un nodo con Child().

      A los recorredores se les puede dividir en dos tipos: relativos y absolutos. Los recorredores relativos son los que permiten cambiar de posición de acuerdo a una posición actual o base, como es el caso en Next(L,p) y Prev(L,p) en la lista, o Father(T,p) y Child(T,p,n) para el árbol. Los absolutos son los que siempre retornan la misma posición del contenedor, como First(L) y Last(L) en la lista o Root(T) en el árbol (los recorredores absolutos no necesitan del argumento "p" que aparece en la Figura 5.11).

      En esta especificación genérica de los recorredores se dice que la posición base debe ser válida, pero en algunos casos este requerimiento no es esencial. Por ejemplo, es perfectamente válido definir el comportamiento de Next(C, Null) si se quiere que al llegar al final del contenedor con Last() se vuelva a comenzar desde el principio; Null en este caso marcaría la transición desde el último al primer elemento del contenedor.

      Después de usar cualquier operación de posicionamiento, el programador cliente del ADT tiene que invocar la función Retrieve() para accesar directamente un elemento del contenedor, pues los recorredores siempre retornan una variable de tipo PCpos.

      Para algunos contenedores puede que no tenga sentido definir este tipo de operación. Por ejemplo, para la pila sólo tiene sentido obtener el elemento que está en el tope. Puede también ocurrir que, aunque sea posible especificar la operación recorrido, sea muy difícil o ineficiente implementarla.

      Si un contenedor tiene "n" elementos, entonces hay al menos n! diferentes formas de recorrerlo. Este número aumenta si se permite visitar a cada elemento más de una vez. En general, a cada contenedor le corresponde una forma "natural" de recorrido, que es la que el programador implementa en su función Next(). Pero si esta forma no es suficiente, el programador cliente del ADT tiene todavía acceso a los iteradores, que precisamente son abstracciones que permiten recorrer un contenedor de muchas formas diferentes.

5.12 Prev(C,p)

FUNCTION  Prev(            { EXPORT }     { ADH }
  {+} VAR C : TContainer;  { SELF }
  {+}     p : PCpos        { Posición en C }
) {>>>>>>>} : PCpos;       { Posición anterior }
{ RESULTADO
  Regresa la posición que precede a "p" en el
  contenedor "C". }
{ REQUIERE
  - Valid(C,p). }

      En la Figura 5.12 está la especificación genérica de la función Prev(C,p), que se usa para recorrer los valores del contenedor, de uno en uno, pero hacia atrás. Prev() es el inverso de la operación Next() y sirve para desplazarse dentro del contenedor en dirección inversa a Next(). Para muchos contenedores no tiene sentido la operación Next() o Prev(). Pero puede ocurrir que para un contenedor sea válido definir Prev() aunque no Next(). Este es el caso del árbol, pues retroceder en este contenedor puede definirse como subir hacia el nodo padre con Father(). La definición de Next() no es tan simple, pues para cada nodo hay que escoger uno de los hijos como el siguiente.

      Como ocurre con la operación Next(), para algunos contenedores no tiene sentido definir Prev(C, Null), o Prev(Next(C, Null)), o sea el elemento previo al primero. Pero, al especificar el ADT, muchas veces para el programador es cómodo, o por lo menos no es inconsistente, definir el significado de avanzar o retroceder en los extremos del contenedor.