Iterator pattern

⏱ Dedicación recomendada: 0 minutos
Esto considera el contenido visible y relevante, e ignora texto colapsado o marcado como opcional.

r8vnhill/collections-kt

Be lazy...

Puedes ejecutar el siguiente comando para crear el módulo

./gradlew setupStaticModule

Mientras se crean los archivos necesarios, puedes leer el código para saber qué está pasando.

import tasks.ModuleSetupTask

tasks.register<ModuleSetupTask>("setupIteratorModule") {
    description = "Creates the base module and files for the iterator pattern lesson"
    module.set("iterator")

    doLast {
        createFiles(
            "iterator",
            main to "Iterator.kt",
            main to "Iterable.kt",
        )
        createFiles(
            "library",
            main to "Library.kt",
            main to "Book.kt",
            main to "BookIterator.kt",
        )
    }
}

Preocúpate de que el plugin static esté aplicado en el archivo build.gradle.kts de tu proyecto.

./gradlew setupStaticModule

Preocúpate de que el nuevo módulo esté incluido en el archivo settings.gradle.kts.

El Iterator pattern es un patrón de diseño de comportamiento que permite recorrer los elementos de una colección de manera secuencial, sin exponer su representación interna (por ejemplo, si es una lista, conjunto o árbol). Este patrón proporciona una interfaz común para acceder a los elementos, lo que facilita recorrer estructuras de datos de manera consistente y uniforme.

Tipos de patrones de diseño

Los patrones de diseño se clasifican en varias categorías, dependiendo del tipo de problema que resuelven y la forma en que lo abordan. Estas categorías son las siguientes:

Patrones Creacionales: Están enfocados en los mecanismos de creación de objetos, asegurando que el proceso sea adecuado para la situación. Ejemplos comunes incluyen el patrón Singleton, que garantiza una única instancia de una clase, y el Builder, que facilita la construcción de objetos complejos.
Patrones Estructurales: Se enfocan en cómo las clases y los objetos se componen para formar estructuras más grandes y flexibles. Ejemplos incluyen el patrón Adapter, que permite la compatibilidad entre interfaces, y el Composite, que trata estructuras jerárquicas.
Patrones de Comportamiento: Estos patrones gestionan la interacción y responsabilidad entre objetos. Ejemplos son el patrón Observer, que define una relación de dependencia entre objetos, y el Strategy, que permite seleccionar algoritmos en tiempo de ejecución.
Patrones de Concurrencia: Abordan problemas asociados con la programación concurrente y la sincronización entre hilos. Ejemplos son el Active Object, que desacopla la ejecución de métodos del objeto, y el Monitor, que maneja la sincronización de acceso a recursos compartidos.

El patrón Iterator pertenece a los patrones de comportamiento, ya que se encarga de definir cómo los objetos interactúan entre sí para recorrer una colección de forma secuencial sin exponer su representación interna.

Problema que resuelve

Cuando se trabaja con diferentes tipos de colecciones, la forma de recorrerlas puede variar dependiendo de su implementación interna. El patrón iterador permite:

Ocultar la implementación interna de la colección: No es necesario conocer si es un array, lista enlazada o cualquier otro tipo de estructura.
Proporcionar una interfaz unificada para recorrer cualquier tipo de colección de forma segura.
Separar las responsabilidades: El iterador maneja la lógica de recorrido, mientras que la colección se enfoca en almacenar los elementos.

Estructura del patrón

El Patrón Iterador involucra los siguientes componentes principales:

Interfaz Iterator: Define los métodos que el iterador debe implementar, como hasNext() y next(), para permitir recorrer la colección.
Interfaz Iterable: Define un método para devolver un iterador asociado con la colección.
Clases Concretas de Iterador: Implementan los métodos definidos por la interfaz del iterador para manejar el recorrido específico de la colección.
Clases Concretas de Colección: Implementan la interfaz iterable para devolver un iterador específico de esa colección.

Ejemplo de implementación

Supongamos que tenemos una clase Book y queremos crear una biblioteca que pueda almacenar varios libros y recorrerlos utilizando el patrón iterador.

1. Definir el iterador

Luego, definimos la interfaz Iterator con los métodos hasNext() y next().

src/main/kotlin/com/github/username/iterator/Iterator.kt
package com.github.username.iterator

interface Iterator<T> {
    fun hasNext(): Boolean
    fun next(): T
}

2. Crear una colección iterable

Ahora definimos la interfaz Iterable, que tiene un método para obtener un iterador.

src/main/kotlin/com/github/username/iterator/Iterable.kt
package com.github.username.iterator

interface Iterable<T> {
    fun iterator(): Iterator<T>
}

3. Clase `Book` y la colección `Library`

Definimos una clase Book y una colección Library que implementa la interfaz Iterable.

src/main/kotlin/com/github/username/library/Book.kt
package com.github.username.library

data class Book(val title: String, val author: String)

src/main/kotlin/com/github/username/library/Library.kt
package com.github.username.library

class Library(vararg books: Book) : Iterable<Book> {
    private val books = books.toList()
    override fun iterator() = BookIterator(books)
}

4. Implementar el iterador de `Library`

Ahora implementamos la clase BookIterator que recorre los libros dentro de la biblioteca.

src/main/kotlin/com/github/username/library/BookIterator.kt
package com.github.username.library

class BookIterator(private val books: List<Book>) : Iterator<Book> {
    private var position = 0

    override fun hasNext(): Boolean = position < books.size

    override fun next(): Book {
        if (!hasNext()) throw NoSuchElementException()
        return books[position++]
    }
}

++i vs i++

En Kotlin, i++ devuelve el valor de i antes de incrementarlo, mientras que ++i primero incrementa i y luego devuelve el valor actualizado. En el caso de position++, se devuelve el valor actual de position y después se incrementa. Esto es útil cuando deseas realizar una acción con el valor actual antes de modificarlo.

Uso del patrón iterador

Ahora que tenemos la implementación completa, podemos recorrer la biblioteca usando el iterador:

fun main() {
    val library = Library(
        Book("Red Drragon", "Thomas Harris"),
        Book("At the Mountains of Madness", "H.P. Lovecraft"),
        Book("The Fellowship of the Ring", "J.R.R. Tolkien")
    )
    val iterator = library.iterator()

    while (iterator.hasNext()) {
        println("${iterator.next()}")
    }
}

Beneficios y limitaciones

Beneficios

Separación de responsabilidades: La colección no necesita preocuparse por cómo se recorre, lo que hace que sea más fácil modificar o extender el comportamiento del iterador.
Abstracción: Permite ocultar los detalles de la estructura de la colección, exponiendo solo los elementos a través de la interfaz Iterator.
Recorridos simultáneos: Se pueden crear múltiples iteradores que recorran la misma colección simultáneamente, sin interferir entre sí. Como cada iterador mantiene su propio estado, se puede paralelizar el recorrido de la colección de forma segura.

Limitaciones

Complejidad adicional: En algunos casos, puede añadir complejidad innecesaria, especialmente si la colección es simple y el recorrido es trivial.
Sobrecarga en recursos: Si la colección es grande o el iterador mantiene referencias adicionales, puede haber un impacto en el rendimiento.

Ejercicio: Recorrer un árbol binario con un iterador

Implementa un iterador para recorrer un árbol binario en orden BFS (Breadth-First Search). Por ejemplo, para el siguiente árbol:

El recorrido en orden debería devolver [1, 2, 3, 4, 5].

data class BinaryTree(
    val value: Int,
    val left: BinaryTree? = null,
    val right: BinaryTree? = null
) : Iterable<Int> {
    // Implementa aquí el iterador
}

Ver hints

Puedes utilizar una cola (Queue) para almacenar los nodos del árbol que aún no han sido visitados. Los siguientes métodos pueden serte útiles:
- add: Queue<E>.(E) → Boolean: Añade un elemento a la cola.
- poll: Queue<E>.() → E?: Extrae y elimina el primer elemento de la cola.
- isEmpty: Queue<E>.() → Boolean e Queue<E>.isNotEmpty: Queue<E>.() → Boolean: Verifican si la cola está vacía o no.

Un ejemplo de implementación de Queue en Kotlin es utilizar una lista enlazada (LinkedList):

import java.util.LinkedList
import java.util.Queue

val queue: Queue<Int> = LinkedList()
queue.add(1)
queue.add(2)
queue.add(3)
queue.poll() // Devuelve 1
queue.poll() // Devuelve 2
queue.poll() // Devuelve 3

Solución

import java.util.LinkedList
import java.util.Queue

data class BinaryTree(
    val value: Int,
    val left: BinaryTree? = null,
    val right: BinaryTree? = null
) : Iterable<Int> {

    override fun iterator(): Iterator<Int> = BinaryTreeIterator(this)

    private class BinaryTreeIterator(root: BinaryTree) : Iterator<Int> {
        private val queue: Queue<BinaryTree> = LinkedList()

        init {
            queue.add(root)
        }

        override fun hasNext(): Boolean = queue.isNotEmpty()

        override fun next(): Int {
            if (!hasNext()) throw NoSuchElementException()
            val node = queue.poll()
            node.left?.let { queue.add(it) }
            node.right?.let { queue.add(it) }
            return node.value
        }
    }
}

Patrón iterator en Kotlin

Kotlin incluye el patrón Iterator de forma nativa en su biblioteca estándar, lo que permite recorrer colecciones de manera segura y eficiente. Este patrón proporciona una forma estructurada de acceder a los elementos de una colección sin exponer su estructura interna.

La interfaz Iterable en Kotlin se define de la siguiente manera:

public interface Iterable<out T> {
    public operator fun iterator(): Iterator<T>
}

El método iterator es un operador que facilita el uso de la sintaxis del bucle for para iterar sobre colecciones. Cada vez que utilizas un bucle for con una colección, Kotlin llama internamente a este método para obtener el iterador.

Ejemplo de uso:

class Library(private val books: List<Book>) : Iterable<Book> {
    override fun iterator(): Iterator<Book> = books.iterator()
}

fun main() {
    val library: Library = TODO()
    for (book in library) {
        println(book)
    }
}

En este ejemplo, la colección library debe implementar la interfaz Iterable, lo que permite iterar sobre sus elementos utilizando el bucle for. Esto hace que el código sea más claro y fácil de leer, eliminando la necesidad de gestionar manualmente los índices o iteradores.

Bibliografías Recomendadas

🌐 "Iterators | Kotlin." Accedido: 27 de septiembre de 2024. [En línea]. Disponible en: https://kotlinlang.org/docs/iterators.html
🌐 "“Iterator”." Accedido: 24 de septiembre de 2024. [En línea]. Disponible en: https://refactoring.guru/design-patterns/iterator

Bibliografías Adicionales

📚 "Iterator". (2021). Alexander Shvets, en Dive Into Design Patterns, (v2021-2.28, pp. 289–303.)
📚 "5. Behavioral Patterns". (2011). Erich Gamma, Richard Helm, Ralph Johnson, y John Vlissides, en Design patterns: elements of reusable object-oriented software, (39. printing, pp. 221–349.) Addison-Wesley.

Problema que resuelve​

Estructura del patrón​

Ejemplo de implementación​

1. Definir el iterador​

2. Crear una colección iterable​

3. Clase Book y la colección Library​

4. Implementar el iterador de Library​

Uso del patrón iterador​

Beneficios y limitaciones​