[UACA]
[<==] [\/] [/\] [==>]


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


Capítulo 6: Operaciones básicas de un iterador

      En la sección 3.5 se discute la utilidad de los iteradores, y se introducen sus operaciones. En este capítulo está la especificación detallada de cada una de ellas.

      En los capítulos anteriores se ha usado la notación de ADT's para especificar cada operación. En este se usa la notación de OOP porque resulta mucho más conveniente para usar iteradores. Para los iteradores la expresividad adicional que agrega OOP sobre la programación procedimental tradicional facilita mucho su uso, y de hecho los torna en una eficiente forma de accesar los elementos almacenados en un contenedor, eficiencia que no se pierde aun cuando el contenedor es parametrizable.

      La idea de usar iteradores no es nueva. Por ejemplo, ya en el año 1977 se hablaba de sus cualidades, específicamente en el contexto del lenguaje Alphard [SWL-77]. En ese trabajo a la operación Next(), que avanza al siguiente valor, la llaman generador. La especificación de cuáles operaciones forman un iterador no fue clara desde el principio, y en algunos casos hasta se llegó a afirmar erróneamente que para usar iteradores es necesario que el lenguaje tenga paquetes genéricos o plantillas como en Ada y C++ [Bis-90]. Los iteradores también han sido usados por la "comunidad Lisp" como excusa para exaltar su lenguaje preferido, en detrimento de los lenguajes no funcionales [Bak-92]. Todo este barullo muestra que son realmente importantes, aunque su estudio no sea incluido en algunos curricula universitarios.

      Las operaciones que conforman un iterador ya han sido definidas en otras obras [Lam-90]; más, aún, lenguajes como CLU incorporan construcciones sintácticas para iterar [LG-86]. Es útil que el lenguaje de programación incorpore construcciones sintácticas para la abstracción de iteración, pero no es estrictamente necesario. Aquí se usa la experiencia adquirida en trabajos anteriores para definir, de forma eficaz y armónica, las operaciones de un iterador:

  1. Init(): Es el constructor del iterador.
  2. Bind(): Es la operación del iterador que se encarga de asociarlo con el contenedor por recorrer.
  3. Finished(): Regresa TRUE cuando ya el iterador ha recorrido completamente el contenedor.
  4. Current(): Retorna el valor actual del iterador, o sea, la posición actual en el contenedor.
  5. Next(): Avanza el iterador a la siguiente posición del contenedor.
  6. Advance(n): Avanza el iterador hacia adelante o hacia atrás. Si n es un número positivo, equivale a invocar Next() n veces.
  7. From(): Avanza el iterador para que la iteración comience a partir de una posición diferente del principio del contenedor.
  8. Range(): Establece un rango de iteración, esto es, delimita un subconjunto de los valores del contenedor que recorrerá el iterador.
  9. Done(): Es el destructor del iterador.

      Una cualidad interesante que tienen los iteradores es que, independientemente de cuál sea el contenedor, la especificación de cualquier iterador siempre es la misma, salvo por supuesto la cláusula que define el orden de recorrido del iterador. Es también debido a esto que en las especificaciones de las operaciones de los iteradores nunca hace falta mencionar cuál es el contenedor que se recorre.

      Un ejemplo de la cláusula ORDEN para un iterador está en la Figura 3.10, en donde se define cuál es el orden en que se recorre el ADT contenedor:

{ ORDEN
  Este iterador permite recorrer el ADT lista desde 
  adentro hacia los extremos.
  - Si L contiene (6,4,2,1,3,5,7), entonces IInOut
    la recorrerá en el orden 1-2-3-4-5-6-7.
  - Si L contiene (5,3,1,2,4,6), entonces IInOut
    la recorrerá en el orden 1-2-3-4-5-6. }
Figura 6.0: Iterador IInOut

6.1 I.Init() [<>] [\/] [/\] [<>]

CONSTRUCTOR Iterator.Init; { EXPORT }     { ADH }
{ RESULTADO
  Inicializa el iterador.
  - "SELF" no queda asociado a ningún contenedor.
  - Para recorrer un contenedor es necesario ligarlo al
    iterador invocando Bind(). }
Figura 6.1: Iterator.Init()

      Como ocurre con los ADT's, es necesario inicializar y destruir los iteradores mediante Init() y Done(). En la Figura 6.1 está la especificación genérica de la operación I.Init(), que tiene la misma función que sus homónimos para ADT's.

      La mayor parte de los iteradores complicados de programar requieren del uso de memoria dinámica, por lo que el constructor y destructor son operaciones necesarias para asegurar el correcto funcionamiento del programa. En la mayoría de los casos, Init() es una operación muy sencilla de implementar, pues basta con ponerles valores nulos a los campos del iterador.

      Como Init() siempre se declara con la palabra clave de Pascal CONSTRUCTOR, el compilador activa las facilidades de polimorfismo que OOP brinda; más aún, todos los métodos de un iterador son virtuales (polimórficos).

6.2 I.Bind(C) [<>] [\/] [/\] [<>]

PROCEDURE Iterator.Bind(   { EXPORT }     { ADH }
  {+} VAR C : TContainer   { contenedor por recorrer }
);
{ RESULTADO
  Asocia el iterador "SELF" con el contenedor que
  recorrerá.
  - Esta operación es el preámbulo necesario para
    recorrer con el iterador el ADT contenedor. }
Figura 6.2: Iterator.Bind(C)

      En la Figura 6.2 está la especificación genérica de la operación I.Bind(C), que asocia el iterador "I" con el contenedor "C" que recorrerá.

Elegante         Alternativo
I.Init           I.Init
I.Bind(L)        I.Bind(L)
I.Finished       I.Finished(L)
I.Current        I.Current(L)
I.Next           I.Next(L)
I.Advance(n)     I.Advance(L,n)
I.From(q)        I.From(L,q)
I.Range(L,p,q)   I.Range(p,q)
I.Done           I.Done
Figura 6.2a: Estilos de iteración

      Bind() es la operación del iterador encargada de asociarlo con el contenedor que será recorrido, y es la única que tiene al contenedor como parámetro. A algunos programadores les gusta que los nombres del contenedor y el del iterador aparezcan en todas la operaciones, como se muestra en la Figura 6.2a. Obligar al programador a repetir el nombre del contenedor en todas las invocaciones al iterador tiene básicamente dos ventajas:

  1. Se ahorra un campo tipo puntero en el Rep de iterador, pues ese campo es necesario en la implementación de las operaciones de iterador para recordar cuál es el contenedor que se está recorriendo.
  2. Como hay mayor redundancia, es posible detectar algunos errores de lógica usando programación defensiva en la implementación del iterador.

      La primera razón no tiene mucho peso, pues en los programas se usan relativamente pocos iteradores, por lo que el ahorro en espacio sería del orden de las decenas de bytes, lo que es claramente innecesario salvo en casos muy, muy especiales: los computadores modernos tienen memorias de millones de bytes.

      La segunda razón tiene un poco más de peso, pero carga innecesariamente la notación. En la mayor parte de los casos el iterador se usa en un contexto en que no es necesaria esta redundancia, como se muestra en la Figura 3.13, pues la invocación a Iterator.Current() y Container.Retrieve() generalmente aparece inmediatamente después del WHILE en que se invoca Iterator.Finished(). De todas maneras, el programador siempre tiene la opción de cambiar su especificación si lo considera necesario.

      Es usual que las operaciones más difíciles de implementar para un iterador sean Bind() y Next(). En general es recomendable que la implementación de Current() sea muy eficiente, pues en ocasiones el programador cliente necesita invocar muchas veces este método. Otra estrategia es que Bind() se encargue de preparar los valores que luego serán retornados, gota a gota, por Next() y Current(). Con frecuencia ocurre que para lograr que el iterador sea eficiente es necesario implementar Bind() y Next() usando estructuras de datos sofisticadas, o métodos de programación alambicados.

      En gran parte, la dificultad de implementar el iterador surge al adaptar la forma natural de recorrer el contenedor al estricto protocolo WHILE / Next() que impone el usar la abstracción de iteración. Si se compara con cuidado el código de la Figura 3.9 (Recorriendo hacia atrás la lista), con el de la Figura 3.13 (Uso del iterador IInOut con OOP), se nota esta disparidad, pues en la primera es necesario anidar el REPEAT dentro del IF precisamente para que, al iterar sobre los valores de la lista, se obtenga de primero al último, y de último el primero. También queda ahí patente que usar iteradores simplifica mucho los programas, pues es mucho más simple entender que el WHILE asegura la precondición de la operación Next() del iterador, que averiguar por qué dentro del IF aparece un REPEAT. Sin embargo, es inevitable que este código complicado aparezca en la implementación de Bind() o Next(); al menos estará oculto detrás de la abstracción de iteración, lo que libera al programador cliente del iterador de invertir esfuerzos para obtener los valores del contenedor en el orden deseado.

      La implementación de un iterador es todavía más complicada cuando hay que transformar un recorrido recursivo en uno iterativo, como ocurre en el caso del procedimiento LRP() para el árbol, en la Figura 3.12. Por eso, para implementar los iteradores del árbol es necesario usar estructuras de datos relativamente complejas, como la pila, y tanto Bind() como Next() tienen que manejar estas estructuras de datos cuidadosamente para lograr la eficiencia que se espera del iterador.

I.Bind(L1); done := FALSE;
WHILE (NOT I.Finished) AND (NOT done) DO BEGIN
  pe := L1.Retrieve(I.Current);
  Procese({+} pe^, {?} done);

  I.Next;
END;

I.Bind(L2);   { <<==<<  debe limpiar I.Bind(L1) }
WHILE NOT I.Finished DO BEGIN
  pe := L1.Retrieve(I.Current);
  ETC({+} pe^);

  I.Next;
END;
Figura 6.2b: Uso consecutivo de I.Bind(L)

      Un requerimiento importante para la implementación de Bind() es que permita iniciar otra iteración aunque la anterior no haya terminado todavía. Muchas veces un iterador se usa un sola vez, pero también ocurre que el mismo iterador se usa varias veces. Si el Rep del iterador usa memoria dinámica, en algunos casos Bind() debe asegurarse de devolver la memoria aun si la iteración anterior no ha terminado. Por ejemplo, en la Figura 6.2b el primer ciclo de iteración puede terminar abruptamente cuando la variable "done" toma el valor TRUE. En este caso, si el Rep del iterador usa memoria dinámica, en la segunda invocación a Bind() [en I.Bind(L2)], hay que retornar adecuadamente la memoria dinámica asignada por la primera invocación [en I.Bind(L1)]: no hacerlo es un error que frecuentemente cometen programadores novatos. Una manera fácil de evitar este escollo es incluir en la implementación del iterador una operación local Clear(), que se encargue de limpiarlo; de esta forma, la primera acción en la implementación de Iterator.Bind() sería invocar Iterator.Clear(). En [DiM-94f] se discute la implementación del iterador OrdVc.pas, que incluye un buen ejemplo de cómo interactúan Iterator.Bind(), Iterator.Clear() e Iterator.Next().

      Como Init() es el preámbulo necesario para poder usar cualquier operación, Bind() sólo se puede invocar después de invocar Init(). Entonces el diagrama de precondiciones para Bind() es el siguiente:

 Init() ==> Bind()

6.3 I.Finished() [<>] [\/] [/\] [<>]

FUNCTION Iterator.Finished { EXPORT }     { ADH }
{>>>>>>} : BOOLEAN;
{ RESULTADO
  Retorna FALSE cuando todavía quedan elementos del
  contenedor por recorrer, y TRUE cuando ya se ha
  terminado de recorrer el contenedor asociado al
  iterador.
  - Si Finished() retorna FALSE, todavía es válido
    invocar Next() o Current().
  - Esta operación nunca cambia el valor del iterador. }
{ REQUIERE
  - El iterador debe haber sido asociado a algún
    contenedor por medio de la operación Bind(). }
Figura 6.3: Iterator.Finished()

      En la Figura 6.3 está la especificación genérica de la operación I.Finished(), que señala cuándo el iterador ha terminado de recorrer el contenedor.

      La operación Finished() retorna un valor booleano que indica si faltan de procesar elementos del contenedor; se usa para establecer la precondición antes de invocar Next() y Current(), por lo que generalmente aparece en el WHILE que encabeza el ciclo de iteración. Finished() puede invocarse cuantas veces sea necesario, pues no modifica el valor del iterador.

      Es usual que la implementación de Finished() sea muy eficiente, tanto en espacio como en tiempo de ejecución, pues el programador puede invocarla cuantas veces quiera en su programa, aunque podría ocurrir que en algunas implementaciones el costo de Finished() fuera más alto. En algunos casos ocurre que la implementación de Finished() es complicada, pues esta función booleana es la que debe lidiar con los casos límite, que a veces no son tan sencillos de manejar.

      El diagrama de precondiciones para la operación Finished() del iterador es el siguiente:

 Init() ==> Bind() ==> Finished()

6.4 I.Current() [<>] [\/] [/\] [<>]

FUNCTION Iterator.Current  { EXPORT }     { ADH }
{>>>>>>} : PCpos;
{ RESULTADO
  Retorna el valor actual del iterador, o sea, la
  posición actual en el contenedor.
  - Esta operación nunca cambia el valor del iterador.
  - Puede ser invocada cuantas veces se quiera sin
    necesidad de avanzar el iterador. }
{ REQUIERE
  - NOT Finished(). }
Figura 6.4: Iterator.Current()

      En la Figura 6.4 está la especificación genérica de la función I.Current(), que sirve para obtener la posición actual del iterador. Al igual que Finished(), esta función nunca debe alterar el valor del iterador, labor que está encomendada principalmente a Next().

      Si en el ciclo de iteración el programador necesita conocer de nuevo la posición actual del iterador, puede obtenerla invocando de nuevo a Current(), pues se le puede invocar tantas veces como sea necesario porque nunca cambia el valor del iterador. Esto es cómodo, pues en ocasiones libera al programador de declarar una variable adicional para recordar dónde está.

      Current() retorna un puntero de tipo "PCpos", y no un puntero al elemento de tipo "PElem", por la misma razón que existe la función Container.Retrieve(): de esta manera se evita crear una dependencia del iterador con los elementos del contenedor. Sin embargo, a veces la implementación del iterador necesita accesar los elementos, como es el caso de un iterador que los retorne ordenados de acuerdo a la función Elem.Less().

      Como Current() sólo puede invocarse si el iterador apunta a una posición válida del contenedor, el diagrama de precondiciones para esta operación debe ser el siguiente:

 Init() ==> Bind() ==> NOT Finished() ==> Current() 

6.5 I.Next() [<>] [\/] [/\] [<>]

PROCEDURE Iterator.Next;   { EXPORT }     { ADH }
{ RESULTADO
  Avanza a la siguiente posición del contenedor, de
  acuerdo al orden definido en la especificación del
  iterador. }
{ REQUIERE
  - NOT Finished(). }
Figura 6.5: Iterator.Next()

      En la Figura 6.5 está la especificación genérica del método I.Next(), que avanza el iterador a la siguiente posición de iteración. Si la implementación de Bind() fue simple, es muy posible que la de Next() sea complicada, y viceversa. Sólo los iteradores muy simples no requieren de complicaciones en la implementación de estas dos operaciones.

      Como se ve en la Figura 6.2b, por lo general la invocación a Next() se pone al final del ciclo de iteración WHILE, el que debe estar resguardado por la invocación a la función Finished(). El diagrama de precondiciones para la operación Next() del iterador es el siguiente:


 Init() ==> Bind() ==> NOT Finished() ==> Current() 
                                      ==> Next()

6.6 I.Advance() [<>] [\/] [/\] [<>]

PROCEDURE Iterator.Advance({ EXPORT }     { ADH }
  {+} n : INTEGER
);
{ RESULTADO
  Avanza el iterador "n" posiciones.
  - Si n>0, su efecto es equivalente a invocar 
    Next() "n" veces sucesivas.
  - Si n<0, en realidad retrocede "-n" posiciones. }
{ NOTA
  A diferencia de Bind(), o Init(), no es necesario 
  que todo iterador tenga esta operación. }
{ REQUIERE
  - NOT Finished(). }
Figura 6.6: Iterator.Advance()

      En la Figura 6.6 está la especificación genérica de la función I.Advance(), que sirva para avanzar a grandes pasos en el contenedor. Esta operación está inspirada en los iteradores aleatorios de la biblioteca STL para C++ (random iterators), que permiten saltar de un lugar a otro dentro del contenedor. Los iteradores aleatorios de C++ han sido diseñados para permitir actualizar el valor almacenado en el contenedor, mientras que los que se describen aquí, no.

      A primera vista parece conveniente que todos los iteradores cuenten con la operación Previous(), por lo menos para implementar la operación Advance(n) para valores negativos de "n". Sin embargo, la implementación de Previous() en muchos casos es muy compleja o requiere gran uso de recursos, tanto de tiempo de ejecución como de memoria. No puede ser obligatorio implementar operaciones que en muchas ocasiones fuerzan al desperdicio: una abstracción debe ser eficiente; de lo contrario está condenada al desuso. Como el método Advance(n) puede tener un alto costo, no es recomendable obligar a que todo iterador lo incluya.

      Como no para todo iterador conviene definir esta operación, a veces el programador deriva del tipo Iterator un nuevo tipo, llamado por ejemplo Iterator_Extra, al que le define esta operación. Esto evita que en el programa objeto final se incluya código para esta operación, o cualquiera de las otras operaciones de iteración opcionales.

      El diagrama de precondiciones para la operación Advance() del iterador es el siguiente:


 Init() ==> Bind() ==> NOT Finished() ==> Current() 
                                      ==> Next()
                                      ==> Advance()

6.7 I.From(q) [<>] [\/] [/\] [<>]

PROCEDURE Iterator.From(   { EXPORT }     { ADH }
  {+} p : PCpos
) {>>>} : PCpos;
{ RESULTADO
  Avanza el iterador hasta la posición "p" del
  contenedor, de acuerdo con el orden del iterador.
  - El iterador queda posicionado en "p", de manera que
    p = Current().
  - El último elemento que el iterador recorrerá es el
    que está al final del contenedor, de acuerdo con
    el orden del iterador.
  - Si "p" no es una posición válida en el contenedor,
    fuerza Finished()=TRUE.
  - Si (p=Null), el iterador avanzará hasta el final
    del contenedor de manera que se cumpla que
    Finished()=TRUE. }
{ NOTA
  A diferencia de Bind(), o Init(), no es necesario
  que todo iterador tenga esta operación. }
{ REQUIERE
  - "SELF" ya debe haber sido asociado a un contenedor
    por medio de la operación Bind(). }
{ COMPLEJIDAD
  << Eficiencia de ejecución >> }
Figura 6.7: Iterator.From()

      En la Figura 6.7 está la especificación genérica de la función I.From(p) que avanza el iterador desde el principio hasta la posición "p".

 VAR
   _done : BOOLEAN;
 BEGIN { From }
   { comienza desde el principio } 
   I.Bind(Container);

   _done := I.Finished;
   WHILE NOT _done DO BEGIN
     IF p = I.Current THEN BEGIN
       _done := TRUE;
     END
     ELSE BEGIN { Avanza }
       I.Next;
       _done := I.Finished;
     END;
   END;
 END;  { From }
Figura 6.7a: Efecto de usar Iterator.From()

      El programador que usa un iterador no siempre quiere que la iteración comience desde el principio, pues necesita comenzar a iterar a partir de un punto específico del contenedor. El efecto de usar From() es equivalente a insertar antes del ciclo de iteración el código de la Figura 6.7a. En muchos casos conviene usar From() en lugar de codificar este ciclo, pues para algunos contenedores es posible implementar esta operación usando una cantidad de esfuerzo constante. Por ejemplo, si el contenedor es un vector, se puede usar directamente el valor del puntero "p", después de verificar que apunta a alguno de los elementos del vector.

      Es usual que para posicionar el iterador en "p" se requiera un esfuerzo significativo. Por eso siempre resulta provechoso mencionar en la especificación cuán costoso es usar From(). En la especificación genérica de la Figura 6.7 se incluye una anotación en este sentido, bajo el encabezado "COMPLEJIDAD".

 I.Bind(Container);

 I.From(p);
 _done := I.Finished;
 WHILE NOT _done DO BEGIN
   pI := I.Current;
   WORK(pI);

   _done := (pI=q);  I.Next;
   _done := _done OR I.Finished; 
 END;
Figura 6.7b: Recorrido de [p..q] con From()

      En la Figura 6.7b se muestra cómo recorrer los valores del contenedor que están en el intervalo [p..q] usando From(). En la condición del ciclo WHILE es necesario incluir la invocación I.Finished() porque no siempre ocurrirá que si se comienza en la posición "p" del contenedor eventualmente se alcanzará la posición "q", pues el que esto ocurra depende del orden en que el iterador recorre el contenedor.

      Para invocar la operación From(), basta que el iterador ya esté ligado a su contenedor, por lo que el diagrama de precondiciones para esta operación es el siguiente:


 Init() ==> Bind() ==> NOT Finished() + ==> Next()
              |                       | ==> Current() 
              + =====> From() ======> +

6.8 I.Range(p,q) [<>] [\/] [/\] [<>]

PROCEDURE Iterator.Range(  { EXPORT }     { ADH }
  {+}      p,q : PCpos     { rango en el contenedor }
  {-} VAR  n   : LONGINT   { # [p..q] }
);
{ RESULTADO
  Establece un rango de iteración.
  - El iterador queda posicionado en "p", de manera que
    p = Current().
  - Retorna la cantidad "n" de invocaciones a Next()
    necesarias para alcanzar a "q" desde "p".
  - Si p=q, retorna cero, a menos que la posición "p"
    no sea una posición válida del contenedor.

  - Si desde "p" no se puede alcanzar la posición "q",
    entonces retorna un valor negativo n<0.
  - Si alguno de "p" o "q" es Null, retorna un número
    negativo.
  - Si alguno de "p" o "q" no es una posición válida
    del contenedor, retorna un número negativo. }
{ NOTA
  A diferencia de Bind(), o Init(), no es necesario que
  todo iterador tenga esta operación. }
{ REQUIERE
  - "SELF" ya debe haber sido asociado a un contenedor
    por medio de la operación Bind(). }
Figura 6.8: Iterator.Range()

      En la Figura 6.8 está la especificación genérica de la operación Range(p,q,n) que sirve para procesar un subconjunto de los elementos del contenedor, en el orden en que lo recorre el iterador.

      Range(p,q,n) se asegura de que si el iterador comienza en la posición "p", exactamente después de "n" invocaciones a Next(), estará en la posición "q" del contenedor. En muchos casos sólo es posible lograr esta certeza recorriendo efectivamente todo el contenedor para constatar que se puede alcanzar "q" desde "p". Por ejemplo, la implementación de esta operación para el iterador BackL.pas de la lista enlazada por punteros requiere recorrer la lista completa buscando "p" y "q" para determinar si denotan una posición de la lista y, además, si desde uno se alcanza el otro.

      A primera vista puede parecer extraño que el tipo del valor "n" que este método retorna no sea un número entero simple, de tipo UNSIGNED o WORD. Sin embargo, aunque lo usual es que la cantidad de valores que un contenedor puede almacenar está acotada por la cantidad de memoria disponible, un iterador puede visitar muchas veces el mismo elemento, por lo que es posible que la cantidad de iteraciones necesarias para cubrir un intervalo de iteración sea un valor que no cabe en una variable de rango reducido. Además, se necesita que la variable tenga signo para denotar el caso en que el intervalo [p..q] es vacío.

 I.Bind(Container);

 I.Range(p,q, n);
 FOR j := 0 TO n DO BEGIN 
   pI := I.Current;
   WORK(pI);

   I.Next;
 END;
Figura 6.8a: Forma de uso de Iterator.Range()

      En la Figura 6.8a se muestra cómo iterar sobre un intervalo [p..q] usando Range(). El estilo de programación usado es diferente del usado para recorrer el mismo intervalo con From(), que está en la Figura 6.7b, pues se puede usar un ciclo FOR para obtener los valores (hay que iterar "n+1" veces para procesar también la posición "q" dentro del ciclo). Cuando se usa From(), hay que manipular con cuidado la variable de iteración "pI", pero Range() tiene la desventaja de que necesita constatar que efectivamente desde "p" se puede alcanzar "q". En ambos casos es necesario invocar la operación Next() para llegar al siguiente elemento de la secuencia. Al usar From(p) no se puede asegurar que la iteración terminará después de procesar al elemento de posición "q", pues puede ocurrir que nunca se le alcance desde "p".

      Si se necesita evitar el costo en que Range() incurre para determinar si el rango [p..q] es no vacío, se puede usar la alternativa de invocar From() como se muestra en la Figura 6.7b, y luego detener la iteración cuando se llega a la posición "q" pues el esfuerzo inicial que usa From() realiza es menor.

 PROCEDURE Iterator.Range(
   {+}      p,q : PCPos;
   {-} VAR  n   : LONGINT
 );

 BEGIN
   From(p);

   IF Finished THEN BEGIN
     n := -1;
   END

   ELSE IF p = q THEN BEGIN 
     n := 0;
   END
   ELSE BEGIN
     n := 0;
     REPEAT
       INC(n);
       Next;
     UNTIL (q = Current) OR Finished; 

     IF q = Current THEN BEGIN
       From(p);
     END
     ELSE BEGIN
       n := -2;
     END;
   END;
 END; { Range }
Figura 6.8b: Implementación de Iterator.Range()

      La Figura 6.8b es una posible implementación de Iterator.Range() que invoca From() dos veces. Para algunos iteradores es muy costoso implementar Range(), por lo que a veces hay que conformarse sólo con From(). Por eso, en la especificación de esta operación claramente se establece que no todo iterador debe contar con ella, pues además de que en muchas ocasiones implementarla es costoso o imposible, muchas veces tampoco agrega funcionalidad alguna al iterador.

      La gran ventaja de iterar usando Range() en lugar de From() es la seguridad de que se obtendrán exactamente los elementos deseados. En muchas aplicaciones, y más aún cuando los contenedores almacenan pocos elementos, la robustez que Range() le agrega al programa bien vale el costo en rapidez que se obtiene respecto a From(). Es el programador cliente quien debe escoger entre estas dos alternativas.

      Para invocar la operación Range() basta con que el iterador ya esté ligado a su contenedor, por lo que el diagrama de precondiciones para esta operación debe ser el siguiente:


 Init() ==> Bind() ==> NOT Finished() + ==> Next()
              |                       | ==> Current() 
              + =====> Range() =====> +

6.9 I.Done() [<>] [\/] [/\] [<>]

DESTRUCTOR Iterator.Done;  { EXPORT }     { ADH }
{ RESULTADO
  Destruye totalmente el iterador "SELF".
  - En general, la destrucción de un objeto consiste
    en devolverle al manejador de memoria dinámica
    toda la memoria dinámica que usa, y cerrar sus
    archivos.
  - El iterador queda inusable, hasta el punto de que 
    la única manera de volver a utilizarlo es 
    reinicializándolo por medio de Init(). }
Figura 6.9: Iterator.Done()

      En la Figura 6.9 está la especificación genérica de la operación I.Done(), que se encarga de destruir el iterador.


 Init() ==> Bind() ==> NOT Finished() + ==> Current() 
   |          |                       | ==> Next()
   |          + =====> From() ======> + ==> Advance()
   |          |                       |
   |          + =====> Range() =====> +
   + =====> Done()
Figura 6.9a: Diagrama de precondiciones de un iterador

      Los iteradores son variables como todas las demás, por lo que necesitan de su destructor. Al incorporar el destructor en el diagrama de precondiciones de los iteradores, el diagrama completo resulta como se muestra Figura 6.9a.

Copyright © 1999 Adolfo Di Mare
Derechos de autor reservados © 1999 Adolfo Di Mare <adolfo@di-mare.com>
[<==] [/\] [<>] [<>] [/\] [==>]