Universidad de Costa Rica Escuela de Ciencias de la Computación e Informática

Se muestra cómo es posible utilizar iteradores Java para contenedores de la biblioteca estándar C++, los que son más simples que los usados usualmente en programas C++.

We show how to use Java iterators for the C++ standard library containers, which are simpler than those usually used in C++ programs.

Introducción

Introduction

Abstracción es una concepto mencionado cuando se habla de construcción de programas pues no es posible producir algo sin antes tener una idea, aunque sea muy general, que defina aquello que se desea crear. El estudioso de la programación conoce las formas de abstracción que se usan para programar: abstracción de datos, abstracción de procedimientos, abstracción de iteración y abstracción de jerarquías de tipos de datos [LG-2000]. Es fácil dejar de lado la abstracción de iteración porque su implementación se hace usando abstacción de datos, pero eso no le disminuye su importancia.

Abstraction is a concept mentioned when talking about building programs because it is not possible to produce something without having an idea first, although very general, to define what it is to be created. The studious of programming knows which abstractions are used to program: data abstraction, procedural abstraction, iteration abstraction, and data type hierarcal abstraction [LG-2000]. It's easy to ignore iteration abstraction because it is implemented using data abstraction, but that does not diminishes its importance.

El uso de la abstracción de iteración en la construcción de programas no es reciente, y ya se ha discutido mucho cómo se debe incorporarla en un lenguaje de programación [Parnas-1983]. Las ideas que han sido implementadas van desde la propuesta de los generadores de Alphard [SW-1977], o los iteradores [MOSS-1996], hasta construcciones más recientes como las propuestas para Chapel [JCD-2006]. También se ha argumentado que es necesario especificar iteradores para poder facilitar el razonamiento sobre la correctitud de los programas [Weide-2006]. Si se pone en el iterador la inteligencia para partir una tarea en pedazos que pueden resolverse concurrentemente, se puede usar la abstracción de iteración para aumentar el paralellismos de los programas usando técnicas como "MapReduce" [DG-2004] (cliente-servidor o maestro-esclavo), y también se puede usar iteradores sobre conjuntos como se hace en el modelo de programación Galois [KPWRBC-2009].

The use of iteration abstraction for program construction is not recent, and much has already been discussed on how to incorporate it into a programming language [Parnas-1983]. The ideas that have been implemented, ranging from the proposed generators for Alphard [SW-1977], or iterators [MOSS-1996], to more recent constructions as those proposed for Chapel [JCD-2006]. It has also been argued that it is necessary to specify iterators in order to facilitate reasoning about the correctness of programs [Weide-2006]. If the intelligence to split a task into pieces that can be solved concurrently is in the iterator, the iteration abstraction can be used to increase the concurrency of programs using techniques such as "MapReduce" [DG-2004] (client-server or master-slave), or by using set iterators as it is done in the Galois programming model [KPWRBC-2009].

La popularidad actual de los lenguajes Java y C++ saca a relucir 2 maneras de implementar la abstracción de iteración. Usando sobrecarga de operadores y plantillas, los iteradores C++ se ven como punteros con los que se accede a los valores de una colección. Java toma un camino más a tono con la Programación Orientada a los Objetos y representa un iterador como una clase externa, que contiene 2 operaciones fundamentales: { hasNext() next() }. Los iteradores Java son una realización concreta de ideas bien discutidas [ZC-1999] o [Eckart-1987], con la gran cualidad de que estos iteradores son muy simples lo que facilita su especificación y uso. Java no incluye contrucciones sintácticas especiales para iteración debido a que la pareja { hasNext() next() } es adecuada para implementar tanto iteradores como generadores. Por ejemplo, a diferencia de los iteradores CLU [LSAS-1977], los iteradores Java sí permiten doble iteración sobre una colección, como se muestra más adelante en la implementación genérica del método "isPalindrome()" (ver Figura 3).

The current popularity of Java and C++ brings out 2 ways to implement the iteration abstraction. Using operator overloading and templates, C++ iterators act as pointers used to access values from a collection. Java is more in tune with Object Oriented Programming and represents an iterator as an external class that has 2 basic operations: { hasNext() next() }. Java iterators are a concrete realization of ideas well discussed [ZC-1999] or [Eckart-1987]; a great quality of these iterators is that they are very simple which facilitates their specification and usage. Java does not include special syntactic constructions for iteration because the pair { hasNext() next() } is adequate to implement both iterators and generators. For example, unlike CLU iterators [LSAS-1977], Java iterators do allow double iteration over a collection, as it is shown later in the generic implementation of method "isPalindrome()" (see Figure 3).

Todos estos argumentos sirven para afirmar que hay consenso en que la abstracción de iteración es necesaria para construir programas. En el contexto del lenguaje C++ se puede avanzar en el uso de la abstracción de iteración al incorporar el patrón de iteración Java en el uso cotidiano del lenguaje, tanto al construir programas como al usar la biblioteca estándard de C++. En este trabajo se demuestra que C++ tiene suficiente poder expresivo para que cualquier programador use iteradores o generadores que siguen el patrón de lo iteradores de Java. Adicionalmente, el compilador C++ puede verificar que un objeto marcado "const" sea modificado, lo que disminuye los problemas que se han detectado para iteradores implementados en otros lenguajes [HPS-2002]. La solución propuesta aquí es simple y compacta, pues la implementación completa cabe totalmente en un el archivo de encabezado "iterJava.h", lo que facilita mucho la incorporación del patrón de iteración en programas C++ porque basta incluir ese archivo de encabezado para usar iteradores { hasNext() next() } en C++ (por eso no es necesario ligar ninguna biblioteca adicional al programa C++).

All these arguments are used to assert that there is agreement that the iteration abstraction is needed to build programs. In the context of the C++ language it is possible to advance in the use of the iteration abstraction by incorporating the Java iteration pattern in the daily use, both to build programs an with the C++ standard library. In this paper it is shown that C++ has enough expressive power for any programmer to use iterators and generators that follow the Java iterator pattern. Additionally, the C++ compiler can verify that an object marked "const" is not modified, reducing the problems that have been identified for iterators implemented in other languages [HPS-2002]. The solution proposed here is simple and compact as the complete implementatio fits in a single header file "iterJava.h", which greatly facilitates the incorporation of the iteration pattern in C++ programs because its enough to include this header file to use the { hasNext() next() } iterators in C++ (this is why it is not necessary to link any library to the C++ program).

Uso de iteradores

Iterator usage

Para usar iteradores Java en C++ basta crear un envoltorio C++, en la forma de una plantilla, que permita usar los iteradores Java para los contenedores C++ más populares. Las operaciones de un iterador Java son las siguientes [Java-2009]:

As Java iterators are very simple, it is a good idea to be able to use them in C++. To achieve this goal its is enough to create a C++ wrapper, as a template, to access the more popular C++ containers with Java iterators. The operations of a Java iterator are these [Java-2009]:

hasNext() Retorna "true" hasta que la iteración haya terminado. next() Retorna el siguiente valor de la iteración. remove() Elimina del contenedor el valor recién retornado por "next()".

hasNext() Returns "true" until the iteration is finished. next() Returns the next iteration value. remove() Removes from the container the value recently returned by "next()".

Para recorrer cualquier contenedor de la biblioteca estándar C++ se requiere utilizar 2 iteradores [Str-1998]. El primero indica cuál es el siguiente valor del contenedor que será usado y el segundo es una marca fuera del rango a recorrer. El ciclo de iteración C++ ha concluido cuando el primer iterador alcanza al segundo.

To traverse any C++ standard library container 2 iterators are required [Str-1998]. The first references the next value in the container to be used and the second is a mark outside the iteration range. The C++ iteration cycle is completed when the first iterator reaches up to the second.

{ // [0] [1] [2] [3] [4] [5] int V[] = { 0 , 1 , 2 , 3 , 4 }; int *it = &V[0]; // it = V+0; int *itEND = &V[5]; // itEND = V+dim(V) for ( it = &V[0]; it != itEND ; ++it ) { std::cout << (*it); } }

Figura 1

Los iteradores de la biblioteca estándar C++ funcionan como un puntero a un vector. En la Figura 1 el puntero "it" es el que sirve para acceder a cada uno de los valores del vector. En cada iteración, el valor de "it" aumenta para acceder el siguiente valor del contenedor hasta que, eventualmente, "it" denota un valor que está fuera del rango de iteración, lo que ocurre cuando alcanza a "itEND" que es el punto de quiebra del ciclo.

C++ standard library iterators work as a pointers into a vector. In Figure 1, pointer "it" is used to access each value in the vector. In each iteration, the value of "it" increases to access the next value in the container until, eventually, "it" denotes a value that is outside the iteration range, which happens when it reaches "itEND" where the cycle is broken.

// Java static void useIterator( java.util.Collection C ) {  java.util.Iterator iter = C.iterator(); while ( iter.hasNext() ) { System.out.print( iter.next() ); iter.remove(); } }

// C++ template <class Collection> void useIterator( Collection& C ) {  iterJava< typename Collection::iterator > iter( C.begin(), C.end() ); while ( iter.hasNext() ) { std::cout << iter.next(); C.erase( iter ); // C.erase( iter.current() ); } }

Figura 2

Para obtener los valores almacenados en un contendor con un iterador Java basta usar sus operaciones, como se muestra en la parte superior de la Figura 2. El método "hasNext()" indica si todavía quedan objetos por acceder y "next()" obtiene el siguiente valor. Opcionalmente, es posible eliminar de la secuencia el valor recién obtenido con "next()" invocando el método "remove()".

To get the values stored in a container with a Java iterator it is enough to use its operations, as it is shown in the upper part of Figure 2. Method "hasNext()" indicates whether objects are still accessible, and "next()" gets the next value. Optionally, it is possible to delete from the sequence the value just returned by "next()" invoking method "remove()".

Los iteradores C++ vienen en varios sabores diferentes: constantes o mutables y hacia adelante o hacia atrás. Por eso existen 4 clases de iteradores: "iterator", "const_iterator" y "reverse_iterator". La ventaja principal de este tipo de iteradores es que permiten lograr una gran independencia entre los algoritmos y los contenedores, pues la biblioteca estándar C++ incluye muchos algoritmos implementados como plantillas que usan iteradores en lugar de usar los contenedores. Como estos iteradores C++ han sido construidos de una forma tan completa y exhaustiva, la implementación de iteradores Java para C++ se simplifica mucho, hasta el punto que basta una sola clase de plantillas "iterJava<>".

C++ iterators come in different flavors: constant or mutable and forward or backward. So there are 4 types of iterators: "iterator", "const_iterator", "reverse_iterator" and "const_reverse_iterator". The main advantage of these iterators is that they achieve a high degree of independence between algorithms and containers, as the C++ standard library includes many algorithms implemented as templates that use iterators instead of containers. As C++ iterators are very comprehensive and thorough implementations, the task of implementing Java iterators for C++ is simple, to the point that the single class template "iterJava<>" is enough.

Decisiones de diseño para la clase "iterJava<>"

Design decisions for the "iterJava<>" class

Lograr que los iteradores C++ se usen de la misma manera en que se usan los iteradores Java es el criterio más dominante al decidir entre las diferentes alternativas de diseño disponibles. Por eso es necesario seguir la interfaz java.util.Iterator en la que están definidas las 3 operaciones que tiene cualquier iterador Java { next() , hasNext() , remove() }. Además, en la clase "iterJava<>" se incluyen la operación "set()" para usar el mismo iterador en otra iteración y "current()" para obtener el valor actual de iteración, que es el que la última invocación de "next()" retornó.

Making the use of C++ iterators similar to Java iterators is the most dominant criteria in deciding among the different design alternatives available. This makes it necessary to follow the java.util.Iterator interface where the 3 operations common to all Java iterators are defined { next() , hasNext() , remove() }. Furthermore, class "iterJava<>" includes the operation "set()" to use the same iterator in another iteration and "current()" to get the current value of iteration, which is what the last invocation of "next()" returned.

No es usual que un iterador Java incluya la operación "current()", posiblemente porque los objetos Java son referencias, por lo que si el programador Java necesita conservar el valor que la última invocación de "next()" retornó basta que lo almacene en alguna variable temporal:       Object tmp = iter.next();

It is unusual for a Java iterator to include operation "current()", possibly because the Java objects are references, so if the Java programmer needs to keep the value of the last invocation of "next()" would return it is enough to store it in some temporary variable:       Object tmp = iter.next();

template <typename C> bool isPalindrome( const C& CCC ) {{ typedef typename C::const_iterator IterFwd; typedef typename std::reverse_iterator<IterFwd> IterBck; iterJava< IterFwd > itFwd( CCC.begin(), CCC.end() ); iterJava< IterBck > itBck( CCC.rbegin(), CCC.rend() ); while ( itFwd.hasNext() && itBck.hasNext() ) { if ( itFwd.next() != itBck.next() ) { return false; } } return ( !itFwd.hasNext() && !itBck.hasNext() ); }}

Figura 3

En la Figura 3 se muestra cómo es posible recorrer el mismo objeto contenedor usando 2 iteradores. Debido a que cada iterador es un objeto, puede mantener su estado sin interferir con otros objetos. Además, el compilador es el encargado de verificar que estos iteradores son constantes que no pueden modificar el objeto recorrido. A diferencia de Java, el lenguaje C++ tiene bien definido el uso de "const" para que el compilador impida que el programador modifique un objeto cuyo valor no debe ser modificado [TE-2005].

In Figure 3 it is shown how to traverse the same container object using 2 iterators. As each iterator is an object, it can maintain its state without interfering with other objects. Furthermore, the compiler is responsible for enforcing the constness of these iterators, as they should not change the object being traversed. Unlike Java, C++ has clearly defined the use of "const" to have the compiler prevent a programmer from modifying an object that must not be changed [TE-2005].

template <typename C> bool isPalindrome( const C& CCC ) {{ typedef typename C::const_iterator Iter; iterJava< Iter > itFwd, itBck; itFwd.set(CCC); itBck.set(CCC); itBck.setReverse(); while ( itFwd.hasNext() && itBck.hasNext() ) { if ( itFwd.next() != itBck.next() ) { return false; } } return ( !itFwd.hasNext() && !itBck.hasNext() ); }}

Figura 4

Como se muestra en la Figure 4, el método "setReverse()" y su sinónimo "setBackward()" de la clase "iterJava<>" sirven para que la iteración se haga de atrás hacia adelante en lugar de la forma natural, de adelante hacia atrás. No se incluye la operación "setForward()" porque no es válido utilizar "setReverse()" si ya la iteración comenzó, por lo que nunca es necesario invocar "setForward()". Además de los métodos observadores "isForward()" y "isBackward()", también se incluyen las operaciones de copia que es usual usar con cualquier clase.

As it is shown in Figure 4, methods "setReverse()" and its synonym "setBackward()" in class "iterJava<>" are used for the iteration to be carried out from back to front instead of the natural way, from front to back. There is no "setForward()" operation because it is not valid to use "setReverse()" if the iteration already started, so it is never necessary to invoke "setForward()". In addition to the observer methods "isForward()" and "isBackward()", a copy operations is also included, which is usually present in any class.

{{ // test::Tree_BF() TL::Tree<char> T; make_a_o(T); Tree_BF<char> iter; std::string L; iter.set(T); while ( iter.hasNext() ) { TL::Tree<char> S = iter.next(); L.push_back( *S ); } assertTrue( L == "abcdefghijklmno" && "Tree_BF" ); }}

T = a /|\ / / \ \ b c d e /|\ /|\ f g h i j k / \ l m / \ n o

Figura 5

Talvez la forma más simple de notar las cualidades de de la abstracción "iterJava<>" es examinar la forma no recursiva para recorrer un árbol, como se muestra en la Figura 5, en donde se ve que el patrón de iteración siempre es el mismo, independientemente de adónde o sobre qué se itera.

Perhaps the simplest way to realize the qualities of abstraction "iterJava<>" is to examine the non-recursive traversal of a tree, as shown in Figure 4.5, where it can be seen that the iteration pattern is always the same regardless of where or what is iterated on.

Implementación de "iterJava<>"

"iterJava<>" implementation

La operación de borrado "remove()" se llama diferente para los iteradores de la biblioteca estándar C++: "erase()". Debido a que la operación "erase()" tiene un funcionamiento que no es uniforme para todos los iteradores, queda como responsabilidad del programador que usa la clase "iterJava<>" determinar si la puede usar o no. Por ejemplo, al invocar "erase()" en una lista sus iteradores siguen siendo válidos, pero lo contrario ocurre si se usa "erase()" en un vector.

The erase operation "remove()" is named differently from C++ standard library iterators: "erase()". As "erase()" is an operation that does not have a uniform behaviour for all iterators, it is the responsibility of the programmer who uses the class "iterJava<>" determine whether it can be used. For example, when invoking "erase()" in a list its iterators remain valid, but the opposite happens when using "erase()" in a vector.

Los iteradores C++ están construidos en base a la clase "iterator_traits<>" en la que se indican varias cualidades del iterador. Debido a que el parámetro de la plantilla "iterJava<>" es un iterador, en lugar del contenedor que se recorre con el iterador, para declarar el tipo de valor que retorna "iterJava<>::next()" es necesario obtenerlo de los atributos descritos en la clase "iterator_traits<>" de la siguiente manera:     template <typename Iter>        typename std::iterator_traits<Iter>::reference           iterJava<Iter>::next();

C++ iterators are constructed based on class "iterator_traits<>" where iterator features are described. Because the parameter for template "iterJava<>" is an iterator, instead of the container traversed with the iterator, to declare the type of the value returned by "iterJava<>::next()" it is necessary to get it from the attributes described in the class "iterator_traits<>" as follows:     template <typename Iter>        typename std::iterator_traits<Iter>::reference           iterJava<Iter>::next();

Para implementar la operación de borrado "remove()" de los iteradores Java, en C++ es necesario recurrir a un truco que consiste en dotar a la clase "iterJava<>" de un convertidor a un iterador, de manera que el compilador C++ pueda compilar apropiadamente la invocación de la operación "erase()". Como se muestra en la Figura 2, para eliminar del contenedor el valor recién retornado por "next()" el programador Java escribe "iter.remove()" mientras que el programador C++ sí debe mencionar al contenedor "C.erase(iter)". El convertidor "operator Iter() const" retorna el iterador que denota el valor actual de iteración, y es con base en ese valor del iterador C++ que el método "erase()" elimina del contenedor el último valor retornado por la operación "next()". Un efecto equivalente puede obtenerse usando "C.erase(iter.current())", pues el método "current()" sirve para obtener, de nuevo, el valor que la última invocación de "next()" retornó.

To implement the delete operation "remove()" for Java iterators, in C++ it is necessary to resort to a trick including in class "iterJava<>" a conversion to an iterator, so the C++ compiler can properly compile the operation invocation for "erase()". As it is shown in Figure 2, to eliminate the value of container recently returned by "next()" a Java programmer writes "iter.remove()" while the C++ programmer should mention the container "C.erase(iter)". The conversion operator "operator Iter() const" returns the iterator that denotes the present value of iteration, and is based on the value of this C++ iterator that the "erase()" method removes the last value of the container returned by operation "next()". An equivalent effect can be obtained using "C.erase(iter.current())", as method "current()" gets, yet again, the value that the last invocation of "next()" returned.

{ // [0] [1] [2] [3] [4] [5] int V[] = { 0 , 1 , 2 , 3 , 4 }; int *it = &V[0]; // it = V+0; int *itEND = &V[5]; // itEND = V+dim(V) iterJava< int* > iter( it, itEND ); while ( iter.hasNext() ) { std::cout << it.next(); } }

Figura 6

¿Es posible que la clase "iterJava<>" incluya un puntero al contenedor que está recorriendo? La respuesta simple es "sí", pero la respuesta más completa es "mejor no". Como se puede ver en la parte inferior de la Figura 2, el parámetro de la clase "iterJava<>" es el tipo de iterador con el que se inicializa el objeto para realizar la iteración (que en este caso es la variable "iter"). Si se incluye en los campos de la clase "iterJava<>" un puntero al contenedor, sería necesario utilizar una clase diferente, por ejemplo "iterPtrJava<>" para usar punteros directamente; ya no sería posible compartir la misma clase para "iterJava<>" valores y punteros. En la Figura 6 se muestra que la forma de recorrer con un objeto "iterJava<>" los valores almacenados en un contenedor se hace de una forma similar a como se recorre un vector C++.

Is it possible for class "iterJava<>" to include a pointer to the container being taversed? The simple answer is yes, but the more complete answer is "better not". As it can be seen at the bottom of Figure 2, the "iterJava<>" class parameter is the type of iterator used to initialize the object used to perform the iteration (in this case, it is variable "iter"). If a pointer to the container is included as a field for class "iterJava<>", it would necessary to use a different class, eg. "iterPtrJava<>", to use pointers directly, and it would not be possible to share the same class "iterJava<>" for values and pointers. In Figure 3 it is shown that traversing a container with an "iterJava<>" object is done in a similar manner as traversing a C++ vector.

template <typename Iter> class iterJava { // Iterate using pointers/iterators protected: Iter itPrev; // Remember last value returned Iter itNext; // Next value to return Iter itEnd; // Past the last value bool isFwd; // false if it is a reverse_iterator };

Figura 7

El tamaño de un objeto "iterJava<>" es relativamente pequeño y lo usual es que los programadores usen relativamente pocas variables de iteración en sus programas. Por eso, en lugar de ahorrar espacio, dentro de un objeto "iterJava<>" se mantienen almacenados 3 iteradores que denotan 3 posiciones en el contenedor: "[itNext]" el valor siguiente de iteración, "[itPrev]" el valor que en la última ocasión retornó "next()" y "[itEnd]" la indicación del final de la iteración. Además, con el fin de permitir que un "iterJava<>" sirva para recorrer en orden inverso, también se incluye una bandera "[isFwd]" que indica si ese iterador avanza hacia adelante o hacia atrás. Como se muestra en la Figura 7, entre los campos de la clase "iterJava<>" no aparece ninguna referencia directa al contenedor.

The size of an "iterJava<>" object is relatively small and it is usual for programmers to use relatively few iteration variables in their programs. So, instead of saving space, inside an "iterJava<>" object 3 iterators are stored to recall 3 positions in the container: "[itNext]" the next iteration value, "[itPrev]" the value returned on the last invocation of "next()" and "[itEnd]" the indication of the end of the iteration. Furthermore, to allow a "iterJava<>" to go in reverse order, a flag "[isFwd]" is included to indicate whether the iterator moves forward or backward. As it is shown in Figure 6, among the fields for class "iterJava<>" there is no direct reference to the container.

// Cannot erase from constant list void const_compile_error( std::list<long> & L ) { typedef iterJava< std::list<long>::const_iterator > Iter; Iter iter( L.begin(),L.end() ); //_CONST_ while ( iter.hasNext() ) { L.erase(iter); // forbidden for const_iterator } assert( L.empty() ); }

Figura 8

Como solo se usa sola clase para usar cualquier tipo de iterador, surge una duda importante: si un contenedor C++ es un objeto constante, ¿evitará el compilador que sea modificado cuando se le recorre con un iterador "iterJava<>"? La respuesta es afirmativa; como esta clase es una plantilla, al instanciarla el compilador usa el iterador provisto en la declaración. Si se trata de usar un iterador no constante, el compilador emitirá errores cuando la referencia retornada por "next()" se use como un valor izquierdo (l-value) por lo que también impedirá que se use la variable de iteración con la operación "erase()", que requiere un iterador no constante como argumento. Por ejemplo, en la rutina de la Figura 8 el compilador emitirá el siguientes error:       ... no matching function for call to std::list<...>::erase(...)

As only a single class it used for any type of iterator, there arises an important question: if a C++ container is a constant object, will the compiler prevent it to be modified when traversed by an "iterJava<>" iterator? The answer is yes; as this class is a template, upon instantiation the compiler uses the iterator instance included in the declaration. If a non constant iterator is used, the compiler will issue an error when the reference returned by "next()" is used as a left value (l-value) and it will also prevent using the iteration variable for operation "erase()", which requires a non-constant iterator as an argument. For example, in the routine in Figure 7 the compiler will issue the following error:       ... no matching function for call to std::list<...>::erase(...)

Uso de "iterJava<>" como generador de iteración

Using "iterJava<>" as an iteration generator

Iterar sobre valores diversos usando la pareja { hasNext() next() } es tan simple que vale la pena usar este patrón de iteración aún si los valores no están almacenados en un contenedor de la biblioteca estándar C++. Por ejemplo, tiene mucho sentido usar este estilo de programación para obtener una secuencia de números aleatorios o para recorrer contenedores no lineales, como árboles y grafos.

Iterating over diverse values using the pair { hasNext() next() } is so simple that it is worth using this iteration pattern even if the values are not stored in a container in the C++ standard library. For example, it makes a lot of sense to use this programming style to get a sequence of random numbers or to traverse nonlinear containers, such as trees and graphs.

class Random { unsigned m_qty; ///< #. unsigned m_last; ///< Max. long m_val; ///< current(). public: Random( int n=1 , long seed=3145159 ) : m_qty(0), m_last(n) { srand(seed); } bool hasNext() const { return m_qty < m_last; } const long& next() { m_qty++; return (m_val = rand()) ; } };

void generateRandom( ) { Random iter( 15, 271828 ); while ( iter.hasNext() ) { std::cout << iter.next() << std::endl; } }

Figura 9

En la Figura 9 se muestra cuán sencillo es encapsular un generador de números aleatorios en un iterador Java; al final de este escrito se incluye el iterador "Tree_BF" para recorrer un árbol por niveles (breadth-first) que funciona para la clase árbol descrita en [DiMare-1997]. La clase "iterJava<>" también puede usarse en conjunción con prestigiosas bibliotecas C++ como Boost [Boost-2009].

In Figure 8 it is shown how easy it is to encapsulate a random number generator in a Java iterator; at the end of this paper it is included iterator "Tree_BF" to traverse a tree by levels (Breadth-First) which works for the tree class described in [DiMare-1997]. Class "iterJava<>" can also be used in conjunction with leading C++ libraries such as Boost [Boost-2009].

Enseñanza universitaria

Teaching at the university

En la Universidad de Costa Rica hemos escogido enseñar programación con una secuencia de 2 cursos. En el primero entrenamos a los estudiantes en el uso y construcción de algoritmos, y en el segundo les mostramos como reutilizar módulos a través de la abstracción y la especificación. Para el primero curso hemos escogido el lenguaje Java [King-1997] pues tiene las siguientes cualidades:

At the Universidad de Costa Rica we have chosen to teach programming with a sequence of 2 courses. In the first we train students in the use and construction of algorithms, and in the second we show them how to reuse modules through abstraction and specification. For the first course we chose the Java language [King-1997] because it has the following qualities:

Existen muy buenos libros de texto para el lenguaje [BK-2007], [Ceballos-2006], [Deitel-2007] Incluye la mayor parte de las construcciones sintácticas de un lenguaje de programación moderno. Existen muchos ambientes de desarrollo y depuración de programas para el lenguaje. El compilador hace un trabajo bastante decente de detección y reporte de errores con base en la verificación de tipos. Es un lenguaje popular tanto en la academia y la industria.

There are very good textbooks for the language [BK-2007], [Ceballos-2006], [Deitel-2007]. It includes most of the syntactic constructions of a modern programming language. There are many program development and debugging environments for the language. The compiler does a fairly decent job of detecting and reporting errors based on type checking. It is a popular language both in academia and industry.

Desde el segundo curso de programación y durante toda la carrera se utiliza C++ como la herramienta primordial de programación. Así se evita limitar a los alumnos a una máquina virtual que los separa de la realidad de la arquitectura de la máquina y de su sistema operativo. Cambiar de lenguaje del primer curso tiene varias desventajas que se manifiestan durante el segundo curso, entre las que se pueden destacar éstas:

From the second programming course and during the whole degree C++ is used as the primary tool for programming. This avoids limiting students to a virtual machine that separates them from the reality of the machine architecture and its operating system. Changing the languages of the first course has several disadvantages which manifest during the second course, among which the following can be highlighted:

Tanto estudiantes como profesores tienen la tendencia de concentrarse en la sintaxis del segundo lenguaje, para adaptarlo a las prácticas de programación asimiladas por los alumnos en el primer curso. Como algunas de las herramientas del segundo lenguaje son diferentes, a veces se pierde mucho tiempo tratando de lograr que la nueva herramienta tenga comportamientos similares a las viejas. Algunos paradigmas de programación del primer lenguaje se pierden porque el estilo de programación del segundo es diferente.

Both students and teachers have the tendency of focusing on the syntax of second language, to adapt it to the programming practices assimilated by pupils in the first course. As some of the tools for the second language are different, sometimes lot of time get lost trying to make the new tool to have a similar behaviour as the old one. Some programming paradigms for the first language get lost because the programming style for the second language is different.

Al cambiar al paradigma de programación C++, además de otras cosas, también se pierden los iteradores Java, pues los iteradores estilo C++ son punteros inteligentes, implementados como clases que sobrecargan las principales operaciones de los punteros { ++ -- * -> }, mientras que en Java se usan generadores { hasNext() next() }.

By changing to the C++ programming paradigm, among other things, Java iterators are also lost, since C++ style iterators are intelligent pointers, implemented as classes that overload the main operations on pointers { ++ -- * -> }, while Java uses generators { hasNext() next() }.

Conclusiones

Conclusions

En este trabajo se ha demostrado que no hace falta desechar los iteradores C++ para aprovechar las ventajas del patrón de iteración Java, que es simple, lo que facilita la especificación y uso de iteradores. El uso de la clase "iterJava<>" permite aprovechar esta potente abstracción de iteración para C++, lo que aumenta las herramientas disponibles para programadores C++ y le ayuda a obtener una mejor implementación. Más aún, debido a que C++ permite declarar referencias "const", la verificación de que no sea modificado un contenedor inmutable la hace el compilador.

In this work it has been demostrated that there is no need to discard C++ iterators to take advantage of the Java iteration pattern, which is simple, what facilitates iterator specification and usage. The use of class "iterJava<>" helps in taking advantage of this powerful iteration abstraction for C++, increasing the tools available for C++ programmers and helps them to get a better implementation. Moreover, because in C++ it is possible to declare "const" references, the verification that an immutable container is not modified is carried out by the compiler.

Si los estudiantes ya conocen el lenguaje Java es útil usar la clase "iterJava<>" en un segundo curso de programación C++. También es ventajoso incorporar el patrón de uso de los iteradores Java en la práctica diaria de cualquier programador C++, pues puede facilitar el incorporarle paralelismo a un algoritmo de iteración. La implementación "iterJava.h" que aquí se presenta cabe en un solo archivo de encabezado, es eficiente porque no usa métodos virtuales y está implementada usando métodos "inline", por lo que al usarla no se renuncia a la posibilidad de que el compilador genere mejor código objeto. Además, esta simple solución se puede aplicar inmediatamente sin necesidad de instalar programas o bibliotecas.

If students already know the Java language it is helpful to use class "iterJava<>" in a second course in C++ programming. It is also advantageous to incorporate the Java iterator pattern in the daily practice of any C++ programmer, as it can facilitate incorporating parallelism to an iteration algorithm. The "iterJava.h" implementation presented here fits into a single header file, is efficient because it has no virtual methods and it is implemented using "inline" methods, so using it does not require to give up to the possibility for the compiler to generate better object code. Furthermore, this simple solution can be applied immediately without having to install programs or libraries.

Agradecimientos

Acknowledgements

Alejandro Di Mare aportó varias observaciones y sugerencias importantes para mejorar este trabajo. Walter Wabe colaboró con la implementación de los iteradores { PLR - LPR - LRP } para la clase "TL::Tree". Tanto el Programa de Posgrado en Computación e Informática, como la Escuela de Ciencias de la Computación e Informática y la Universidad de Costa Rica aportaron fondos para realizar esta investigación.

Alejandro Di Mare made several important observations and suggestions for improving this work. Walter Wabe colaborated with the implementation of the iterators { PLR - LPR - LRP } for the "TL::Tree" class. The Graduate Program in Computación e Informática, the Escuela de Ciencias de la Computación e Informática and the Universidad de Costa Rica provided funding for this research.

Código fuente

Source code

iterJava.zip: [.zip]

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

http://www.di-mare.com/adolfo/p/iterJava/es/index.html

http://www.di-mare.com/adolfo/p/iterJava/en/index.html

---

iterJava.h: [.spanish] [.english] [.h] [.txt]

http://www.di-mare.com/adolfo/p/iterJava/es/iterJava_8h_source.html

http://www.di-mare.com/adolfo/p/iterJava/en/iterJava_8h_source.html

test_iterJava.cpp: [.spanish] [.english] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/iterJava/es/classtest__iterJava.html

http://www.di-mare.com/adolfo/p/iterJava/en/classtest__iterJava.html

---

Tree_L.h: [.spanish] [.english] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/iterJava/es/classTL_1_1Tree.html

http://www.di-mare.com/adolfo/p/iterJava/en/classTL_1_1Tree.html

Tree_BF.h: [.spanish] [.english] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/iterJava/es/Tree__BF_8h_source.html

http://www.di-mare.com/adolfo/p/iterJava/en/Tree__BF_8h_source.html

Tree_PLR.h: [.spanish] [.english] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/iterJava/es/Tree__PLR_8h_source.html

http://www.di-mare.com/adolfo/p/iterJava/en/Tree__PLR_8h_source.html

Tree_LPR.h: [.spanish] [.english] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/iterJava/es/Tree__LPR_8h_source.html

http://www.di-mare.com/adolfo/p/iterJava/en/Tree__LPR_8h_source.html

Tree_LRP.h: [.spanish] [.english] [.cpp] [.txt]

http://www.di-mare.com/adolfo/p/iterJava/es/Tree__LRP_8h_source.html

http://www.di-mare.com/adolfo/p/iterJava/en/Tree__LRP_8h_source.html

---

Doxygen:

ftp://ftp.stack.nl/pub/users/dimitri/doxygen-1.5.9-setup.exe

Indice    [-] Resumen [1] Introducción [2] Uso de iteradores [3] Decisiones de diseño para la clase "iterJava<>" [4] Implementación de "iterJava<>" [5] Uso de "iterJava<>" como generador de iteración [6] Enseñanza universitaria [-] Conclusiones [-] Agradecimientos [-] Código fuente Bibliografía Indice Acerca del autor Acerca de este documento Principio Indice Final

Index    [-] Abstract [1] Introduction [2] Iterator usage [3] Design decisions for the "iterJava<>" class [4] "iterJava<>" implementation [5] Using "iterJava<>" as an iteration generator [6] Teaching at the university [-] Conclusions [-] Acknowledgements [-] Source code Bibliography Index About the author About this document Begin Index End

Adolfo Di Mare <adolfo@di-mare.com>

Referencia:	Di Mare, Adolfo: Iteradores Java para C++, Artículo 65 de la Décima Conferencia del Latin American And Caribbean Consortium Of Engineering Institutions (Consorsio de Escuelas de Ingeniería de Latinoamérica y del Caribe), (LACCEI-2012), realizada del 23 al 27 de julio de 2012 en Universidad Tecnológica de Panamá, Panamá, Panamá.
Internet:	http://www.di-mare.com/adolfo/p/iterJava.htm http://www.laccei.org/LACCEI2012-Panama/RefereedPapers/RP065.pdf
Autor:	Adolfo Di Mare <adolfo@di-mare.com>
Contacto:	Apdo 4249-1000, San José Costa Rica Tel: (506) 2511-8000       Fax: (506) 2438-0139
Revisión:	ECCI-UCR, Agosto 2009
Visitantes: